main-content

## Inhaltsverzeichnis

### Chosen-Prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities

We present a novel, automated way to find differential paths for MD5. As an application we have shown how, at an approximate expected cost of 2

50

calls to the MD5 compression function, for any two chosen message prefixes

P

and

P

′, suffixes

S

and

S

′ can be constructed such that the concatenated values

P

||

S

and

P

′||

S

′ collide under MD5. Although the practical attack potential of this construction of

chosen-prefix collisions

is limited, it is of greater concern than random collisions for MD5. To illustrate the practicality of our method, we constructed two MD5 based X.509 certificates with identical signatures but different public keys

and

different Distinguished Name fields, whereas our previous construction of colliding X.509 certificates required identical name fields. We speculate on other possibilities for abusing chosen-prefix collisions. More details than can be included here can be found on

www.win.tue.nl/hashclash/ChosenPrefixCollisions/

.

Marc Stevens, Arjen Lenstra, Benne de Weger

### Non-trivial Black-Box Combiners for Collision-Resistant Hash-Functions Don’t Exist

A (

k

,ℓ)-robust combiner for collision-resistant hash-functions is a construction which from ℓ hash-functions constructs a hash-function which is collision-resistant if at least

k

of the components are collision-resistant. One trivially gets a (

k

,ℓ)-robust combiner by concatenating the output of any ℓ−

k

+ 1 of the components, unfortunately this is not very practical as the length of the output of the combiner is quite large. We show that this is unavoidable as no black-box (

k

,ℓ)-robust combiner whose output is significantly shorter than what can be achieved by concatenation exists. This answers a question of Boneh and Boyen (Crypto’06).

Krzysztof Pietrzak

### The Collision Intractability of MDC-2 in the Ideal-Cipher Model

We provide the first proof of security for MDC-2, the most well-known construction for turning an

n

-bit blockcipher into a 2

n

-bit cryptographic hash function. Our result, which is in the ideal-cipher model, shows that MDC-2, when built from a blockcipher having blocklength and keylength

n

, has security much better than that delivered by any hash function that has an

n

-bit output. When the blocklength and keylength are

n

= 128 bits, as with MDC-2 based on AES-128, an adversary that asks fewer than 2

74.9

queries usually cannot find a collision.

John P. Steinberger

### An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries

We show an efficient secure two-party protocol, based on Yao’s construction, which provides security against malicious adversaries. Yao’s original protocol is only secure in the presence of semi-honest adversaries. Security against malicious adversaries can be obtained by applying the compiler of Goldreich, Micali and Wigderson (the “GMW compiler”). However, this approach does not seem to be very practical as it requires using generic zero-knowledge proofs.

Our construction is based on applying cut-and-choose techniques to the original circuit and inputs. Security is proved according to the ideal/real simulation paradigm, and the proof is in the standard model (with no random oracle model or common reference string assumptions). The resulting protocol is computationally efficient: the only usage of asymmetric cryptography is for running

O

(1) oblivious transfers for each input bit (or for each bit of a statistical security parameter, whichever is larger). Our protocol combines techniques from folklore (like cut-and-choose) along with new techniques for efficiently proving consistency of inputs. We remark that a naive implementation of the cut-and-choose technique with Yao’s protocol does

not

yield a secure protocol. This is the first paper to show how to properly implement these techniques, and to provide a full proof of security.

Our protocol can also be interpreted as a constant-round black-box reduction of secure two-party computation to oblivious transfer and perfectly-hiding commitments, or a black-box reduction of secure two-party computation to oblivious transfer alone, with a number of rounds which is linear in a statistical security parameter. These two reductions are comparable to Kilian’s reduction, which uses OT alone but incurs a number of rounds which is linear in the depth of the circuit [18].

Yehuda Lindell, Benny Pinkas

### Revisiting the Efficiency of Malicious Two-Party Computation

