What: A special *IN-PERSON* crypto day on Friday, July 23 at Northeastern

We’re very excited to bring the Boston-area crypto community back together for a special in-person crypto day. We can’t wait to see all of you in person again! 

Where: Northeastern University, ISEC building (805 Columbus Ave), first floor auditorium (room 102).

Logistics: Masks are optional for fully vaccinated participants and required for everyone else. The talks will be in a large auditorium to give participants plenty of room to socially distance if desired. No food or drinks are allowed in the auditorium. Lunch will be served on the 6th floor in room 655.

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


9:15-9:30 Welcome
9:30 – 10:30Jon Ullman, Northeastern University
The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation (video)
11:00 – 12:00Hoeteck Wee, NTT Research
Breaking the sqrt(N) Barrier in Pairing-Based Broadcast Encryption (video)
12:00 – 1:30Lunch (provided – in ISEC 655)
1:30 – 2:30Zhengzhong Jin, Johns Hopkins University
SNARGs for P from LWE (video)
3 – 4Yael Tauman Kalai, MSR and MIT
Somewhere Statistical Soundness, Post-Quantum Security, and SNARGs (video)
4:30 – 5:30Rishab Goyal, MIT
Dynamic Collusion Bounded Functional Encryption from Identity-Based Encryption (video)


Speaker:  Jon Ullman, Northeastern University
Title:  The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation

Abstract: There has been a recent wave of interest in intermediate trust models for differential privacy that eliminate the need for a fully trusted central data collector, but overcome the limitations of local differential privacy. This interest has led to the introduction of the shuffle model (Cheu et al., EUROCRYPT 2019; Erlingsson et al., SODA 2019) and revisiting the pan-private model (Dwork et al., ITCS 2010). The message of this line of work is that, for a variety of low-dimensional problems — such as counts, means, and histograms — these intermediate models offer nearly as much power as central differential privacy. However, there has been considerably less success using these models for high-dimensional learning and estimation problems. In this work, we show that, for a variety of high-dimensional learning and estimation problems, both the shuffle model and the pan-private model inherently incur an exponential price in sample complexity relative to the central model. For example, we show that, private agnostic learning of parity functions over $d$ bits requires $Ω(2^{d/2})$ samples in these models, and privately selecting the most common attribute from a set of $d$ choices requires $Ω(d^{1/2})$ samples, both of which are exponential separations from the central model. Our work gives the first non-trivial lower bounds for these problems for both the pan-private model and the general multi-message shuffle model.

Joint work with Albert Cheu

Speaker:  Hoeteck Wee, NTT Research
Title: Breaking the sqrt(N) Barrier in Pairing-Based Broadcast Encryption

Abstract: We present the first pairing-based ciphertext-policy attribute-based
encryption (CP-ABE) scheme for the class of degree 3 polynomials with
compact parameters: the public key, ciphertext and secret keys
comprise O(n) group elements, where n is input length for the
function. As an immediate corollary, we obtain a pairing-based
broadcast encryption scheme for N users with O(N^{1/3})-sized
parameters, breaking the long-standing sqrt{N} barrier for pairing-based
broadcast encryption. All of our constructions achieve adaptive security
against unbounded collusions, and rely on the (bilateral) $k$-Lin
assumption in prime-order bilinear groups.

Speaker:  Zhengzhong Jin, Johns Hopkins University
Title:  SNARGs for P from LWE

Abstract: We provide the first construction of a succinct non-interactive argument (SNARG) for *all* polynomial time deterministic computations based on standard assumptions. For T steps of computation, the size of the proof and the common random string (CRS) as well as the verification time are poly-logarithmic in T. The security of our scheme relies on the hardness of the Learning with Errors (LWE) problem against polynomial-time adversaries. Previously, SNARGs based on standard assumptions could support bounded-depth computations and required sub-exponential hardness assumptions [Jawale-Kalai-Khurana-Zhang, STOC’21].

Along the way, we also provide the first construction of non-interactive batch arguments for NP based solely on the LWE assumption.

Based on the joint work with Arka Rai Choudhuri and Abhishek Jain.

Speaker: Yael Tauman Kalai, MSR and MIT
Title:  Somewhere Statistical Soundness, Post-Quantum Security, and SNARGs


We introduce the notion of a somewhere statistically sound (SSS) interactive argument, which is a hybrid between a statistically sound proof and a computationally sound proof.We show that Kilian’s protocol, instantiated with a computationally non-signaling PCP (Brakerski, Holmgren, and Kalai, STOC 2017) and a somewhere statistically binding hash family (Hubacek and Wichs, ITCS 2015), is an SSS argument.  We observe that the first two messages of Kilian, instantiated with these primitives, is a sound instantiation of the BMW heuristic (Kalai, Raz, Rothblum, STOC 2013).  Armed with this observation, we show how to efficiently convert any succinct non-interactive argument (SNARG) for BatchNP into a SNARG for any language that has a non-signaling PCP, including any deterministic language and any language in NTISP, using a somewhere statistically binding hash family.

