When: Friday, Dec 14 at BU.

Where: Barrister’s Hall at the ground floor of the BU Law School. The address is 765 Comm Ave but it’s better to enter the building from the back entrance on Bay State Road, and then turn right.

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

Thanks: NSF MACS Project for their generous support.

Program:

9:30 – 10:00. Coffee/Breakfast
10:00 – 11:00. Sandro Coretti, NYU

The Double Ratchet: Security Notions, Proofs, and Modularization for the Signal Protocol

11:15 – 12:15. Omer Paneth, Northeastern and MIT

Weak Zero-Knowledge Beyond the Black-Box Barrier

12:15 – 1:30. Lunch
1:30 – 2:30. Lisa Yang, MIT

Publicly Verifiable Delegation from Standard Assumptions

2:45 – 3:45. Alex Lombardi, MIT

Fiat-Shamir from Simpler Assumptions

Abstracts:

Speaker:  Sandro Coretti, NYU
Title: The Double Ratchet: Security Notions, Proofs, and Modularization for the Signal Protocol

Abstract:

Signal is a famous secure messaging protocol used by billions of
people, by virtue of many secure text messaging applications including
Signal itself, WhatsApp, Facebook Messenger, Skype, and Google Allo.
At its core it uses the concept of double ratcheting, where every
message is encrypted and authenticated using a fresh symmetric key; it
has many attractive properties, such as forward security,
post-compromise security, and immediate (no-delay) decryption, which
had never been achieved in combination by prior messaging protocols.While the formal analysis of the Signal protocol, and ratcheting in
general, has attracted a lot of recent attention, we argue that none
of the existing analyses is fully satisfactory. To address this
problem, we give a clean and general definition of secure messaging,
which clearly indicates the types of security we expect, including
forward security, post-compromise security, and immediate decryption.
We are the first to explicitly formalize and model the immediate
decryption property, which implies (among other things) that parties
seamlessly recover if a given message is permanently lost—a property
not achieved by any of the recent provably secure alternatives to
Signal. We build a modular generalized Signal protocol from the
following components: (a) continuous key agreement (CKA), a clean
primitive we introduce and which can be easily and generically built
from public-key encryption (not just Diffie-Hellman as is done in the
current Signal protocol) and roughly models so-called public-key
ratchets; (b) forward-secure authenticated encryption with associated
data (FS-AEAD), which roughly captures so-called symmetric-key
ratchets; and (c) a two-input hash function that is a pseudorandom
function (resp. generator with input) in its first (resp. second)
input, which we term PRF-PRNG. As a result, in addition to
instantiating our framework in a way resulting in the existing, widely
used Diffie-Hellman based Signal protocol, we can easily get
post-quantum security and not rely on random oracles in the analysis.We further show that our design can be elegantly extended to include
forms of fine-grained state compromise recently studied at CRYPTO’18,
but without sacrificing the immediate decryption property. However, we
argue that the additional security offered by these modifications is
unlikely to justify the efficiency hit of using much heavier
public-key cryptography in place of symmetric-key cryptography.

Speaker: Omer Paneth, Northeastern and MIT 
Title: Weak Zero-Knowledge Beyond the Black-Box Barrier

Abstract: The round complexity of zero-knowledge protocols is a long-standing open question, yet to be settled under standard assumptions. So far, the question has appeared equally challenging for relaxations such as weak zero-knowledge and witness hiding. Protocols satisfying these relaxed notions under standard assumptions have at least four messages, just like full-fledged zero knowledge. The difficulty in improving round complexity stems from a fundamental barrier: none of these notions can be achieved in three messages via reductions (or simulators) that treat the verifier as a black box.

We introduce a new non-black-box technique and use it to obtain the first protocols that cross this barrier under standard assumptions. Our main results are:
– Weak zero-knowledge for $\NP$ in two messages, assuming quasipolynomially-secure fully-homomorphic encryption and other standard primitives (known from quasipolynomial hardness of Learning with Errors), as well as subexponentially-secure one-way functions.
– Weak zero-knowledge for $\NP$ in three messages under standard polynomial assumptions (following for example from fully-homomorphic encryption and factoring).
We also give, under polynomial assumptions, a two-message witness-hiding protocol for any language L \in NP that has a witness encryption scheme. This protocol is also publicly verifiable.
Our technique is based on a new homomorphic trapdoor paradigm, which can be seen as a non-black-box analog of the classic Feige-Lapidot-Shamir trapdoor paradigm.
Joint work with Nir Bitansky and Dakshita Khurana

 

 

Speaker: Lisa Yang, MIT
Title: Publicly Verifiable Delegation from Standard Assumptions

