We present a general probabilistic lemma that can be applied to upper bound the advantage of an adversary in distinguishing between two families of functions. Our lemma reduces the task of upper bounding the advantage to that of upper bounding the ratio of two probabilities associated to the adversary, when this ratio is is viewed as a random variable. It enables us to obtain significantly tighter analyses than more conventional methods. In this paper we apply the technique to the problem of PRP to PRF conversion. We present a simple, new construction of a PRF from a PRP that makes only two invocations of the PRP and has insecurity linear in the number of queries made by the adversary. We also improve the analysis of the truncation construction.

One of the toughest challenges in designing cryptographic protocols is to design them so that they will remain secure even when composed. For example, concurrent executions of a zero-knowledge protocol by a single prover (with one or more verifiers) may leak information and may not be zero-knowledge in toto. In this work we: (1) Suggest time as a mechanism to design concurrent cryptographic protocols and in particular maintaining zero-knowledge under concurrent execution. (2) Introduce the notion of of Deniable Authentication and connect it to the problem of concurrent zero-knowledge. We do not assume global synchronization, however we assume an (alpha,beta) timing constraint: for any two processors $P_1$ and $P_2$, if $P_1$ measures alpha elapsed time on its local clock and $P_2$ measures beta elapsed time on its local clock, and $P_2$ starts after $P_1$ does, then $P_2$ will finish after $P_1$ does. We show that for an adversary controlling all the processors clocks (as well as their communication channels) but which is constrained by an (alpha,beta) constraint there exist four-round almost concurrent zero-knowledge interactive proofs and perfect concurrent zero-knowledge arguments for every language in NP. We also address the more specific problem of Deniable Authentication, for which we propose several particularly efficient solutions. Deniable Authentication is of independent interest, even in the sequential case; our concurrent solutions yield sequential solutions, without recourse to timing, i.e., in the standard model.

We introduce the notion of Resettable Zero-Knowledge (rZK), a new security measure for cryptographic protocols which strengthens the classical notion of zero-knowledge. In essence, an rZK protocol is one that remains zero knowledge even if an adeversary can interact with the prover many times, each time resetting the prover to its initial state and forcing him to use the same random tape. Under general complexity asumptions, which hold for example if the Discrete Logarithm Problem is hard, we construct (1) rZK proof-systems for NP: (2) constant-round resettable witness-indistinguishable proof-systems for NP; and (3) constant-round rZK arguments for NP in the public key model where verifiers have fixed, public keys associated with them. In addition to shedding new light on what makes zero knowledge possible (by constructing ZK protocols that use randomness in a dramatically weaker way than before), rZK has great relevance to applications. Firstly, we show that rZK protocols are closed under parallel and concurrent execution and thus are guaranteed to be secure when implemented in fully asynchronous networks, even if an adversary schedules the arrival of every message sent. Secondly, rZK protocols enlarge the range of physical ways in which provers of a ZK protocols can be securely implemented, including devices which cannot reliably toss coins on line, nor keep state betweeen invocations. (For instance, because ordinary smart cards with secure hardware are resattable, they could not be used to implement securely the provers of classical ZK protocols, but can now be used to implement securely the provers of rZK protocols.)

The problem of password authentication over an insecure network when the user holds only a human-memorizable password has received much attention in the literature. The first rigorous treatment was provided by Halevi and Krawczyk (ACM CCS, 1998), who studied off-line password guessing attacks in the scenario in which the authentication server possesses a pair of private and public keys. HK's definition of security concentrates on the single-user (and single server) case. <P> In this work we: (1) Show the inadequacy of both the Halevi-Krawczyk formalization and protocol in the case where there is more than a single user: using a simple and realistic attack, we prove failure of the HK solution in the two-user case. (2) Propose a new definition of security for the multi-user case, expressed in terms of transcripts of the entire system, rather than individual protocol executions. (3) Suggest several ways of achieving this security against both static and dynamic adversaries. In a recent revision of their paper, Halevi and Krawczyk attempted to handle the multi-user case. We expose a weakness in their approach.

