Advances in Cryptology – CRYPTO 2005

In this paper, we present new techniques for collision search in the hash function SHA-0. Using the new techniques, we can find collisions of the full 80-step SHA-0 with complexity less than 2

39

hash operations.

In this paper, we present new collision search attacks on the hash function SHA-1. We show that collisions of SHA-1 can be found with complexity less than 2

69

hash operations. This is the first attack on the full 80-step SHA-1 with complexity less than the 2

80

theoretical bound.

We investigate methods for providing easy-to-check proofs of computational effort. Originally intended for discouraging spam, the concept has wide applicability as a method for controlling denial of service attacks. Dwork, Goldberg, and Naor proposed a specific memory-bound function for this purpose and proved an asymptotically tight amortized lower bound on the number of memory accesses any polynomial time bounded adversary must make. Their function requires a large random table which, crucially, cannot be compressed.

We answer an open question of Dwork et al. by designing a compact representation for the table. The paradox, compressing an incompressible table, is resolved by embedding a time/space tradeoff into the process for constructing the table from its representation.

We study the question whether the sequential or parallel composition of two functions, each indistinguishable from a random function by non-adaptive distinguishers is secure against adaptive distinguishers. The sequential composition of

F

$(\centerdot)$

and

G

$(\centerdot)$

is the function

G

(

F

(

$\centerdot$

)), the parallel composition is

F

$(\centerdot) \bigstar$

G

$(\centerdot)$

where ⋆ is some group operation. It has been shown that composition indeed gives adaptive security in the information theoretic setting, but unfortunately the proof does not translate into the more interesting computational case.

In this work we show that in the computational setting composition does not imply adaptive security: If there is a prime order cyclic group where the decisional Diffie-Hellman assumption holds, then there are functions

F

and

G

which are indistinguishable by non-adaptive polynomially time-bounded adversaries, but whose parallel composition can be completely broken (i.e. we recover the key) with only three adaptive queries. We give a similar result for sequential composition. Interestingly, we need a standard assumption from the asymmetric (aka. public-key) world to prove a negative result for symmetric (aka. private-key) systems.

Using a recent idea of Gaudry and exploiting rational representations of algebraic tori, we present an index calculus type algorithm for solving the discrete logarithm problem that works directly in these groups. Using a prototype implementation, we obtain practical upper bounds for the difficulty of solving the DLP in the tori

$T_2(\mathbb{F}_{p^m})$

and

$T_6(\mathbb{F}_{p^m})$

for various

p

and

m

. Our results do not affect the security of the cryptosystems LUC, XTR, or CEILIDH over prime fields. However, the practical efficiency of our method against other methods needs further examining, for certain choices of

p

and

m

in regions of cryptographic interest.

In this paper we present a practical heuristic attack on the Ko, Lee et al. key exchange protocol introduced at Crypto 2000 [11]. Using this attack, we were able to break the protocol in about 150 minutes with over 95% success rate for typical parameters. One of the ideas behind our attack is using Dehornoy’s handle reduction method as a counter measure to diffusion provided by the Garside normal form, and as a tool for simplifying braid words. Another idea employed in our attack is solving the

decomposition problem

in a braid group rather than the

conjugacy search problem

.

Motivated by the security of the nonlinear filter generator, the concept of correlation was previously extended to the conditional correlation, that studied the linear correlation of the inputs conditioned on a given (short) output pattern of some specific nonlinear function. Based on the conditional correlations, conditional correlation attacks were shown to be successful and efficient against the nonlinear filter generator. In this paper, we further generalize the concept of conditional correlations by assigning it with a different meaning, i.e. the correlation of the output of an arbitrary function conditioned on the unknown (partial) input which is uniformly distributed. Based on this generalized conditional correlation, a general statistical model is studied for dedicated key-recovery distinguishers. It is shown that the generalized conditional correlation is no smaller than the unconditional correlation. Consequently, our distinguisher improves on the traditional one (in the worst case it degrades into the traditional one). In particular, the distinguisher may be successful even if no ordinary correlation exists. As an application, a conditional correlation attack is developed and optimized against Bluetooth two-level E0. The attack is based on a recently detected flaw in the resynchronization of E0, as well as the investigation of conditional correlations in the Finite State Machine (FSM) governing the keystream output of E0. Our best attack finds the original encryption key for two-level E0 using the first 24 bits of 2

