main-content

## Über dieses Buch

The 2006 edition of the Eurocrypt conference was held in St. Petersburg,Russia from May 28 to June 1, 2006. It was the 25th Eurocrypt conference. Eurocrypt is sponsored by the International Association for Cryptologic Research (IACR). Eurocrypt2006waschairedbyAnatolyLebedev,andIhadtheprivilegetochair the Program Committee. Eurocrypt collected 198 submissions on November 21, 2005. The Program Committee carried out a thorough review process. In total, 863 review reports were written by renowned experts, Program Committee members as well as external referees. Online discussions led to 1,114 additional discussion messages and about 1,000 emails. The review process was run using e-mail and the iChair software by Thomas Baign` eres and Matthieu Finiasz. Every submitted paper received at least three review reports. The Program Committee had a meeting in Lausanne on February 4, 2006. We selected 33 papers, noti?ed acceptance or rejection to the authors, and had a cheese fondue. Authors were then invited to revise their submission. The present proceedings include all the revised papers. Due to time constraints the revised versions could not be reviewed again. We delivered a “Eurocrypt Best Paper Award.” The purpose of the award is to formally acknowledge authors of outstanding papers and to recognize - cellence in the cryptographic research ?elds. Committee members were invited to nominate papers for this award. A poll then yielded a clear majority. This year, we were pleased to deliver the Eurocrypt Best Paper Award to Phong Q.

## Inhaltsverzeichnis

### Security Analysis of the Strong Diffie-Hellman Problem

Let

g

be an element of prime order

p

in an abelian group and

$\alpha\in {{\mathbb Z}}_p$

. We show that if

g

,

g

α

, and

$g^{\alpha^d}$

are given for a positive divisor

d

of

p

–1, we can compute the secret

α

in

$O(\log p \cdot (\sqrt{p/d}+\sqrt d))$

group operations using

$O(\max\{\sqrt{p/d},\sqrt d\})$

memory. If

$g^{\alpha^i}$

(

i

=0,1,2,...,

d

) are provided for a positive divisor

d

of

p

+1,

α

can be computed in

$O(\log p \cdot (\sqrt{p/d}+d))$

group operations using

$O(\max\{\sqrt{p/d},\sqrt d\})$

memory. This implies that the strong Diffie-Hellman problem and its related problems have computational complexity reduced by

$O(\sqrt d)$

from that of the discrete logarithm problem for such primes.

Further we apply this algorithm to the schemes based on the Diffie-Hellman problem on an abelian group of prime order

p

. As a result, we reduce the complexity of recovering the secret key from

$O(\sqrt p)$

to

$O(\sqrt{p/d})$

for Boldyreva’s blind signature and the original ElGamal scheme when

p

–1 (resp.

p

+1) has a divisor

d

p

1/2

(resp.

d

p

1/3

) and

d

signature or decryption queries are allowed.

Jung Hee Cheon

### Cryptography in Theory and Practice: The Case of Encryption in IPsec

Despite well-known results in theoretical cryptography highlighting the vulnerabilities of unauthenticated encryption, the IPsec standards mandate its support. We present evidence that such “encryption-only” configurations are in fact still often selected by users of IPsec in practice, even with strong warnings advising against this in the IPsec standards. We then describe a variety of attacks against such configurations and report on their successful implementation in the case of the Linux kernel implementation of IPsec. Our attacks are realistic in their requirements, highly efficient, and recover the complete contents of IPsec-protected datagrams. Our attacks still apply when integrity protection is provided by a higher layer protocol, and in some cases even when it is supplied by IPsec itself.

Kenneth G. Paterson, Arnold K. L. Yau

### Polynomial Equivalence Problems: Algorithmic and Theoretical Aspects

The Isomorphism of Polynomials (IP) [28], which is the main concern of this paper, originally corresponds to the problem of recovering the secret key of a C

*

scheme [26]. Besides, the security of various other schemes (signature, authentication [28], traitor tracing [5], ...) also depends on the practical hardness of IP. Due to its numerous applications, the Isomorphism of Polynomials is thus one of the most fundamental problems in multivariate cryptography. In this paper, we address two complementary aspects of IP, namely its theoretical and practical difficulty. We present an upper bound on the theoretical complexity of “IP-like” problems, i.e. a problem consisting in recovering a particular transformation between two sets of multivariate polynomials. We prove that these problems are not NP-Hard (provided that the polynomial hierarchy does not collapse). Concerning the practical aspect, we present a new algorithm for solving IP. In a nutshell, the idea is to generate a suitable algebraic system of equations whose zeroes correspond to a solution of IP. From a practical point of view, we employed a fast Gröbner basis algorithm, namely F

5

[17], for solving this system. This approach is efficient in practice and obliges to modify the current security criteria for IP. We have indeed broken several challenges proposed in literature [28, 29, 5]. For instance, we solved a challenge proposed by O. Billet and H. Gilbert at Asiacrypt’03 [5] in less than one second.

Jean-Charles Faugère, Ludovic Perret

### Alien vs. Quine, the Vanishing Circuit and Other Tales from the Industry’s Crypt

This talk illustrates the everyday challenges met by embedded security practitioners by five real examples. All the examples were actually encountered while designing, developing or evaluating commercial products.

This note, which is not a refereed research paper, presents the details of one of these five examples. It is intended to help the audience follow that part of our presentation.

Vanessa Gratzer, David Naccache

### Hiding Secret Points Amidst Chaff

Motivated by the representation of biometric and multimedia objects, we consider the problem of hiding noisy point-sets using a secure sketch. A point-set

X

consists of

s

points from a

d

-dimensional discrete domain [0,

N

– 1]

d

. Under permissible noises, for every point

$\left \langle x_1,..,x_d\right \rangle \in X$

, each

x

i

may be perturbed by a value of at most

δ

t

points in

X

may be replaced by other points in [0,

N

– 1]

d

. Given an original

X

, we want to compute a secure sketch

P

. A known method constructs the sketch by adding a set of random points

R

, and the description of (

X

R

) serves as part of the sketch. However, the dependencies among the random points are difficult to analyze, and there is no known non-trivial bound on the entropy loss. In this paper, we first give a general method to generate

R

and show that the entropy loss of (

X

R

) is at most

s

(

d

logΔ+

d

+ 0.443), where Δ= 2

δ

+1. We next give improved schemes for

d

= 1, and special cases for

d

= 2. Such improvements are achieved by pre-rounding, and careful partition of the domains into cells. It is possible to make our sketch short, and avoid using randomness during construction. We also give a method in

d

= 1 to demonstrate that, using the size of

R

as the security measure would be misleading.

Ee-Chien Chang, Qiming Li

### Parallel and Concurrent Security of the HB and HB +  Protocols

Juels andWeis (building on prior work of Hopper and Blum) propose and analyze two shared-key authentication protocols - HB and HB

+

- whose extremely low computational cost makes them attractive for low-cost devices such as radio-frequency identification (RFID) tags. Security of these protocols is based on the conjectured hardness of the “learning parity with noise” (LPN) problem: the HB protocol is proven secure against a passive (eavesdropping) adversary, while the HB

+

protocol is proven secure against active attacks.

Juels and Weis prove security of these protocols only for the case of

sequential

executions, and explicitly leave open the question of whether security holds also in the case of

parallel

or

concurrent

executions. In addition to guaranteeing security against a stronger class of adversaries, a positive answer to this question would allow the HB

+

protocol to be parallelized, thereby substantially reducing its round complexity.

Adapting a recent result by Regev, we answer the aforementioned question in the affirmative and prove security of the HB and HB+ protocols under parallel/concurrent executions. We also give what we believe to be substantially

simpler

security proofs for these protocols which are more

complete

in that they explicitly address the dependence of the soundness error on the number of iterations.

Jonathan Katz, Ji Sun Shin

### Polling with Physical Envelopes: A Rigorous Analysis of a Human-Centric Protocol

We propose simple, realistic protocols for polling that allow the responder to plausibly repudiate his response, while at the same time allow accurate statistical analysis of poll results. The protocols use simple physical objects (envelopes or scratch-off cards) and can be performed without the aid of computers. One of the main innovations of this work is the use of techniques from theoretical cryptography to rigorously prove the security of a realistic, physical protocol. We show that, given a few properties of physical envelopes, the protocols are unconditionally secure in the universal composability framework.

Tal Moran, Moni Naor

### QUAD: A Practical Stream Cipher with Provable Security

We introduce a practical stream cipher with provable security named QUAD. The cipher relies on the iteration of a multivariate quadratic system of

m

equations in

n

<

m

unknowns over a finite field. The security of the keystream generation of QUAD is provably reducible to the conjectured intractability of the MQ problem, namely solving a multivariate system of quadratic equations. Our recommended version of QUAD uses a 80-bit key, 80-bit IV and an internal state of

n

= 160 bits. It outputs 160 keystream bits (

m

= 320) at each iteration until 2

40

bits of keystream have been produced.

Côme Berbain, Henri Gilbert, Jacques Patarin

### How to Strengthen Pseudo-random Generators by Using Compression

Sequence compression is one of the most promising tools for strengthening pseudo-random generators used in stream ciphers. Indeed, adding compression components can thwart algebraic attacks aimed at LFSR-based stream ciphers. Among such components are the Shrinking Generator and the Self-Shrinking Generator, as well as recent variations on Bit-Search-based decimation. We propose a general model for compression used to strengthen pseudo-random sequences. We show that there is a unique (up to length-preserving permutations) construction that reaches an optimal trade-off between output rate and security against several attacks.

Aline Gouget, Hervé Sibert

### Efficient Computation of Algebraic Immunity for Algebraic and Fast Algebraic Attacks

In this paper we propose several efficient algorithms for assessing the resistance of Boolean functions against algebraic and fast algebraic attacks when implemented in LFSR-based stream ciphers. An algorithm is described which permits to compute the algebraic immunity

d

of a Boolean function with

n

variables in

$\mathcal{O}(D^2)$

operations, for

$D \approx \binom{n}{d}$

, rather than in

$\mathcal{O}(D^3)$

operations necessary in all previous algorithms. Our algorithm is based on multivariate polynomial interpolation. For assessing the vulnerability of arbitrary Boolean functions with respect to fast algebraic attacks, an efficient generic algorithm is presented that is not based on interpolation. This algorithm is demonstrated to be particularly efficient for symmetric Boolean functions. As an application it is shown that large classes of symmetric functions are very vulnerable to fast algebraic attacks despite their proven resistance against conventional algebraic attacks.

Frederik Armknecht, Claude Carlet, Philippe Gaborit, Simon Künzli, Willi Meier, Olivier Ruatta

### VSH, an Efficient and Provable Collision-Resistant Hash Function

We introduce VSH,

very smooth hash

, a new

S

-bit hash function that is provably collision-resistant assuming the hardness of finding nontrivial modular square roots of very smooth numbers modulo an

S

-bit composite. By very smooth, we mean that the smoothness bound is some fixed polynomial function of

S

. We argue that finding collisions for VSH has the same asymptotic complexity as factoring using the Number Field Sieve factoring algorithm, i.e., subexponential in

S

.

VSH is theoretically pleasing because it requires just a single multiplication modulo the

S

-bit composite per Ω(

S

) message-bits (as opposed to

O

(log

S

) message-bits for previous provably secure hashes). It is relatively practical. A preliminary implementation on a 1GHz Pentium III processor that achieves collision resistance at least equivalent to the difficulty of factoring a 1024-bit RSA modulus, runs at 1.1 MegaByte per second, with a moderate slowdown to 0.7MB/s for 2048-bit RSA security.

VSH can be used to build a fast, provably secure randomised trapdoor hash function, which can be applied to speed up provably secure signature schemes (such as Cramer-Shoup) and designated-verifier signatures.

Scott Contini, Arjen K. Lenstra, Ron Steinfeld

### Herding Hash Functions and the Nostradamus Attack

In this paper, we develop a new attack on Damgård-Merkle hash functions, called the

herding attack

, in which an attacker who can find many collisions on the hash function by brute force can first provide the hash of a message, and later “herd” any given starting part of a message to that hash value by the choice of an appropriate suffix. We focus on a property which hash functions should have–Chosen Target Forced Prefix (CTFP) preimage resistance–and show the distinction between Damgård-Merkle construction hashes and random oracles with respect to this property. We describe a number of ways that violation of this property can be used in arguably practical attacks on real-world applications of hash functions. An important lesson from these results is that hash functions susceptible to collision-finding attacks, especially brute-force collision-finding attacks, cannot in general be used to prove knowledge of a secret value.

### Optimal Reductions Between Oblivious Transfers Using Interactive Hashing

We present an asymptotically optimal reduction of one-out-of-two String Oblivious Transfer to one-out-of-two Bit Oblivious Transfer using Interactive Hashing in conjunction with Privacy Amplification. Interactive Hashing is used in an innovative way to test the receiver’s adherence to the protocol. We show that (1 +

ε

)

k

uses of Bit OT suffice to implement String OT for

k

-bit strings. Our protocol represents a two-fold improvement over the best constructions in the literature and is asymptotically optimal. We then show that our construction can also accommodate weaker versions of Bit OT, thereby obtaining a significantly lower expansion factor compared to previous constructions. Besides increasing efficiency, our constructions allow the use of any 2-universal family of Hash Functions for performing Privacy Amplification. Of independent interest, our reduction illustrates the power of Interactive Hashing as an ingredient in the design of cryptographic protocols.

Claude Crépeau, George Savvides

### Oblivious Transfer Is Symmetric

We show that oblivious transfer of bits from

A

to

B

can be obtained from a single instance of the same primitive from

B

to

A

. Our reduction is perfect and shows that oblivious transfer is in fact a symmetric functionality. This solves an open problem posed by Crépeau and Sántha in 1991.

Stefan Wolf, Jürg Wullschleger

### Symplectic Lattice Reduction and NTRU

NTRU is a very efficient public-key cryptosystem based on polynomial arithmetic. Its security is related to the hardness of lattice problems in a very special class of lattices. This article is motivated by an interesting peculiar property of NTRU lattices. Namely, we show that NTRU lattices are proportional to the so-called symplectic lattices. This suggests to try to adapt the classical reduction theory to symplectic lattices, from both a mathematical and an algorithmic point of view. As a first step, we show that orthogonalization techniques (Cholesky, Gram-Schmidt, QR factorization, etc.) which are at the heart of all reduction algorithms known, are all compatible with symplecticity, and that they can be significantly sped up for symplectic matrices. Surprisingly, by doing so, we also discover a new integer Gram-Schmidt algorithm, which is faster than the usual algorithm for all matrices. Finally, we study symplectic variants of the celebrated LLL reduction algorithm, and obtain interesting speed ups.

Nicolas Gama, Nick Howgrave-Graham, Phong Q. Nguyen

### The Function Field Sieve in the Medium Prime Case

In this paper, we study the application of the function field sieve algorithm for computing discrete logarithms over finite fields of the form

${\mathbb {F}}_{q^n}$

when

q

is a medium-sized prime power. This approach is an alternative to a recent paper of Granger and Vercauteren for computing discrete logarithms in tori, using efficient torus representations. We show that when

q

is not too large, a very efficient

L

(1/3) variation of the function field sieve can be used. Surprisingly, using this algorithm, discrete logarithms computations over some of these fields are even easier than computations in the prime field and characteristic two field cases. We also show that this new algorithm has security implications on some existing cryptosystems, such as torus based cryptography in

T

30

, short signature schemes in characteristic 3 and cryptosystems based on supersingular abelian varieties. On the other hand, cryptosystems involving larger basefields and smaller extension degrees, typically of degree at most 6, such as LUC, XTR or

T

6

torus cryptography, are not affected.

Antoine Joux, Reynald Lercier

### Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures

Lattice-based signature schemes following the Goldreich- Goldwasser-Halevi (GGH) design have the unusual property that each signature leaks information on the signer’s secret key, but this does not necessarily imply that such schemes are insecure. At Eurocrypt ’03, Szydlo proposed a potential attack by showing that the leakage reduces the key-recovery problem to that of distinguishing integral quadratic forms. He proposed a heuristic method to solve the latter problem, but it was unclear whether his method could attack real-life parameters of GGH and

NTRU Cryptosystems

sign. Here, we propose an alternative method to attack signature schemes à la GGH, by studying the following learning problem: given many random points uniformly distributed over an unknown

n

-dimensional parallelepiped, recover the parallelepiped or an approximation thereof. We transform this problem into a multivariate optimization problem that can be solved by a gradient descent. Our approach is very effective in practice: we present the first succesful key-recovery experiments on

NTRU Cryptosystems

sign-251 without perturbation, as proposed in half of the parameter choices in NTRU standards under consideration by IEEE P1363.1. Experimentally, 90,000 signatures are sufficient to recover the

NTRU Cryptosystems

sign-251 secret key. We are also able to recover the secret key in the signature analogue of all the GGH encryption challenges, using a number of signatures which is roughly quadratic in the lattice dimension.

Phong Q. Nguyen, Oded Regev

### The Cramer-Shoup Encryption Scheme Is Plaintext Aware in the Standard Model

In this paper we examine the notion of plaintext awareness as it applies to hybrid encryption schemes. We apply this theory to the Cramer-Shoup hybrid scheme acting on fixed length messages and deduce that the Cramer-Shoup scheme is plaintext-aware in the standard model. This answers a previously open conjecture of Bellare and Palacio on the existence of fully plaintext-aware encryption schemes.

Alexander W. Dent

### Private Circuits II: Keeping Secrets in Tamperable Circuits

Motivated by the problem of protecting cryptographic hardware, we continue the investigation of

private circuits

initiated in [16]. In this work, our aim is to construct circuits that should protect the secrecy of their internal state against an adversary who may modify the values of an

unbounded

number of wires,

anywhere in the circuit

. In contrast, all previous works on protecting cryptographic hardware relied on an assumption that some portion of the circuit must remain

completely free

from tampering.

We obtain the first feasibility results for such private circuits. Our main result is an efficient transformation of a circuit

C

, realizing an arbitrary (reactive) functionality, into a private circuit

C

′ realizing the same functionality. The transformed circuit can successfully detect any serious tampering and erase all data in the memory. In terms of the information available to the adversary, even in the presence of an unbounded number of adaptive wire faults, the circuit

C

C

.

Yuval Ishai, Manoj Prabhakaran, Amit Sahai, David Wagner

### Composition Implies Adaptive Security in Minicrypt

To prove that a secure key-agreement protocol exists one must at least show

P

NP

. Moreover any proof that the sequential composition of two non-adaptively secure pseudorandom functions is secure against at least two adaptive queries must falsify the decisional Diffie-Hellman assumption, a standard assumption from public-key cryptography. Hence proving any of this two seemingly unrelated statements would require a significant breakthrough. We show that

at least one

of the two statements is true.

To our knowledge this gives the first

positive

cryptographic result (namely that composition implies some weak adaptive security) which holds in

Minicrypt

, but not in

Cryptomania

, i.e. under the assumption that one-way functions exist, but public-key cryptography does not.

Krzysztof Pietrzak

### Perfect Non-interactive Zero Knowledge for NP

Non-interactive zero-knowledge (NIZK) proof systems are fundamental cryptographic primitives used in many constructions, including CCA2-secure cryptosystems, digital signatures, and various cryptographic protocols. What makes them especially attractive, is that they work equally well in a concurrent setting, which is notoriously hard for interactive zero-knowledge protocols. However, while for interactive zero-knowledge we know how to construct statistical zero-knowledge argument systems for all NP languages, for non-interactive zero-knowledge, this problem remained open since the inception of NIZK in the late 1980’s. Here we resolve two problems regarding NIZK:

We construct the first perfect NIZK argument system for any NP language.

We construct the first UC-secure NIZK argument for any NP language in the presence of a dynamic/adaptive adversary.

While it is already known how to construct efficient prover computational NIZK

proofs

for any NP language, the known techniques yield large common reference strings and large proofs. Another contribution of this paper is NIZK proofs with much shorter common reference string and proofs than previous constructions.

Jens Groth, Rafail Ostrovsky, Amit Sahai

### Language Modeling and Encryption on Packet Switched Networks

The holy grail of a mathematical model of secure encryption is to devise a model that is both faithful in its description of the real world, and yet admits a construction for an encryption system that fulfills a meaningful definition of security against a realistic adversary. While enormous progress has been made during the last 60 years toward this goal, existing models of security still overlook features that are closely related to the fundamental nature of communication. As a result there is substantial doubt in this author’s mind as to whether there is any reasonable definition of “secure encryption” on the Internet.

Kevin S. McCurley

### A Provable-Security Treatment of the Key-Wrap Problem

We give a provable-security treatment for the

key-wrap problem

, providing definitions, constructions, and proofs. We suggest that key-wrap’s goal is security in the sense of

deterministic authenticated-encryption

(DAE), a notion that we put forward. We also provide an alternative notion, a

pseudorandom injection

(PRI), which we prove to be equivalent. We provide a DAE construction, SIV, analyze its concrete security, develop a blockcipher-based instantiation of it, and suggest that the method makes a desirable alternative to the schemes of the X9.102 draft standard. The construction incorporates a method to turn a PRF that operates on a string into an equally efficient PRF that operates on a vector of strings, a problem of independent interest. Finally, we consider IV-based authenticated-encryption (AE) schemes that are maximally forgiving of repeated IVs, a goal we formalize as

misuse-resistant AE

. We show that a DAE scheme with a vector-valued header, such as SIV, directly realizes this goal.

Phillip Rogaway, Thomas Shrimpton

### Luby-Rackoff Ciphers from Weak Round Functions?

The Feistel-network is a popular structure underlying many block-ciphers where the cipher is constructed from many simpler rounds, each defined by some function which is derived from the secret key.

Luby and Rackoff showed that the three-round Feistel-network – each round instantiated with a pseudorandom function secure against adaptive chosen plaintext attacks (

CPA

) – is a

CPA

secure pseudorandom permutation, thus giving some confidence in the soundness of using a Feistel-network to design block-ciphers.

But the round functions used in actual block-ciphers are – for efficiency reasons – far from being pseudorandom. We investigate the security of the Feistel-network against

CPA

distinguishers when the only security guarantee we have for the round functions is that they are secure against non-adaptive chosen plaintext attacks (

nCPA

). We show that in the information-theoretic setting, four rounds with

nCPA

secure round functions are sufficient (and necessary) to get a

CPA

secure permutation. Unfortunately, this result does not translate into the more interesting pseudorandom setting. In fact, under the so-called Inverse Decisional Diffie-Hellman assumption the Feistel-network with four rounds, each instantiated with a

nCPA

secure pseudorandom function, is in general not a

CPA

secure pseudorandom permutation.

Ueli Maurer, Yvonne Anne Oswald, Krzysztof Pietrzak, Johan Sjödin

### The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs

We show that, in the ideal-cipher model, triple encryption (the cascade of three independently-keyed blockciphers) is more secure than single or double encryption, thereby resolving a long-standing open problem. Our result demonstrates that for DES parameters (56-bit keys and 64-bit plaintexts) an adversary’s maximal advantage against triple encryption is small until it asks about 2

78

queries. Our proof uses code-based game-playing in an integral way, and is facilitated by a framework for such proofs that we provide.

Mihir Bellare, Phillip Rogaway

### Compact Group Signatures Without Random Oracles

We present the first efficient group signature scheme that is provably secure without random oracles. We achieve this result by combining provably secure hierarchical signatures in bilinear groups with a novel adaptation of the recent Non-Interactive Zero Knowledge proofs of Groth, Ostrovsky, and Sahai. The size of signatures in our scheme is logarithmic in the number of signers; we prove it secure under the Computational Diffie-Hellman and the Subgroup Decision assumptions in the model of Bellare, Micciancio, and Warinshi, as relaxed by Boneh, Boyen, and Shacham.

Xavier Boyen, Brent Waters

### Practical Identity-Based Encryption Without Random Oracles

We present an Identity Based Encryption (IBE) system that is fully secure in the standard model and has several advantages over previous such systems – namely, computational efficiency, shorter public parameters, and a “tight” security reduction, albeit to a stronger assumption that depends on the number of private key generation queries made by the adversary. Our assumption is a variant of Boneh et al.’s decisional Bilinear Diffie-Hellman Exponent assumption, which has been used to construct efficient hierarchical IBE and broadcast encryption systems. The construction is remarkably simple. It also provides recipient anonymity automatically, providing a second (and more efficient) solution to the problem of achieving anonymous IBE without random oracles. Finally, our proof of CCA2 security, which has more in common with the security proof for the Cramer-Shoup encryption scheme than with security proofs for other IBE systems, may be of independent interest.

Craig Gentry

### Sequential Aggregate Signatures and Multisignatures Without Random Oracles

We present the first aggregate signature, the first multisignature, and the first verifiably encrypted signature provably secure without random oracles. Our constructions derive from a novel application of a recent signature scheme due to Waters. Signatures in our aggregate signature scheme are sequentially constructed, but knowledge of the order in which messages were signed is not necessary for verification. The aggregate signatures obtained are shorter than Lysyanskaya et al. sequential aggregates and can be verified more efficiently than Boneh et al. aggregates. We also consider applications to secure routing and proxy signatures.

Steve Lu, Rafail Ostrovsky, Amit Sahai, Hovav Shacham, Brent Waters

### Our Data, Ourselves: Privacy Via Distributed Noise Generation

In this work we provide efficient distributed protocols for generating shares of random noise, secure against malicious participants. The purpose of the noise generation is to create a distributed implementation of the privacy-preserving statistical databases described in recent papers [14,4,13]. In these databases, privacy is obtained by perturbing the true answer to a database query by the addition of a small amount of Gaussian or exponentially distributed random noise. The computational power of even a simple form of these databases, when the query is just of the form ∑

i

f

(

d

i

), that is, the sum over all rows

i

in the database of a function

f

applied to the data in row

i

, has been demonstrated in [4]. A distributed implementation eliminates the need for a trusted database administrator.

The results for noise generation are of independent interest. The generation of Gaussian noise introduces a technique for distributing shares of many unbiased coins with fewer executions of verifiable secret sharing than would be needed using previous approaches (reduced by a factor of

n

). The generation of exponentially distributed noise uses two shallow circuits: one for generating many arbitrarily but identically biased coins at an amortized cost of two unbiased random bits apiece, independent of the bias, and the other to combine bits of appropriate biases to obtain an exponential distribution.

Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, Moni Naor

### On the (Im-)Possibility of Extending Coin Toss

We consider the cryptographic two-party protocol task of extending a given coin toss. The goal is to generate

n

common random coins from a single use of an ideal functionality which gives

m

<

n

common random coins to the parties. In the framework of Universal Composability we show the impossibility of securely extending a coin toss for statistical and perfect security. On the other hand, for computational security the existence of a protocol for coin toss extension depends on the number

m

For the case of stand-alone security, i.e., a simulation based security definition without an environment, we present a novel protocol for unconditionally secure coin toss extension. The new protocol works for superlogarithmic

m

, which is optimal as we show the impossibility of statistically secure coin toss extension for smaller

m

.

Combining our results with already known results, we obtain a (nearly) complete characterization under which circumstances coin toss extension is possible.

Dennis Hofheinz, Jörn Müller-Quade, Dominique Unruh

### Efficient Binary Conversion for Paillier Encrypted Values

We consider the framework of secure

n

-party computation based on threshold homomorphic cryptosystems as put forth by Cramer, Damgård, and Nielsen at Eurocrypt 2001. When used with Paillier’s cryptosystem, this framework allows for efficient secure evaluation of any arithmetic circuit defined over ℤ

N

, where

N

is the RSA modulus of the underlying Paillier cryptosystem.

In this paper, we extend the scope of the framework by considering the problem of converting a given Paillier encryption of a value

x

∈ ℤ

N

into Paillier encryptions of the bits of

x

. We present solutions for the general case in which

x

can be any integer in {0,1,...,

N

– 1}, and for the restricted case in which

x

<

N

/(

n

2

κ

) for a security parameter

κ

. In the latter case, we show how to extract the ℓ least significant bits of

x

(in encrypted form) in time proportional to ℓ, typically saving a factor of log

2

N

/ℓ compared to the general case.

Thus, intermediate computations that rely in an essential way on the binary representations of their input values can be handled without enforcing that the

entire

computation is done bitwise. Typical examples involve the relational operators such as < and =. As a specific scenario we will consider the setting for (approximate) matching of biometric templates, given as bit strings.

Berry Schoenmakers, Pim Tuyls

### Information-Theoretic Conditions for Two-Party Secure Function Evaluation

The standard security definition of unconditional secure function evaluation, which is based on the ideal/real model paradigm, has the disadvantage of being overly complicated to work with in practice. On the other hand, simpler ad-hoc definitions tailored to special scenarios have often been flawed. Motivated by this unsatisfactory situation, we give an information-theoretic security definition of secure function evaluation which is very simple yet provably equivalent to the standard, simulation-based definitions.

Claude Crépeau, George Savvides, Christian Schaffner, Jürg Wullschleger

### Unclonable Group Identification

We introduce and motivate the concept of unclonable group identification, that provides maximal protection against sharing of identities while still protecting the anonymity of users. We prove that the notion can be realized from any one-way function and suggest a more efficient implementation based on specific assumptions.

Ivan Damgård, Kasper Dupont, Michael Østergaard Pedersen

### Fully Collusion Resistant Traitor Tracing with Short Ciphertexts and Private Keys

We construct a fully collusion resistant tracing traitors system with sublinear size ciphertexts and constant size private keys. More precisely, let

N

be the total number of users. Our system generates ciphertexts of size

$O(\sqrt{N})$

and private keys of size

O

(1). We first introduce a simpler primitive we call

(PLBE) and show that any PLBE gives a tracing traitors system with the same parameters. We then show how to build a PLBE system with

$O(\sqrt{N})$

size ciphertexts. Our system uses bilinear maps in groups of composite order.

Dan Boneh, Amit Sahai, Brent Waters

### Simplified Threshold RSA with Adaptive and Proactive Security

We present the currently simplest, most efficient, optimally resilient, adaptively secure, and proactive threshold RSA scheme. A main technical contribution is a new rewinding strategy for analysing threshold signature schemes. This new rewinding strategy allows to prove adaptive security of a proactive threshold signature scheme which was previously assumed to be only statically secure. As a separate contribution we prove that our protocol is secure in the UC framework.

Jesús F. Almansa, Ivan Damgård, Jesper Buus Nielsen

### Erratum to: Advances in Cryptology -- EUROCRYPT 2006

Erratum to: S. Vaudenay (Ed.) Advances in Cryptology – EUROCRYPT 2006 DOI: 10.1007/978-3-540-34547-3The book was inadvertently published with an incorrect name of the copyright holder. The name of the copyright holder for this book is: © Springer-Verlag Berlin Heidelberg. The book has been updated with the changes.

Serge Vaudenay

### Backmatter

Weitere Informationen