Network coding allows the routers to mix the received information before forwarding them to the next nodes. Though this information mixing has been proven to maximize network throughput, it also introduces security challenges such as pollution attacks. A malicious node could insert a malicious packet into the system and this corrupted packet will propagate more quickly than in traditional copy-and-forward networks. Several authors have studied secure network coding from both information theoretic and probabilistic viewpoints. In this paper, we show that there are serious flaws in several of these schemes (the security ``proofs'' for these schemes were presented in these publications). Furthermore, we will propose a secure homomorphic authentication scheme for network coding.

Formal RFID security and privacy frameworks are fundamental to the design and analysis of robust RFID systems. In this paper, we develop a new definitional framework for RFID privacy in a rigorous and precise manner. Our framework is based on a zero-knowledge (ZK) formulation [7, 5] and incorporates the notions of adaptive completeness and mutual authentication. We provide meticulous justification of the new framework and contrast it with existing ones in the literature. In particular, we prove that our framework is stronger than the ind-privacy model of [14], which answers an open question posed in [14] for developing stronger RFID privacy models. Along the way we also try to clarify certain confusions and rectify several defects in the existing frameworks. Based on the protocol of [16], we propose an efficient RFID mutual authentication protocol and analyze its security and privacy. The methodology used in our analysis is of independent interest and can be applied to analyze other RFID protocols within the new framework.

We give a list of the Solinas prime numbers of the form $f(2^k)=2^m - 2^n \pm 1$, $m \leq 2000$, with small modular reduction weight $wt < 15$, and $k=8,16,32,64$, i.e., $k$ is a multiple of the computer integer arithmetic word size. These can be useful in the construction of cryptographic protocols.

Hamsi is one of the second round candidates of the SHA-3 competition. In this study, we present non-random differential properties for the compression function of the hash function Hamsi-256. Based on these properties, we first demonstrate a distinguishing attack that requires a few evaluations of the compression function and extend the distinguisher to 5 rounds with complexity $2^{83}$. Then, we present a message recovery attack with complexity of $2^{10.48}$ compression function evaluations. Also, we present a pseudo-preimage attack for the compression function with complexity $2^{254.25}$. The pseudo-preimage attack on the compression function is easily converted to a pseudo second preimage attack on Hamsi-256 hash function with the same complexity.

This paper presents an improved Cache trace attack on AES and CLEFIA by considering Cache miss trace information and S-box misalignment. In 2006, O. Ac&#305;içmez et al. present a trace driven Cache attack on AES first two rounds, and point out that if the Cache element number of the Cache block is 16, at most 48-bit of AES key can be obtained in the first round attack. Their attack is based on the ideal case when S-box elements are perfected aligned in the Cache block. However, this paper discovers that, the S-box elements are usually misaligned, and due to this feature and by considering Cache miss trace information, about 200 samples are enough to obtain full 128-bit AES key within seconds. In 2010, Chester Rebeiro et al. present the first trace driven Cache attack on C LEFIA by considering Cache hit information and obtain 128-bit key with 243 CLEFIA encryptions. In this paper, we present a new attack on CLEFIA by considering Cache miss information and S-box misalignment features, finally successfully obtain CLEFIA-128 key for about 220 samples within seconds.

Secure two-party authentication and key exchange are fundamental problems. Traditionally, the parties authenticate each other by means of their identities, using a public-key infrastucture (PKI). However, this is not always feasible or desirable: an appropriate PKI may not be available, or the parties may want to remain anonymous, and not reveal their identities. To address these needs, we introduce the notions of credential-authenticated identification (CAID) and key exchange (CAKE), where the compatibility of the parties' \emph{credentials} is the criteria for authentication, rather than the parties' \emph{identities} relative to some PKI. We formalize CAID and CAKE in the universal composability (UC) framework, with natural ideal functionalities, and we give practical, modularly designed protocol realizations. We prove all our protocols UC-secure in the adaptive corruption model with erasures, assuming a common reference string (CRS). The proofs are based on standard cryptographic assumptions and do not rely on random oracles. CAKE includes password-authenticated key exchange (PAKE) as a special case, and we present two new PAKE protocols. The first one is interesting in that it is uses completly different techniques than known practical PAKE protocols, and also achieves UC-security in the adaptive corruption model with erasures; the second one is the first practical PAKE protocol that provides a meaningful form of resilience against server compromise without relying on random oracles.

Several types of timing attacks have been published, but they are either in theory or hard to be taken into practice. In order to improve the feasibility of attack, this paper proposes an advance timing attack scheme on RSA-CRT with T-test statistical tool. Similar timing attacks have been presented, such as BB-Attack and Shindler’s attack, however none of them applied statistical tool in their methods with such efficiency, and showed the complete recovery in practice by attacking on RSA-CRT. With T-test, we enlarge the 0-1 gap, reduce the neighborhood size and improve the precision of decision. However, the most contribution of this paper is that our algorithm has an error detection property which can detect the erroneous decision of guessing qk and correct it. We could make the success rate of recovering q to be 100% indeed for interprocess timing attack, recovery 1024bits RSA key completely in practice.

In the paper on the example of the cryptosystem DES, the successful method of a cryptanalysis is presented. As a result, it is offered as a criterion of the cryptographic security to use a complexity of building and solving the system of Boolean functions, describing the cipher construction procedure.

