Back to Events

Seminar Series

July 26

Ran Gelles: Optimal Short-Circuit Resilient Formulas

Ran Gelles, Bar Ilan University

Part Of

10:30A
- 12:00P

Location

Hewlett, G882
Add to Calendar 2019-07-26 10:30:00 2019-07-26 12:00:00 America/New_York Ran Gelles: Optimal Short-Circuit Resilient Formulas Abstract: We consider fault-tolerant boolean formulas in which the output of a faulty gate is short-circuited to one of the gate’s inputs. A recent result by Kalai et al. [FOCS 2012] converts any boolean formula into a resilient formula of polynomial size that works correctly if less than a fraction 1/6 of the gates (on every input-to-output path) are faulty. We improve the result of Kalai et al., and show how to efficiently fortify any boolean formula against a fraction 1/5 of short-circuit gates per path, with only a polynomial blowup in size. We additionally show that it is impossible to obtain formulas with higher resilience and sub-exponential growth in size.Towards our results, we consider interactive coding schemes when noiseless feedback is present; these produce resilient boolean formulas via a Karchmer-Wigderson relation. We develop a coding scheme that resists up to a fraction 1/5 of corrupted transmissions in each direction of the interactive channel. We further show that such a level of noise is maximal for coding schemes with sub-exponential blowup in communication. Our coding scheme takes a surprising inspiration from Blockchain technology.Joint work with Mark Braverman, Klim Efremenko, and Michael Yitayew Hewlett, G882

October 11

Rotem Tsabary: Fully Secure Attribute-Based Encryption for t-CNF from LWE

Rotem Tsabary

Part Of

10:30A
- 12:00P

Location

Hewlett, G882
Add to Calendar 2019-10-11 10:30:00 2019-10-11 12:00:00 America/New_York Rotem Tsabary: Fully Secure Attribute-Based Encryption for t-CNF from LWE Abstract: Attribute-based Encryption (ABE), first introduced by [SW05, GPSW06], is a public key encryption system that can support multiple users with varying decryption permissions. One of the main properties of such schemes is the supported function class of policies. While there are fully secure constructions from bilinear maps for a fairly large class of policies, the situation with lattice-based constructions is less satisfactory and many efforts were made to close this gap. Prior to this work the only known fully secure lattice construction was for the class of point functions (also known as IBE).In this talk we discuss the main challenges in proving full security of ABE schemes and new techniques to overcome those barriers. As a main result, we construct for the first time a lattice-based (ciphertext-policy) ABE for the function class t-CNF, which consists of CNF formulas where each clause depends on at most t bits of the input, for any constant t. This class includes NP-verification policies, bit-fixing policies and t-threshold policies. Towards this goal we also construct a fully secure single-key constrained PRF from OWF for the same function class, which might be of independent interest. Hewlett, G882

Adrienne Mannov: A Call for Crypto-Anthropology

Adrienne Mannov, PhD. Social Anthropologist, Aalborg University, Denmark

Part Of

4:00P
- 5:00P

Location

PLEASE NOTE ROOM is G575
Add to Calendar 2019-10-11 16:00:00 2019-10-11 17:00:00 America/New_York Adrienne Mannov: A Call for Crypto-Anthropology Abstract: As a social anthropologist, cryptography is interesting because what counts as secure, what constitutes trust, and how sensitive information is perceived are not only cryptographic questions but deeply social ones. Anthropologists study societal and cultural praxes, processes and perceptions, and information security and cryptography are becoming important themes for such inquiries. In this talk, I invite you to be curious about how anthropologists explore notions of security, privacy and trust and how this might be relevant to your work. I suggest that joining forces across disciplines could be mutually beneficial for commercial applications, offer new ways to think methodologically together, and offer a platform for much needed societal debate and critique.From a commercial perspective, there seems to be a disconnect between developing new cryptographic primitives and getting these brilliant schemes adopted for actual use (Anderson 1994; Whitten and Tygar 2005). This is connected to what appears to be a narrative about how tasks are distributed: We start with math and crypto, which is then passed on to engineers who develop software. From there, policies and laws are developed and hardware issues are addressed. But the final step, adoption by users, is problematic. If users do not recognize the need for information security tools or are not able to understand them well enough to be convinced that they work, all the other steps are for naught. Perhaps we should re-think this distribution of tasks. When users’ existing practices, perceptions and life conditions are embedded in designs from the beginning, they are more successful.The narrative above describes a movement from the general and abstract (math) to the specific and practical (users), with each step separate from the others. What if we designed cryptographic tools by thinking athwart (Cf. Helmreich 2009)? Placing math and social analysis next to each other, and tacking back and forth between them, offers a different methodological construct (Mannov, Andersen, and Bruun, n.d.). It places, for example, actual social trust and cryptographic trust schemes next to each other, showing more clearly how they agree or contradict (Bruun, Mannov, and Andersen n.d.). Similar questions can be asked about “security” (von Schnitzler 2008), “risk” (Cf. Appel 2012) and “privacy”.Bringing our disciplines together in this way is new and it represents an opportunity: The Snowden revelations and Cambridge Analytica’s recent abuses have changed the way citizens think about data security and the time may be right for launching a nuanced public debate. Addressing the socio-mathematical issues of trust, privacy and security together positions us to offer well-informed criticism on issues such as data-citizens’ rights (Taylor 2017) and surveillance capitalism (Zuboff 2019). PLEASE NOTE ROOM is G575