Secondly, we show that the soundness of SSS arguments can be proved in a straight-line manner, implying that they are also post-quantum sound if the underlying assumption is post-quantum secure. This provides a straightforward proof that Kilian’s protocol, instantiated this way, is post-quantum sound under the post-quantum hardness of LWE (though we emphasize that a computationally non-signaling PCP exists only for deterministic languages and for specific subclasses of non-deterministic languages such as NTISP, but not for all of NP).  We put forward a natural conjecture that constant-round SSS arguments can be soundly converted into non-interactive arguments via the Fiat-Shamir transformation. We argue that SSS arguments evade the current Fiat-Shamir counterexamples, including the one for Kilian’s protocol (Bartusek, Bronfman, Holmgren, Ma and Rothblum, TCC 2019) by requiring additional properties from both the hash family and the PCP.

This is joint work with Vinod Vaikuntanathan and Rachel Zhang.

Speaker:  Rishab Goyal, MIT
Title: Dynamic Collusion Bounded Functional Encryption from Identity-Based Encryption

Abstract: Functional Encryption is a powerful notion of encryption in which each decryption key is associated with a function $f$ such that decryption recovers the function evaluation $f(m)$. Informally, security states that a user with access to function keys $\mathsf{sk}_{f_1}, \mathsf{sk}_{f_2}, \ldots$ (and so on) can only learn $f_1(m), f_2(m), \ldots$ (and so on) but nothing more about the message. The system is said to be $q$-bounded collusion resistant if the security holds as long as an adversary gets access to at most $q = q(\lambda)$ function keys. A major drawback of such \emph{statically} bounded collusion systems is that the collusion bound $q$ must be declared at setup time and is fixed for the entire lifetime of the system.
We initiate the study of \emph{dynamically} bounded collusion resistant functional encryption systems which provide more flexibility in terms of selecting the collusion bound, while reaping the benefits of statically bounded collusion FE systems (such as quantum resistance, simulation security, and general assumptions).
Briefly, the virtues of a dynamically bounded scheme can be summarized as:

1) [Fine-grained individualized selection.] It lets each encryptor select the collusion bound by weighing the trade-off between performance overhead and the amount of collusion resilience.
2) [Evolving encryption strategies.] Since the system is no longer tied to a single collusion bound, thus it allows to dynamically adjust the desired collusion resilience based on any number of evolving factors such as the age of the system, or a number of active users, etc.
3) [Ease and simplicity of updatability.] None of the system parameters have to be updated when adjusting the collusion bound. That is, the same key $\mathsf{sk}_f$ can be used to decrypt ciphertexts for collusion bound $q = 2$ as well as $q = 2^\lambda$.

We construct such a dynamically bounded functional encryption scheme for the class of all polynomial-size circuits under the general assumption of Identity-Based Encryption. 

joint work with Rachit Garg, George Lu and Brent Waters

When: Friday, Feb 12, 2021.

Where: Virtual: A zoom link will be sent to the e-mail list. If you do not receive it, e-mail the organizers to ask for one.

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


10:30 – 11:30.Nick Spooner, BU
Proof-Carrying Data without Succinct Arguments

11:45 – 12:45.Dima Kogan, Stanford
Private Information Retrieval with Sublinear Online Time

12:45 – 1:30.Lunch
1:30 – 3:15.Alex Bredariol Grilo (CNRS/Sorbonne)
and James Bartusek (UC Berkeley)
(double feature with 15 min break in the middle)
Secure Computation is in MiniQCrypt

3:30-4:30. Justin Holmgren, NTT Research
Error Correcting Codes for Uncompressed Messages



Speaker: Nick Spooner, BU
Title: Proof-Carrying Data without Succinct Arguments

Abstract: Proof-carrying data (PCD) is a powerful cryptographic primitive that enables mutually distrustful parties to perform distributed computations that run indefinitely. Prior approaches to construct PCD are based on succinct non-interactive arguments of knowledge (SNARKs) that have a succinct verifier or a succinct accumulation scheme. In this talk I will describe how to obtain PCD without relying on SNARKs. In particular, we construct a PCD scheme given any non-interactive argument of knowledge (e.g., with linear-size proofs) that has a split accumulation scheme, which is a weak form of accumulation that we introduce. We then exploit this new framework to achieve a more efficient PCD construction, by giving an accumulation scheme for a non-interactive argument of knowledge for R1CS with constant verification time. Our results are supported by a modular and efficient implementation.

