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.

Program:

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

Abstracts:

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.

Advertisements

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.

Program:

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

Abstracts:

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.

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, Feb 16 at MIT.

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

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

Thanks: NSF MACS Project for their generous support.

Program:

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

Abstracts:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

When: Friday, December 15 at Northeastern.

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

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

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

Thanks: NSF MACS Project for their generous support.

Program:

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

Abstracts:

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

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

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

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

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

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

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

 

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

 

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

Speaker: Adam Smith,BU
Title:  Learning with Fully Distributed Private Protocols

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

 

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

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

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

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

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

Thanks: NSF MACS Project for their generous support.

Program:

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

Abstracts:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

joint work with Giorgos Zirdelis.