We provide two contributions to exact security analysis of digital signatures: We put forward a new method of constructing Fiat-Shamir-like signature schemes that yields better "exact security" than the original Fiat-Shamir method; and we extend exact security analysis to "exact cost-security analysis" by showing that digital signature schemes with "loose security" may be preferable for reasonable measures of cost.

We study the security of individual bits in an RSA encrypted message E_N(x). We show that given E_N(x), predicting any single bit in x with only a non-negligible advantage over the trivial guessing strategy, is (through a polynomial time reduction) as hard as breaking RSA. Moreover, we prove that blocks of O(log log N) bits of x are computationally indistinguishable from random bits. The results carry over to the Rabin encryption scheme. Considering the discrete exponentiation function, g^x modulo p, with probability 1-o(1) over random choices of the prime p, the analog results are demonstrated. Finally, we prove that the bits of ax+b modulo p give hard core predicates for any one-way function f.

We prove the equivalence of two definitions of non-malleable encryption appearing in the literature--- the original one of Dolev, Dwork and Naor and the later one of Bellare, Desai, Pointcheval and Rogaway. The equivalence relies on a new characterization of non-malleable encryption in terms of the standard notion of indistinguishability of Goldwasser and Micali. We show that non-malleability is equivalent to indistinguishability under a ``parallel chosen ciphertext attack,'' this being a new kind of chosen ciphertext attack we introduce, in which the adversary's decryption queries are not allowed to depend on answers to previous queries, but must be made all at once. This characterization simplifies both the notion of non-malleable encryption and its usage, and enables one to see more easily how it compares with other notions of encryption. The results here apply to non-malleable encryption under any form of attack, whether chosen-plaintext, chosen-ciphertext, or adaptive chosen-ciphertext.

In this paper we present a new scheme for constructing universal one-way hash functions that hash arbitrarily long messages out of universal one-way hash functions that hash fixed-length messages. The new construction is extremely simple and is also very efficient, yielding shorter keys than previously proposed composition constructions.

We describe a digital signature scheme in which the public key is fixed but the secret signing key is updated at regular intervals so as to provide a <i>forward security</i> property: compromise of the current secret key does not enable an adversary to forge signatures pertaining to the past. This can be useful to mitigate the damage caused by key exposure without requiring distribution of keys. Our construction uses ideas from the Fiat-Shamir and Ong-Schnorr identification and signature schemes, and is proven to be forward secure based on the hardness of factoring, in the random oracle model. The construction is also quite efficient.

We introduce the notion of Interleaved Zero-Knowledge (iZK), a new security measure for cryptographic protocols which strengthens the classical notion of zero-knowledge, in a way suitable for multiple concurrent executions in an asynchronous environment like the internet. We prove that iZK protocols are robust: they are ``parallelizable'', and preserve security when run concurrently in a fully asynchronous network. Furthermore, this holds even if the prover's random-pads in all these concurrent invocations are identical. Thus, iZK protocols are ideal for smart-cards and other devices which cannot reliably

We show that if any one-way function exists, then 3-round concurrent zero-knowledge arguments for all NP problems can be built in a model where a short auxiliary string with a prescribed distribution is available to the players. We also show that all known efficient identification schemes using specialized assumptions can be modified to work in this model with no essential loss of efficiency. We argue that the assumptions of the model will be satisfied in most practical scenarios where public key cryptography is used, in particular our construction works given any secure public key infrastructure. Finally, we point out that in a model with preprocessing (and no auxiliary string) proposed earlier, concurrent zero-knowledge for NP can be based on any one-way function.

We present a new signature scheme which is existentially unforgeable under chosen message attacks, assuming some variant of the RSA conjecture. This scheme is not based on "signature trees", and instead it uses the so called "hash-and-sign" paradigm. It is unique in that the assumptions made on the cryptographic hash function in use are well defined and reasonable (although non-standard). In particular, we do not model this function as a random oracle. We construct our proof of security in steps. First we describe and prove a construction which operates in the random oracle model. Then we show that the random oracle in this construction can be replaced by a hash function which satisfies some strong (but well defined!) computational assumptions. Finally, we demonstrate that these assumptions are reasonable, by proving that a function satisfying them exists under standard intractability assumptions.

