When: Friday, April 18

Where: BU, 665 Commonweath Avenue, 17 th Floor

Organizers: Henry Corrigan-Gibbs, Yael Kalai, Eran Tromer, Vinod Vaikuntanathan and Daniel Wichs

Program:

9:30–10:00	Coffee/Welcome
10:00–11:00	Cody Freitag (Northeastern) Unambiguous SNARGs for P from LWE with applications to PPAD hardness
11:30–12:30	Zeyu (Thomas) Liu (Yale) Snake-eye Resistant PKE from LWE for Oblivious Message Retrieval and Robust Encryption
12:30–1:30	Lunch (provided)
1:30–2:30	Josh Alman (Columbia) Fine-Grained Complexity in a World without Cryptography
3:00–4:00	Matt Green (Johns Hopkins) New adventures in applied secret-sharing

Abstracts

Title: Unambiguous SNARGs for P from LWE with applications to PPAD hardness

We construct the first unambiguous succinct non-interactive arguments (SNARGs) for P and
incrementally verifiable computation (IVC) for P from the polynomial hardness of learning with
errors (LWE). Unambiguity guarantees that it is computationally hard to find two distinct
accepting proofs for the same statement. As an application, we establish PPAD hardness based
on the polynomial hardness of LWE combined with a widely believed complexity assumption.
Central to our approach is a new notion of rate-1 witness-unambiguous batch arguments for
NP, which we construct from the polynomial hardness of LWE.

Based on joint work with Liyan Chen, Zhengzhong Jin, and Daniel Wichs.

Title: Snake-eye Resistant PKE from LWE for Oblivious Message Retrieval and Robust Encryption

In this work, we introduce snake-eye resistance, a new security property for public-key
encryption (PKE). This property ensures that a ciphertext—potentially adversarially
generated—cannot decrypt to the same plaintext under two different secret keys. Snake-eye
resistance is particularly useful for (1) preventing spamming attacks in oblivious message
retrieval (OMR) and (2) enabling efficient robust encryption schemes.
We first analyze the snake-eye resistance of lattice-based PKE schemes. Our study reveals that
while Regev05 and PVW08 satisfy this property, more efficient, state-of-the-art schemes like
Crystals-Kyber do not. To bridge this gap, we propose LWEmongrass, a new lattice-based PKE
scheme that is provably snake-eye resistant under the standard LWE assumption while
significantly improving efficiency over Regev05 and PVW08.
Applying LWEmongrass to OMR, we achieve a 12× speedup over existing spamming-attack-
resistant OMR schemes (conjectured in LT22 and proven in this work), while maintaining
provable security under the LWE assumption.
Additionally, we establish that snake-eye resistance implies robustness, yielding the first robust
lattice-based PKE scheme that avoids the inefficiencies of the KEM-DEM paradigm.
As a contribution of independent interest, we introduce two LWE variants with side information, which serve as key building blocks in our security proofs and enable reductions from standard
LWE for relevant parameter settings.
 

 This is a joint work with Katerina Sotiraki, Eran Tromer, and Yunhao Wang

Title: Fine-Grained Complexity in a World without Cryptography

Abstract: The study of fine-grained cryptography has proliferated in recent years due to its allure
of relying on weaker assumptions compared to standard cryptography. As fine-grained
cryptography only requires polynomial gaps between the adversary and honest parties, it seems
plausible to build primitives relying upon popular hardness assumptions about problems in P
such as k-SUM or Zero-k-Clique. The ultimate hope is that fine-grained cryptography could still
be viable even if all current cryptographic assumptions are false, such as if P=NP or if we live in
Pessiland where one-way functions do not exist.
In this talk, we’ll consider whether this approach is viable by studying fine-grained complexity
when all standard cryptographic assumptions are false. I’ll present two main results. First, I’ll
show that many candidate hardness assumptions for building fine-grained cryptography are no
longer options in Pessiland, since many popular fine-grained complexity problems are easy to
solve in the average-case when one-way functions do not exist. Second, I’ll show that barriers for
reductions in fine-grained complexity may be explained by problems in cryptography: finding
faster algorithms for computing discrete logarithms is equivalent to designing average-case
equivalence between k-SUM and some natural variants.
Based on joint work with Yizhi Huang and Kevin Yeo.

Title:  New adventures in applied secret-sharing

Secret sharing is one of the oldest tools in the cryptographic toolbox. Aside from its well-known applications to MPC and threshold cryptography, secret sharing has a variety of uses in privacy-preserving protocols, such as threshold PSI, traitor tracing, and privacy-preserving analytics. In this talk I will revisit the properties of secret sharing and discuss use-cases for an “anonymity” property in secret sharing schemes. At a high level, this property ensures that an insufficient set of shares (i.e., a set of shares that does not satisfy the secret sharing scheme’s access structure) enjoys stronger protections than simple privacy: an adversary should be unable to determine whether a given set of shares are even associated with the same secret, or the same dealer. I will then discuss practical applications of these schemes, including stalking detection for privacy-preserving location tags (e.g., Airtags), as well as improved privacy for threshold analytics. Finally I will discuss some of the practical and theoretical results around these constructions as well as several open questions.

When: Friday, Sep. 13.

Where: MIT, Room 32-D463 (Star).

Organizers: Henry Corrigan-Gibbs, Yael Kalai, Eran Tromer, Vinod Vaikuntanathan and Daniel Wichs

Program:

9:15–9:30	Coffee/Welcome
9:30–10:30	David Wu (UT Austin) Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation
10:45–11:45	Ran Canetti (BU) Towards general-purpose program obfuscation via local mixing
11:45–12:45	Lunch (provided)
12:45–1:45	Brent Waters (NTT Research & UT Austin) A New Approach for Non-Interactive Zero-Knowledge from Learning with Errors
2:00–3:00	Julia Len (MIT) Recent Developments in Authenticated Encryption

Abstracts