23.8

frames and with 2

38

computations. This is clearly the fastest and only practical known-plaintext attack on Bluetooth encryption compared with all existing attacks. Current experiments confirm our analysis.

Non-interactive zero-knowledge (NIZK) proofs have been investigated in two models: the

Public Parameter

model and the

Secret Parameter model

. In the former, a public string is “ideally” chosen according to some efficiently samplable distribution and made available to both the Prover and Verifier. In the latter, the parties instead obtain correlated (possibly different) private strings. To add further choice, the definition of zero-knowledge in these settings can either be

non-adaptive

or

adaptive

.

In this paper, we obtain several

unconditional

characterizations of computational, statistical and perfect NIZK for all combinations of these settings. Specifically, we show:

In the secret parameter model,

NIZK

=

NISZK

=

NIPZK

=

AM

.

In the public parameter model,

– for the non-adaptive definition,

NISZK

⊆

AM

∩

coAM

,

– for the adaptive one, it also holds that

NISZK

⊂

BPP

,

– for computational NIZK for “hard” languages, one-way functions are both

necessary

and

sufficient

.

From our last result, we arrive at the following

unconditional

characterization of computational NIZK in the public parameter model (which complements well-known results for interactive zero-knowledge):

Either NIZK proofs exist only for “easy” languages (i.e., languages that are not hard-on-average), or they exist for all of

AM

(i.e., all languages which admit non-interactive proofs).

In this paper, we continue the study of the round complexity of black-box zero knowledge in the bare public-key (

BPK

, for short) model previously started by Micali and Reyzin in [11]. Specifically we show the impossibility of 3-round concurrent (and thus resettable) black-box zero-knowledge argument systems with sequential soundness for non-trivial languages. In light of the previous state-of-the-art, our result completes the analysis of the round complexity of black-box zero knowledge in the

BPK

model with respect to the notions of soundness and black-box zero knowledge.

Further we give sufficient conditions for the existence of a 3-round resettable zero-knowledge

proof

(in contrast to argument) system with concurrent soundness for

$\mathcal{NP}$

in the upperbounded public-key model introduced in [14].

We show how to turn three-move proofs of knowledge into non-interactive ones in the random oracle model. Unlike the classical Fiat-Shamir transformation our solution supports an online extractor which outputs the witness from such a non-interactive proof instantaneously, without having to rewind or fork. Additionally, the communication complexity of our solution is significantly lower than for previous proofs with online extractors. We furthermore give a superlogarithmic lower bound on the number of hash function evaluations for such online extractable proofs, matching the number in our construction, and we also show how to enhance security of the group signature scheme suggested recently by Boneh, Boyen and Shacham with our construction.

Anonymous channels are necessary for a multitude of privacy-protecting protocols. Onion routing is probably the best known way to achieve anonymity in practice. However, the cryptographic aspects of onion routing have not been sufficiently explored: no satisfactory definitions of security have been given, and existing constructions have only had ad-hoc security analysis for the most part.

We provide a formal definition of onion-routing in the universally composable framework, and also discover a simpler definition (similar to CCA2 security for encryption) that implies security in the UC framework. We then exhibit an efficient and easy to implement construction of an onion routing scheme satisfying this definition.

A simple and efficient shuffling scheme containing two protocols is proposed. Firstly, a prototype, Protocol-1 is designed, which is based on the assumption that the shuffling party cannot find a linear relation of the shuffled messages in polynomial time. As application of Protocol-1 is limited, it is then optimised to Protocol-2, which does not need the assumption. Both protocols are simpler and more efficient than any other shuffling scheme with unlimited permutation. Moreover, they achieve provable correctness and ZK privacy.