Abstract: We construct a delegation scheme for all polynomial time computations.  Our scheme is publicly verifiable and completely non-interactive in the common reference string (CRS) model. 

Our scheme is based on an efficiently falsifiable decisional assumption on groups with bilinear maps.  Prior to this work, publicly verifiable non-interactive delegation schemes were only known under knowledge assumptions (or in the Random Oracle
model), or under non-standard assumptions related to obfuscation or multilinear maps.
 
We obtain our result in two steps.  First we construct a scheme with a long CRS (polynomial in the running time of the computation) by following the blueprint of Paneth and Rothblum (TCC 2017).  Then we show how to bootstrap this scheme to obtain a short CRS.  Our bootstrapping theorem exploits the fact that our scheme can securely delegate certain classes of nondeterministic computations. 

 

 

Speaker: Alex Lombardi
Title: Fiat-Shamir from Simpler Assumptions

Abstract: We present two new protocols:

(1) A succinct publicly verifiable non-interactive argument system for log-space uniform NC computations, under the assumption that any one of a broad class of fully homomorphic encryption (FHE) schemes has almost optimal security against polynomial-time adversaries. The class includes all FHE schemes in the literature that are based on the learning with errors (LWE) problem.

(2) A non-interactive zero-knowledge argument system for NP in the common random string model, assuming almost optimal hardness of search-LWE against polynomial-time adversaries.

Both results are obtained by applying the Fiat-Shamir transform with explicit, efficiently computable functions to certain classes of interactive proofs. We improve over prior work by reducing the security of these protocols to qualitatively weaker computational hardness assumptions. Along the way, we also show that the Fiat-Shamir transform can be soundly applied (in the plain model) to a richer class of protocols than was previously known.

Joint work with Ran Canetti, Yilei Chen, Justin Holmgren, Guy Rothblum, and Ron Rothblum

Advertisements

When: Friday, April 20 at MSR.

Where:  Microsoft New England Research and Development Center
One Memorial Drive, Cambridge MA 02142.

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

Thanks: NSF MACS Project for their generous support.

Program:

9:30 – 10:00. Coffee/Welcome
10:00 – 11:00.
Brent Waters, UT Austin
Collusion Resistant Traitor Tracing from Learning with Errors
11:15 – 12:15. Mor Weiss, Northeastern
Private Anonymous Data Access
12:15 – 1:30. Lunch
1:30 – 2:30. Tianren Liu, MIT
Breaking the Circuit-Size Barrier for General Secret Sharing
2:45 – 3:45. Ron Rothblum, MIT + Northeastern
Efficient Batch Verification for UP

Abstracts:

Speaker:  Brent Waters, UT Austin
Title:  Collusion Resistant Traitor Tracing from Learning with Errors

Abstract: In this work we provide a traitor tracing construction with ciphertexts that grow polynomially in log(n) where n is the number of users and prove it secure under the Learning with Errors (LWE) assumption. This is the first traitor tracing scheme with such parameters provably secure from a standard assumption. In addition to achieving new traitor tracing results, we believe our techniques push forward the broader area of computing on encrypted data under standard assumptions. Notably, traitor tracing is substantially different problem from other cryptography primitives that have seen recent progress in LWE solutions.

We achieve our results by first conceiving a novel approach to building traitor tracing that starts with a new form of Functional Encryption that we call Mixed FE. In a Mixed FE system the encryption algorithm is bimodal and works with either a public key or master secret key. Ciphertexts encrypted using the public key can only encrypt one type of functionality. On the other hand the secret key encryption can be used to encode many different types of programs, but is only secure as long as the attacker sees a bounded number of such ciphertexts.

We first show how to combine Mixed FE with Attribute-Based Encryption to achieve traitor tracing. Second we build Mixed FE systems for polynomial sized branching programs (which corresponds to the complexity class logspace) by relying on the polynomial hardness of the LWE assumption with super-polynomial modulus-to-noise ratio.

Joint work with Rishab Goyal and Venkata Koppula

Speaker: Mor Weiss, Northeastern 
Title:  Private Anonymous Data Access

Abstract: We consider a scenario where a server holds a huge database that it wants to make accessible to a large group of clients. After an initial setup phase, clients should be able to read arbitrary locations in the database while maintaining privacy (the server does not learn which locations are being read) and anonymity (the server does not learn which client is performing each read). This should hold even if the server colludes with a subset of the clients. Moreover, the run-time of both the server and the client during each read operation should be low, ideally only polylogarithmic in the size of the database and the number of clients. We call this notion Private Anonymous Data Access (PANDA).

