Advances in Cryptology – EUROCRYPT 2008

KeeLoq is a lightweight block cipher with a 32-bit block size and a 64-bit key. Despite its short key size, it is widely used in remote keyless entry systems and other wireless authentication applications. For example, authentication protocols based on KeeLoq are supposedly used by various car manufacturers in anti-theft mechanisms. This paper presents a practical key recovery attack against KeeLoq that requires 2

16

known plaintexts and has a time complexity of 2

44.5

KeeLoq encryptions. It is based on the slide attack and a novel approach to meet-in-the-middle attacks. The fully implemented attack requires 65 minutes to obtain the required data and 7.8 days of calculations on 64 CPU cores. A variant which requires 2

16

chosen plaintexts needs only 3.4 days on 64 CPU cores. Using only 10 000 euro, an attacker can purchase a cluster of 50 dual core computers that will find the secret key in about two days. We investigated the way KeeLoq is intended to be used in practice and conclude that our attack can be used to subvert the security of real systems. An attacker can acquire chosen plaintexts in practice, and one of the two suggested key derivation schemes for KeeLoq allows to recover the master secret from a single key.

In this paper, we study the key recovery problem for the

C

*

scheme and generalisations where the quadratic monomial of

C

*

(the product of two linearized monomials) is replaced by a product of three or more linearized monomials. This problem has been further generalized to any system of multivariate polynomials hidden by two invertible linear maps and named the Isomorphism of Polynomials (

IP

) problem by Patarin. Some cryptosystems have been built on this apparently hard problem such as an authentication protocol proposed by Patarin and a traitor tracing scheme proposed by Billet and Gilbert. Here we show that if the hidden multivariate system is the projection of a quadratic monomial on a base finite field, as in

C

*

, or a cubic (or higher) monomial as in the traitor tracing scheme, then it is possible to recover an equivalent secret key in polynomial time

O

(

n

d

) where

n

is the number of variables and

d

is the degree of the public polynomials.

Despite their popularity, lattice reduction algorithms remain mysterious cryptanalytical tools. Though it has been widely reported that they behave better than their proved worst-case theoretical bounds, no precise assessment has ever been given. Such an assessment would be very helpful to predict the behaviour of lattice-based attacks, as well as to select keysizes for lattice-based cryptosystems. The goal of this paper is to provide such an assessment, based on extensive experiments performed with the NTL library. The experiments suggest several conjectures on the worst case and the actual behaviour of lattice reduction algorithms. We believe the assessment might also help to design new reduction algorithms overcoming the limitations of current algorithms.

We generalize the concept of sequential aggregate signatures (SAS), proposed by Lysyanskaya, Micali, Reyzin, and Shacham (LMRS) at Eurocrypt 2004, to a new primitive called

sequential aggregate signed data

(SASD) that tries to minimize the total amount of transmitted data, rather than just signature length. We present SAS and SASD schemes that offer numerous advantages over the LMRS scheme. Most importantly, our schemes can be instantiated with

uncertified

claw-free permutations, thereby allowing implementations based on low-exponent RSA and factoring, and drastically reducing signing and verification costs. Our schemes support aggregation of signatures under keys of different lengths, and the SASD scheme even has as little as 160 bits of bandwidth overhead. Finally, we present a multi-signed data scheme that, when compared to the state-of-the-art multi-signature schemes, is the first scheme with non-interactive signature generation not based on pairings. All of our constructions are proved secure in the random oracle model based on families of claw-free permutations.

This paper proves “tight security in the random-oracle model relative to factorization” for the lowest-cost signature systems available today: every hash-generic signature-forging attack can be converted, with negligible loss of efficiency and effectiveness, into an algorithm to factor the public key. The most surprising system is the “fixed unstructured

B

= 0 Rabin-Williams” system, which has a tight security proof despite hashing unrandomized messages.