We identify and fill some gaps with regard to consistency (the extent to which false positives are produced) for public-key encryption with keyword search (PEKS). We define computational and statistical relaxations of the existing notion of perfect consistency, show that the scheme of [7] is computationally consistent, and provide a new scheme that is statistically consistent. We also provide a transform of an anonymous IBE scheme to a secure PEKS scheme that, unlike the previous one, guarantees consistency. Finally we suggest three extensions of the basic notions considered here, namely anonymous HIBE, public-key encryption with temporary keyword search, and identity-based encryption with keyword search.

In this paper, we consider the problem of private searching on streaming data. We show that in this model we can efficiently implement searching for documents under a secret criteria (such as presence or absence of a hidden combination of hidden keywords) under various cryptographic assumptions. Our results can be viewed in a variety of ways: as a generalization of the notion of a Private Information Retrieval (to the more general queries and to a streaming environment as well as to public-key program obfuscation); as positive results on privacy-preserving datamining; and as a delegation of hidden program computation to other machines.

In many important applications, a collection of mutually distrustful parties must perform private computation over multisets. Each party’s input to the function is his private input multiset. In order to protect these private sets, the players perform

privacy-preserving

computation; that is, no party learns more information about other parties’ private input sets than what can be deduced from the result. In this paper, we propose efficient techniques for privacy-preserving operations on multisets. By building a framework of multiset operations, employing the mathematical properties of polynomials, we design efficient, secure, and composable methods to enable privacy-preserving computation of the

union, intersection,

and

element reduction

operations. We apply these techniques to a wide range of practical problems, achieving more efficient results than those of previous work.

We describe two new public key broadcast encryption systems for stateless receivers. Both systems are fully secure against any number of colluders. In our first construction both ciphertexts and private keys are of constant size (only two group elements), for any subset of receivers. The public key size in this system is linear in the total number of receivers. Our second system is a generalization of the first that provides a tradeoff between ciphertext size and public key size. For example, we achieve a collusion resistant broadcast system for

n

users where both ciphertexts and public keys are of size

$O(\sqrt{N})$

for any subset of receivers. We discuss several applications of these systems.

Broadcast encryption schemes allow a message sender to broadcast an encrypted data so that only legitimate receivers decrypt it. Because of the intrinsic nature of one-to-many communication in broadcasting, transmission length may be of major concern. Several broadcast encryption schemes with good transmission overhead have been proposed. But, these broadcast encryption schemes are not practical since they are greatly sacrificing performance of other efficiency parameters to achieve good performance in transmission length.

In this paper we study a generic transformation method which transforms any broadcast encryption scheme to one suited to desired application environments while preserving security. Our transformation reduces computation overhead and/or user storage by slightly increasing transmission overhead of a given broadcast encryption scheme. We provide two transformed instances. The first instance is comparable to the results of the “stratified subset difference (SSD)” technique by Goodrich et al. and firstly achieves

$\mathcal{O}(log n)$

storage,

$\mathcal{O}(log n)$

computation, and

$\mathcal{O}(\frac{log n}{log log n}r)$

transmission, at the same time, where

n

is the number of users and

r

is the number of revoked users. The second instance outperforms the “one-way chain based broadcast encryption” of Jho et al., which is the best known scheme achieving less than

r

transmission length with reasonable communication and storage overhead.

Forgery and counterfeiting are emerging as serious security risks in low-cost pervasive computing devices. These devices lack the computational, storage, power, and communication resources necessary for most cryptographic authentication schemes. Surprisingly, low-cost pervasive devices like Radio Frequency Identification (RFID) tags share similar capabilities with another weak computing device: people.

These similarities motivate the adoption of techniques from human-computer security to the pervasive computing setting. This paper analyzes a particular human-to-computer authentication protocol designed by Hopper and Blum (HB), and shows it to be practical for low-cost pervasive devices. We offer an improved, concrete proof of security for the HB protocol against passive adversaries.

