When: Friday, December 15 at Northeastern.

Where:  Northeastern University, ISEC Building (805 Columbus Ave).
Talks in room 136. Coffee + Lunch in room 655.

Attendance is free, as usual, but please register by filling in this rather short google form: https://goo.gl/forms/PkOmXELG8xPqwG812

Organizers: Ran Canetti, Yael Kalai, Ron Rothblum, Vinod Vaikuntanathan and Daniel Wichs.

Thanks: NSF MACS Project for their generous support.

### Program:

 9:30 – 10:00. Coffee/Welcome (Room 655) 10:00 – 11:00. Guy Rothblum, Weizmann: Calibration for The  Masses 11:15 – 12:15. Ilan  Komargodski, Cornell Tech: How to Share a Secret: infinitely, dynamically and robustly 12:15 – 1:30. Lunch (Room 655) 1:30 – 2:30. Fabrice Benhamouda, IBM: k-Round MPC from k-Round OT via Garbled Interactive Circuits 2:45 – 3:45. Adam Smith, BU: Learning with Fully Distributed Private Protocols

### Abstracts:

Speaker: Guy Rothblum, Weizmann Institute of Science
Title: Calibration for The  Masses

Abstract:  As algorithms increasingly inform and influence decisions made about individuals, it becomes increasingly important to address concerns that these algorithms might be discriminatory. The output of an algorithm can be discriminatory for many reasons, most notably: (1) the data used to train the algorithm might be biased (in various ways) to favor certain populations over others; (2) the analysis of this training data might inadvertently or maliciously introduce biases that are not borne out in the data. This work focuses on the latter concern.

We develop and study multicalibration — a new measure of algorithmic fairness that aims to mitigate concerns about discrimination that is introduced in the process of learning a predictor from data. Multicalibration guarantees accurate (calibrated) predictions for every subpopulation that can be identified within a specified class of computations. We think of the class as being quite rich; in particular, it can contain many overlapping subgroups of a protected group.

We show that in many settings this strong notion of protection from discrimination is both attainable and aligned with the goal of obtaining accurate predictions. Along the way, we present new algorithms for learning a multicalibrated predictor, study the computational complexity of this task, and draw connections to the theory of agnostic learning.

Based on joint work with Úrsula Hébert-Johnson, Michael P. Kim and Omer Reingold.

Speaker: Ilan  Komargodski, Cornell Tech
Title: How to Share a Secret: infinitely, dynamically and robustly.

Abstract:  Secret sharing schemes allow a dealer to distribute a secret piece of information among several parties such that only qualified subsets of parties can reconstruct the secret. The collection of qualified subsets is called an access structure. The best known example is the k-threshold access structure, where the qualified subsets are those of size at least k. When k=2 and there are n parties, there are schemes where the size of the share each party gets is roughly log(n) bits, and this is tight even for secrets of 1 bit. In these schemes, the number of parties n must be given in advance to the dealer.
We consider the case where the set of parties is not known in advance and could potentially be infinite. Our goal is to give the t-th party arriving a small share as possible as a function of t. We present a scheme for general access structures and several schemes for variants of the k-threshold access structure in which at any point in time some bounded number of parties can recover the secret. Lastly, we discuss other classical notions such as robustness, and adapt them to the unbounded setting.

Speaker: Fabrice Benhamouda, IBM
Title: k-Round MPC from k-Round OT via Garbled Interactive Circuits

Abstract:  We present new constructions of round-efficient, or even round-optimal, Multi-Party Computation (MPC) protocols from Oblivious Transfer (OT) protocols. Our constructions establish a tight connection between MPC and OT: In the setting of semi-honest security, for any $k \ge 2$, $k$-round semi-honest OT is necessary and complete for $k$-round semi-honest MPC. In the round-optimal case of $k = 2$, we obtain 2-round semi-honest MPC from 2-round semi-honest OT, resolving the round complexity of semi-honest MPC assuming weak and necessary assumption. In comparison, previous 2-round constructions rely on either the heavy machinery of indistinguishability obfuscation or witness encryption, or the algebraic structure of bilinear pairing groups. More generally, for an arbitrary number of rounds $k$, all previous constructions of $k$-round semi-honest MPC require at least OT with $k’$ rounds for $k’ \le \lfloor k/2 \rfloor$.
In the setting of malicious security, we show: For any $k \ge 5$, $k$-round malicious OT is necessary and complete for $k$-round malicious MPC. In fact, OT satisfying a weaker notion of delayed-semi-malicious security suffices. In the common reference string model, for any $k \ge 2$, we obtain $k$-round malicious Universal Composable (UC) protocols from any $k$-round semi-malicious OT and non-interactive zero-knowledge. Previous 5-round protocols in the plain model, and 2-round protocols in the common reference string model all require algebraic assumptions such as DDH or LWE.
At the core of our constructions is a new framework for garbling interactive circuits. Roughly speaking, it allows for garbling interactive machines that participates in interactions of a special form. The garbled machine can emulate the original interactions receiving messages sent in the clear (without being encoded using secrets), and reveals only the transcript of the interactions, provided that the transcript is computationally uniquely defined. We show that garbled interactive circuits for the purpose of constructing MPC can be implemented using OT. Along the way, we also propose a new primitive of witness selector that strengthens witness encryption, and a new notion of zero-knowledge functional commitments.
This is a joint work with Rachel (Huijia) Lin

Title:  Learning with Fully Distributed Private Protocols

Abstract: I’ll review some recent (and not so recent) results on learning in the “local” model of differential privacy, in which participants retain control of their private data and send only differential private outputs to a central, untrusted aggregator. I’ll focus, in particular, on the role of interaction in this model — how does restricting our attention to noninteractive protocols limit the class of learning tasks we can accomplish? The model is of both theoretical and practical interest–several recent deployments of differentially private algorithms follow the “local” paradigm.