In a recent paper Mohassel and Franklin study the efficiency of secure two-party computation in the presence of malicious behavior. Their aim is to make classical solutions to this problem, such as zero-knowledge compilation, more efficient. The authors provide several schemes which are the most efficient to date. We propose a modification to their main scheme using expanders. Our modification asymptotically improves at least one measure of efficiency of all known schemes. We also point out an error, and improve the analysis of one of their schemes.

David P. Woodruff

### Efficient Two-Party Secure Computation on Committed Inputs

We present an efficient construction of Yao’s “garbled circuits” protocol for securely computing any two-party circuit on committed inputs. The protocol is secure in a universally composable way in the presence of

malicious

adversaries under the decisional composite residuosity (DCR) and strong RSA assumptions, in the common reference string model. The protocol requires a constant number of rounds (four-five in the standard model, two-three in the random oracle model, depending on whether both parties receive the output),

O

(|

C

|) modular exponentiations per player, and a bandwidth of

O

(|

C

|) group elements, where |

C

| is the size of the computed circuit.

Our technical tools are of independent interest. We propose a homomorphic, semantically secure variant of the Camenisch-Shoup verifiable cryptosystem, which uses shorter keys, is

unambiguous

(it is infeasible to generate two keys which successfully decrypt the same ciphertext), and allows efficient proofs that a committed plaintext is encrypted under a

committed key

.

Our second tool is a practical four-round (two-round in ROM) protocol for

committed

oblivious transfer on

strings

(string-COT) secure against malicious participants. The string-COT protocol takes a few exponentiations per player, and is UC-secure under the DCR assumption in the common reference string model. Previous protocols of comparable efficiency achieved either committed OT on

bits

, or standard (non-committed) OT on strings.

Stanisław Jarecki, Vitaly Shmatikov

### Universally Composable Multi-party Computation Using Tamper-Proof Hardware

Protocols proven secure within the

universal composability (UC) framework

satisfy strong and desirable security properties. Unfortunately, it is known that within the “plain” model, secure computation of general functionalities without an honest majority is impossible. This has prompted researchers to propose various “setup assumptions” with which to augment the bare UC framework in order to bypass this severe negative result. Existing setup assumptions seem to inherently require

some

trusted party (or parties) to initialize the setup in the real world.

We propose a new setup assumption — more along the lines of a

physical

assumption regarding the existence of tamper-proof hardware — which also suffices to circumvent the impossibility result mentioned above. We suggest this assumption as potentially leading to an approach that might alleviate the need for trusted parties, and compare our assumption to those proposed previously.

Jonathan Katz

### Generic and Practical Resettable Zero-Knowledge in the Bare Public-Key Model

We present a generic construction for constant-round concurrsound resettable zero-knowledge (rZK-CS) arguments for

$\mathcal{NP}$

in the bare public-key (BPK) model under any (sub-exponentially strong) one-way function (OWF), which is a traditional assumption in this area. The generic construction in turn allows round-optimal implementation for

$\mathcal{NP}$

still under general assumptions, and can be converted into a highly practical instantiation (under specific number-theoretic assumptions) for any language admitting Σ-protocols. Further, the rZK-CS arguments developed in this work also satisfy a weak (black-box) concurrent knowledge-extractability property as proofs of knowledge, in which case some super-polynomial-time assumption is intrinsic.

Moti Yung, Yunlei Zhao

### Instance-Dependent Verifiable Random Functions and Their Application to Simultaneous Resettability

We introduce a notion of

instance-dependent verifiable random functions

(InstD-VRFs for short). Informally, an InstD-VRF is, in some sense, a verifiable random function [23] with a special public key, which is generated via a (possibly)

interactive

protocol and contains an instance

y

∈

L

∩ {0,1}

*

for a specific NP language

L

, but the security requirements on such a function are relaxed: we only require the

pseudorandomness

property when

y

∈

L

and only require the

uniqueness

property when

y

