The Cramer-Shoup cryptosystem for groups of prime order is a practical public-key cryptosystem, provably secure in the standard model under standard assumptions. This paper extends the cryptosystem for groups of unknown order, namely the group of quadratic residues modulo a composed N. Two security results are: In the standard model, the scheme is provably secure if both the Decisional Diffie-Hellman assumption for QR_N *and* the factorisation assumption for N hold. In the random oracle model, the security of the scheme is provable by a quite efficient reduction.

In a proxy signature scheme, a potential signer delegates his signing capability to a proxy entity, who signs a message on behalf of the original signer. All the proposals of proxy signature schemes made until now have been based on Schnorr's signature scheme. Threshold versions of these schemes have also been proposed, in which the power of the proxy signer is distributed among a group of players, in such a way that any subset with a minimum number (threshold) of players can sign a message on behalf of the original signer. We consider a model that is fully distributed, because we want to distribute not only the power of the proxy signer, but also the original signer ability to delegate his signing capability. Furthermore, we consider general structures, instead of only the threshold ones, for both the tolerated subsets of dishonest players and the subsets of honest players authorized to execute a valid instance of the protocol, and in both the original and the proxy signer entities. We find sufficient combinatorial conditions that these structures must satisfy in order to design a fully distributed, secure and robust proxy signature scheme for this general scenario. We propose such a scheme for this setting. It is also based on Schnorr's signature scheme.

In this paper we study secret sharing schemes whose access structure has three or four minimal qualified subsets. The ideal case is completely characterized and for the non-ideal case we provide bounds on the optimal information rate.

We introduce a tensor transform for Boolean functions that covers the algebraic normal and Walsh transforms but which also allows for the definition of new, probabilistic and weight transforms, relating a function to its bias polynomial and to the weights of its subfunctions respectively. Our approach leads to easy proofs for some known results and to new properties of the aforecited transforms. Several new results about algebraic and correlation properties that depend on the weight transform of Boolean functions are proved. Finally, we present a new probabilistic characteristic of a Boolean function that is defined by its algebraic normal and probabilistic transforms over the reals.

The public key cryptosystems $MST_1$ and $MST_2$ make use of certain kinds of factorizations of finite groups. We show that generalizing such factorizations to infinite groups allows a uniform description of several proposed cryptographic primitives. In particular, a generalization of $MST_2$ can be regarded as a unifying framework for several suggested cryptosystems including the ElGamal public key system, a public key system based on braid groups and the MOR cryptosystem.

Cryptographic systems often involve running multiple concurrent instances of some protocol, where the instances have some amount of joint state and randomness. (Examples include systems where multiple protocol instances use the same public-key infrastructure, or the same common reference string.) Rather than attempting to analyze the entire system as a single unit, we would like to be able to analyze each such protocol instance as stand-alone, and then use a general composition theorem to deduce the security of the entire system. However, no known composition theorem applies in this setting, since they all assume that the composed protocol instances have disjoint internal states, and that the internal random choices in the various instances are independent. We propose a new composition operation that can handle the case where different components have some amount of joint state and randomness, and demonstrate sufficient conditions for when the new operation preserves security. The new operation, which is called {\em universal composition with joint state} (and is based on the recently proposed universal composition operation), turns out to be very useful in a number of quite different scenarios such as those mentioned above.

We formally study the notion of a joint signature and encryption in the public-key setting. We refer to this primitive as {\em signcryption}, adapting the terminology of Zheng [Zhe97]. We present wo definitions for the security of signcryption depending on whether the adversary is an outsider or a legal user of the system. We then examine generic sequential composition methods of building signcryption from a signature and encryption scheme. Contrary to what recent results in the symmetric setting [BN00,Kra01] might lead one to expect, we show that classical ``encrypt-then-sign'' (EtS) and ``sign-then-encrypt'' (StE) methods are both {\em secure} composition methods in the public-key setting. We also present a new composition method which we call ``commit-then-encrypt-and-sign'' (CtE&S). Unlike the generic sequential composition methods, CtE&S applies the expensive signature and encryption operations {\em in parallel}, which could imply a gain in efficiency over the StE and EtS schemes. We also show that the new CtE&S method elegantly combines with the recent ``hash-sign-switch'' technique of Shamir and Tauman [ST01], leading to efficient {\em on-line/off-line} signcryption. Finally and of independent interest, we discuss the {\em definitional} inadequacy of the standard notion of chosen ciphertext (CAA) security. Motivated by our applications to signcryption, we show that the notion of CAA-security is syntactically ill-defined, and leads to artificial examples of ``secure'' encryption schemes which do not meet the formal definition of CCA-security. We suggest a natural and very slight relaxation of CAA-security, which we call generalized CCA-security (gCCA). We show that gCCA-security suffices for all known uses of CCA-secure encryption, while no longer suffering from the definitional shortcomings of the latter.

This paper describes an effort to attack S-DES using differential cryptanalysis and linear cryptanalysis. S-DES is a reduced version of the Data Encryption Standard (DES). It also includes a discussion on the subject of cryptology and a literature survey of useful papers regarding cryptography and cryptanalysis. This paper is meant as a tutorial on the fundamentals of differential cryptanalysis and linear cryptanalysis of a Feistel cipher.

Several recently proposed ciphers are built with layers of small S-boxes, interconnected by linear key-dependent layers. Their security relies on the fact, that the classical methods of cryptanalysis (e.g. linear or differential attacks) are based on probabilistic characteristics, which makes their security grow exponentially with the number of rounds Nr. In this paper we study the security of such ciphers under an additional hypothesis: the S-box can be described by an overdefined system of algebraic equations (true with probability 1). We show that this hypothesis is true for both Serpent (due to a small size of S-boxes) and Rijndael (due to unexpected algebraic properties). We study general methods known for solving overdefined systems of equations, such as XL from Eurocrypt'00, and show their inefficiency. Then we introduce a new method called XSL that uses the sparsity of the equations and their specific structure. The XSL attack is very powerful, but heuristic and it is very difficult to evaluate its complexity. The XSL attack has a parameter P, and in theory we show that P should be a constant. The XSL attack would then be polynomial in Nr, with a huge constant that is double-exponential in the size of the S-box. We demonstrated by computer simulations that the XSL attack works well enough on a toy cipher. It seems however that P will rather increase very slowly with Nr. More simulations are needed for bigger ciphers. Our optimistic evaluation shows that the XSL attack might be able to break Rijndael 256 bits and Serpent for key lengths 192 and 256 bits. However if only $P$ is increased by 2 (respectively 4) the XSL attack on Rijndael (respectively Serpent) would become slower than the exhaustive search. At any rate, it seems that the security of these ciphers does NOT grow exponentially with the number of rounds.

The notion of efficient computation is usually identified in cryptography and complexity with (strict) probabilistic polynomial time. However, until recently, in order to obtain *constant-round* zero-knowledge proofs and proofs of knowledge, one had to allow simulators and knowledge-extractors to run in time that is only polynomial *on the average* (i.e., *expected* polynomial time). Recently Barak gave the first constant-round zero-knowledge argument with a *strict* (in contrast to expected) polynomial-time simulator. The simulator in his protocol is a *non-black-box* simulator (i.e., it makes inherent use of the description of the *code* of the verifier). In this paper, we further address the question of strict polynomial-time in constant-round zero-knowledge proofs and arguments of knowledge. First, we show that there exists a constant-round zero-knowledge *argument of knowledge* with a *strict* polynomial-time *knowledge extractor*. As in the simulator of Barak's zero-knowledge protocol, the extractor for our argument of knowledge is not black-box and makes inherent use of the code of the prover. On the negative side, we show that non-black-box techniques are *essential* for both strict polynomial-time simulation and extraction. That is, we show that no (non-trivial) constant-round zero-knowledge proof or argument can have a strict polynomial-time *black-box* simulator. Similarly, we show that no (non-trivial) constant-round zero-knowledge proof or argument of knowledge can have a strict polynomial-time *black-box* knowledge extractor.

We introduce a new methodology for achieving security against adaptive chosen-ciphertext attack (CCA) for public-key encryption schemes, which we call the {\em oblivious decryptors model}. The oblivious decryptors model generalizes both the two-key model of Naor and Yung, as well the Cramer--Shoup encryption schemes. The key ingredient in our new paradigm is Sahai's notion of Simulation-Sound NIZK proofs. Our methodology is easy to use: First, construct an encryption scheme which satisfies the ``bare'' oblivious-decryptors model: This can be done quite easily, with simple proofs of security. Then, by adding a Simulation-Sound NIZK proof, the scheme becomes provably CCA-secure. Note that this paradigm allows for the use of {\em efficient} special-purpose Simulation-Sound NIZK proofs, such as those recently put forward by Cramer and Shoup. We also show how to present all known efficient (provably secure) CCA-secure public-key encryption schemes as special cases of our model.