This paper also offers a new, augmented version of the HB protocol, named HB

 + 

, that is secure against active adversaries. The HB

 + 

protocol is a novel, symmetric authentication protocol with a simple, low-cost implementation. We prove the security of the HB

 + 

protocol against active adversaries based on the hardness of the Learning Parity with Noise (LPN) problem.

We propose a way to establish peer-to-peer authenticated communications over an insecure channel by using an extra channel which can authenticate very short strings, e.g. 15 bits.We call this SAS-based authentication as for authentication based on Short Authenticated Strings. The extra channel uses a weak notion of authentication in which strings cannot be forged nor modified, but whose delivery can be maliciously stalled, canceled, or replayed. Our protocol is optimal and relies on an extractable or equivocable commitment scheme.

This approach offers an alternative (or complement) to public-key infrastructures, since we no longer need any central authority, and to password-based authenticated key exchange, since we no longer need to establish a confidential password. It can be used to establish secure associations in ad-hoc networks. Applications could be the authentication of a public key (e.g. for SSH or PGP) by users over the telephone, the user-aided pairing of wireless (e.g. Bluetooth) devices, or the restore of secure associations in a disaster case, namely when one remote peer had his long-term keys corrupted.

Error correcting codes and matroids have been widely used in the study of ordinary secret sharing schemes. In this paper, we study the connections between codes, matroids and a special class of secret sharing schemes, namely multiplicative linear secret sharing schemes. Such schemes are known to enable multi-party computation protocols secure against general (non-threshold) adversaries.

Two open problems related to the complexity of multiplicative LSSSs are considered in this paper.

The first one deals with strongly multiplicative LSSSs. As opposed to the case of multiplicative LSSSs, it is not known whether there is an efficient method to transform an LSSS into a strongly multiplicative LSSS for the same access structure with a polynomial increase of the complexity. We prove a property of strongly multiplicative LSSSs that could be useful in solving this problem. Namely, using a suitable generalization of the well-known Berlekamp-Welch decoder, we show that all strongly multiplicative LSSSs enable efficient reconstruction of a shared secret in the presence of malicious faults.

The second one is to characterize the access structures of ideal multiplicative LSSSs. Specifically, we wonder whether all self-dual vector space access structures are in this situation. By the aforementioned connection, this in fact constitutes an open problem about matroid theory, since it can be re-stated in terms of representability of identically self-dual matroids by self-dual codes. We introduce a new concept, the flat-partition, that provides a useful classification of identically self-dual matroids. Uniform identically self-dual matroids, which are known to be representable by self-dual codes, form one of the classes. We prove that this property also holds for the family of matroids that, in a natural way, is the next class in the above classification: the identically self-dual bipartite matroids.

A

black-box

secret sharing scheme (BBSSS) for a given access structure works in exactly the same way over any finite Abelian group, as it only requires black-box access to group operations and to random group elements. In particular, there is no dependence on e.g. the structure of the group or its order. The expansion factor of a BBSSS is the length of a vector of shares (the number of group elements in it) divided by the number of players

n

.

At CRYPTO 2002 Cramer and Fehr proposed a threshold BBSSS with an asymptotically minimal expansion factor Θ(log

n

).

In this paper we propose a BBSSS that is based on a new paradigm, namely,

primitive sets in algebraic number fields

. This leads to a new BBSSS with an expansion factor that is absolutely minimal up to an additive term of at most 2, which is an improvement by a constant additive factor.

We provide good evidence that our scheme is considerably more efficient in terms of the computational resources it requires. Indeed, the number of group operations to be performed is Õ(

n

2

) instead of Õ(

n

3

) for sharing and Õ(

n

1.6

) instead of Õ(

n

2.6

) for reconstruction.

Finally, we show that our scheme, as well as that of Cramer and Fehr, has asymptotically optimal randomness efficiency.

