Textbooks tell us that a birthday attack on a hash function $h$ with range size $r$ requires $r^{1/2}$ trials (hash computations) to find a collision. But this is misleading, being true only if $h$ is regular, meaning all points in the range have the same number of pre-images under $h$; if $h$ is not regular, \textit{fewer} trials may be required. But how much fewer? This paper addresses this question by introducing a measure of the ``amount of regularity'' of a hash function that we call its balance, and then providing estimates of the success-rate of the birthday attack as a function of the balance of the hash function being attacked. In particular, we will see that the number of trials to find a collision can be significantly less than $r^{1/2}$ for hash functions of low balance. This leads us to examine popular design principles, such as the MD (Merkle-Damgård) transform, from the point of view of balance preservation, and to mount experiments to determine the balance of popular hash functions.

In this paper, we consider the statistical decision processes behind a linear and a differential cryptanalysis. By applying techniques and concepts of statistical hypothesis testing, we describe precisely the shape of optimal linear and differential distinguishers and we improve known results of Vaudenay concerning their asymptotic behaviour. Furthermore, we formalize the concept of ``sequential distinguisher'' and we illustrate potential applications of such tools in various statistical attacks.

Key exchange protocols in the setting of universal composability are investigated. First we show that the ideal functionality F_KE of [CK02] cannot be realized in the presence of adaptive adversaries, thereby disproving a claim in [CK02]. We proceed to propose a modification F_KE^(i,j), which is proven to be realizable by two natural protocols for key exchange. Furthermore, sufficient conditions for securely realizing this modified functionality are given. Two notions of key exchange are introduced that allow for security statements even when one party is corrupted. Two natural key exchange protocols are proven to fulfill the "weaker" of these notions, and a construction for deriving protocols that satisfy the "stronger" notion is given.

We present a secure unauthenticated as well as an authenticated multi party key agreement protocol. The unauthenticated version of our protocol uses ternary trees and is based on bilinear maps and Joux's three party protocol. The number of rounds, computation/communication complexity of our protocol compares favourably with previously known protocols. The authenticated version of our protocol also uses ternary trees and is based on public IDs and Key Generation Centres. The authenticated version of our protocol is more efficient than all previously known authenticated key agreement protocols.

We propose public-key cryptosystems with public key a system of polynomial equations, algebraic or differential, and private key a single polynomial or a small-size ideal. We set up probabilistic encryption, signature, and signcryption protocols.

In this paper we determine the number of isomorphism classes of Picard curves, i.e., superelliptic curves $y^3=f(x)$ of genus three, over finite fields of characteristic different from $3$. In the process of doing this we also provide reduced forms of Picard curves together the number of such forms up to isomorphism. In addition to its own theoretical meaning it has applications to cryptography.