The boomerang attack is a new and very powerful cryptanalytic technique. However, due to the adaptive chosen plaintext and ciphertext nature of the attack, boomerang key recovery attacks that retrieve key material on both sides of the boomerang distinguisher are hard to mount. We also present a method for using a boomerang distinguisher, which enables retrieving subkey bits on both sides of the boomerang distinguisher. The rectangle attack evolved from the boomerang attack.In this paper we present a new algorithm which improves the results of the rectangle attack. Using these improvements we can attack 3.5-round SC2000 with $2^{67}$ adaptive chosen plaintexts and ciphertexts, and 10-round Serpent with time complexity of $2^{173.8}$ memory accesses (which are equivalent to $2^{165.3}$ Serpent encryptions) with data complexity of $2^{126.3}$ chosen plaintexts.

It has recently been shown that authenticated Byzantine agreement, in which more than a third of the parties are corrupted, cannot be securely realized under concurrent or parallel (stateless) composition. This result puts into question any usage of authenticated Byzantine agreement in a setting where many executions take place. In particular, this is true for the whole body of work of secure multi-party protocols in the case that a third or more of the parties are corrupted. This is because these protocols strongly rely on the extensive use of a broadcast channel, which is in turn realized using authenticated Byzantine agreement. We remark that it was accepted folklore that the use of a broadcast channel (or authenticated Byzantine agreement) is actually essential for achieving meaningful secure multi-party computation whenever a third or more of the parties are corrupted. In this paper we show that this folklore is false. We present a mild relaxation of the definition of secure computation allowing abort. Our new definition captures all the central security issues of secure computation, including privacy, correctness and independence of inputs. However, the novelty of the definition is in {\em decoupling} the issue of agreement from these issues. We then show that this relaxation suffices for achieving secure computation in a point-to-point network. That is, we show that secure multi-party computation for this definition can be achieved for {\em any} number of corrupted parties and {\em without} a broadcast channel (or trusted preprocessing phase as required for running authenticated Byzantine agreement). Furthermore, this is achieved by just replacing the broadcast channel in known protocols with a very simple and efficient echo-broadcast protocol. An important corollary of our result is the ability to obtain multi-party protocols that remain secure under composition, without assuming a broadcast channel.

In (Partial) Key Escrow, how to monitoring a user securitly and efficiently is a very important problem. This paper initially proposes a monitoring scheme of a typical partial key escrow scheme. In this scheme, the escrowed key is not compromised even if the user is monitored for many times.

In a distributed digital signature scheme, a set of participants shares a secret information that allows them to compute a valid signature for a given message. These systems are said to be robust if they can tolerate the presence of some dishonest players. Up to now, all the proposed schemes consider only threshold structures: the tolerated subsets of corrupted players as well as the subsets of players who can sign a message are defined according to their cardinality. We propose a framework that is more general than the threshold one, considering a general access structure of players allowed to sign and a general family of dishonest players that the scheme can tolerate. If these general structures satisfy some combinatorial conditions, we can design a distributed and secure RSA signature scheme for this setting. Our construction is based on the threshold scheme of Shoup.

We propose an elliptic curve scheme over the ring $\entq$, which is efficient and semantically secure in the standard model. There appears to be no previous elliptic curve cryptosystem based on factoring that enjoys both of these properties. KMOV scheme has been used as an underlying primitive to obtain efficiency and probabilistic encryption. Semantic security of the scheme is based on a new decisional assumption, namely, the Decisional Small-$x$ $e$-Multiples Assumption. Confidence on this assumption is also discussed.

A {\em black-box} secret sharing scheme for the threshold access structure $T_{t,n}$ is one which works over any finite Abelian group $G$. Briefly, such a scheme differs from an ordinary linear secret sharing scheme (over, say, a given finite field) in that distribution matrix and reconstruction vectors are defined over the integers and are designed {\em independently} of the group $G$ from which the secret and the shares are sampled. This means that perfect completeness and perfect privacy are guaranteed {\em regardless} of which group $G$ is chosen. We define the black-box secret sharing problem as the problem of devising, for an arbitrary given $T_{t,n}$, a scheme with minimal expansion factor, i.e., where the length of the full vector of shares divided by the number of players $n$ is minimal. Such schemes are relevant for instance in the context of distributed cryptosystems based on groups with secret or hard to compute group order. A recent example is secure general multi-party computation over black-box rings. In 1994 Desmedt and Frankel have proposed an elegant approach to the black-box secret sharing problem based in part on polynomial interpolation over cyclotomic number fields. For arbitrary given $T_{t,n}$ with $0<t<n-1$, the expansion factor of their scheme is $O(n)$. This is the best previous general approach to the problem. Using low degree integral extensions of the integers over which there exists a pair of sufficiently large Vandermonde matrices with co-prime determinants, we construct, for arbitrary given $T_{t,n}$ with $0<t<n-1$ , a black-box secret sharing scheme with expansion factor $O(\log n)$, which we show is minimal.

Joux's protocol is a one round, tripartite key agreement protocol that is more bandwidth-efficient than any previous three-party key agreement protocol. But it is insecure, suffering from a simple man-in-the-middle attack. This paper shows how to make Joux's protocol secure, presenting several tripartite, authenticated key agreement protocols that still require only one round of communication. A pass-optimal authenticated and key confirmed tripartite protocol that generalises the station-to-station protocol is also presented. The security properties of the new protocols are studied using provable security methods and heuristic approaches. Applications for the protocols are also discussed.

We introduce the OAEP++ encoding method, which is an adaptation of the OAEP encoding method, replacing the last step of the encoding operation with an application of a block cipher such as AES. We demonstrate that if $f$ is a one-way trapdoor function that is hard to invert, then OAEP++ combined with $f$ is secure against an IND-CCA2 adversary in the random oracle model. Moreover, the security reduction is tight; an adversary against $f$-OAEP++ can be extended to an $f$-inverter with a running time linear in the number of oracle queries.

The aim of this work is to examine the relation between the notions of semantic security and indistinguishability against chosen ciphertext attacks. For this purpose, a new security notion called non-dividability is introduced independent of attack models, and is shown to be equivalent to both of the two notions. This result is expected to provide a clearer understanding of the equivalence between semantic security and indistinguishability under any form of attack.

In this paper we describe an elementary criterion to determine supersingular hyperelliptic curve of genus $2$, using only the given Weierstrass equation. Furthermore, we show that the discrete logarithm problem defined on any supersingular abelian variety of dimension $2$ over ${\mathbb F}_p, p>16,$ can be embedded to that over the extension field ${\mathbb F}_{p^{k}}$, with $k \leq 6.$ This implies that supersingular hyperelliptic curves are cryptographically weaker than the general case due to the Frey-R$\ddot{u}$ck attack. A family of the hyperelliptic curve $H/{\mathbb F}_p$ of the type $v^2=u^5+a$ and $v^2 = u^5 + au$ have been studied and further examples are listed.

We describe a parallel design principle for hash functions. Given a secure hash function $h:\{0,1\}^n\rightarrow \{0,1\}^m$ with $n\geq 2m$, and a binary tree of $2^t$ processors we show how to construct a secure hash function $h^{*}$ which can hash messages of lengths less than $2^{n-m}$ and a secure hash function $h^{\infty}$ which can hash messages of arbitrary length. The number of parallel rounds required to hash a message of length $L$ is $\lfloor\frac{L}{2^t}\rfloor+t+2$. Further, our algorithm is incrementally parallelizable in the following sense : given a digest produced using a binary tree of $2^t$ processors, we show that the same digest can also be produced using a binary tree of $2^{t^{\prime}}$ $(0\leq t^{\prime}\leq t)$ processors.

We address the problem of testing the hypothesis H_0 that the letters from some alphabet A= {a_1,a_2,..., a_k }, are distributed uniformly against the alternative hypothesis H_1 that the true distribution is not uniform, in case k is large. (It is typical for random number testing and some cryptographic problems where k= 2^{10} - 2^{30} and more). In such a case it is difficult to use the chi-square test because the sample size must be greater than k. We suggest the adaptive chi-square test which can be successfully applied for testing some kinds of H_1 even in case when the sample size is much less than k. This statement is confirmed theoretically and experimentally. The theoretical proof is based on the consideration of one kind of the alternative hypothesis H_1 where the suggested test rejects the null hypothesis when the sample size is O( \sqrt{k} ) (instead of const k for the usual chi-square test ). For experimental investigation of the suggested test we consider a problem of testing ciphered Russian texts. It turns out that the suggested test can distinguish the ciphered texts from random sequences basing on a sample which is much smaller than that required for the usual chi-square test.

We present a new protocol for efficient distributed computation modulo a shared secret. We further present a protocol to distributively generate a random shared prime or safe prime that is much more efficient than previously known methods. This allows to distributively compute shared RSA keys, where the modulus is the product of two safe primes, much more efficiently than was previously known.

In this paper we propose a universal forgery attack of Hess's second ID-based signature scheme against the known-message attack.

