Advances in Cryptology -- CRYPTO 2015

In this paper, we present a simpler and more restricted variant of the universally composable security (UC) framework that is suitable for “standard” two-party and multiparty computation tasks. Many of the complications of the UC framework exist in order to enable more general tasks than classic secure computation. This generality may be a barrier to entry for those who are used to the stand-alone model of secure computation and wish to work with universally composable security but are overwhelmed by the differences. The variant presented here (called simplified universally composable security, or just SUC) is closer to the definition of security for multiparty computation in the stand-alone setting. The main difference is that a protocol in the SUC framework runs with a fixed set of parties, and machines cannot be added dynamically to the execution. As a result, the definitions of polynomial time and protocol composition are much simpler. In addition, the SUC framework has authenticated channels built in, as is standard in previous definitions of security, and all communication is done via the adversary in order to enable arbitrary scheduling of messages. Due to these differences, not all cryptographic tasks can be expressed in the SUC framework. Nevertheless, standard secure computation tasks (like secure function evaluation) can be expressed. Importantly, we show that for every protocol that can be represented in the SUC framework, the protocol is secure in SUC if and only if it is secure in UC. Therefore, the UC composition theorem holds and any protocol that is proven secure under SUC is secure under the general framework (with some technical changes to the functionality definition). As a result, protocols that are secure in the SUC framework are secure when an a priori unbounded number of concurrent executions of the protocols take place (relative to the same fixed set of parties).

Recently, Goyal (STOC’13) proposed a new non-black box simulation techniques for fully concurrent zero knowledge with straight-line simulation. Unfortunately, so far this technique is limited to the setting of concurrent zero knowledge. The goal of this paper is to study what can be achieved in the setting of concurrent secure computation using non-black box simulation techniques, building upon the work of Goyal. The main contribution of our work is a secure computation protocol in the fully concurrent setting with a straight-line simulator, that allows us to achieve several new results:

We give first positive results for concurrent blind signatures and verifiable random functions in the plain model

as per the ideal/real world security definition

. Our positive result is somewhat surprising in light of the impossibility result of Lindell (STOC’03) for black-box simulation. We circumvent this impossibility using non-black box simulation. This gives us a quite natural example of a functionality in concurrent setting which is impossible to realize using black-box simulation but can be securely realized using non-black box simulation.

Moreover, we expand the class of realizable functionalities in the concurrent setting. Our main theorem is a positive result for concurrent secure computation as long as the ideal world satisfies the

bounded pseudo-entropy condition

(BPC) of Goyal (FOCS’12). The BPC requires that in the ideal world experiment, the total amount of information learnt by the adversary (via calls to the ideal functionality) should have “bounded pseudoentropy”.

We also improve the round complexity of protocols in the single-input setting of Goyal (FOCS’12) both qualitatively and quantitatively. In Goyal’s work, the number of rounds depended on the length of honest party inputs. In our protocol, the round complexity depends only on the security parameter, and is completely independent of the length of the honest party inputs.

Our results are based on a non-black box simulation technique using a new language (which allows the simulator to commit to an Oracle program that can access information with bounded pseudoentropy), and a simulation-sound version of the concurrent zero-knowledge protocol of Goyal (STOC’13). We assume the existence of collision resistant hash functions and constant round semi-honest oblivious transfer.

The multiple ideal query (MIQ) model [Goyal, Jain, and Ostrovsky, Crypto’10] offers a relaxed notion of security for concurrent secure computation, where the simulator is allowed to query the ideal functionality

multiple times per session

(as opposed to just once in the standard definition). The model provides a quantitative measure for the degradation in security under concurrent self-composition, where the degradation is measured by the number of ideal queries. However, to date, all known MIQ-secure protocols guarantee only an overall

average

bound on the number of queries per session throughout the execution, thus allowing the adversary to potentially fully compromise some sessions of its choice. Furthermore, [Goyal and Jain, Eurocrypt’13] rule out protocols where the simulator makes only an adversary-independent constant number of ideal queries per session.

We show the first MIQ-secure protocol with worst-case per-session guarantee. Specifically, we show a protocol for any functionality that matches the [GJ13] bound: The simulator makes only a

constant

number of ideal queries in

every

session. The constant depends on the adversary but is independent of the security parameter.

As an immediate corollary of our main result, we obtain the first password authenticated key exchange (PAKE) protocol for the fully concurrent, multiple password setting in the standard model with no set-up assumptions.

We study the round complexity of multiparty computation with fairness and guaranteed output delivery, assuming existence of an honest majority. We demonstrate a new lower bound and a matching upper bound. Our lower bound rules out any two-round fair protocols in the standalone model, even when the parties are given access to a common reference string (CRS). The lower bound follows by a reduction to the impossibility result of virtual black box obfuscation of arbitrary circuits.

Then we demonstrate a three-round protocol with guarantee of output delivery, which in general is harder than achieving fairness (since the latter allows the adversary to force a fair abort). We develop a new construction of a threshold fully homomorphic encryption scheme, with a new property that we call “flexible” ciphertexts. Roughly, our threshold encryption scheme allows parties to adapt flexible ciphertexts to the public keys of the non-aborting parties, which provides a way of handling aborts without adding any communication.

Concurrent non-malleable zero-knowledge

(

$$\mathrm {CNMZK}$$

CNMZK

) protocols are zero-knowledge protocols that are secure even when the adversary interacts with multiple provers and verifiers simultaneously. Recently, the first

statistical

$$\mathrm {CNMZK}$$

CNMZK

argument for

$$\mathcal {NP}$$

NP

was constructed by Orlandi et al. (TCC’14) under the DDH assumption.

In this paper, we construct a statistical

$$\mathrm {CNMZK}$$

CNMZK

argument for