Abdalla et al. proposed the first gateway-oriented password-based authenticated key exchange (GPAKE) protocol. The security goal of GPAKE is to securely establish a session key between the client and the gateway by the help of the authentication server without revealing any information of the password to the gateway. However, Byun et al. showed that the original GPAKE protocol was suspectable to an undetectable on-line dictionary attack by a malicious gateway. Recently, Abdalla et al. presented a new variant of the original GPAKE protocol to resist Byun et al.'s attack. In this letter, we show that the new GPAKE protocol is still vulnerable to another simple but powerful undetectable on-line dictionary attack. We then make a suggestion for improvement.

Almost cryptographic protocols are presented with security arguments. None of them, however, did explain why a protocol should like this, not like that. The reason is that there are short of any principles for designing and analyzing cryptographic protocols. In this paper, we put forth such a principle beyond security, called Less Parameters, which says that the involved parameters should be reduced as less as possible. Actually, the principle ensures a protocol better cost. In different scenarios, the principle is not easy to grasp. Intuitively, we advise to introduce public parameters as less as possible. In the light of the principle, we investigate some signatures. We believe the techniques developed in this paper will be helpful to better some cryptographic protocols.

We are interested in the integrity of the query results from an outsourced database service provider. Alice passes a set D of d-dimensional points, together with some authentication tag T, to an untrusted service provider Bob. Later, Alice issues some query over D to Bob, and Bob should produce the query result and a proof based on D and T. Alice wants to verify the integrity of the query result with the help of the proof, using only the private key. In this paper, we consider aggregate query conditional on multidimensional range selection. In its basic form, a query asks for the total number of data points within a d-dimensional range. We are concerned about the number of communication bits required and the size of the tag T. We give a scheme that requires O(d^2 log^2 N) communication bits to authenticate an aggregate count query conditional on d-dimensional range selection, where N is the number of points in the dataset. The security of our scheme relies on Generalized Knowledge of Exponent Assumption proposed by Wu and Stinson [1]. The low communication bandwidth is achieved due to a new functional encryption scheme, which exploits a special property of BBG [2] HIBE scheme. Besides counting, our scheme can be extended to support summing, finding of the minimum and usual (non-aggregate) range selection with similar complexity, and the proposed approach potentially can be applied to other queries by using suitable functional encryption schemes.

We show tight connections between several cryptographic primitives, namely encryption with weakly random keys, encryption with key-dependent messages (KDM), and obfuscation of point functions with multi-bit output(which we call multi-bit point functions, or MBPFs, for short). These primitives, which have been studied mostly separately in recent works, bear some apparent similarities, both in the flavor of their security requirements and in the flavor of their constructions and assumptions. Still, rigorous connections have not been drawn. Our results can be interpreted as indicating that MBPF obfuscators imply a very strong form of encryption that simultaneously achieves security for weakly-random keys and key-dependent messages as special cases. Similarly, each one of the other primitives implies a certain restricted form of MBPF obfuscation. Our results carry both constructions and impossibility results from one primitive to others. In particular: - The recent impossibility result for KDM security of Haitner and Holenstein (TCC '09) carries over to MBPF obfuscators. - The Canetti-Dakdouk construction of MBPF obfuscators based on a strong variant of the DDH assumption (EC '08) gives an encryption scheme which is secure w.r.t. any weak key distribution of super-logarithmic min-entropy (and in particular, also has very strong leakage resilient properties). - All the recent constructions of encryption schemes that are secure w.r.t. weak keys imply a weak form of MBPF obfuscators.

Recently, Yoon et al. and Wu proposed two improved remote mutual authentication and key agreement scheme for mobile devices on elliptic curve cryptosystem. In this paper, we show that Yoon et al.’s protocol fails to provide explicit key perfect forward secrecy and fails to achieve explicit key confirmation. We also point out Wu’s scheme decreases efficiency by using the double secret keys and is vulnerable to the password guessing attack and the forgery attack. In order to overcome the drawback, we proposed and improved scheme. Through the comparison with other protocol, we believe that our improved scheme is more suitable for real-life applications.

Straight line factoring algorithms include a variant Lenstra's elliptic curve method. This note proves lower bounds on the length of straight line factoring algorithms.

This paper presents a novel and robust chaos-based cryptosystem for secure transmitted images and four others versions. In the proposed block encryption/decryption algorithms, an 2D chaotic map is used to shuffle the image pixel positions. Then, substitution (confusion) and permutation (diffusion) operations on every block, with multiple rounds, are combined using two perturbed chaotic PWLCM maps. The perturbing orbit technique improves the dynamical statistical properties of generated chaotic sequences. The obtained error propagation in various standard cipher block modes demonstrates that the proposed cryptosystem including OFB, or CTR modes, is suitable to transmit cipher data over a corrupted digital channel. Finally, to quantify the security level of the proposed cryptosystem, many standard tools are performed and experimental results show that the suggested cryptosystem has a high security level.

Permutation is widely used in cryptographic algorithm. Recently, a number of candidate instructions have been proposed to efficient compute arbitrary bit permutations. Among these, we present the most attractive methods and having good inherent cryptographic properties. We propose to control it by the perturbed chaotic maps that we studied in [1]. Then, we measure the efficiency of the obtained chaotic permutation methods on a standard image. This study allows choosing a good chaotic permutation method to be used in a chaotic cryptosystem.