We describe very efficient protocols for non-malleable (interactive) proofs of plaintext knowledge for the RSA, Rabin, Paillier, and El-Gamal encryption schemes whose security can be proven in the standard model. We also highlight some important applications of these protocols, where we take care to ensure that our protocols remain secure when run in an asynchronous, concurrent environment: --- Chosen-ciphertext-secure, interactive encryption: In some settings where both parties are on-line (e.g., SSL), an interactive encryption protocol may be used. We construct chosen-ciphertext-secure interactive encryption schemes based on any of the schemes above. In each case, the improved scheme requires only a small overhead beyond the original, semantically-secure scheme. --- Password-based authenticated key exchange: We provide efficient protocols for password-based authenticated key exchange in the public- key model \cite{HK98,B99}. Security of our protocols may be based on any of the cryptosystems mentioned above. --- Deniable authentication: We demonstrate deniable authentication protocols satisfying the strongest notion of security. These are the first efficient constructions based on, e.g., the RSA or computational Diffie-Hellman assumptions. Our techniques provide a general methodology for constructing efficient \emph{non-malleable} (zero-knowledge) proofs of knowledge when shared parameters are available (for our intended applications, these parameters can simply be included as part of users' public keys). Thus, non-malleable proofs of knowledge are easy to achieve ``in practice''.

Proved here is the sufficiency of certain conditions to ensure the Elliptic Curve Digital Signature Algorithm (ECDSA) existentially unforgeable by adaptive chosen-message attacks. The sufficient conditions include (i) a uniformity property and collision-resistance for the underlying hash function, (ii) pseudo-randomness in the private key space for the ephemeral private key generator, (iii) generic treatment of the underlying group, and (iv) a further condition on how the ephemeral public keys are mapped into the private key space. For completeness, a brief survey of necessary security conditions is also given. Some of the necessary conditions are weaker than the corresponding sufficient conditions used in the security proofs here, but others are identical. Despite the similarity between DSA and ECDSA, the main result is not appropriate for DSA, because the fourth condition above seems to fail for DSA. (The corresponding necessary condition is plausible for DSA, but is not proved here nor is the security of DSA proved assuming this weaker condition.) Brickell et al., Jakobsson et al. and Pointcheval et al. only consider signature schemes that include the ephemeral public key in the hash input, which ECDSA does not do, and moreover, assume a condition on the hash function stronger than the first condition above. This work seems to be the first advance in the provable security of ECDSA.

We propose a new technique for making mix nets robust, called randomized partial checking (RPC). The basic idea is that rather than providing a proof of completely correct operation, each server provides strong evidence of its correct operation by revealing a pseudo-randomly selected subset of its input/output relations. Randomized partial checking is exceptionally efficient compared to previous proposals for providing robustness; the evidence provided at each layer is shorter than the output of that layer, and producing the evidence is easier than doing the mixing. It works with mix nets based on any encryption scheme (i.e., on public-key alone, and on hybrid schemes using public-key/symmetric-key combinations). It also works both with Chaumian mix nets where the messages are successively encrypted with each servers' key, and with mix nets based on a single public key with randomized re-encryption at each layer. Randomized partial checking is particularly well suited for voting systems, as it ensures voter privacy and provides assurance of correct operation. Voter privacy is ensured (either probabilistically or cryptographically) with appropriate design and parameter selection. Unlike previous work, our work provides voter privacy as a global property of the mix net rather than as a property ensured by a single honest server. RPC-based mix nets also provide very high assurance of a correct election result, since a corrupt server is very likely to be caught if it attempts to tamper with even a couple of ballots.

In this paper we investigate the timed release of standard digital signatures, and demonstrate how to do it for RSA, Schnorr and DSA signatures. Such signatures, once released, cannot be distinguished from signatures of the same type obtained without a timed release, making it transparent to an observer of the end result. While previous work has allowed timed release of signatures, these have not been standard, but special-purpose signatures. Building on the recent work by Boneh and Naor on timed commitments, we introduce the notion of a reusable time-line, which, besides allowing the release of standard signatures, lowers the session costs of existing timed applications.

We introduce a novel technique for computation of consecutive preimages of hash chains. Whereas traditional techniques have a memory-times-computation complexity of $O(n)$ per output generated, the complexity of our technique is only $O(log^2 \, n)$, where $n$ is the length of the chain. Our solution is based on the same principal amortization principle as \cite{J01}, and has the same asymptotic behavior as this solution. However, our solution decreases the real complexity by approximately a factor of two. Thus, the computational costs of our solution are approximately $ {1 \over 2} log_2 \, n$ hash function applications, using only a little more than $log_2 \, n$ storage cells. A result of independent interest is the lower bounds we provide for the optimal (but to us unknown) solution to the problem we study. The bounds show that our proposed solution is very close to optimal. In particular, we show that there exists no improvement on our scheme that reduces the complexity by more than an approximate factor of two.

The Fiat-Shamir paradigm for transforming identification schemes into signature schemes has been popular since its introduction because it yields efficient signature schemes, and has been receiving renewed interest of late as the main tool in deriving forward-secure signature schemes. We find minimal (meaning necessary and sufficient) conditions on the identification scheme to ensure security of the signature scheme in the random oracle model, in both the usual and the forward-secure cases. Specifically we show that the signature scheme is secure (resp. forward-secure) against chosen-message attacks in the random oracle model if and only if the underlying identification scheme is secure (resp. forward-secure) against impersonation under passive (i.e.. eavesdropping only) attacks, and has its commitments drawn at random from a large space. An extension is proven incorporating a random seed into the Fiat-Shamir transform so that the commitment space assumption may be removed.

For independent binary random variables x_1,...,x_n and a Boolean function f(x), x=(x_1,...,x_n), we suppose that |1/2 - P{x_i = 1}|<=e, 1<=i<=n. Under these conditions we present new characteristics D_F(f(),e) = max{|1/2 - P{y=1}|} of the probability properties of Boolean functions, where y = F(x), and F(x) being equal to 1) F(x)=f(x), 2) F(x)=f(x)+(a,x), 3) F(x)=f(x)+f(x+a), and investigate their properties. Special attention is paid to the classes of balanced and correlation immune functions, bent functions, and second order functions, for which upper estimates of D_F(f(),e) are found and statements on behaviour of sequences f^{(n)}(x) of functions of n arguments are made.

We describe a cryptanalytical technique for distinguishing some stream ciphers from a truly random process. Roughly, the ciphers to which this method applies consist of a ``non-linear process'' (say, akin to a round function in block ciphers), and a ``linear process'' such as an LFSR (or even fixed tables). The output of the cipher can be the linear sum of both processes. To attack such ciphers, we look for any property of the ``non-linear process'' that can be distinguished from random. In addition, we look for a linear combination of the linear process that vanishes. We then consider the same linear combination applied to the cipher's output, and try to find traces of the distinguishing property. In this report we analyze two specific ``distinguishing properties''. One is a linear approximation of the non-linear process, which we demonstrate on the stream cipher SNOW. This attack needs roughly $2^{95}$ words of output, with work-load of about $2^{100}$. The other is a ``low-diffusion'' attack, that we apply to the cipher Scream-0. The latter attack needs only about $2^{43}$ bytes of output, using roughly $2^{50}$ space and $2^{80}$ time.

We report on the design of Scream, a new software-efficient stream cipher, which was designed to be a ``more secure SEAL''. Following SEAL, the design of Scream resembles in many ways a block-cipher design. The new cipher is roughly as fast as SEAL, but we believe that it offers a significantly higher security level. In the process of designing this cipher, we re-visit the SEAL design paradigm, exhibiting some tradeoffs and limitations.

In this paper we propose an identity(ID)-based signature scheme using gap Diffie-Hellman (GDH) groups. Our scheme is proved secure against existential forgery on adaptively chosen message and ID attack under the random oracle model. Using GDH groups obtained from bilinear pairings, as a special case of our scheme, we obtain an ID-based signature scheme that shares the same system parameters and the same private/public key pairs with the ID-based encryption scheme (BF-IBE) by Boneh and Franklin, and is as efficient as the BF-IBE. Combining our signature scheme with the BF-IBE yields a complete solution of an ID-based public key system. It can be an alternative for certificate-based public key infrastructures, especially when efficient key management and moderate security are required.

We discuss a modification of the Cramer-Shoup strong-RSA signature scheme. Our proposal also presumes the strong RSA assumption (and a collision-intractable hash function for long messages), but -without loss in performance- the size of a signature is almost halved compared to the original scheme. We also show how to turn the signature scheme into a "lightweight" anonymous (but linkable) group identification protocol without random oracles.

Motivated by emerging needs in online interactions, we define a new type of digital signature called a `Content Extraction Signature' (CES). A CES allows the owner, Bob, of a document signed by Alice, to produce an `extracted signature' on selected extracted portions of the original document, which can be verified to originate from Alice by any third party Cathy, while hiding the unextracted (removed) document portions. The new signature therefore achieves verifiable content extraction with minimal multi-party interaction. We specify desirable functional and security requirements for a CES (including an efficiency requirement: a CES should be more efficient in either computation or communication than the simple multiple signature solution). We propose and analyze four CES constructions which are provably secure with respect to known cryptographic assumptions and compare their performance characteristics.

In time of internet attacks is important to use cryptographic protcols and algorithms to secure private data that are sent via Internet. But using of such protocol is not enough. To really secure our data we must know that used protocol is secure. For this purpose where a lot of methods design such as well-known BAN logic. In this articel we want to present DLA (Database and Logic Abduction)- method that is used to prove that a security or cryptographic protocol is secure or it is possible perform an attack.