$$\mathcal {NP}$$

NP

assuming only the existence of one-way functions

. The security is proven via black-box simulation, and the round complexity is

$$\mathsf {poly}(n)$$

poly

(

n

)

. Under the existence of collision-resistant hash functions, the round complexity can be reduced to

$$\omega (\log n)$$

ω

(

log

n

)

, which is essentially optimal for black-box concurrent zero-knowledge.

We introduce

implicit zero-knowledge

arguments (

$$\mathsf{iZK }$$

iZK

) and simulation-sound variants thereof (

$$\mathsf{SSiZK }$$

SSiZK

); these are lightweight alternatives to zero-knowledge arguments for enforcing semi-honest behavior. Our main technical contribution is a construction of efficient two-flow

$$\mathsf{iZK }$$

iZK

and

$$\mathsf{SSiZK }$$

SSiZK

protocols for a large class of languages under the (plain)

$$\mathsf{DDH }$$

DDH

assumption in cyclic groups in the common reference string model. As an application of

$$\mathsf{iZK }$$

iZK

, we improve upon the round-efficiency of existing protocols for securely computing inner product under the

$$\mathsf{DDH }$$

DDH

assumption. This new protocol in turn provides privacy-preserving biometric authentication with lower latency.

In this work, we show how to use the positive results on succinct argument systems to prove impossibility results on leakage-resilient black-box zero knowledge. This recently proposed notion of zero knowledge deals with an adversary that can make leakage queries on the state of the prover. Our result holds for black-box simulation only and we also give some insights on the non-black-box case. Additionally, we show that, for several functionalities, leakage-resilient multi-party computation is impossible (regardless of the number of players and even if just one player is corrupted).

More in details, we achieve the above results by extending a technique of [Nielsen, Venturi, Zottarel – PKC13] to prove lower bounds for leakage-resilient security. Indeed, we use leakage queries to run an execution of a communication-efficient protocol in the head of the adversary. Moreover, to defeat the black-box simulator we connect the above technique for leakage resilience to security against reset attacks.

Our results show that the open problem of [Ananth, Goyal, Pandey – Crypto 14] (i.e., continual leakage-resilient proofs without a common reference string) has a negative answer when security through black-box simulation is desired. Moreover our results close the open problem of [Boyle et al. – STOC 12] for the case of black-box simulation (i.e., the possibility of continual leakage-resilient secure computation without a leak-free interactive preprocessing).

We describe a zero-knowledge proof system in which a prover holds a large dataset

M

and can repeatedly prove NP relations about that dataset. That is, for any (public) relation

R

and

x

, the prover can prove that

$$\exists w: R(M,x,w)=1$$

∃

w

:

R

(

M

,

x

,

w

)

=

1

. After an initial setup phase (which depends only on

M

), each proof requires only a constant number of rounds and has communication/computation cost proportional to that of a

random-access machine (RAM)

implementation of

R

, up to polylogarithmic factors. In particular, the cost per proof in many applications is sublinear in |

M

|. Additionally, the storage requirement between proofs for the verifier is constant.

Motivated by the goal of constructing efficient hash functions, we investigate the possibility of hashing a long message by only making parallel, non-adaptive calls to a hash function on short messages. Our main result is a simple construction of a collision-resistant hash function

$$h:\{0,1\}^n\rightarrow \{0,1\}^k$$

h

:

{

0

,

1

}

n

→

{

0

,

1

}

k

that makes a polynomial number of parallel calls to a

random

function

$$f:\{0,1\}^k\rightarrow \{0,1\}^k$$

f

:

{

0

,

1

}

k

→

{

0

,

1

}

k

, for any polynomial

$$n=n(k)$$

n

=

n

(

k

)

. This should be compared with the traditional use of a Merkle hash tree, that requires at least

$$\log (n/k)$$

log

(

n

/

k

)

rounds of calls to

f

, and with a more complex construction of Maurer and Tessaro [

26

] (Crypto 2007) that requires two rounds of calls to

f

. We also show that our hash function

h

satisfies a relaxed form of the notion of indifferentiability of Maurer et al. [

27

] (TCC 2004) that suffices for implementing the Fiat-Shamir paradigm. As a corollary, we get sublinear-communication non-interactive arguments for NP that only make two rounds of calls to a small random oracle.

An attractive feature of our construction is that

h

can be implemented by Boolean circuits that only contain parity gates in addition to the parallel calls to

f

. Thus, we get the first domain-extension scheme which is

degree-preserving

in the sense that the algebraic degree of

h

over the binary field is equal to that of

f

.

Our construction makes use of

list-recoverable codes

, a generalization of list-decodable codes that is closely related to the notion of randomness condensers. We show that list-recoverable codes are necessary for any construction of this type.

There is a large body of work on using noisy communication channels for realizing different cryptographic tasks. In particular, it is known that secure message transmission can be achieved unconditionally using only

one-way

communication from the sender to the receiver. In contrast, known solutions for more general secure computation tasks inherently require interaction, even when the entire input originates from the sender.

We initiate a general study of cryptographic protocols over noisy channels in a setting where only one party speaks. In this setting, we show that the landscape of what a channel is useful for is much richer. Concretely, we obtain the following results.

Relationships Between Channels.

The binary erasure channel (BEC) and the binary symmetric channel (BSC), which are known to be securely reducible to each other in the interactive setting, turn out to be qualitatively different in the setting of one-way communication. In particular, a BEC cannot be implemented from a BSC, and while the erasure probability of a BEC can be manipulated in both directions, the crossover probability of a BSC can only be manipulated in one direction.

Zero-knowledge Proofs and Secure Computation of Deterministic Functions.