We consider the use of threshold signatures in ad-hoc and dynamic groups such as MANETs (“mobile ad-hoc networks”). While the known threshold RSA signature schemes have several properties that make them good candidates for deployment in these scenarios, none of these schemes seems practical enough for realistic use in these highly-constrained environments. In particular, this is the case of the most efficient of these threshold RSA schemes, namely, the one due to Shoup. Our contribution is in presenting variants of Shoup’s protocol that overcome the limitations that make the original protocol unsuitable for dynamic groups. The resultant schemes provide the efficiency and flexibility needed in ad-hoc groups, and add the capability of incorporating new members (share-holders) to the group of potential signers without relying on central authorities. Namely, any threshold of existing members can cooperate to add a new member. The schemes are efficient, fully non-interactive and do not assume broadcast.

Standard security notions for encryption schemes do not guarantee any security if the encrypted messages depend on the secret key. Yet it is exactly the stronger notion of security in the presence of

key-dependent

messages (KDM security) that is required in a number of applications: most prominently, KDM security plays an important role in analyzing cryptographic multi-party protocols in a formal calculus. But although often assumed, the mere existence of KDM secure schemes is an open problem. The only previously known construction was proven secure in the random oracle model.

We present symmetric encryption schemes that are KDM secure in the standard model (i.e., without random oracles). The price we pay is that we achieve only a relaxed (but still useful) notion of key-dependent message security. Our work answers (at least partially) an open problem posed by Black, Rogaway, and Shrimpton. More concretely, our contributions are as follows:

1

We present a (stateless) symmetric encryption scheme that is information-theoretically secure in face of a

bounded

number and length of encryptions for which the messages depend in an arbitrary way on the secret key.

1

We present a stateful symmetric encryption scheme that is computationally secure in face of an arbitrary number of encryptions for which the messages depend only on the respective

current

secret state/key of the scheme. The underlying computational assumption is minimal: we assume the existence of one-way functions.

1

We give evidence that the only previously known KDM secure encryption scheme cannot be proven secure in the standard model (i.e., without random oracles).

We propose a new computational problem called the

twin Diffie-Hellman problem

. This problem is closely related to the usual (computational) Diffie-Hellman problem and can be used in many of the same cryptographic constructions that are based on the Diffie-Hellman problem. Moreover, the twin Diffie-Hellman problem is at least as hard as the ordinary Diffie-Hellman problem. However, we are able to show that the twin Diffie-Hellman problem remains hard, even in the presence of a decision oracle that recognizes solutions to the problem — this is a feature not enjoyed by the ordinary Diffie-Hellman problem. In particular, we show how to build a certain “trapdoor test” which allows us to effectively answer such decision oracle queries, without knowing any of the corresponding discrete logarithms. Our new techniques have many applications. As one such application, we present a new variant of ElGamal encryption with very short ciphertexts, and with a very simple and tight security proof, in the random oracle model, under the assumption that the ordinary Diffie-Hellman problem is hard. We present several other applications as well, including: a new variant of Diffie and Hellman’s non-interactive key exchange protocol; a new variant of Cramer-Shoup encryption, with a very simple proof in the standard model; a new variant of Boneh-Franklin identity-based encryption, with very short ciphertexts; a more robust version of a password-authenticated key exchange protocol of Abdalla and Pointcheval.

Predicate encryption is a new paradigm generalizing, among other things, identity-based encryption. In a predicate encryption scheme, secret keys correspond to predicates and ciphertexts are associated with attributes; the secret key

SK

f

corresponding to a predicate

f

can be used to decrypt a ciphertext associated with attribute

I

if and only if

f

(

I

) = 1. Constructions of such schemes are currently known for relatively few classes of predicates.

We construct such a scheme for predicates corresponding to the evaluation of

inner products

over

(for some large integer

N

). This, in turn, enables constructions in which predicates correspond to the evaluation of disjunctions, polynomials, CNF/DNF formulae, or threshold predicates (among others). Besides serving as a significant step forward in the theory of predicate encryption, our results lead to a number of applications that are interesting in their own right.

We describe the use of explicit isogenies to translate instances of the Discrete Logarithm Problem from Jacobians of hyperelliptic genus 3 curves to Jacobians of non-hyperelliptic genus 3 curves, where they are vulnerable to faster index calculus attacks. We provide explicit formulae for isogenies with kernel isomorphic to (ℤ/2ℤ)

3