This paper presents a novel chaos-based cryptosystem for secure transmitted images. In the proposed block encryption/decryption algorithm, two chaotic permutation methods (key-dependant shift approach and Socek method) are used to shuffle the image pixel bits. These methods are controlled using a perturbed chaotic PWLCM map. The perturbing orbit technique improves the dynamical statistical properties of generated chaotic sequences. Our algorithm is based on tree encryption cryptosystems (Socek, Yang and Xiang algorithms). In this paper, we prove that the proposed cryptosystem overcomes the drawbacks of these algorithms. Finally, many standard tools are performed to quantify the security level of the proposed cryptosystem, and experimental results show that the suggested cryptosystem has a high security level.

BLAKE is a hash function selected by NIST as one of the 14 second round candidates for the SHA-3 Competition. In this paper, we follow a bottom-up approach to exhibit properties of BLAKE and of its building blocks: based on differential properties of the internal function G, we show that a round of BLAKE is a permutation on the message space, and present an efficient inversion algorithm. For 1.5 rounds we present an algorithm that finds preimages faster than in previous attacks. Discovered properties lead us to describe large classes of impossible differentials for two rounds of BLAKE’s internal permutation, and particular impossible differentials for five and six rounds, respectively for BLAKE- 32 and BLAKE-64. Then, using a linear and rotation-free model, we describe near-collisions for four rounds of the compression function. Finally, we discuss the problem of establishing upper bounds on the probability of differential characteristics for BLAKE.

Since Bellare and Rogaway presented the first formal security model for authenticated key exchange (AKE) protocols in 1993, many formal security models have been proposed. The extended Canetti-Krawczyk (eCK) model proposed by LaMacchia et al. is currently regarded as the strongest security model for two-party AKE protocols. In this paper, we first generalize the eCK model for tripartite AKE protocols, called teCK model, and enhance the security of the new model by adding a new reveal query. In the teCK model, the adversary has stronger powers, and can learn more secret information. Then we present a new tripartite AKE protocol based on the NAXOS protocol, called T-NAXOS protocol, and analyze its security in the teCK model under the random oracle assumption.

The Advanced Encryption Standard (AES) is the most widely deployed block cipher. It follows the modern iterated block cipher approach, iterating a simple round function multiple times. The last round of AES slightly differs from the others, as a linear mixing operation (called MixColumns) is omitted from it. Following a statement of the designers, it is widely believed that the omission of the last round MixColumns has no security implications. As a result, the majority of attacks on reduced-round variants of AES assume that the last round of the reduced-round version is free of the MixColumns operation. In this note we refute this belief, showing that the omission of MixColumns does affect the security of (reduced-round) AES. First, we consider a simple example of 1-round AES, where we show that the omission reduces the time complexity of an attack with a single known plaintext from 2^{48} to 2^{16}. Then, we examine several previously known attacks on 7-round AES-192 and show that the omission reduces their time complexities by a factor of 2^{16}.

In 2008, Groth and Sahai proposed a general methodology for constructing non-interactive zero-knowledge (and witness-indistinguishable) proofs in bilinear groups. While avoiding expensive NP-reductions, these proof systems are still inefficient due to a number of pairing computations required for verification. We apply recent techniques of batch verification to the Groth-Sahai proof systems and manage to improve significantly the complexity of proof verification. We give explicit batch verification formulas for generic Groth-Sahai equations (whose cost is less than a tenth of the original) and also for specific popular protocols relying on their methodology (namely Groth's group signatures and Belenkiy-Chase-Kohlweiss-Lysyanskaya's P-signatures).

Let $\mathbb{F}_{q}$ be a finite field, $\mathbb{F}_{q^s}$ be an extension of $\mathbb{F}_q$, let $f(x)\in \mathbb{F}_q[x]$ be a polynomial of degree $n$ with $\gcd(n,q)=1$. We present a recursive formula for evaluating the exponential sum $\sum_{c\in \mathbb{F}_{q^s}}\chi^{(s)}(f(x))$. Let $a$ and $b$ be two elements in $\mathbb{F}_q$ with $a\neq 0$, $u$ be a positive integer. We obtain an estimate of the exponential sum $\sum_{c\in \mathbb{F}^*_{q^s}}\chi^{(s)}(ac^u+bc^{-1})$, where $\chi^{(s)}$ is the lifting of an additive character $\chi$ of $\mathbb{F}_q$. Some properties of the sequences constructed from these exponential sums are provided also.

Fault attacks are one of the most severe attacks against secure embedded cryptographic implementations. Block ciphers such as AES, DES or public key algorithms such as RSA can be broken with as few as a single or a handful of erroneous computation results. Many countermeasures have been proposed both at the algorithmic level and using ad-hoc methods. In this paper, we address the problem of finding efficient countermeasures for RSA signature computations based on the Chinese Remainder Theorem for which one uses the inverse operation (verification) in order to secure the algorithm against fault attacks. We propose new efficient methods with associated security proofs in two different models; our methods protect against run-time errors, computation errors, and most permanent errors in the key parameters as well. We also extend our methods with infective computation strategies to secure the algorithm against double faults.

Let E be a non-supersingular elliptic curve over a finite field F_q. At CRYPTO 2009, Icart introduced a deterministic function F_q->E(F_q) which can be computed efficiently, and allowed him and Coron to define well-behaved hash functions with values in E(F_q). Some properties of this function rely on a conjecture which was left as an open problem in Icart's paper. We prove this conjecture as well as analogues for other hash functions. See also Farahashi, Shparlinski and Voloch, _On Hashing into Elliptic Curves_, for independent results of a similar form.