One-way communication over BEC or BSC is sufficient for securely realizing any deterministic (possibly reactive) functionality which takes its inputs from a sender and delivers its outputs to a receiver. This provides the first truly non-interactive solutions to the problem of zero-knowledge proofs.

Secure Computation of Randomized Functions.

One-way communication over BEC or BSC

cannot

be used for realizing general randomized functionalities which take input from a sender and deliver output to a receiver. On the other hand, one-way communication over other natural channels, such as bursty erasure channels, can be used to realize such functionalities. This type of protocols can be used for distributing certified cryptographic keys without revealing the keys to the certification authority.

We revisit the problem of black-box constructions of universal one-way hash functions (UOWHFs) from several typical classes of one-way functions (OWFs), and give respective constructions that either improve or generalize the best previously known.

For any 1-to-1 one-way function, we give an optimal construction of UOWHFs with key and output length

$$\varTheta (n)$$

Θ

(

n

)

by making a single call to the underlying OWF. This improves the constructions of Naor and Yung (STOC 1989) and De Santis and Yung (Eurocrypt 1990) that need key length

$$O(n\cdot \omega ({\log {n})})$$

O

(

n

·

ω

(

log

n

)

)

.

For any known-(almost-)regular one-way function with known hardness, we give an optimal construction of UOWHFs with key and output length

$$\varTheta (n)$$

Θ

(

n

)

and a single call to the one-way function.

For any known-(almost-)regular one-way function, we give a construction of UOWHFs with key and output length

$$O(n{\cdot }\omega (1))$$

O

(

n

·

ω

(

1

)

)

and by making

$$\omega (1)$$

ω

(

1

)

non-adaptive calls to the one-way function. This improves the construction of Barhum and Maurer (Latincrypt 2012) that requires key and output length

$$O(n{\cdot }\omega (\log {n}))$$

O

(

n

·

ω

(

log

n

)

)

and

$$\omega (\log {n})$$

ω

(

log

n

)

calls.

For any weakly-regular one-way function introduced by Yu et al. at TCC 2015 (i.e., the set of inputs with maximal number of siblings is of an

$$n^{-c}$$

n

-

c

-fraction for some constant

c

), we give a construction of UOWHFs with key length

$$O(n{\cdot }{\log }n)$$

O

(

n

·

log

n

)

and output length

$$\varTheta (n)$$

Θ

(

n

)

. This generalizes the construction of Ames et al. (Asiacrypt 2012) which requires an unknown-regular one-way function (i.e.,

$$c=0$$

c

=

0

).

Along the way, we use several techniques that might be of independent interest. We show that almost 1-to-1 (except for a negligible fraction) one-way functions and known (almost-)regular one-way functions are equivalent in the known-hardness (or non-uniform) setting, by giving an optimal construction of the former from the latter. In addition, we show how to transform any one-way function that is far from regular (but only weakly regular on a noticeable fraction of domain) into an almost-regular one-way function.

Round-optimal blind signatures are notoriously hard to construct in the standard model, especially in the malicious-signer model, where blindness must hold under adversarially chosen keys. This is substantiated by several impossibility results. The only construction that can be termed theoretically efficient, by Garg and Gupta (

Eurocrypt

’14), requires complexity leveraging, inducing an exponential security loss.

We present a construction of practically efficient round-optimal blind signatures in the standard model. It is conceptually simple and builds on the recent structure-preserving signatures on equivalence classes (SPS-EQ) from

Asiacrypt

’14. While the traditional notion of blindness follows from standard assumptions, we prove blindness under adversarially chosen keys under an interactive variant of DDH. However, we neither require non-uniform assumptions nor complexity leveraging.

We then show how to extend our construction to partially blind signatures and to blind signatures on message vectors, which yield a construction of one-show anonymous credentials à la “anonymous credentials light” (

CCS

’13) in the standard model.

Furthermore, we give the first SPS-EQ construction under non-interactive assumptions and show how SPS-EQ schemes imply conventional structure-preserving signatures, which allows us to apply optimality results for the latter to SPS-EQ.

We introduce the notion of asymmetric programmable hash functions (APHFs, for short), which adapts Programmable Hash Functions, introduced by Hofheinz and Kiltz at Crypto 2008, with two main differences. First, an APHF works over bilinear groups, and it is asymmetric in the sense that, while only

secretly

computable, it admits an isomorphic copy which is publicly computable. Second, in addition to the usual programmability, APHFs may have an alternative property that we call

programmable pseudorandomness

. In a nutshell, this property states that it is possible to embed a pseudorandom value as part of the function’s output, akin to a random oracle. In spite of the apparent limitation of being only secretly computable, APHFs turn out to be surprisingly powerful objects. We show that they can be used to generically implement both regular and linearly-homomorphic signature schemes in a simple and elegant way. More importantly, when instantiating these generic constructions with our concrete realizations of APHFs, we obtain: (1) the

first

linearly-homomorphic signature (in the standard model) whose public key is

sub-linear

in both the dataset size and the dimension of the signed vectors; (2) short signatures (in the standard model) whose public key is shorter than those by Hofheinz-Jager-Kiltz from Asiacrypt 2011, and essentially the same as those by Yamada, Hannoka, Kunihiro, (CT-RSA 2012).

Structure-preserving signatures (SPS) are pairing-based signatures where all the messages, signatures and public keys are group elements, with numerous applications in public-key cryptography. We present new, simple and improved SPS constructions under standard assumptions via a conceptually different approach. Our constructions significantly narrow the gap between existing constructions from standard assumptions and optimal schemes in the generic group model.

Group signatures are a central cryptographic primitive which allows users to sign messages while hiding their identity within a crowd of group members. In the standard model (without the random oracle idealization), the most efficient constructions rely on the Groth-Sahai proof systems (Eurocrypt’08). The structure-preserving signatures of Abe