Speaker: Dima Kogan (Stanford)
Title: Private Information Retrieval with Sublinear Online Time

Speaker: Alex Bredariol Grilo (CNRS/Sorbonne) and James Bartusek (UC Berkeley)
Title: Secure Computation is in MiniQCrypt

Abstract: MiniQCrypt is a world where quantum-secure one-way functions exist, and quantum communication is possible. This talk will show that simulation-secure oblivious transfer is in MiniQCrypt, and thus that secure multi-party computation of any quantum functionality is in MiniQCrypt. The main technical contribution is a construction of extractable and equivocal bit commitment from quantum-secure one-way functions, which is used to instantiate the Bennet-Brassard-Crépeau-Skubiszewska (CRYPTO 91) framework to yield simulation-secure OT.

Speaker: Justin Holmgren (NTT Research)
Title: Error Correcting Codes for Uncompressed Messages

Abstract: Most types of messages we transmit (e.g., video, audio, images, text)
are not fully compressed, since efficient compression algorithms
can fail to reach the information-theoretic limit. In this
work, we study the transmission of partially compressed messages
over a noisy channel, noting that these messages may have additional
structure that is unused by standard error correcting codes.

We introduce a model in which “well-formed” messages comprise a
small fraction of all strings, and are recognizable. In this model,
we construct a (probabilistic) encoding procedure that achieves
better tradeoffs between data rates and error-resilience (compared to
just applying a standard error correcting code).

Surprisingly, our techniques also yield better tradeoffs in the standard setting
where all binary strings are valid messages.

When: Thursday and Friday, July 30-31.
How: A Zoom link was sent to the e-mail list. If you did not receive it, e-mail the organizers to ask for one.
Organizers: Ran Canetti, Yael Kalai, Vinod Vaikuntanathan and Daniel Wichs.

Program (All times are in ET)

Thursday, July 30
12:15–12:30p Virtual Coffee / Hangout
12:30–1:30p Venkata Koppula, Weizmann Institute of Science
Chosen Ciphertext Security from Injective Trapdoor Functions
1:45–2:45p Alex Lombardi, MIT
Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs
3:00–4:00p Lisa Yang, MIT
PPAD-Hardness and Delegation with Unambiguous Proofs
Friday, July 31
12:30-1:30p Mark Bun, Boston University
An Equivalence between Private Classification and Online Prediction
1:45-2:45p Jonathan Shafer, UC Berkeley
Learning vs. Verifying: Interactive Proofs for Verifying Machine Learning
3:00-4:00p Mark Zhandry, Princeton
Local Quantum Cryptography

Chosen Ciphertext Security from Injective Trapdoor Functions
Venkata Koppula

Abstract: In this talk, I will present a construction of chosen ciphertext secure public-key encryption from (injective) trapdoor functions. This construction is black box and assumes no special properties (e.g. “lossy”, “correlated product secure”) of the trapdoor function.

Joint work with Susan Hohenberger and Brent Waters [ paper ]

Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs
Alex Lombardi

Abstract: The Fiat-Shamir transform is a methodology for compiling a (public-coin) interactive proof system for a language L into a non-interactive argument system for L. In this work, we consider the problem of compiling Pietrzak’s succinct interactive proof system (ITCS 2019) for the iterated squaring problem. We construct a hash function family (with evaluation time roughly 2^{\lambda^\epsilon}) that guarantees the soundness of Fiat-Shamir for this protocol assuming the sub-exponential (2^{-n^{1-\epsilon}})-hardness of the n-dimensional learning with errors problem. (The latter follows from the worst-case 2^{n^{1-\epsilon}} hardness of lattice problems.) More generally, we extend the “bad-challenge function” methodology of Canetti et al. for proving the soundness of Fiat-Shamir to a class of protocols whose bad-challenge functions are not efficiently computable.

As a corollary (following Choudhuri et al., ePrint 2019 and Ephraim et al., EUROCRYPT 2020), we construct hard-on-average problems in the complexity class CLS \subset PPAD under the 2^{\lambda^\epsilon}-hardness of the repeated squaring problem and the 2^{-n^{1-\epsilon}}-hardness of the learning with errors problem. Under the additional assumption that the repeated squaring problem is “inherently sequential”, we also obtain a Verifiable Delay Function (Boneh et al., EUROCRYPT 2018) in the standard model. Finally, we give additional PPAD-hardness and VDF instantiations demonstrating a broader tradeoff between the strength of the repeated squaring assumption and the strength of the lattice assumption.

Joint work with Vinod Vaikuntanathan.

Updatable Delegation and PPAD-Hardness
Lisa Yang

Abstract: In this work, we show the hardness of finding a Nash equilibrium, a PPAD-complete problem, based on the quasi-polynomial hardness of the decisional assumption on bilinear groups introduced by Kalai, Paneth and Yang [STOC 2019].Towards this goal, we construct an unambiguous and updatable delegation scheme that is of independent interest.