In the setting of secure multiparty computation, a set of parties wish to jointly compute some function of their inputs. Such a computation must preserve certain security properties, like privacy and correctness, even if some of the participating parties or an external adversary collude to attack the honest parties. Until this paper,

all

protocols for general secure computation assumed that the parties can communicate reliably via authenticated channels. In this paper, we consider the feasibility of secure computation without

any

setup assumption.

We consider a completely unauthenticated setting, where all messages sent by the parties may be tampered with and modified by the adversary (without the honest parties being able to detect this fact). In this model, it is not possible to achieve the same level of security as in the authenticated-channel setting. Nevertheless, we show that meaningful security guarantees

can

be provided. In particular, we define a relaxed notion of what it means to “securely compute” a function in the unauthenticated setting. Then, we construct protocols for securely realizing any functionality in the stand-alone model,

with no setup assumptions whatsoever.

In addition, we construct universally composable protocols for securely realizing any functionality in the common reference string model (while still in an unauthenticated network). We also show that our protocols can be used to provide conceptually simple and unified solutions to a number of problems that were studied separately in the past, including

password-based authenticated key exchange

and

non-malleable commitments

.

We present a constant-round protocol for general secure multiparty computation which makes a

black-box

use of a pseudorandom generator. In particular, the protocol does not require expensive zero-knowledge proofs and its communication complexity does not depend on the computational complexity of the underlying cryptographic primitive. Our protocol withstands an active, adaptive adversary corrupting a minority of the parties. Previous constant-round protocols of this type were only known in the semi-honest model or for restricted classes of functionalities.

Motivated by database search problems such as partial match or nearest neighbor, we present secure multiparty computation protocols for constant-depth circuits. Specifically, for a constant-depth circuit

C

of size

s

with an

m

-bit input

x

, we obtain the following types of protocols.

– In a setting where

k

 ≥ 

poly

log

(

s

) servers hold

C

and a client holds

x

, we obtain a protocol in which the client privately learns

C

(

x

) by communicating Õ(m) bits with each server.

– In a setting where

x

is arbitrarily distributed between

k

 ≥ 

poly

log

(

s

) parties who all know

C

, we obtain a secure protocol for evaluating

C

(

x

) using

O

(

m

·

poly

(

k

)) communication.

Both types of protocols tolerate

t

 = 

k

/

poly

log

(

s

) dishonest parties and their computational complexity is nearly linear in

s

. In particular, the protocols are optimal “up to polylog factors” with respect to communication, local computation, and minimal number of participating parties.

We then apply the above results to obtain sublinear-communication secure protocols for natural database search problems. For instance, for the partial match problem on a database of

n

points in {0,1}

m

we get a protocol with

$k \approx \frac{1}{2} log n$

servers, Õ(m) communication, and nearly linear server computation. Applying previous protocols to this problem would either require Ω(

nm

) communication, Ω̃(m) servers, or super-polynomial computation.

We investigate several previously suggested scenarios of instantiating random oracles (ROs) with “realizable” primitives in cryptographic schemes. As candidates for such “instantiating” primitives we pick perfectly one-way hash functions (POWHFs) and verifiable pseudorandom functions (VPRFs). Our analysis focuses on the most practical encryption schemes such as OAEP and its variant PSS-E and the Fujisaki-Okamoto hybrid encryption scheme. We also consider the RSA Full Domain Hash (FDH) signature scheme. We first show that some previous beliefs about instantiations for some of these schemes are not true. Namely we show that, contrary to Canetti’s conjecture, in general one cannot instantiate either one of the two ROs in the OAEP encryption scheme by POWHFs without losing security. We also confirm through the FDH signature scheme that the straightforward instantiation of ROs with VPRFs may result in insecure schemes, in contrast to regular pseudorandom functions which can provably replace ROs (in a well-defined way). But unlike a growing number of papers on negative results about ROs, we bring some good news. We show that one can realize

one

of the two ROs in a variant of the PSS-E encryption scheme and

either one