et al.

(Asiacrypt’12) make it possible to design group signatures based on well-established, constant-size number theoretic assumptions (a.k.a. “simple assumptions”) like the Symmetric eXternal Diffie-Hellman or Decision Linear assumptions. While much more efficient than group signatures built on general assumptions, these constructions incur a significant overhead w.r.t. constructions secure in the idealized random oracle model. Indeed, the best known solution based on simple assumptions requires 2.8 kB per signature for currently recommended parameters. Reducing this size and presenting techniques for shorter signatures are thus natural questions. In this paper, our first contribution is to significantly reduce this overhead. Namely, we obtain the first fully anonymous group signatures based on simple assumptions with signatures shorter than 2 kB at the 128-bit security level. In dynamic (resp. static) groups, our signature length drops to 1.8 kB (resp. 1 kB). This improvement is enabled by two technical tools. As a result of independent interest, we first construct a new structure-preserving signature based on simple assumptions which shortens the best previous scheme by

$$25\,\%$$

25

%

. Our second tool is a method for attaining anonymity in the strongest sense using a new CCA2-secure encryption scheme which is also a Groth-Sahai commitment.

Recently, there has been huge progress in the field of concretely efficient secure computation, even while providing security in the presence of

malicious adversaries

. This is especially the case in the two-party setting, where constant-round protocols exist that remain fast even over slow networks. However, in the multi-party setting, all concretely efficient fully-secure protocols, such as SPDZ, require many rounds of communication.

In this paper, we present an MPC protocol that is fully-secure in the presence of malicious adversaries and for any number of corrupted parties. Our construction is based on the constant-round BMR protocol of Beaver et al., and is the first fully-secure version of that protocol that makes black-box usage of the underlying primitives, and is therefore concretely efficient.

Our protocol includes an online phase that is extremely fast and mainly consists of each party locally evaluating a garbled circuit. For the offline phase we present both a generic construction (using any underlying MPC protocol), and a highly efficient instantiation based on the SPDZ protocol. Our estimates show the protocol to be considerably more efficient than previous fully-secure multi-party protocols.

In [Eurocrypt 2004] Katz and Ostrovsky establish the

exact

round complexity of secure two-party computation with respect to black-box proofs of security. They prove that 5 rounds are necessary for secure two-party protocols (4-round are sufficient if only one party receives the output) and provide a protocol that matches such lower bound. The main challenge when designing such protocol is to parallelize the proofs of consistency provided by both parties – necessary when security against malicious adversaries is considered– in 4 rounds. Toward this goal they employ specific proofs in which the statement can be unspecified till the last round but that require non-black-box access to the underlying primitives.

A rich line of work [

1

,

9

,

11

,

13

,

24

] has shown that the non-black-box use of the cryptographic primitive in secure two-party computation is not necessary by providing black-box constructions matching basically all the feasibility results that were previously demonstrated only via non-black-box protocols.

All such constructions however are far from being round optimal. The reason is that they are based on cut-and-choose mechanisms where one party can safely take an action only

after

the other party has successfully completed the cut-and-choose phase, therefore requiring additional rounds.

A natural question is whether round-optimal constructions do inherently require non-black-box access to the primitives, and whether the lower bound shown by Katz and Ostrovsky can only be matched by a non-black-box protocol.

In this work we show that round-optimality is achievable even with only black-box access to the primitives. We provide the first 4-round black-box oblivious transfer based on any enhanced trapdoor permutation. Plugging a parallel version of our oblivious transfer into the black-box non-interactive secure computation protocol of [

12

] we obtain the first round-optimal black-box two-party protocol in the plain model for any functionality.

Motivated by the goal of improving the concrete efficiency of secure multiparty computation (MPC), we revisit the question of MPC with only two rounds of interaction. We consider a minimal setting in which parties can communicate over secure point-to-point channels and where no broadcast channel or other form of setup is available.

Katz and Ostrovsky (Crypto 2004) obtained negative results for such protocols with

$$n=2$$

n

=

2

parties. Ishai et al. (Crypto 2010) showed that if only one party may be corrupted, then

$$n \ge 5$$

n

≥

5

parties can securely compute any function in this setting, with guaranteed output delivery, assuming one-way functions exist. In this work, we complement the above results by presenting positive and negative results for the cases where

$$n = 3$$

n

=

3

or

$$n = 4$$

n

=

4

and where there is a

single malicious party

.

When

$$n=3$$

n

=

3

, we show a 2-round protocol which is secure with “selective abort” against a single malicious party. The protocol makes a black-box use of a pseudorandom generator or alternatively can offer unconditional security for functionalities in

$$\mathrm {NC}^1$$

NC

1

. The concrete efficiency of this protocol is comparable to the efficiency of secure two-party computation protocols for

semi-honest

parties based on garbled circuits.

When

$$n= 4$$

n

=

4

in the setting described above, we show the following:

A

statistical VSS

protocol that has a 1-round sharing phase and 1-round reconstruction phase. This improves over the state-of-the-art result of Patra et al. (Crypto 2009) whose VSS protocol required 2 rounds in the reconstruction phase.

A 2-round statistically secure protocol for

linear functionalities

with guaranteed output delivery. This implies a 2-round 4-party fair coin tossing protocol. We complement this by a negative result, showing that there is a (nonlinear) function for which there is no 2-round statistically secure protocol.

A 2-round computationally secure protocol for

general functionalities

with guaranteed output delivery, under the assumption that injective (one-to-one) one-way functions exist.

A 2-round protocol for general functionalities with guaranteed output delivery in the

preprocessing model

, whose correlated randomness complexity is proportional to the length of the inputs. This protocol makes a black-box use of a pseudorandom generator or alternatively can offer unconditional security for functionalities in

