In this work we deal with one-round key-agreement protocols, called Merkle's Puzzles, in the random oracle model, where the players Alice and Bob are allowed to query a random permutation oracle $n$ times. We prove that Eve can always break the protocol by querying the oracle $O(n^2)$ times. The long-time unproven optimality of the quadratic bound in the fully general, multi-round scenario has been proven recently by Barak and Mahmoody-Ghidary. The results in this paper have been found independently of their work.

In this paper we present a new method for scalar multiplication that uses a generic multibase representation to reduce the number of required operations. Further, a multibase NAF-like algorithm that efficiently converts numbers to such representation without impacting memory or speed performance is developed and showed to be sublinear in terms of the number of nonzero terms. Additional representation reductions are discussed with the introduction of window-based variants that use an extended set of precomputations. To realize the proposed multibase scalar multiplication with or without precomputations in the setting of Elliptic Curve Cryptosystems (ECC) over prime fields, we also present a methodology to derive fast composite operations such as tripling or quintupling of a point that require less memory than previous point formulae. Point operations are then protected against simple side-channel attacks using a highly efficient atomic structure. Extensive testing is carried out to show that our multibase scalar multiplication is the fastest method to date in the setting of ECC and exhibits a small footprint, which makes it ideal for implementation on constrained devices.

We present a new methodology to derive faster composite operations of the form dP+Q, where d is a small integer >= 2, for generic ECC scalar multiplications over prime fields. In particular, we present an efficient Doubling-Addition (DA) operation that can be exploited to accelerate most scalar multiplication methods, including multiscalar variants. We also present a new precomputation scheme useful for window-based scalar multiplications that is shown to achieve the lowest cost among all known methods using only one inversion. In comparison to the remaining approaches that use none or several inversions, our scheme offers higher performance for most common I/M ratios. By combining the benefits of our precomputation scheme and the new DA operation, we can save up to 6.2% in the scalar multiplication using fractional wNAF.

Here we propose an identity based signcryption scheme in the multi-PKG environment where sender and receiver receive public key from different PKG. We also define security models for our scheme and give security proofs in random oracle model.

We show an efficient secure two-party protocol, based on Yao's construction, which provides security against malicious adversaries. Yao's original protocol is only secure in the presence of semi-honest adversaries, and can be transformed into a protocol that achieves security against malicious adversaries by applying the compiler of Goldreich, Micali and Wigderson (the ``GMW compiler''). However, this approach does not seem to be very practical as it requires using generic zero-knowledge proofs. Our construction is based on applying cut-and-choose techniques to the original circuit and inputs. Security is proved according to the {\sf ideal/real simulation paradigm}, and the proof is in the standard model (with no random oracle model or common reference string assumptions). The resulting protocol is computationally efficient: the only usage of asymmetric cryptography is for running $O(1)$ oblivious transfers for each input bit (or for each bit of a statistical security parameter, whichever is larger). Our protocol combines techniques from folklore (like cut-and-choose) along with new techniques for efficiently proving consistency of inputs. We remark that a naive implementation of the cut-and-choose technique with Yao's protocol does \emph{not} yield a secure protocol. This is the first paper to show how to properly implement these techniques, and to provide a full proof of security. Our protocol can also be interpreted as a constant-round black-box reduction of secure two-party computation to oblivious transfer and perfectly-hiding commitments, or a black-box reduction of secure two-party computation to oblivious transfer alone, with a number of rounds which is linear in a statistical security parameter. These two reductions are comparable to Kilian's reduction, which uses OT alone but incurs a number of rounds which is linear in the depth of the circuit~\cite{Kil}.

In case of security analysis of hash functions, finding a good collision-inducing differential paths has been only focused on. However, it is not clear how differential paths of a hash function influence the securities of schemes based on the hash function. In this paper, we show that any differential path of a hash function can influence the securities of schemes based on the hash function. We explain this fact with the MD4 hash function. We first show that APOP-MD4 with a nonce of fixed length can be analyzed efficiently with a new differential path. Then we improve the result of the key-recovery attack on NMAC-MD4 described by Fouque {\em et al.} \cite{FoLeNg07} by combining new differential paths. Our results mean that good hash functions should have the following property : \textit{It is computationally infeasible to find differential a path of hash functions with a high probability}.

This paper presents fair traceable multi-group signatures (FTMGS), which have enhanced capabilities, compared to group and traceable signatures, that are important in real world scenarios combining accountability and anonymity. The main goal of the primitive is to allow multiple groups that are managed separately (managers are not even aware of the other ones), yet allowing users (in the spirit of the Identity 2.0 initiative) to manage what they reveal about their identity with respect to these groups by themselves. This new primitive incorporates the following additional features. - While considering multiple groups it discourages users from sharing their private membership keys through two orthogonal and complementary approaches. In fact, it merges functionality similar to credential systems with anonymous type of signing with revocation. - The group manager now mainly manages joining procedures, and new entities (called fairness authorities and consisting of various representatives, possibly) are involved in opening and revealing procedures. In many systems scenario assuring fairness in anonymity revocation is required. We specify the notion and implement it in the random oracle model.