of the two ROs in the Fujisaki-Okamoto hybrid encryption scheme through POWHFs, while preserving the IND-CCA security in both cases (still in the RO model). Although this partial instantiation in form of substituting only one RO does not help to break out of the random oracle model, it yet gives a better understanding of the necessary properties of the primitives and also constitutes a better security heuristic.

The most common way of constructing a hash function (

e.g.

, SHA-1) is to iterate a compression function on the input message. The compression function is usually designed from scratch or made out of a block-cipher. In this paper, we introduce a new security notion for hash-functions, stronger than collision-resistance. Under this notion, the arbitrary length hash function

H

must behave as a random oracle when the fixed-length building block is viewed as a random oracle or an ideal block-cipher. The key property is that if a particular construction meets this definition, then any cryptosystem proven secure assuming

H

is a random oracle remains secure if one plugs in this construction (still assuming that the underlying fixed-length primitive is ideal). In this paper, we show that the current design principle behind hash functions such as SHA-1 and MD5 — the (strengthened) Merkle-Damgård transformation — does not satisfy this security notion. We provide several constructions that provably satisfy this notion; those new constructions introduce minimal changes to the plain Merkle-Damgård construction and are easily implementable in practice.

The

Full-Domain Hash

(FDH) signature scheme forms [3] one the most basic usages of random oracles. It works with a family

$\mathcal{F}$

of trapdoor permutations (TDP), where the signature of

m

is computed as

f

− − 1

(

h

(

m

)) (here

${f} \in_{\mathcal{R}} \mathcal{F}$

and

h

is modelled as a random oracle). It is known to be existentially unforgeable for any TDP family

$\mathcal{F}$

[3], although a much tighter security reduction is known for a restrictive class of TDP’s [10,14]— namely, those induced by a family of claw-free permutations (CFP) pairs. The latter result was shown [11] to match the best

possible

“black-box” security reduction in the random oracle model, irrespective of the TDP family

$\mathcal{F}$

(e.g., RSA) one might use.

In this work we investigate the question if it is possible to instantiate the random oracle

h

with a “real” family of hash functions

$\mathcal{H}$

such that the corresponding schemes can be proven secure

in the standard model

, under some natural assumption on the family

$\mathcal{F}$

. Our main result

rules out

the existence of such instantiations for

any

assumption on

$\mathcal{F}$

which (1) is satisfied by a family of random permutations; and (2) does not allow the attacker to invert

${f} \in_{\mathcal{R}} \mathcal{F}$

on an a-priori unbounded number of points. Moreover, this holds even if the choice of

$\mathcal{H}$

can arbitrarily depend on

f

. As an immediate corollary, we rule out instantiating FDH based on general claw-free permutations, which shows that in order to prove the security of FDH in the standard model one must utilize significantly more structure on

$\mathcal{F}$

than what is sufficient for the best proof of security in the random oracle model.

Since bit and string

oblivious transfer

and

commitment

, two primitives of paramount importance in secure two- and multi-party computation, cannot be realized in an unconditionally secure way for both parties from scratch,

reductions

to weak information-theoretic primitives as well as between different variants of the functionalities are of great interest. In this context, we introduce three independent

monotones

—quantities that cannot be increased by any protocol|and use them to derive lower bounds on the

possibility

and

efficiency

of such reductions. An example is the transition between different versions of oblivious transfer, for which we also propose a new protocol allowing to increase the number of messages the receiver can choose from at the price of a reduction of their length. Our scheme matches the new lower bound and is, therefore, optimal.

Secret-key agreement between two parties Alice and Bob, connected by an insecure channel, can be realized in an information-theoretic sense if the parties share many independent pairs of correlated and partially secure bits. We study the special case where only one-way communication from Alice to Bob is allowed and where, for each of the bit pairs, with a certain probability, the adversary has no information on Alice’s bit. We give an expression which, for this situation, exactly characterizes the rate at which Alice and Bob can generate secret key bits.

