# Friday, July 23 (In Person!)

What: A special *IN-PERSON* crypto day on Friday, July 23 at Northeastern

We’re very excited to bring the Boston-area crypto community back together for a special in-person crypto day. We can’t wait to see all of you in person again!

Where: Northeastern University, ISEC building (805 Columbus Ave), first floor auditorium (room 102).

Logistics: Masks are optional for fully vaccinated participants and required for everyone else. The talks will be in a large auditorium to give participants plenty of room to socially distance if desired. No food or drinks are allowed in the auditorium. Lunch will be served on the 6th floor in room 655.

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

### Abstracts:

Speaker:  Jon Ullman, Northeastern University
Title:  The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation

Abstract: There has been a recent wave of interest in intermediate trust models for differential privacy that eliminate the need for a fully trusted central data collector, but overcome the limitations of local differential privacy. This interest has led to the introduction of the shuffle model (Cheu et al., EUROCRYPT 2019; Erlingsson et al., SODA 2019) and revisiting the pan-private model (Dwork et al., ITCS 2010). The message of this line of work is that, for a variety of low-dimensional problems — such as counts, means, and histograms — these intermediate models offer nearly as much power as central differential privacy. However, there has been considerably less success using these models for high-dimensional learning and estimation problems. In this work, we show that, for a variety of high-dimensional learning and estimation problems, both the shuffle model and the pan-private model inherently incur an exponential price in sample complexity relative to the central model. For example, we show that, private agnostic learning of parity functions over $d$ bits requires $Ω(2^{d/2})$ samples in these models, and privately selecting the most common attribute from a set of $d$ choices requires $Ω(d^{1/2})$ samples, both of which are exponential separations from the central model. Our work gives the first non-trivial lower bounds for these problems for both the pan-private model and the general multi-message shuffle model.

Joint work with Albert Cheu

Speaker:  Hoeteck Wee, NTT Research
Title: Breaking the sqrt(N) Barrier in Pairing-Based Broadcast Encryption

Abstract: We present the first pairing-based ciphertext-policy attribute-based
encryption (CP-ABE) scheme for the class of degree 3 polynomials with
compact parameters: the public key, ciphertext and secret keys
comprise O(n) group elements, where n is input length for the
function. As an immediate corollary, we obtain a pairing-based
broadcast encryption scheme for N users with O(N^{1/3})-sized
parameters, breaking the long-standing sqrt{N} barrier for pairing-based
against unbounded collusions, and rely on the (bilateral) $k$-Lin
assumption in prime-order bilinear groups.

Speaker:  Zhengzhong Jin, Johns Hopkins University
Title:  SNARGs for P from LWE

Abstract: We provide the first construction of a succinct non-interactive argument (SNARG) for *all* polynomial time deterministic computations based on standard assumptions. For T steps of computation, the size of the proof and the common random string (CRS) as well as the verification time are poly-logarithmic in T. The security of our scheme relies on the hardness of the Learning with Errors (LWE) problem against polynomial-time adversaries. Previously, SNARGs based on standard assumptions could support bounded-depth computations and required sub-exponential hardness assumptions [Jawale-Kalai-Khurana-Zhang, STOC’21].

Along the way, we also provide the first construction of non-interactive batch arguments for NP based solely on the LWE assumption.

Based on the joint work with Arka Rai Choudhuri and Abhishek Jain.

Speaker: Yael Tauman Kalai, MSR and MIT
Title:  Somewhere Statistical Soundness, Post-Quantum Security, and SNARGs

Abstract:

We introduce the notion of a somewhere statistically sound (SSS) interactive argument, which is a hybrid between a statistically sound proof and a computationally sound proof.We show that Kilian’s protocol, instantiated with a computationally non-signaling PCP (Brakerski, Holmgren, and Kalai, STOC 2017) and a somewhere statistically binding hash family (Hubacek and Wichs, ITCS 2015), is an SSS argument.  We observe that the first two messages of Kilian, instantiated with these primitives, is a sound instantiation of the BMW heuristic (Kalai, Raz, Rothblum, STOC 2013).  Armed with this observation, we show how to efficiently convert any succinct non-interactive argument (SNARG) for BatchNP into a SNARG for any language that has a non-signaling PCP, including any deterministic language and any language in NTISP, using a somewhere statistically binding hash family.

Secondly, we show that the soundness of SSS arguments can be proved in a straight-line manner, implying that they are also post-quantum sound if the underlying assumption is post-quantum secure. This provides a straightforward proof that Kilian’s protocol, instantiated this way, is post-quantum sound under the post-quantum hardness of LWE (though we emphasize that a computationally non-signaling PCP exists only for deterministic languages and for specific subclasses of non-deterministic languages such as NTISP, but not for all of NP).  We put forward a natural conjecture that constant-round SSS arguments can be soundly converted into non-interactive arguments via the Fiat-Shamir transformation. We argue that SSS arguments evade the current Fiat-Shamir counterexamples, including the one for Kilian’s protocol (Bartusek, Bronfman, Holmgren, Ma and Rothblum, TCC 2019) by requiring additional properties from both the hash family and the PCP.

This is joint work with Vinod Vaikuntanathan and Rachel Zhang.

Speaker:  Rishab Goyal, MIT
Title: Dynamic Collusion Bounded Functional Encryption from Identity-Based Encryption

Abstract: Functional Encryption is a powerful notion of encryption in which each decryption key is associated with a function $f$ such that decryption recovers the function evaluation $f(m)$. Informally, security states that a user with access to function keys $\mathsf{sk}_{f_1}, \mathsf{sk}_{f_2}, \ldots$ (and so on) can only learn $f_1(m), f_2(m), \ldots$ (and so on) but nothing more about the message. The system is said to be $q$-bounded collusion resistant if the security holds as long as an adversary gets access to at most $q = q(\lambda)$ function keys. A major drawback of such \emph{statically} bounded collusion systems is that the collusion bound $q$ must be declared at setup time and is fixed for the entire lifetime of the system.
We initiate the study of \emph{dynamically} bounded collusion resistant functional encryption systems which provide more flexibility in terms of selecting the collusion bound, while reaping the benefits of statically bounded collusion FE systems (such as quantum resistance, simulation security, and general assumptions).
Briefly, the virtues of a dynamically bounded scheme can be summarized as:

1) [Fine-grained individualized selection.] It lets each encryptor select the collusion bound by weighing the trade-off between performance overhead and the amount of collusion resilience.
2) [Evolving encryption strategies.] Since the system is no longer tied to a single collusion bound, thus it allows to dynamically adjust the desired collusion resilience based on any number of evolving factors such as the age of the system, or a number of active users, etc.
3) [Ease and simplicity of updatability.] None of the system parameters have to be updated when adjusting the collusion bound. That is, the same key $\mathsf{sk}_f$ can be used to decrypt ciphertexts for collusion bound $q = 2$ as well as $q = 2^\lambda$.

We construct such a dynamically bounded functional encryption scheme for the class of all polynomial-size circuits under the general assumption of Identity-Based Encryption.

joint work with Rachit Garg, George Lu and Brent Waters