∉

L

, instead of requiring both pseudorandomness and uniqueness to hold

simultaneously

. We show that this notion can be realized under standard assumption.

Our motivation is the conjecture posed by Barak et al.[2], which states there exist resettably-sound resettable zero knowledge arguments for NP. The instance-dependent verifiable random functions is a powerful tool to tackle this problem. We first use them to obtain two interesting instance-dependent argument systems from the Barak’s public-coin bounded concurrent zero knowledge argument [1], and then, we

1

Construct the

first

(constant round) zero knowledge arguments for NP enjoying a

certain

simultaneous resettability under standard hardness assumptions in the plain model, which we call bounded-class resettable ZK arguments with weak resettable-soundness Though the malicious party (prover or verifier) in such system is limited to a kind of bounded resetting attack, We put NO restrictions on the number of the total resets made by malicious party.

2

show that, under standard assumptions, if there exist public-coin concurrent zero knowledge arguments for NP, there exist the resettably-sound resetable zero knowledge arguments for NP.

Yi Deng, Dongdai Lin

### Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility

We study conditional computational entropy: the amount of randomness a distribution appears to have to a computationally bounded observer who is given some correlated information. By considering conditional versions of HILL entropy (based on indistinguishability from truly random distributions) and Yao entropy (based on incompressibility), we obtain:

a separation between conditional HILL and Yao entropies (which can be viewed as a separation between the traditional HILL and Yao entropies in the shared random string model, improving on Wee’s 2004 separation in the random oracle model);

the first demonstration of a distribution from which extraction techniques based on Yao entropy produce more pseudorandom bits than appears possible by the traditional HILL-entropy-based techniques;

a new, natural notion of unpredictability entropy, which implies conditional Yao entropy and thus allows for known extraction and hardcore bit results to be stated and used more generally.

Chun-Yuan Hsiao, Chi-Jen Lu, Leonid Reyzin

### Zero Knowledge and Soundness Are Symmetric

We give a complexity-theoretic characterization of the class of problems in

NP

having zero-knowledge argument systems. This characterization is symmetric in its treatment of the zero knowledge and the soundness conditions, and thus we deduce that the class of problems in

NP

∩

coNP

having zero-knowledge arguments is closed under complement. Furthermore, we show that a problem in

NP

has a

statistical

zero-knowledge argument system if and only if its complement has a computational zero-knowledge

proof

system. What is novel about these results is that they are

unconditional

, i.e., do not rely on unproven complexity assumptions such as the existence of one-way functions.

Our characterization of zero-knowledge arguments also enables us to prove a variety of other unconditional results about the class of problems in

NP

having zero-knowledge arguments, such as equivalences between honest-verifier and malicious-verifier zero knowledge, private coins and public coins, inefficient provers and efficient provers, and non-black-box simulation and black-box simulation. Previously, such results were only known unconditionally for zero-knowledge

proof systems

, or under the assumption that one-way functions exist for zero-knowledge argument systems.

### Mesh Signatures

How to Leak a Secret with Unwitting and Unwilling Participants

We define the mesh signature primitive as an anonymous signature similar in spirit to ring signatures, but with a much richer language for expressing signer ambiguity. The language can represent complex access structures, and in particular allows individual signature components to be replaced with complete certificate chains. Because withholding one’s public key from view is no longer a shield against being named as a possible cosignatory, mesh signatures may be used as a ring signature with compulsory enrollment.

We give an efficient construction based on bilinear maps in the common random string model. Our signatures have linear size, achieve everlasting perfect anonymity, and reduce to very efficient ring signatures without random oracles as a special case. We prove non-repudiation from a mild extension of the SDH assumption, which we introduce and justify meticulously.

Xavier Boyen

### The Power of Proofs-of-Possession: Securing Multiparty Signatures against Rogue-Key Attacks

Multiparty signature protocols need protection against

rogue-key attacks