Welcome to the first crypto day of this academic year. What’s in store: Coffee, lattices and much more!

When: Friday, November 10 at MIT. Thursday, November 9 at BU.

Where: Hariri Seminar Room, 111 Cummington Mall Room 180, Boston MA.

Attendance is free, as usual, but please register by filling in this rather short google form: https://goo.gl/forms/PkOmXELG8xPqwG812

Organizers: Ran Canetti, Yael Kalai, Ron Rothblum and Vinod Vaikuntanathan.

Thanks: NSF MACS Project for their generous support.

### Program:

 9:30 – 10:00. Coffee/Welcome 10:00 – 11:00. Elette Boyle, IDC Herzliya Can We Access a Database Both Locally and Privately? 11:15 – 12:15. Zvika Brakerski, Weizmann Constraint Hiding Constrained PRFs from LWE 12:15 – 1:15. Lunch (provided) 1:15 – 2:15. David Wu, Stanford Quasi-Optimal SNARGs via Linear Multi-Prover Interactive Proofs 2:15 – 2:30. Coffee Break 2:30 – 3:30. Daniel Wichs, Northeastern Obfuscating Compute-and-Compare Programs under LWE

### Abstracts:

Speaker: Elette Boyle
Title: Can We Access a Database Both Locally and Privately?
We consider the following strong variant of private information retrieval (PIR). There is a large database x that we want to make publicly available. To this end, we post an encoding X of x together with a short public key pk in a publicly accessible repository. The goal is to allow any client who comes along to retrieve a chosen bit x_i by reading a small number of bits from X, whose positions may be randomly chosen based on i and pk, such that even an adversary who can fully observe the access to X does not learn information about i.

Towards solving the above problem, we study a weaker secret key variant where the data is encoded and accessed by the same party. This primitive, that we call an oblivious locally decodable code (OLDC), is independently motivated by applications such as searchable symmetric encryption. We reduce the public-key variant of PIR to OLDC using an ideal form of obfuscation that can be instantiated heuristically with existing indistinguishability obfuscation candidates, or alternatively implemented with small and stateless tamper-proof hardware.

Finally, a central contribution of our work is the first proposal of an OLDC candidate. Our candidate is based on a secretly permuted Reed-Muller code. We analyze the security of this candidate against several natural attacks and leave its further study to future work.

Joint work with Yuval Ishai, Rafael Pass, and Mary Wootters.

Speaker: Zvika Brakerski
Title: Constraint-Hiding Constrained PRFs from LWE

We show how to construct a constraint-hiding constrained pseudorandom functions (CH-CPRF) based on the learning with errors assumption. We show two constructions using two different methods, which end up achieving similar features. Our constructions support arbitrary constraint functions (of a-priori bounded polynomial non-uniformity and depth), contrary to previous works that could only handle NC1 constraints. Similarly to previous works, our constructions do not protect against collusion (i.e. an adversary is only allowed to posses a single constrained key).

Technically, we extend the methodology of Brakerski and Vaikuntanathan (TCC 2015) that showed a duality between LWE-based attribute based encryption (ABE) and CPRF. If this duality extended to (weakly) attribute hiding ABE, then CH-CPRF would have followed. However this was not the case for previously known constructions of attribute hiding ABE. We show how to bridge this gap, and along the way present cleaner constructions of weakly attribute hiding ABE from LWE.

Joint work with Rotem Tsabary, Vinod Vaikuntanathan and Hoeteck Wee.

Speaker: David Wu
Title: Quasi-Optimal SNARGs via Linear Multi-Prover Interactive Proofs

Succinct non-interactive arguments (SNARGs) enable verifying NP computations with significantly less complexity than that required for classical NP verification. In this work, we focus on simultaneously minimizing the proof size and the prover complexity of SNARGs. Concretely, for a security parameter k, we measure the asymptotic cost of achieving soundness error 2^{-k} against provers of size 2^k. We say a SNARG is quasi-optimally succinct if its proof length is quasilinear in the security parameter, and that it is quasi-optimal, if moreover, its prover complexity is only polylogarithmically greater than the running time of the classical NP prover. These bounds are the best we could hope for assuming that NP does not have succinct proofs.

In this work, we give the first quasi-optimal SNARG for Boolean circuit satisfiability from a concrete cryptographic assumption. Our construction takes a two-step approach. The first is an information-theoretic construction of a quasi-optimal linear multi-prover interactive proof (linear MIP) for circuit satisfiability. Then, we describe a generic cryptographic compiler that transforms our quasi-optimal linear MIP into a quasi-optimal SNARG by relying on the notion of linear-only vector encryption over rings introduced by Boneh et al. (Eurocrypt 2017). Combining these two primitives yields the first quasi-optimal SNARG based on linear-only vector encryption.

Joint work with Dan Boneh, Yuval Ishai, and Amit Sahai.

Speaker: Daniel Wichs
Title: Obfuscating Compute-and-Compare Programs under LWE

We show how to obfuscate a large and expressive class of programs, which we call compute-and-compare programs, under the learning-with-errors (LWE) assumption. Each such program CC[f,y] is parametrized by an arbitrary polynomial-time computable function f along with a target value y and we define CCf,y to output 1 if f(x)=y. In other words, the program performs an arbitrary computation f and then compares its output against a target y. Our obfuscator satisfies distributional virtual-black-box security, which guarantees that the obfuscated program does not reveal any partial information about the function f or the target value y, as long as they are chosen from some distribution where y has sufficient pseudo-entropy given f. We also extend our result to multi-bit compute-and-compare programs which output a message z if f(x)=y.

