Archive

Author Archives: danwichs

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.

Program:

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

Abstracts:

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

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.

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

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

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, 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.

 

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

When: Friday, February 17.

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

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

Thanks: NSF MACS Project for their generous support.

Program:

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

Abstracts:

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

SPEAKER: Tal Rabin, IBM Research

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

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

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

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

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

SPEAKER: Yevgeniy Dodis, New York University

ABSTRACT:

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

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

Joint Work with Siyao Guo and Jonathan Katz.

TITLE: The Magic of ELFs

SPEAKER: Mark Zhandry, Princeton

ABSTRACT:

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

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

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

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

SPEAKER: Chris Peikert, University of Michigan

ABSTRACT:

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

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

Joint work with Oded Regev and Noah Stephens-Davidowitz.

TITLE: “Real cryptographers don’t use obfuscation”

SPEAKER: Hoeteck Wee, CNRS and ENS Paris

ABSTRACT:

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

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

When: Friday, December 9.

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

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

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

Thanks: NSF MACS Project for their generous support.

Program:

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

Abstracts:

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

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

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

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

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

 

Speaker: Gillat Kol
Title: Interactive Compression for Product Distributions

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

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

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

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

Please join us for the next installment of Crypto Day on Friday, April 17 at Northeastern University.

Location:
103 Churchill Hall
Northeastern University Boston, MA 02115

Program:

9:30 – 10:00. Introduction/Coffee
10:00 – 11:00.
Leo Reyzin, BU
Wyner’s Wire-Tap Channel, Forty Years Later
11:30 – 12:30. Christopher Fletcher, MIT
Onion ORAM: A Constant Bandwidth ORAM using Additively Homomorphic Encryption
12:30 – 2:00. Lunch (provided)
2:00 – 3:00. Daniele Micciancio, UCSD
FHEW: Bootstrapping Homomorphic Encryption in less than a second
3:30 – 4:30. Kobbi Nissim, Ben-Gurion University and CRCS@Harvard
Learning under Differential Privacy

Abstracts:

Speaker: Leo Reyzin

Wyner’s Wire-Tap Channel, Forty Years Later

Wyner’s information theory paper “The Wire-Tap Channel” turns forty this year. Its importance is underappreciated in cryptography, where its intellectual progeny includes pseudorandom generators, privacy amplification, information reconciliation, and many flavors of randomness extractors (including plain, strong, fuzzy, robust, nonmalleable, source-private, local, and reusable). Focusing mostly on privacy amplification and fuzzy extractors, I will demonstrate the connection from Wyner’s paper to today’s research, including work on program obfuscation. I will conclude with some recent results on the feasibility of fuzzy extractors, based on joint work with Benjamin Fuller and Adam Smith.

 

Speaker: Christopher Fletcher

Title: Onion ORAM: A Constant Bandwidth ORAM using Additively Homomorphic Encryption

Oblivious RAM (ORAM) is a cryptographic primitive that obfuscates a client’s access pattern (address, data, read/write) to an untrusted memory source. In addition to its traditional application to outsourced storage, ORAM has proven to be an important component in the Cryptographic “swiss army knife” — finding uses in Garbled RAM, Secure Computation, Proofs of Retrievability, and more.

In this talk I will discuss Onion ORAM, a constant bandwidth ORAM that uses poly-logarithmic server computation to circumvent the well-known logarithmic lower bound in ORAM bandwidth. In addition to being constant bandwidth, Onion ORAM achieves constant client and server storage blowups — asymptotically optimal for each category — and does so without relying on Fully Homomorphic Encryption. In particular, we only require an Additively Homomorphic Encryption scheme with constant ciphertext blowup such as the Damgard-Jurik cryptosystem. We will extend the scheme to be secure against a malicious server using standard assumptions. To the best of our knowledge, Onion ORAM is the first concrete instantiation of a constant-bandwidth ORAM with poly-logarithmic computation (even for the semi-honest setting).

Joint work with Ling Ren, Srini Devadas, Marten van Dijk, Elaine Shi and Daniel Wichs

 

Speaker: Daniele Micciancio

Title: FHEW: Bootstrapping Homomorphic Encryption in less than a second

The main bottleneck affecting the efficiency of all known fully homomorphic encryption (FHE) schemes is Gentry’s bootstrapping procedure, which is required to refresh noisy ciphertexts and keep computing on encrypted data. We present a new method to homomorphically compute simple bit operations, and refresh (bootstrap) the resulting output, which runs on a personal computer in just about half a second.

Join work with Leo Ducas, to appear in Eurocrypt 2015

 

Speaker: Kobbi Nissim

Title: Learning under Differential Privacy

Learning is a task that abstracts many of the computations performed over large collections of sensitive individual information, hence natural to examine in conjunction with differential privacy. Predating differential privacy, in 2005 Blum, Dwork, McSherry and Nissim showed that any concept class that is learnable in Kearns’ model of statistical queries is also learnable with privacy. The concept of Private Learning formalized by Kasiviswanathan et al. in 2008 as the conjunction of PAC learning and differential privacy. They showed that any concept class |C| can be learned privately with O(log|C|) samples, via a construction that is somewhat analogous to the Occam Razor (non-private) learner.

Investigating the gap between the sample complexity and computational complexity of private and non-private learners resulted in a rich picture that we will highlight in the talk. In particular, we will examine some of the lower bound and upper bound techniques used in this context, and explore some of the ways to mitigate the costs of private learners. Time permitting, we will see relationships between private learning and other tasks, such as median computation and data sanitization.

Based on joint works with: Amos Beimel, Avrim Blum, Hai Brenner, Mark Bun, Cynthia Dwork, Shiva Kasiviswanathan, Homin Lee, Frank McSherry, Sofya Raskhodnikova, Adam Smith, Uri Stemmer, and Salil Vadhan.