Author Archives: danwichs

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.


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”


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

SPEAKER: Tal Rabin, IBM Research

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


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


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


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


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.


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


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

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,


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.

103 Churchill Hall
Northeastern University Boston, MA 02115


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


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.

Please join us for the next installment of Crypto Day on Friday, February 20 at Microsoft Research, New England.

Location and Arrival Instructions:
Microsoft New England Research and Development Center
One Memorial Drive, Cambridge MA 02142

Upon arrival, be prepared to show a picture ID and sign the Building Visitor Log when approaching the Lobby Floor Security Desk. Alert them to the name of the event, and ask them to direct you to the appropriate floor. The talks will be held the First Floor Conference Center, in the Horace Mann Conference Room. Detailed guidance on directions, via car or public transportation, is available here. Parking will be available for the on-site parking garage for $27/day.


9:30 – 10:00. Introduction/Coffee
10:00 – 11:00.
Tal Malkin, Columbia
The Power of Negations in Cryptography
11:30 – 12:30. Rachel Lin, USCB
Constant-Round Concurrent Zero-knowledge from Indistinguishability Obfuscation
12:30 – 2:00. Lunch (provided)
2:00 – 3:00. Alessandra Scaffuro, BU and Northeastern
Garbled RAM From One-Way Functions
3:30 – 4:30. Henry Corrigan-Gibbs, Stanford
Building Anonymous Messaging Systems that ‘Hide the Metadata’


Speaker: Tal Malkin
Title: The Power of Negations in Cryptography

The study of monotonicity and negation complexity for Boolean functions has been prevalent in complexity theory as well as in computational learning theory, but little attention has been given to it in the cryptographic context. Recently, Goldreich and Izsak (2012) have initiated a study of whether cryptographic primitives can be monotone, and showed that one-way functions can be monotone (assuming they exist), but a pseudorandom generator cannot.

In this work, we start by filling in the picture and proving that many other basic cryptographic primitives cannot be monotone. We then initiate a quantitative study of the power of negations, asking how many negations are required. We provide several lower bounds, some of them tight, for various cryptographic primitives and building blocks including one-way permutations, pseudorandom functions, small-bias generators, hard-core predicates, error-correcting codes, and randomness extractors. Among our results, we highlight the following.

i) Unlike one-way functions, one-way permutations cannot be monotone.

ii) We prove that pseudorandom functions require log n−O(1) negations (which is optimal up to the additive term).

iii) Error-correcting codes with optimal distance parameters require log n−O(1) negations (again, optimal up to the additive term).

iv) We prove a general result for monotone functions, showing a lower bound on the depth of any circuit with t negations on the bottom that computes a monotone function f in terms of the monotone circuit depth of f. This result addresses a question posed by Koroth and Sarma (2014) in the context of the circuit complexity of the Clique problem.

Joint work with Siyao Guo, Igor Carboni Oliveira, and Alon Rosen.

Speaker: Rachel Lin
Title: Constant-Round Concurrent Zero-knowledge from Indistinguishability Obfuscation

We present a constant-round concurrent zero-knowledge protocol for NP. Our protocol relies on the existence of families of collision-resistant hash functions, one-way permutations, and indistinguishability obfuscators for P/poly (with slightly super-polynomial security).

Speaker: Alessandra Scafuro
Title: Garbled RAM From One-Way Functions

Yao’s garbled circuit construction is a fundamental construction in cryptography and recent efficiency optimizations have brought it much closer to practice. However these constructions work only for circuits and garbling a RAM program involves the inefficient process of first converting it into a circuit. Towards avoiding this inefficiency, Lu and Ostrovsky [Eurocrypt 2013] introduced the notion of “garbled RAM” as a method to garble RAM programs directly. It can be seen as a RAM analogue of Yao’s garbled circuits such that, the size of the garbled program and the time it takes to create and evaluate it, is proportional only to the running time on the RAM program rather than its circuit size.
Known realizations of this primitive, either rely on stronger computational assumptions such as the existence of
Identity-Based Encryption, or rely on one-way functions only but do not achieve the aforementioned efficiency [Gentry, Halevi, Lu, Ostrovsky, Raykova and Wichs, EUROCRYPT 2014].