One-time signature schemes have found numerous applications: in ordinary, on-line/off-line, and forward-secure signatures. More recently, they have been used in multicast and broadcast authentication. We propose a one-time signature scheme with very efficient signing and verifying, and short signatures. Our scheme is well-suited for broadcast authentication, and, in fact, can be viewed as an improvement of the BiBa one-time signature (proposed by Perrig in CCS 2001 for broadcast authentication).

We study the problem of root extraction in finite Abelian groups, where the group order is unknown. This is a natural generalization of the problem of decrypting RSA ciphertexts. We study the complexity of this problem for generic algorithms, that is, algorithms that work for any group and do not use any special properties of the group at hand. We prove an exponential lower bound on the generic complexity of root extraction, even if the algorithm can choose the "public exponent" itself. In other words, both the standard and the strong RSA assumption are provably true w.r.t. generic algorithms. The results hold for arbitrary groups, so security w.r.t. generic attacks follows for any cryptographic construction based on root extracting. As an example of this, we revisit Cramer-Shoup signature scheme. We modify the scheme such that it becomes a generic algorithm. This allows us to implement it in RSA groups without the original restriction that the modulus must be a product of safe primes. It can also be implemented in class groups. In all cases, security follows from a well defined complexity assumption (the strong root assumption), without relying on random oracles, and the assumption is shown to be true w.r.t. generic attacks.

We describe general exponent group signature schemes and show how these naturally give rise to identity based signature schemes if pairings are used. We prove these schemes to be secure in the random oracle model. Furthermore we describe a particular identity based signature scheme which is quite efficient in terms of bandwidth and computing time, and we develop a further scheme which is not derived from a general exponent group signature scheme. The realization of these schemes uses supersingular elliptic curves and the Tate pairing, which is more efficient than the Weil pairing. Finally we show that these schemes have a more natural solution, than Shamir's original scheme, to the ``escrow'' property that all identity based signature schemes suffer from.

This paper considers arbitrary-length chosen-ciphertext secure asymmetric encryption, thus addressing what is actually needed for a practical usage of strong public-key cryptography in the real world. We put forward two generic constructions, gem-1 and gem-2, which apply to explicit fixed-length weakly secure primitives and provide a strongly secure (IND-CCA2) public-key encryption scheme for messages of unfixed length (typically computer files). Our techniques optimally combine a single call to any one-way trapdoor function with repeated encryptions through some weak block-cipher (a simple xor is fine) and hash functions of fixed-length input so that a minimal number of calls to these functions is needed. Our encryption/decryption throughputs are comparable to the ones of standard methods (asymmetric encryption of a session key + symmetric encryption with multiple modes). In our case, however, we formally prove that our designs are secure in the strongest sense and provide complete security reductions holding in the random oracle model.

This paper describes malicious applets that use Java's sophisticated graphic features to rectify the browser's padlock area and cover the address bar with a false https domain name. The attack was successfully tested on Netscape's Navigator and Microsoft's Internet Explorer; we consequently recommend to neutralize Java whenever funds or private data transit via these browsers and patch the flaw in the coming releases. The degree of novelty of our attack is unclear since similar (yet non-identical) results can be achieved by spoofing as described by Felten; however our scenario is much simpler to mount as it only demands the inclusion of an applet in the attacker's web page. In any case, we believe that the technical dissection of our malicious Java code has an illustrative value in itself.

Secure and reliable group communication is an active area of research. Its popularity is caused by the growing importance of group-oriented and collaborative applications. The central research challenge is secure and efficient group key management. While centralized methods are often appropriate for key distribution in large multicast-style groups, many collaborative group settings require distributed key agreement techniques. This work investigates a novel group key agreement approach which blends so-called key trees with Diffie-Hellman key exchange. It yields a secure protocol suite (TGDH) that is both simple and fault-tolerant. Moreover, the efficiency of TGDH appreciably surpasses that of prior art.

We describe fast new algorithms to implement recent cryptosystems based on the Tate pairing. In particular, our techniques improve pairing evaluation speed by a factor of about 55 compared to previously known methods in characteristic 3, and attain performance comparable to that of RSA in larger characteristics. We also propose faster algorithms for scalar multiplication in characteristic 3 and square root extraction over $\GF{p^m}$, the latter technique being also useful in contexts other than that of pairing-based cryptography.

For speeding up elliptic curve scalar multiplication and making it secure against side-channel attacks such as timing or power analysis, various methods have been proposed using specifically chosen elliptic curves. We show that both goals can be achieved simultaneously even for conventional elliptic curves over $\mathbb{F}_p$. This result is shown via two facts. First, we recall the known fact that every elliptic curve over $\mathbb{F}_p$ admits a scalar multiplication via a (Montgomery ladder) Lucas chain. As such chains are known to be resistant against timing- and simple power/electromagnetic radiation analysis attacks, the security of our scalar multiplication against timing and simple power/electromagnetic radiation analysis follows. Second, we show how to parallelize the 19 multiplications within the resulting \lq\lq double" and \lq\lq add" formulas of the Lucas chain for the scalar multiplication. This parallelism together with the Lucas chain results in 10 parallel field multiplications per bit of the scalar. Finally, we also report on a concrete successful implementation of the above mentioned scalar multiplication algorithm on a very recently developed and commercially available coprocessor for smart cards.

For certain security applications, including identity based encryption and short signature schemes, it is useful to have abelian varieties with security parameters that are neither too small nor too large. Supersingular abelian varieties are natural candidates for these applications. This paper determines exactly which values can occur as the security parameters of supersingular abelian varieties (in terms of the dimension of the abelian variety and the size of the finite field), and gives constructions of supersingular abelian varieties which are optimal for use in cryptography.

Filiol and Fontaine recently proposed a family of stream ciphers named COS. COS is based on nonlinear feedback shift registers and was claimed to be with high cryptographic strength. Babbage showed that COS $(2,128)$ Mode II is extremely weak. But Babbage's attack is too expensive to break the COS $(2,128)$ Mode I (the complexity is around $2^{52}$). In this paper, we show that the COS $(2,128)$ Mode I is too weak. With about $2^{16}$-bit known plaintext, the secret information could be recovered with small amount of memory and computation time (less than one second on a Pentium IV Processor).

We present an efficient identity-based signature scheme which makes use of bilinear pairings on elliptic curves. Our scheme is similar to the generalized ElGamal signature scheme. We consider the security of our scheme.

This report surveys on a series of Square attacks on reduced-round versions of the Skipjack block cipher. {\bf Skipjack} is an iterated block cipher encrypting 64-bit plaintext blocks into 64-bit ciphertext blocks, using an 80-bit key. Its design is based on a generalized Feistel Network making up 32 rounds of two different types. This cipher was developed by the National Security Agency for the Clipper chip and Fortezza PC card.

In the literature, voting protocols are considered secure if they satisfy requirements such as privacy, accuracy, robustness, etc. It can be time consuming to evaluate a voting protocol with respect to all these requirements and it is not clear that the list of known requirements is complete. Perhaps because of this many papers on electronic voting do not offer any security proof at all. As a solution to this, we suggest evaluating voting schemes in the universal composability framework. We investigate the popular class of voting schemes based on homomorphic threshold encryption. It turns out that schemes in this class realize an ideal voting functionality that takes the votes as input and outputs the result. This ideal functionality corresponds closely to the well-known ballot box model used today in manual voting. Security properties such as privacy, accuracy and robustness now follow as easy corollaries. We note that some security requirements, for instance incoercibility, are not addressed by our solution. Security holds in the random oracle model against a non-adaptive adversary. We show with a concrete example that the schemes are not secure against adaptive adversaries. We proceed to sketch how to make them secure against adaptive adversaries in the erasure model with virtually no loss of efficiency. We also sketch how to achieve security against adaptive adversaries in the erasure-free model.

We introduce a novel amortization technique for computation of consecutive preimages of hash chains, given knowledge of the seed. While all previously known techniques have a memory-times-computational complexity of $O(n)$ per chain element, the complexity of our technique can be upper bounded at $O(log^2 n)$, making it a useful primitive for low-cost applications such as authentication, signatures and micro-payments. Our technique uses a logarithmic number of {\em pebbles} associated with points on the hash chain. The locations of these pebbles are modified over time. Like fractals, where images can be found within images, the pebbles move within intervals and sub-intervals according to a highly symmetric pattern.