(over an algebraic closure of the base field) for any hyperelliptic genus 3 curve over a field of characteristic not 2 or 3. These isogenies are rational for a positive fraction of all hyperelliptic genus 3 curves defined over a finite field of characteristic

p

 > 3. Subject to reasonable assumptions, our constructions give an explicit and efficient reduction of instances of the DLP from hyperelliptic to non-hyperelliptic Jacobians for around 18.57% of all hyperelliptic genus 3 curves over a given finite field.

In this paper we prove that the sponge construction introduced in [4] is indifferentiable from a random oracle when being used with a random transformation or a random permutation and discuss its implications. To our knowledge, this is the first time indifferentiability has been shown for a construction calling a random permutation (instead of an ideal compression function or ideal block cipher) and for a construction generating outputs of any length (instead of a fixed length).

We propose a new mode of operation,

enciphered CBC

, for domain extension of length-preserving functions (like block ciphers), which is a variation on the popular CBC mode of operation. Our new mode is twice slower than CBC, but has many (property-preserving) properties not enjoyed by CBC and other known modes. Most notably, it yields the first constant-rate Variable Input Length (VIL) MAC from any length preserving Fixed Input Length (FIL) MAC. This answers the question of Dodis and Puniya from Eurocrypt 2007. Further, our mode is a secure domain extender for PRFs (with basically the same security as encrypted CBC). This provides a hedge against the security of the block cipher: if the block cipher is pseudorandom, one gets a VIL-PRF, while if it is “only” unpredictable, one “at least” gets a VIL-MAC. Additionally, our mode yields a VIL random oracle (and, hence, a collision-resistant hash function) when instantiated with length-preserving random functions, or even random permutations (which can be queried from both sides). This means that one does not have to re-key the block cipher during the computation, which was critically used in most previous constructions (analyzed in the ideal cipher model).

We provide attacks and analysis that capture a tradeoff, in the ideal-permutation model, between the speed of a permutation-based hash function and its potential security. We show that any 2

n

-bit to

n

-bit compression function will have unacceptable collision resistance it makes fewer than three

n

-bit permutation invocations, and any 3

n

-bit to 2

n

-bit compression function will have unacceptable security if it makes fewer than five

n

-bit permutation invocations. Any rate-

α

hash function built from

n

-bit permutations can be broken, in the sense of finding preimages as well as collisions, in about

N

1 − 

α

queries, where

N

 = 2

n

. Our results provide guidance when trying to design or analyze a permutation-based hash function about the limits of what can possibly be done.

At Crypto ’07, Fouque, Leurent and Nguyen presented full key-recovery attacks on HMAC/NMAC-MD4 and NMAC-MD5, by extending the partial key-recovery attacks of Contini and Yin from Asiacrypt ’06. Such attacks are based on collision attacks on the underlying hash function, and the most expensive stage is the recovery of the so-called outer key. In this paper, we show that the outer key can be recovered with near-collisions instead of collisions: near-collisions can be easier to find and can disclose more information. This improves the complexity of the FLN attack on HMAC/NMAC-MD4: the number of MAC queries decreases from 2

88

to 2

72

, and the number of MD4 computations decreases from 2

95

to 2

77

. We also improved the total complexity of the related-key attack on NMAC-MD5. Moreover, our attack on NMAC-MD5 can partially recover the outer key without the knowledge of the inner key, which might be of independent interest.

We analyse the hash function family based on walks in LPS Ramanujan graphs recently introduced by Charles et al. We present an algorithm for finding collisions that runs in quasi-linear time in the length of the hashed value. A concrete instance of the hash function is considered, based on a 100-digit prime. A short collision is given, together with implementation details.

We develop a new generic long-message second preimage attack, based on combining the techniques in the second preimage attacks of Dean [8] and Kelsey and Schneier [16] with the herding attack of Kelsey and Kohno [15]. We show that these generic attacks apply to hash functions using the Merkle-Damgård construction with only slightly more work than the previously known attack, but allow enormously more control of the contents of the second preimage found. Additionally, we show that our new attack applies to several hash function constructions which are not vulnerable to the previously known attack, including the dithered hash proposal of Rivest [25], Shoup’s UOWHF [26] and the ROX hash construction [2]. We analyze the properties of the dithering sequence used in [25], and develop a time-memory tradeoff which allows us to apply our second preimage attack to a wide range of dithering sequences, including sequences which are much stronger than those in Rivest’s proposals. Finally, we show that both the existing second preimage attacks [8,16] and our new attack can be applied even more efficiently to multiple target messages; in general, given a set of many target messages with a total of 2