PANDA simultaneously combines aspects of Private Information Retrieval (PIR) and Oblivious RAM (ORAM). PIR has no initial setup, and allows anybody to privately and anonymously access a public database, but the server’s run-time is linear in the data size. On the other hand, ORAM achieves poly-logarithmic server run-time, but requires an initial setup after which only a single client with a secret key can access the database. The goal of PANDA is to get the best of both worlds: allow many clients to privately and anonymously access the database as in PIR, while having an efficient server as in ORAM.

In this work, we construct bounded-collusion PANDA schemes, where the efficiency scales linearly with a bound on the number of corrupted clients that can collude with the server, but is otherwise poly-logarithmic in the data size and the total number of clients. Our solution relies on standard assumptions, namely the existence of fully homomorphic encryption, and combines techniques from both PIR and ORAM. We also extend PANDA to settings where clients can write to the database.

Joint work with Ariel Hamlin, Rafail Ostrovsky,  and Daniel Wichs

Speaker: Tianren Liu, MIT
Title:  Breaking the Circuit-Size Barrier for General Secret Sharing

Abstract: We study secret sharing schemes for general (non-threshold) access structures. A general secret sharing scheme for $n$ parties is associated to a monotone function $F:{0,1}^n\to{0,1}$. In such a scheme, a dealer distributes shares of a secret $s$ among $n$ parties. Any subset of parties $T \subseteq [n]$ should be able to put together their shares and reconstruct the secret $s$ if $F(T)=1$, and should have no information about $s$ if $F(T)=0$. One of the major long-standing questions in information-theoretic cryptography is to minimize the (total) size of the shares in a secret-sharing scheme for arbitrary monotone functions $F$.

There is a large gap between lower and upper bounds for secret sharing. The best known scheme for general $F$ has shares of size $2^{n-o(n)}$, but the best lower bound is $\Omega(n^2/\log n)$. Indeed, the exponential share size is a direct result of the fact that in all known secret-sharing schemes, the share size grows with the size of a circuit (or formula, or monotone span program) for $F$. Indeed, several researchers have suggested the existence of a {\em representation size barrier} which implies that the right answer is closer to the upper bound, namely, $2^{n-o(n)}$.

In this work, we overcome this barrier by constructing a secret sharing scheme for any access structure with shares of size $2^{0.994n}$ and a linear secret sharing scheme for any access structure with shares of size $2^{0.999n}$.  Our construction builds on our recent works that construct better protocols for the conditional disclosure of secrets (CDS) problem.

Joint work with Vinod Vaikuntanathan

Speaker:  Ron Rothblum, MIT + Northeastern
Title:  Efficient Batch Verification for UP

Abstract: We construct an interactive proof for verifying the correctness of any k UP statements (i.e., NP statements that have a unique witness). Our proof-system has a constant number of rounds of interaction and has communication complexity is $k^\delta \cdot poly(m)$, where $\delta>0$ is an arbitrarily small constant, m is the length of a single witness and the $poly$ term refers to a fixed polynomial that only depends on the language and not on $\delta$. The (honest) prover strategy can be implemented in polynomial-time given access to the k (unique) witnesses.

Since communication grows sub-linearly with k, for large values of k this proof-system is much more efficient than the naive solution in which the prover simply sends the k witnesses.

Joint work with Omer Reingold and Guy Rothblum

 

When: Friday, Feb 16 at MIT.

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

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
10:00 – 11:00.
Siyao Guo, Northeastern University
Random Oracles and Non-Uniformity
11:15 – 12:15. Muthuramakrishnan Venkitasubramaniam, University of Rochester
Ligero: Lightweight Sublinear Zero-Knowledge Arguments
12:15 – 1:30. Lunch
1:30 – 2:30. Yael Kalai, MSR and MIT
Non-Interactive Delegation for Low-Space Non-Deterministic Computation
2:45 – 3:45. Daniel Genkin, UPenn
Spectre and Meltdown: Speculative Execution Considered Harmful

Abstracts:

Speaker: Siyao Guo, Northeastern University
Title: Random Oracles and Non-Uniformity

Abstract: We revisit security proofs for various cryptographic primitives in the {\em auxiliary-input random oracle model} (AI-ROM), in which an attacker can compute arbitrary $S$ bits of leakage 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 (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) security against preprocessing.

We obtain a number of new results about the AI-ROM:

(1) Unruh introduced the {\em pre-sampling technique}, which generically reduces security proofs in the AI-ROM to those in a much simpler {\em $P$-bit-fixing random oracle model} (BF-ROM), where the attacker can arbitrarily fix the values of $O$ on some $P$ coordinates, but then the remaining coordinates are chosen at random. Unruh’s security loss for this transformation is $\sqrt{ST/P}$. We improve this loss to the {\em optimal} value $O(ST/P)$, which implies nearly tight security bounds for a variety of indistinguishability applications in the AI-ROM.