An accumulator scheme, introduced be Benaloh and de Mare and further studied by Baric̈ and Pfitzmann, is an algorithm that allows to hash a large set of inputs into one short value, called the \textit{accumulator}, such that there is a short witness that a given input was incorporated into the accumulator. We put forward the notion of \textit{dynamic accumulators}, i.e., a method that allows to dynamically add and delete inputs from the accumulator, such that the cost of an add or delete is independent on the number of accumulated values. We achieve this under the strong RSA assumption. For this construction, we also show an efficient zero-knowledge protocol for proving that a committed value is in the accumulator. In turn, our construction of dynamic accumulator enables efficient membership revocation in the anonymous setting. This method applies to membership revocation in group signature schemes, such as the one due to Ateniese et al., and efficient revocation of credentials in anonymous credential systems, such as the one due to Camenisch and Lysyanskaya. Using our method, allowing revocation does not alter the complexity of any operations of the underlying schemes. In particular, the cost of a group signature verification or credential showing increases by only a small constant factor, less than 2. All previously known methods (such as the ones due to Bresson and Stern and Ateniese and Tsudik incurred an increase in these costs that was linear in the number of members.

This document is an initial proposal for a draft for a forthcoming ISO standard on public-key encryption. It is hoped that this proposal will serve as a basis for discussion, from which a consensus for a standard may be formed.

We describe an ID based authenticated two pass key agreement protocol which makes use of the Weil pairing. The protocol is described and its properties are discussed including the ability to add key confirmation.

This document compares the two published RSA-based hybrid encryption schemes having linear reduction in their security proof: RSA-KEM with DEM1 and RSA-REACT. While the performance of RSA-REACT is worse than the performance of RSA-KEM+DEM1, a complete proof of its security has already been published. This is indeed an advantage, because we show that the security result for RSA-KEM+DEM1 has a small hole. We provide here a complete proof of the security of RSA-KEM+DEM1. We also propose some changes to RSA-REACT to improve its efficiency without changing its security, and conclude that this new RSA-REACT is a generalisation of RSA-KEM+DEM1, with at most the same security, and with possibly worse performance. Therefore we show that RSA-KEM+DEM1 should be preferred to RSA-REACT.

I n this paper, some new notions of soundness in public-key model are presented. We clarify the relationships among our new notions of soundness and the original 4 soundness notions presented by Micali and Reyzin. Our new soundness notions also characterize a new model for ZK protocols in public key model: weak soundness model. By ``weak” we mean for each common input x selected by a malicious prover on the fly, x is used by the malicious prover at most a-priori bounded polynomial times. The weak soundness model just lies in between BPK model and UPK model. Namely, it is weaker than BPK model but stronger than UPK model. In the weak soundness model (also in the UPK model, since weak soundness model implies UPK model), we get a 3-round black-box rZK arguments with weak resettable soundness for NP. Note that simultaneous resettability is an important open problem in the field of ZK protocols. And Reyzin has proven that there are no ZK protocols with resettable soundness in the BPK model. It means that to achieve simultaneous resettability one needs to augment the BPK model in a reasonable fashion. Although Barak et al. [BGGL01] have proven that any language which has a black-box ZK arguments with resettable soundness is in BPP. It is the weak soundness that makes us to get simultaneous resettability. More interestingly, our protocols work in a somewhat ``parallel repetition” manner to reduce the error probability and the verifier indeed has secret information with respect to historical transcripts. Note that in general the error probability of such protocols can not be reduced by parallel repetition. [BIN97] At last, we give a 3-round non-black-box rZK arguments system with resettable soundness for NP in the preprocessing model in which a trusted third party is assumed. Our construction for such protocol is quite simple. Note that although the preprocessing model is quite imposing but it is still quite reasonable as indicated in [CGGM00]. For example, in many e-commerce setting a trusted third party is often assumed. The critical tools used in this paper are: verifiable pseudorandom functions, zap and complexity leveraging. To our knowledge, our protocols are also the second application of verifiable pseudorandom functions. The first application is the 3-round rZK arguments with one-time soundness for NP in the public-key model as indicated by Micali and Reyzin [MR01a].

A new public key encryption scheme, along with several variants, is proposed and analyzed. The scheme and its variants are quite practical, and are proved secure against adaptive chosen ciphertext attack under standard intractability assumptions. These appear to be the first public-key encryption schemes in the literature that are simultaneously practical and provably secure.

In this paper we show that any {\em two-party} functionality can be securely computed in a {\em constant number of rounds}, where security is obtained against malicious adversaries that may arbitrarily deviate from the protocol specification. This is in contrast to Yao's constant-round protocol that ensures security only in the face of semi-honest adversaries, and to its malicious adversary version that requires a polynomial number of rounds. In order to obtain our result, we present a constant-round protocol for secure coin-tossing of polynomially many coins (in parallel). We then show how this protocol can be used in conjunction with other existing constructions in order to obtain a constant-round protocol for securely computing any two-party functionality. On the subject of coin-tossing, we also present a constant-round {\em perfect} coin-tossing protocol, where by ``perfect'' we mean that the resulting coins are guaranteed to be statistically close to uniform (and not just pseudorandom).

A new family of very fast stream ciphers called COS (for “crossing over system”) has been proposed by Filiol and Fontaine, and seems to have been adopted for at least one commercial standard. COS(2,128) Mode I and COS(2,128) Mode II are particular members of this family for which the authors proposed a cryptanalysis challenge. The ciphers accept secret keys of 256, 192 or 128 bits. In this note we cryptanalyse both of these ciphers, using a small amount of known keystream — with negligible effort in the case of Mode II, and with effort well below that required for a single DES key search in the case of Mode I.

We put forward a new type of computationally-sound proof systems, called universal-arguments, which are related but different from both CS-proofs (as defined by Micali) and arguments (as defined by Brassard, Chaum and Crepeau). In particular, we adopt the instance-based prover-efficiency paradigm of CS-proofs, but follow the computational-soundness condition of argument systems (i.e., we consider only cheating strategies that are implementable by polynomial-size circuits). We show that universal-arguments can be constructed based on standard intractability assumptions that refer to polynomial-size circuits (rather than assumptions referring to subexponential-size circuits as used in the construction of CS-proofs). As an application of universal-arguments, we weaken the intractability assumptions used in the recent non-black-box zero-knowledge arguments of Barak. Specifically, we only utilize intractability assumptions that refer to polynomial-size circuits (rather than assumptions referring to circuits of some ``nice'' super-polynomial size).

Following Dwork, Naor, and Sahai (30th STOC, 1998), we consider concurrent execution of protocols in a semi-synchronized network. Specifically, we assume that each party holds a local clock such that a constant bound on the relative rates of these clocks is a-priori known, and consider protocols that employ time-driven operations (i.e., time-out in-coming messages and delay out-going messages). We show that the constant-round zero-knowledge proof for NP of Goldreich and Kahan (Jour. of Crypto., 1996) preserves its security when polynomially-many independent copies are executed concurrently under the above timing model. We stress that our main result establishes zero-knowledge of interactive proofs, whereas the results of Dwork et al. are either for zero-knowledge arguments or for a weak notion of zero-knowledge (called $\epsilon$-knowledge) proofs. Our analysis identifies two extreme schedulings of concurrent executions under the above timing model: the first is the case of parallel execution of polynomially-many copies, and the second is of concurrent execution of polynomially-many copies such the number of copies that are simultaneously active at any time is bounded by a constant (i.e., bounded simultaneity). Dealing with each of these extreme cases is of independent interest, and the general result (regarding concurrent executions under the timing model) is obtained by combining the two treatments.

Some attacks on cryptographic systems exploit the leakage of information through so-called ``side channels'', such as power consumption or time employed by a computation. For cryptosystems involving an exponentiation, a few possible countermeasures are suggested. In the case of elliptic curves over a binary finite field, we show how to split point addition into two blocks which, through the addition of a little overhead, can be made undistinguishable from a point doubling. This allows the whole exponentiation process to be performed as a sequence of homogeneous steps. To add some randomization to the exponentiation process in the ECC case, we suggest the use of points of small order, computed on the fly. This presents some disadvantages over known methods, but allows to avoid the storage of points in non-volatile RAM. A multiplicative variation of ``additive exponent blinding'' is suggested. This involves a two-phase exponentiation and is valid both for discrete log and RSA settings. Computer experiments implementing some of these ideas are described and analyzed.

We present an Extended Quadratic Frobenius Primality Test (EQFT), which is related to the Miller-Rabin test and the Quadratic Frobenius test (QFT) by Grantham. EQFT is well-suited for generating large, random prime numbers since on a random input number, it takes time about equivalent to 2 Miller-Rabin tests, but has much smaller error probability. EQFT extends QFT by verifying additional algebraic properties related to the existence of elements of order 3 and 4. We obtain a simple closed expression that upper bounds the probability of acceptance for any input number. This in turn allows us to give strong bounds on the average-case behaviour of the test: consider the algorithm that repeatedly chooses random odd $k$ bit numbers, subjects them to $t$ iterations of our test and outputs the first one found that passes all tests. We obtain numeric upper bounds for the error probability of this algorithm as well as a general closed expression bounding the error. For instance, it is at most $2^{-143}$ for $k=500, t=2$. Compared to earlier similar results for the Miller-Rabin test, the results indicates that our test in the average case has the effect of 9 Miller-Rabin tests, while only taking time equivalent to about 2 such tests. We also give bounds for the error in case a prime is sought by incremental search from a random starting point. While EQFT is slower than the average case on a small set of inputs, we present a variant that is always fast, i.e.takes time about 2 Miller-Rabin tests. The variant has slightly larger worst case error probability than EQFT, but still improves on previous proposed tests.

A group signature scheme allows any group member to sign on behalf of the group in an anonymous and unlinkable fashion. In the event of a dispute, a designated trusted entity can reveal the identity of the signer. Group signatures are claimed to have many useful applications such as voting and electronic cash. A number of group signature schemes have been proposed to-date. However, in order for the whole group signature concept to become practical and credible, the problem of secure and efficient group member revocation must be addressed. In this paper, we construct a new revocation method for group signatures based on the signature scheme by Ateniese et al. at Crypto 2000. This new method represents an advance in the state-of-the-art since the only revocation schemes proposed thus far are either: 1) based on implicit revocation and the use of fixed time periods, or 2) require the signature size to be linear in the number of revoked members. Our method, in contrast, does not rely on time periods, offers constant-length signatures and constant work for the signer.