, made possible whenever an adversary can choose its public key(s) arbitrarily. For many schemes, provable security has only been established under the

knowledge of secret key

(KOSK) assumption where the adversary is required to reveal the secret keys it utilizes. In practice, certifying authorities rarely require the strong proofs of knowledge of secret keys required to substantiate the KOSK assumption. Instead,

proofs of possession

(POPs) are required and can be as simple as just a signature over the certificate request message. We propose a general

registered key

model, within which we can model both the KOSK assumption and in-use POP protocols. We show that simple POP protocols yield provable security of Boldyreva’s multisignature scheme [11], the LOSSW multisignature scheme [28], and a 2-user ring signature scheme due to Bender, Katz, and Morselli [10]. Our results are the

first

to provide formal evidence that POPs can stop rogue-key attacks.

Thomas Ristenpart, Scott Yilek

### Batch Verification of Short Signatures

With computer networks spreading into a variety of new environments, the need to authenticate and secure communication grows. Many of these new environments have particular requirements on the applicable cryptographic primitives. For instance, several applications require that communication overhead be small and that many messages be processed at the same time. In this paper we consider the suitability of public key signatures in the latter scenario. That is, we consider signatures that are 1) short and 2) where many signatures from (possibly) different signers on (possibly) different messages can be verified quickly.

We propose the first batch verifier for messages from many (certified) signers without random oracles and with a verification time where the dominant operation is independent of the number of signatures to verify. We further propose a new signature scheme with very short signatures, for which batch verification for

many

signers is also highly efficient. Prior work focused almost exclusively on batching signatures from the same signer. Combining our new signatures with the best known techniques for batching certificates from the

same

authority, we get a fast batch verifier for certificates and messages combined. Although our new signature scheme has some restrictions, it is the only solution, to our knowledge, that is a candidate for some pervasive communication applications.

Jan Camenisch, Susan Hohenberger, Michael Østergaard Pedersen

### Cryptanalysis of SFLASH with Slightly Modified Parameters

SFLASH is a signature scheme which belongs to a family of multivariate schemes proposed by Patarin

et al.

in 1998 [9]. The SFLASH scheme itself has been designed in 2001 [8] and has been selected in 2003 by the NESSIE European Consortium [6] as the best known solution for implementation on low cost smart cards. In this paper, we show that slight modifications of the parameters of SFLASH within the general family initially proposed renders the scheme insecure. The attack uses simple linear algebra, and allows to forge a signature for an arbitrary message in a question of minutes for practical parameters, using only the public key. Although SFLASH itself is not amenable to our attack, it is worrying to observe that no rationale was ever offered for this “lucky” choice of parameters.

Vivien Dubois, Pierre-Alain Fouque, Jacques Stern

### Differential Cryptanalysis of the Stream Ciphers Py, Py6 and Pypy

Py and Pypy are efficient array-based stream ciphers designed by Biham and Seberry. Both were submitted to the eSTREAM competition. This paper shows that Py and Pypy are practically insecure. If one key is used with about 2

16

IVs with special differences, with high probability two identical keystreams will appear. This can be exploited in a key recovery attack. For example, for a 16-byte key and a 16-byte IV, 2

23

chosen IVs can reduce the effective key size to 3 bytes. For a 32-byte key and a 32-byte IV, the effective key size is reduced to 3 bytes with 2

24

chosen IVs. Py6, a variant of Py, is more vulnerable to these attacks.

Hongjun Wu, Bart Preneel

### Secure Computation from Random Error Correcting Codes

Secure computation consists of protocols for secure arithmetic: secret values are added and multiplied securely by networked processors. The striking feature of secure computation is that security is maintained even in the presence of an adversary who corrupts a quorum of the processors and who exercises full, malicious control over them. One of the fundamental primitives at the heart of secure computation is secret-sharing. Typically, the required secret-sharing techniques build on Shamir’s scheme, which can be viewed as a cryptographic twist on the Reed-Solomon error correcting code. In this work we further the connections between secure computation and error correcting codes. We demonstrate that threshold secure computation in the secure channels model can be based on arbitrary codes. For a network of size