(2) While the basic pre-sampling technique cannot give tight bounds for unpredictability applications, we introduce a novel “mutiplicative version” of pre-sampling, which allows to dramatically reduce the size of $P$ of the pre-sampled set (namely, $P=O(ST)$), and yields nearly tight security bounds for a variety of unpredictability applications in the AI-ROM. Qualitatively, it validates Unruh’s “polynomial pre-sampling conjecture”—disproved in general by Dodis \etal (Eurocrypt 2017)—for the special case of unpredictability applications.

(3) Finally, we build two general compilers showing how to generically extend the security of applications proven in the traditional ROM to the AI-ROM. One compiler simply prepends a public salt to the random oracle and shows that {\em salting generically provably defeats preprocessing}.

Overall, or results makes it much easier to get concrete security bounds in the AI-ROM. These bounds in turn give concrete conjectures about the security of these applications (in the standard model) against {\em non-uniform} attackers.

Joint work with Sandro Coretti, Yevgeniy Dodis and John Steinberger.

Speaker: Muthuramakrishnan Venkitasubramaniam, University of Rochester
Title:  Ligero: Lightweight Sublinear Zero-Knowledge Arguments

Abstract: Succinct non-interactive zero-knowledge (ZK) argument of knowledge or zk-SNARKs, a variant of ZK proof systems, have recently gained a lot of attention as a tool that enables anonymity and integrity in blockchain technologies and forms the backbone of the Zcash cryptocurrency. However, the current (efficient) solutions either rely on trusted setup or make heavy use of public-key primitives and/or complex combinatorial objects (eg, probabilistically checkable proofs).

We design and implement a simple zero-knowledge argument protocol for arbitrary statements (i.e., NP) whose communication complexity is proportional to the square-root of the verification circuit size. The protocol can be based on any collision-resistant hash function. Alternatively, it can be made non-interactive in the random oracle model, yielding concretely efficient zk-SNARKs that do not require a trusted setup or public-key cryptography.

Our protocol is attractive not only for very large verification circuits but also for moderately large circuits (Boolean or Arithmetic) that arise in applications. For instance, for verifying a SHA-256 preimage in zero-knowledge with 2^{-40} soundness error, the proof length is 34KB, the prover running time is 140 ms, and the verifier running time is 62 ms. This proof is roughly 5 times shorter than a similar proof of ZKB++ (Chase et al., CCS 2017), an optimized variant of ZKBoo (Giacomelli et al., USENIX 2016).

I will describe some applications where our zero-knowledge argument will improve the state-of-the-art and present some on-going work.

Based on joint works with Scott Ames, Carmit Hazay, and Yuval Ishai

Speaker: Yael Kalai, MSR and MIT
Title:  Non-Interactive Delegation for Low-Space Non-Deterministic Computation

Abstract: We construct a delegation scheme for verifying *non-deterministic* computations, with complexity proportional only to the non-deterministic space of the computation.  Specifically, letting n denote the input length, we construct a delegation scheme for any language verifiable in non-deterministic time and space (T(n), S(n)), with communication complexity poly(S(n)), verifier runtime n*polylog(T(n))+poly(S(n)), and prover runtime poly(T(n)).

Our scheme consists of only two messages and has adaptive soundness, assuming the existence of a sub-exponentially secure private information retrieval (PIR) scheme, which can be instantiated under the sub-exponential LWE assumption.

Specifically, the verifier publishes a (short) public key ahead of time, and this key can be used by any prover to *non-interactively* prove the correctness of any *adaptively chosen* non-deterministic computation.  Our scheme is privately verifiable, where the verifier needs the corresponding secret key in order to verify proofs.
This is joint work with Saikrishna Badrinarayanan, Dakshita Khurana, Amit Sahai, and Daniel Wichs.

Speaker: Daniel Genkin, UPenn
Title:  Spectre and Meltdown: Speculative Execution Considered Harmful

Abstract: This talk presents Spectre and Meltdown, two new microarchitectural attacks that exploit speculative execution of instructions to leak sensitive information from computer systems. The talk discusses the mechanisms employed by the attacks, initial countermeasures and the implications on secure software design. 

This is a joint work with Anders Fogh, Daniel Gruss, Werner Haas, Mike Hamburg, Jann Horn, Paul Kocher, Moritz Lipp, Stefan Mangard, Thomas Prescher, and Michael Schwarz and Yuval Yarom

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

Speaker: Adam Smith,BU
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.