R

message blocks, these second preimage attacks can find a second preimage for one of those target messages with no more work than would be necessary to find a second preimage for a single target message of 2

R

message blocks.

Recently, Aumann and Lindell introduced a new realistic security model for secure computation, namely, security against

covert adversaries

. The main motivation was to obtain secure computation protocols which are efficient enough to be usable in practice. Aumann and Lindell presented an efficient two party computation protocol secure against covert adversaries. They were able to utilize cut and choose techniques rather than relying on expensive zero knowledge proofs.

In this paper, we design an efficient multi-party computation protocol in the covert adversary model which remains secure even if a majority of the parties are dishonest. We also substantially improve the two-party protocol of Aumann and Lindell. Our protocols avoid general NP-reductions and only make a

black box

use of efficiently implementable cryptographic primitives. Our two-party protocol is constant-round while the multi-party one requires a logarithmic (in number of parties) number of rounds of interaction between the parties. Our protocols are secure as per the standard

simulation-based

definitions of security.

Although our main focus is on designing efficient protocols in the covert adversary model, the techniques used in our two party case directly generalize to improve the efficiency of two party computation protocols secure against standard malicious adversaries.

Secure multi-party computation (MPC) is a central problem in cryptography. Unfortunately, it is well known that MPC is possible if and only if the underlying communication network has very large connectivity — in fact,

Ω

(

t

), where

t

is the number of potential corruptions in the network. This impossibility result renders existing MPC results far less applicable in practice, since many deployed networks have in fact a very small degree.

In this paper, we show how to circumvent this impossibility result and achieve meaningful security guarantees for graphs with small degree (such as expander graphs and several other topologies). In fact, the notion we introduce, which we call

almost-everywhere MPC

, building on the notion of almost-everywhere agreement due to Dwork, Peleg, Pippenger and Upfal, allows the degree of the network to be much smaller than the total number of allowed corruptions. In essence, our definition allows the adversary to

implicitly

wiretap some of the good nodes by corrupting sufficiently many nodes in the “neighborhood” of those nodes. We show protocols that satisfy our new definition, retaining both correctness and privacy for most nodes despite small connectivity, no matter how the adversary chooses his corruptions.

Instrumental in our constructions is a new model and protocol for the

secure message transmission

(SMT) problem, which we call

SMT by public discussion

, and which we use for the establishment of pairwise secure channels in limited connectivity networks.

In the model of perfectly secure message transmission schemes (PSMTs), there are

n

channels between a sender and a receiver. An infinitely powerful adversary

may corrupt (observe and forge) the messages sent through

t

out of

n

channels. The sender wishes to send a secret

s

to the receiver perfectly privately and perfectly reliably without sharing any key with the receiver.

In this paper, we show the first 2-round PSMT for

n

 = 2

t

 + 1 such that not only the transmission rate is

O

(

n

) but also the computational costs of the sender and the receiver are both polynomial in

n

. This means that we solve the open problem raised by Agarwal, Cramer and de Haan at CRYPTO 2006.

A secure

failure-localization path-quality-monitoring

(FL- PQM) protocols allows a sender to localize faulty links on a single path through a network to a receiver, even when intermediate nodes on the path behave adversarially. Such protocols were proposed as tools that enable Internet service providers to select high-performance paths through the Internet, or to enforce contractual obligations. We give the first formal definitions of security for FL-PQM protocols and construct:

1

A simple FL-PQM protocol that can localize a faulty link

every time

a packet is not correctly delivered. This protocol’s communication overhead is

O

(1) additional messages of length

O

(

n

) per packet (where

n

is the security parameter).

1

A more efficient FL-PQM protocol that can localize a faulty link when a