October 18

Christopher Peikert: Noninteractive Zero Knowledge for NP from Learning With Errors

Christopher Peikert, University of Michigan (Ann Arbor)

Part Of

10:30A
- 12:00P

Location

Hewlett, G882
Add to Calendar 2019-10-18 10:30:00 2019-10-18 12:00:00 America/New_York Christopher Peikert: Noninteractive Zero Knowledge for NP from Learning With Errors Abstract:We finally close the long-standing problem of constructing anoninteractive zero-knowledge (NIZK) proof system for any NP languagewith security based on the Learning With Errors (LWE) problem, andthereby on worst-case lattice problems. Our proof system instantiatesa framework developed in a series of recent works for soundlyapplying the Fiat-Shamir transform using a hash function family thatis *correlation intractable* for a suitable class of relations.Previously, such hash families were based either on ``exotic''assumptions (e.g., indistinguishability obfuscation or optimalhardness of ad-hoc LWE variants) or, more recently, on the existenceof circularly secure fully homomorphic encryption. However, none ofthese assumptions are known to be implied by LWE or worst-casehardness.Our main technical contribution is a hash family that is correlationintractable for arbitrary size-S circuits, for any polynomiallybounded S, based on LWE (with small polynomial approximationfactors). Our construction can be instantiated in two possible``modes,'' yielding a NIZK that is either computationally sound andstatistically zero knowledge in the common random string model, orvice-versa in the common reference string model.Time permitting, we will also discuss some ongoing work on improving the efficiency of NIZKs from LWE. Hewlett, G882

October 25

Henry Yuen: Perfect zero knowledge for quantum multiprover interactive proofs

Henry Yuen, University of Toronto

Part Of

10:30A
- 12:00P

Location

Hewlett, G882
Add to Calendar 2019-10-25 10:30:00 2019-10-25 12:00:00 America/New_York Henry Yuen: Perfect zero knowledge for quantum multiprover interactive proofs Abstract: In a seminal 1988 paper, Ben-Or, Goldwasser, Kilian, and Wigderson (BGKW) introduced the model of multiprover interactive proofs (MIPs), and furthermore showed that zero knowledge can always be attained in this model without computational assumptions. Their paper has been enormously influential across cryptography and complexity theory, inspiring much research into zero knowledge, interactive proofs, PCPs, delegated computation, and more. In 2004, Cleve, Hoyer, Toner, and Watrous introduced the model of quantum multiprover interactive proofs (QMIPs), which are MIPs where the provers are allowed to share quantum entanglement (but still cannot communicate). The study of QMIPs has similarly been extremely fruitful in both quantum complexity theory and quantum cryptography. In this work, we prove the quantum analogue of BGKW's result: we show every quantum multiprover interactive proof can be transformed into an equivalent protocol that has the zero knowledge property. Since recent work has shown that QMIPs are capable of deciding extremely complex languages (such as nondeterministic *doubly-exponential* time), our result implies that such languages also have (quantum) zero knowledge proofs. The main techniques used in this paper is a procedure to compress quantum interactive protocols, and quantum error correcting codes. I will keep this talk self-contained and accessible; in particular I will not assume any background in quantum information. Hewlett, G882

November 08

Rishab Goyal: Mixed Functional Encryption: A new stepping stone towards efficient tracing

Rishab Goyal, University of Texas

Part Of

10:30A
- 12:00P

Location