In 2003, Shen et al [4] proposed a timestamp-based password authentication scheme in which remote server does not need to store the passwords or veri&#64257;cation table for users authentication. Unfortunately Wang and Li[6], E.J.Yoon [8],Lieu et al.[3], analyzed independently the Shen Lin Scheme [4] and was found to be vulnerable to some deadly attacks. In continuation to it, this paper analyzes few attacks and &#64257;nally proposes an improved Timestamp- based password remote user authentication scheme so that it can withstand the existing forged attacks.

In this paper, we introduce the intermediate hashed Diffie-Hellman (IHDH) assumption which is weaker than the hashed DH (HDH) assumption (and thus the decisional DH assumption), and is stronger than the computational DH assumption. We then present two public key encryption schemes with short ciphertexts which are both chosen-ciphertext secure under this assumption. The short-message scheme has smaller size of ciphertexts than Kurosawa-Desmedt (KD) scheme, and the long-message scheme is a KD-size scheme with arbitrary plaintext length which is based on a weaker assumption than the HDH assumption.

In this note, we prove that the order of $x^p-x-1\in \F_p[x]$ is $\frac{p^p-1}{p-1}$, where $p$ is a prime and $\mathbb{F}_p$ is the finite field of size $p$. As a consequence, it is shown that $x^p-x-a\in \mathbb{F}_p[x]$ is primitive if and only if $a$ is a primitive element in $\mathbb{F}_p$.

This paper proposes practical chosen-ciphertext secure public-key encryption systems that are provably secure under the computational Diffie-Hellman assumption, in the standard model. Our schemes are conceptually simpler and more efficient than previous constructions. We also show that in bilinear groups the size of the public-key can be shrunk from n to 2\sqrt{n} group elements, where n is the security parameter.

Differential Fault Analysis against AES has been actively studied these years. Based on similar assumptions of the fault injection, different DFA attacks against AES have been proposed. However, it is difficult to understand how different attack results are obtained for the same fault injection. It is also difficult to understand the relationship between similar assumptions of fault injection and the corresponding attack results. This paper reviews the previous DFA attacks against AES based on the information theory, and gives a general and easy understanding of DFA attacks against AES. We managed to apply the analysis on DFA attacks on AES-192 and AES-256, and we propose the attack procedures to reach the theoretically minimal number of fault injections.

We adapt the CRT approach to computing Hilbert class polynomials to handle a wide range of class invariants. For suitable discriminants D, this improves its performance by a large constant factor, more than 200 in the most favourable circumstances. This has enabled record-breaking constructions of elliptic curves via the CM method, including examples with |D| > 10^{15}.

In this paper, we analyze the complexity of the construction of the $2^k$-diamond structure proposed by Kelsey and Kohno. We point out a flaw in their analysis and show that their construction may not produce the desired diamond structure. We then give a more rigorous and detailed complexity analysis of the construction of a diamond structure. For this, we appeal to random graph theory (in particular, to the theory of random intersection graphs), which allows us to determine sharp necessary and sufficient conditions for the {\it message complexity} (i.e., the number of hash computations required to build the required structure). We also analyze the {\it computational complexity} for constructing a diamond structure, which has not been previously studied in the literature. Finally, we study the impact of our analysis on herding and other attacks that use the diamond structure as a subroutine. Precisely, our results shows the following: \begin{enumerate} \item The message complexity for the construction of a diamond structure is $\sqrt{k}$ times more than the amount previously stated in literature. \item The time complexity is $n$ times the message complexity, where $n$ is the size of hash value. \end{enumerate} Due to the above two results, the herding attack~\cite{KK06} and the second preimage attack~\cite{ABFHKSZ08} on iterated hash functions have increased complexity. We also show that the message complexity of herding and second preimage attacks on ``hash twice'' is $n$ times the complexity claimed by~\cite{ABDK09}, by giving a more detailed analysis of the attack.

Two settings are traditionally considered for secure multiparty computation, depending on whether or not a majority of the parties are assumed to be honest. Protocols designed under this assumption provide ``full security'' (and, in particular, guarantee output delivery and fairness) when this assumption holds; unfortunately, these protocols are completely insecure if this assumption is violated. On the other hand, protocols tolerating an arbitrary number of corruptions do not guarantee fairness or output delivery even if only a \emph{single} party is dishonest. It is natural to wonder whether it is possible to achieve the ``best of both worlds'': namely, a single protocol that simultaneously achieves the best possible security in both the above settings. Here, we rule out this possibility (at least for general functionalities) but show some positive results regarding what \emph{can} be achieved.

Security and efficiency are two crucial issues in vehicular ad hoc networks. Many researches have devoted to these issues. However, we found that most of the proposed protocols in this area are insecure and can’t satisfy the anonymous property. Due to this observation, we propose a secure and anonymous method based on bilinear pairings to resolve the problems. After analysis, we conclude that our scheme is the most secure when compared with other protocols proposed so far.

Low bandwidth consumption is an important issue in a busy commercial network whereas time may not be so crucial, for example, the end-of-day financial settlement for commercial transactions in a day. In this paper, we construct a secure and low bandwidth-consumption k-out-of-n oblivious transfer scheme based on bilinear pairings. We analyze the security and efficiency of our scheme and conclude that our scheme is more secure and efficient in communication bandwidth consumption than most of the other existing oblivious transfer schemes that we know.