Designing secure protocols in the Universal Composability (UC) framework confers many advantages. In particular, it allows the protocols to be securely used as building blocks in more complex protocols, and assists in understanding their security properties. Unfortunately, most existing models in which universally composable computation is possible (for useful functionalities) require a trusted setup stage. Recently, Katz [Eurocrypt '07] proposed an alternative to the trusted setup assumption: tamper-proof hardware. Instead of trusting a third party to correctly generate the setup information, each party can create its own hardware tokens, which it sends to the other parties. Each party is only required to trust that its own tokens are tamper-proof. Katz designed a UC commitment protocol that requires both parties to generate hardware tokens. In addition, his protocol relies on a specific number-theoretic assumption. In this paper, we construct UC commitment protocols for ``David'' and ``Goliath'': we only require a single party (Goliath) to be capable of generating tokens. We construct a version of the protocol that is secure for computationally unbounded parties, and a more efficient version that makes computational assumptions only about David (we require only the existence of a one-way function). Our protocols are simple enough to be performed by hand on David's side. These properties may allow such protocols to be used in situations which are inherently asymmetric in real-life, especially those involving individuals versus large organizations. Classic examples include voting protocols (voters versus ``the government'') and protocols involving private medical data (patients versus insurance-agencies or hospitals).

We consider the use of threshold signatures in ad-hoc and dynamic groups such as MANETs ("mobile ad-hoc networks"). While the known threshold RSA signature schemes have several properties that make them good candidates for deployment in these scenarios, we show that none of these schemes is practical enough for realistic use in these highly-constrained environments. In particular, this is the case of the most efficient of these threshold RSA schemes, namely, the one due to Shoup. Our contribution is in presenting variants of Shoup's protocol that overcome the limitations that make the original protocol unsuitable for dynamic groups. The resultant schemes provide the efficiency and flexibility needed in ad-hoc groups, and add the capability of incorporating new members (share-holders) to the group of potential signers without relying on central authorities. Namely, any threshold of existing members can cooperate to add a new member. The schemes are efficient, fully non-interactive and do not assume broadcast.

We explore the problem of secret-key distribution in _unidirectional_ channels, those in which a sender transmits information blindly to a receiver. We consider two approaches: (1) Key sharing across _space_, i.e., across simultaneously emitted values that may follow different data paths and (2) Key sharing across _time_, i.e., in temporally staggered emissions. Our constructions are of general interest, treating, for instance, the basic problem of constructing highly compact secret shares. Our main motivating problem, however, is that of practical key management in RFID (Radio-Frequency IDentification) systems. We describe the application of our techniques to RFID-enabled supply chains and a prototype privacy-enhancing system.

In this paper, we will present a cryptanalysis of CRUSH hash structure. Surprisingly, our attack could find pre-image for any desired length of internal message. Time complexity of this attack is completely negligible. We will show that the time complexity of finding a pre-image of any length is O(1). In this attack, an adversary could freely find a pre-image with the length of his own choice for any given message digits. We can also find second pre-image, collision, multi-collision in the same complexity with our attack. In this paper, we also introduce a stronger variant of the algorithm, and show that an adversary could still be able to produce collisions for this stronger variant of CRUSH hash structure with a time complexity less than a Birthday attack.

Since the introduction at Crypto'05 by Juels and Weis of the protocol HB+, a lightweight protocol secure against active attacks but only in a detection based-model, many works have tried to enhance its security. We propose here a new approach to achieve resistance against Man-in-The-Middle attacks. Our requirements - in terms of extra communications and hardware - are surprisingly low.

In this paper, a new identity-based proxy signcryption scheme is presented. The proposed scheme allows partial delegation of signing rights. Consequently, a signature created by the proxy signer is distinguishable from that created by the principal signer. This level of security is a common requirement in many applications to prevent malicious proxy agents from impersonating the principal signer. Moreover, the scheme is based on bilinear pairings over elliptic curves and thus smaller key sizes are required compared to schemes not utilizing elliptic curves. A revocation protocol of dishonest agents is given together with a renewal procedure for the proxies of honest agents. Finally, an application scenario for the proposed scheme is presented.

In this paper, we propose a new method for constructing a bilinear pairing over (hyper)elliptic curves, which we call the R-ate pairing. This pairing is a generalization of the Ate and Ate_i pairing, and also improves efficiency of the pairing computation. Using the R-ate pairing, the loop length in Miller's algorithm can be as small as ${\rm log}(r^{1 / \phi(k)})$ for some pairing-friendly elliptic curves which have not reached this lower bound. Therefore we obtain from 29 % to 69 % savings in overall costs compared to the Ate_i pairing. On supersingular hyperelliptic curves of genus 2, we show that this approach makes the loop length in Miller's algorithm shorter than that of the Ate pairing.

Manual authentication is a recently proposed model of communication motivated by the settings where the only trusted infrastructure is a low bandwidth authenticated channel, possibly realized by the aid of a human, that connects the sender and the receiver who are otherwise connected through an insecure channel and do not have any shared key or public key infrastructure. A good example of such scenarios is pairing of devices in Bluetooth. Manual authentication systems are studied in computational and information theoretic security model and protocols with provable security have been proposed. In this paper we extend the results in information theoretic model in two directions. Firstly, we extend a single receiver scenario to multireceiver case where the sender wants to authenticate the same message to a group of receivers. We show new attacks (compared to single receiver case) that can launched in this model and demonstrate that the single receiver lower bound $2\log(1/\epsilon)+O(1)$ on the bandwidth of manual channel stays valid in the multireceiver scenario. We further propose a protocol that achieves this bound and provides security, in the sense that we define, if up to $c$ receivers are corrupted. The second direction is the study of non-interactive protocols in unconditionally secure model. We prove that unlike computational security framework, without interaction a secure authentication protocol requires the bandwidth of the manual channel to be at least the same as the message size, hence non-trivial protocols do not exist.

Anonymity of consumers is an essential functionality that should be supported in e-cash systems, locations based services, electronic voting systems as well as digital rights management system. Privacy protection is an important aspect for wider acceptance of consumers of DRM systems. The concept of a blind signature is one possible cryptographic solution, yet it has not received much attention in the identity-based setting. In the identity-based setting, the public key of a user is derived from his identity, thus simplifying certificates management process compared to traditional public key cryptosystems. In this paper, a new blind identity-based signature scheme with message recovery based on bilinear pairings on elliptic curves is presented. The use of bilinear pairings over elliptic curves enables utilizing smaller key sizes, while achieving the same level of security compared to other schemes not utilizing elliptic curves. The scheme achieves computational savings compared to other schemes in literature. The correctness of the proposed scheme is validated and the proof of the blindness property is provided. Performance and other security related issues are also addressed.

We define a general model for consecutive delegations of signing rights with the following properties: The delegatee actually signing and all intermediate delegators remain anonymous. As for group signatures, in case of misuse, a special authority can open signatures to reveal the chain of delegations and the signer's identity. The scheme satisfies a strong notion of non-frameability generalizing the one for dynamic group signatures. We give formal definitions of security and show them to be satisfiable by constructing an instantiation proven secure under general assumptions in the standard model. Our primitive is a proper generalization of both group signatures and proxy signatures and can be regarded as non-frameable dynamic hierarchical group signatures.

\begin{abstract} Let $A$ be a Feistel scheme with $5$ rounds from $2n$ bits to $2n$ bits. In the present paper we show that for most such schemes $A$: \begin{enumerate} \item It is possible to distinguish $A$ from a random permutation from $2n$ bits to $2n$ bits after doing at most ${\cal O}(2^{n})$ computations with ${\cal O}(2^{n})$ non-adaptive {\bf chosen} plaintexts. \item It is possible to distinguish $A$ from a random permutation from $2n$ bits to $2n$ bits after doing at most ${\cal O}(2^{\frac{3n}{2}})$ computations with ${\cal O}(2^{\frac{3n}{2}})$ {\bf random} plaintext/ciphertext pairs. \end{enumerate} Since the complexities are smaller than the number $2^{2n}$ of possible inputs, they show that some generic attacks always exist on Feistel schemes with $5$ rounds. Therefore we recommend in Cryptography to use Feistel schemes with at least $6$ rounds in the design of pseudo-random permutations. We will also show in this paper that it is possible to distinguish most of $6$ round Feistel permutations generator from a truly random permutation generator by using a few (i.e. ${\cal O}(1)$) permutations of the generator and by using a total number of ${\cal O}(2^{2n})$ queries and a total of ${\cal O}(2^{2n})$ computations. This result is not really useful to attack a single $6$ round Feistel permutation, but it shows that when we have to generate several pseudo-random permutations on a small number of bits we recommend to use more than $6$ rounds. We also show that it is also possible to extend these results to any number of rounds, however with an even larger complexity. \end{abstract}

Oblivious transfer, first introduced by Rabin, is one of the basic building blocks of cryptographic protocols. In an oblivious transfer (or more exactly, in its 1-out-of-2 variant), one party known as the sender has a pair of messages and the other party known as the receiver obtains one of them. Somewhat paradoxically, the receiver obtains exactly one of the messages (and learns nothing of the other), and the sender does not know which of the messages the receiver obtained. Due to its importance as a building block for secure protocols, the efficiency of oblivious transfer protocols has been extensively studied. However, to date, there are almost no known oblivious transfer protocols that are secure in the presence of \emph{malicious adversaries} under the \emph{real/ideal model simulation paradigm} (without using general zero-knowledge proofs). Thus, \emph{efficient protocols} that reach this level of security are of great interest. In this paper we present efficient oblivious transfer protocols that are secure according to the ideal/real model simulation paradigm. We achieve constructions under the DDH, $N$th residuosity and quadratic residuosity assumptions, as well as under the assumption that homomorphic encryption exists.

Commitment schemes are arguably among the most important and useful primitives in cryptography. According to the computational power of receivers, commitments can be classified into three possible types: {\it computational hiding commitments, statistically hiding commitments} and {\it perfect computational commitments}. The fist commitment with constant rounds had been constructed from any one-way functions in last centuries, and the second with non-constant rounds were constructed from any one-way functions in FOCS2006, STOC2006 and STOC2007 respectively, furthermore, the lower bound of round complexity of statistically hiding commitments has been proven to be $\frac{n}{logn}$ rounds under the existence of one-way function. Perfectly hiding commitments implies statistically hiding, hence, it is also infeasible to construct a practically perfectly hiding commitments with constant rounds under the existence of one-way function. In order to construct a perfectly hiding commitments with constant rounds, we have to relax the assumption that one-way functions exist. In this paper, we will construct a practically perfectly hiding commitment with two-round from any one-way permutation. To the best of our knowledge, these are the best results so far.

We show that every construction of one-time signature schemes from a random oracle achieves black-box security at most $2^{(1+o(1))q}$, where $q$ is the total number of oracle queries asked by the key generation, signing, and verification algorithms. That is, any such scheme can be broken with probability close to $1$ by a (computationally unbounded) adversary making $2^{(1+o(1))q}$ queries to the oracle. This is tight up to a constant factor in the number of queries, since a simple modification of Lamport's one-time signatures (Lamport'79) achieves $2^{(0.812-o(1))q}$ black-box security using $q$ queries to the oracle. Our result extends (with a loss of a constant factor in the number of queries) also to the random permutation and ideal-cipher oracles. Since the symmetric primitives (e.g. block ciphers, hash functions, and message authentication codes) can be constructed by a constant number of queries to the mentioned oracles, as corollary we get lower bounds on the efficiency of signature schemes from symmetric primitives when the construction is black-box. This can be taken as evidence of an inherent efficiency gap between signature schemes and symmetric primitives.

