July 26

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 Belfer sarah_donahue@hks.harvard.edu

October 11

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 Belfer sarah_donahue@hks.harvard.edu

Adrienne Mannov: A Call for Crypto-Anthropology

Adrienne Mannov, PhD. Social Anthropologist, Aalborg University, Denmark
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 Belfer sarah_donahue@hks.harvard.edu

October 18

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 Belfer sarah_donahue@hks.harvard.edu