In this paper, we present two further improved differential fault analysis methods on Camellia by exploring fault width and depth. Our first method broadens the fault width of previous Camellia attacks, injects multiple byte faults into the rth round left register to recover multiple bytes of the rth round equivalent key, and obtains Camellia-128,192/256 key with at least 8 and 12 faulty ciphertexts respectively; our second method extends fault depth of previous Camellia attacks, injects one byte fault into the r-2th round left register to recover full 8 bytes of the rth round equivalent key, 5-6 bytes of the r-1th round equivalent key, 1 byte of the r-2th round equivalent key, and obtains Camellia-128,192/256 key with 4 and 6 faulty ciphertexts respectively. Simulation experiments demonstrate: due to its reversible permutation function, Camellia is vulnerable to multiple bytes fault attack, the attack efficiency is increased with fault width, this feature greatly improves fault attack’s practicalities; and due to its Feistel structure, Camellia is also vulnerable to deep single byte fault attack, 4 and 6 faulty ciphertexts are enough to reduce Camellia-128 and Camellia-192/256 key hypotheses to 222.2 and 231.8 respectively.

In 1994 Langford and Hellman introduced differential-linear cryptanalysis, which involves building a differential-linear distinguisher by concatenating a linear approximation with such a (truncated) differential that with probability 1 does not affect the bit(s) concerned by the input mask of the linear approximation. In 2002 Biham, Dunkelman and Keller presented an enhanced approach to include the case when the differential has a probability smaller than 1; and in 2005 they proposed several extensions of differential-linear cryptanalysis, including the high-order differential-linear analysis, the differential-bilinear analysis and the differential-bilinear-boomerang analysis. In this paper, we show that Biham et al.'s methodologies for computing the probabilities of a differential-linear distinguisher, a high-order differential-linear distinguisher, a differential-bilinear distinguisher and a differential-bilinear-boomerang distinguisher do not have the generality to describe the analytic techniques. Thus the previous cryptanalytic results obtained by using these techniques of Biham et al. are questionable. Finally, from a mathematical point we give general methodologies for computing the probabilities. The new methodologies lead to some better cryptanalytic results, for example, differential-linear attacks on 13-round DES and 10-round CTC2 with a 255-bit block size and key.

We propose a couple of general ways of constructing authentication schemes from actions of a semigroup on a set, without exploiting any specific algebraic properties of the set acted upon. Then we give several concrete realizations of this general idea, and in particular, we describe several authentication schemes with long-term private keys where forgery (a.k.a. impersonation) is NP-hard. Computationally hard problems that can be employed in these realizations include Graph Colorability, Diophantine Problem, and many others.

This paper describes a differential fault analysis (DFA) on AES with 192 and 256-bit keys. We show a new attack in which both 192 and 256-bit keys are retrieved within a feasible computational time. In order to verify the proposed attack and estimate the calculation time, we implement the proposed attack using C code on a PC. As a result, we successfully recover the original 192-bit key using 3 pairs of correct and faulty ciphertexts within 5 minutes, and 256-bit key using 2 pairs of correct and faulty ciphertexts and 2 pairs of correct and faulty plaintexts within 10 minutes.

In this paper, we revisit security notions for dedicated-key hash functions, considering two essential theoretical aspects; namely, formal definitions for security notions, and the relationships among them. Our contribution is twofold. First, we provide a new set of enhanced security notions for dedicated-key hash functions. The provision of this set of enhanced properties has been motivated by the introduction of enhanced target collision resistance (eTCR) property by Halevi and Krawczyk at Crypto 2006. We notice that the eTCR property does not belong to the set of the seven security notions previously investigated by Rogaway and Shrimpton at FSE 2004, namely: Coll, Sec, aSec, eSec, Pre, aPre and ePre. The fact that eTCR, as a new useful property, is the enhanced variant of the well-known TCR (a.k.a. eSec or UOWHF) property motivates one to investigate the possibility of providing enhanced variants for the other properties. We provide such an enhanced set of properties. Interestingly, there are six enhanced variants of security notions available, excluding ``ePre'' which can be demonstrated to be non-enhanceable. As the second and main part of our contribution, we provide a full picture of relationships (i.e. implications and separations) among the (thirteen) security properties including the (six) enhanced properties and the previously considered seven properties. The implications and separations are supported by formal proofs (reductions) and/or counterexamples in the concrete-security framework.

In SAC'08, an improved fast correlation attack on stream ciphers was proposed. This attack is based on the fast correlation attack proposed at Crypto'00 and combined with the fast Walsh transform. However, we found that the attack results are wrong. In this paper, we correct the results of the attack algorithm by analyzing it theoretically. Also we propose a threshold of the valid bias.

In this paper the number of $\overline{\mathbb{F}}_q$-isomorphism classes of Jacobi quartic curves, i.e., the number of Jacobi quartic curves with distinct $j$-invariants, over finite field $\mathbb{F}_q$ is enumerated.

This paper introduces the related-key boomerang and the related-key rectangle attacks. These new attacks can expand the cryptanalytic toolbox, and can be applied to many block ciphers. The main advantage of these new attacks, is the ability to exploit the related-key model twice. Hence, even ciphers which were considered resistant to either boomerang or related-key differential attacks may be broken using the new techniques. In this paper we present a rigorous treatment of the related-key boomerang and the related-key rectangle distinguishers. Following this treatment, we devise optimal distinguishing algorithms using the LLR (Logarithmic Likelihood Ratio) statistics. We then analyze the success probability under reasonable independence assumptions, and verify the computation experimentally by implementing an actual attack on a 6-round variant of KASUMI. The paper ends with a demonstration of the strength of our new proposed techniques with attacks on 10-round AES-192 and the full KASUMI.