This result can be used to analyze a slightly restricted variant of the problem of polarizing circuits, introduced by Sahai and Vadhan in the context of statistical zero-knowledge, which we show to be equivalent to secret-key agreement as described above. This provides us both with new constructions to polarize circuits, but also proves that the known constructions work for parameters which are tight.

As a further application of our results on secret-key agreement, we show how to immunize single-bit public-key encryption schemes from decryption errors and insecurities of the encryption, a question posed and partially answered by Dwork, Naor, and Reingold. Our construction works for stronger parameters than the known constructions.

Assuming an insecure quantum channel and an authenticated classical channel, we propose an unconditionally secure scheme for encrypting classical messages under a shared key, where attempts to eavesdrop the ciphertext can be detected. If no eavesdropping is detected, we can securely re-use the entire key for encrypting new messages. If eavesdropping is detected, we must discard a number of key bits corresponding to the length of the message, but can re-use almost all of the rest. We show this is essentially optimal. Thus, provided the adversary does not interfere (too much) with the quantum channel, we can securely send an arbitrary number of message bits, independently of the length of the initial key. Moreover, the key-recycling mechanism only requires one-bit feedback. While ordinary quantum key distribution with a classical one time pad could be used instead to obtain a similar functionality, this would need more rounds of interaction and more communication.

At

Eurocrypt ’03

, Goh and Jarecki showed that, contrary to other signature schemes in the discrete-log setting, the

EDL

signature scheme has a

tight

security reduction, namely to the Computational Diffie-Hellman (CDH) problem, in the Random Oracle (RO) model. They also remarked that

EDL

can be turned into an off-line/on-line signature scheme using the technique of Shamir and Tauman, based on chameleon hash functions.

In this paper, we propose a new signature scheme that also has a tight security reduction to CDH but whose resulting signatures are smaller than

EDL

signatures. Further, similarly to the Schnorr signature scheme (but contrary to

EDL

), our signature is naturally efficient on-line: no additional trick is needed for the off-line phase and the verification process is unchanged.

For example, in elliptic curve groups, our scheme results in a 25% improvement on the state-of-the-art discrete-log based schemes, with the same security level. This represents to date the most efficient scheme of any signature scheme with a tight security reduction in the discrete-log setting.

We present an improved bound on the advantage of any

q

-query adversary at distinguishing between the CBC MAC over a random

n

-bit permutation and a random function outputting

n

bits. The result assumes that no message queried is a prefix of any other, as is the case when all messages to be MACed have the same length. We go on to give an improved analysis of the encrypted CBC MAC, where there is no restriction on queried messages. Letting

m

be the block length of the longest query, our bounds are about

mq

2

/2

n

for the basic CBC MAC and

m

o

(1)

q

2

/2

n

for the encrypted CBC MAC, improving prior bounds of

m

2

q

2

/2

n

. The new bounds translate into improved guarantees on the probability of forging these MACs.

The MQV protocol of Law, Menezes, Qu, Solinas and Vanstone is possibly the most efficient of all known authenticated Diffie-Hellman protocols that use public-key authentication. In addition to great performance, the protocol has been designed to achieve a remarkable list of security properties. As a result MQV has been widely standardized, and has recently been chosen by the NSA as the key exchange mechanism underlying

“the next generation cryptography to protect US government information”.

One question that has not been settled so far is whether the protocol can be proven secure in a rigorous model of key-exchange security. In order to provide an answer to this question we analyze the MQV protocol in the Canetti-Krawczyk model of key exchange. Unfortunately, we show that MQV fails to a variety of attacks in this model that invalidate its basic security as well as many of its stated security goals. On the basis of these findings, we present HMQV, a carefully designed variant of MQV, that provides the same superb performance and functionality of the original protocol but for which all the MQV’s security goals can be formally proved to hold in the random oracle model under the computational Diffie-Hellman assumption.

We base the design and proof of HMQV on a new form of “challenge-response signatures”, derived from the Schnorr identification scheme, that have the property that both the challenger and signer can compute the

same

signature; the former by having chosen the challenge and the latter by knowing the private signature key.