In this paper, we describe an important shortcoming of the first self-certified model proposed by Girault, that may be exploited by the authority to compute users' secret keys. We also show, while it is possible to make the attack ineffective by taking additional precautions, the resulting model loses all merits of the original model and does no longer meet the primary contribution of the self-certified notion.

In this paper, we first show that three public-key $(k,n)$-traceability schemes can be derived from an $[n,u,d]$-linear code ${\cal C}$ such that $d \geq 2k+1$. The previous schemes are obtained as special cases. This observation gives a more freedom and a new insight to this field. For example, we show that Boneh-Franklin scheme is equivalent to a slight modification of the corrected Kurosawa-Desmedt scheme. This means that BF scheme is redundant or overdesigned because the modified KD scheme is much simpler. It is also shown that the corrected KD scheme is the best among them.

We describe a fast hash algorithm that maps arbitrary messages onto points of an elliptic curve defined over a finite field of characteristic 3. Our new scheme runs in time $O(m^2)$ for curves over $\GF{3^m}$. The best previous algorithm for this task runs in time $O(m^3)$. Experimental data confirms the speedup by a factor $O(m)$, or approximately a hundred times for practical $m$ values. Our results apply for both standard and normal basis representations of $\GF{3^m}$.

HMAC is the internet standard for message authentication. What distinguishes HMAC from other MAC algorithms is that it provides proofs of security assuming that the underlying cryptographic hash (e.g. SHA-1) has some reasonable properties. HMAC is efficient for long messages, however, for short messages the nested construction results in a significant inefficiency. For example to MAC a message shorter than a block, HMAC requires at least two calls to the compression function rather than one. This inefficiency may be particularly high for some applications, like message authentication of signaling messages, where the individual messages may all fit within one or two blocks. Also for TCP/IP traffic it is well known that large number of packets (e.g. acknowledgment) have sizes around 40 bytes which fit within a block of most cryptographic hashes. We propose an enhancement that allows both short and long messages to be message authenticated more efficiently than HMAC while also providing proofs of security. In particular, for a message smaller than a block our MAC only requires one call to the compression function.

In using elliptic curves for cryptography, one often needs to construct elliptic curves with a given or known number of points over a given finite field. In the context of primality proving, Atkin and Morain suggested the use of the theory of complex multiplication to construct such curves. One of the steps in this method is the calculation of the Hilbert class polynomial $H_D(X)$ modulo some integer $p$ for a certain fundamental discriminant $D$. The usual way of doing this is to compute $H_D(X)$ over the integers and then reduce modulo $p$. But this involves computing the roots with very high accuracy and subsequent rounding of the coefficients to the closest integer. (Such accuracy issues also arise for higher genus cases.) We present a modified version of the Chinese remainder theorem (CRT) to compute $H_D(X)$ modulo $p$ directly from the knowledge of $H_D(X)$ modulo enough small primes. Our algorithm is inspired by Couveigne's method for computing square roots in the number field sieve, which is useful in other scenarios as well. It runs in heuristic expected time less than the CRT method in [CNST]. Moreover, our method requires very few digits of precision to succeed, and avoids calculating the exponentially large coefficients of the Hilbert class polynomial over the integers.

We argue that threshold trust is not an option in most of the real-life electronic auctions. We then propose two new cryptographic Vickrey auction schemes that involve, apart from the bidders and the seller $S$, an auction authority $A$ so that unless $S$ and $A$ collude the outcome of auctions will be correct, and moreover, $S$ will not get any information about the bids, while $A$ will learn bid statistics. Further extensions make it possible to decrease damage that colluding $S$ and $A$ can do, and to construct $(m+1)$st price auction schemes. The communication complexity between the $S$ and $A$ in medium-size auctions is at least one order of magnitude less than in the Naor-Pinkas-Sumner scheme.

We consider the set of slopes of lines formed by joining all pairs of points in some subset S of a Desarguesian affine plane of prime order, p. If all the slopes are distinct and non-infinite, we have a slope packing; if every possible non-infinite slope occurs, then we have a slope covering. We review and unify some results on these problems that can be derived from the study of Sidon sets and sum covers. Then we report some computational results we have obtained for small values of p. Finally, we point out some connections between slope packings and coverings and generic algorithms for the discrete logarithm problem in prime order (sub)groups. Our results provide a combinatorial characterization of such algorithms, in the sense that any generic algorithm implies the existence of a certain slope packing or covering, and conversely.

We consider threshold cryptosystems over a composite modulus $N$ where the \emph{factors} of $N$ are shared among the participants as the secret key. This is a new paradigm for threshold cryptosystems based on a composite modulus, differing from the typical treatment of RSA-based systems where a ``decryption exponent'' is shared among the participants. Our approach yields solutions to some open problems in threshold cryptography; in particular, we obtain the following: 1. \emph{Threshold homomorphic encryption}. A number of applications (e.g., electronic voting or efficient multi-party computation) require threshold homomorphic encryption schemes. We present a protocol for threshold decryption of the homomorphic Goldwasser-Micali encryption scheme \cite{GM84}, answering an open question of \cite{FPS00}. 2. \emph{Threshold cryptosystems as secure as factoring}. We describe a threshold version of a variant of the signature standards ISO 9796-2 and PKCS\#1 v1.5 (cf.\ \cite[Section 11.3.4]{MvOV}), thus giving the first threshold signature scheme whose security (in the random oracle model) is equivalent to the hardness of factoring \cite{C02}. Our techniques may be adapted to distribute the Rabin encryption scheme \cite{R79} whose semantic security may be reduced to the hardness of factoring. 3. \emph{Efficient threshold schemes without a trusted dealer.} Because our schemes only require sharing of $N$ --- which furthermore need not be a product of strong primes --- our schemes are very efficient (compared to previous schemes) when a trusted dealer is not assumed and key generation is done in a distributed manner. Extensions to achieve robustness and proactivation are also possible with our schemes.

Many of the keystream generators which are used in practice are LFSR-based in the sense that they produce the keystream according to a rule $y=C(L(x))$, where $L(x)$ denotes an internal linear bitstream, produced by a small number of parallel linear feedback shift registers (LFSRs), and $C$ denotes some nonlinear compression function. We present an $n^{O(1)} 2^{(1-\alpha)/(1+\alpha)n}$ time bounded attack, the FBDD-attack, against LFSR-based generators, which computes the secret initial state $x\in\booln$ from $cn$ consecutive keystream bits, where $\alpha$ denotes the rate of information, which $C$ reveals about the internal bitstream, and $c$ denotes some small constant. The algorithm uses Free Binary Decision Diagrams (FBDDs), a data structure for minimizing and manipulating Boolean functions. The FBDD-attack yields better bounds on the effective key length for several keystream generators of practical use, so a $0.656n$ bound for the self-shrinking generator, a $0.6403 n$ bound for the A5/1 generator, used in the GSM standard, a $0.6n$ bound for the $E_0$ encryption standard in the one level mode, and a $0.8823n$ bound for the two-level $E_0$ generator used in the Bluetooth wireless LAN system.

Canetti and Fischlin have recently proposed the security notion {\em universal composability} for commitment schemes and provided two examples. This new notion is very strong. It guarantees that security is maintained even when an unbounded number of copies of the scheme are running concurrently, also it guarantees non-malleability, resilience to selective decommitment, and security against adaptive adversaries. Both of their schemes uses $\Theta(k)$ bits to commit to one bit and can be based on the existence of trapdoor commitments and non-malleable encryption. We present new universally composable commitment schemes based on the Paillier cryptosystem and the Okamoto-Uchiyama cryptosystem. The schemes are efficient: to commit to $k$ bits, they use a constant number of modular exponentiations and communicates $O(k)$ bits. Further more the scheme can be instantiated in either perfectly hiding or perfectly binding versions. These are the first schemes to show that constant expansion factor, perfect hiding, and perfect binding can be obtained for universally composable commitments. We also show how the schemes can be applied to do efficient zero-knowledge proofs of knowledge that are universally composable.

We propose a fully functional identity-based encryption scheme (IBE). The scheme has chosen ciphertext security in the random oracle model assuming an elliptic curve variant of the computational Diffie-Hellman problem. Our system is based on bilinear maps between groups. The Weil pairing on elliptic curves is an example of such a map. We give precise definitions for secure identity based encryption schemes and give several applications for such systems.