Compute-and-compare programs are powerful enough to capture many interesting obfuscation tasks as special cases. This includes obfuscating conjunctions, and therefore we improve on the prior work of Brakerski et al. (ITCS ’16) which constructed a conjunction obfuscator under a non-standard “entropic” ring-LWE assumption, while here we obfuscate a significantly broader class of programs under standard LWE. We show that our obfuscator has several interesting applications such as upgrading attribute-based encryption to predicate encryption and witness encryption to indistinguishability obfuscation which is secure for all null circuits. Furthermore, we show that our obfuscator gives new circular-security counter-examples for public-key bit encryption and for unbounded length key cycles.

joint work with Giorgos Zirdelis.

UPDATE: Videos from the Crypto Day are now posted here. Enjoy!

Join us for the second Charles River Crypto Day of 2017 on Friday, May 12 at Boston University.

To help us plan for the event, please register here.

When: Friday, May 12.

Where: Hariri Seminar Room, 111 Cummington Mall Room 180, Boston MA.

Organizers: Ran Canetti, Yael Kalai, Ron Rothblum, Vinod Vaikuntanathan and Daniel Wichs.

Thanks: NSF MACS Project for their generous support.

### Program:

 9:30 – 10:00. Introduction/Coffee/Light Breakfast 10:00 – 10:50. Raluca Ada Popa, UC Berkeley An Oblivious and Encrypted Distributed Analytics Platform 11:00 – 11:50. Justin Holmgren, MIT Delegation with Nearly Minimal Time-Space Overhead 12:00 – 1:30. Lunch (provided) 1:30 – 2:20. Fabrice Ben Hamouda, IBM Research On the Robustness of Non-Interactive Multi-Party Computation 2:30 – 3:20. Abhi Shelat, Northeastern Full Accounting for Verifiable Outsourcing 3:30 – 3:50. Coffee Break 3:50 – 4:40. Eran Tromer, Tel Aviv University and Columbia University PhotoProof: Cryptographic Image Authentication for Any Set of Permissible Transformations 4:40. Ushering of Summer Reception

### Abstracts:

TITLE: An Oblivious and Encrypted Distributed Analytics Platform

SPEAKER: Raluca Ada Popa, Berkeley

ABSTRACT:

Many systems run rich data analytics on sensitive data in the cloud, but are prone to data
breaches. A recent hardware enclave architecture promises data confidentiality and isolated
execution of arbitrary computations, yet still suffers from leakage due to memory and network accesses patterns. In this talk, I will describe Opaque, a distributed data analytics platform supporting a wide range of queries while protecting the data. Even a compromised operating system sees only encrypted data. Opaque also protects against leakage from memory and network accesses outside of the enclave (a property called obliviousness). To accomplish this goal, Opaque introduces new distributed oblivious relational operators, as well as new query planning techniques to optimize these new operators. Opaque is implemented on Spark SQL with few changes to the underlying system. Opaque provides data encryption, authentication, and computation verification with a performance ranging from 52% faster to 3.3x slower than vanilla Spark SQL; obliviousness comes with a 1.6–46x overhead. At the same time, Opaque provides an improvement of three orders of magnitude over state-of- the-art oblivious protocols.

Joint work with W. Zheng, A. Dave, J. G. Beekman, J. E. Gonzalez, and I. Stoica.

TITLE: Delegation with nearly minimal time-space overhead

SPEAKER: Justin Holmgren, MIT

ABSTRACT:

Consider a scenario in which a client wants to utilize a powerful, but untrusted, server to
perform computations which are beyond the client’s ability. Since the client does not trust the server, we would like the server to certify the correctness of the result. We would like the verification procedure to be extremely efficient, whereas the complexity of proving shouldn’t be much larger than that of computing.

Assuming LWE, we construct a one-round argument-system for proving the correctness of any
time T and space S computation, in which both the verifier and prover are extremely efficient. In particular, the prover runs in time T * poly(k) and space S + poly(k), where k is a security parameter.

Our result builds on a line of work initiated by Kalai et al. (STOC, 2014). The prover in all of these works runs in time T^c for a large constant c (where c is at least 3). As an additional contribution we significantly simplify a central construct that appears in all of these works.

Joint work with Ron Rothblum.

TITLE: On the Robustness of Non-Interactive Multi-Party Computation

SPEAKER: Fabrice Ben Hamouda, IBM

ABSTRACT:

Non-Interactive Multiparty Computation (Beimel et al., Crypto 2014) is a very powerful notion equivalent (under some corruption model) to garbled circuits, Private Simultaneous Messages protocols, and obfuscation. We present robust solutions to the problem of Non-Interactive Multiparty Computation in the computational and information-theoretic models. Our results include the first efficient and robust protocols to compute any function in NC1 for constant-size collusions, in the information-theoretic setting and in the computational setting, to compute any function in P for constant-size collusions, assuming the existence of one-way functions. Our constructions start from a Private Simultaneous Messages construction (Feige, Killian Naor, STOC 1994 and Ishai, Kushilevitz, ISTCS 1997) and transform it into a Non-Interactive Multiparty Computation for constant-size collusions.

We also present a new Non-Interactive Multiparty Computation protocol for symmetric functions with significantly better communication complexity compared to the only known one of Beimel et al.

This is joint work with Hugo Krawczyk and Tal Rabin.

TITLE:  Full accounting for verifiable outsourcing

SPEAKER: Abhi Shelat, Northeastern

ABSTRACT:

Systems for verifiable outsourcing incur costs for a prover, a verifier, and precomputation; outsourcing makes sense when these costs are cheaper than not outsourcing. Yet, prover costs are generally ignored. The only exception is Verifiable ASICs~(VA), wherein the prover is a custom chip; however, the only prior VA system ignores the cost of precomputation.