A new formal security model for session key exchange protocols is proposed, and several efficient protocols are analyzed in this model. Our new model is in the style of multi-party simulatability: it specifies the service and security guarantees that a key exchange protocol should provide to higher-level protocols as a simple, natural, and intuitive interface to which a high-level protocol designer can program. The relationship between this new model and previously proposed models is explored, and in particular, several flaws and shortcomings in previously proposed models are discussed. The model also deals with anonymous users---that is, users who do not have public keys, but perhaps have passwords that can be used to authenticate themselves within a secure session.

We present an RSA threshold signature scheme. The scheme enjoys the following properties: it is unforgeable and robust; in the random oracle model, assuming the RSA problem is hard; signature share generation and verification is completely non-interactive; the size of an individual signature share is bounded by a constant times the size of the RSA modulus.

The notion of correlation intractability was introduced in an attempt to capture the ``unpredictability" property of random oracles: It is assumed that if $R$ is a random oracle then it is infeasible to find an input $x$ such that the input-output pair $(x,R(x))$ has some desired property. It is desirable that a plausible construction of correlation intractable function ensembles will be provided since the unpredictability property is often useful to design many cryptographic applications in the random oracle model. However, no plausibility result has been proposed. In this paper, we show that proving the implication, ``if uniform one-way functions exist then uniform correlation intractable function ensembles exist", is as hard as proving a claim regarding the triviality of 3-round auxiliary-input zero-knowledge Arthur-Merlin proofs without making any assumptions. We believe that it is unlikely that one can prove it unconditionally. Therefore, we conclude that it will be difficult to construct uniform correlation intractable function ensembles based solely on uniform one-way functions.

In this paper, we construct a 3-round zero-knowledge protocol for any NP language. Our protocol achieves weaker notions of zero-knowledge than black-box simulation zero-knowledge. Therefore, our result does not contradict the triviality result of Goldreich and Krawczyk which shows that 3-round black-box simulation zero-knowledge exist only for BPP languages. Our main contribution is to provide a non-black-box simulation technique. Whether there exists such a simulation technique was a major open problem in the theory of zero-knowledge. Our simulation technique is based on a non-standard computational assumption related to the Diffie-Hellman problem, which was originally proposed by Damgard.

We generalize and improve the security and efficiency of the verifiable encryption scheme of Asokan et al., such that it can rely on more general assumptions, and can be proven secure without assuming random oracles. We show a new application of verifiable encryption to group signatures with separability, these schemes do not need special purpose keys but can work with a wide range of signature, identification, and encryption schemes already in use. Finally, we extend our basic primitive to verifiable threshold and group encryption. By encrypting digital signatures this way, one gets new solutions to the verifiable signature sharing problem.

scheme, DHAES. The scheme is as efficient as ElGamal encryption, but has stronger security properties. Furthermore, these security properties are proven to hold under appropriate assumptions on the underlying primitive. We show that DHAES has not only the ``basic'' property of secure encryption (namely privacy under a chosen-plaintext attack) but also achieves privacy under both non-adaptive and adaptive chosen-ciphertext attacks. (And hence it also achieves non-malleability.) DHAES is built in a generic way from lower-level primitives: a symmetric encryption scheme, a message authentication code, group operations in an arbitrary group, and a cryptographic hash function. In particular, the underlying group may be an elliptic-curve group or the multiplicative group of integers modulo a prime number. The proofs of security are based on appropriate assumptions about the hardness of the Diffie-Hellman problem and the assumption that the underlying symmetric primitives are secure. The assumptions are all standard in the sense that no random oracles are involved. We suggest that DHAES provides an attractive starting point for developing public-key encryption standards based on the Diffie-Hellman assumption.