$$\mathrm {NC}^1$$

NC

1

.

Prior to our work, the feasibility results implied by our positive results were not known to hold even in the stronger MPC model considered by Gennaro et al. (Crypto 2002), where a broadcast channel is available.

Motivated by the recent success of Bitcoin we study the question of constructing distributed cryptographic protocols in a fully peer-to-peer scenario under the assumption that the adversary has limited computing power and there is

no

trusted setup (like PKI, or an unpredictable beacon). We propose a formal model for this scenario and then we construct a broadcast protocol in it. This protocol is secure under the assumption that the honest parties have computing power that is some non-negligible fraction of computing power of the adversary (this fraction can be small, in particular it can be much less than 1 / 2), and a (rough) total bound on the computing power in the system is known.

Using our broadcast protocol we construct a protocol for simulating any trusted functionality. A simple application of the broadcast protocol is also a scheme for generating an unpredictable beacon (that can later serve, e.g., as a genesis block for a new cryptocurrency).

Under a stronger assumption that the majority of computing power is controlled by the honest parties we construct a protocol for simulating any trusted functionality with guaranteed termination (i.e. that cannot be interrupted by the adversary). This could in principle be used as a provably-secure substitute of the blockchain technology used in the cryptocurrencies.

Our main tool for verifying the computing power of the parties are the Proofs of Work (Dwork and Naor, CRYPTO 92). Our broadcast protocol is built on top of the classical protocol of Dolev and Strong (SIAM J. on Comp. 1983).

We reconsider the concept of two-prover (and more generally: multi-prover) commitments, as introduced in the late eighties in the seminal work by Ben-Or

et al

. As was recently shown by Crépeau

et al

., the security of known two-prover commitment schemes not only relies on the explicit assumption that the two provers cannot communicate, but also depends on what their information processing capabilities are. For instance, there exist schemes that are secure against classical provers but insecure if the provers have

quantum

information processing capabilities, and there are schemes that resist such quantum attacks but become insecure when considering general so-called

non-signaling

provers, which are restricted

solely

by the requirement that no communication takes place.

This poses the natural question whether there exists a two-prover commitment scheme that is secure under the

sole

assumption that no communication takes place, and that does not rely on any further restriction of the information processing capabilities of the dishonest provers; no such scheme is known.

In this work, we give strong evidence for a negative answer: we show that any single-round two-prover commitment scheme can be broken by a non-signaling attack. Our negative result is as bad as it can get: for any candidate scheme that is (almost) perfectly hiding, there exists a strategy that allows the dishonest provers to open a commitment to an arbitrary bit (almost) as successfully as the honest provers can open an honestly prepared commitment, i.e., with probability (almost) 1 in case of a perfectly sound scheme. In the case of multi-round schemes, our impossibility result is restricted to perfectly hiding schemes.

On the positive side, we show that the impossibility result can be circumvented by considering

three

provers instead: there exists a three-prover commitment scheme that is secure against arbitrary non-signaling attacks.

An interactive proof of proximity (

$$\mathsf{{IPP}}$$

) is an interactive protocol in which a prover tries to convince a

sublinear-time

verifier that

$$x \in \mathcal {L}$$

. Since the verifier runs in sublinear-time, following the property testing literature, the verifier is only required to reject inputs that are

far

from

$$\mathcal {L}$$

. In a recent work, Rothblum

et. al

(STOC, 2013) constructed an

$$\mathsf{{IPP}}$$

for every language computable by a low depth circuit.

In this work, we study the computational analogue, where soundness is required to hold only against a

computationally bounded

cheating prover. We call such protocols

interactive arguments of proximity

.

Assuming the existence of a sub-exponentially secure

$$\mathsf{{FHE}}$$

scheme, we construct a

one-round

argument of proximity for

every language

computable in time

t

, where the running time of the verifier is

$$o(n) + \mathsf{polylog}(t)$$

and the running time of the prover is

$$\mathsf{poly}(t)$$

.

As our second result, assuming sufficiently hard cryptographic

$$\mathsf{PRG }$$

s, we give a lower bound, showing that the parameters obtained both in the

$$\mathsf{{IPP}}$$

s of Rothblum

et al.

, and in our arguments of proximity, are close to optimal.

Finally, we observe that any one-round argument of proximity immediately yields a one-round delegation scheme (without proximity) where the verifier runs in

linear

time.

In this paper we consider the problem of extracting secret key from an eavesdropped source

$$p_{XYZ}$$

p

X

Y

Z

at a rate given by the conditional mutual information. We investigate this question under three different scenarios: (i) Alice (

X

) and Bob (

Y

) are unable to communicate but share common randomness with the eavesdropper Eve (

Z

), (ii) Alice and Bob are allowed one-way public communication, and (iii) Alice and Bob are allowed two-way public communication. Distributions having a key rate of the conditional mutual information are precisely those in which a “helping” Eve offers Alice and Bob no greater advantage for obtaining secret key than a fully adversarial one. For each of the above scenarios, strong necessary conditions are derived on the structure of distributions attaining a secret key rate of

I

(

X

:

Y

|

Z

). In obtaining our results, we completely solve the problem of secret key distillation under scenario (i) and identify

H

(

S

|

Z

) to be the optimal key rate using shared randomness, where

S

is the Gács-Körner Common Information. We thus provide an operational interpretation of the conditional Gács-Körner Common Information. Additionally, we introduce simple example distributions in which the rate

I

(

X

:

Y

|

Z

) is achievable if and only if two-way communication is allowed.

We revisit the impossibility of a variety of cryptographic tasks including privacy and differential privacy with imperfect randomness. For traditional notions of privacy, such as security of encryption, commitment or secret sharing schemes, dramatic impossibility results are known [

MP90

,

DOPS04

] for several concrete sources