G882
Add to Calendar 2019-11-08 10:30:00 2019-11-08 12:00:00 America/New_York Rishab Goyal: Mixed Functional Encryption: A new stepping stone towards efficient tracing Abstract: In a broadcast encryption (BE) system for N users, as introduced by Fiat and Naor, a sender can encrypt a message m to an arbitrary subset (unable to view) of users such that i-th user can decrypt, using its own private decryption key, (unable to view) . Although BE solves the problem of secure broadcast, it introduces the problem of accountability thereby enabling piracy attacks. To that end, Chor, Fiat, and Naor in the early 90s introduced the concept of traitor tracing (TT) capturing such piracy attacks when the sender can only broadcast to all N users. Informally, a TT system guarantees that if some of the N users collude to construct a pirate decoding box, then by running a special "Tracing" algorithm one can identify at least one of the secret keys used to construct the pirate device. The primary goal while designing such systems is to achieve short ciphertext size, ideally independent of N. Recently, in a joint work with Venkata Koppula and Brent Waters, we built the first fully collusion resistant compact TT scheme provably secure under the learning with errors (LWE) assumption. A vital component in our system was a new form of functional encryption (FE) that we called Mixed FE.Whilst this solves the piracy problem in broadcast systems when sender only broadcasts to all users, it does not allow for general broadcast along with providing tracing capability. Since we already have essentially optimal solutions to BE under bilinear maps, a natural question is whether the recent developments in TT could be combined with optimal BE systems to construct more general broadcast and trace systems. In this talk, I'll show that by a careful combination of LWE and bilinear maps we can improve the prior best construction of broadcast and trace (under standard assumptions) by Boneh and Waters. Central to this result is an augmented variant of Mixed FE, that we call Broadcast Mixed FE.Finally, I also describe an extension of regular TT systems in which the user keys are embedded with polynomial length identities that can be extracted by the tracing algorithm. This also builds upon the framework of Mixed FE, thereby showcasing the applicability of Mixed FE in broader tracing scenarios.Based on joint works with Venkata Koppula, Willy Quach, Brent Waters, and Daniel Wichs. G882

November 15

Daniel Wichs: Extracting Randomness from Exractor-Dependent Sources

Daniel Wichs, Northeastern University

Part Of

10:30A
- 12:00P

Location

Hewlett, G882
Add to Calendar 2019-11-15 10:30:00 2019-11-15 12:00:00 America/New_York Daniel Wichs: Extracting Randomness from Exractor-Dependent Sources Abstract: We revisit the well-studied problem of extracting nearly uniform randomness from an arbitrary source of sufficient min-entropy. Strong seeded extractors solve this problem by relying on a public random seed, which is unknown to the source. Here, we consider a setting where the seed is reused over time and the source may depend on prior calls to the extractor with the same seed. Can we still extract nearly uniform randomness? In more detail, we assume the seed is chosen randomly, but the source can make arbitrary oracle queries to the extractor with the given seed before outputting a sample. We require that the sample has entropy and differs from any of the previously queried values. The extracted output should look uniform even to a distinguisher that gets the seed. We provide constructions and lower bounds for extractors in this setting. joint work with Yevgeniy Dodis and Vinod Vaikuntanathan Hewlett, G882

November 22

Ashutosh Kumar: Securing Secret Sharing Against Leakage and Tampering

Ashutosh Kumar, UCLA

Part Of

10:30A
- 12:00P

Location