This delegation scheme is for super-polynomial time deterministic computations and is publicly verifiable and non-interactive in the common reference string (CRS) model. It is unambiguous meaning that it is hard to find two different proofs for the same statement. It is updatable meaning that given a proof for the statement that a Turing machine reaches some configuration C in T steps, one can efficiently update it into a proof for the statement that the machine reaches the next configuration C’ in T+1 steps.

Joint work with Yael Kalai and Omer Paneth.

An Equivalence between Private Classification and Online Prediction
Mark Bun

Abstract: Differential privacy enables rich statistical analyses on data while provably protecting individual-level privacy. The last decade of research has shown that, at least in principle, a number of fundamental statistical tasks are compatible with differential privacy. However, privacy-preserving analyses often require additional complexity over their non-private counterparts, for instance, in terms of the number of data samples one needs to collect in order to get accurate results. In fact, some infinite concept classes that are “easy” to learn in standard computational learning theory become impossible to learn under differential privacy using any finite number of samples.

In this talk, we will describe these impossibility results for private learning and place them in context. We will present a recent characterization of the privately learnable concept classes as exactly those that are learnable in Littlestone’s mistake-bound model of online learning. This equivalence opens new connections between privacy, combinatorics, and stability in learning theory.

Based primarily on work with contributions from Noga Alon, Roi Livni, Maryanthe Malliaris, Shay Moran, Kobbi Nissim, Uri Stemmer, and Salil Vadhan.

Learning vs. Verifying: Interactive Proofs for Verifying Machine Learning
Jonathan Shafer

Abstract: This talk will address the following question: Assume an untrusted party claims to have used machine learning to learn a classifier for a certain task. In what cases is it cheaper to verify that the proposed classifier is good (in the PAC sense), compared to independently learning a new classifier from scratch?

If verification is significantly cheaper than learning, that could have important practical implications for delegation of machine learning tasks in commercial settings, and might also have consequences for verification of scientific publications, and for AI safety. Two results will be discussed: (1) There exists a learning problem where verification requires quadratically less random samples than are required for learning. (2) The broad class of Fourier-sparse functions (which includes decision trees, for example) can be efficiently verified using random samples only, even though it is widely believed to be impossible to efficiently learn this class from random samples alone.

Jonathan is a PhD student at UC Berkeley. This talk covers joint work with Shafi Goldwasser (UC Berkeley), Guy Rothblum (Weizmann Institute of Science), and Amir Yehudayoff (Technion-IIT).

Local Quantum Cryptography
Mark Zhandry

Abstract: “Quantum cryptography” uses a quantum communication channel to achieve new functionalities. For example, the unclonability of quantum messages means an attacker cannot both record quantum communication and also pass it along to the recipient. This leads to a form of eavesdropping detection that is central to quantum key distribution.

In this talk, I will discuss some recent work in an emerging area that I call “local quantum cryptography.” Here, all communication channels remain classical, but the various parties leverage local quantum computing to achieve never-before-possible functionalities. Functionalities we achieve include unclonable cryptographic keys, quantum money with classical communication, rate-limited signatures, and more. The central challenge in this area is to take advantage of features of quantum mechanics such as unclonability, even though all “quantumness” is happening locally on the adversary’s device and therefore is entirely under the adversary’s control.

Based on joint works with Ryan Amos, Marios Georgiou, and Aggelos Kiayias

When: Friday, Nov 1, 2019.

Where: Microsoft New England Research and Development Center
Abigail Adams room on floor M.
1 Memorial Drive, Cambridge MA 02142.

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

Thanks: NSF MACS Project for their generous support.


9:30 – 10:00.Coffee/Breakfast
10:00 – 11:00.Fermi Ma, Princeton University
On the (In)security of Kilian-Based SNARGs
11:15 – 12:15.Giulio Malavolta, Carnegie Mellon University
Homomorphic Time-Lock Puzzles
12:15 – 1:30.Lunch
1:30 – 2:30.Shai Halevi, Algorand Foundation
Compressible FHE with Applications to PIR
2:45 – 3:45.Noah Stephens-Davidowitz, MIT
Will lattice-based cryptography be broken in practice?
4 – 5 Prashant Vasudevan, UC Berkeley
Formalizing Data Deletion in the Context of the Right to be Forgotten


Speaker: Fermi Ma, Princeton University
Title: On the (In)security of Kilian-Based SNARGs