n

, we then show a reduction in communication for secure computation amounting to a multiplicative logarithmic factor (in

n

) compared to classical methods for small, e.g., constant size fields, while tolerating

$t < ({1 \over 2} - {\epsilon}) {n}$

players to be corrupted, where

ε

> 0 can be arbitrarily small. For large networks this implies considerable savings in communication. Our results hold in the broadcast/negligible error model of Rabin and Ben-Or, and complement results from CRYPTO 2006 for the zero-error model of Ben-Or, Goldwasser and Wigderson (BGW). Our general theory can be extended so as to encompass those results from CRYPTO 2006 as well. We also present a new method for constructing high information rate ramp schemes based on arbitrary codes, and in particular we give a new construction based on algebraic geometry codes.

Hao Chen, Ronald Cramer, Shafi Goldwasser, Robbert de Haan, Vinod Vaikuntanathan

### Round-Efficient Secure Computation in Point-to-Point Networks

Essentially all work studying the round complexity of secure computation assume broadcast as an atomic primitive. Protocols constructed under this assumption tend to have very poor round complexity when compiled for a point-to-point network due to the high overhead of emulating each invocation of broadcast. This problem is compounded when broadcast is used in more than one round of the original protocol due to the complexity of handling sequential composition (when using round-efficient emulation of broadcast).

We argue that if the goal is to optimize round complexity in point-to-point networks, then it is preferable to design protocols — assuming a broadcast channel — minimizing the

number of rounds in which broadcast is used

rather than minimizing the

total number of rounds

. With this in mind, we present protocols for secure computation in a number of settings that use only a

single

round of broadcast. In all cases, we achieve optimal security threshold for adaptive adversaries, and obtain protocols whose round complexity (in a point-to-point network) improves on prior work.

Jonathan Katz, Chiu-Yuen Koo

### Atomic Secure Multi-party Multiplication with Low Communication

We consider the standard secure multi-party multiplication protocol due to M. Rabin. This protocol is based on Shamir’s secret sharing scheme and it can be viewed as a practical variation on one of the central techniques in the foundational results of Ben-Or, Goldwasser, and Wigderson and Chaum, Crépeau, and Damgaard on secure multi-party computation. Rabin’s idea is a key ingredient to virtually all practical protocols in threshold cryptography.

Given a passive

t

-adversary in the secure channels model with synchronous communication, for example, secure multiplication of two secret-shared elements from a finite field

K

based on this idea uses one communication round and has the network exchange

O

(

n

2

) field elements, if

t

= Θ(

n

) and

t

<

n

/2 and if

n

is the number of players. This is because each of

O

(

n

) players must perform Shamir secret sharing as part of the protocol. This paper demonstrates that under a few restrictions much more efficient protocols are possible; even at the level of a single multiplication.

We demonstrate a twist on Rabin’s idea that enables one-round secure multiplication

with just O

(

n

)

bandwidth

in certain settings, thus reducing it from quadratic to linear. The ideas involved can additionally be employed in the evaluation of arithmetic circuits, where under appropriate circumstances similar efficiency gains can be obtained.

Ronald Cramer, Ivan Damgård, Robbert de Haan

### Cryptanalysis of the Sidelnikov Cryptosystem

We present a structural attack against the Sidelnikov cryptosystem [8]. The attack creates a private key from a given public key. Its running time is subexponential and is effective if the parameters of the Reed-Muller code allow for efficient sampling of minimum weight codewords. For example, the length 2048, 3rd-order Reed-Muller code as proposed in [8] takes roughly an hour to break on a stock PC using the presented method.

Lorenz Minder, Amin Shokrollahi

### Toward a Rigorous Variation of Coppersmith’s Algorithm on Three Variables