This paper describes a new VA system, called Giraffe; charges Giraffe for all three costs; and identifies regimes where outsourcing is worthwhile. Giraffe’s base is an interactive proof geared to data parallel computation. Giraffe makes this protocol asymptotically optimal for the prover, i.e., for a large enough batch size, the prover’s running time is linear in the total number of gates in the arithmetic circuit (whereas prior work incurs an extra log(width of circuit) factor).

Giraffe wins even when outsourcing several tens of sub-computations, scales to 500X larger computations than prior work, and can profitably outsource parts of programs that are not worthwhile to outsource in full.

Joint work with Riad Wahby, Ye Ji, Andrew J Blumberg, Justin Thaler, Michael Walfish and Thomas Wies.

TITLE:  PhotoProof: Cryptographic Image Authentication for Any Set of Permissible Transformations

SPEAKER: Eran Tromer, Tel Aviv University and Columbia University

ABSTRACT:

Authenticating images that claim to depict real events is desirable in many context. Some
cameras already attach digital signatures to photographs, but plain signatures become invalid when the image undergoes legitimate processing such as cropping, rotation, brightness-adjustment or compression. Prior attempts to address this need had inadequate functionality and/or security.

We present PhotoProof, a new approach to image authentication based on cryptographic proofs. It can be configured according to application requirements, to allow any permissible set of (efficiently computable) transformations. Starting with a signed image, the scheme attaches, to each legitimately derived image, a succinct proof of computational integrity attesting that the transformation was permissible. Anyone can verify these proofs, and generate updated proofs when applying further permissible transformations. Moreover, the proofs are zero-knowledge so that, for example, an authenticated cropped image reveals nothing about the cropped-out regions.

PhotoProof is based on Proof-Carrying Data (PCD), a cryptographic primitive for verified
execution of distributed computations, built on top of zero-knowledge SNARK proofs. We will
discuss the scheme, its implementation, and possible extensions to other forms of data provenance.

Joint with with Assa Naveh.

Join us for the first Charles River Crypto Day of 2017 on Friday, February 17 at Microsoft Research New England. In addition to celebrating great research, we are also celebrating Yevgeniy Dodis’s upcoming wedding!

When: Friday, February 17.

Where:  Microsoft New England Research and Development Center
Clara Barton Room (First Floor),
One Memorial Drive, Cambridge MA 02142.

Organizers: Yael Kalai, Ron Rothblum, Vinod Vaikuntanathan and Daniel Wichs.

Thanks: NSF MACS Project for their generous support.

### Program:

 9:30 – 10:00. Introduction/Coffee 10:00 – 11:00. Tal Rabin, IBM Research Privacy-Preserving Search of Similar Patients in Genomic Data 11:00 – 12:00. Yevgeniy Dodis, NYU (Congratulations on upcoming wedding!!!) Fixing Cracks in the Concrete: Random Oracles with Auxiliary Input, Revisited 12:00 – 1:30. Lunch (provided) 1:30 – 2:30. Mark Zhandry, Princeton The Magic of ELFs 2:30 – 3:30. Chris Peikert, Michigan Pseudo-randomness of Ring-LWE for any Ring and Modulus 3:30 – 4:00. Coffee Break 4:00 – 5:00. Hoeteck Wee, CNRS and ENS “Real Cryptographers don’t use Obfuscation”

### Abstracts:

TITLE: Privacy-Preserving Search of Similar Patients in Genomic Data

SPEAKER: Tal Rabin, IBM Research

ABSTRACT:
The growing availability of genomic data holds great promise for advancing medicine and research, but unlocking its full potential requires adequate methods for protecting the privacy of individuals whose genome data we use. One example of this tension is running Similar Patient Query on remote genomic data: In this setting a doctor that holds the genome of his/her patient may try to find other individuals with “close” genomic data (in edit distance), and use the data of these individuals to help diagnose and find effective treatment for that patient’s conditions. This is clearly a desirable mode of operation, however, the privacy exposure implications are considerable, so we would like to carry out the above “closeness” computation in a privacy preserving manner.

In this work we put forward a new approach for highly efficient edit-distance approximation that works well even in settings with much higher divergence. We present contributions both in the design of the approximation method itself and in the protocol for computing it privately.

We also implemented our system. There is a preprocessing step which takes 11-15 seconds and then each query can be answered in 1-2 second depending on the database size.

Joint work with Gilad Asharov, Shai Halevi, and Yehuda Lindell.

TITLE: Fixing Cracks in the Concrete: Random Oracles with Auxiliary Input, Revisited

SPEAKER: Yevgeniy Dodis, New York University

ABSTRACT:

We revisit security proofs for various cryptographic primitives in the random oracle model with auxiliary input (ROM-AI): a (computationally unbounded) attacker A can compute arbitrary S bits of leakage z=z(O) about the random oracle O before attacking the system, and then use additional T oracle queries to O during the attack. This model was explicitly studied by Unruh in 2007 (CRYPTO 2007), but dates back to the seminal paper of Hellman in 1980 about time-space tradeoffs for inverting random functions, and has natural applications in settings where traditional random oracle proofs are not useful: (a) security against non-uniform attackers; (b) space-time tradeoffs; (c) security against preprocessing; (d) resilience to backdoors in hash functions.

We obtain a number of new results about ROM-AI, but our main message is that ROM-AI is the “new cool kid in town”: it nicely connects theory and practice, has a lot of exciting open questions, leads to beautiful math, short definitions, elegant proofs, surprising algorithms, and is still in its infancy. In short, you should work on it!

Joint Work with Siyao Guo and Jonathan Katz.

TITLE: The Magic of ELFs

SPEAKER: Mark Zhandry, Princeton

ABSTRACT:

We introduce the notion of an Extremely Lossy Function (ELF). An ELF is a family of functions with an image size that is tunable anywhere from injective to having a polynomial-sized image. Moreover, for any efficient adversary, for a sufficiently large polynomial r (necessarily chosen to be larger than the running time of the adversary), the adversary cannot distinguish the injective case from the case of image size r.

