April 27-29, 2018

Hacienda Forest View Hotel

Ma'alot-Tarshiha, Israel

Please access the desktop version of this page for the abstracts

## Eli Ben-Sasson (Technion)

## Scalable, Transparent and Post-Quantum Secure Computational Integrity

In this talk we shall discuss some of the main ideas and challenges that surround the construction and code-realization of zero knowledge proof/argument systems that are (i) universal (apply to any language L in NEXP), (ii) transparent (public randomness), (iii) doubly scalable (quasilinear proving time *and* poly-logarithmic verification time) and "post-quantum secure" (their security is not known to be compromised by quantum computers).

Joint work with Iddo Bentov, Yinon Horesh and Michael Riabzev.

Please access the desktop version of this page for the abstracts

## Jens Groth (University College London)

## Linear-Time Zero-Knowledge Proofs for Arithmetic Circuit Satisfiability

We give computationally efficient zero-knowledge proofs of knowledge for arithmetic circuit satisfiability over a large field where the prover only has constant overhead compared to direct verification of the witness. More precisely, for a circuit with N addition and multiplication gates, the prover uses O(N) multiplications and the verifier uses O(N) additions in the field. If the commitments we use are statistically binding, our zero-knowledge proofs have unconditional soundness, while if the commitments are statistically hiding we get computational soundness. Our zero-knowledge proofs also have sub-linear communication if the commitment scheme is compact.

Our construction proceeds in three steps. First, we give a zero-knowledge proof for arithmetic circuit satisfiability in an ideal linear commitment model where the prover may commit to secret vectors of field elements, and the verifier can receive certified linear combinations of those vectors. Second, we show that the ideal linear commitment proof can be instantiated using error-correcting codes and non-interactive commitments. Finally, by choosing efficient instantiations of the commitments using e.g. linear-time computable collision-resistant hash functions to get statistically hiding commitments we obtain linear-time zero-knowledge proofs.We give computationally efficient zero-knowledge proofs of knowledge for arithmetic circuit satisfiability over a large field where the prover only has constant overhead compared to direct verification of the witness. More precisely, for a circuit with N addition and multiplication gates, the prover uses O(N) multiplications and the verifier uses O(N) additions in the field. If the commitments we use are statistically binding, our zero-knowledge proofs have unconditional soundness, while if the commitments are statistically hiding we get computational soundness. Our zero-knowledge proofs also have sub-linear communication if the commitment scheme is compact.

Our construction proceeds in three steps. First, we give a zero-knowledge proof for arithmetic circuit satisfiability in an ideal linear commitment model where the prover may commit to secret vectors of field elements, and the verifier can receive certified linear combinations of those vectors. Second, we show that the ideal linear commitment proof can be instantiated using error-correcting codes and non-interactive commitments. Finally, by choosing efficient instantiations of the commitments using e.g. linear-time computable collision-resistant hash functions to get statistically hiding commitments we obtain linear-time zero-knowledge proofs.

## Yevgeniy Dodis (NYU)

## Small-Box Cryptography and the Provable Security of SPNs

One of the ultimate goals of symmetric-key cryptography is to find rigorous theoretical framework for building block ciphers from small components, such as cryptographic S-boxes, and then argue why iterating such small components for sufficiently many rounds would yield a secure construction. Unfortunately, a fundamental obstacle towards reaching this goal comes from the fact that traditional security proofs cannot get security beyond than 2^{-n}, where n is the size of the corresponding component.

As a result, prior provably secure approaches --- which we call "big-box cryptography" --- always made n larger than the security parameter, which led to several problems: (a) the design was too coarse to really explain practical constructions, as (arguably) the most interesting design choices happening when instantiating such "big-box" were completely abstracted out; (b) the theoretically-predicted number of rounds for the security of this approach was always dramatically smaller than in reality, where the "big-box" building block could not be made as ideal as required by the proof. For example, Even-Mansour (and, more generally, key-alternating) ciphers completely ignored

the *substitution-permutation network* (SPN) paradigm which is the heart of most real-world implementations of such ciphers.

In this work introduce a novel paradigm for justifying the security of existing block ciphers, which we call *small-box cryptography*. Unlike the "big-box" paradigm, it allows one to go much deeper inside the existing block cipher constructions, by only idealizing a small (and, hence, realistic!) building block of very small size n, such as an 8-to-32-bit S-box. It then introduces a clean and rigorous mixture of proofs and hardness conjectures which allow one to lift traditional, and seemingly meaningless, "at most 2^{-n}" security proofs for *reduced-round* idealized variants of the existing block ciphers, into meaningful, *full-round* security justifications of the actual ciphers used in the real world.