$$\mathcal {R}$$

R

, including a (seemingly) very “nice and friendly” Santha-Vazirani (SV) source. Somewhat surprisingly, Dodis et al. [

DLMV12

] showed that non-trivial

differential

privacy is possible with the SV sources. This suggested a qualitative gap between traditional and differential privacy, and left open the question of whether differential privacy is possible with more realistic (i.e., less structured) sources than the SV sources.

Motivated by this question, we introduce a new, modular framework for showing strong impossibility results for (both traditional and differential) privacy under a

general

imperfect source

$$\mathcal {R}$$

R

. As direct corollaries of our framework, we get the following new results:

(1)

Existing, but

quantitatively improved

, impossibility results for traditional privacy, but under a wider variety of sources

$$\mathcal {R}$$

R

.

(2)

First impossibility results for

differential

privacy for a variety of realistic sources

$$\mathcal {R}$$

R

(including most “block sources”, but not the SV source).

(3)

Any imperfect source allowing (either traditional or differential) privacy under

$$\mathcal {R}$$

R

admits a certain type of deterministic bit extraction from

$$\mathcal {R}$$

R

.

We initiate a systematic treatment of the communication complexity of conditional disclosure of secrets (CDS), where two parties want to disclose a secret to a third party if and only if their respective inputs satisfy some predicate. We present a general upper bound and the first non-trivial lower bounds for conditional disclosure of secrets. Moreover, we achieve tight lower bounds for many interesting setting of parameters for CDS with linear reconstruction, the latter being a requirement in the application to attribute-based encryption. In particular, our lower bounds explain the trade-off between ciphertext and secret key sizes of several existing attribute-based encryption schemes based on the dual system methodology.

In predicate encryption, a ciphertext is associated with descriptive attribute values

x

in addition to a plaintext

$$\mu $$

μ

, and a secret key is associated with a predicate

f

. Decryption returns plaintext

$$\mu $$

μ

if and only if

$$f(x) = 1$$

f

(

x

)

=

1

. Moreover, security of predicate encryption guarantees that an adversary learns nothing about the attribute

x

or the plaintext

$$\mu $$

μ

from a ciphertext, given arbitrary many secret keys that are not authorized to decrypt the ciphertext individually.

We construct a leveled predicate encryption scheme for all circuits, assuming the hardness of the subexponential learning with errors (LWE) problem. That is, for any polynomial function

$$d = d(\lambda )$$

d

=

d

(

λ

)

, we construct a predicate encryption scheme for the class of all circuits with depth bounded by

$$d(\lambda )$$

d

(

λ

)

, where

$$\lambda $$

λ

is the security parameter.

We develop a technique inspired by pseudorandom functions that allows us to increase the entropy available for proving the security of dual system encryption schemes under the Decisional Linear Assumption. We show an application of the tool to Attribute-Based Encryption by presenting a Key-Policy ABE scheme that is fully-secure under DLIN with short public parameters.

The common approach to defining secure channels in the literature is to consider transportation of discrete messages provided via atomic encryption and decryption interfaces. This, however, ignores that many practical protocols (including TLS, SSH, and QUIC) offer streaming interfaces instead, moreover with the complexity that the network (possibly under adversarial control) may deliver arbitrary fragments of ciphertexts to the receiver. To address this deficiency, we initiate the study of stream-based channels and their security. We present notions of confidentiality and integrity for such channels, akin to the notions for atomic channels, but taking the peculiarities of streams into account. We provide a composition result for our setting, saying that combining chosen-plaintext confidentiality with integrity of the transmitted ciphertext stream lifts confidentiality of the channel to chosen-ciphertext security. Notably, for our proof of this theorem in the streaming setting we need an additional property, called error predictability. We finally give an AEAD-based construction that achieves our notion of a secure stream-based channel. The construction matches rather well the one used in TLS, providing validation of that protocol’s design.

Many efficient data structures use randomness, allowing them to improve upon deterministic ones. Usually, their efficiency and/or correctness are analyzed using probabilistic tools under the assumption that the inputs and queries are

independent

of the internal randomness of the data structure. In this work, we consider data structures in a more robust model, which we call the

adversarial model

. Roughly speaking, this model allows an adversary to choose inputs and queries

adaptively

according to previous responses. Specifically, we consider a data structure known as “Bloom filter” and prove a tight connection between Bloom filters in this model and cryptography.

A Bloom filter represents a set

S

of elements approximately, by using fewer bits than a precise representation. The price for succinctness is allowing some errors: for any

$$x \in S$$

x

∈

S

it should always answer ‘Yes’, and for any

$$x \notin S$$

x

∉

S

it should answer ‘Yes’ only with small probability.

In the adversarial model, we consider both efficient adversaries (that run in polynomial time) and computationally unbounded adversaries that are only bounded in the amount of queries they can make. For computationally bounded adversaries, we show that non-trivial (memory-wise) Bloom filters exist if and only if one-way functions exist. For unbounded adversaries we show that there exists a Bloom filter for sets of size

n

and error

$$\varepsilon $$

ε

, that is secure against

t

queries and uses only

$$O(n \log {\frac{1}{\varepsilon }}+t)$$

O

(

n

log

1

ε

+

t

)

bits of memory. In comparison,

$$n\log {\frac{1}{\varepsilon }}$$

n

log

1

ε

is the best possible under a non-adaptive adversary.

Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto’92) as protection to a shared resource. The basic idea is to ask the service requestor to dedicate some non-trivial amount of computational work to every request. The original applications included prevention of spam and protection against denial of service attacks. More recently, PoWs have been used to prevent double spending in the Bitcoin digital currency system.

In this work, we put forward an alternative concept for PoWs – so-called

proofs of space