We develop a handful of techniques for using ELFs, and show that such extreme lossiness is useful for instantiating random oracles in several settings. In particular, we show how to use ELFs to build secure point function obfuscation with auxiliary input, as well as polynomially-many hardcore bits for any one-way function. Such applications were previously known from strong knowledge assumptions — for example polynomially-many hardcore bits were only know from differing inputs obfuscation, a notion whose plausibility has been seriously challenged. We also use ELFs to build a simple hash function with output intractability, a new notion we define that may be useful for generating common reference strings.

Next, we give a construction of ELFs relying on the exponential hardness of the decisional Diffie-Hellman problem, which is plausible in elliptic curve groups. Combining with the applications above, our work gives several practical constructions relying on qualitatively different — and arguably better — assumptions than prior works.

TITLE: Pseudorandomness of Ring-LWE for Any Ring and Modulus

SPEAKER: Chris Peikert, University of Michigan

ABSTRACT:

Our main result is a quantum polynomial-time reduction from worst-case problems on ideal lattices to the decision version of Learning With Errors over Rings (Ring-LWE), for any number ring and any modulus that is not too small (relative to the error rate). Such a reduction was previously known for the search version of Ring-LWE, but hardness of the decision version—which is typically needed for cryptographic applications—was only known to hold for the special case of Galois number rings, such as cyclotomics. The new reduction at least matches, and in some cases improves upon, the parameters obtained in prior work for both the search and decision problems.

Our approach also applies to the original Learning With Errors (LWE) problem, yielding a quantum reduction from worst-case problems on general lattices to decision LWE, again matching or improving upon the parameters obtained by all prior reductions.

Joint work with Oded Regev and Noah Stephens-Davidowitz.

TITLE: “Real cryptographers don’t use obfuscation”

SPEAKER: Hoeteck Wee, CNRS and ENS Paris

ABSTRACT:

In this talk, I will provide a survey of several recent works showing how to use pairing groups to “compile” private-key primitives to public-key ones.

Join us for Charles River Crypto Day on Friday, December 9 at Northeastern University.

When: Friday, December 9.

Where: 90 Snell Library, Northreastern University Campus, Boston MA
Directions:  This link takes you to the correct building on google maps.  Also, see directions for public transportation and driving/parking. Once you enter the library go downstairs to get to room 90.

Please register (free) to attend this event by filling out this  form.
We need all attendees to register to get access to Snell library.

Organizers: Yael Kalai, Ron Rothblum, Vinod Vaikuntanathan and Daniel Wichs.

Thanks: NSF MACS Project for their generous support.

### Program:

 9:30 – 10:00. Introduction/Coffee 10:00 – 11:00. Dana Dachman-Soled, UMD Towards Non-Black-Box Separations of Public Key Encryption and One Way Function 11:15 – 12:15. Leo Reyzin, BU Scrypt is Maximally Memory-Hard 12:15– 1:30 Lunch (provided) 1:30 – 2:30. Gillat Kol, Princeton Interactive Compression for Product Distributions 3 – 4 Mike Rosulek, Oregon State Linicrypt: A Model for Practical Cryptography

### Abstracts:

Speaker: Dana Dachman-Soled
Title: Towards Non-Black-Box Separations of Public Key Encryption and One Way Function

Abstract: Separating public key encryption from one way functions is one of the
fundamental goals of complexity-based cryptography. Beginning with the seminal
work of Impagliazzo and Rudich (STOC, 1989), a sequence of works have ruled
out certain classes of reductions from public key encryption (PKE)—or even
key agreement—to one way function. Unfortunately, known results—so called
black-box separations—do not apply to settings where the construction and/or
reduction are allowed to directly access the code, or circuit, of the one way
function. In this work, we present a meaningful, non-black-box separation
between public key encryption (PKE) and one way function.

Specifically, we introduce the notion of BBN- reductions (similar to the BBNp
reductions of Baecher et al. (ASIACRYPT, 2013)), in which the construction E
accesses the underlying primitive in a black-box way, but wherein the
universal reduction R receives the efficient code/circuit of the underlying
additionally require that the number of oracle queries made to Adv, and the
success probability of R are independent of the run-time/circuit size of the
underlying primitive. We prove that there is no non-adaptive, BBN- reduction
from PKE to one way function, under the assumption that certain types of
strong one way functions exist. Specifically, we assume that there exists a
regular one way function f such that there is no Arthur-Merlin protocol
proving that z not in Range(f)'', where soundness holds with high probability overno instances,” y ~ f(U_n), and Arthur may receive
polynomial-sized, non-uniform advice. This assumption is related to the
average-case analogue of the widely believed assumption coNP \not\subseteq
NP/poly.

Speaker: Leo Reyzin
Title: Scrypt is Maximally Memory-Hard

Abstract: The function scrypt (Percival, 2009) is defined as the result of n steps, where each step consists of selecting one or two previously computed w-bit values (the selection depends on the values themselves) and hashing them to get a new w-bit value. Because it is conjectured that this function is memory-hard, it has been used for key derivation and proofs of work in cryptocurrencies, and has inspired subsequent designs.
We show that indeed scrypt is maximally memory-hard in the parallel random oracle model. Specifically, we show that the product of memory and time used during the computation of scrypt must be Theta(n^2 w), even if the adversary is allowed to make an unlimited number of parallel random oracle queries at each step. Moreover, even if the amount of memory used fluctuates during the computation, we show that the sum of memory usage over time (a.k.a. “cumulative memory complexity” introduced by Alwen and Serbinenko at STOC 2015) is Theta(n^2 w), which implies high memory cost even for adversaries who can amortise the cost over many evaluations.
Our result improves both quantitatively and qualitatively upon the recent work by Alwen et al. (Eurocrypt ’16) who proved a weaker lower bound of Omega(n^2 w / log^2 n) for a restricted class of adversaries.  Our proof is the first showing optimal memory hardness in the random oracle model for any MHF.
Joint work with Joel Alwen, Binyi Chen, Krzysztof Pietrzak, and Stefano Tessaro, http://eprint.iacr.org/2016/989