Abstract: The Fiat-Shamir transform applied to Kilian’s protocol (and its extension to interactive oracle proofs) is at the heart of both theoretical results as well as practical implementations of highly efficient non-interactive proof systems (e.g., SNARKs and STARKs). In this work, we demonstrate significant obstacles to establishing the soundness of this approach. We exhibit a particular (contrived) interactive oracle proof (IOP) for NP for which Fiat-Shamir is unsound for any concrete hash function and any Merkle tree commitment. We also show that if Kilian’s original protocol for PCPs is instantiated with a particular (contrived) Merkle tree commitment and any “natural” PCP, then the Fiat-Shamir transform cannot be soundly applied using any concrete hash function. Put together, our results suggest that provably-secure PCP/IOP-based SNARGs will require a synergistic choice of the PCP/IOP, the Merkle tree commitment, and Fiat-Shamir hash function.

Joint work with James Bartusek, Liron Bronfman, Justin Holmgren, and
Ron D. Rothblum.

Speaker: Giulio Malavolta, Carnegie Mellon University
Title: Homomorphic Time-Lock Puzzles

Abstract: Time-lock puzzles allow one to encrypt messages for the future, by efficiently generating a puzzle with a solution s that remains hidden until time T has elapsed. The solution is required to be concealed from the eyes of any algorithm running in (parallel) time less than T. We put forth the notion of homomorphic time-lock puzzles, where one can evaluate functions over puzzles without solving them, i.e., one can manipulate a set of puzzles with solutions (s1,…,sn) to obtain a puzzle that solves to f(s1,…,sn), for any function f. We give a construction of homomorphic time-lock puzzle for any polynomially-computable function based on standard cryptographic assumptions. Then we discuss how homomorphic time-lock puzzles overcome the limitations of classical time-lock puzzles by proposing new protocols for applications of interest, such as e-voting, multi-party coin flipping, and fair contract signing.

Based on a joint work with Sri Aravinda Krishnan Thyagarajan.

Speaker: Shai Halevi, Algorand Foundation
Title: Compressible FHE with Applications to PIR

Homomorphic encryption (HE) is often viewed as impractical, both in communication and computation. Here we provide an additively homomorphic encryption scheme based on (ring) LWE with nearly optimal rate (1-\epsilon for any \epsilon>0). Moreover, we describe how to compress many Gentry-Sahai-Waters (GSW) ciphertexts (e.g., ciphertexts that may have come from a homomorphic evaluation) into (fewer) high-rate ciphertexts.

Using our high-rate HE scheme, we are able for the first time to describe a single-server private information retrieval (PIR) scheme with sufficiently low computational overhead so as to be practical for large databases. Single-server PIR inherently requires the server to perform at least one bit operation per database bit, and we describe a rate-(4/9) scheme with computation which is not so much worse than this inherent lower bound. In fact it is probably less than whole-database AES encryption — specifically about 2.3 mod-q multiplication per database byte, where q is about 50 to 60 bits. Asymptotically, the computational overhead of our PIR scheme is $\tilde{O}(\log\log k + \log\log\log N)$, where $k$ is the security parameter and $N$ is the number of database files, which are assumed to be sufficiently large.

joint work with Craig Gentry

Speaker: Noah Stephens-Davidowitz, MIT
Title:  Will lattice-based cryptography be broken in practice?

Lattice-based cryptography is currently being standardized for widespread use, in anticipation of the development of quantum computers. I.e., we’re going to use this to secure the internet. So, how secure is it really?
I’ll discuss the intimate relationship between lattice-based cryptography and worst-case lattice problems and present both new lower bounds and new algorithmic progress for these problems.

Based on joint works with Divesh Aggarwal, Zvika Brakerski, Huck Bennett, Sasha Golovnev, and Vinod Vaikuntanathan.

Speaker: Prashant Vasudevan, UC Berkeley
Title:  Formalizing Data Deletion in the Context of the Right to be Forgotten

  The right of an individual to request the deletion of their personal data by an entity that might be storing it — referred to as “the right to be forgotten” —  has been explicitly recognized, legislated, and exercised in several jurisdictions across the world, including the European Union, Argentina, and California. However, much of the discussion surrounding this right offers only an intuitive notion of what it means for it to be fulfilled — of what it means for such personal data to be deleted.
    In this work, we provide a formal definitional framework for the right to be forgotten using tools and paradigms from cryptography. In particular, we provide a precise definition of what could be (or should be) expected from an entity that collects individuals’ data when a request is made of it to delete some of this data. While it cannot be viewed as expressing the statements of current laws (since these are rather vague in this respect), our work offers technically precise definitions that represent possibilities for what the law could reasonably expect, and alternatives for what future versions of the law could explicitly require.
    Finally, with the goal of demonstrating the applicability of our framework and definitions, we consider various natural and simple scenarios where the right to be forgotten comes up. For each of these scenarios, we highlight the pitfalls that arise even in genuine attempts at implementing systems offering deletion guarantees, and also describe technological solutions that provably satisfy our definitions. These solutions bring together techniques built by various communities.