In this work we provide the first construction with strictly poly-logarithmic overhead in both space and time based only on the minimal assumption
that one-way functions exist.

Join work with Sanjam Garg, Steve Lu and Rafail Ostrovsky.

Henry Corrigan-Gibbs

Title: Building Anonymous Messaging Systems that ‘Hide the Metadata’

Encryption can protect the contents of a message being sent over an open network. In many situations, though, hiding the contents of a communication is not enough: parties to a conversation want to conceal the fact that they ever communicated. In this talk, I will explain how anonymity-preserving messaging systems can help ‘hide the metadata’ pertaining to a conversation and I will survey the state of the art in anonymous messaging protocols.

A limitation of existing protocols is that they exhibit computation and communication costs that scale linearly with the number of users (i.e., the anonymity set size) or they require expensive zero-knowledge proofs. In recent work, we have designed Riposte, a new system for anonymous messaging that applies private-information-retrieval and secure multi-party computation techniques to circumvent these limitations.

An implementation and experimental evaluation of Riposte demonstrates that, for latency-tolerant applications, the system can provide near-ideal anonymity for groups of millions of users—two orders of magnitude more than current systems support. I will conclude the talk with a discussion of open problems and directions for future work.

Joint work with: Dan Boneh and David Mazières

Please join us for the next installment of Crypto Day on Friday, December 5 at Boston University.

Location: 111 Cummington Mall Room 180. [directions]

Parking: There’s a pay lot across the street and 4-hour meters on Bay State Road.


9:30 – 10:00. Introduction/Coffee
10:00 – 11:00.
Yuval Ishai, Technion
Circuits Resilient to Additive Attacks, with Applications to Secure Computation
11:30 – 12:30. Omer Paneth, Boston University
Publicly-Verifiable Non-Interactive Arguments for Delegating Computations
12:30 – 2:00. Lunch (provided)
2:00 – 3:00. Elaine Shi, University of Maryland
Programs to Circuits: Towards a Programming Language for Cryptography
3:30 – 4:30. Sergey Gorbunov, MIT
Leveled Fully Homomorphic Signatures from Standard Lattices

Thanks: NSF Frontier Grant: Modular Approach to Cloud Security (MACS), Hariri Institute for Computing and Center for RISCS.

Special thanks to Leo Reyzin, Debbie Lehto, and Lauren Dupee for help with organization


Speaker: Yuval Ishai
Title: Circuits Resilient to Additive Attacks, with Applications to Secure Computation

We study the question of protecting arithmetic circuits against additive attacks that can add an arbitrary fixed value to each wire in the circuit. We show how to transform an arithmetic circuit C into a functionally equivalent, randomized circuit C’ of comparable size, such that the effect of any additive attack on the wires of C’ can be simulated (up to a small statistical distance) by an additive attack on just the inputs and outputs of C.

Our study of this question is motivated by the goal of simplifying and improving protocols for secure multiparty computation (MPC). It is typically the case that securing MPC protocols against active adversaries is much more difficult than securing them against passive adversaries. We observe that in simple MPC protocols that were designed to protect circuit evaluation only against passive adversaries, the effect of any active adversary corresponds precisely to an additive attack on the circuit’s wires. Thus, to securely evaluate a circuit C in the presence of active adversaries, it suffices to apply the passive-case protocol to a corresponding circuit C’ which is secure against additive attacks. We use this methodology to simplify feasibility results and obtain efficiency improvements in several standard MPC models.

Joint work with Daniel Genkin, Manoj Prabhakaran, Amit Sahai, and Eran Tromer.

Speaker: Omer Paneth
Title: Publicly-Verifiable Non-Interactive Arguments for Delegating Computations