Speaker: Gillat Kol
Title: Interactive Compression for Product Distributions

Abstract: In a profoundly influential 1948 paper, Claude Shannon introduced information theory and used it to study one-way data transmission problems over different channels, both noisy and noiseless. That paper initiated the study of error correcting codes and data compression, two concepts that are especially relevant today with the rise of the internet and data-intensive applications. In the last decades, interactive communication protocols are used and studied extensively, raising the fundamental question: To what extent can Shannon’s results be generalized to the interactive setting, where parties engage in an interactive communication protocol?

In this talk we will focus on the interactive analog of data compression in an attempt to answer the above question. Specifically, we will consider the case where the parties have inputs that are independent of each other, and give a simulation protocol that communicates poly(I) bits, where I is the information cost of the original protocol. Our protocol is the first simulation protocol whose communication complexity is bounded by a polynomial in the information cost of the original protocol.

Speaker: Mike Rosulek
Title: Linicrypt: A Model for Practical Cryptography

Abstract: A wide variety of objectively practical cryptographic schemes can be constructed using only symmetric-key operations and linear operations. To formally study this restricted class of cryptographic algorithms, we present a new model called Linicrypt. A Linicrypt program has access to a random oracle whose inputs and outputs are field elements, and otherwise manipulates data only via fixed linear combinations.
Our main technical result is that it is possible to decide in polynomial time whether two given Linicrypt programs induce computationally indistinguishable distributions (against arbitrary PPT adversaries, in the random oracle model).
We show also that indistinguishability of Linicrypt programs can be expressed as an existential formula, making the model amenable to automated program synthesis. In other words, it is possible to use a SAT/SMT solver to automatically generate Linicrypt programs that satisfy a given security constraint. Interestingly, the properties of Linicrypt imply that this synthesis approach is both sound and complete. We demonstrate this approach by synthesizing Linicrypt constructions of garbled circuits.
This talk is joint work with Brent Carmer.

Come to the first Charles River Crypto Day of this academic year and get your fix of coffee, blockchains, rational proofs, memory hard functions and (need we say) indistinguishability obfuscation.

When: Friday, October 14 at MIT.

Where: 32 Vassar St (Stata Center)
G-882 (Hewlett), Cambridge MA 02139.

Organizers: Yael Kalai, Ron Rothblum, Vinod Vaikuntanathan and Daniel Wichs.

Thanks: NSF MACS Project for their generous support.

### Program:

 9:30 – 10:00. Introduction/Coffee 10:00 – 11:00. Nir Bitansky, MIT From Cryptomania to Obfustopia through Secret-Key Functional Encryption 11:00 – 12:00. Rachel Lin, UC Santa Barbara Indistinguishability Obfuscation from DDH-like Assumptions on Constant-Degree Graded Encodings 12:00 – 1:30. Lunch (provided) 1:30 – 2:30. Jing Chen, Stony Brook Rational Proofs with Multiple Provers 2:30 – 3:30. Elaine Shi, Cornell Blockchains and Beyond: Rethinking Distributed Consensus in New Settings 3:30 – 4:00. Coffee Break 4:00 – 5:00. Jeremiah Blocki, Purdue Towards a Theory of Data-Independent Memory Hard Functions

### Abstracts:

Speaker: Nir Bitansky
Title: From Cryptomania to Obfustopia through Secret-Key Functional Encryption

Functional encryption lies at the frontiers of current research in cryptography; some variants have been shown sufficiently powerful to yield indistinguishability obfuscation (IO) while other variants have been constructed from standard assumptions such as LWE. Indeed, most variants have been classified as belonging to either the former or the latter category. However, one mystery that has remained is the case of \emph{secret-key functional encryption} with an unbounded number of keys and ciphertexts. On the one hand, this primitive is not known to imply anything outside of minicrypt, the land of secret-key crypto, but on the other hand, we do no know how to construct it without the heavy hammers in obfustopia.

In this work, we show that (subexponentially secure) secret-key functional encryption is powerful enough to construct indistinguishability obfuscation if we additionally assume the existence of (subexponentially secure) plain public-key encryption. In other words, secret-key functional encryption provides a bridge from cryptomania to obfustopia.

On the technical side, our result relies on two main components. As our first contribution, we show how to use secret key functional encryption to get “exponentially-efficient indistinguishability obfuscation” (XIO), a notion recently introduced by Lin et al. (PKC ’16) as a relaxation of IO. Lin et al. show how to use XIO and the LWE assumption to build IO. As our second contribution, we improve on this result by replacing its reliance on the LWE assumption with any plain public-key encryption scheme.

Lastly, we ask whether secret-key functional encryption can be used to construct public-key encryption itself and therefore take us all the way from minicrypt to obfustopia. A result of Asharov and Segev (FOCS ’15) shows that this is not the case under black-box constructions, even for exponentially secure functional encryption. We show, through a non-black box construction, that subexponentially secure-key functional encryption indeed leads to public-key encryption. The resulting public-key encryption scheme, however, is at most quasi-polynomially secure, which is insufficient to take us to obfustopia.

Joint work with Ryo Nishimaki, Alain Passelègue, and Daniel Wichs

Speaker: Rachel Lin
Title: Indistinguishability Obfuscation from DDH-like Assumptions on Constant-Degree Graded Encodings