We propose a fast and communication-efficient proof of plaintext-knowledge (PPTK) protocol based on the Chinese Remainder theorem. With a PPTK the receiver of a ciphertext verifies that the sender knows the corresponding cleartext in such a way that a dishonest sender or an eavesdropper does not learn anything about the plaintext except with sub-polynomial probability. We turn any semantically secure public key cryptosystem into an efficient (interactive) one which is immune against adaptive chosen ciphertext attacks by adding the PPTK protocol. Using our PPTK protocol we also derive an efficient protocol for deniable authentication.

We describe a general technique to simplify as well as to improve several lattice based cryptographic protocols. The technique is rather straightforward and is easily applied to the protocols, and gives both a simpler analysis and better performance than the original protocols. The improvement is global: the modified protocols are simpler, faster, require less storage, use less bandwidth and need less random bits than the originals. Moreover, the improvement is achieved without any loss in security: we formally prove that the modified protocols are at least as secure as the original ones. In fact, the modified protocols might even be more secure as the adversary gets less information. We exemplify our technique on the Goldreich-Goldwasser zero-knowledge proof systems for lattice problems and the GGH public key cryptosystem.

We study protocols for strong authentication and key exchange in asymmetric scenarios where the authentication server possesses a pair of private and public keys while the client has only a weak human-memorizable password as its authentication key. We present and analyze several simple password protocols in this scenario, and show that the security of these protocols can be formally proven based on standard cryptographic assumptions. Remarkably, our analysis shows optimal resistance to off-line password guessing attacks under the choice of suitable public key encryption functions. In addition to user authentication, we enhance our protocols to provide two-way authentication, authenticated key exchange, defense against server's compromise, and user anonymity. We complement these results with a proof that public key techniques are unavoidable for password protocols that resist off-line guessing attacks. As a further contribution, we introduce the notion of public passwords that enables the use of the above protocols in situations where the client's machine does not have the means to validate the server's public key. Public passwords serve as "hand-held certificates" that the user can carry without the need for special computing devices.

We point out an error in the multiparty computation protocol for mixed adversaries and zero error from the Crypto 98 paper by Fitzi, Hirt and Maurer. We show that the protocol only works under a stronger requirement on the adversary than the one claimed. Hence the bound on the adversary's corruption capability given there is not tight. Subsequent work has shown, however, a new bound which is indeed tight.

The Chinese Remainder Theorem states that a positive integer m is uniquely specified by its remainder modulo k relatively prime integers p_1,...,p_k, provided m < \prod_{i=1}^k p_i. Thus the residues of m modulo relatively prime integers p_1 < p_2 < ... < p_n form a redundant representation of m if m <= \prod_{i=1}^k p_i and k < n. This suggests a number-theoretic construction of an ``error-correcting code'' that has been implicitly considered often in the past. In this paper we provide a new algorithmic tool to go with this error-correcting code: namely, a polynomial-time algorithm for error-correction. Specifically, given n residues r_1,...,r_n and an agreement parameter t, we find a list of all integers m < \prod_{i=1}^k p_i such that (m mod p_i) = r_i for at least t values of i in {1,...,n}, provided t = Omega(sqrt{kn (log p_n)/(log p_1)}). We also give a simpler algorithm to decode from a smaller number of errors, i.e., when t > n - (n-k)(log p_1)/(log p_1 + \log p_n). In such a case there is a unique integer which has such agreement with the sequence of residues. One consequence of our result is that is a strengthening of the relationship between average-case complexity of computing the permanent and its worst-case complexity. Specifically we show that if a polynomial time algorithm is able to guess the permanent of a random n x n matrix on 2n-bit integers modulo a random n-bit prime with inverse polynomial success rate, then #P=BPP. Previous results of this nature typically worked over a fixed prime moduli or assumed very small (though non-negligible) error probability (as opposed to small but non-negligible success probability).

We describe and analyze a new digital signature scheme. The new scheme is quite efficient, does not require the the signer to maintain any state, and can be proven secure against adaptive chosen message attack under a reasonable intractability assumption, the so-called Strong RSA Assumption. Moreover, a hash function can be incorporated into the scheme in such a way that it is also secure in the random oracle model under the standard RSA Assumption.