Speaker:  David Wu (UT Austin)

Title: Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation

Abstract: A succinct non-interactive argument (SNARG) for NP allows a prover to convince a verifier that an NP statement x is true with a proof whose size scales sublinearly with the size of the associated NP witness. A SNARG satisfies adaptive soundness if the malicious prover can choose the statement to prove after seeing the scheme parameters. In this talk, I will show how to construct an adaptively-sound SNARG for NP in the plain model assuming sub-exponentially-hard indistinguishability obfuscation and sub-exponentially-hard one-way functions. This gives the first adaptively-sound SNARG for NP from falsifiable assumptions. All previous constructions of SNARGs for NP either relied on non-falsifiable assumptions or achieved the weaker notion of non-adaptive soundness where the adversary has to declare its statement up front (before seeing the scheme parameters).

Based on joint works with Brent Waters.

Speaker: Ran Canetti (BU)

Title: Towards general-purpose program obfuscation via local mixing

Abstract: We explore the possibility of obtaining general-purpose obfuscation for all circuits by way of making only simple, local, functionality preserving random perturbations in the circuit structure. Towards this goal, we use the additional structure provided by reversible circuits, but no additional algebraic structure. Our approach is rooted in statistical mechanics and can be thought of as locally “thermalizing” a circuit  while preserving its functionality.

We analyze the security of this approach in two steps.  First, we provide arguments towards its security for a relatively simple task: obfuscating random circuits of bounded length. Next  we show how to construct indistinguishability obfuscators for all (unbounded length) circuits given an obfuscator for random  reversible circuits of  bounded length.  Here security is proven under a new assumption regarding the pseudorandomness of sufficiently-long random reversible circuits.

Our specific candidate obfuscators are very simple and relatively efficient: the obfuscated version of an n-wire, m-gate (reversible) circuit with security parameter κ has n wires and poly(n, κ)m gates. We hope that our initial exploration will motivate further study of this alternative path to program obfuscation (and, hence, cryptography in general).

This is joint work with Claudio Chamon, Eduardo R. Mucciolo, and Andrei E. Ruckenstein.

Speaker: Brent Waters (NTT Research & UT Austin)

Title: A New Approach for Non-Interactive Zero-Knowledge from Learning with Errors

Abstract: I will put forward a new approach for achieving non-interactive zero-knowledge proofs (NIKZs) from the learning with errors (LWE) assumption. I will describe a LWE-based construction of a hidden bits generator that gives rise to a NIZK via the celebrated hidden bits paradigm. A notable feature of the construction is its simplicity. Our construction employs lattice trapdoors, but beyond that uses only simple operations. Unlike prior solutions, it does not rely on a correlation intractability argument nor does it utilize fully homomorphic encryption techniques.

Speaker: Julia Len (MIT)

Title: The Next Generation of Authenticated Encryption

Abstract:

This talk will focus on the need for a new approach for designing authenticated encryption with associated data (AEAD). In the last few years, researchers and practitioners have discovered that widely deployed AEAD schemes, designed almost two decades ago, have many limitations. These range from uncomfortably small security margins to outright security vulnerabilities.

First, this talk will focus on the importance of context commitment security, which asks that AEAD schemes will not decrypt the same adversarially-chosen ciphertext under two different, adversarially-chosen contexts (secret key, associated data, and nonce). A spate of recent attacks have shown that many popular schemes, including AES-GCM and ChaCha20/Poly1305, are not context committing. We resolve open questions
around the commitment security of other important schemes such as CCM, EAX, and SIV. Finally, this talk will discuss our ongoing work to design new schemes that resolve the above limitations, laying the foundation for a new generation of AEAD schemes. Our approach is what we refer to as flexible AEAD.

This is joint work with Mihir Bellare, John Chan, Paul Grubbs, Shay Gueron, Viet Tung Hoang, Sanketh Menda, Thomas Ristenpart, and Phillip Rogaway.

When: Friday, March 8

Where: Northeastern University, West Village H, Room 366

Organizers: Ran Canetti, Henry Corrigan-Gibbs, Yael Kalai, Eran Tromer, Vinod Vaikuntanathan and Daniel Wichs

Program:

9:00 – 9:30	Welcome and Breakfast
9:30 – 10:30	Rahul Ilango (MIT) Beating Brute Force for Compression Problems
10:45 – 11:45	Marshall Ball (NYU) Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement
11:45 – 1:30	Lunch (provided)
1:30 – 2:30	Neekon Vafa (MIT) Memory Checking Requires Logarithmic Overhead
2:45 – 3:45	Stefano Tessaro (UW) The t-wise Independence of Substitution Permutation Networks
4:00-5:00	Ben Edelman (Harvard) Watermarks in the Sand: Impossibility of Strong Watermarking for Generative Models

 

Abstracts

Speaker:  Rahul Ilango (MIT)

Title: Beating Brute Force for Compression Problems

Abstract: A compression problem is defined with respect to an efficient encoding function f; given a string x, the goal is to find the shortest y such that f(y)=x. The obvious brute-force algorithm for solving this compression task on n-bit strings runs in time about 2^s, where s is the length of the shortest description y.

Speaker: Marshall Ball (NYU)

Title: Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement

Abstract: Only a handful candidates for computational assumptions that imply secure key-agreement protocols (KA) are known, and even fewer are believed to be quantum safe. In this work, we present a new hardness assumption – the worst-case hardness of a promise problem related to an interactive version of Kolmogorov Complexity.

Roughly speaking, the promise problem requires telling apart tuples of strings (\pi,x,y) with relatively (w.r.t. K(\pi)) low time-bounded Interactive Kolmogorov Complexity (IK^t), and those with relatively high Kolmogorov complexity, given the promise that K^t(x|y)< s, K^t(y|x)< s and s = log n, and where IK^t(\pi;x;y) is defined as the length of the shortest pair of t-bounded TMs (A,B) such that the interaction of (A,B) lead to the transcript \pi and the respective outputs x,y.