noticeable fraction

of the packets sent during some time period are not correctly delivered. The number of additional messages is an arbitrarily small fraction of the total number of packets.

We also prove lower bounds for such protocols:

1

Every secure FL-PQM protocol requires

each

intermediate node on the path to have some shared secret information (

e.g.

keys).

1

If secure FL-PQM protocols exist then so do one-way functions.

1

Every

black-box

construction of a FL-PQM protocol from a random oracle that securely localizes every packet and adds at most

O

(log

n

) messages overhead per packet requires

each

intermediate node to invoke the oracle.

These results show that implementing FL-PQM requires active cooperation (

i.e.

maintaining keys and agreeing on, and performing, cryptographic protocols) from

all

of the intermediate nodes along the path. This may be problematic in the Internet, where links operate at extremely high speeds, and intermediate nodes are owned by competing business entities with little incentive to cooperate.

The innovative

protocol of Juels and Weis [10] extends device authentication to low-cost RFID tags. However, despite the very simple on-tag computation there remain some practical problems with

and despite an elegant proof of security against some limited active attacks, there is a simple man-in-the-middle attack due to Gilbert

et al.

[8]. In this paper we consider improvements to

in terms of both security and practicality. We introduce a new protocol that we denote

random

-

. This proposal avoids many practical drawbacks of

, remains provably resistant to attacks in the model of Juels and Weis, and at the same time is provably resistant to a broader class of active attacks that includes the attack of [8]. We then describe an enhanced variant called

which offers practical advantages over

.

A shuffle of a set of ciphertexts is a new set of ciphertexts with the same plaintexts in permuted order. Shuffles of homomorphic encryptions are a key component in mix-nets, which in turn are used in protocols for anonymization and voting. Since the plaintexts are encrypted it is not directly verifiable whether a shuffle is correct, and it is often necessary to prove the correctness of a shuffle using a zero-knowledge proof or argument.

In previous zero-knowledge shuffle arguments from the literature the communication complexity grows linearly with the number of ciphertexts in the shuffle. We suggest the first practical shuffle argument with sub-linear communication complexity. Our result stems from combining previous work on shuffle arguments with ideas taken from probabilistically checkable proofs.

Precise zero knowledge

introduced by Micali and Pass (STOC’06) guarantees that the view of any verifier

V

can be simulated in time closely related to the

actual

(as opposed to worst-case) time spent by

V

in the generated view. We provide the first constructions of precise concurrent zero-knowledge protocols. Our constructions have essentially optimal precision; consequently this improves also upon the previously tightest non-precise concurrent zero-knowledge protocols by Kilian and Petrank (STOC’01) and Prabhakaran, Rosen and Sahai (FOCS’02) whose simulators have a quadratic worst-case overhead. Additionally, we achieve a statistically-precise concurrent zero-knowledge property—which requires simulation of unbounded verifiers participating in an unbounded number of concurrent executions; as such we obtain the first (even non-precise) concurrent zero-knowledge protocols which handle verifiers participating in a super-polynomial number of concurrent executions.

Non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs have played a significant role in the theory of cryptography. However, lack of efficiency has prevented them from being used in practice. One of the roots of this inefficiency is that non-interactive zero-knowledge proofs have been constructed for general NP-complete languages such as Circuit Satisfiability, causing an expensive blowup in the size of the statement when reducing it to a circuit. The contribution of this paper is a general methodology for constructing very simple and efficient non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs that work directly for groups with a bilinear map, without needing a reduction to Circuit Satisfiability.

Groups with bilinear maps have enjoyed tremendous success in the field of cryptography in recent years and have been used to construct a plethora of protocols. This paper provides non-interactive witness-indistinguishable proofs and non-interactive zero-knowledge proofs that can be used in connection with these protocols. Our goal is to spread the use of non-interactive cryptographic proofs from mainly theoretical purposes to the large class of practical cryptographic protocols based on bilinear groups.

Zero Knowledge Sets, introduced by Micali, Rabin and Kilian in [17], allow a prover to commit to a secret set

S

in a way such that it can later prove, non interactively, statements of the form

x

 ∈ 

S