(PoS), where a service requestor must dedicate a significant amount of disk space as opposed to computation. We construct secure PoS schemes in the random oracle model (with one additional mild assumption required for the proof to go through), using graphs with high “pebbling complexity” and Merkle hash-trees. We discuss some applications, including follow-up work where a decentralized digital currency scheme called Spacecoin is constructed that uses PoS (instead of wasteful PoW like in Bitcoin) to prevent double spending.

The main technical contribution of this work is the construction of (directed, loop-free) graphs on

N

vertices with in-degree

$$O(\log \log N)$$

O

(

log

log

N

)

such that even if one places

$$\varTheta (N)$$

Θ

(

N

)

pebbles on the nodes of the graph, there’s a constant fraction of nodes that needs

$$\varTheta (N)$$

Θ

(

N

)

steps to be pebbled (where in every step one can put a pebble on a node if all its parents have a pebble).

Fully homomorphic encryption is an encryption method with the property that any computation on the plaintext can be performed by a party having access to the ciphertext only. Here, we formally define and give schemes for

quantum

homomorphic encryption, which is the encryption of

quantum

information such that

quantum

computations can be performed given the ciphertext only. Our schemes allow for arbitrary Clifford group gates, but become inefficient for circuits with large complexity, measured in terms of the non-Clifford portion of the circuit (we use the “

$$\pi /8$$

π

/

8

” non-Clifford group gate, also known as the

$$\mathsf{T}$$

T

-gate).

More specifically, two schemes are proposed: the first scheme has a decryption procedure whose complexity scales with the square of the

number

of

$$\mathsf{T}$$

T

-gates (compared with a trivial scheme in which the complexity scales with the total number of gates); the second scheme uses a quantum evaluation key of length given by a polynomial of degree exponential in the circuit’s

$$\mathsf{T}$$

T

-gate depth, yielding a homomorphic scheme for quantum circuits with constant

$$\mathsf{T}$$

T

-depth. Both schemes build on a classical fully homomorphic encryption scheme.

A further contribution of ours is to formally define the security of encryption schemes for quantum messages: we define

quantum indistinguishability under chosen plaintext attacks

in both the public- and private-key settings. In this context, we show the equivalence of several definitions. Our schemes are the first of their kind that are secure under modern cryptographic definitions, and can be seen as a quantum analogue of classical results establishing homomorphic encryption for circuits with a limited number of

multiplication

gates. Historically, such results appeared as precursors to the breakthrough result establishing classical fully homomorphic encryption.

Gentry, Sahai and Waters recently presented the first (leveled) identity-based fully homomorphic (IBFHE) encryption scheme (CRYPTO 2013). Their scheme however only works in the single-identity setting; that is, homomorphic evaluation can only be performed on ciphertexts created with the same identity. In this work, we extend their results to the multi-identity setting and obtain a multi-identity IBFHE scheme that is selectively secure in the random oracle model under the hardness of Learning with Errors (LWE). We also obtain a multi-key fully-homomorphic encryption (FHE) scheme that is secure under LWE in the standard model. This is the first multi-key FHE based on a well-established assumption such as standard LWE. The multi-key FHE of López-Alt, Tromer and Vaikuntanathan (STOC 2012) relied on a non-standard assumption, referred to as the Decisional Small Polynomial Ratio assumption.

In a functional encryption (FE) scheme, the owner of the secret key can generate restricted decryption keys that allow users to learn specific functions of the encrypted messages and nothing else. In many known constructions of FE schemes, security is guaranteed only for messages that are fixed ahead of time (i.e., before the adversary even interacts with the system). This so-called

selective security

is too restrictive for many realistic applications. Achieving

adaptive security

(also called

full security

), where security is guaranteed even for messages that are adaptively chosen at any point in time, seems significantly more challenging. The handful of known adaptively-secure schemes are based on specifically tailored techniques that rely on strong assumptions (such as obfuscation or multilinear maps assumptions).

We show that any sufficiently-expressive

selectively-secure

FE scheme can be transformed into an

adaptively-secure

one without introducing any additional assumptions. We present a black-box transformation, for both public-key and private-key schemes, making novel use of

hybrid encryption

, a classical technique that was originally introduced for improving the efficiency of encryption schemes. We adapt the hybrid encryption approach to the setting of functional encryption via a technique for embedding a “hidden execution thread” in the decryption keys of the underlying scheme, which will only be activated within the proof of security of the resulting scheme. As an additional application of this technique, we show how to construct functional encryption schemes for arbitrary circuits starting from ones for shallow circuits (NC1 or even TC0).

We propose the first construction for achieving adaptively secure functional encryption (FE) for poly-sized circuits (without complexity leveraging) from indistinguishability obfuscation (

$$i\mathcal {O}$$

i

O

). Our reduction has polynomial loss to the underlying primitives. We develop a “punctured programming” approach to constructing and proving systems where outside of obfuscation we rely only on primitives realizable from pseudo random generators.

Our work consists of two constructions. Our first FE construction is provably secure against any attacker that is limited to making all of its private key queries

after

it sees the challenge ciphertext. (This notion implies selective security.) Our construction makes use of an we introduce called puncturable deterministic encryption (PDE) which may be of independent interest. With this primitive in place we show a simple FE construction.

We then provide a second construction that achieves adaptive security from indistinguishability obfuscation. Our central idea is to achieve an adaptively secure functional encryption by bootstrapping from a one-bounded FE scheme that is adaptively secure. By using bootstrapping we can use “selective-ish” techniques at the outer level obfuscation level and push down the challenge of dealing with adaptive security to the one-bounded FE scheme, where it has been already been solved. We combine our bootstrapping framework with a new “key signaling” technique to achieve our construction and proof. Altogether, we achieve the first construction and proof for adaptive security for functional encryption.