We demonstrate that when t is some polynomial, then not only does this hardness assumption imply the existence of KA, but it is also necessary for the existence of secure KA. As such, it yields the first natural hardness assumption characterizing the existence of key-agreement protocols.

We additionally show that if the threshold s is made just slightly bigger (e.g., s = 55log n), then the (worst-case) hardness of this problem instead characterizes the existence of one-way functions (OWFs). As such, our work also clarifies exactly what it would take to base KA on the existence of OWFs, and demonstrates that this question boils down to demonstrating a worst-case reduction between two closely related promise problems.

Based on joint work with Yanyi Liu, Noam Mazor, and Rafael Pass.

Speaker: Neekon Vafa (MIT)

Title: Memory Checking Requires Logarithmic Overhead

Abstract: In this talk, we present the first general tight lower bound on the complexity of memory checkers with computational security.

Memory checkers, first introduced over 30 years ago by Blum, Evans, Gemmel, Kannan, and Naor (FOCS ’91, Algorithmica ’94), allow a user to store and maintain a large memory on a remote and unreliable server by using small trusted local storage. The user can issue instructions to the server and after every instruction, obtain either the correct value or a failure (but not an incorrect answer) with high probability. The main complexity measure of interest is the size of the local storage and the number of queries the memory checker makes upon every logical instruction. The most efficient known construction has query complexity O(log n/loglog n) and local space proportional to a computational security parameter, assuming one-way functions, where n is the logical memory size. Dwork, Naor, Rothblum, and Vaikuntanathan (TCC ’09) showed that for a restricted class of “deterministic and non-adaptive” memory checkers, this construction is optimal, up to constant factors. However, going beyond the small class of deterministic and non-adaptive constructions has remained a major open problem.

In this talk, we fully resolve the complexity of memory checkers by showing that any construction with local space p and query complexity q must satisfy p >= n/(log n)^O(q). This implies, as a special case, that q >= \Omega(log n/loglog n) in any scheme, assuming that p <= n^0.999. The bound applies to any scheme with computational security, completeness 2/3, and inverse polynomial in n soundness (all of which make our lower bound only stronger). We further extend the lower bound to schemes where the read complexity q_r and write complexity q_w differ. For instance, we show the tight bound that if q_r = O(1) and p <= n^0.999, then q_w >= n^{\Omega(1)}. This is the first lower bound, for any non-trivial class of constructions, showing a read-write query complexity trade-off.

Our proof is via a delicate compression argument showing that a “too good to be true” memory checker can be used to compress random bits of information. We draw inspiration from tools recently developed for lower bounds for relaxed locally decodable codes. However, our proof itself significantly departs from these works, necessitated by the differences between settings.

Joint work with Elette Boyle and Ilan Komargodski.

Speaker: Stefano Tessaro (UW)

Title: The t-wise Independence of Substitution Permutation Networks

Abstract: Block ciphers like AES are used ubiquitously in applied cryptography
to instantiate pseudorandom functions (PRFs). However, their structure
differs substantially from that of theoretical PRF constructions, and
standard tools from provable security are inherently incompatible with
their analysis. Nonetheless, despite a lack of security proofs, block
cipher constructions are natural, mathematically elegant, and decades
of in-depth cryptanalysis have failed to make a dent in the security
of many proposed designs.

This talk will focus on an ongoing agenda aimed at proving security of
block ciphers against limited classes of attacks. We will focus on
proving that Substitution Permutation Networks (SPNs), the block
cipher family that includes AES, give us t-wise independent
permutations. This is a weak property (compared to being a
full-fledged PRF), but several classical families of statistical
cryptanalytic attacks (including linear and differential
cryptanalysis) would invalidate it if successful. This line of work is
in contrast with prior works aiming at full proofs of security for
strongly idealized versions of block ciphers.

Based on joint works with Tianren Liu (Peking University), Angelos
Pelecanos (Berkeley) and Vinod Vaikuntanathan (MIT).

Speaker: Ben Edelman (Harvard)

Title: Watermarks in the Sand: Impossibility of Strong Watermarking for Generative Models

Abstract: Watermarking generative models consists of planting a statistical signal (watermark) in a model’s output so that it can be later verified that the output was generated by the given model. We will motivate generative watermarking of AI outputs, and contrast it with the traditional notion of digital watermarking. Then, we will describe our argument that if several natural assumptions about the setting hold, then it is impossible for a generative watermarking scheme to be robust to quality-preserving erasure attacks from bounded attackers. The impossibility result is a consequence of a generic efficient watermark attack; we demonstrate the feasibility of the attack with a proof-of-concept implementation which successfully removes watermarks implanted by three existing watermarking schemes for large language models.

Based on https://arxiv.org/abs/2311.04378. Joint work with Hanlin Zhang, Danilo Francati, Daniele Venturi, Giuseppe Ateniese, and Boaz Barak.

When: Friday, Oct. 20.

Where: MIT, Stata Center 32-G882

Organizers: Ran Canetti, Henry Corrigan-Gibbs, Yael Kalai, Eran Tromer, Vinod Vaikuntanathan and Daniel Wichs

Program:

9:30 – 10:00	Welcome and Breakfast
10:00 – 11:00	Tina Zhang (MIT) Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification
11:30 – 12:30	Aayush Jain (CMU) Multi-Party Homomorphic Secret Sharing from Sparse Learning Parity with Noise
12:30 – 2:00	Lunch (provided)
2:00 – 3:00	Hoeteck Wee (NTT Research & ENS) ABE for Circuits with poly(λ)-sized Keys from LWE
3:30 – 4:30	Ji Luo (U Washington) Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices

Abstracts

Speaker:  Tina Zhang (MIT)

Title: Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification

Abstract: We present a step towards the goal of producing a general cryptographic ‘compilation’ procedure which can translate any entangled nonlocal game into a single-prover interactive protocol while preserving quantum completeness and soundness, using cryptography to simulate the separation between the provers. A candidate for such a procedure was introduced by Kalai et al. (STOC ’23), who defined a black-box cryptographic compilation procedure that applies to any nonlocal game and showed that it preserves classical value. In this work, we make progress towards a full understanding of the quantum value of the single-prover protocols that result from applying the Kalai et al. compilation procedure to entangled games.
For the special case of CHSH, we prove that the Tsirelson bound holds under the compilation procedure introduced by Kalai et al., and we also recover a strong version of the ‘rigidity’ property that makes CHSH so useful. As an application, we give a single-prover cryptographically sound classical verification protocol for BQP, and we prove its soundness using our CHSH rigidity analysis. Our protocol replicates the functionality of Mahadev’s protocol (FOCS ’18) but with two advantages: (1) the protocol is conceptually intuitive and requires fewer bespoke ingredients, and the soundness analysis is simpler and directly follows the analysis of the nonlocal case, and (2) the soundness analysis does not explicitly use the assumption of a TCF or an adaptive hardcore bit, and only requires QFHE as a black box (though currently the only known constructions of QFHE use TCFs).

Joint work with Anand Natarajan; https://arxiv.org/abs/2303.01545.

Speaker: Aayush Jain (CMU)

Title: Multi-Party Homomorphic Secret Sharing from Sparse Learning Parity with Noise

Abstract: Over the past few years, homomorphic secret sharing (HSS) has emerged as a compelling alternative to fully homomorphic encryption (FHE), due to its feasibility from an array of standard assumptions and its potential efficiency benefits. However, all known HSS schemes, with the exception of schemes built from FHE or indistinguishability obfuscation (iO), can only support two or four parties.

In this talk, I will present our recent HSS construction that supports threshold corruption policies over arbitrary polynomial number of parties. Our construction supports evaluations of multivariate polynomials of degree log / log log  over arbitrary finite fields and can be based on the sparse Learning Parity with Noise (LPN) assumption, a standard variant of LPN with a sparse public matrix that has been studied and used in prior works. Curiously, the version of the assumption we use is not even known to imply a public key encryption as of now.

In this talk, I will describe the construction, some observations, and some prominent applications, notably,  a secure multiparty computation (MPC) protocol for any number of parties, with (slightly) sub-linear per-party communication of roughly O(S / \log \log S) bits when evaluating a layered Boolean circuit of size S. I will conclude with a few open questions.

Speaker: Hoeteck Wee (NTT Research & ENS)

Title: ABE for Circuits with poly(λ)-sized Keys from LWE

Abstract: We present a key-policy attribute-based encryption (ABE) scheme for
circuits based on the Learning With Errors (LWE) assumption whose key
size is independent of the circuit depth. Our result constitutes the
first improvement for ABE for circuits from LWE in almost a decade,
given by Gorbunov, Vaikuntanathan, and Wee (STOC 2013) and Boneh, et
al. (EUROCRYPT 2014), reducing the key size in the latter from
poly(depth, λ) to poly(λ). We present new lattice techniques to
eliminate the use of pairings and generic bilinear groups in the
recent ABE of Li, Lin, and Luo (TCC 2022) with poly(λ) key size.

Joint work with Valerio Cini (AIT).

Speaker: Ji Luo (U Washington)

Title: Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices

Abstract: Although we have known about fully homomorphic encryption (FHE) from circular security assumptions for over a decade [Gentry, FOCS ’10; Brakerski–Vaikuntanathan, STOC ’11], there is still a significant gap in understanding related homomorphic primitives supporting all *unrestricted* polynomial-size computations.  One prominent example is attribute-based encryption (ABE).  The state-of-the-art constructions, relying on the hardness of learning with errors (LWE) [Gorbunov–Vaikuntanathan–Wee, STOC ’13; Boneh et al., Eurocrypt ’14], only accommodate circuits up to all *predetermined* depth, akin to leveled homomorphic encryption.  In addition, their components (master public key, secret keys, and ciphertexts) have sizes polynomial in the maximum circuit depth.  Even in the simpler setting where a single key is published (or a single circuit is involved), the depth dependency persists, showing up in constructions of 1-key ABE and related primitives, including laconic function evaluation (LFE), 1-key functional encryption (FE), and reusable garbling schemes.  So far, the only approach of eliminating depth dependency relies on indistinguishability obfuscation.  Intriguingly, for over a decade, it has remained unclear whether the circular security assumptions empowering FHE can similarly benefit ABE.

In this work, we introduce new lattice-based techniques to overcome the depth-dependency limitations:

– Relying on a circular security assumption, we construct LFE, 1-key FE, 1-key ABE, and reusable garbling schemes capable of evaluating circuits of unbounded depth and size.

– Based on the *evasive circular* LWE assumption, a stronger variant of the recently proposed *evasive* LWE assumption [Wee, Eurocrypt ’22; Tsabary, Crypto ’22], we construct a full-fledged ABE scheme for circuits of unbounded depth and size.

Our constructions eliminate the multiplicative overheads polynomial in depth from previous constructions.  Our LFE, 1-key FE, and reusable garbling schemes achieve almost optimal succinctness.  Their ciphertexts and input encodings are proportional in length to the input, while function digest, secret keys, and garbled circuits maintain a constant size independent of circuit parameters.  Our ABE schemes offer short components, with master public key and ciphertext sizes linear in the attribute length and secret key being constant-size.

Joint work with Yao-Ching Hsieh and Rachel Lin.

A special crypto day in honor of Ran Canetti on the occasion of his 60th birthday.

Website: https://cryptowithcanetti.github.io/

When: Friday, May 12.

Where:  17th floor seminar room at BU’s new Center for Computing and Data Sciences, 665 Commonwealth Ave, Boston MA 02215.

Program:

9:30 – 10:00	Welcome and Breakfast
10:00 – 11:00	Luowen Qian (BU)
11:30 – 12:30	Rachel Lin (University of Washington) New Ways to Garble Arithmetic Circuits
12:30 – 2:00	Lunch (provided)
2:00 – 3:00	Justin Holmgren (NTT Research) Locally Covert Learning
3:30 – 4:30	Mayank Varia (BU) Protecting Cryptography Against Compelled Self-Incrimination
4:30	Reception

When: Friday, Mar 10.

Where:  17th floor seminar room at BU’s new Center for Computing and Data Sciences, 665 Commonwealth Ave, Boston MA 02215.

Organizers: Ran Canetti, Henry Corrigan-Gibbs, Yael Kalai, Vinod Vaikuntanathan and Daniel Wichs

Program:

9:30 – 10:00	Welcome and Breakfast
10:00 – 11:00	Eran Tromer (Columbia) Oblivious Message Retrieval
11:30 – 12:30	Noga Amit (Weizmann) Constant-round Arguments from One-way Functions
12:30 – 2:00	Lunch (provided)
2:00 – 3:00	Jiahui Liu (UT Austin) Collusion-Resistant Copy-Protection for Watermarkable Functionalities
3:30 – 4:30	James Bartusek (UC Berkeley) Obfuscation of Pseudo-Deterministic Quantum Circuits

---

Speaker: Eran Tromer (Columbia)

Title: Oblivious Message Retrieval

Abstract:

Anonymous message delivery systems, such as private messaging services and privacy-preserving blockchains, need a mechanism for recipients to retrieve the messages addressed to them, without leaking metadata or letting their messages be linked. Recipients could download all posted messages and scan for those addressed to them, but communication and computation costs are excessive at scale.

We show how untrusted servers can detect messages on behalf of recipients, and summarize these into a compact encrypted digest that recipients can easily decrypt. These servers operate obliviously and do not learn anything about which messages are addressed to which recipients. Privacy, soundness, and completeness hold even if everyone but the recipient is adversarial and colluding.

Furthermore, the model and constructions generalize to the setting of group messaging or mailing lists: senders can generate messages that would be efficiently detected by multiple recipients of their choice.

Our starting point is an asymptotically-efficient approach, using Fully Homomorphic Encryption and homomorphically-encoded Sparse Random Linear Codes. We then address the concrete performance using bespoke tailoring of lattice-based cryptographic components, alongside various algebraic and algorithmic optimizations. This reduces the digest size to a few bits per message scanned. Concretely, the servers’ cost is ~$1 per million messages scanned, and the resulting digests can be decoded by recipients in ~20ms. Our schemes can thus practically attain the strongest form of receiver privacy for current applications such as privacy-preserving cryptocurrencies.