Many RFID authentication protocols have been proposed to preserve security and privacy. Nevertheless, most of these protocols are analyzed and it is shown that they can not provide security against some RFID attacks. Moreover, some of the secure ones are criticized, because they suffer from scalability at the reader/server side as in tag identification or authentication phase they require a linear search depending on number of tags in the system. Recently, new authentication protocols have been presented to solve scalability issue, i.e. they require constant time for tag identification with providing security. In this paper, we analyze two of these new RFID authentication protocols SSM (very recently proposed by Song and Mitchell) and LRMAP (proposed by Ha et al.) and to the best of our knowledge, they have received no attacks yet. These schemes take O(1) work to authenticate a tag and are designed to meet the privacy and security requirements. The common point of these protocols is that normal and abnormal states are defined for tags. In the normal state, server authenticates the tag in constant time, while in the abnormal state, occurs rarely, authentication is realized with linear search. We show that, however, these authentication protocols do not provide untraceability which is one of their design objectives. We also discover that the SSM protocol is vulnerable to a desynchronization attack, that prevents a legitimate reader/server from authenticating a legitimate tag. Furthermore, in the light of these attacks, we conclude that allowing tags to be in different states may give clue to an adversary in tracing the tags, although such a design is preferred to achieve scalability and efficiency at the server side.

We describe a one-time signature scheme based on the hardness of the syndrome decoding problem, and prove it secure in the random oracle model. Our proposal can be instantiated on general linear error correcting codes, rather than restricted families like alternant codes for which a decoding trapdoor is known to exist.

We revisit narrow-pipe designs that are in practical use, and their security against preimage attacks. Our results are the best known preimage attacks on Tiger, MD4, and reduced SHA-2, with the result on Tiger being the first cryptanalytic shortcut attack on the full hash function. Our attacks runs in time $2^{188.8}$ for finding preimages, and $2^{188.2}$ for second-preimages. Both have memory requirement of order $2^{8}$, which is much less than in any other recent preimage attacks on reduced Tiger. Using pre-computation techniques, the time complexity for finding a new preimage or second-preimage for MD4 can now be as low as $2^{78.4}$ and $2^{69.4}$ MD4 computations, respectively. The second-preimage attack works for all messages longer than 2 blocks. To obtain these results, we extend the meet-in-the-middle framework recently developed by Aoki and Sasaki in a series of papers. In addition to various algorithm-specific techniques, we use a number of conceptually new ideas that are applicable to a larger class of constructions. Among them are (1) incorporating multi-target scenarios into the MITM framework, leading to faster preimages from pseudo-preimages, (2) a simple precomputation technique that allows for finding new preimages at the cost of a single pseudo-preimage, and (3) probabilistic initial structures, compared with deterministic ones, to enable more neutral words, and hence to reduce the attack time complexity. All the techniques developed await application to other hash functions. To illustrate this, we give as another example improved preimage attacks on SHA-2 members.

Based on re-keying techniques by Abdalla, Bellare, and Borst [1,2], we consider two black-box secure block cipher based symmetric encryption schemes, which we prove secure in the physically observable cryptography model. They are proven side-channel secure against a strong type of adversary that can adaptively choose the leakage function as long as the leaked information is bounded. It turns out that our simple construction is side-channel secure against all types of attacks that satisfy some reasonable assumptions. In particular, the security turns out to be negligible in the block cipher’s block size n, for all attacks. We also show that our ideas result in an interesting alternative to the implementation of block ciphers using different logic styles or masking countermeasures.

This paper provides a unified framework for {\em improving} \PRF(pseudorandom function) advantages of several popular MACs (message authentication codes) based on a blockcipher modeled as \tx{RP} (random permutation). In many known MACs, the inputs of the underlying blockcipher are defined to be some deterministic affine functions of previously computed outputs of the blockcipher. Keeping the similarity in mind, we introduce a class of \tx{ADE}s (affine domain extensions) and a wide subclass of \tx{SADE}s (secure \tx{ADE}) containing $\mathcal{C} = \{ \tx{CBC-MAC},\ \tx{GCBC}^*,\ \tx{OMAC},\ \tx{PMAC} \}$. We define a parameter $N(t,q)$ for each domain extension and show that all \tx{SADE}s have \PRF advantages $O(tq/2^n + N(t,q)/2^n)$ where $t$ is the total number of blockcipher computations needed for all $q$ queries. We prove that \PRF advantage of any \tx{SADE} is $O(t^2/2^n)$ by showing that $N(t,q)$ is always at most ${t \choose 2}$. We provide a better estimate $O(tq)$ of $N(t,q)$ for all members of $\mathcal{C}$ and hence these MACs have {\em improved advantages $O(tq / 2^n)$}. Our proposed bounds for \tx{CBC-MAC} and $\tx{GCBC}^*$ are better than previous best known bounds.