In 1996, Coppersmith introduced two lattice reduction based techniques to find small roots in polynomial equations. One technique works for modular univariate polynomials, the other for bivariate polynomials over the integers. Since then, these methods have been used in a huge variety of cryptanalytic applications. Some applications also use extensions of Coppersmith’s techniques on more variables. However, these extensions are heuristic methods. In the present paper, we present and analyze a new variation of Coppersmith’s algorithm on three variables over the integers. We also study the applicability of our method to short RSA exponents attacks. In addition to lattice reduction techniques, our method also uses Gröbner bases computations. Moreover, at least in principle, it can be generalized to four or more variables.

Aurélie Bauer, Antoine Joux

### An L (1/3 + ε) Algorithm for the Discrete Logarithm Problem for Low Degree Curves

The discrete logarithm problem in Jacobians of curves of high genus

g

over finite fields

$\mathbb {F}_q$

is known to be computable with subexponential complexity

$L_{q^g}(1/2, O(1))$

. We present an algorithm for a family of plane curves whose degrees in

X

and

Y

are low with respect to the curve genus, and suitably unbalanced. The finite base fields are arbitrary, but their sizes should not grow too fast compared to the genus. For this family, the group structure can be computed in subexponential time of

$L_{q^g}(1/3, O(1))$

, and a discrete logarithm computation takes subexponential time of

$L_{q^g}(1/3+ \varepsilon, o(1))$

for any positive

ε

. These runtime bounds rely on heuristics similar to the ones used in the number field sieve or the function field sieve algorithms.

Andreas Enge, Pierrick Gaudry

### General Ad Hoc Encryption from Exponent Inversion IBE

Among the three broad classes of Identity-Based Encryption schemes built from pairings, the exponent inversion paradigm tends to be the most efficient, but also the least extensible: currently there are no hierarchical or other known extension of IBE based on those schemes. In this work, we show that such extensions can be realized from IBE systems that conform to a certain abstraction of the exponent inversion paradigm. Our method requires no random oracles, and is simple and efficient.

Xavier Boyen

### Non-interactive Proofs for Integer Multiplication

We present two universally composable and practical protocols by which a dealer can, verifiably and non-interactively, secret-share an integer among a set of players. Moreover, at small extra cost and using a distributed verifier proof, it can be shown in zero-knowledge that three shared integers

a

,

b

,

c

satisfy

ab

=

c

. This implies by known reductions non-interactive zero-knowledge proofs that a shared integer is in a given interval, or that one secret integer is larger than another. Such primitives are useful, e.g., for supplying inputs to a multiparty computation protocol, such as an auction or an election. The protocols use various set-up assumptions, but do not require the random oracle model.

Ivan Damgård, Rune Thorbek

### Ate Pairing on Hyperelliptic Curves

In this paper we show that the Ate pairing, originally defined for elliptic curves, generalises to hyperelliptic curves and in fact to arbitrary algebraic curves. It has the following surprising properties: The loop length in Miller’s algorithm can be up to

g

times shorter than for the Tate pairing, with

g

the genus of the curve, and the pairing is automatically reduced, i.e. no final exponentiation is needed.

R. Granger, F. Hess, R. Oyono, N. Thériault, F. Vercauteren

### Ideal Multipartite Secret Sharing Schemes

Multipartite secret sharing schemes are those having a multipartite access structure, in which the set of participants is divided into several parts and all participants in the same part play an equivalent role. Several particular families of multipartite schemes, such as the weighted threshold schemes, the hierarchical and the compartmented schemes, and the ones with bipartite or tripartite access structure have been considered in the literature. The characterization of the access structures of ideal secret sharing schemes is one of the main open problems in secret sharing. In this work, the characterization of ideal multipartite access structures is studied with all generality. Our results are based on the well-known connections between ideal secret sharing schemes and matroids. One of the main contributions of this paper is the application of discrete polymatroids to secret sharing. They are proved to be a powerful tool to study the properties of multipartite matroids. In this way, we obtain some necessary conditions and some sufficient conditions for a multipartite access structure to be ideal.