We construct publicly verifiable non-interactive arguments that can be used to delegate polynomial time computations. These computationally sound proof systems are completely non-interactive in the common reference string model. The verifier’s running time is nearly-linear in the input length, and poly-logarithmic in the complexity of the delegated computation. Our protocol is based on graded encoding schemes, introduced by Garg, Gentry and Halevi (Eurocrypt 2012). Security is proved under a falsifiable and arguably simple cryptographic assumption about graded encodings. All prior publicly verifiable non-interactive argument systems were based on non-falsifiable knowledge assumptions. Our new result builds on the beautiful recent work of Kalai, Raz and Rothblum (STOC 2014), who constructed privately verifiable 2-message arguments. While building on their techniques, our protocols avoid no-signaling PCPs, and we obtain a simplified and modular analysis.

As a second contribution, we also construct a publicly verifiable non-interactive argument for (logspace-uniform) computations of bounded depth. The verifier’s complexity grows with the depth of the circuit. This second protocol is adaptively sound, and its security is based on a falsifiable assumption about the hardness of a search problem on graded encodings (a milder cryptographic assumption). This result builds on the interactive proof of Goldwasser, Kalai and Rothblum (STOC 2008), using graded encodings to construct a non-interactive version of their protocol.

Joint work with Guy Rothblum.

Speaker: Elaine Shi
Title: Programs to Circuits: Towards a Programming Language for Cryptography

Modern cryptography (e.g., secure multi-party computation, fully-homomorphic encryption, program obfuscation) commonly models computation as “circuits”. To make modern cryptography work for real-world programs, it is necessary to compile “programs” into compact “circuits”. The key difficulty is that programs make dynamic memory accesses, whereas circuits have static wiring. To address this challenge, we need efficient Oblivious RAM and oblivious algorithms.

In this talk, I will first describe Circuit ORAM, a new ORAM scheme that yields very small circuit size. Circuit ORAM shows the tightness of certain stronger interpretations of the well-known Goldreich-Ostrovsky lower bound.

Next, I will describe ObliVM, a programming framework that compiles real-life programs into compact circuits, while offering formal security guarantees.

Speaker: Sergey Gorbunov
Title: Leveled Fully Homomorphic Signatures from Standard Lattices

In a homomorphic signature scheme, a user Alice signs some large dataset x using her secret signing key and uploads the signed data to an untrusted remote server. The server can then run some computation y=f(x) over the signed data and homomorphically derive a short signature \sigma_{f,y} certifying that y is the correct output of the computation f. Anybody can verify the tuple (f, y, \sigma_{f,y}) using Alice’s public verification key and become convinced of this fact without having to retrieve the entire underlying data.

In this work, we construct the first (leveled) fully homomorphic signature schemes that can evaluate arbitrary circuits over signed data. Only the maximal depth d of the circuits needs to be fixed a-priori at setup, and the size of the evaluated signature grows polynomially in d, but is otherwise independent of the circuit size or the data size. Our solution is based on the (sub-exponential) hardness of the small integer solution (SIS) problem in standard lattices. In the standard model, we get a scheme with large public parameters whose size exceeds the total size of a dataset. In the random-oracle model, we get a scheme with short public parameters. In both cases, the schemes can be used to sign many different datasets. The complexity of verifying a signature for a computation f is at least as large as that of computing f, but can be amortized when verifying the same computation over many different datasets. Furthermore, the signatures can be made context-hiding so as not to reveal anything about the data beyond the outcome of the computation.

These results offer a significant improvement in capabilities and assumptions over the best prior homomorphic signature schemes, which were limited to evaluating polynomials of constant degree.

As a building block of independent interest, we introduce and construct a new object called homomorphic trapdoor functions (HTDF) which conceptually unites homomorphic encryption and signatures.

Joint work with Vinod Vaikuntanathan (MIT) and Daniel Wichs (Northeastern).

The Charles River Crypto Day is back! We now plan to make it a regular event held about once every two months. Please join us on Friday, October 24 at MIT for the first Crypto Day of 2014-2015.

Location: MIT Stata Center Building 32 Gates Tower, 8th floor Room G-882 (Hewlett).