The privacy of most GSM phone conversations is currently protected by the 20+ years old A5/1 and A5/2 stream ciphers, which were repeatedly shown to be cryptographically weak. They will soon be replaced in third generation networks by a new A5/3 block cipher called KASUMI, which is a modified version of the MISTY cryptosystem. In this paper we describe a new type of attack called a sandwich attack, and use it to construct a simple distinguisher for 7 of the 8 rounds of KASUMI with an amazingly high probability of $2^{ -14}$. By using this distinguisher and analyzing the single remaining round, we can derive the complete 128 bit key of the full KASUMI by using only 4 related keys, $2^{26}$ data, $2^{30}$ bytes of memory, and $2^{32}$ time. These complexities are so small that we have actually simulated the attack in less than two hours on a single PC, and experimentally verified its correctness and complexity. Interestingly, neither our technique nor any other published attack can break MISTY in less than the $2^{128}$ complexity of exhaustive search, which indicates that the changes made by the GSM Association in moving from MISTY to KASUMI resulted in a much weaker cryptosystem.

The paper presents a differential cache trace attack against CLEFIA, a $128$ bit block cipher designed by Sony Corporation. The attack shows that such ciphers based on the generalized Feistel structures leak information of the secret key if the cache trace pattern is revealed to an adversary. The attack that we propose is a three staged attack and reveals the entire key with $2^{43}$ CLEFIA encryptions. The attack is simulated on an Intel Core 2 Duo Processor with a cache architecture with $32$ byte lines as a target platform.

LEX is a stream cipher proposed by Alex Biryukov. It was selected to phase 3 of the eSTREAM competition. LEX is based on the Advanced Encryption Standard (AES) block cipher and uses a methodology called "Leak Extraction", proposed by Biryukov himself. In this paper, we cryptanalyze LEX using two related keys. We have mounted a key recovery attack on LEX, which using $2^{54. 3}$ key streams yields a complete round key with $2^{102}$ operations. This improves the existing best cryptanalysis of LEX which needs $2^{112}$ operations to ascertain the key.

As a result of extensive analyses on cryptographic hash functions, NIST started an open competition for selecting a new standard hash function SHA-3. One important aspect of this competition is in evaluating hardware implementations and in collecting much attention of researchers in this area. For a fair comparison of the hardware performance, we propose an evaluation platform, a hardware design strategy, and evaluation criteria that must be consistent for all SHA-3 candidates. First, we define specifications of interface for the SASEBO-GII platform that are suitable for evaluating the performance in real-life hash applications, while one can also evaluate the performance of the SHA-3 core function that has an ideal interface. Second, we discuss the design strategy for high-throughput hardware implementations. Lastly, we explain the evaluation criteria to compare the cost and speed performance of eight SHA-3 candidates out of fourteen.

It is a difficult task to compute the $r$-th order nonlinearity of a given function with algebraic degree strictly greater than $r>1$. Even the lower bounds on the second order nonlinearity is known only for a few particular functions. We investigate the lower bounds on the second order nonlinearity of cubic Boolean functions $F_u(x)=Tr(\sum_{l=1}^{m}\mu_{l}x^{d_{l}})$, where $u_{l} \in F_{2^n}^{*}$, $d_{l}=2^{i_{l}}+2^{j_{l}}+1$, $i_{l}$ and $j_{l}$ are positive integers, $n>i_{l}> j_{l}$. Especially, for a class of Boolean functions $G_u(x)=Tr(\sum_{l=1}^{m}\mu_{l}x^{d_{l}})$, we deduce a tighter lower bound on the second order nonlinearity of the functions, where $u_{l} \in F_{2^n}^{*}$, $d_{l}=2^{i_{l}\gamma}+2^{j_{l}\gamma}+1$, $i_{l}> j_{l}$ and $\gamma\neq 1$ is a positive integer such that $gcd(n,\gamma)=1$. \\The lower bounds on the second order nonlinearity of cubic monomial Boolean functions, represented by $f_\mu(x)=Tr(\mu x^{2^i+2^j+1})$, $\mu\in F_{2^n}^*$, $i$ and $j$ are positive integers such that $i>j$, have recently (2009) been obtained by Gode and Gangopadhvay. Our results have the advantages over those of Gode and Gangopadhvay as follows. We first extend the results from monomial Boolean functions to Boolean functions with more trace terms. We further generalize and improve the results to a wider range of $n$. Also, our bounds are better than those of Gode and Gangopadhvay for monomial functions $f_\mu(x)$.

Direct anonymous attestation (DAA) is a special digital signature primitive, which provides a balance between signer authentication and privacy. One of the most interesting properties that makes this primitive attractive in practice is its construction of signers. The signer role of DAA is split between two entities, a principal signer (a trusted platform module (TPM)) with limited computational capability and an assistant signer (a computer platform into which the TPM is embedded) with more computational power but less security tolerance. Our first contribution in this paper is a new DAA scheme that requires very few TPM resources. In fact the TPM has only to perform two exponentiations for the DAA Join algorithm and three exponentiations for the DAA Signing algorithm. We show that this new scheme has better performance than the existing DAA schemes and is provable secure based on the $q$-SDH problem and DDH problem under the random oracle model. Our second contribution is a modification of the DAA game-based security model to cover the property of non-frameability.