(or

x

 ∉ 

S

), without revealing any further information (on top of what explicitly revealed by the inclusion/exclusion statements above) on

S

, not even its size. Later, Chase

et al.

[5] abstracted away the Micali, Rabin and Kilian’s construction by introducing an elegant new variant of commitments that they called (trapdoor) mercurial commitments. Using this primitive, it was shown in [5,4] how to construct zero knowledge sets from a variety of assumptions (both general and number theoretic).

In this paper we introduce the notion of trapdoor

q

-mercurial commitments (

qTMC

s), a notion of mercurial commitment that allows the sender to commit to an

ordered

sequence of exactly

q

messages, rather than to a single one. Following [17,5] we show how to construct ZKS from

qTMC

s and collision resistant hash functions.

Then, we present an efficient realization of

qTMC

s that is secure under the so called Strong Diffie Hellman assumption, a number theoretic conjecture recently introduced by Boneh and Boyen in [3]. Using our scheme as basic building block, we obtain a construction of ZKS that allows for proofs that are much shorter with respect to the best previously known implementations. In particular, for an appropriate choice of the parameters, our proofs are up to 33% shorter for the case of proofs of membership, and up to 73% shorter for the case of proofs of non membership.

In this work we introduce a novel paradigm for the construction of ramp schemes with strong multiplication that allows the secret to be chosen in an extension field, whereas the shares lie in a base field. When applied to the setting of Shamir’s scheme, for example, this leads to a ramp scheme with strong multiplication from which protocols can be constructed for atomic secure multiplication with communication equal to a linear number of field elements in the size of the network.

This is also achieved by the results from Cramer, Damgaard and de Haan from EUROCRYPT 2007. However, our new ramp scheme has an improved privacy bound that is essentially optimal and leads to a significant mathematical simplification of the earlier results on atomic secure multiplication.

As a result, by considering high degree rational points on algebraic curves, this can now be generalized to algebraic geometric ramp schemes with strong multiplication over a constant size field, which in turn leads to low communication atomic secure multiplication where the base field can now be taken constant, as opposed to earlier work.

Consider an abstract storage device

$\Sigma(\mathcal{G})$

that can hold a single element

x

from a fixed, publicly known finite group

$\mathcal{G}$

. Storage is private in the sense that an adversary does not have read access to

$\Sigma(\mathcal{G})$

at all. However,

$\Sigma(\mathcal{G})$

is non-robust in the sense that the adversary can modify its contents by adding some offset

$\Delta \in \mathcal{G}$

. Due to the privacy of the storage device, the value

Δ

can only depend on an adversary’s

a priori

knowledge of

x

. We introduce a new primitive called an

algebraic manipulation detection

(AMD) code, which encodes a source

s

into a value

x

stored on

$\Sigma(\mathcal{G})$

so that any tampering by an adversary will be detected. We give a nearly optimal construction of AMD codes, which can flexibly accommodate arbitrary choices for the length of the source

s

and security level. We use this construction in two applications:

We show how to efficiently convert any linear secret sharing scheme into a

robust secret sharing scheme

, which ensures that no

unqualified subset

of players can modify their shares and cause the reconstruction of some value

s

′ ≠ 

s

.

We show how to build nearly optimal

robust fuzzy extractors

for several natural metrics. Robust fuzzy extractors enable one to reliably extract and later recover random keys from noisy and non-uniform secrets, such as biometrics, by relying only on

non-robust public storage

. In the past, such constructions were known only in the random oracle model, or required the entropy rate of the secret to be greater than half. Our construction relies on a randomly chosen common reference string (CRS) available to all parties.

We construct obfuscators of point functions with multibit output and other related functions. A point function with multibit output returns a fixed string on a single input point and zero everywhere else. Obfuscation of such functions has a useful application as a strong form of symmetric encryption which guarantees security even when the key has very low entropy: Essentially, learning information about the plaintext is paramount to finding the key via exhaustive search on the key space.