All node certificate based transitive signature schemes available in the literature make use of any digital signature scheme which is assumed to be provably secure against adaptive chosen-message attack, as a building block to produce node certificates in a graph. Consequently the algebraic structures to represent nodes in the graph are independent of the algebraic structure of signature scheme employed. This inconsistence of representation structures of the signature scheme, nodes and edges in the graph could increase the cost to manage those public data. For example, the transitive signature schemes presented by Micali and Rivest \cite{MR} and Bellare and Neven (the node certificate based version FBTS-1, in \cite{BN}), both heavily rely on the standard provably secure signature scheme (say Goldwasser-Micali-Rivest's signature scheme \cite{GMR}). Consequently, a core problem related to transitive signature schemes is {\it how to construct transitive signature schemes so that the representation structures of signature schemes, nodes and edges in a graph can be implemented compactly?} \vskip 2mm Bellare and Neven's hash-based modification, FBTS-2, achieving shorter signatures by eliminating the need for node certificates and provable under the same factoring assumption in the random oracle model, is actually the first solution to the above question. Our approach to attack the problem mentioned above, is different from Bellare and Neven's. We attack the problem by first carefully defining algebraic structure to represent vertices and edges in an undirected graph, then we construct a signature scheme so that its algebraic structure is coincident with that of vertices and edges in the graph. Finally, we present a practical realization of a transitive signature scheme that is proven transitively unforgeable under adaptive chosen message attack in the standard intractability paradigm. To the best knowledge of authors, this approach has NOT been reported in the literature.

We propose an elliptic curve trapdoor system which is of interest in key escrow applications. In this system, a pair ($E_{\rm s}, E_{\rm pb}$) of elliptic curves over $\F_{2^{161}}$ is constructed with the following properties: (i) the Gaudry-Hess-Smart Weil descent attack reduces the elliptic curve discrete logarithm problem (ECDLP) in $E_{\rm s}(\F_{2^{161}})$ to a hyperelliptic curve DLP in the Jacobian of a curve of genus 7 or 8, which is computationally feasible, but by far not trivial; (ii) $E_{\rm pb}$ is isogenous to $E_{\rm s}$; (iii) the best attack on the ECDLP in $E_{\rm pb}(\F_{2^{161}})$ is the parallelized Pollard rho method.\\ The curve $E_{\rm pb}$ is used just as usual in elliptic curve cryptosystems. The curve $E_{\rm s} is submitted to a trusted authorityfor the purpose of key escrow. The crucial difference from other key escrow scenarios is that the trusted authority has to invest a considerable amount of computation to compromise a user's private key, which makes applications such as widespread wire-tapping impossible.

We present a new protocol for the following task. Given tow secrets a,b shared among n players, compute the value g^{ab}. The protocol uses the generic BGW approach for multiplication of shared secrets, but we show that if one is computing ``multiplications in the exponent'' the polynomial randomization step can be avoided (assuming the Decisional Diffie-Hellman Assumption holds). This results in a non-interactive and more efficient protocol.

In distributed networks, a target party $T$ could be a person never meet with a source party $S$, therefore $S$ may not hold any prior evaluation of trustworthiness of $T$. To get permit to access $S$, $T$ should be somewhat trusted by $S$. Consequently, we should study the approach to evaluate trustworthiness of $T$. To attack the problem, we view individual participant in distributed networks as a node of a delegation graph $G$ and map a delegation path from target party $T$ to source party $S$ in networks into an edge in the correspondent transitive closure of graph $G$. Based on the transitive closure property of the graph $G$, we decompose the problem to three related questions below: -how to evaluate trustworthiness of participants in an edge? -how to compute trustworthiness of participants in a path? -how to evaluate the trustworthiness of a target participant in a transitive closure graph? We attack the above three questions by first computing trustworthiness of participants in distributed and authenticated channel. Then we present a practical approach to evaluate trustworthiness by removing the assumption of the authenticated channel in distributed networks.

Blackmailing may be the most serious drawback of the known electronic cash systems offering unconditional anonymity. Recently, D.Kugler proposed an on-line payment system without trusted party to prevent blackmailing based on the idea of marking. In this paper, some disadvantages of D.Kugler¡¯s scheme are analyzed and then a new online electronic cash scheme to prevent blackmailing is present by using group blind signature technique. In our scheme, the blackmailed cash was marked by an entity, called supervisor, therefore the bank can distinguish it from the valid cash. Also, we can modify our scheme to be offline so that it can used to decrease other crimes, e.g., money laundering, bribery etc. in electronic cash system.

The pairings on elliptic curves have been applied for realizing the secure ID based cryptosystems that can be invulnerable to the collusion attacks. The computation of the pairing are necessary for the cryptosystems, though the computation of the pairing requires high cost compared with the computation cost for the power operation over the finite fields or on the elliptic curve when the parameters are securely to be provided. In this paper we propose an efficient method for a class of ID based cryptosystems which have been proposed by the present authors. The proposed method is able to reduce the number of the computations for the pairing for verifying the ID based signature and also for decoding of the ID based public key cryptosystems with the authentication, by a factor of 2. Moreover we propose the ID based public key cryptosystems with signature and the ID based public key cryptosystems having the multiple centers.

We give a closed formula for the Tate-pairing on the hyperelliptic curve $y^2 = x^p - x + d$ in characteristic $p$. This improves recent implementations by Barreto et.al. and by Galbraith et.al. for the special case $p=3$. As an application, we propose a $n$-round key agreement protocol for up to $3^n$ participants by extending Joux's pairing-based protocol to $n$ rounds.

In this paper we present a practically feasible attack on RSA-based sessions in SSL/TLS protocols. These protocols incorporate the PKCS#1 (v. 1.5) encoding method for the RSA encryption of a premaster-secret value. The premaster-secret is the only secret value that is used for deriving all the particular session keys. Therefore, an attacker who can recover the premaster-secret can decrypt the whole captured SSL/TLS session. We show that incorporating a version number check over PKCS#1 plaintext used in the SSL/TLS creates a side channel that allows the attacker to invert the RSA encryption. The attacker can then either recover the premaster-secret or sign a message on behalf of the server. Practical tests showed that two thirds of randomly chosen Internet SSL/TLS servers were vulnerable. The attack is an extension of Bleichenbacher’s attack on PKCS#1 (v. 1.5). We introduce the concept of a bad-version oracle (BVO) that covers the side channel leakage, and present several methods that speed up the original algorithm. Our attack was successfully tested in practice and the results of complexity measurements are presented in the paper. Plugging a testing server (2x Pentium III/1.4 GHz, 1 GB RAM, 100 Mb/s Ethernet, OS RedHat 7.2, Apache 1.3.27), it was possible to achieve a speed of 67.7 BVO calls per second for a 1024 bits RSA key. The median time for a whole attack on the premaster-secret could be then estimated as 54 hours and 42 minutes. We also propose and discuss countermeasures, which are both cryptographically acceptable and practically feasible.

A hardware random number generator was described at CHES 2002 by T. Tkacik. In this paper, we analyze its method of generating randomness and, as a consequence of the analysis, we describe how, in principle, an attack on the generator can be executed.

We introduce a new cryptographic primitive we call **concealment**, which is related, but quite different from the notion of commitment. A concealment is a publicly known randomized transformation, which, on input m, outputs a *hider* h and a *binder* b. Together, h and b allow one to recover m, but separately, (1) the hider h reveals "no information" about m, while (2) the binder b can be "meaningfully opened" by at most one hider h. While setting b=m, h=empty is a trivial concealment, the challenge is to make |b|<<|m|, which we call a "non-trivial" concealment. We show that non-trivial concealments are equivalent to the existence of collision-resistant hash functions. Moreover, our construction of concealments is extremely simple, optimal, and yet very general, giving rise to a multitude of efficient implementations. We show that concealments have natural and important applications in the area of **authenticated encryption**. Specifically, let AE be an authenticated encryption scheme (either public- or symmetric-key) designed to work on short messages. We show that concealments are **exactly** the right abstraction allowing one to use AE for encrypting long messages. Namely, to encrypt long m, one uses a concealment scheme to get h and b, and outputs authenticated ciphertext (AE(b),h). More surprisingly, the above paradigm leads to a very simple and general solution to the problem of **remotely keyed (authenticated) encryption** (RKAE). In this problem, one wishes to split the task of high-bandwidth authenticated encryption between a secure, but low-bandwidth/computationally limited device, and an insecure, but computationally powerful host. We give formal definitions for RKAE, which we believe are simpler and more natural than all the previous definitions. We then show that our composition paradigm satisfies our (very strong) definition. Namely, for authenticated encryption, the host simply sends a short value b to the device (which stores the actual secret key for AE), gets back AE(b), and outputs (AE(b),h) (authenticated decryption is similar). Finally, we also observe that several previous RKAE proposals are all special examples of our general paradigm.

Boneh and Venkatesan have proposed a polynomial time algorithm for recovering a "hidden" element $\alpha \in \F_p$, where $p$ is prime, from rather short strings of the most significant bits of the residue of $\alpha t$ modulo $p$ for several randomly chosen $t\in \F_p$. Gonzälez Vasco and the first author have recently extended this result to subgroups of $\F_p^*$ of order at least $p^{1/3+\varepsilon}$ for all $p$ and to subgroups of order at least $p^\varepsilon$ for almost all $p$. Here we introduce a new modification in the scheme which amplifies the uniformity of distribution of the `multipliers' $t$ and thus extend this result to subgroups of order at least $(\log p)/(\log \log p)^{1-\varepsilon}$ for all primes $p$. As in the above works, we give applications of our result to the bit security of the Diffie--Hellman secret key starting with subgroups of very small size, thus including all cryptographically interesting subgroups.

In this paper we introduce the class of composite access structures for secret sharing. We also provide secret sharing schemes realizing these structures and study their information rates. As a particular case of this construction, we present the subclass of iterated threshold schemes, a large class of ideal secret sharing schemes.

Extensive studies have been made of the public-key cryptosystems based on multivariate polynomials . However most of the proposed public-key cryptosystems of rate 1.0 based on multivariate polynomials, are proved not secure. In this paper, we propose several types of new constructions of public-key cryptosystems based on two classes of randomly generated simultaneous equations, namely, a class based on bijective transformation and another class based on random transformation. One of the features of the proposed cryptosystems is that the sets of random simultaneous equations significantly improve the utilization factor of the public-key space. We show an example of the proposed cryptosystem whose size is only 100 bits that seems to be apparently secure in a sense that the utilization factor is significantly large compared with the conventional public-key cryptosystems.

Recently, based on Guillou-Quisquater signature scheme, Saeednia proposed an identity-based society oriented signature scheme. However, in this note, we point out that Saeednia's scheme does not satisfy the claimed properties.

Sufficient conditions are obtained on the prime factors of an RSA modulus in order to avoid Wiener and Boneh-Durfee attacks. The public exponent can be chosen arbitrarily.

An Identity-based cryptosystem is a Public Key cryptosystem in which the public keys of the entities are their identities, or strings derived from their identities. Signcryption combines digital signatures and encryption with a cost significantly smaller than that required for signature-then-encryption. This paper proposes an ID-based signcryption scheme based on bilinear pairings on elliptic curves. It is shown that the new scheme is an improved version of the existing signcryption scheme [10] by comparing the computations in both the schemes.

We present a new, elegant composition method for joint signature and encryption, also referred to as signcryption. The new method, which we call *Padding-based Parallel Signcryption* (PbPS), builds an efficient signcryption scheme from any family of trapdoor permutations, such as RSA. Each user U generates a single public/secret key pair f_U/f^{-1}_U used for both sending and receiving the data. To signcrypt a message m to a recipient with key f_{rcv}, a sender with key f_{snd} efficiently transforms m into a pair {w|s}, and simply sends { f_{rcv}(w) | f^{-1}_{snd}(s) }. PbPS enjoys many attractive properties: simplicity, efficiency, generality, parallelism of ``encrypting''/``signing'', optimal exact security, flexible and ad-hoc key management, key reuse for sending/receiving data, optimally-low message expansion, long message and associated data support, and, finally, complete compatibility with the PKCS#1 infrastructure. The pairs {w|s} sufficient for the security of PbPS are called *universal two-padding schemes*. Using one round of the Feistel transform, we give a very general construction of such schemes. Interestingly, we notice that all popular padding schemes with message recovery used for plain signature or encryption, such as OAEP, OAEP+, PSS-R, and ``scramble all, encrypt small'', naturally consist of two pieces {w|s}. Quite remarkably, we show that all such pairs become special cases of our construction. As a result, we find a natural generalization of all conventional padding schemes, and show that any such padding can be used for signcryption with PbPS. However, none of such paddings gives optimal message bandwidth. For that purpose and of independent interest, we define a new ``hybrid'' between PSS-R and OAEP, which we call *Probabilistic Signature-Encryption Padding* (PSEP). We recommend using PbPS with PSEP to achieve the most flexible and secure signcryption scheme up-to-date. To justify this point, we provide a detailed practical comparison of PbPS/PSEP with other previously-proposed signcryption candidates.

In this paper we show how to achieve timed fair exchange of digital signatures of standard type. Timed fair exchange (in particular, contract signing) has been considered before, but only for Rabin and RSA signatures of a special kind. Our construction follows the gradual release paradigm, and works on a new ``time'' structure that we call a {\em mirrored time-line.} Using this structure, we design a protocol for the timed fair exchange by two parties of arbitrary values (values lying on their respective mirrored time-lines). Finally, we apply the blinding techniques of Garay and Jakobsson to turn this protocol into a protocol for the timed fair exchange of standard signatures. The length of these mirrored time-lines makes another problem apparent, which is making sure that the underlying sequence has a period large enough so that cycling is not observed. We also show how to construct these structures so that, under reasonable assumptions, this is indeed the case.

The shrinking generator is a well-known keystream generator composed of two linear feedback shift registers, LFSR$_1$ and LFSR$_2$, where LFSR$_1$ is clock-controlled according to regularly clocked LFSR$_2$. The keystream sequence is thus a decimated LFSR$_1$ sequence. Statistical distinguishers for keystream generators are algorithms whose objective is to distinguish the keystream sequence from a purely random sequence. Previously proposed statistical distinguishers for the shrinking generator are based on detecting binary linear relations in the keystream sequence that hold with a probability sufficiently different from one half. In this paper a novel approach which significantly reduces the required computation time is introduced. It is based on a probabilistic reconstruction of the bits in the regularly clocked LFSR$_1$ sequence that satisfy the LFSR$_1$ recurrence or any linear recurrence derived from low-weight multiples of the LFSR$_1$ characteristic polynomial. The keystream sequence length and the computation time required for a reliable statistical distinction are analyzed both theoretically and experimentally.

We study the relationship between the Walsh transform and the algebraic normal form of a Boolean function. In the first part of the paper, we carry out a combinatorial analysis to obtain a formula for the Walsh transform at a certain point in terms of parameters derived from the algebraic normal form. The second part of the paper is devoted to simplify this formula and develop an algorithm to evaluate it. Our algorithm can be applied in situations where it is practically impossible to use the fast Walsh transform algorithm. Experimental results show that under certain conditions it is possible to execute our algorithm to evaluate the Walsh transform (at a small set of points) of functions on a few scores of variables having a few hundred terms in the algebraic normal form.

We introduce cryptography based on algebraic tori, give a new public key system called CEILIDH, and compare it to other discrete log based systems including LUC and XTR. Like those systems, we obtain small key sizes. While LUC and XTR are essentially restricted to exponentiation, we are able to perform multiplication as well. We also disprove the open conjectures from the paper "Looking beyond XTR", and give a new algebro-geometric interpretation of the approach in that paper and of LUC and XTR.

In this paper, we propose a pretty-simple password-authenticated key-exchange protocol, which is proven to be secure in the standard model under the following three assumptions. (1) DDH (Decision Diffie-Hellman) problem is hard. (2) The entropy of the password is large enough to avoid on-line exhaustive search (but not necessarily off-line exhaustive search). (3) MAC is selectively unforgeable against partially chosen message attacks, (which is weaker than being existentially unforgeable against chosen message attacks).

Recently there has been an interest in zero-knowledge protocols with stronger properties, such as concurrency, unbounded simulation soundness, non-malleability, and universal composability. In this paper, we show a novel technique to convert a large class of existing honest-verifier zero-knowledge protocols into ones with these stronger properties in the common reference string model. More precisely, our technique utilizes a signature scheme existentially unforgeable against adaptive chosen-message attacks, and transforms any $\Sigma$-protocol (which is honest-verifier zero-knowledge) into an unbounded simulation sound concurrent zero-knowledge protocol. We also introduce $\Omega$-protocols, a variant of $\Sigma$-protocols for which our technique further achieves the properties of non-malleability and/or universal composability. In addition to its conceptual simplicity, a main advantage of this new technique over previous ones is that it avoids the Cook-Levin theorem, which tends to be rather inefficient. Indeed, our technique allows for very efficient instantiation based on the security of some efficient signature schemes and standard number-theoretic assumptions. For instance, one instantiation of our technique yields a universally composable zero-knowledge protocol under the Strong RSA assumption, incurring an overhead of a small constant number of exponentiations, plus the generation of two signatures.

We describe a cryptanalysis of a public-key encryption scheme based on the polynomial reconstruction problem. Given the public-key and a ciphertext, we recover the corresponding plaintext in polynomial time. Therefore, the scheme is not one-way. Our technique is a variant of the Berlekamp-Welsh algorithm.

The proposed approach works for any underlying secret sharing scheme. It is based on the concept of verification sets of participants, related to authorized set of participants. The participants interact (no third party involved) in order to check validity of their shares before they are pooled for secret recovery. Verification efficiency does not depend on the number of faulty participants.

In 1986, Fiat and Shamir suggested a general method for transforming secure 3-round public-coin identification schemes into digital signature schemes. The significant contribution of this method is a means for designing efficient digital signatures, while hopefully achieving security against chosen message attacks. All other known constructions which achieve such security are substantially more inefficient and complicated in design. In 1996, Pointcheval and Stern proved that the signature schemes obtained by the Fiat-Shamir transformation are secure in the so called `Random Oracle Model'. The question is: does the proof of the security of the Fiat-Shamir transformation in the Random Oracle Model, imply that the transformation yields secure signature schemes in the ``real-world"? In this paper we answer this question negatively. We show that there exist secure 3-round public-coin identification schemes for which the Fiat-Shamir methodology produces {\bf insecure} digital signature schemes for {\bf any} implementation of the `Random Oracle Model' in the `real-world' by a function ensemble.

In this paper we describe an integral distinguisher over 2 rounds of Safer++. It allows a practical attack against 3 rounds of Safer++128, as well as attacks on 4 rounds of Safer++128 and Safer++256, under the chosen-plaintext hypothesis. These results achieve much lower complexity than the currently known best attacks on Safer++, namely weak-key linear cryptanalysis by Nakahara. As a side result, we prove that the byte-branch number of the linear transform of Safer++ is 5. We also discuss a way for further research in order to extend integral cryptanalysis.

In this paper we present a general framework for password-based authenticated key exchange protocols, in the common reference string model. Our protocol is actually an abstraction of the key exchange protocol of Katz et al.\ and is based on the recently introduced notion of smooth projective hashing by Cramer and Shoup. We gain a number of benefits from this abstraction. First, we obtain a modular protocol that can be described using just three high-level cryptographic tools. This allows a simple and intuitive understanding of its security. Second, our proof of security is significantly simpler and more modular. Third, we are able to derive analogues to the Katz et al.\ protocol under additional cryptographic assumptions. Specifically, in addition to the DDH assumption used by Katz et al., we obtain protocols under both the Quadratic and $N$-Residuosity assumptions. In order to achieve this, we construct new smooth projective hash functions.

We propose a new notion of cryptographic tamper evidence. A tamper-evident signature scheme provides an additional procedure Div which detects tampering: given two signatures, Div can determine whether one of them was generated by the forger. Surprisingly, this is possible even after the adversary has inconspicuously learned some --- or even all --- the secrets in the system. In this case, it might be impossible to tell which signature is generated by the legitimate signer and which by the forger. But at least the fact of the tampering will be made evident. We define several variants of tamper-evidence, differing in their power to detect tampering. In all of these, we assume an equally powerful adversary: she adaptively controls all the inputs to the legitimate signer (i.e., all messages to be signed and their timing), and observes all his outputs; she can also adaptively expose all the secrets at arbitrary times. We provide tamper-evident schemes for all the variants and prove their optimality. We stress that our mechanisms are purely cryptographic: the tamper-detection algorithm Div is stateless and takes no inputs except the two signatures (in particular, it keeps no logs), we use no infrastructure (or other ways to conceal additional secrets), and we use no hardware properties (except those implied by the standard cryptographic assumptions, such as random number generators). Our constructions are based on arbitrary ordinary signature schemes and do not require random oracles.

Secure multi-party computation (MPC) is an active research area, and a wide range of literature can be found nowadays suggesting improvements and generalizations of existing protocols in various directions. However, all current techniques for secure MPC apply to functions that are represented by (boolean or arithmetic) circuits over finite {\em fields}. We are motivated by two limitations of these techniques: {\sc Generality.} Existing protocols do not apply to computation over more general algebraic structures (except via a brute-force simulation of computation in these structures). {\sc Efficiency.} The best known {\em constant-round} protocols do not efficiently scale even to the case of large finite fields. Our contribution goes in these two directions. First, we propose a basis for unconditionally secure MPC over an arbitrary finite {\em ring}, an algebraic object with a much less nice structure than a field, and obtain efficient MPC protocols requiring only a {\em black-box access} to the ring operations and to random ring elements. Second, we extend these results to the constant-round setting, and suggest efficiency improvements that are relevant also for the important special case of fields. We demonstrate the usefulness of the above results by presenting a novel application of MPC over (non-field) rings to the round-efficient secure computation of the maximum function.

We prove that three OAEP-inspired randomised padding schemes (i.e., OAEP, OAEP+ and SAEP), when used with the RSA function in the trapdoor direction, form provably secure signature schemes with message recovery. Two of our three reductionist proofs are tight and hence provide exact security. Because of the exact security and OAEP's optimally high bandwidth for message recovery, our results form a desirable improvement from a previous universal RSA padding scheme good for both encryption and signature.

Elliptic curve cryptosystems in the presence of faults were studied by Biehl, Meyer and Mueller (2000). The first fault model they consider requires that the input point P in the computation of dP is chosen by the adversary. Their second and third fault models only require the knowledge of P. But these two latter models are less `practical' in the sense that they assume that only a few bits of error are inserted (typically exactly one bit is supposed to be disturbed) either into P just prior to the point multiplication or during the course of the computation in a chosen location. This report relaxes these assumptions and shows how random (and thus unknown) errors in either coordinates of point P, in the elliptic curve parameters or in the field representation enable the (partial) recovery of multiplier d. Then, from multiple point multiplications, we explain how this can be turned into a total key recovery. Simple precautions to prevent the leakage of secrets are also discussed.

We develop cryptographically secure techniques to guarantee unconditional privacy for respondents to polls. Our constructions are efficient and practical, and are shown not to allow cheating respondents to affect the ``tally'' by more than their own vote --- which will be given the exact same weight as that of other respondents. We demonstrate solutions to this problem based on both traditional cryptographic techniques and quantum cryptography.

For most of the time since they were proposed, it was widely believed that hyperelliptic curve cryptosystems (HECC) carry a substantial performance penalty compared to elliptic curve cryptosystems (ECC) and are, thus, not too attractive for practical applications. Only quite recently improvements have been made, mainly restricted to curves of genus 2. The work at hand advances the state-of-the-art considerably in several aspects. First, we generalize and improve the closed formulae for the group operation of genus 3 for HEC defined over fields of characteristic two. For certain curves we achieve over 50% complexity improvement compared to the best previously published results. Second, we introduce a new complexity metric for ECC and HECC defined over characteristic two fields which allow performance comparisons of practical relevance. It can be shown that the HECC performance is in the range of the performance of an ECC; for specific parameters HECC can even possess a lower complexity than an ECC at the same security level. Third, we describe the first implementation of a HEC cryptosystem on an embedded (ARM7) processor. Since HEC are particularly attractive for constrained environments, such a case study should be of relevance.

Homomorphic cryptosystems are designed for the first time over any finite group. Applying Barrington's construction we produce for any boolean circuit of the logarithmic depth its encrypted simulation of a polynomial size over an appropriate finitely generated group.

Two common notions of security for public key encryption schemes are shown to be equivalent: we prove that indistinguishability against chosen-ciphertext attacks (IND-CCA) is in fact polynomially equivalent to (yet "slightly" weaker than) securely realizing the ideal functionality F_PKE in the general modeling of cryptographic protocols of [http://eprint.iacr.org/2000/067]. This disproves in particular the claim that security in the sense of IND-CCA strictly implies security in the sense of realizing F_PKE (see [http://eprint.iacr.org/2000/067]). Moreover, we give concrete reductions among such security notions and show that these relations hold for both uniform and non-uniform adversarial entities.

We present a new identity based scheme based on pairings over elliptic curves. It combines the functionalities of signature and encryption and is provably secure in the random oracle model. We compare it with Malone-Lee's one from security and efficiency points of view. We give a formal proof of semantical security under the Decisional Bilinear Diffie-Hellman assumption for this new scheme and we show how to devise other provably secure schemes that produce even shorter ciphertexts.

On January 8th 2003, Eric Filiol published on the eprint a paper (eprint.iacr.org/2003/003/) in which he claims that AES can be broken by a very simple and very fast ciphertext-only attack. If such an attack existed, it would be the biggest discovery in code-breaking since some 10 or more years. Unfortunately the result is very hard to believe. In this paper we present the results of computer simulations done by several independent people, with independently written code. Nobody has confirmed a single anomaly in AES, even for much weaker versions of the bias claimed by the author. We also studied the source code provided by the author to realize that the first version had various issues and bugs, and the latest version still does not confirm the claimed result on AES.

We propose a new cryptographically protected multi-round auction mechanism for online auctions. This auction mechanism is designed to provide (in this order) security, cognitive convenience, and round-effectiveness. One can vary internal parameters of the mechanism to trade off bid privacy and cognitive costs, or cognitive costs and the number of rounds. We are aware of no previous work that interleaves cryptography explicitly with the mechanism design.

In this paper we extend the conditional correlation attack ([LCPP96]) against the nonlinear filter generator (NLFG) by introducing new conditions and generalisations and present two known-plaintext attacks, called hybrid correlation attack and concentration attack. The NLFG is a well known LFSR-based keystream generator which could be used as a basic building block in a synchronous stream cipher system. Both new attacks use methods from the conditional correlation attack and additional from fast correlation attacks to derive the unknown initial state of the LFSR of the NLFG. The basic principle of iteratively cumulating and updating conditional correlations for the NLFG was proposed in [Loh01] and for general combiners with memory in [GBM02]. With the hybrid correlation attack it is possible to successfully attack the NLFG by applying a fast correlation attack, even if the filter function $f$ of the NLFG is highly nonlinear, e.g. the normalised nonlinearity $p_{e,f}$ is $\ge 0.45$. The concentration attack maps all computed conditional correlations to $D-B$ unknown LFSR bits, where $D \ge k$ and $1 \le B \le k$ are parameters which can be chosen by the attacker, and $k$ is the length of the LFSR of the NLFG. Even with low values of conditional correlations, it is possible to mount the hybrid correlation attack and the concentration attack successfully. This is not the case for the originally version of the conditional correlation attack ([LCPP96]) in a time lower than a full search over all possible initial states.

We propose the first polynomial time algorithm for the braid Diffie-Hellman conjugacy problem (DHCP) on which the braid key exchange scheme and the braid encryption scheme are based~\cite{KLCHKP01}. We show the proposed method solves the DHCP for the image of braids under the Lawrence-Krammer representation and the solutions play the equivalent role of the original key for the DHCP of braids. Given a braid index $n$ and a canonical length $\ell$, the complexity is about $2^{-2}\ell^3 n^{4\tau+2}\log n$ bit operations, where $\tau=\log_27\approx 2.8$ (Theoretically, it can be reduced to $O(\ell^3 n^{8.3}\log n)$ using $\tau=2.376$). Further, we show that the generalization into the decomposition problem causes only 8 times of the complexity.

In this paper, we extend the 2-party key exchange protocol on braid groups to the group key agreement protocol based on the hardness of Ko-Lee problem. We also provide authenticity to the group key agreement protocol.

An {\em $(s;n,q,t)$-perfect hash family} is a set of functions $\phi_1,\phi_2,\ldots ,\phi_s$ from a set $V$ of cardinality $n$ to a set $F$ of cardinality $q$ with the property that every $t$-subset of $V$ is injectively mapped into $F$ by at least one of the functions $\phi_i$. The paper shows that the maximum value $n_{s,t}(q)$ that $n$ can take for fixed $s$ and $t$ has a leading term that is linear in $q$ if and only if $t>s$. Moreover, for any $s$ and $t$ such that $t>s$, the paper shows how to calculate the coefficient of this linear leading term; this coefficient is explicitly calculated in some cases. As part of this process, new classes of good perfect hash families are constructed.

We proposed the first threshold GQ signature scheme. The scheme is unforgeable and robust against any adaptive adversary if the base GQ signature scheme is unforgeable under the chosen message attack and computing the discrete logarithm modulo a safe prime is hard. Our scheme achieve optimal resilience, that is, the adversary can corrupt up to a half of the players. As an extension of our work, we proposed a threshold forward-secure signature scheme, which is the threshold version of the most efficient forward-secure signature scheme up to now.

Bridging the gap between formal methods and cryptography has recently received a lot of interest, i.e., investigating to what extent proofs of cryptographic protocols made with abstracted cryptographic operations are valid for real implementations. However, a major goal has not been achieved yet: a soundness proof for an abstract crypto-library as needed for the cryptographic protocols typically proved with formal methods, e.g., authentication and key exchange protocols. Prior work that directly justifies the typical Dolev-Yao abstraction is restricted to passive adversaries and certain protocol environments. Prior work starting from the cryptographic side entirely hides the cryptographic objects, so that the operations are not composable: While secure channels or signing of application data is modeled, one cannot encrypt a signature or sign a key. We make the major step towards this goal: We specify an abstract crypto-library that allows composed operations, define a cryptographic realization, and prove that the abstraction is sound for arbitrary active attacks in arbitrary reactive scenarios. The library currently contains public-key encryption and signatures, nonces, lists, and application data. The proof is a novel combination of a probabilistic, imperfect bisimulation with cryptographic reductions and static information-flow analysis.

In this paper, we present a new stream cipher called Hiji-bij-bij (HBB). The basic design principle of HBB is to mix a linear and a nonlinear map. Our innovation is in the design of the linear and the nonlinear maps. The linear map is realised using two 256-bit maximal period 90/150 cellular automata. The nonlinear map is simple and consists of several alternating linear and nonlinear layers. We prove that the mixing achieved by the nonlinear map is complete and the maximum bias in any non-zero linear combination of the input and output bits of the nonlinear map is at most $2^{-13}$. We also identify a self-synchronizing mode ({\bf SS}) of operation for HBB. The performance of HBB is reasonably good in software and is expected to be very fast in hardware. To the best of our knowledge, a generic exhaustive search seems to be the only method of attacking the cipher.

In smartcard encryption and signature applications, randomized algorithms can be used to increase tamper resistance against attacks based on averaging data-dependent power or EMR variations. Recently, Oswald and Aigner described such an algorithm suitable for point multiplication in elliptic curve cryptography (ECC). With the assumption that an attacker can identify additions and doublings and distinguish them from each other during a single point multiplication, it is shown that the algorithm is insecure for repeated use of the same secret key without blinding of that key. This scotches hopes that the expense of such blinding might be avoided by using the algorithm unless the differences between point additions and doublings can be obscured successfully.

RC4 cipher is the most widely used stream cipher in software applications. It was designed by R. Rivest in 1987. In this paper we find the number of keys of the RC4 cipher generating initial permutations with the same cycle structure. We obtain that the distribution of initial permutations is not uniform.

Key authentication is very important in secret communications and data security. Recently, Lee, Hwang and Li proposed a new public key authentication scheme for cryptosystems with a trusty server. However, in this paper, we will show that Lee-Hwang-Li's key authentication scheme is not secure, from the obtained public information, any one can get the private key of the user. And then, we propose an improved scheme. We conclude that our new key authentication scheme not only resolves the problems appeared but also is secure.

We explain how a differential fault analysis (DFA) works on AES 128, 192 or 256 bits.

We obtain a {\em finite} binary tree algorithm to extend the domain of a UOWHF. The associated key length expansion is only a constant number of bits more than the minimum possible. Our finite binary tree algorithm is a practical parallel algorithm to securely extend the domain of a UOWHF. Also the speed-up obtained by our algorithm is approximately proportional to the number of processors.

In this paper we describe two different DFA attacks on the AES. The first one uses a fault model that induces a fault on only one bit of an intermediate result, hence allowing us to obtain the key by using 50 faulty ciphertexts for an AES-128. The second attack uses a more realistic fault model: we assume that we may induce a fault on a whole byte. For an AES-128, this second attack provides the key by using less than 250 faulty ciphertexts. Moreover, this attack has been successfully put into practice on a smart card.

We present a practical protocol that allows two players to negotiate price over the Internet in a deniable way so that a player $A$ can prevent another player $B$ from showing this offer $P$ to a third party $C$ in order to elicit a better offer while player $B$ should be sure that this offer $P$ generated by $A$, but should $C$ be unclear whether $P$ is generated by $A$ or $B$ itself, even $C$ and $B$ fully cooperated. Our protocol is a standard browser-server model and uses a trusted third party, but only in a very limited fashion: the trusted third party is only needed in the cases where one player attempts to cheat or simply crashes, therefore, in the vast of majority transactions, the third party is not to be involved at all. In addition, Our price negotiable transaction system enjoys the following properties: \begin{description} \item[(1)]It works in an asynchronous communication model. \item[(2)]It is inter-operated with existing or proposed scheme for electronics voting system; \item[(3)]The two players need not sacrifice their privacy in making use of the trusted third party; \item[(4)]The deniable property can be proved secure in the random oracle paradigm, while the matching protocol can be proved secure in the standard intractable assumption. \end{description}

We use a general treatment of both information-theoretic and cryptographic settings for Multi-Party Computation (MPC), based on the underlying linear secret sharing scheme. Our goal is to study the Monotone Span Program (MSP), which is the result of local multiplication of shares distributed by two given MSPs as well as the access structure that this resulting MSP computes. First, we expand the construction proposed by Cramer et~al. multiplying two different general access structures and we prove some properties of the resulting MSP ${\cal M}$. Next we expand the definition of multiplicative MSPs and we prove that when one uses dual MSPs only all players together can compute the product, i.e., the construction proposed by Cramer et~al. gives only multiplicative MPC. Third, we propose a solution for the strongly multiplicative MPC (in presence of adversary). The knowledge of the resulting MSP and the access structure it computes allows us to build an analog of the algebraic simplification protocol of Gennaro et~al. We show how to achieve in the computational model MPC secure against adaptive adversary in the zero-error case, through the application of homomorphic commitments. There is an open problem how efficiently we can determine $\Gamma$ the access structure of the resulting MSP ${\cal M}$. This open problem reflects negatively on the efficiency of the proposed solution.

In threshold cryptography the goal is to distribute the computation of basic cryptographic primitives across a number of nodes in order to relax trust assumptions on individual nodes, as well as to introduce a level of fault-tolerance against node compromise. Most threshold cryptography has previously looked at the distribution of public key primitives, particularly threshold signatures and threshold decryption mechanisms. In this paper we look at the application of threshold cryptography to symmetric primitives, and in particular the encryption or decryption of a symmetric key block cipher. We comment on some previous work in this area and then propose a model for shared encryption / decryption of a block cipher. We will present several approaches to enable such systems and will compare them.

This paper proposes ID-based tripartite authenticated key agreement protocols. The authenticated three party key agreement protocols from pairings [15], and the ID-based two party authenticated key agreement protocol [13] are studied. These two protocols are taken as the basis for designing three new ID-based tripartite authenticated key agreement protocols. The security properties of all these protocols are studied listing out the possible attacks on them. Further, these protocols are extended to provide key confirmation.

This paper presents a new ``operational'' cryptanalysis of block ciphers based on the use of a well-known error-correcting code: the repetition codes. We demonstrate how to describe a block cipher with such a code before explaining how to design a new ciphertext only cryptanalysis of these cryptosystems on the assumption that plaintext belongs to a particular class. This new cryptanalysis may succeed for any block cipher and thus is likely to question the security of those cryptosystems for encryption. We then apply this cryptanalysis to the 128-bit key AES. Our results have been experimentallly confirmed with 100 {\bf effective} cryptanalysis. Our attack enables to recover two information bits of the secret key with only $2^{31}$ ciphertext blocks and a complexity of $\mathcal{O}(2^{31})$ with a success probability of 0.68.

A property of the NTRU public-key cryptosystem is that it does not provide perfect decryption. That is, given an instance of the cryptosystem, there exist ciphertexts which can be validly created using the public key but which can't be decrypted using the private key. The valid ciphertexts which an NTRU secret key will not correctly decipher determine, up to a cyclic shift, the secret key. In this paper we present attacks based on this property against the NTRU primitive and many of the suggested NTRU padding schemes. These attacks use an oracle for determining if valid ciphertexts can be correctly deciphered, and recover the user's secret key. The attacks are quite practical. For example, the attack against the NTRU-REACT padding scheme proposed at CRYPTO 2002 with the $N=503$ parameter set requires on average fewer than 30,000 oracle calls and can be performed on a PC in a few minutes. As the traditional definition of a public-key encryption scheme requires perfect decryption, we also define a new type of encryption scheme which encompasses both NTRU and an attack model for the attacks presented against it.

At the recent AES Modes of Operation Conference, several modes of operation were proposed for using a block cipher to provide both confidentiality and authentication. These modes require only a little more work than the cost of encryption alone, and come with proofs of security. However, these modes require the entire message to be sent in encrypted form. This can cause problems in situations where some of the message neeeds to be sent in plaintext while still being authenticated. This paper describes a simple variation that allows any choice of message blocks to be sent in plaintext form rather than in encrypted form. This mode, Partial Encryption with Message Integrity (PEMI), is shown to be secure for message integrity and message secrecy.