Secure Multi-Party Computation (MPC) providing information theoretic security allows a set of n parties to securely compute an agreed function F over a finite field ${\mathbb F}$, even if t parties are under the control of a computationally unbounded active adversary. Asynchronous MPC (AMPC) is an important variant of MPC, which works over an asynchronous network. It is well known that perfect AMPC is possible if and only if n \geq 4t+1, while statistical AMPC is possible if and only if n \geq 3t+1. In this paper, we study the communication complexity of AMPC protocols (both statistical and perfect) designed with exactly n = 4t+1 parties. Our major contributions in this paper are as follows: 1. Asynchronous Verifiable Secret Sharing (AVSS) is one of the main building blocks for AMPC. In this paper, we design two AVSS protocols with 4t+1 parties: the first one is statistically secure and has non-optimal resilience, while the second one is perfectly secure and has optimal resilience. Both these schemes achieve a common interesting property, which was not achieved by the previous schemes. Specifically, our AVSS schemes allow to share a secret through a polynomial of degree at most d, where t \leq d \leq 2t. In contrast, the existing AVSS schemes can share a secret only through a polynomial of degree at most t. The new property of our AVSS simplifies the degree reduction step for the evaluation of multiplication gates in an AMPC protocol. 2.Using our statistical AVSS, we design a statistical AMPC protocol with n = 4t+1 which communicates O(n^2) field elements per multiplication gate. Though this protocol has non-optimal resilience, it significantly improves the communication complexity of the existing statistical AMPC protocols. 3. We then present a perfect AMPC protocol with n = 4t+1 (using our perfect AVSS scheme), which also communicates O(n^2) field elements per multiplication gate. This protocol improves on our statistical AMPC protocol as it has optimal resilience. To the best of our knowledge, this is the most communication efficient perfect AMPC protocol in the information theoretic setting.

This paper reports on the factorization of the 768-bit number RSA-768 by the number field sieve factoring method and discusses some implications for RSA.

In this paper, we consider the Frobenius endomorphism on twisted Edwards curve and give the characteristic polynomial of the map. Applying the Frobenius endomorphism on twisted Edwards curve, we construct a skew-Frobenius map defined on the quadratic twist of an twisted Edwards curve. Our results show that the Frobenius endomorphism on twisted Edwards curve and the skew-Frobenius endomorphism on quadratic twist of an twisted Edwards curve can be exploited to devise fast point multiplication algorithm that do not use any point doubling. As an application, the GLV method can be used for speeding up point multiplication on twisted Edwards curve.

Edwards curves have attracted great interest for their efficient addition and doubling formulas. Furthermore, the addition formulas are strongly unified or even complete, i.e., work without change for all inputs. In this paper, we propose the first halving algorithm on binary Edwards curves, which can be used for scalar multiplication. We present a point halving algorithm on binary Edwards curves in case of $d_1\neq d_2$. The halving algorithm costs about $3I+5M+4S$, which is slower than the doubling one. We also give a theorem to prove that the binary Edwards curves have no minimal two-torsion in case of $d_1= d_2$, and we briefly explain how to achieve the point halving algorithm using an improved algorithm in this case. Finally, we apply our halving algorithm in scalar multiplication with $\omega$-coordinate using Montgomery ladder.

In this paper, we present an \emph{online/offline identity-based signature} scheme for the wireless sensor network (WSN). We argue that due to significant reduction in computational and storage costs, our scheme is particularly suitable for the WSN environment with severely constrained resources. One of the interesting features of our scheme is that it provides \textit{multi-time} usage of the offline storage, which allows the signer to re-use the offline pre-computed information in polynomial time, in contrast to \textit{one-time} usage in all previous online/offline signature schemes. As evidence of the practicality and feasibility of our scheme to be used in the WSN environment, we provide an actual implementation result of our scheme on the MicaZ platform.

In this paper, we propose a new practical identity-based encryption scheme which is suitable for wireless sensor network (WSN). We call it \textit{Receiver-Bounded Online/Offline Identity-based Encryption} (RB-OOIBE). It splits the encryption process into two parts -- the offline and the online part. In the offline part, all heavy computations are done without the knowledge of the receiver's identity and the plaintext message. In the online stage, only light computations such as modular operation and symmetric key encryption are required, together with the receiver's identity and the plaintext message. Moreover, since each offline ciphertext can be re-used for the same receiver, the number of offline ciphertexts the encrypter holds only confines the number of receivers instead of the number of messages to be encrypted. In this way, a sensor node (with limited computation power and limited storage) in WSN can send encrypted data easily: A few offline ciphertexts can be computed in the manufacturing stage while the online part is light enough for the sensor to process. We propose an efficient construction for this new notion. The scheme can be proven selective-ID CCA secure in the standard model. Compared to previous online/offline identity-based encryption schemes, our scheme is exempt from a high storage requirement, which is proportional to the number of messages to be sent. The improvement is very significant if many messages are sent to few receivers.

\begin{abstract} Let assume that Alice, Bob, and Charlie, the three classical people of cryptography are not limited anymore to perform a finite number of computations on real computers, but are limited to $\alpha$ computations and to $\alpha$ bits of memory, where $\alpha$ is a fixed infinite cardinal. For example $\alpha = \aleph _0$ (the countable cardinal, i.e. the cardinal of $\mathbb {N}$ the set of integers), or $\alpha = \mathfrak {C}$ (the cardinal of the set $\mathbb {R}$ of real numbers). Is it possible to do secret key cryptography? Public key cryptography? Encryption? Authentication? Signatures? Is it possible to generalize the notion of one way function? The aim of this paper is to give some elements of answers to these questions. We will see for example that for secret key cryptography there are some simple solutions. However for public key cryptography the results are much less clear. \end{abstract}