Although the constructions appear to be simple and modular, their analysis turns out to be quite intricate. In particular, we uncover some weaknesses in the current definitions of obfuscation. One weakness is that current definitions do not guarantee security even under very weak forms of composition. We thus define a notion of obfuscation that is preserved under an appropriate composition operation. The constructions can use any obfuscator of point functions under the proposed definition. Alternatively, they can use perfect one way (POW) functions with statistical indistinguishability, or with computational indistinguishability at the price of somewhat weaker security.

We consider proof of knowledge protocols where the cheating prover may communicate with some external adversarial environment during the run of the proof. Without additional setup assumptions, no witness hiding protocol can securely ensure that the prover knows a witness in this scenario. This is because the prover may just be forwarding messages between the environment and the verifier while the environment performs all the necessary computation.

In this paper we consider an ℓ-

isolated

prover, which is restricted to exchanging at most ℓ bits of information with its environment. We introduce a new notion called ℓ-isolated proofs of knowledge (ℓ-IPoK). These protocols securely ensure that an ℓ-isolated prover knows the witness. To prevent the above-mentioned attack, an ℓ-IPoK protocol has to have communication complexity greater than ℓ. We show that for any relation in NP and any value ℓ, there is an ℓ-IPoK protocol for that relation. In addition, the communication complexity of such a protocol only needs to be larger than ℓ by a constant multiplicative factor.

Designing secure protocols in the Universal Composability (UC) framework confers many advantages. In particular, it allows the protocols to be securely used as building blocks in more complex protocols, and assists in understanding their security properties. Unfortunately, most existing models in which universally composable computation is possible (for useful functionalities) require a trusted setup stage. Recently, Katz [Eurocrypt ’07] proposed an alternative to the trusted setup assumption: tamper-proof hardware. Instead of trusting a third party to correctly generate the setup information, each party can create its own hardware tokens, which it sends to the other parties. Each party is only required to trust that its own tokens are tamper-proof.

Katz designed a UC commitment protocol that requires both parties to generate hardware tokens. In addition, his protocol relies on a specific number-theoretic assumption. In this paper, we construct UC commitment protocols for “David” and “Goliath”: we only require a single party (Goliath) to be capable of generating tokens. We construct a version of the protocol that is secure for computationally unbounded parties, and a more efficient version that makes computational assumptions only about David (we require only the existence of a one-way function). Our protocols are simple enough to be performed by hand on David’s side.

These properties may allow such protocols to be used in situations which are inherently asymmetric in real-life, especially those involving individuals versus large organizations. Classic examples include voting protocols (voters versus “the government”) and protocols involving private medical data (patients versus insurance-agencies or hospitals).

The Universal Composability framework was introduced by Canetti to study the security of protocols which are concurrently executed with other protocols in a network environment. Unfortunately it was shown that in the so called plain model, a large class of functionalities cannot be securely realized. These severe impossibility results motivated the study of other models involving some sort of setup assumptions, where general positive results can be obtained. Until recently, all the setup assumptions which were proposed required some trusted third party (or parties).

Katz recently proposed using a

physical setup

to avoid such trusted setup assumptions. In his model, the physical setup phase includes the parties exchanging tamper proof hardware tokens implementing some functionality. The tamper proof hardware is modeled so as to assume that the receiver of the token can do nothing more than observe its input/output characteristics. It is further assumed that the sender

knows

the program code of the hardware token which it distributed. Based on the DDH assumption, Katz gave general positive results for universally composable multi-party computation tolerating any number of dishonest parties making this model quite attractive.

In this paper, we present new constructions for UC secure computation using tamper proof hardware (in a stronger model). Our results represent an improvement over the results of Katz in several directions using substantially different techniques. Interestingly, our security proofs do not rely on being able to rewind the hardware tokens created by malicious parties. This means that we are able to relax the assumptions that the parties

know

the code of the hardware token which they distributed. This allows us to model real life attacks where, for example, a party may simply pass on the token obtained from one party to the other without actually knowing its functionality. Furthermore, our construction models the interaction with the tamper-resistant hardware as a simple request-reply protocol. Thus, we show that the hardware tokens used in our construction can be

resettable

. In fact, it suffices to use token which are completely stateless (and thus cannot execute a multi-round protocol). Our protocol is also based on general assumptions (namely enhanced trapdoor permutations).