9:00 – 9:30. Introduction/Coffee
9:30 – 10:30.
Ron Rivest, MIT
Spritz—A spongy RC4-like stream cipher and hash function
11:00 – 12:00. Allison Bishop Lewko, Columbia
Witness Encryption and Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption
12:00 – 2:00. Lunch (provided)
2:00 – 3:00. Alessandro Chiesa, ETH Zurich
Scalable Zero Knowledge via Cycles of Elliptic Curves
3:30 – 4:30. Alon Rosen, IDC Herzlia
An Algebraic Approach to Non-Malleability


Speaker: Ron Rivest (MIT)
Title/Abstract:  Spritz—A spongy RC4-like stream cipher and hash function

Abtract: We reconsider the design of the stream cipher RC4, and proposes an improved variant, which we call “Spritz”.

Our work leverages the considerable cryptanalytic work done on the original RC4 and its proposed variants. It also uses simulations extensively to search for biases and to guide the selection of intermediate expressions.

We estimate that Spritz can produce output with about 24 cycles/byte of computation. Furthermore, our statistical tests suggest that about 2^81 bytes of output are needed before one can reasonably distinguish Spritz output from random output; this is a marked improvement over RC4.

In addition, we formulate Spritz as a “sponge (or sponge-like) function,” (see Bertoni et al), which can Absorb new data at any time, and from which one can Squeeze pseudorandom output sequences of arbitrary length. Spritz can thus be easily adapted for use as a cryptographic hash function, an encryption algorithm, or a message-authentication code generator. (However, in hash-function mode, Spritz is rather slow.)

Joint work with Jacob Schuldt.

Speaker: Allison Bishop Lewko (Cloumbia U)
Title: Witness encryption and indistinguishability obfuscation from the multilinear subgroup elimination assumption

We present constructions of witness encryption and indistinguishability obfuscation along with security reductions to the multilinear subgroup elimination assumption. This assumption is a natural multilinear extension of the subgroup decision assumptions used in bilineargroups.

This talk is based on joint works with Gentry and Waters and with Gentry, Sahai and Waters.

Speaker: Alessandro Chiesa (ETH Zurich)
Title: Scalable Zero Knowledge via Cycles of Elliptic Curves

Abstract: Non-interactive zero-knowledge proofs for general NP statements are a powerful cryptographic primitive. Recent work has achieved theoretical constructions and working implementations of zero-knowledge proofs that are short and easy to verify.

Alas, all prior implementations suffer from severe scalability limitations: the proving key’s size and the prover’s space complexity grow with the size of the computation being proved.

The bootstrapping technique of Bitansky et al. (STOC 2013), following Valiant (TCC 2008), offers an approach to scalability, by recursively composing proofs, but it has never been realized in practice, due to enormous computational cost.

In this work, by leveraging new elliptic-curve cryptographic techniques, we achieve the first practical implementation of recursive proof composition, and thereby achieve the first implementation of *scalable zero knowledge*.

Joint work with Eli Ben-Sasson, Eran Tromer, and Madars Virza.

Speaker: Alon Rosen (IDC Herzliya)
Title: An Algebraic Approach to Non-Malleability

Abstract: I will present a new technique for constructing non-malleable protocols with only a single “slot”. Two direct byproducts of our ideas are a four round non-malleable commitment and a four round non-malleable zero-knowledge argument, the latter matching the round complexity of the best known zero-knowledge arguments (without the non-malleability requirement). The protocols are based on the existence of one-way functions and admit very efficient instantiations via standard homomorphic commitments and sigma protocols.

Our analysis relies on algebraic reasoning, and makes use of error correcting codes in order to ensure that committers’ tags differ in many coordinates. One way of viewing our construction is as a method for combining many atomic sub-protocols in a way that simultaneously amplifies soundness and non-malleability, thus requiring much weaker guarantees to begin with, and resulting in a protocol which is much trimmer in complexity compared to the existing ones.

Joint work with Vipul Goyal, Silas Richelson and Margarita Vald.