Joint work with Sanjam Garg and Shafi Goldwasser

When: Friday, May 3, 2019.

Where: Northeastern University, ISEC Building (805 Columbus Ave) Room 655.

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

Thanks: NSF MACS Project for their generous support.


9:30 – 10:00.Coffee/Breakfast
10:00 – 11:00.Benedikt Bünz, Stanford University
Verifiable Delay Functions and Succinct Proofs in Groups of Unknown Order
11:15 – 12:15.Dakshita Khurana, Microsoft Research
Quantum Advantage and Classical Cryptography
12:15 – 1:30.Lunch
1:30 – 2:30.Prabhanjan Ananth, MIT
Secure MPC with Honest Majority: Minimal Rounds and Efficiency Optimizations
3:00 – 4:00.Aloni Cohen, MIT
Towards Formalizing the GDPR Notion of Singling Out


Speaker: Benedikt Bünz, Stanford University
Title: Verifiable Delay Functions and Succinct Proofs in Groups of Unknown Order

We study the problem of building a verifiable delay function (VDF). A VDF requires a specified number of sequential steps to evaluate, yet produces a unique output that can be efficiently and publicly verified. VDFs have many applications in decentralized systems, including public randomness beacons, leader election in consensus protocols, and proofs of replication. We formalize the requirements for VDFs and present new candidate constructions that are the first to achieve an exponential gap between evaluation and verification time.

Further we survey new VDF constructions by Pietrzak and Wesolowski in groups of unknown order. Building on Wesolowski’s techniques we build succinct proofs in groups of unknown order. We build Sigma protocols that have good soundness in the challenge space and communication complexity independent of the witness. This circumvents a previous impossibility result. These proofs have applications to accumulators and vector commitments.

Papers: https://eprint.iacr.org/2018/601.pdf and https://eprint.iacr.org/2018/1188

Speaker: Dakshita Khurana, Microsoft Research
Title: Quantum Advantage and Classical Cryptography

We demonstrate applications of quantum advantage to building new protocols for classical cryptography. In particular, we observe that in many applications, the oft-used technique of leveraging (time) complexity can be replaced with leveraging quantum advantage instead. In this talk, I will describe how this observation can be combined with additional techniques to obtain:
1. Non-interactive non-malleable commitments without setup in the plain model, under well-studied assumptions.
2. Two-message (privately verifiable) WI arguments based on the polynomial hardness of factoring and quantum polynomial hardness of LWE.

In the first case, I will begin by discussing how to build simple non-interactive non-malleable commitments for O (log log n) tags assuming the sub-exponential hardness of factoring or discrete log, and *quantum* sub-exponential hardness of LWE. Next, I will describe new combinatorial techniques to amplify the number of tags, assuming only the existence of NIWI (non-interactive witness indistinguishable) proofs. These techniques yield the first construction of non-interactive non-malleable commitments w.r.t. replacement for exponentially many tags in the plain model, based on well-studied assumptions. 

I will also discuss how the second application (and some others) follow almost immediately from our observation on quantum advantage. This is based on joint work with Yael Tauman Kalai. The paper is available online at https://eccc.weizmann.ac.il/report/2018/203/.

Speaker: Prabhanjan Ananth, MIT
Title: Secure MPC with Honest Majority: Minimal Rounds and Efficiency Optimizations

We present two constructions of two-round secure multiparty computation protocols with honest majority:

– Our first construction satisfies statistical security with abort and can handle any functionality implementable in NC1. All the previous two-round protocols either required computational assumptions or had a weaker corruption threshold. Our construction employs both broadcast and point-to-point channels. We also show how to generically transform this protocol into one that only employs point-to-point channels while satisfying statistical security with selective abort property. 

– Our second construction can securely compute any functionality implementable in P/poly and has per-party computation cost to be (|C|+n^2) poly(k)  with C being the circuit securely computed, n being the number of parties and k being the security parameter. It is based on one-way functions and satisfies semi-honest security. The per-party computation cost of all the previous protocols in this setting was |C| n^2 poly(k) or more. With an additional round, we can either upgrade to malicious security or achieve a protocol with total computation cost (|C|+n^2) poly(k). 

Based on joint works with Arka Rai Choudhuri (JHU), Aarushi Goel (JHU) and Abhishek Jain (JHU). 

Speaker: Aloni Cohen, MIT
Title: Towards Formalizing the GDPR Notion of Singling Out

There is a significant conceptual gap between legal and mathematical thinking around data privacy. The effect is uncertainty as to the which technical offerings adequately match expectations expressed in legal standards. The uncertainty is exacerbated by a litany of successful privacy attacks, demonstrating that traditional statistical disclosure limitation techniques often fall short of the sort of privacy envisioned by legal standards.