We prove that every key agreement protocol in the random oracle model in which the honest users make at most $n$ queries to the oracle can be broken by an adversary who makes $O(n^2)$ queries to the oracle. This improves on the previous $\Omega(n^6)$ query attack given by Impagliazzo and Rudich (STOC '89) and resolves an open question posed by them. Our bound is optimal up to a constant factor since Merkle proposed a key agreement protocol in 1974 that can be easily implemented with $n$ queries to a random oracle and cannot be broken by any adversary who asks $o(n^2)$ queries.

Attribute based group signature (ABGS) is a a new generation of group signature schemes. In such a scheme the verifier could define the role of a signer within the group. He determines the attributes possessed by the member signing the document. In this paper we propose the first ABGS scheme with multi-authorities and define its security notions. We construct an ABGS that is proved to be fully traceable and fully anonymous. Our scheme is efficient and secure.

Consider an abstract storage device $\Sigma(\G)$ that can hold a single element $x$ from a fixed, publicly known finite group $\G$. Storage is private in the sense that an adversary does not have read access to $\Sigma(\G)$ at all. However, $\Sigma(\G)$ is non-robust in the sense that the adversary can modify its contents by adding some offset $\Delta \in \G$. Due to the privacy of the storage device, the value $\Delta$ can only depend on an adversary's {\em a priori} knowledge of $x$. We introduce a new primitive called an {\em algebraic manipulation detection} (AMD) code, which encodes a source $s$ into a value $x$ stored on $\Sigma(\G)$ so that any tampering by an adversary will be detected, except with a small error probability $\delta$. We give a nearly optimal construction of AMD codes, which can flexibly accommodate arbitrary choices for the length of the source $s$ and security level $\delta$. We use this construction in two applications: \begin{itemize} \item We show how to efficiently convert any linear secret sharing scheme into a {\em robust secret sharing scheme}, which ensures that no \emph{unqualified subset} of players can modify their shares and cause the reconstruction of some value $s'\neq s$. \item We show how how to build nearly optimal {\em robust fuzzy extractors} for several natural metrics. Robust fuzzy extractors enable one to reliably extract and later recover random keys from noisy and non-uniform secrets, such as biometrics, by relying only on {\em non-robust public storage}. In the past, such constructions were known only in the random oracle model, or required the entropy rate of the secret to be greater than half. Our construction relies on a randomly chosen common reference string (CRS) available to all parties. \end{itemize}

Let E be an elliptic curve defined over a finite field. Balasubramanian and Koblitz have proved that if the l-th roots of unity m_l is not contained in the ground field, then a field extension of the ground field contains m_l if and only if the l-torsion points of E are rational over the same field extension. We generalize this result to Jacobians of genus two curves. In particular, we show that the Weil- and the Tate-pairing are non-degenerate over the same field extension of the ground field. From this generalization we get a complete description of the l-torsion subgroups of Jacobians of supersingular genus two curves. In particular, we show that for l>3, the l-torsion points are rational over a field extension of degree at most 24.

The innovative HB+ protocol of Juels and Weis [10] extends device authentication to low-cost RFID tags. However, despite the very simple on-tag computation there remain some practical problems with HB+ and despite an elegant proof of security against some limited active attacks, there is a simple man-in-the-middle attack due to Gilbert et al. [8]. In this paper we consider improvements to HB+ in terms of both security and practicality. We introduce a new protocol that we denote random-HB#. This proposal avoids many practical drawbacks of HB+, remains provably resistant to attacks in the model of Juels and Weis, and at the same time is provably resistant to a broader class of active attacks that includes the attack of [8]. We then describe an enhanced variant called HB# which offers practical advantages over HB+.

A blind signature scheme is a cryptographic protocol for obtaining a signature from a signer such that the signer's view of the protocol cannot be linked to the resulting message signature pair. In this paper we have proposed two blind signature schemes using Braid groups. The security of given schemes depends upon conjugacy search problem in Braid groups.

An explicit construction of pairing-friendly hyperelliptic curves with ordinary Jacobians was firstly given by D.~Freeman. In this paper, we give other explicit constructions of pairing-friendly hyperelliptic curves with ordinary Jacobians based on the closed formulae for the order of the Jacobian of a hyperelliptic curve of type $y^2=x^5+ax$. We present two methods in this paper. One is an analogue of the Cocks-Pinch method and the other is a cyclotomic method. By using these methods, we construct a pairing-friendly hyperelliptic curve $y^2=x^5+ax$ over a finite prime field ${¥mathbb F}_p$ whose Jacobian is ordinary and simple over ${¥mathbb F}_p$ with a prescribed embedding degree. Moreover, the analogue of the Cocks-Pinch produces curves with $¥rho¥approx 4$ and the cyclotomic method produces curves with $3¥le ¥rho¥le 4$.

Let E be an elliptic curve defined over a finite field. Balasubramanian and Koblitz have proved that if the l-th roots of unity m_l is not contained in the ground field, then a field extension of the ground field contains m_l if and only if the l-torsion points of E are rational over the same field extension. We generalize this result to Jacobians of genus two curves with complex multiplication. In particular, we show that the Weil- and the Tate-pairing on such a Jacobian are non-degenerate over the same field extension of the ground field.

Proxy signature schemes allow delegation of signing rights. The paper proposes the notion of Identity Based Strong Bi-Designated Verifier Proxy Signature (ID-SBDVPS) schemes. In such schemes, only the two designated verifiers can verify that the proxy signer on behalf of the original signer signed the message but none of them is able to convince anyone else of this fact. The paper proposes nine such schemes and analyses the computational efficiency of each.

While recent timed-release encryption (TRE) schemes are implicitly supported by a certificateless encryption (CLE) mechanism, the security models of CLE and TRE differ and there is no generic transformation from a CLE to a TRE. This paper gives a generalized model for CLE that fulfills the requirements of TRE. This model is secure against adversaries with adaptive trapdoor extraction capabilities, decryption capabilities for arbitrary public keys, and partial decryption capabilities. It also supports hierarchical identifiers. We propose a concrete scheme under our generalized model and prove it secure without random oracles, yielding the first strongly-secure security-mediated CLE and the first TRE in the standard model. In addition, our technique of partial decryption is different from the previous approach.

Generally speaking, the probability of a differential path determines an upper bound for the expected workload and thus for the true risk potential of a differential attack. In particular, if the expected workload seems to be in a borderline region between practical feasibility and non-feasibility it is desirable to know the path probability as exact as possible. We present a generally applicable approach to determine at least almost exact probabilities of differential paths where we focus on (near-)collision paths for Merkle-Damgard-type hash functions. Our results show both that the number of bit conditions provides only a rough estimate for the true path probability and that the IV may have significant impact on the path probability. For MD5 we verified the effectivity of our approach experimentally. An abbreviated version [GIS4], which in particular omits proofs, technical details and several examples, will appear in the proceedings of the security conference 'Sicherheit 2008'.

In the recent years, side channel analysis has received a lot of attention, and attack techniques have been improved. Side channel analysis of second order is now successful in breaking implementations of block ciphers supposed to be effectively protected. This progress shows not only the practicability of second order attacks, but also the need for provably secure countermeasures. Surprisingly, while many studies have been dedicated to the attacks, only a few papers have been published about the dedicated countermeasures. In fact, only the method proposed by Schramm and Paar at CT-RSA 2006 enables to thwart second order side channel analysis. In this paper, we introduce two new methods which constitute a worthwhile alternative to Schramm and Paar's proposition. We prove their security in a strong security model and we exhibit a way to signifficantly improve their efficiency by using the particularities of the targeted architectures. Finally, we argue that the introduced methods allow to efficiently protect a wide variety of block ciphers, including AES.

We propose two constructions of chosen-ciphertext secure identity-based encryption (IBE) schemes. Our schemes have a security proof in the standard model, yet they offer performance competitive with all known random-oracle based schemes. The efficiency improvement is obtained by combining modifications of the IBE schemes by Waters and Gentry with authenticated symmetric encryption.

To reduce bandwidth in elliptic curve cryptography one can transmit only $x$-coordinates of points (or $x$-coordinates together with an extra bit). For further computation using the points one can either recover the $y$-coordinates by taking square roots or one can use point multiplication formulae which use $x$-coordinates only. We consider how to efficiently use point compression in pairing-based cryptography. We give a method to compute compressed Weil pairings using $x$-coordinates only. We also show how to compute the compressed Tate and ate pairings using only one $y$-coordinate. Our methods are more efficient than taking square roots when the embedding degree is small. We implemented the algorithms in the case of embedding degree 2 curves over $\F_p$ where $p \equiv 3 \pmod{4}$ and found that our methods are $10-15\%$ faster than the analogous methods using square roots.

A disjunctive multi-level secret sharing scheme divides users into different levels. Each level L is associated with a threshold t_L, and a group of users can only recover the secret if, for some L, there are at least t_L users at levels 0....L in the group. We present a simple ideal disjunctive multi-level secret sharing scheme -- in fact, the simplest and most direct scheme to date. It is the first polynomial-time solution that allows the dealer to add new users dynamically. Our solution is by far the most efficient; the dealer must perform O(t) field operations per user, where t is the highest threshold in the system. We demonstrate the simplicity of our scheme by extending our construction into a distributed commitment scheme using standard techniques.

The stream cipher RC4 was designed by R.~Rivest in 1987, and it has a very simple and elegant structure. It is probably the most deployed cipher on the Earth. ~~~~In this paper we analyse the class RC4-$N$ of RC4-like stream ciphers, where $N$ is the modulus of operations, as well as the length of internal arrays. Our new attack is a state recovery attack which accepts the keystream of a certain length, and recovers the internal state. For the original RC4-256, our attack has total complexity of around $2^{241}$ operations, whereas the best previous attack needs $2^{779}$ of time. Moreover, we show that if the secret key is of length $N$ bits or longer, the new attack works faster than an exhaustive search. The algorithm of the attack was implemented and verified on small cases.

This paper introduces EECM-MPFQ, a fast implementation of the elliptic-curve method of factoring integers. EECM-MPFQ uses fewer modular multiplications than the well-known GMP-ECM software, takes less time than GMP-ECM, and finds more primes than GMP-ECM. The main improvements above the modular-arithmetic level are as follows: (1) use Edwards curves instead of Montgomery curves; (2) use extended Edwards coordinates; (3) use signed-sliding-window addition-subtraction chains; (4) batch primes to increase the window size; (5) choose curves with small parameters and base points; (6) choose curves with large torsion.

In many applications, it is desirable to work with signatures that are both short, and yet where many messages from different signers be verified very quickly. RSA signatures satisfy the latter condition, but are generally thousands of bits in length. Recent developments in pairing-based cryptography produced a number of short signatures which provide equivalent security in a fraction of the space. Unfortunately, verifying these signatures is computationally intensive due to the expensive pairing operation. In an attempt to simultaneously achieve "short and fast" signatures, Camenisch, Hohenberger and Pedersen (Eurocrypt 2007) showed how to batch verify two pairing-based schemes so that the total number of pairings was independent of the number of signatures to verify. In this work, we present both theoretical and practical contributions. On the theoretical side, we introduce new batch verifiers for a wide variety of regular, identity-based, group, ring and aggregate signature schemes. These are the first constructions for batching group signatures, which answers an open problem of Camenisch et al. On the practical side, we implement each of these algorithms and compare each batching algorithm to doing individual verifications. Our goal is to test whether batching is practical; that is, whether the benefits of removing pairings significantly outweigh the cost of the additional operations required for batching, such as group membership testing, randomness generation, and additional modular exponentiations and multiplications. We experimentally verify that the theoretical results of Camenisch et al. and this work, indeed, provide an efficient, effective approach to verifying multiple signatures from (possibly) different signers.

We study an adaptive variant of oblivious transfer in which a sender has N messages, of which a receiver can adaptively choose to receive k one-after-the-other, in such a way that (a) the sender learns nothing about the receiver’s selections, and (b) the receiver only learns about the k requested messages. We propose two practical protocols for this primitive that achieve a stronger security notion than previous schemes with comparable efficiency. In particular, by requiring full simulatability for both sender and receiver security, our notion prohibits a subtle selective-failure attack not addressed by the security notions achieved by previous practical schemes. Our first protocol is a very efficient generic construction from unique blind signatures in the random oracle model. The second construction does not assume random oracles, but achieves remarkable efficiency with only a constant number of group elements sent during each transfer. This second construction uses novel techniques for building efficient simulatable protocols.

This paper introduces ``twisted Edwards curves,'' a generalization of the recently introduced Edwards curves; shows that twisted Edwards curves include more curves over finite fields, and in particular every elliptic curve in Montgomery form; shows how to cover even more curves via isogenies; presents fast explicit formulas for twisted Edwards curves in projective and inverted coordinates; and shows that twisted Edwards curves save time for many curves that were already expressible as Edwards curves.

Bellare and Micciancio's MuHASH applies a pre-existing hash function to map indexed message blocks into a secure group. The resulting hash is the product. Bellare and Micciancio proved, in the random oracle model, that MuHASH is collision-resistant if the group's discrete logarithm problem is infeasible. MuHASH, however, relies on a pre-existing hash being collision resistant. In this paper, we remove such a reliance by replacing the pre-existing hash with a block cipher under a fixed key. We adapt Bellare and Micciancio's collision-resistance proof to the ideal cipher model. Preimage resistance requires us to add a further modification.

In this paper I study the MOR cryptosystem using the special linear group over finite fields. At our current state of knowledge, I show that the MOR cryptosystem is more secure than the ElGamal cryptosystem over finite fields.

Xoring two permutations is a very simple way to construct pseudorandom functions from pseudorandom permutations. The aim of this paper is to get precise security results for this construction. Since such construction has many applications in cryptography (see \cite{BI,BKrR,HWKS,SL} for example), this problem is interesting both from a theoretical and from a practical point of view. In \cite{SL}, it was proved that Xoring two random permutations gives a secure pseudorandom function if $m \ll 2^{\frac {2n}{3}}$. By ``secure'' we mean here that the scheme will resist all adaptive chosen plaintext attacks limited to $m$ queries (even with unlimited computing power). More generally in \cite{SL} it is also proved that with $k$ Xor, instead of 2, we have security when $m \ll 2^{\frac {kn}{k+1}}$. In this paper we will prove that for $k=2$, we have in fact already security when $m \ll O(2^n)$. Therefore we will obtain a proof of a similar result claimed in \cite{BI} (security when $m\ll O(2^n /n^{2/3})$). Moreover our proof is very different from the proof strategy suggested in \cite{BI} (we do not use Azuma inequality and Chernoff bounds for example, but we will use the ``$H_{\sigma}$ technique'' as we will explain), and we will get precise and explicit $O$ functions. Another interesting point of our proof is that we will show that this (cryptographic) problem of security is directly related to a very simple to describe and purely combinatorial problem.

\begin{abstract} Xoring the output of $k$ permutations, $k\geq 2$ is a very simple way to construct pseudo-random functions (PRF) from pseudo-random permutations (PRP). Moreover such construction has many applications in cryptography (see \cite{BI,BKrR,HWKS,SL} for example). Therefore it is interesting both from a theoretical and from a practical point of view, to get precise security results for this construction. In this paper, we will describe the best attacks that we have found on the Xor of $k$ random $n$-bit to $n$-bit permutations. When $k=2$, we will get an attack of computational complexity $O(2^n)$. This result was already stated in \cite{BI}. On the contrary, for $k \geq 3$, our analysis is new. We will see that the best known attacks require much more than $2^n$ computations when not all of the $2^n$ outputs are given, or when the function is changed on a few points. We obtain like this a new and very simple design that can be very usefull when a security larger than $2^n$ is wanted, for example when $n$ is very small. \end{abstract}

In this paper we present a new method to construct a polynomial $u(x) \in \mathbb{Z}[x]$ which will make $\mathrm{\Phi}_{k}(u(x))$ reducible. We construct a finite separable extension of $\mathbb{Q}(\zeta_{k})$, denoted as $\mathbb{E}$. By primitive element theorem, there exists a primitive element $\theta \in \mathbb{E}$ such that $\mathbb{E}=\mathbb{Q}(\theta)$. We represent the primitive $k$-th root of unity $\zeta_{k}$ by $\theta$ and get a polynomial $u(x) \in \mathbb{Q}[x]$ from the representation. The resulting $u(x)$ will make $\mathrm{\Phi}_{k}(u(x))$ factorable.

We consider one-round identity-based key exchange protocols secure in the standard model. The security analysis uses the powerful security model of Canetti and Krawczyk and a natural extension of it to the ID-based setting. It is shown how KEMs can be used in a generic way to obtain two different protocol designs with progressively stronger security guarantees. A detailed analysis of the performance of the protocols is included; surprisingly, when instantiated with specific KEM constructions, the resulting protocols are competitive with the best previous schemes that have proofs only in the random oracle model.

In frameworks for universal composability, complex protocols can be built from sub-protocols in a modular way using composition theorems. However, as first pointed out and studied by Canetti and Rabin, this modular approach often leads to impractical implementations. For example, when using a functionality for digital signatures within a more complex protocol, parties have to generate new verification and signing keys for every session of the protocol. This motivates to generalize composition theorems to so-called joint state (composition) theorems, where different copies of a functionality may share some state, e.g., the same verification and signing keys. In this paper, we present a joint state theorem which is more general than the original theorem of Canetti and Rabin, for which several problems and limitations are pointed out. We apply our theorem to obtain joint state realizations for three functionalities: public-key encryption, replayable public-key encryption, and digital signatures. Unlike most other formulations, our functionalities model that ciphertexts and signatures are computed locally, rather than being provided by the adversary. To obtain the joint state realizations, the functionalities have to be designed carefully. Other formulations proposed in the literature are shown to be unsuitable. Our work is based on the IITM model. Our definitions and results demonstrate the expressivity and simplicity of this model. For example, unlike Canetti's UC model, in the IITM model no explicit joint state operator needs to be defined and the joint state theorem follows immediately from the composition theorem in the IITM model.

We propose to apply an information theoretic metric to the evaluation of side-channel resistant logic styles. Due to the long design and development time required for the physical evaluation of such hardware countermeasures, our analysis is based on simulations. Although they do not aim to replace the need of actual measurements, we show that simulations can be used as a meaningful first step in the validation chain of a cryptographic product. For illustration purposes, we apply our methodology to gate-level simulations of different logic styles and stress that it allows a significant improvement of the previously considered evaluation methods. In particular, our results allow putting forward the respective strengths and weaknesses of actual countermeasures and determining to which extent they can practically lead to secure implementations (with respect to a noise parameter), if adversaries were provided with simulation-based side-channel traces. Most importantly, the proposed methodology can be straightforwardly adapted to adversaries provided with any other kind of leakage traces (including physical ones).

This paper describes several constructions of tweakable strong pseudorandom permutations (SPRPs) built from different modes of operations of a block cipher and suitable universal hash functions. For the electronic codebook (ECB) based construction, an invertible blockwise universal hash function is required. We simplify an earlier construction of such a function described by Naor and Reingold. The other modes of operations considered are the counter mode and the output feedback (OFB) mode. All the constructions make the same number of block cipher calls and the same number of multiplications. Combined with a class of polynomials defined by Bernstein, the new constructions provide the currently best known algorithms for the important practical problem of disk encryption.

In this paper we don't examine security of Turbo SHA-2 completely; we only show new collision attacks on it, with smaller complexity than it was considered by Turbo SHA-2 authors. In [1] they consider Turbo SHA-224/256-r and Turbo SHA-384/512-r with variable number of rounds r from 1 to 8. The authors of [1] show collision attack on Turbo SHA-256-1 with one round which has the complexity of 2^64. For other r from 2 to 8 they don't find better attack than with the complexity of 2^128. Similarly, for Turbo SHA-512 they find only collision attack on Turbo SHA-512-1 with one round which has the complexity of 2^128. For r from 2 to 8 they don't find better attack than with the complexity of 2^256. In this paper we show collision attack on SHA-256-r for r = 1, 2,..., 8 with the complexity of 2^{16*r}. We also show collision attack on Turbo SHA-512-r for r = 1, 2,..., 8 with the complexity of 2^{32*r}. It follows that the only one remaining candidate from the hash family Turbo SHA is Turbo SHA-256 (and Turbo SHA-512) with 8 rounds. The original security reserve of 6 round has been lost.

We introduce a new cryptographic primitive which is the signature analogue of fuzzy identity based encryption(IBE). We call it fuzzy identity based signature(IBS). It possesses similar error-tolerance property as fuzzy IBE that allows a user with the private key for identity $\omega$ to decrypt a ciphertext encrypted for identity $\omega'$ if and only if $\omega$ and $\omega'$ are within a certain distance judged by some metric. A fuzzy IBS is useful whenever we need to allow the user to issue signature on behalf of the group that has certain attributes. Fuzzy IBS can also be applied to biometric identity based signature. To our best knowledge, this primitive was never considered in the identity based signature before. We give the definition and security model of the new primitive and present the first practical implementation based on Sahai-Waters construction\cite{6} and the two level hierarchical signature of Boyen and Waters\cite{9}. We prove that our scheme is existentially unforgeable against adaptively chosen message attack without random oracles.

Key agreement protocols are essential for secure communications in open and distributed environments. The protocol design is, however, extremely error-prone as evidenced by the iterative process of fixing discovered attacks on published protocols. We revisit an efficient identity-based (ID-based) key agreement protocol due to Ryu, Yoon and Yoo. The protocol is highly efficient and suitable for real-world applications despite offering no resilience against key-compromise impersonation (K-CI). We then show that the protocol is, in fact, insecure against reflection attacks. A slight modification to the protocol is proposed, which results in significant benefits for the security of the protocol without compromising on its efficiency. Finally, we prove the improved protocol secure in a widely accepted model.

Key distribution in Wireless Sensor Networks (WSNs) is challenging. Symmetric cryptosystems can perform it efficiently, but they often do not provide a perfect trade-off between resilience and storage. Further, even though conventional public key and elliptic curve cryptosystem are computationally feasible on sensor nodes, protocols based on them are not. They require exchange and storage of large keys and certificates, which is expensive. Using Pairing-based Cryptography (PBC) protocols, conversely, parties can agree on keys without any interaction. In this work, we (i) show how security in WSNs can be bootstrapped using an authenticated identity-based non-interactive protocol and (ii) present TinyPBC, to our knowledge, the most efficient implementation of PBC primitives for an 8-bit processor. TinyPBC is an open source code able to compute pairings as well as binary multiplication in about 5.5s and 4019.46$\mu$s, respectively, on the ATmega128L 7.3828-MHz/4KB SRAM/128KB ROM processor -- the MICA2 and MICAZ node processor.

Kurosawa and Desmedt proposed an efficient hybrid encryption scheme(KD04) which is secure against adaptive chosen ciphertext attacks(IND-CCA) although the underlying KEM(key encapsulation mechanism) is not IND-CCA secure\cite{Kurosawa2004}. We show a variant of KD04 which is IND-CCA secure when the the underlying DEM part is IND-CCA secure. We need a DEM built from one-time symmetric encryption scheme and a MAC in the security reduction to check if the KEM part of a ciphertext is valid. However in the real situation we can check if the KEM part of the ciphertext is valid without the help of the MAC. So the hybrid encryption scheme can also use redundancy-free IND-CCA secure DEMs that avoid the overhead due to the MAC. When using redundancy-free(MAC-free) IND-CCA secure DEMs, the new scheme will be more efficient than KD04 in bandwidth.

This letter proposes a differential fault analysis on the AES key schedule and shows how an entire 128-bit AES key can be retrieved. In the workshop at FDTC 2007, we presented the DFA mechanism on the AES key schedule and proposed general attack rules. Using our proposed rules, we showed an efficient attack that can retrieve 80 bits of the 128-bit key. Recently, we have found a new attack that can obtain an additional 8 bits compared with our previous attack. As a result, we present most efficient attack for retrieving 88 bits of the 128-bit key using approximately two pairs of correct and faulty ciphertexts.

In this paper, we propose an extremely simple identification protocol and prove its security using the Knowledge-of-Exponent Assumption (KEA). We discuss the applicability of KEA in various protocol settings as well. Recently, doubts have been raised about applying KEA in some protocols where an adversary has auxiliary inputs. However, we suggest that KEA is applicable in these cases. We present two variants of KEA, Generalized KEA (GKEA) and Auxiliary-Input KEA (AI-KEA), to clarify the proper use of KEA.

Universal composability and concurrent general composition consider a setting where secure protocols are run concurrently with each other and with arbitrary other possibly insecure protocols. Protocols that meet the definition of universal composability are guaranteed to remain secure even when run in this strongly adversarial setting. In the case of an honest majority, or where there is a trusted setup phase of some kind (like a common reference string or the key-registration public-key infrastructure of Barak et al.~in FOCS 2004), it has been shown that any functionality can be securely computed in a universally composable way. On the negative side, it has also been shown that in the {\em plain model}\/ where there is no trusted setup at all, there are large classes of functionalities which cannot be securely computed in a universally composable way without an honest majority. In this paper we extend these impossibility results for universal composability. We study a number of public-key models and show for which models the impossibility results of universal composability hold and for which they do not. We also consider a setting where the inputs to the protocols running in the network are fixed before any execution begins. The majority of our results are negative and we show that the known impossibility results for universal composability in the case of no honest majority extend to many other settings.

This paper presents a new powerful side-channel cryptanalytic method - algebraic collision attacks - representing an efficient class of power analysis being based on both the power consumption information leakage and specific structure of the attacked cryptographic algorithm. This can result in an extremely low measurement count needed for a key recovery. The algebraic collision attacks are well applicable to AES, if one-byte collisions are detectable. For the recovery of the complete AES key, one needs 3 measurements with a probability of 0.42 and 4.24 PC hours post-processing, 4 measurements with a probability of 0.82 and several seconds of offline computations or 5 measurements with success probability close to 1 and several seconds of post-processing.

In this paper I describe the construction of Dynamic SHA family of cryptographic hash functions. They are built with design components from the SHA-2 family, but there is function R in the new hash functionh. It enabled us to achieve a novel design principle: When message is changed, different rotate right operation maybe done. It make the system can resistant against all extant attacks.

A desirable goal for cryptographic protocols is to guarantee security when the protocol is composed with other protocol instances. Universally Composable (UC) security provides this guarantee in a strong sense: A UC-secure protocol maintains its security properties even when composed concurrently with an unbounded number of instances of arbitrary protocols. However, many interesting cryptographic tasks are provably impossible to realize with UC security in the standard, ``plain'' model of computation. Impossibility holds even if ideally authenticated communication channels are provided. In contrast, it has been demonstrated that general secure computation can be obtained in a number of idealized models. Each one of these models represents a form of trust that is put in some of the system's components. This survey examines and compares some of these trust models, both from the point of view of their sufficiency for building UC secure protocols, and from the point of view of their practical realizability. We start with the common reference string (CRS) model, and then describe several relaxations and alternatives including the Defective CRS model, the key registration models, the hardware token model, the global and augmented CRS models, and a timing assumption. Finally, we briefly touch upon trust models for obtaining authenticated communication.

Although advances in SHA-1 cryptanalysis have been made since the 2005 announcement of a $2^{63}$ attack by Wang et al., the details of the attack have not yet been vetted; this note does just that. Working from Adi Shamir's 2005 CRYPTO rump session presentation of Wang et al.'s work, this note corroborates and presents the differential path and associated conditions for the two-block attack. Although the error analysis for the advanced condition correction technique is not verified, a method is given which yields a two-block collision attack on SHA-1 requiring an estimated $2^{62}$ SHA-1 computations if the original error analysis by Wang et al. is correct.

This paper presents a new paradigm to realize cryptographic primitives such as authenticated key exchange and key encapsulation without random oracles under three assumptions: the decisional Diffie-Hellman (DDH) assumption, target collision resistant (TCR) hash functions and a class of pseudo-random functions (PRFs), $\pi$PRFs, PRFs with pairwise-independent random sources. We propose a (PKI-based) two-pass authenticated key exchange (AKE) protocol that is comparably as efficient as the existing most efficient protocols like MQV and that is secure without random oracles (under these assumptions). Our protocol is shown to be secure in the (currently) strongest security definition, the extended Canetti-Krawczyk (eCK) security definition introduced by LaMacchia, Lauter and Mityagin. We also show that a variant of the Kurosawa-Desmedt key encapsulation mechanism (KEM) using a $\pi$PRF is CCA-secure under the three assumptions. This scheme is secure in a stronger security notion, the chosen public-key and ciphertext attack (CPCA) security, with using a generalized TCR (GTCR) hash function in place of a TCR hash function. The proposed schemes in this paper are validity-check-free and the implication is that combining them with validity-check-free symmetric encryption (DEM) will yield validity-check-free (e.g., MAC-free) CCA-secure hybrid encryption.

The stream cipher Salsa20 was introduced by Bernstein in 2005 as a candidate in the eSTREAM project, accompanied by the reduced versions Salsa20/8 and Salsa20/12. ChaCha is a variant of Salsa20 aiming at bringing better diffusion for similar performance. Variants of Salsa20 with up to 7 rounds (instead of 20) have been broken by differential cryptanalysis, while ChaCha has not been analyzed yet. We introduce a novel method for differential cryptanalysis of Salsa20 and ChaCha, inspired by correlation attacks and related to the notion of neutral bits. This is the first application of neutral bits in stream cipher cryptanalysis. It allows us to break the 256-bit version of Salsa20/8, to bring faster attacks on the 7-round variant, and to break 6- and 7-round ChaCha. In a second part, we analyze the compression function Rumba, built as the XOR of four Salsa20 instances and returning a 512-bit output. We find collision and preimage attacks for two simplified variants, then we discuss differential attacks on the original version, and exploit a high-probability differential to reduce complexity of collision search from 2^256 to 2^79 for 3-round Rumba. To prove the correctness of our approach we provide examples of collisions and near-collisions on simplified versions.

WEP is a protocol for securing wireless networks. In the past years, many attacks on WEP have been published, totally breaking WEP’s security. This thesis summarizes all major attacks on WEP. Additionally a new attack, the PTW attack, is introduced, which was partially developed by the author of this document. Some advanced versions of the PTW attack which are more suiteable in certain environments are described as well. Currently, the PTW attack is fastest publicly known key recovery attack against WEP protected networks.

We consider the task of computing power products $\prod_{1 \leq i \leq k} g_i^{e_i}$ ("multi-exponentiation") where base elements $g_2, ..., g_k$ are fixed while $g_1$ is variable between multi-exponentiations but may repeat, and where the exponents are bounded (e.g., in a finite group). We present a new technique that entails two different ways of computing such a result. The first way applies to the first occurrence of any $g_1$ where, besides obtaining the actual result, we create a cache entry based on $g_1$, investing very little memory or time overhead. The second way applies to any multi-exponentiation once such a cache entry exists for the $g_1$ in question: the cache entry provides for a significant speed-up. Our technique is useful for ECDSA or DSA signature verification with common domain parameters and recurring signers.

Password-authenticated key exchange (PAKE) protocols are designed to be secure even when the secret key used for authentication is a human-memorable password. In this paper, we consider PAKE protocols in the group scenario, in which a group of clients, each of them shares a password with an ``honest but curious'' server, intend to establish a common secret key (i.e., a group key) with the help of the server. In this setting, the key established is known to the clients only and no one else, including the server. Each client needs to remember passwords only while the server keeps passwords in addition to private keys related to his identity. Towards our goal, we present a compiler that transforms any group key exchange (KE) protocol secure against a passive eavesdropping to a group PAKE which is secure against an active adversary who controls all communication in the network. This compiler is built on any group KE protocol (e.g., the Burmester-Desmedt protocol), any identity-based encryption (IBE) scheme (e.g., Gentry's scheme), and any identity-based signature (IBS) scheme (e.g., Paterson-Schuldt scheme). It adds only two rounds and $O(1)$ communication (per client) to the original group KE protocol. As long as the underlying group KE protocol, IBE scheme and an IBS scheme have provably security without random oracles, a group PAKE constructed by our compiler can be proven to be secure without random oracles.

M. Abdalla, M. Bellare and P. Rogaway proposed a variation of Diffie-Hellman assumption named as oracle Diffie-Hellman(ODH) assumption. They recommend to use a one-way cryptographic hash function for the ODH assumption. We notice that if the hash function is just one-way then there will be an attack. We show that if the the hash function is non-malleable then the computational version of ODH assumption can be reduced to the computational Diffie-Hellman(CDH) assumption. But we can not reduce the ODH assumption to the decisional Diffie-Hellman(DDH) even if the hash function is non-malleable. It seems that we need a random oracle hash function to reduce the ODH assumption to the DDH assumption.

We show that interactive and noninteractive zero-knowledge are equivalent in the `help model' of Ben-Or and Gutfreund ({\em J. Cryptology}, 2003). In this model, the shared reference string is generated by a probabilistic polynomial-time dealer who is given access to the statement to be proven. Our results do not rely on any unproven complexity assumptions and hold for statistical zero knowledge, for computational zero knowledge restricted to AM, and for quantum zero knowledge when the help is a pure quantum state.

This paper presents an improved impossible differential attack on the new block cipher CLEFIA which is proposed by Sony Corporation at FSE 2007. Combining some observations with new tricks, we can filter out the wrong keys more efficiently, and improve the impossible differential attack on 11-round CLEFIA-192/256, which also firstly works for CLEFIA-128. The complexity is about $2^{103.1}$ encryptions and $2^{103.1}$ chosen plaintexts. By putting more constraint conditions on plaintext pairs, we give the first attack on 12-round CLEFIA for all three key lengths with $2^{119.1}$ encryptions and $2^{119.1}$ chosen plaintexts. For CLEFIA-192/256, our attack is applicable to 13-round variant, of which the time complexity is about $2^{181}$, and the data complexity is $2^{120}$. We also extend our attack to 14-round CLEFIA-256, with about $2^{245.4}$ encryptions and $2^{120.4}$ chosen plaintexts. Moreover, a birthday sieve method is introduced to decrease the complexity of the core precomputation.

At ASIACRYPT 2006, Chang et al. analyzed the indifferentiability of some popular hash functions based on block ciphers, namely, the twenty collision resistant PGV, the MDC2 and the PBGV hash functions, etc. In particular, two indifferentiable attacks were presented on the four of the twenty collision resistant PGV and the PBGV hash functions with the prefix-free padding. In this article, a synthetic indifferentiability analysis of some block-cipher-based hash functions is considered. First, a more precise definition is proposed on the indifferentiability adversary in block-cipher-based hash functions. Next, the advantage of indifferentiability is separately analyzed by considering whether the hash function is keyed or not. Finally, a limitation is observed in Chang et al.'s indifferentiable attacks on the four PGV and the PBGV hash functions. The formal proofs show the fact that those hash functions are indifferentiable from a random oracle in the ideal cipher model with the prefix-free padding, the NMAC/HMAC and the chop construction.

Research on secure multiparty computation has mainly concentrated on the case where the parties can authenticate each other and the communication between them. This work addresses the question of what security can be guaranteed when authentication is not available. We consider a completely unauthenticated setting, where {\em all} messages sent by the parties may be tampered with and modified by the adversary without the uncorrupted parties being able to detect this fact. In this model, it is not possible to achieve the same level of security as in the authenticated-channel setting. Nevertheless, we show that meaningful security guarantees {\em can} be provided: Essentially, all the adversary can do is to partition the network into disjoint sets, where in each set the computation is secure in of itself, and also {\em independent} of the computation in the other sets. In this setting we provide, for the first time, non-trivial security guarantees in a model with {\em no setup assumptions whatsoever.} We also obtain similar results while guaranteeing universal composability, in some variants of the common reference string model. Finally, our protocols can be used to provide conceptually simple and unified solutions to a number of problems that were studied separately in the past, including password-based authenticated key exchange and non-malleable commitments. As an application of our results, we study the question of constructing secure protocols in partially-authenticated networks, where some of the links are authenticated and some are not (as is the case in most networks today).

The computation speed of pairing based cryptosystems is slow compared with the other public key cryptosystems even though several efficient computation algorithms have been proposed. Thus more efficient computation of the Tate pairing is an important research goal. GF(3m) multiplication in GF(36m) in the pairing algorithm is the greatest consumer of time. Past research concentrated on reducing the number of GF(3m) multiplications, for instance the Karatsuba method. In this article, we propose a new method to reduce the number of online precomputations( precomputations) in GF(3m) multiplications for the eta T pairing. The proposed algorithm reduces 18 online precomputations in GF(36m) in the eta T pairing to 4 online precomputations by reusing the intermediate products obtained in precomputation.We implement the proposed algorithm and compare the time taken by the proposed algorithm with that of the previous work. Our algorithm offers a 40% performance increase for GF(3m) multiplications in GF(36m) on an AMD 64-bit processor. Additionally, a completely new finding is obtained. The results show that the reducing the number of the multiplications in GF(36m) does not necessarily lead to a speed-up of the eta T pairing calculation.

We give a generic construction for universal designated-verifier signature schemes from a large class, C, of signature schemes. The resulting schemes are efficient and have two important properties. Firstly, they are provably DV-unforgeable, non-transferable and also non-delegatable. Secondly, the signer and the designated verifier can independently choose their cryptographic settings. We also propose a generic construction for identity-based signature schemes from any signature scheme in C and prove that the construction is secure against adaptive chosen message and identity attacks. We discuss possible extensions of our constructions to hierarchical identity-based signatures, identity-based universal designated verifier signatures, and identity-based ring signatures from any signature in C.

In this paper,we construct two veriable attribute-based encryption(VABE)schemes.One is with a single authority,and the other is with multi authorities.Not only our schemes are proved secure as the previous ABE schemes,they also provide a verication property.Adding the verication property has a few advantages:first,it allows the user to immediately check the correctness of the keys,if not,he only needs the authority to resend the corresponding shares,especially,in multi-authoritycase,if the key does not pass the check,the user only needs to ask the particular authority to resend its own part,without need to go to all the authorities,this saves a lot of time when error appears;second,if the keys pass the verication but the user still does not rightly decrypt out the message,something might be wrong with the attributes or ciphertexts,then,the user has to contact with the encryptor.We formalize the notion of VABE and prove our schemes in our model.

We raise and propose solutions to the problem of guaranteeing that a user of incentive remailing services for anonymization cannot lose money if he does not get full service, i.e., if his message does not reach its destination. Applications such as voting over the Internet or reviewing of articles require anonymous delivery of messages. An anonymizing technique was proposed several decades ago by Chaum and is based on a group of volunteer agents called {\em mixnet}. However, mixnets are not yet widely known and used today, and one often mentioned reason is the lack of incentives for volunteers. A recently proposed solution is based on adding digital coins to messages, such that each volunteer can extract only the digital coin designated as a payment for her. However, registered volunteers can sabotage the system by extracting and using their coins without performing their task --- which consists of forwarding anonymized messages. The main improvement we propose is to guarantee that no money is lost by the user without getting his message at the destination. This is an essential property for a viable service. Solutions described are based on handshaking mechanisms where each volunteer gets her payment (or key to decrypt the payment) from the agent to which she is expected to forward the message, or from the destination using a public board or a reply message. This ensures that a volunteer gets her financial support only if she fulfills her task. We discuss how techniques for non-repudiation of receipt of a message, together with reputation systems, can address the remaining problems.

We present an efficient off-line divisible e-cash scheme which is \emph{truly anonymous} without a trusted third party. This is the second scheme in the literature which achieves full unlinkability and anonymity, after the seminal work proposed by Canard and Gouget. The main trick of our scheme is the use of a bounded accumulator in combination with the classical binary tree approach. The aims of this paper are twofold. Firstly, we analyze Canard and Gouget's seminal work on the efficient off-line divisible e-cash. We point out some subtleties on the parameters generation of their scheme. Moreover, spending a coin of small value requires computation of several hundreds of multi-based exponentiations, which is very costly. In short, although this seminal work provides a new approach of achieving a truly anonymous divisible e-cash, unfortunately it is rather impractical. Secondly, we present our scheme that uses a novel approach of incorporating a bounded accumulator. In terms of time and space complexities, our scheme is $50$ to $100$ times more efficient than Canard and Gouget's work in the spend protocol at the cost of an $10$ to $500$ (the large range is due to whether pre-processing is taken into account and the probabilistic nature of our withdrawal protocol) times less efficient withdrawal protocol. We believe this trade-off between the withdrawal protocol and the spend protocol is reasonable as the former protocol is to be executed much less frequent than the latter. Nonetheless, while their scheme provides an affirmative answer to whether divisible e-cash can be \emph{truly anonymous}, our result puts it a step further and we show that truly anonymous divisible e-cash can be \emph{practical}.

Can a one-way function f on n input bits be used with fewer than $n$ bits while retaining comparable hardness of inversion? We show that the answer to this fundamental question is negative, if one is limited black-box reductions. Instead, we ask whether one can save on secret random bits at the expense of more public random bits. Using a shorter secret input is highly desirable, not only because it saves resources, but also because it can yield tighter reductions from higher-level primitives to one-way functions. Our first main result shows that if the number of output elements of f is at most $2^k$, then a simple construction using pairwise-independent hash functions results in a new one-way function that uses only k secret bits. We also demonstrate that it is not the knowledge of security of f, but rather of its structure, that enables the savings: a black-box reduction cannot, for a general f, reduce the secret-input length, even given the knowledge that security of f is only $2^{-k}$; nor can a black-box reduction use fewer than k secret input bits when f has $2^k$ distinct outputs. Our second main result is an application of the public-randomness approach: we show a construction of a pseudorandom generator based on any regular one-way function with output range of known size $2^k$. The construction requires a seed of only 2n+O(k\log k) bits (as opposed to O(n \log n) in previous constructions); the savings come from the reusability of public randomness. The secret part of the seed is of length only k (as opposed to n in previous constructions), less than the length of the one-way function input.

In this paper, we will implement a standard probabilistic method of computing bilinear pairings. We will compare its performance to a deterministic algorithm introduced in [5] to compute the squared Tate/Weil pairings which are claimed to be 20 percent faster than the standard method. All pairings will be evaluated over pairing-friendly ordinary elliptic curves of embedding degrees 8 and 10 and a supersingular curve of embedding degree 6. For these curves, we can make the algorithm to compute both the ordinary Weil and Tate pairings deterministic and optimizations to improve the algorithms are applied. We will show that the evaluation of squared Weil pairing is, indeed, faster than the ordinary Weil pairing even with optimizations. However, evaluation of the squared Tate pairing is not faster than the ordinary Tate pairing over the curves that we used when optimizations are applied.

We present a stronger notion of zero-knowledge: precise concurrent zero-knowledge. Our notion captures the idea that the view of any verifier in concurrent interaction can be reconstructed in the almost same time (within a constant/polynomial factor). Precise zero-knowledge in stand-alone setting was introduced by Micali and Pass in STOC'06 (The original work used the term "local zero-knowledge".). Their notion shows that the view of any verifier can be reconstructed in the almost same time in stand-alone setting. Hence our notion is the generalization of their notion in concurrent setting. Furthermore, we propose a $\omega (\log ^2 n)$-round concurrent zero-knowledge argument for ${\rm{NP}}$ with linear precision, which shows that the view of any verifier in concurrent interaction can be reconstructed by the simulator with linear-time overhead. Our argument is Feige-Lapidot-Shamir type which consists of a proof-preamble and a proof-body for a modified NP statement. Our result assumes the restriction of adversarial scheduling the communication that the concurrent interaction of preambles of all sessions will be scheduled before any proof-body by the adversarial verifier.

Let $P$ be a point on an elliptic curve over a finite field of large characteristic. Exactly how many points $2P,3P,5P,7P,9P,\ldots,mP$ should be precomputed in a sliding-window computation of $nP$? Should some or all of the points be converted to affine form, and at which moments during the precomputation should these conversions take place? Exactly how many field multiplications are required for the resulting computation of $nP$? The answers depend on the size of $n$, the $\inversions/\mults$ ratio, the choice of curve shape, the choice of coordinate system, and the choice of addition formulas. This paper presents answers that, compared to previous analyses, are more carefully optimized and cover a much wider range of situations.

This technical report describes a novel certificateless signature scheme suitable for aggregation that requires no pairing computations for signing and only 3 pairing computations for signature verification. We provide proofs for the security of single and aggregate signatures.

We investigate the relationships between identity-based non-interactive key distribution and identity-based encryption. We provide constructions for these schemes that make use of general trapdoor discrete log groups. We then investigate the schemes that result in two concrete settings, obtaining new, provably secure, near-practical identity-based encryption schemes.

We describe a new method for constructing Brezing-Weng-like pairing-friendly elliptic curves. The new construction uses the minimal polynomials of elements in a cyclotomic field. Using this new construction we present new ``record breaking'' families of pairing-friendly curves with embedding degrees of $k \in \{16,18,36,40\}$, and some interesting new constructions for the cases $k \in \{8,32\}$

\emph{Precise zero knowledge} introduced by Micali and Pass (STOC'06) guarantees that the view of any verifier $V$ can be simulated in time closely related to the \emph{actual} (as opposed to worst-case) time spent by $V$ in the generated view. We provide the first constructions of precise concurrent zero-knowledge protocols. Our constructions have essentially optimal precision; consequently this improves also upon the previously tightest non-precise concurrent zero-knowledge protocols by Kilian and Petrank (STOC'01) and Prabhakaran, Rosen and Sahai (FOCS'02) whose simulators have a quadratic worst-case overhead. Additionally, we achieve a statistically-precise concurrent zero-knowledge property---which requires simulation of unbounded verifiers participating in an unbounded number of concurrent executions; as such we obtain the first (even non-precise) concurrent zero-knowledge protocols which handle verifiers participating in a super-polynomial number of concurrent executions.

We construct a short group signature which is proven secure without random oracles. By making certain reasonable assumptions and applying the technique of non-interactive proof system, we prove that our scheme is full anonymity and full traceability. Compared with other related works, such as BW06, BW07, ours is more practical due to the short size of both public key and group signature.

\begin{abstract} Unbalanced Feistel schemes with expanding functions are used to construct pseudo-random permutations from $kn$ bits to $kn$ bits by using random functions from $n$ bits to $(k-1)n$ bits. At each round, all the bits except $n$ bits are changed by using a function that depends only on these $n$ bits. C.S.Jutla \cite{Jut} investigated such schemes, which he denotes by $F^d_k$, where $d$ is the number of rounds. In this paper, we describe novel Known Plaintext Attacks (KPA) and Non Adaptive Chosen Plaintext Attacks (CPA-1) against these schemes. With these attacks we will often be able to improve the result of C.S.Jutla. We also give precise formulas for the complexity of our attacks in $d$, $k$ and $n$. \end{abstract}

Abstract. Algebraic attacks are relatively new and interesting subject in cryptanalysis. The algebraic attacks where introduced in [1], where several possible attack's scenarios where given. The big attention was paid to deterministic scenarios of those. In this paper, probabilistic scenarios are studied. Conception of conditional correlation and partial higher order nonlinearity of Boolean function where introduced (briefly definition of conditional correlation: $C(g,f|f = a): = \Pr (g = f|f = a) - \Pr (g \ne f|f = a)$ ) . It was shown, that the both types of scenarios can be seen as a one unified attack - higher order correlation attack, which uses conditional correlation. The clear criteria of vulnerability of Boolean function to both types of scenarios was given. Accordingly, the notion of the algebraic immunity was extended. There are very vulnerable functions to probabilistic scenario. Calculations show that if a function with a very low partial higher order nonlinearity was used in the cipher like SFINKS [8], the simple attack would require only about $ 2^{42}$ operations and $32Kb$ of keystream. The question about relation between partial higher order nonlinearity and algebraic immunity remains open yet.

We propose a security notion named as weak adaptive chosen ciphertext security(IND-WCCA) for hybrid encryption schemes. Although it is weaker than adaptive chosen ciphertext security(IND-CCA), a IND-WCCA secure hybrid encryption scheme can be used in any situations that a IND-CCA secure hybrid encryption scheme used in. We show that IND-WCCA secure hybrid encryption scheme can be constructed from IND-CCA secure KEM and IND-PA secure DEM. Since IND-PA is the basic requirement of symmetric key encryption schemes, IND-WCCA hybrid encryption scheme is very flexible and can use most of the stream ciphers and block ciphers as the DEM part of the scheme. Use the new secure notion we can refine current IND-CCA secure hybrid encryption schemes and get more efficient IND-WCCA secure hybrid encryption schemes.

A PIR scheme is a scheme that allows an user to get an element of a database without giving any information about what part of the database he is interested in. In this paper we present a lattice-based PIR scheme, using an NTRU-like approach, in which the computational cost is a few thousand bit-operations per bit in the database. This improves the protocol computational performance by two orders of magnitude when compared to existing approaches. Our scheme has worse communication performance than other existing protocols, but we show that practical usability of PIR schemes is not as dependent on communication performance as the literature suggests, and that a trade-off between communication and computation leads to much more versatile schemes.

In this paper a new efficient public key cryptosystem usable for both encryption and digital signatures is presented. Due to its simple structure this public key cipher can be implemented easily in every software or hardware device, making the cryptosystem available for circumstances where the implementation of an alternative like RSA, El Gamal / Diffie - Hellmann, etc. is too complicated. Furthermore the construction on the closest and shortest vector problem using a new homomorph "almost" linear one-way function gives not only strong evidence of the ciphers security, but may be also the base for a new class of "errorprone" cryptographic primitives based on lattice problems. Therefore this cipher and its construction is a good alternative to cryptosystems based on the integer factoriziation problem or the discrete logarithm and might be a base for secure "errorprone" application like biometrics or image watermarking.

Among cryptographically significant characteristics of Boolean functions used in symmetric ciphers the algebraic immunity and the nonlinearities of high orders play the important role. Some bounds on the nonlinearities of high orders of Boolean functions via its algebraic immunity were obtained in recent papers. In this paper we improve these results and obtain new tight bounds. We prove new universal tight lower bound that reduces the problem of an estimation of high order nonlinearities to the problem of the finding of dimensions of some linear spaces of Boolean functions. As simple consequences we obtain all previously known bounds in this field. For polynomials with disjoint terms we reduce the finding of dimensions of linear spaces of Boolean functions mentioned above to a simple combinatorial analysis. Finally, we prove the tight lower bound on the nonlinearity of the second order via its algebraic immunity.

This article analyses some properties of the \emph{template attack}. Examples come from attacks against an unprotected ASIC implementation of DES. The principal components analysis (PCA) is used to represent the templates in two dimensions. We give a physical interpretation of the templates PCA eigenvalues and eigenvectors. We show that the S-boxes are \emph{not} the target of template attacks. We point out that the efficiency of template attacks on unprotected implementations can be unleashed by using a power model. The most suitable power-model happens to be linked to the key schedule. This casts a new light on key schedule requirements for SCA resistance against a ``template'' attacker. The results are tailored for DES, because this symmetric block cipher is emblematic and is still promised a long life. Its key schedule is also remarkably simple, with cryptanalytic weaknesses,that paradoxically turn out to be a strength against SCA.

We examine several versions of the one-more-discrete-log and one-more-Diffie-Hellman problems. In attempting to evaluate their intractability, we find conflicting evidence of the relative hardness of the different problems. Much of this evidence comes from natural families of groups associated with curves of genus 2, 3, 4, 5, and 6. This leads to questions about how to interpret reductionist security arguments that rely on these non-standard problems.

This paper improves implementation techniques of Elliptic Curve Cryptography. We introduce new formulae and algorithms for the group law on Jacobi quartic, Jacobi intersection, Edwards, and Hessian curves. The proposed formulae and algorithms can save time in suitable point representations. To support our claims, a cost comparison is made with classic scalar multiplication algorithms using previous and current operation counts. Most notably, the best speedup is obtained in the case of Jacobi quartic curves which also lead to one of the most efficient scalar multiplications benefiting from the proposed 2M + 5S + 1D (i.e. 2 multiplications, 5 squarings, and 1 multiplication by a curve constant) point doubling and 7M + 3S + 1D point addition algorithms. Furthermore, the new addition algorithm provides an efficient way to protect against side channel attacks which are based on simple power analysis (SPA).

In 2005 Das et al. [5] proposed a remote user authentication scheme using bilinear pairings. Fang and Huang [7] analyzed the scheme and pointed out some weaknesses. They also proposed an improvement. Recently, Giri and Srivastava [9] observed that the improved scheme is still insecure to off-line attack and an improvement. However, the improved scheme is still insecure. In this paper, we show some weaknesses in the existing scheme and propose an improvement. The proposed scheme also enables users to choose and change the password without the help of the remote server.

A key agreement protocol is a cryptographical primitive which allows participants to share a common secret key via insecure channel. In particular, a multiparty key agreement protocol is a key agreement protocol that can manage arbitrary number of participants at once. In the security point of view, authentication and forward secrecy are the most important requirements in such protocols. One interesting problem in key agreement protocols is to construct a multiparty key agreement protocol satisfying the above security requirements with minimal number of communication rounds (i.e. one-round). In literature, there has been no one-round multiparty key agreement protocol that satisfies both of authentication and forward secrecy. In this paper, we present a new multiparty key agreement protocol using bilinear map and adopting the key generation center. The protocol demands only one round for arbitrary number of participants to share a group key and satisfies both authentication and (partial) forward secrecy.

We construct two new multiparty digital signature schemes that allow multiple signers to sequentially produce a compact, fixed-length signature. First, we introduce a new primitive that we call \emph{ordered multisignatures} (OMS), which allows signers to attest to a common message as well as the order in which they signed. Our OMS construction substantially improves computational efficiency and scalability over any existing scheme with suitable functionality. Second, we design a new identity-based sequential aggregate signature scheme, where signers can attest to different messages and signature verification does not require knowledge of traditional public keys. The latter property permits savings on bandwidth and storage as compared to public-key solutions. In contrast to the only prior scheme to provide this functionality, ours offers improved security that does not rely on synchronized clocks or a trusted first signer. We provide formal security definitions and support the proposed schemes with security proofs under appropriate computational assumptions. We focus on potential applications of our schemes to secure network routing, but we believe they will find many other applications as well.

Tweakable enciphering schemes are length preserving block cipher modes of operation that provide a strong pseudo-random permutation. It has been suggested that these schemes can be used as the main building blocks for achieving in-place disk encryption. In the past few years there has been an intense research activity towards constructing secure and efficient tweakable enciphering schemes. But, actual experimental performance data of these newly proposed schemes are yet to be reported. Accordingly, in this paper we present optimized FPGA implementations of five tweakable enciphering schemes, namely, HCH, HCTR, XCB, EME and TET, using a 128-bit AES core as the underlying block cipher. We report performance timings of these modes when using both, pipelined and sequential AES structures. The universal polynomial hash function included in the specification of HCH, HCHfp (a variant of HCH), HCTR, XCB and TET, was implemented using a Karatsuba-Ofman multiplier as the main building block. We provide detailed analyses of each of the schemes and their experimental performances achieved in various scenarios. Our experiments show that a sequential AES core is not an attractive option for the design of these modes as it leads to rather poor throughputs. In contrast, by using an encryption/decryption pipelined AES core we get a throughput of 3.67 Gbps for HCTR and by using a encryption only pipeline AES core we get a throughput of 5.71 Gbps for EME. The performance results reported in this paper provide experimental evidence that hardware implementations of tweakable enciphering schemes can actually match and even outperform the data rates achieved by state-of-the-technology disk controllers, thus showing that they might be used for achieving provably secure in-place hard disk encryption.

The stream ciphers Py, Pypy and Py6 were designed by Biham and Seberry for the ECRYPT-eSTREAM project in 2005. The ciphers were promoted to the `Focus' ciphers of the Phase II of the eSTREAM project. However, due to some cryptanalytic results on the ciphers, strengthened versions of the ciphers, namely TPy, TPypy and TPy6 were built. So far there exists no attacks on TPy6. In this paper, we find hitherto unknown weaknesses in the keystream generation algorithms of the Py6 and of its stronger variant TPy6. Exploiting these weaknesses, a large number of distinguishing attacks are mounted on the ciphers, the best of which works with $2^{224.6}$ data and comparable time. In the second part, we present two new ciphers derived from the TPy6, namely TPy6-A and TPy6-B, whose performances are 2.65 cycles/byte and 4.4 cycles/byte on Pentium III. As a result, to the best of our knowledge, on Pentium platforms TPy6-A becomes the fastest stream cipher in the literature. Based on our security analysis, we conjecture that no attacks better than brute force are possible on the ciphers TPy6-A and TPy6-B.