Hewlett, G882
Add to Calendar 2019-11-22 10:30:00 2019-11-22 12:00:00 America/New_York Ashutosh Kumar: Securing Secret Sharing Against Leakage and Tampering ABSTRACT: Secret sharing is one of the most classical and widely used cryptographic primitives. In the most basic and perhaps the most important setup, a secret needs to be shared between n parties such that any t of them can recover the secret but no fewer can gain any information even with collusion. As useful as this model, such schemes are still susceptible to attacks where someone 'tampers' or 'leaks' tiny amount of information from the parties. Here we seek to counteract such threats.We say that a scheme is p-party leakage-resilient if the secret remains statistically hidden even after an adversary learns a bounded amount of leakage, where each bit of leakage can depend jointly on the shares of an adaptively chosen subset of p parties. We rely on communication complexity lower bounds in the number-on-forehead model to transform any scheme into a p-party leakage-resilient one for p logarithmic in the number of parties. This yields the first multi-party schemes secure against adaptive and joint leakage.We say that a scheme is non-malleable if the secret is essentially `destroyed' in case an adversary tampers with (possibly all) the shares. This notion is inspired by the beautiful line of work on non-malleable codes. We transform any scheme into one that is non-malleable against an adversary who tampers with all the shares arbitrarily and independently. We also consider stronger adversaries who may jointly tamper multiple shares. All our constructions achieve information-theoretic security.Based on joint works with Vipul Goyal, Raghu Meka, and Amit Sahai. Hewlett, G882

December 06

Dhiraj Holden: No Signaling Proofs with sqrt(log n) Provers in PSPACE

Dhiraj Holden, MIT

Part Of

10:30A
- 12:00P

Location

G882, Hewlett
Add to Calendar 2019-12-06 10:30:00 2019-12-06 12:00:00 America/New_York Dhiraj Holden: No Signaling Proofs with sqrt(log n) Provers in PSPACE Abstract: No-signaling proofs, motivated by quantum computation, havefound applications in cryptography and hardness of approximation. Animportant open problem is characterizing the power of no-signalingproofs. It is known that 2-prover no-signaling proofs are characterizedby PSPACE, and that no-signaling proofs with poly(n)-provers arecharacterized by EXP. However, the power of k-prover no-signalingproofs, for 2 < k < poly(n) remained an open problem.We show that k-prover no-signaling proofs (with negligible soundness)for k = sqrt(log n) are contained in PSPACE. We prove this via twodifferent routes that are of independent interest. In both routes weconsider a relaxation of no-signaling called sub-no-signaling. Our maintechnical contribution (which is used in both our proofs) is a reductionshowing how to convert any sub-no-signaling strategy with value at least1 - 2^(-Omega(k^2)) into a no-signaling one with value at least 2^-O(k^2).In the first route, we show that the classical prover reduction methodfor converting k-prover games into 2-prover games carries over to theno-signaling setting with the following loss in soundness: if a k-playergame has value less than 2^(-ck^2) (for some constant c>0), then thecorresponding 2-prover game has value at most 1-2(-dk^2) (for someconstant d>0). In the second route we show that the value of asub-no-signaling game can be approximated in space that is polynomial inthe communication complexity and exponential in the number of provers. G882, Hewlett

December 13

Muthu Venkitasubramaniam: A Round-Collapse Theorem for Computationally-Sound Protocols; or, TFNP is Hard-on-Average in Pessiland

Muthu Venkitasubramaniam

Part Of

10:30A
- 12:00P

Location

Hewlett, G882
Add to Calendar 2019-12-13 10:30:00 2019-12-13 12:00:00 America/New_York Muthu Venkitasubramaniam: A Round-Collapse Theorem for Computationally-Sound Protocols; or, TFNP is Hard-on-Average in Pessiland Abstract: Consider the following two fundamental open problems in complexity theory:* Does a hard-on-average language in NP imply the existence of one-way functions?* Does a hard-on-average language in NP imply a hard problem in TFNP (i.e., the class of total NP search problem)?We show that the answer to (at least) one of these questions is yes. In other words, in Impagliazzo's Pessiland (where NP is hard-on-average, but one-way functions do not exist), TFNP is unconditionally hard (on average).This result follows from a more general theory of interactive average-case complexity, and in particular, a novel round-collapse theorem for computationally-sound protocols, analogous to Babai-Moran's celebrated round-collapse theorem for information-theoretically sound protocols. As another consequence of this treatment, we show that the existence of O(1)-round public-coin non-trivial arguments (i.e., argument systems that are not proofs) imply the existence of a hard-on-average problem in NP/poly. Hewlett, G882

December 18

Noah Golowich: On the Power of Multiple Anonymous Messages

Noah Golowich, MIT

Part Of

2:00P
- 3:00P

Location

Hewlett, G882
Add to Calendar 2019-12-18 14:00:00 2019-12-18 15:00:00 America/New_York Noah Golowich: On the Power of Multiple Anonymous Messages Abstract: An exciting new development in differential privacy is the shuffled model, in which an anonymous channel enables circumventing the large errors that are necessary in the local model, while relying on much weaker trust assumptions than in the central model. We study basic counting problems in the shuffled model and establish separations between the error that can be achieved in the single-message shuffled model and in the shuffled model with multiple messages per user. For the frequency estimation problem with n users and for a domain of size B, we obtain:- A nearly tight lower bound of Ω̃ (min(n^(1/4), B^(1/2))) on the error in the single-message shuffled model. This implies that the protocols obtained from the amplification via shuffling work of Erlingsson et al. (SODA 2019) and Balle et al. (Crypto 2019) are essentially optimal for single-message protocols.- A nearly tight lower bound of Ω (log B / log log B) on the sample complexity with constant relative error in the single-message shuffled model. This improves on the lower bound of Ω(log^(1/17) B) obtained by Cheu et al. (Eurocrypt 2019).- Protocols in the multi-message shuffled model with poly(log B,log n) bits of communication per user and polylog B error, which provide an exponential improvement on the error compared to what is possible with single-message algorithms.For the related selection problem, we also show a nearly tight sample complexity lower bound of Ω(B) in the single-message shuffled model. This improves on the Ω(B^(1/17)) lower bound obtained by Cheu et al. (Eurocrypt 2019), and when combined with their Õ (√B)-error multi-message algorithm, implies the first separation between single-message and multi-message protocols for this problem. Joint work with Badih Ghazi, Ravi Kumar, Rasmus Pagh, and Ameya Velingker. Hewlett, G882