A new family of broadcast encryption schemes (BESs), which will be called linear broadcast encryption schemes (LBESs), is presented in this paper by using linear algebraic techniques. This family generalizes most previous proposals and provide a general framework to the study of broadcast encryption schemes. We present a method to construct LBESs for a general specification structure in order to find schemes that fit in situations that have not been considered before.

The most important point in the design of broadcast encryption schemes (BESs) is obtain a good trade-off between the amount of secret information that must be stored by every user and the length of the broadcast message, which are measured, respectively, by the information rate $\rho$ and the broadcast information rate $\rho_B$. In this paper we present a simple method to combine two given BESs in order to improve the trade-off between $\rho$ and $\rho_B$ by finding BESs with good information rate $\rho$ for arbitrarily many different values of the broadcast information rate $\rho_B$. We apply this technique to threshold $(R,T)$-BESs and we present a method to obtain, for every rational value $1/R \le \rho_B \le 1$, a $(R,T)$-BES with optimal information rate $\rho$ among all $(R,T)$-BESs that can be obtained by combining two of the $(R,T)$-BESs proposed by Blundo et al.

A metering scheme is a method by which an audit agency is able to measure the interaction between servers and clients during a certain number of time frames. Naor and Pinkas proposed metering schemes where any server is able to compute a proof, i.e., a value to be shown to the audit agency at the end of each time frame, if and only if it has been visited by a number of clients larger than or equal to some threshold $h$ during the time frame. Masucci and Stinson showed how to construct a metering scheme realizing any access structure, where the access structure is the family of all subsets of clients which enable a server to compute its proof. They also provided lower bounds on the communication complexity of metering schemes. In this paper we describe a linear algebraic approach to design metering schemes realizing any access structure. Namely, given any access structure, we present a method to construct a metering scheme realizing it from any linear secret sharing scheme with the same access structure. Besides, we prove some properties about the relationship between metering schemes and secret sharing schemes. These properties provide some new bounds on the information distributed to clients and servers in a metering scheme. According to these bounds, the optimality of the metering schemes obtained by our method relies upon the optimality of the linear secret sharing schemes for the given access structure.

A family $(S_t)$ of sets is $p$-bounded Diophantine if $S_t$ has a representing $p$-bounded polynomial $R_{S,t}$, s.t. $x\in S_t \iff (\exists y)[R_{S}(x;y)=0]$. We say that $(S_t)$ is unbounded Diophantine if additionally, $R_{S,t}$ is a fixed $t$-independent polynomial. We show that $p$-bounded (resp., unbounded) Diophantine set has a polynomial-size (resp., constant-size) statistical zero-knowledge proof system that a committed tuple $x$ belongs to $S$. We describe efficient SZK proof systems for several cryptographically interesting sets. Finally, we show how to prove in SZK that an encrypted number belongs to $S$.

We present several new and fairly practical public-key encryption schemes and prove them secure against adaptive chosen ciphertext attack. One scheme is based on Paillier's Decision Composite Residuosity (DCR) assumption, while another is based in the classical Quadratic Residuosity (QR) assumption. The analysis is in the standard cryptographic model, i.e., the security of our schemes does not rely on the Random Oracle model. We also introduce the notion of a universal hash proof system. Essentially, this is a special kind of non-interactive zero-knowledge proof system for an NP language. We do not show that universal hash proof systems exist for all NP languages, but we do show how to construct very efficient universal hash proof systems for a general class of group-theoretic language membership problems. Given an efficient universal hash proof system for a language with certain natural cryptographic indistinguishability properties, we show how to construct an efficient public-key encryption schemes secure against adaptive chosen ciphertext attack in the standard model. Our construction only uses the universal hash proof systemas a primitive: no other primitives are required, although even more efficient encryption schemes can be obtained by using hash functions with appropriate collision-resistance properties. We show how to construct efficient universal hash proof systems for languages related to the DCR and QR assumptions. From these we get corresponding public-key encryption schemes that are secure under these assumptions. We also show that the Cramer-Shoup encryption scheme (which up until now was the only practical encryption scheme that could be proved secure against adaptive chosen ciphertext attack under a reasonable assumption, namely, the Decision Diffie-Hellman assumption) is also a special case of our general theory.

In this paper, we analyze the Gaudry-Hess-Smart (GHS) Weil descent attack on the elliptic curve discrete logarithm problem (ECDLP) for elliptic curves defined over characteristic two finite fields of composite extension degree. For each such field $F_{2^N}$, $N \in [100,600]$, we identify elliptic curve parameters such that (i) there should exist a cryptographically interesting elliptic curve $E$ over $F_{2^N}$ with these parameters; and (ii) the GHS attack is more efficient for solving the ECDLP in $E(F_{2^N})$ than for solving the ECDLP on any other cryptographically interesting elliptic curve over $F_{2^N}$. We examine the feasibility of the GHS attack on the specific elliptic curves over $F_{2^{176}}$, $F_{2^{208}}$, $F_{2^{272}}$, $F_{2^{304}}$, and $F_{2^{368}}$ that are provided as examples inthe ANSI X9.62 standard for the elliptic curve signature scheme ECDSA. Finally, we provide several concrete instances of the ECDLP over $F_{2^N}$, $N$ composite, of increasing difficulty which resist all previously known attacks but which are within reach of the GHS attack.

In this paper we consider matrices of special form introduced in [11] and used for the constructing of resilient functions with cryptographically optimal parameters. For such matrices we establish lower bound ${1\over\log_2(\sqrt{5}+1)}=0.5902...$ for the important ratio ${t\over t+k}$ of its parameters and point out that there exists a sequence of matrices for which the limit of ratio of its parameters is equal to lower bound. By means of these matrices we construct $m$-resilient $n$-variable functions with maximum possible nonlinearity $2^{n-1}-2^{m+1}$ for $m=0.5902...n+O(\log_2 n)$. This result supersedes the previous record.

This document provides a short description of practical protocols for private credential systems. We explain the basic concepts and mechanisms behind issuing and showing of private credentials and e-cash. The goal is to describe concisely how practical private credential systems can be achieved and not to provide intuition or motivation for the technology; for information on these subjects, see [1,2,3]. We give the details of one specific type of practical protocols for private credentials; other choices of functionalities and optimizations are possible. The reader is assumed to have general knowledge of basic concepts of cryptography such as the Discrete Logarithm problem, basic group theory and hash functions. For security proofs and more elaborate descriptions of the techniques used we refer the reader to [2].

A sufficient condition for secure ping--pong protocols is repretsented. This condition, called \emph{name--suffixing}, is essentially to insert identities of participants in messages. We prove its sufficiency and discuss the feature of security in terms of name--suffixing.

This note summarizes the results of Babbage's cryptanalysis of COS ciphers and shows that in fact COS ciphers are not weak as claimed. These ciphers have been designed according a novel concept of encryption directly determined by the context of use. This concept is here more precisely defined.

This paper addresses the security of authenticated encryption schemes in the public key setting. We present two new notions of authenticity that are stronger than the integrity notions given in the symmetric setting \cite{bn00}. We also show that chosen-ciphertext attack security (IND-CCA) in the public key setting is not obtained in general from the combination of chosen-plaintext security (IND-CPA) and integrity of ciphertext (INT-CTXT), which is in contrast to the results shown in the symmetric setting \cite{ky00,bn00}. We provide security analyses of authenticated encryption schemes constructed by combining a given public key encryption scheme and a given digital signature scheme in a ``generic'' manner ---namely, Encrypt-and-Sign, Sign-then-Encrypt, and Encrypt-then-Sign--- and show that none of them, in general, provide security under all notions defined in this paper. We then present a scheme called {\em ESSR} that meets all security notions defined here. We also give security analyses on an efficient Diffie-Hellman based scheme called {\em DHETM}, which can be thought of as a transform of the encryption scheme ``DHIES'' \cite{abr01} into an {\em authenticated} encryption scheme in the public key setting.

A new family of very fast stream ciphers called COS (for "crossing over system") has been proposed by Filiol and Fontaine, and seems to have been adopted for at least one commercial standard. In this note we show that the COS ciphers are very weak indeed — it requires negligible effort to reconstruct the state of the keystream generator from a very small amount of known keystream.

In this note we discuss a novel but simple time-memory tradeoff attack against the stream cipher LILI-128. The attack defeats the security advantage of having an irregular stepping function. The attack requires $2^{46}$ bits of keystream, a lookup table of $2^{45}$ 89-bit words and computational effort which is roughly equivalent to $2^{48}$ DES operations.