Correlated secret randomness is an essential resource for information-theoretic cryptography. In the context of secure two-party computation, the high level of efficiency achieved by information-theoretic protocols has motivated a paradigm of starting with correlated randomness, specifically random oblivious transfer (OT) correlations. This correlated randomness can be generated and stored during an offline preprocessing phase, long before the inputs are known. But what if some information about the correlated randomness is leaked to an adversary or to the other party? Can we still recover “fresh” correlated randomness after such leakage has occurred?

This question is a direct analog of the classical question of privacy amplification, which addresses the case of a

shared

random secret key, in the setting of

correlated

random secrets. Remarkably, despite decades of study of OT-based secure computation, very little is known about this question. In particular, the question of how much leakage is tolerable when recovering OT correlations has remained wide open. In our work, we resolve this question.

Prior to our work, the work of Ishai, Kushilevitz, Ostrovsky, and Sahai (FOCS 2009) obtained an initial feasibility result, tolerating only a tiny constant leakage rate. In our work, we show that starting with

n

random OT correlations, where each party holds 2

n

bits, up to

$$(1-\epsilon )\frac{n}{2}$$

(

1

-

ϵ

)

n

2

bits of leakage are tolerable. This result is optimal, by known negative results on OT combiners.

We then ask the same question for other correlations: is there a correlation that is more leakage-resilient than OT correlations, and also supports secure computation? We answer in the affirmative, by showing that there exists a correlation that can tolerate up to

$$1/2-\epsilon $$

1

/

2

-

ϵ

fractional leakage, for any

$$\epsilon >0$$

ϵ

>

0

(compared to the optimal 1/4 fractional leakage for OT correlations).

A central problem in cryptography is that of converting protocols that offer security against passive (or semi-honest) adversaries into ones that offer security against active (or malicious) adversaries. This problem has been the topic of a large body of work in the area of secure multiparty computation (MPC). Despite these efforts, there are still big efficiency gaps between the best protocols in these two settings. In two recent works, Genkin et al. (STOC 2014) and Ikarashi et al. (ePrint 2014) suggested the following new paradigm for efficiently transforming passive-secure MPC protocols into active-secure ones. They start by observing that in several natural information-theoretic MPC protocols, an arbitrary active attack on the protocol can be perfectly simulated in an ideal model that allows for

additive

attacks on the arithmetic circuit being evaluated. That is, the simulator is allowed to (blindly) modify the original circuit by adding an arbitrary field element to each wire. To protect against such attacks, the original circuit is replaced by a so-called

AMD circuit

, which can offer protection against such attacks with constant multiplicative overhead to the size.

Our motivating observation is that in the most efficient known information-theoretic MPC protocols, which are based on packed secret sharing, it is

not

the case that general attacks reduce to additive attacks. Instead, the corresponding ideal attack can include limited forms of linear combinations of wire values. We extend the AMD circuit methodology to so-called

secure SIMD circuits,

which offer protection against this more general class of attacks.

We apply secure SIMD circuits to obtain several asymptotic and concrete efficiency improvements over the current state of the art. In particular, we improve the additive per-layer overhead of the current best protocols from

$$O(n^2)$$

to

O

(

n

), where

n

is the number of parties, and obtain the first protocols based on packed secret sharing that “natively” achieve near-optimal security without incurring the high concrete cost of Bracha’s committee-based security amplification method.

Our analysis is based on a new modular framework for proving reductions from general attacks to algebraic attacks. This framework allows us to reprove previous results in a conceptually simpler and more unified way, as well as obtain our new results.

We present the first efficient (i.e., polylogarithmic overhead) method for securely and privately processing large data sets over multiple parties with

parallel, distributed algorithms

. More specifically, we demonstrate load-balanced, statistically secure computation protocols for computing Parallel RAM (PRAM) programs, handling

$$(1/3 - \epsilon )$$

(

1

/

3

-

ϵ

)

fraction malicious players, while preserving up to polylogarithmic factors the computation, parallel time, and memory complexities of the PRAM program, aside from a one-time execution of a broadcast protocol per party. Additionally, our protocol has

$$\mathsf{polylog}$$

polylog

communication locality—that is, each of the

n

parties speaks only with

$$\mathsf{polylog}(n)$$

polylog

(

n

)

other parties.

Composable notions of incoercibility aim to forbid a coercer from using anything beyond the coerced parties’ inputs and outputs to catch them when they try to deceive him. Existing definitions are restricted to weak coercion types, and/or are not universally composable. Furthermore, they often make too strong assumptions on the knowledge of coerced parties—e.g., they assume they known the identities and/or the strategies of other coerced parties, or those of corrupted parties—which makes them unsuitable for applications of incoercibility such as e-voting, where colluding adversarial parties may attempt to coerce honest voters, e.g., by offering them money for a promised vote, and use their own view to check that the voter keeps his end of the bargain.

In this work we put forward the first universally composable notion of incoercible multi-party computation, which satisfies the above intuition and does not assume collusions among coerced parties or knowledge of the corrupted set. We define natural notions of UC incoercibility corresponding to standard coercion-types, i.e., receipt-freeness and resistance to full-active coercion. Importantly, our suggested notion has the unique property that it builds

on top

of the well studied UC framework by Canetti instead of modifying it. This guarantees backwards compatibility, and allows us to inherit results from the rich UC literature.

We then present MPC protocols which realize our notions of UC incoercibility given access to an arguably minimal setup—namely honestly generate tamper-proof hardware performing a very simple cryptographic operation—e.g., a smart card. This is, to our knowledge, the first proposed construction of an MPC protocol (for more than two parties) that is incoercibly secure

and

universally composable, and therefore the first construction of a universally composable receipt-free e-voting protocol.