We define predicate singling out, a new type of privacy attack intended to capture the concept of singling out appearing in the General Data Protection Regulation (GDPR).

Informally, an adversary predicate singles out a dataset X using the output of a data release mechanism M(X) if it manages to a predicate p matching exactly one row in X with probability much better than a statistical baseline. A data release mechanism that precludes such attacks is secure against predicate singling out (PSO secure).

We argue that PSO security is a mathematical concept with legal consequences. Any data release mechanism that purports to “render anonymous” personal data under the GDPR must be secure against singling out, and hence must be PSO secure. We then analyze PSO security, showing that it fails to self-compose. Namely, a combination of $\omega(\log n)$ exact counts, each individually PSO secure, enables an attacker to predicate single out. In fact, the composition of just two PSO secure mechanisms can fail to provide PSO security.

Finally, we ask whether differential privacy and k-anonymity are PSO secure. Leveraging a connection to statistical generalization, we show that differential privacy implies PSO security. However, k-anonymity does not: there exists a simple and general predicate singling out attack under mild assumptions on the k-anonymizer and the data distribution.

When: Friday, Mar 8, 2019.

Where:  MIT Stata Center G-882 (Hewlett Room)

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

Thanks: NSF MACS Project for their generous support.


9:30 – 10:00.Coffee/Breakfast
10:00 – 11:00.Zvika Brakerski, Weizmann
Worst-Case Hardness for LPN and Cryptographic Hashing via Code Smoothing
11:15 – 12:15.Gilad Asharov, JP Morgan AI Research
OptORAMa: Optimal Oblivious RAM
12:15 – 1:30.Lunch
1:30 – 2:30.Rachel Lin, University of Washington
Pseudo Flawed-smudging Generators and its Application to Indistinguishability Obfuscation
2:45 – 3:45.Mohammad Mahmoody, University of Virginia
Coin-tossing, Concentration of Products, and Limits of Robust Learning
4:00 – 5:00.abhi shelat, Northeastern
Threshold Factoring from Factoring Assumptions


Speaker: Zvika Brakerski, Weizmann
Title: Worst-Case Hardness for LPN and Cryptographic Hashing via Code Smoothing

We present a worst case decoding problem whose hardness reduces to that ofsolving the Learning Parity with Noise (LPN) problem, in some parameterregime. Prior to this work, no worst case hardness result was known for LPN(as opposed to syntactically similar problems such as Learning with Errors).The caveat is that this worst case problem is only mildly hard and inparticular admits a quasi-polynomial time algorithm, whereas the LPN variantused in the reduction requires extremely high noise rate of $1/2-1/\poly(n)$.Thus we can only show that “very hard” LPN is harder than some “very mildlyhard” worst case problem. We note that LPN with noise $1/2-1/\poly(n)$already implies symmetric cryptography.
Specifically, we consider the $(n,m,w)$-nearest codeword problem($(n,m,w)$-NCP) which takes as input a generating matrix for a binary linearcode in $m$ dimensions and rank $n$, and a target vector which is very closeto the code (Hamming distance at most $w$), and asks to find the codewordnearest to the target vector. We show that for balanced (unbiased) codes andfor relative error $w/m \approx {\log^2 n}/{n}$, $(n,m,w)$-NCP can be solvedgiven oracle access to an LPN distinguisher with noise ratio$1/2-1/\poly(n)$.
Our proof relies on a smoothing lemma for codes which we show to have furtherimplications: We show that $(n,m,w)$-NCP with the aforementioned parameterslies in the complexity class $SearchBPP^{SZK}$ (i.e.\ reducible to a problemthat has a statistical zero knowledge protocol) implying that it is unlikelyto be $NP$-hard. We then show that the hardness of LPN with very low noiserate $\log^2(n)/n$ implies the existence of collision resistant hash functions(our aforementioned result implies that in this parameter regime LPN is alsoin $BPP^{SZK}$).
Joint work with Vadim Lyubashevsky, Vinod Vaikuntanathan and Daniel Wichs.

Speaker: Gilad Asharov, JP Morgan AI Research
Title: OptORAMa: Optimal Oblivious RAM

