## All papers in 1999 (24 results)

A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion

Uncategorized

Uncategorized

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.

Concurrent Zero-Knowledge

Uncategorized

Uncategorized

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.

Resettable Zero-Knowledge

Uncategorized

Uncategorized

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.)

Public-Key Cryptography and Password Protocols: The Multi-User Case

Uncategorized

Uncategorized

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.

Improving the Exact Security of Digital Signature Schemes

Uncategorized

Uncategorized

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.

Security of all RSA and Discrete Log Bits

Uncategorized

Uncategorized

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.

Non-Malleable Encryption: Equivalence between Two Notions, and an Indistinguishability-Based Characterization

Uncategorized

Uncategorized

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.

A Composition Theorem for Universal One-Way Hash Functions

Uncategorized

Uncategorized

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.

A forward-secure digital signature scheme

Uncategorized

Uncategorized

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.

Interleaved Zero-Knowledge in the Public-Key Model

Uncategorized

Uncategorized

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

Concurrent Zero-Knowledge is Easy in Practice

Uncategorized

Uncategorized

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.

Secure Hash-and-Sign Signatures without the Random Oracle

Uncategorized

Uncategorized

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.

On Formal Models for Secure Key Exchange

Uncategorized

Uncategorized

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.

Practical Threshold Signatures

Uncategorized

Uncategorized

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.

A Relationship between One-Wayness and Correlation Intractability

Uncategorized

Uncategorized

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.

On the Existence of3-Round Zero-Knowledge Protocols

Uncategorized

Uncategorized

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.

Verifiable Encryption and Applications to Group Signatures and Signature Sharing

Uncategorized

Uncategorized

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.

DHAES: An Encryption Scheme Based on the Diffie-Hellman Problem

Uncategorized

Uncategorized

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.

Last updated: 1999-04-19

Fast Proof of Plaintext-Knowledge and Deniable Authentication Based on Chinese Remainder Theorem

Uncategorized

Uncategorized

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.

Lattice Based Cryptography: A Global Improvement

Uncategorized

Uncategorized

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.

Public-key cryptography and password protocols

Uncategorized

Uncategorized

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.

An error in the mixed adversary protocol by Fitzi, Hirt and Maurer

Uncategorized

Uncategorized

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.

Chinese Remaindering with Errors

Uncategorized

Uncategorized

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).

Signature Schemes Based on the Strong RSA Assumption

Uncategorized

Uncategorized

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.