Our results can be summarized as follows. First, we present a characterization of matroid-related multipartite access structures in terms of discrete polymatroids. As a consequence of this characterization, a necessary condition for a multipartite access structure to be ideal is obtained. Second, we use linear representations of discrete polymatroids to characterize the linearly representable multipartite matroids. In this way we obtain a sufficient condition for a multipartite access structure to be ideal. Finally, we apply our general results to obtain a complete characterization of ideal tripartite access structures, which was until now an open problem.

Oriol Farràs, Jaume Martí-Farré, Carles Padró

### Non-wafer-Scale Sieving Hardware for the NFS: Another Attempt to Cope with 1024-Bit

Significant progress in the design of special purpose hardware for supporting the Number Field Sieve (NFS) has been made. From a practical cryptanalytic point of view, however, none of the published proposals for coping with the sieving step is satisfying. Even for the best known designs, the technological obstacles faced for the parameters expected for a 1024-bit RSA modulus are significant.

Below we present a new hardware design for implementing the sieving step. The suggested chips are of moderate size and the inter-chip communication does not seem unrealistic. According to our preliminary analysis of the 1024-bit case, we expect the new design to be about 2 to 3.5 times slower than TWIRL (a wafer-scale design). Due to the more moderate technological requirements, however, from a practical cryptanalytic point of view the new design seems to be no less attractive than TWIRL.

Willi Geiselmann, Rainer Steinwandt

### Divisible E-Cash Systems Can Be Truly Anonymous

This paper presents an off-line divisible e-cash scheme where a user can withdraw a divisible coin of monetary value 2

L

that he can parceled and spend anonymously and unlinkably. We present the construction of a security tag that allows to protect the anonymity of honest users and to revoke anonymity only in case of cheat for protocols based on a binary tree structure without using a trusted third party. This is the first divisible e-cash scheme that provides both full unlinkability and anonymity without requiring a trusted third party.

Sébastien Canard, Aline Gouget

### A Fast and Key-Efficient Reduction of Chosen-Ciphertext to Known-Plaintext Security

Motivated by the quest for reducing assumptions in security proofs in cryptography, this paper is concerned with designing efficient symmetric encryption and authentication schemes based on any

weak

pseudorandom function (PRF) which can be much more efficiently implemented than PRFs. Damgård and Nielsen (CRYPTO ’02) have shown how to construct an efficient symmetric encryption scheme based on any weak PRF that is provably secure against chosen-

plaintext

attacks. The main ingredient is a range-extension construction for weak PRFs. By using well-known techniques, they also showed how their scheme can be made secure against the stronger chosen-

ciphertext

attacks.

The results of our paper are three-fold. First, we give a range-extension construction for weak PRFs that is optimal within a large and natural class of reductions (especially all known today). Second, we propose a construction of a regular PRF from any weak PRF. Third, these two results imply a (for long messages) much more efficient chosen-ciphertext secure encryption scheme than the one proposed by Damgård and Nielsen. The results also give answers to open questions posed by Naor and Reingold (CRYPTO ’98) and by Damgård and Nielsen.

Ueli Maurer, Johan Sjödin

### Range Extension for Weak PRFs; The Good, the Bad, and the Ugly

We investigate a general class of (black-box) constructions for range extension of weak pseudorandom functions: a construction based on

m

independent functions

F

1

,...,

F

m

is given by a set of strings over {1,...,

m

}

*

, where for example {〈2〉, 〈1,2〉} corresponds to the function

X

↦[

F

2

(

X

),

F

2

(

F

1

(

X

))]. All efficient constructions for range expansion of weak pseudorandom functions that we are aware of are of this form.

We completely classify such constructions as

good

,