All constructions of general purpose indistinguishability obfuscation (IO) rely on either meta-assumptions that encapsulate an exponential family of assumptions (e.g., Pass, Seth and Telang, CRYPTO 2014) or polynomial families of assumptions, on graded encoding schemes with a high polynomial degree/multilinearity (e.g., Gentry, Lewko, Sahai and Waters, FOCS 2014).

In this talk, we present two recent works on simplifying graded encodings needed for constructing IO [Lin EUROCRYPT 2016 and Lin-Vaikuntanathan FOCS 2016]. These two works show that IO can be constructed from only constant-degree graded encodings, with a security reduction to a DDH-like assumption — called the joint-SXDH assumption — on the graded encodings, and the sub-exponential security of a polynomial-stretch PRG in NC0. Our assumption on graded encodings is simple, has constant size, and does not require handling composite-order rings. This narrows the gap between the mathematical objects that exist (bilinear maps, from elliptic curve groups) and ones that suffice to construct general purpose IO.

Speaker: Jing Chen
Title: Rational Proofs with Multiple Provers

Classic interactive proofs model a world where a verifier delegates computation to an untrustworthy prover, verifying the prover’s claims before accepting them. We provide the first model that extends rational interactive proofs to allow multiple provers. A verifier pay the provers according to his own randomness and the information received from them. The provers are rational rather than untrustworthy —they may lie, but only to increase the payment. Properly designed protocols incentivize the provers to provide correct information and hence let the verifier to learn the correct answer.

We give tight upper and lower bounds on the computation power of this model. On the way, we show that multiple rational provers are strictly more powerful than one, under standard complexity-theoretic assumptions. We further show that the full power of rational proofs with multiple provers can be achieved using only two provers and five rounds of interaction. Finally, we consider more demanding models where the verifier wants the payment to decrease significantly when the provers are lying, and fully characterize the power of the model when the payment gap must be noticeable.

Speaker: Elaine Shi
Title: Blockchains and Beyond: Rethinking Distributed Consensus in New Settings

Abstract coming soon.

Speaker: Jeremiah Blocki
Title: Towards a Theory of Data-Independent Memory Hard Functions

There is a growing interest in functions which are moderately hard to compute on a normal single-processor machine, but which cannot be computed at a significantly lower cost of dedicated hardware. Such functions are necessary for password-hashing to prevent brute-force attacks implemented on application specific integrated circuits (ASICs). Towards this goal memory-hard functions (MHFs) have been proposed, motivated by the observation that memory costs on customized hardware is not much cheaper than on general architectures. A MHF should have the properties that: (1) Computing the MHF on any input, using a sequential algorithm requires a moderate amount of computational resources (memory and time), and (2) The MHF cannot be repeatedly computed in parallel with significantly less computational resources even if an adversary can amortize his costs across multiple instances (e.g., password guesses). More specifically, we want to ensure that any algorithm evaluating multiple instances of the MHF has high amortized ST-cost — Space X Time divided by #instances evaluated. The second property ensures that the amortized cost of computing an MHF cannot be significantly reduced by developing application specific integrated circuits (ASICs).

Of particular interest in the context of password hashing are data-independent MHFs (iMHFs) as they enjoy a natural resistance to certain side channel attacks which might otherwise leak information about the user’s password. An iMHF can be specified by fixing a directed acyclic graph (DAG) G_n on n nodes of constant indegree and a single sink node n. G_n represents the data-dependency graph between intermediate calls to an underlying hash function during the computation of the iMHF and node n represents final output.

This talk will overview recent results demonstrating that a combinatorial property called depth-robustness fully characterizes iMHFs with high amortized ST-cost. On the positive side we construct a family of DAGs G_n with ST-cost at least $\Omega(n^2/log(n))$. We also show that any iMHF has amortized ST-cost at most $O(n^2 log(log(n))/log(n))$ so our construction is nearly optimal in an asymptotic sense. On the negative side we show that Argon2i, the winner of the password hashing competition, is defined using a directed acyclic graph G_n that is not depth-robust and can be computed by an algorithm with low amortized ST-cost $O(n^{1.71})$. The resulting attacks are practical for realistic settings of the Argon2i parameters.

Based on joint works with Joel Alwen and Krzysztof Pietrzak.

Please join us for second Charles River Crypto Day of this academic year on Friday, February 26 at MSR New England.

Location and Arrival Instructions:
Microsoft New England Research and Development Center
Clara Barton Room (First Floor),
One Memorial Drive, Cambridge MA 02142.

Thanks to NSF MACS Project for their generous support.

### Program:

 9:30 – 10:00. Introduction/Coffee 10:00 – 11:00. Ron Rothblum, MIT Constant-round Interactive-proofs for Delegating Computations 11:30 – 12:30. Omer Paneth, Boston University Delegating RAM Computations 12:30 – 1:30. Lunch (provided) 1:30 – 2:30. Silas Richelson, MIT Three round Non-Malleable Commitment from Non-Malleable Codes 3:00 – 4:00. Muthu Venkitasubramaniam, University of Rochester On the Power of Secure Two-Party Computation

### Abstracts:

Speaker: Ron Rothblum
Title: Constant-round Interactive-proofs for Delegating Computations

Interactive proofs have had a dramatic impact on Complexity Theory and Cryptography. In particular, the celebrated IP=PSPACE Theorem [LFKN92,Shamir92] allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be evaluated using polynomial space). The interactive proof system designed for this purpose requires a polynomial number of communication rounds. It is very natural and well motivated to examine the power of more efficient interactive proofs, and this is the focus of this work.

Our main result is that for every statement that can be evaluated in polynomial time and bounded-polynomial space there exists an interactive proof that satisfies the following strict efficiency requirements: (1) the honest prover runs in polynomial time, (2) the verifier is almost linear time (and under some conditions even sub linear), and (3) the interaction consists of only a constant number of communication rounds.

