Crypto Day: March 8 at Northeastern
Daniel Wichs
The organizers (Ran Canetti, Henry Corrigan-Gibs, Yael Kalai, Eran Tromer, Vinod Vaikuntanathan and Daniel Wichs)
Daniel Wichs
When: Friday, Oct. 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.
In this talk, I will discuss how to show that every compression problem has a Boolean circuit family which finds short descriptions more efficiently than brute force. In particular, our circuits have size roughly 2^{4s/5}. Our construction builds on Fiat-Naor’s data structure for function inversion [SICOMP 1999]: we show how to carefully modify their data structure so that it can be nontrivially implemented using Boolean circuits, and we show how to utilize hashing so that the circuit size is only exponential in the description length.
As a consequence, the Minimum Circuit Size Problem for generic fan-in two circuits of size s(n) on truth tables of size 2n can be solved by circuits of size 2{4/5 w+o(w}
poly(2n), where w=s(n)log2(s(n)+n). This improves over the brute-force approach of trying all possible size-s(n) circuits for all s(n) >= n.
This talk is based on joint work with Shuichi Hirahara and Ryan Williams, which will be merged with concurrent and independent work of Noam Mazor and Rafael Pass.
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.
Daniel Wichs
Dear Friends, Colleagues, Cryptographers:We hope to see you on Friday, March 8 @ Northeastern for crypto day. The program of talks is now up, see also below.Note: It's being held in West Village H, which is a different building than the last few iterations at Northeastern.Best,The organizers (Ran Canetti, Henry Corrigan-Gibs, Yael Kalai, Eran Tromer, Vinod Vaikuntanathan and Daniel Wichs)-----------------
When: Friday, March. 8