(Covers https://eprint.iacr.org/2021/1256 and ongoing joint work with Zeyu Liu and Yunhao Wang.)

---

Speaker: Noga Amit (Weizmann)

Title: Constant-round Arguments from One-way Functions

Abstract: We study the following question: what cryptographic assumptions are needed for obtaining constant-round computationally-sound argument systems? We focus on argument systems with almost-linear verification time for subclasses of P, such as depth-bounded computations. Kilian’s celebrated work [STOC 1992] provides such 4-message arguments for P (actually, for NP) using collision-resistant hash functions. We show that one-way functions suffice for obtaining constant-round arguments of almost-linear verification time for languages in P that have log-space uniform circuits of linear depth and polynomial size. More generally, the complexity of the verifier scales with the circuit depth. Furthermore, our argument systems (like Kilian’s) are doubly-efficient; that is, the honest prover strategy can be implemented in polynomial-time. Unconditionally sound interactive proofs for this class of computations do not rely on any cryptographic assumptions, but they require a linear number of rounds [Goldwasser, Kalai and Rothblum, STOC 2008]. Constant-round interactive proof systems of linear communication (or verification) complexity are not known even for NC (indeed, even for AC^1).

Based on joint work with Guy Rothblum.

---

Speaker: Jiahui Liu (UT Austin)

Title: Collusion-Resistant Copy-Protection for Watermarkable Functionalities

Abstract: Copy-protection is the task of encoding a program into a quantum state to prevent illegal duplications. A line of recent works studied copy-protection schemes under “1 -> 2 attacks”: the adversary receiving one program copy can not produce two valid copies. However, under most circumstances, vendors need to sell more than one copy of a program and still ensure that no duplicates can be generated. In this work, we initiate the study of collusion resistant copy-protection in the plain model. Our results are twofold:

(*) The feasibility of copy-protecting all watermarkable functionalities is an open question raised by Aaronson et al. (CRYPTO’ 21). In the literature, watermarking decryption, digital signature schemes and PRFs have been extensively studied. For the first time, we show that digital signature schemes can be copy-protected. Together with the previous work on copy-protection of decryption and PRFs by Coladangelo et al. (CRYPTO’ 21), it suggests that many watermarkable functionalities can be copy-protected, partially answering the above open question by Aaronson et al.

(*) We make all the above schemes (copy-protection of decryption, digital signatures, and PRFs) k bounded collusion resistant for any polynomial k, giving the first bounded collusion resistant copy-protection for various functionalities in the plain model.

---

Speaker: James Bartusek (UC Berkeley)

Title: Obfuscation of Pseudo-Deterministic Quantum Circuits

Abstract: We will show how to obfuscate pseudo-deterministic quantum circuits in the classical oracle model, assuming the quantum hardness of learning with errors. Instantiating the classical oracle with a candidate post-quantum indistinguishability obfuscator, we obtain the first candidate construction of indistinguishability obfuscation for a class of circuits that is powerful enough to implement Shor’s algorithm.

Along the way, we construct a publicly-verifiable classical verification of quantum computation scheme for quantum “partitioning” circuits, which can be used to verify the evaluation procedure of Mahadev’s quantum fully-homomorphic encryption scheme. We achieve this by constructing a type of publicly-decodable “Pauli functional commitment” scheme, which must satisfy a notion of binding against committers that have access to both of the receiver’s standard and Hadamard basis decoding functionalities.

Based on joint work with Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa.

---

When: Friday, Dec 2.

Where:  17th floor seminar room at BU’s new CDS building  (665 Commonwealth Ave)

Organizers: Ran Canetti, Henry Corrigan-Gibbs, Yael Kalai, Vinod Vaikuntanathan and Daniel Wichs

Program:

9:00 – 9:30	Welcome and Breakfast
9:30 – 10:30	Prabhanjan Ananth (UCSB) Cloning Games: A General Framework for Unclonable Primitives
11:00 – 12:00	Fermi Ma (Simons/Berkeley) Commitments to Quantum States
12 – 1:30	Lunch (provided)
1:30 – 2:30	Zhengzhong Jin (MIT) Indistinguishability Obfuscation via Mathematical Proofs of Equivalence
3:00 – 4:00	Sam Hopkins (MIT) Differential Privacy versus Robustness: Black-Box Reductions and Efficient Algorithms

Speaker: Prabhanjan Ananth (UCSB)
Title: Cloning Games: A General Framework for Unclonable Primitives

Abstract:

The powerful no-cloning principle of quantum mechanics can be leveraged to achieve interesting primitives, referred to as unclonable primitives, that are impossible to achieve classically. In the past few years, we have witnessed a surge of new unclonable primitives. Understanding the relationship between the different unclonable primitives is still in its nascent stages and moving forward, we need a more systematic study of unclonable primitives.

We introduce a new framework called cloning games. We show that this framework captures many fundamental unclonable primitives such as quantum money, copy-protection, unclonable encryption, single-decryptor encryption and many more. By reasoning about different types of cloning games, we obtain many interesting implications to unclonable cryptography, including the following:

– We obtain the first construction of information-theoretically secure single-decryptor encryption in the one-time setting.
– We construct unclonable encryption in the quantum random oracle model based on BB84 states, improving upon the previous work which used coset states. Our work also provides a simpler security proof for the previous work.
– We construct copy-protection for single-bit point functions in the quantum random oracle model based on BB84 states, also improving upon the previous work which used coset states, and also achieving a simpler proof.
– We obtain an equivalence of copy-protection schemes with respect to different challenge distributions. Similarly, we also obtain an equivalence of single-decryptor encryption schemes with respect to different ciphertext distributions.

En route, we present a new toolkit that enables us to generically use classical techniques to build unclonable primitives.  

(Joint work with Fatih Kaleoglu and Qipeng Liu) 

Speaker: Fermi Ma (Simons/Berkeley)
Title: Commitments to Quantum States

Abstract:

What does it mean to commit to a quantum state? In this talk, I will present a simple, but perhaps counterintuitive answer: a quantum state commitment (QSC) is binding if sending the commitment erases the committed message from the sender’s view. Using this new definition, I will show how to construct the first succinct QSCs, which can be seen as an analog of collision-resistant hashing for quantum messages.

Commitments to quantum states open the door to many new cryptographic possibilities. Our flagship application is a quantum-communication version of Kilian’s succinct arguments for any language that has
quantum PCPs with constant error and polylogarithmic locality. Plugging in the PCP theorem, this yields succinct arguments for NP
under significantly weaker assumptions than required classically; moreover, if the quantum PCP conjecture holds, this extends to QMA. At the heart of our security proof is a new rewinding technique for
extracting quantum information.

Joint work with Sam Gunn, Nathan Ju, and Mark Zhandry.
https://eprint.iacr.org/2022/1358.pdf

Speaker: Zhengzhong Jin (MIT)
Title: Indistinguishability Obfuscation via Mathematical Proofs of Equivalence

Abstract:

Over the last decade, indistinguishability obfuscation (iO) has emerged as a seemingly omnipotent primitive in cryptography. Moreover, recent breakthrough work has demonstrated that iO can be realized from well-founded assumptions. A thorn to all this remarkable progress is a limitation of all known constructions of general-purpose iO: the security reduction incurs a loss that is exponential in the input length of the function. This “input-length barrier” to iO stems from the non-falsifiability of the iO definition and is discussed in folklore as being possibly inherent. It has many negative consequences; notably, constructing iO for programs with inputs of unbounded length remains elusive due to this barrier. 

We present a new framework aimed towards overcoming the input-length barrier. Our approach relies on short mathematical proofs of functional equivalence of circuits and Turing machines to avoid the brute-force input-by-input check employed in prior works.

 – We show how to obfuscate circuits that have efficient proofs of equivalence in Propositional Logic with a security loss independent of input length. 

 – Next, we show how to obfuscate Turing machines with unbounded length inputs, whose functional equivalence can be proven in Cook’s Theory PV. 

 – Finally, we demonstrate applications of our results to succinct non-interactive arguments and witness encryption, and provide guidance on using our techniques for building new applications.

To realize our approach, we depart from prior work and develop a new gate-by-gate obfuscation template that preserves the topology of the input circuit.

Joint work with Abhishek Jain.

Speaker: Sam Hopkins (MIT)
Title: Differential Privacy versus Robustness: Black-Box Reductions and Efficient Algorithms

Abstract:

I’ll discuss connections between robustness to adversarial corruption and differential privacy in high-dimensional statistical estimation problems; highlights include (1) a black-box reduction from privacy to robustness and (2) the first computationally-efficient algorithms for learning high-dimensional Gaussians privately with nearly-optimal sample complexity (and robustness).

Based on joint works with Kristian Georgiev, Gautam Kamath, Mahbod Majid, and Shyam Narayanan

ITC (July 5-7) + Crypto Day (July 8) = Crypto Week!

When: Crypto Day is on Friday, July 8, immediately after ITC (July 5-7).

Logistic: ITC requires a separate registration. No registration required for Crypto Day.

Where:  MIT Stata Center, Room 32-141.

To enter the building you need to sign in here: https://visitors.mit.edu/?event=1a6f4422-30c3-4e54-a94b-2371cae14cdd and receive a QR code.

Organizers: Ran Canetti, Henry Corrigan-Gibbs, Yael Kalai, Vinod Vaikuntanathan and Daniel Wichs

Program:

9:00 – 9:30	Welcome and Breakfast
9:30 – 10:30	Benny Applebaum (Tel Aviv University) – video Quadratic Multiparty Randomized Encodings Beyond Honest Majority and Their Applications
11:00 – 12:00	Rafael Pass (Cornell Tech) – video Leakage-Resilient Hardness v.s. Randomness
12 – 1:30	Lunch (provided)
1:30 – 2:30	Dakshita Khurana (UIUC) – video SNARGs for P from sub-exponential DDH and QR
3:00 – 4:00	Wei-Kai Lin (Northeastern) – video Optimal Single-Server Private Information Retrieval

Speaker: Benny Applebaum (Tel Aviv University)
Title: Quadratic Multiparty Randomized Encodings Beyond Honest Majority and Their Applications

Abstract:

Multiparty randomized encodings (Applebaum, Brakerski, and Tsabary, SICOMP 2021) reduce the task of securely computing a complicated multiparty functionality f to the task of securely computing a simpler functionality g. The reduction is non-interactive and preserves information-theoretic security against a passive (semi-honest) adversary, also referred to as {\em privacy}. The special case of a degree-2 encoding g (2MPRE) has recently found several applications to secure multiparty computation (MPC) with either information-theoretic security or making black-box access to cryptographic primitives. Unfortunately, as all known constructions are based on information-theoretic MPC protocols in the plain model, they can only be private with an honest majority.

In this work, we break the honest-majority barrier and present the first construction of general 2MPRE that remains secure in the presence of a dishonest majority. Our construction encodes every n-party functionality f by a 2MPRE that tolerates at most t=2n/3 passive corruptions. 

We derive several applications including (1) The first non-interactive client-server MPC protocol with perfect privacy against any coalition of a minority of the servers and up to t of the n clients; (2) Completeness of 3-party functionalities under non-interactive t-private reductions; and (3) A single-round t-private reduction from general-MPC to an ideal oblivious transfer (OT). These positive results partially resolve open questions that were posed in several previous works. We also show that t-private 2MPREs are necessary for solving (2) and (3), thus establishing new equivalence theorems between these three notions. Finally, we present a new approach for constructing fully-private 2MPREs based on multi-round protocols in the OT-hybrid model that achieve *perfect privacy* against *active* attacks. Moreover, by slightly restricting the power of the active adversary, we derive an equivalence between these notions. This forms a surprising and quite unique connection between a non-interactive passively-private primitive to an interactive actively-private primitive.

Based on joint work with Yuval Ishai, Or Karni, and Arpita Patra.

Speaker: Rafael Pass (Cornell Tech)
Title: Leakage-Resilient Hardness v.s. Randomness

Abstract:

A central open problem in complexity theory concerns the question of whether all efficient randomized algorithms can be simulated by efficient deterministic algorithms. The celebrated “hardness v.s. randomness” paradigm pioneered by Blum-Micali (SIAM JoC’84), Yao (FOCS’84) and Nisan-Wigderson (JCSS’94) presents hardness assumptions under which prBPP = prP, but these hardness assumptions are not known to also be necessary for such derandomization.

In this work, following the recent work by Chen and Tell (STOC’20) that considers “almost-all-input” hardness of a function f (i.e., hardness of computing f on more than a finite number of inputs), we consider “almost-all-input” *leakage-resilient hardness* of a function f—that is, hardness of computing f(x) even given, say, sqrt(|x|) bits of leakage of f(x). We show that leakage-resilient hardness characterizes derandomization of prBPP (i.e., gives a both *necessary* and *sufficient* condition for derandomization). In more detail, we show that there exists a constant c such that the following are equivalent:

• prBPP = P;
• Existence of a poly-time computable function f : {0, 1}^n -> {0,1}^n that is almost-all-input leakage-resilient hard with respect to n^c-time probabilistic algorithms.

Our characterization naturally extends also to the low-end derandomization regime, to derandomization of MA, and also to average-case derandomization, by appropriately weakening the requirements on the function f.

Joint work with Yanyi Liu

Speaker: Dakshita Khurana (UIUC)
Title: SNARGs for P from sub-exponential DDH and QR

Abstract:

Abstract: We will describe a construction of publicly-verifiable Succinct Non-Interactive Arguments (SNARGs) for arbitrary deterministic computations and bounded space non-deterministic computations from group-based assumptions, without relying on pairings. In particular, assuming the sub-exponential hardness of both the Decisional Diffie-Hellman (DDH) and Quadratic Residuosity (QR) assumptions, we obtain the following results, where n denotes the size of the instance:
1. A SNARG for any language that can be decided in non-deterministic time T and space S with communication complexity and verifier runtime (n+S).T^{o(1)}
2. A SNARG for any language that can be decided in deterministic time T with communication complexity and verifier runtime n.T^{o(1)}.

Speaker: Wei-Kai Lin (Northeastern)
Title: Optimal Single-Server Private Information Retrieval

Abstract:

In this talk, we present a single-server Private Information Retrieval (PIR) scheme, which allows a client to privately query the database from the server. Our construction achieves optimal bandwidth and server computation (up to poly-logarithmic factors), assuming the hardness of the Learning With Errors (LWE) problem.

In the setting of single-server PIR, the server stores an n-bit database, and the client wants to query some bits in the database privately and adaptively so that the server learns nothing about the indices of the queried bits. Our scheme uses ~O(√n) client storage, but it achieves amortized ~O(√n) server and client computation and ~O(1) bandwidth per query, and completes in a single roundtrip, where the ~O notation hides a security parameter and poly-logarithmic factor. In particular, we achieve a significant reduction in bandwidth over the state-of-the-art scheme by Corrigan-Gibbs, Henzinger, and Kogan (Eurocrypt’22): their scheme requires as much as ~O(√n) bandwidth per query, with comparable computational and storage cost as ours. Since they proved that their scheme is nearly optimal in terms of server computation and client storage, our scheme is additionally optimal in bandwidth.

This is a joint work with Mingxun Zhou, Yiannis Tselekounis, and Elaine Shi.

When: Crypto Day on Friday, April 29.

Where:  Northeastern University, ISEC building (805 Columbus Ave), Room 655 (6th floor)

Logistics: Masks are optional for fully vaccinated attendees.

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

Program:

9:00 – 9:30	Welcome and Breakfast
9:30 – 10:30	Zvika Brakerski, Weizmann Institute, Constructive Post-Quantum Reductions (video)
11:00 – 12:00	David Wu, UT Austin Batch Arguments for NP and More from Standard Bilinear Group Assumptions (video)
12 – 1:30	Lunch (provided)
1:30 – 2:30	Rahul Ilango, MIT The Minimum Circuit Size Problem: What is it, what’s new, and where might things go? (video)
3:00 – 4:00	Alexandra Henzinger, MIT Single-Server Private Information Retrieval with Sublinear Amortized Time (video)

Speaker: Zvika Brakerski (Weizmann Institute)
Title: Constructive Post-Quantum Reductions

Abstract:

Is it possible to convert classical cryptographic reductions into post-quantum ones? It is customary to argue that while this is problematic in the interactive setting, non-interactive reductions do carry over. However, when considering quantum auxiliary input, this conversion results in a non-constructive post-quantum reduction that requires duplicating the quantum auxiliary input, which is in general inefficient or even impossible. This violates the win-win premise of provable cryptography: an attack against a cryptographic primitive should lead to an algorithmic advantage.

We initiate the study of constructive quantum reductions and present positive and negative results for converting large classes of classical reductions to the post-quantum setting in a constructive manner. We show that any non-interactive non-adaptive reduction from assumptions with a polynomial solution space (such as decision assumptions) can be made post-quantum constructive. In contrast, assumptions with super-polynomial solution space (such as general search assumptions) cannot be generally converted.

Along the way, we make several additional contributions:

1. We put forth a framework for reductions (or general interaction) with stateful solvers for a computational problem, that may change their internal state between consecutive calls. We show that such solvers can still be utilized. This framework and our results are meaningful even in the classical setting.

2. A consequence of our negative result is that quantum auxiliary input that is useful against a problem with a super-polynomial solution space cannot be generically “restored” post-measurement. This shows that the novel rewinding technique of Chiesa et al. (FOCS 2021) is tight in the sense that it cannot be extended beyond a polynomial measurement space.

Joint work with Nir Bitansky and Yael Kalai.

Speaker: David Wu, UT Austin
Title: Batch Arguments for NP and More from Standard Bilinear Group Assumptions

Abstract:

Non-interactive batch arguments for NP provide a way to amortize the cost of NP verification across multiple instances. They enable a prover to convince a verifier of multiple NP statements with communication much smaller than the total witness length and verification time much smaller than individually checking each instance.

In this talk, we introduce a direct approach for constructing batch arguments from standard bilinear map assumptions (e.g., subgroup decision or k-Lin) which avoids heavy tools like correlation-intractable hash functions or probabilistically-checkable proofs common to previous approaches. In turn, we obtain the first construction of batch arguments for NP from standard bilinear map assumptions.

As corollaries to our main construction, we also obtain a delegation scheme for RAM programs (i.e., a SNARG for P) as well as an aggregate signature scheme supporting bounded aggregation from standard bilinear map assumptions in the plain model.

Joint work with Brent Waters

Speaker: Rahul Ilango
Title: The Minimum Circuit Size Problem: What is it, what’s new, and where might things go?

Title: The Minimum Circuit Size Problem: What is it, what’s new, and where might things go?

Abstract:

In this talk, I will give a broad introduction to the Minimum Circuit Size Problem (and, more generally, the area of “meta-complexity”) and then survey some exciting recent developments. These new developments include:
a) equivalences between the existence of one-way functions and average-case hardness of the Minimum Circuit Size Problem,
b) worst-case to average-case reductions for NP via meta-complexity, and
c) a framework building towards reducing SAT to the Minimum Circuit Size Problem.
No prior background on this topic is required!