We introduce several new notions for interactive proofs that turn out to be very useful in our work and may be of independent interest. One of these notions is that of unambiguous interactive proofs where the prover has a unique successful strategy. Another notion is that of probabilistically checkable interactive proofs (PCIPs) where the verifier only reads a few bits of the transcript in checking the proof (this could be viewed as an interactive extension of PCPs).

Joint work with Omer Reingold and Guy Rothblum.

Speaker: Omer Paneth
Title: Delegating RAM Computations

In the setting of cloud computing a user wishes to delegate its data, as well as computations over this data, to a cloud provider. Each computation may read and modify the data, and these modifications should persist between computations. Minding the computational resources of the cloud, delegated computations are modeled as RAM programs. In particular, the delegated computations’ running time may be sub-linear, or even exponentially smaller than the memory size.

We construct a two-message protocol for delegating RAM computations to an untrusted cloud. In our protocol, the user saves a short digest of the delegated data. For every delegated computation, the cloud returns, in addition to the computation’s output, the digest of the modified data, and a proof that the output and digest were computed correctly. When delegating a T-time RAM computation M with security parameter k, the cloud runs in time T * Poly(k) and the user in time Poly(|M|, log(T), k).

Our protocol is secure assuming super-polynomial hardness of the Learning with Error (LWE) assumption. Security holds even when the delegated computations are chosen adaptively as a function of the data and output of previous computations.

We note that RAM delegation schemes are an improved variant of memory delegation schemes [Chung et al. CRYPTO 2011]. In memory delegation, computations are modeled as Turing machines, and therefore, the cloud’s work always grows with the size of the delegated data.

Joint work with Yael Tauman Kalai.

Speaker: Silas Richelson
Title: Three-Round Non-Malleable Commitments from Non-Malleable Codes

We present a new non-malleable commitment protocol. Our protocol has the following features:

1) The protocol has only three rounds of interaction. Pass (TCC 2013) showed an impossibility result for a two-round non-malleable commitment scheme w.r.t. a black-box reduction to any “standard” intractability reduction. Thus, this resolves the round complexity of non-malleable commitment at least w.r.t. black-box security reductions. Our construction is secure as per the standard notion of non-malleability w.r.t. commitment.

2) Our protocol is efficient. In our basic protocol, the entire computation of the committer is dominated by just three invocations of a non-interactive statically binding commitment scheme, while, the receiver computation (in the commitment stage) is limited to just sampling a random string. Unlike many previous works, we directly construct a protocol for large tags and hence avoid any non-malleability amplification steps.

3) Our protocol is based on a black-box use of any non-interactive statistically binding commitment scheme. Such schemes, in turn, can be based on any one-to-one one-way function (or any one-way function at the cost of an extra initialization round). Previously, the best known black-box construction of non-malleable commitments required a larger (constant) number of rounds.

4) Our construction is public-coin and makes use of only black-box simulation. Prior to our work, no public-coin constant round non-malleable commitment schemes were known based on black-box simulation.

Our techniques depart significantly from the techniques used previously to construct non-malleable commitment schemes. As a main technical tool, we rely on non-malleable codes in the split state model. Our proofs of security are purely combinatorial in nature.

In addition, we also present a simple construction of constant round non-malleable commitments from any one-way function. While this result is not new, the main feature is its simplicity compared to any previous construction of non-malleable commitments (regardless of the number of rounds). We believe the construction is simple enough to be covered in a graduate level course on cryptography. The construction uses non-malleable codes in the split state model in a black-box way.

This is joint work with Vipul Goyal and Omkant Pandey.

Speaker: Muthu Venkitasubramaniam
Title: On the Power of Secure Two-Party Computation

Ishai, Kushilevitz, Ostrovsky and Sahai (STOC07, SIAM JoC 2009) introduced the powerful “MPC-in-the-head” technique that provided a general transformation of information-theoretic MPC protocols secure against passive adversaries to a ZK proof in a “black-box” way. In this work, we extend this technique and provide a generic transformation of any semi-honest secure two-party computation (2PC) protocol (with mild adaptive security guarantees) in the so called \emph{oblivious-transfer} hybrid model to an adaptive ZK proof for any NP-language, in a “black-box” way assuming only one-way functions. Our basic construction based on Goldreich-Micali-Wigderson’s 2PC protocol yields an adaptive ZK proof with communication complexity proportional to quadratic in the size of the circuit implementing the NP relation. Previously such proofs relied on an expensive Karp reduction of the NP language to Graph Hamiltonicity (Lindell and Zarosim (TCC09, Journal of Cryptology 2011)). We also improve our basic construction to obtain the first linear-rate adaptive ZK proofs by relying on efficient maliciously secure 2PC protocols. Core to this construction is a new way of transforming 2PC protocols to efficient (adaptively secure) instance-dependent commitment schemes.

As our second contribution, we provide a general transformation to construct a randomized encoding of a function f from any 2PC protocol that securely computes a related functionality (in a black-box way). We show that if the 2PC protocol has mild adaptive security guarantees then the resulting randomized encoding (RE) can be decomposed to an offline/online encoding.

As an application of our techniques, we show how to improve the construction of Lapidot and Shamir (Crypto`90) to obtain black-box constructions of commit-and-prove protocols with the so called input-delayed property where the honest prover’s algorithm does not require the actual statement until the last round. Using this, we obtain first constructions of a 4-round concurrent non-malleable commitments scheme based on one-way permutations where the underlying one-way permutation is used in a black-box way. Previous constructions either required more number of rounds or made non-black-box usage of the underlying primitive. We also show how these proofs can improve round complexity of secure computation protocols in the tamper-proof model.

Joint work with Carmit Hazay.