We then apply our framework to the design of popular SPN-based ciphers, which include AES, Serpent, and PRESENT, among others. In particular, it allows us to reduce practical security of such SPN ciphers to a clean theoretical question of independent interest: security of SPN networks in the random permutations model, where the latter models a small cryptographic S-box --- the only source of hardness that we assume. As our main technical contribution, we then give nearly complete characterization for the security of SPN ciphers in the random permutation model: we show that 3 rounds of S-boxes are necessary and sufficient for secure *linear* SPNs, but that even 1-round SPNs can be secure when non-linearity is allowed.

To the best of our knowledge, our results give the most accurate and plausible theoretical justification for the security of SPN ciphers to date.

## Moni Naor (Weizmann Institute)

## White-Box vs. Black-Box Search Problems: A Cryptographic Perspective

Ramsey theory assures us that in any graph there is a clique or independent set of a certain size, roughly logarithmic in the graph size. But how diﬃcult is it to ﬁnd the clique or independent set? If the graph is given explicitly, then it is possible to do so while examining a linear number of edges. If the graph is given by a black-box, where to ﬁgure out whether a certain edge exists the box should be queried, then a large number of queries must be issued. But what if one is given a program or circuit for computing the existence of an edge? What if we are assured that the program is small without being given explicitly?

In this talk I will explore recent work on the complexity of search problems with guaranteed solution (the class TFNP) and the tight relationship with cryptographic assumptions and techniques.

Based on joint works with Pavel Hubacek, Ilan Komargodski and Eylon Yogev.

## Shai Halevi (IBM Research)

## Best Possible Information-Theoretic MPC

We reconsider the security guarantee that can be achieved by general secure computation protocols in the most basic of settings: information-theoretic security against static, semi-honest adversary. Solved since the 80's, in this work we nonetheless revisit this question, putting forward a new notion of security which is strictly stronger than the standard one, and which we argue to be "best possible". For several interesting families of functions, we exhibit information-theoretic protocols that are secure against dishonest minority in the usual sense, but still offer a meaningful security when the adversary corrupts a majority of players.

We articulate the notion of security that can be achieved in this setting, characterizing the information that must be leaked to a dishonest majority, and showing that our protocols do not leak anything more, hence they are the best possible in this setting.

Joint work with Yuval Ishai, Eyal Kushilevitz, and Tal Rabin.

## Eike Kiltz (Ruhr-Universität Bochum)

## Memory-Tight Reductions

Cryptographic reductions typically aim to be tight by transforming an adversary A into an

algorithm that uses essentially the same resources as A. In this talk we consider memory

efficiency in reductions. We argue that the amount of working memory used (relative to the initial

adversary) is a relevant parameter in reductions, and that reductions that are inefficient with memory will sometimes yield less meaningful security guarantees. We then discuss several common techniques in reductions that are memory-inefficient and give a toolbox for reducing memory usage. We review common cryptographic assumptions and their sensitivity to memory usage. Finally, we show an impossibility result showing that reductions between some assumptions must unavoidably be either memory- or time-inefficient.

## Nikolaos Makriyannis (TAU)

Tighter Bounds on Multi-Party Coin Flipping, via Augmented Weak Martingales and Differentially Private Sampling

In his seminal work, Cleve [STOC 1986] has proved that any r-round coin-flipping protocol can be efficiently biassed by Ω(1/r). The above lower bound was met for the two-party case by Moran, Naor, and Segev [Journal of Cryptology '16], and the three-party case (up to a polylog factor) by Haitner and Tsfadia [SICOMP '17], and was approached for n-party protocols when n < loglog(r) by Buchbinder, Haitner, Levi, and Tsfadia [SODA '17]. For n > loglog(r), however, the best bias for n-party coin-flipping protocols remains Θ(n/√r) achieved by the majority protocol of Awerbuch, Blum, Chor, Goldwasser, and Micali [Manuscript '85].

Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, for every constant ε > 0, an r^ε-party r-round coin-flipping protocol can be efficiently biased by Ω(1/√r). As far as we know, this is the first improvement of Cleve's bound that holds in the standard model, and is only r^ε (multiplicative) far from the aforementioned upper bound of Awerbuch et al.

For proving the above lower bound, we present two new results that we believe are of independent interest. The first result is that a sequence of (augmented) weak martingales have large gap: with constant probability there exists two adjacent variables whose gap is at least the ratio between the gap between the first and last variables and the square root of the number of variables. This generalizes the result of Cleve and Impagliazzo [Manuscript '93], who proved that the above holds for strong martingales. The second result is a new sampling algorithm that uses a differentially private mechanism to minimize the effect of data divergence.

The paper is available here.

Join work with Amos Beimel, Iftach Haitner and Eran Omri.