This survey is based on many works by many authors, including (non-exhaustively): Eric Allender, Lijie Chen, Mahdi Cheraghchi, Shuichi Hirahara, Yanyi Liu, Bruno Loff, Dimitrios Myrisiotis, Igor Oliveira, Rafael Pass, Hanlin Ren, Rahul Santhanam, Harsha Tirumala, Neekon Vafa, and Ilya Volkovich.

Speaker: Alexandra Henzinger, MIT
Single-Server Private Information Retrieval with Sublinear Amortized Time

Abstract:

This talk will present new private-information-retrieval protocols in the single-server setting. These schemes allow a client to privately fetch a sequence of database records from a server, while the server answers each query in average time sublinear in the database size. 

Specifically, we introduce the first single-server private-information-retrieval schemes that have sublinear amortized server time, require sublinear additional storage, and allow the client to make her queries adaptively. Our protocols rely only on standard cryptographic assumptions (decision Diffie-Hellman, quadratic residuosity, learning with errors, etc.). They work by having the client first fetch a small “hint” about the database contents from the server. Generating this hint requires server time linear in the database size. Thereafter, the client can use the hint to make a bounded number of adaptive queries to the server, which the server answers in sublinear time—yielding sublinear amortized cost. 

Finally, we give lower bounds proving that our most efficient scheme is optimal with respect to the trade-off it achieves between server online time and client storage.

This talk is based on joint work with Henry Corrigan-Gibbs and Dmitry Kogan.