Oblivious RAM (ORAM), first introduced in the ground-breaking work of Goldreich and Ostrovsky (STOC ’87 and J. ACM ’96) is a technique for provably obfuscating programs’ access patterns, such that the access patterns leak no information about the programs’ secret inputs.  To compile a general program to an oblivious counterpart, it is well-known that $\Omega(\log N)$ amortized blowup is necessary, where $N$ is the size of the logical memory. This was shown in Goldreich and Ostrovksy’s original ORAM work for statistical security and in a somewhat restricted model (the so called \emph{balls-and-bins} model), and recently by Larsen and Nielsen (CRYPTO ’18) for computational security.
A long standing open question is whether there exists an optimal ORAM construction that matches the aforementioned logarithmic lower bounds (without making large memory word assumptions, and assuming a constant number of CPU registers). In this paper, we resolve this problem and present the first secure ORAM with $O(\log N)$ amortized blowup, assuming one-way functions. Our result is inspired by and non-trivially improves on the recent beautiful work of Patel et al. (FOCS ’18) who gave a construction with $O(\log N\cdot \log\log N)$ amortized blowup, assuming one-way functions.
One of our building blocks of independent interest is a linear-time deterministic oblivious algorithm for tight compaction: Given an array of $n$ elements where some elements are marked, we permute the elements in the array so that all marked elements end up in the front of the array. Our $O(n)$ algorithm improves the previously best known deterministic or randomized algorithms whose running time is  $O(n \cdot\log n)$ or $O(n \cdot\log \log n)$, respectively. 
With Ilan Komargodski, Wei-Kai Lin, Kartik Nayak, Enoch Peserico and Elaine Shi.

Speaker: Rachel Lin, University of Washington
Title: Pseudo Flawed-smudging Generators and its Application to Indistinguishability Obfuscation

We introduce Pseudo Flawed-smudging Generators (PFGs). They are polynomially expanding functions over Zp with polynomially small outputs that have some weak pseudo-randomness property. More specifically, the output distribution of a PFG is computationally indistinguishable to a so-called flawed smudging distribution y <– Y, satisfying that for every B = poly(n) bounded noise distribution E, the distributions of (e, e + y) and (e’, e+y) are statistically close, where e and e’ are independent samples from E conditioned on agreeing at a few, o(n), coordinates. Moreover, the statistical closeness only holds with 1/poly(n) probability over the choice of y <– Y. In essence, the output of PFG computationally hides a small noise vector at all but a few coordinates with noticeable probability.
We use PFGs to construct Indistinguishability Obfuscation (IO) schemes for polynomial-sized circuits. Assuming LWE and the existence of constant-locality pseudorandom generators, we construct IO using PFGs and a  Functional Encryption (FE) scheme able to compute them. Instantiating the PFGs with new candidates from [Ananth, Jain, Sahai, Eprint 2018] and instantiating the FE with a new partially hiding FE scheme constructed from bilinear maps, we obtain IO based on i) the security of the new PFG candidates, ii) the SXDH assumption over bilinear maps, iii) LWE, and iv) the security of constant-locality pseudorandom generators.  

Speaker: Mohammad Mahmoody, University of Virginia
Title: Coin-tossing, Concentration of Products, and Limits of Robust Learning

A recent active line of work in robust learning studies attacks on learning algorithms through adversarial perturbations that happen during the training phase (i.e., poisoning attacks) or testing phase (i.e., evasion attacks; aka adversarial examples). In this talk, I first show the existence of some generic information theoretic poisoning attacks as well as evasion attacks for certain theoretically natural input distributions (e.g., the uniform distribution) based on classical results about concentration of measure in certain metric probability spaces (known as Normal Levy Families). I will then show how to make some of these attacks polynomial time by proving computational variants of the measure concentration for any product space under Hamming distance using new (polynomial time) attacks on cryptographic coin tossing protocols.
Based on joint works with Saeed Mahloujifar and Dimitrios Diochnos from NeurIPS’18, AAAI’19 and ALT’19.

Speaker: abhi shelat, Northeastern
Title: Threshold Factoring from Factoring Assumptions

The problem of jointly generating an RSA modulus N has been well considered since Boneh and Franklin first proposed a solution in 1996.  In this talk, we discuss our latest multi-party protocol for this problem as well as interesting open directions that could improve our solution.  Our solution only requires the assumption of OT and can thus be instantiated from the factoring assumption alone; we discuss the costs of this restriction by studying the benefits/costs of using protocols that rely on homomorphic primitives. We also discuss the new motivation behind this problem arising from the use of an RSA modulus N in the construction of a verifiable delay function (VDF), and the use of VDFs in consensus protocols.

This is joint work with Megan Chen, Ran Cohen, Jack Doerner, Yash Kondi,  Eysa Lee, Schuyler Rosefield as well as Carmit Hazay and Muthu Venkitasubramaniam from Ligero.

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.

When:Friday, Dec 14 at BU.

Thanks: NSF MACS Project for their generous support.


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 (video)

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

Weak Zero-Knowledge Beyond the Black-Box Barrier (video)

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

Publicly Verifiable Delegation from Standard Assumptions (video)

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

Fiat-Shamir from Simpler Assumptions (video)

3:45 – 4:30. Reception


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


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

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.


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


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.


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


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.


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


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.