or

ugly

, where the good constructions are those whose security can be proven via a black-box reduction, the bad constructions are those whose

in

security can be proven via a black-box reduction, and the ugly constructions are those which are neither good nor bad.

Our classification shows that the range expansion from [10] is optimal, in the sense that it achieves the best possible expansion (2

m

− 1 when using

m

keys).

Along the way we show that for weak

quasirandom

functions (i.e. in the information theoretic setting), all constructions which are not bad – in particular all the ugly ones – are secure.

Krzysztof Pietrzak, Johan Sjödin

### Feistel Networks Made Public, and Applications

Feistel Network, consisting of a repeated application of the Feistel Transform, gives a very convenient and popular method for designing “cryptographically strong” permutations from corresponding “cryptographically strong” functions. Up to now, all usages of the Feistel Network, including the celebrated Luby-Rackoff’s result, critically rely on (a)

the (pseudo)randomness of round functions

; and (b)

the secrecy of (at least some of) the intermediate round values

appearing during the Feistel computation. Moreover, a small constant number of Feistel rounds was typically sufficient to guarantee security under assumptions (a) and (b). In this work we consider several natural scenarios where at least one of the above assumptions does not hold, and show that a constant, or even logarithmic number of rounds is

provably insufficient

to handle such applications, implying that a new method of analysis is needed.

On a positive side, we develop a new combinatorial understanding of Feistel networks, which makes them applicable to situations when the round functions are merely

unpredictable

rather than (pseudo)random and/or when the intermediate round values may be leaked to the adversary (either through an attack or because the application

requires

it). In essence, our results show that in any such scenario a super-logarithmic number of Feistel rounds is

necessary and sufficient

to guarantee security.

Of independent interest, our technique yields a novel domain extension method for messages authentication codes and other related primitives, settling a question studied by An and Bellare in CRYPTO 1999.

Yevgeniy Dodis, Prashant Puniya

### Oblivious-Transfer Amplification

Oblivious transfer (OT) is a primitive of paramount importance in cryptography or, more precisely, two- and multi-party computation due to its universality. Unfortunately, OT cannot be achieved in an unconditionally secure way for both parties from scratch. Therefore, it is a natural question what information-theoretic primitives or computational assumptions OT

can

be based on.

The results in our paper are threefold. First, we give an optimal proof for the standard protocol to realize unconditionally secure OT from a weak variant of OT called

universal OT

, for which a malicious receiver can virtually obtain any possible information he wants, as long as he does not get all the information. This result is based on a novel distributed leftover hash lemma which is of independent interest.

Second, we give conditions for when OT can be obtained from a faulty variant of OT called

weak OT

, for which it can occur that any of the parties obtains too much information, or the result is incorrect. These bounds and protocols, which correct on previous results by Damgård

et. al.

, are of central interest since in most known realizations of OT from weak primitives, such as noisy channels, a weak OT is constructed first.

Finally, we carry over our results to the computational setting and show how a weak OT that is sometimes incorrect and is only mildly secure against computationally bounded adversaries can be strengthened.

Jürg Wullschleger

We study an

variant of oblivious transfer in which a sender has

N

k

one-after-the-other, in such a way that (a) the sender learns nothing about the receiver’s selections, and (b) the receiver only learns about the

k

requested messages. We propose two practical protocols for this primitive that achieve a stronger security notion than previous schemes with comparable efficiency. In particular, by requiring full simulatability for both sender and receiver security, our notion prohibits a subtle selective-failure attack not addressed by the security notions achieved by previous practical schemes.

Our first protocol is a very efficient generic construction from unique blind signatures in the random oracle model. The second construction does not assume random oracles, but achieves remarkable efficiency with only a constant number of group elements sent during each transfer. This second construction uses novel techniques for building efficient simulatable protocols.

Jan Camenisch, Gregory Neven, abhi shelat

### Backmatter

Weitere Informationen