A secure function evaluation protocol allows two parties to jointly compute a function $f(x,y)$ of their inputs in a manner not leaking more information than necessary. A major result in this field is: ``any function $f$ that can be computed using polynomial resources can be computed securely using polynomial resources'' (where `resources' refers to communication and computation). This result follows by a general transformation from any circuit for $f$ to a secure protocol that evaluates $f$. Although the resources used by protocols resulting from this transformation are polynomial in the circuit size, they are much higher (in general) than those required for an insecure computation of $f$. For the design of efficient secure protocols we suggest two new methodologies, that differ with respect to their underlying computational models. In one methodology we utilize the communication complexity tree (or branching program) representation of $f$. We start with an efficient (insecure) protocol for $f$ and transform it into a secure protocol. In other words, ``any function $f$ that can be computed using communication complexity $c$ can be can be computed securely using communication complexity that is polynomial in $c$ and a security parameter''. The second methodology uses the circuit computing $f$, enhanced with look-up tables as its underlying computational model. It is possible to simulate any RAM machine in this model with polylogarithmic blowup. Hence it is possible to start with a computation of $f$ on a RAM machine and transform it into a secure protocol. We show many applications of these new methodologies resulting in protocols efficient either in communication or in computation. In particular, we exemplify a protocol for the ``millionaires problem'', where two participants want to compare their values but reveal no other information. Our protocol is more efficient than previously known ones in either communication or computation.

Factoring integers is the most established problem on which cryptographic primitives are based. This work presents an efficient construction of {\em pseudorandom functions} whose security is based on the intractability of factoring. In particular, we are able to construct efficient length-preserving pseudorandom functions where each evaluation requires only a {\em constant} number of modular multiplications per output bit. This is substantially more efficient than any previous construction of pseudorandom functions based on factoring, and matches (up to a constant factor) the efficiency of the best known factoring-based {\em pseudorandom bit generators}.

In this paper, we study the security of randomized CBC-MACs and propose a new construction that resists birthday paradox attacks and provably reaches full security. The size of the MAC tags in this construction is optimal, i.e., exactly twice the size of the block cipher. Up to a constant, the security of the proposed randomized CBC-MAC using an n-bit block cipher is the same as the security of the usual encrypted CBC-MAC using a 2n-bit block cipher. Moreover, this construction adds a negligible computational overhead compared to the cost of a plain, non-randomized CBC-MAC. We give a full standard proof of our construction using one pass of a block cipher with 2n-bit keys but there also is a proof for n-bit keys block ciphers in the ideal cipher model.

In this paper we propose a very efficient (string) $OT_n^1$ scheme for any $n\geq 2$. We build our $OT_n^1$ scheme from fundamental cryptographic techniques directly. It achieves optimal efficiency in the number of rounds and the total number of exchanged messages for the case that the receiver's choice is unconditionally secure. The computation time of our $OT_n^1$ scheme is very efficient, too. The receiver need compute 2 modular exponentiations only no matter how large $n$ is, and the sender need compute $2n$ modular exponentiations. Furthermore, the system-wide parameters need not change during the lifetime of the system and are {\em universally usable}. That is, all possible receivers and senders use the same parameters and need no trapdoors specific to each of them. For our $OT_n^1$ scheme, the privacy of the receiver's choice is unconditionally secure and the privacy of the un-chosen secrets is at least as strong as the hardness of the decisional Diffie-Hellman problem. \par We extend our $OT_n^1$ scheme to distributed oblivious transfer schemes. Our distributed $OT_n^1$ scheme takes full advantage of the research results of secret sharing and is conceptually simple. It achieves better security than Noar and Pinkas's scheme does in many aspects. For example, our scheme is secure against collusion of $R$ and $t$-$1$ servers and it need not restrict $R$ to contact at most $t$ servers, which is difficult to enforce. \par For applications, we present a method of transforming any single-database PIR protocol into a symmetric PIR protocol with only one extra unit of communication cost.

In the paper [1] published in ``Asiacrypt 2000", L. Goubin and N.T. Courtois propose an attack on the TTM cryptosystem. In paper [1], they mispresent TTM cryptosystem. Then they jump an attack from an example of TTM to the general TTM cryptosystem. Finally they conclude:"There is very little hope that a secure triangular system (Tame transformation system in our terminology) will ever be proposed". This is serious challenge to many people working in the field. In this paper, we will show that their attack is full of gaps in section 5. Even their attack on one implementation of TTM is questionable. We write a lengthy introduction to restate TTM cryptosystem and point out many possible implementations. It will be clear that their attack on one implementation can not be generalized to attacks on other implementations. As one usually said: "truth is in the fine details", we quote and analysis their TPM system at the end of the introduction and $\S$ 2. We further state one implementations of TTM cryptosystem in $\S$ 3. We analysis their MiniRank(r) attack in $\S$ 4 and show that is infeasible. We conclude that the attack of [1] on the TTM cryptosystem is infeasible and full of gaps. There is no known attacks which can crack the TTM cryptosystem.

In the trivial $n$-recipient public-key encryption scheme, a ciphertext is a concatenation of independently encrypted messages for $n$ recipients. In this paper, we say that an $n$-recipient scheme has a ``{\it shortened ciphertext}'' property if the length of the ciphertext is almost a half (or less) of the trivial scheme and the security is still almost the same as the underlying single-recipient scheme. We first present (multi-plaintext, multi-recipient) schemes with the ``{\it shortened ciphertext}'' property for ElGamal scheme and Cramer-Shoup scheme. We next show (single-plaintext, multi-recipient) hybrid encryption schemes with the ``{\it shortened ciphertext}'' property.

The authors analyze the security of Hierocrypt-3(128-bit) and Hierocrypt-L1(64-bit) designed on the nested SPN(NSPN) structure against the differential and linear cryptanalysis, and found that they are sufficiently secure, e.g., the maximum average differential and linear hull probabilities (MACP and MALHP) are bounded by $2^{-96}$ for 4-round of Hierocrypt-3; those probabilities are bounded by $2^{-48}$ for 4-round of Hierocrypt-L1. The authors get these results by extending the provable security theorem by Hong et al.. Furthermore, the extended theory is applied to Rijndael, and found that MACP and MALHP of 4-round Rijndael are bounded by $2^{-96}$. This outperforms the best previous result by Keliher et al..

Informally, an {\em obfuscator} $O$ is an (efficient, probabilistic) ``compiler'' that takes as input a program (or circuit) $P$ and produces a new program $O(P)$ that has the same functionality as $P$ yet is ``unintelligible'' in some sense. Obfuscators, if they exist, would have a wide variety of cryptographic and complexity-theoretic applications, ranging from software protection to homomorphic encryption to complexity-theoretic analogues of Rice's theorem. Most of these applications are based on an interpretation of the ``unintelligibility'' condition in obfuscation as meaning that $O(P)$ is a ``virtual black box,'' in the sense that anything one can efficiently compute given $O(P)$, one could also efficiently compute given oracle access to $P$. In this work, we initiate a theoretical investigation of obfuscation. Our main result is that, even under very weak formalizations of the above intuition, obfuscation is impossible. We prove this by constructing a family of functions $F$ that are {\em \inherently unobfuscatable} in the following sense: there is a property $\pi : F \rightarrow \{0,1\}$ such that (a) given {\em any program} that computes a function $f\in F$, the value $\pi(f)$ can be efficiently computed, yet (b) given {\em oracle access} to a (randomly selected) function $f\in F$, no efficient algorithm can compute $\pi(f)$ much better than random guessing. We extend our impossibility result in a number of ways, including even obfuscators that (a) are not necessarily computable in polynomial time, (b) only {\em approximately} preserve the functionality, and (c) only need to work for very restricted models of computation ($TC_0$). We also rule out several potential applications of obfuscators, by constructing ``unobfuscatable'' signature schemes, encryption schemes, and pseudorandom function families.

This paper reports on variants of the Square attack applied to reduced-round versions of the PES and IDEA block ciphers. Attacks on 2.5 rounds of IDEA require $3\cdot 2^{16}$ chosen-plaintexts and recover 78 key bits. A new kind of attack, the Square related-key attack, is applied on 2.5 rounds of IDEA and recovers 32 key bits, with 2 chosen-plaintexts and $2^{17}$ related keys. Similar results hold for 2.5 rounds of PES. Implementations of the attacks on 32-bit block mini-versions of both ciphers confirmed the expected computational complexity. Although our attacks do not improve on previous approaches, this report shows new variants of the Square attack on word-oriented block ciphers like IDEA and PES.

In Crypto'99, Boneh and Franklin proposed a public key traitor tracing scheme~\cite{Boneh}, which was believed to be able to catch all traitors while not accusing any innocent users (i.e., full-tracing and error-free). Assuming that Decision Diffie-Hellman problem is unsolvable in $G_{q}$, Boneh and Franklin proved that a decoder cannot distinguish valid ciphertexts from invalid ones that are used for tracing. However, our novel pirate decoder $P_{3}$ manages to make some invalid ciphertexts distinguishable without violating their assumption, and it can also frame innocent users to fool the tracer. Neither the single-key nor arbitrary pirate tracing algorithm presented in~\cite{Boneh} can identify all keys used by $P_{3}$ as claimed. Instead, it is possible for both algorithms to catch none of the traitors. We believe that the construction of our novel pirate also demonstrates a simple way to defeat some other black-box traitor tracing schemes in general.

In the public key cryptosystem using finite non abelian groups which is suggested in CRYPTO 2001, the discrete logarithm problems in inner automorphism groups are used. In this paper, we generalize the system and give some examples of non abelian groups which is applicable to our system.