Melissa Chase

Microsoft Research Redmond Cryptography Colloquium

The MSR Redmond Cryptography Group (opens in new tab) invites researchers to visit the group and speak in our colloquium series.

Unless otherwise listed, the colloquia are open to the public. For directions or other questions contact: melissac (opens in new tab).

Visitors and Speakers (Spring 2014 – Summer 2015): Katherine Stange University of Colorado 8/4 Tues 10:30am Building 99 Room 1927 Ring-Learning With Errors Sarah Meiklejohn University College London 7/28 Tues 1:30pm Building 99 Room 1915 Centrally Banked Cryptocurrencies Thijs Laarhoven Eindhoven University of Technology 6/22 Mon 1:30pm Building 99 Room 1915 Sieving for shortest vectors in lattices using locality-sensitive hashing Tarik Moataz Colorado State University and Telecom Bretagne 11/19 Thurs 1:30pm Building 99 Room 1927 Toward Practical ORAMs Travis Mayberry Northeastern University 10/30 Thurs 1:30pm Building 99 Room 1915 Toward Robust Hidden Volumes Using Write-Only Oblivious RAM Mike Rosulek Oregon State University 8/27 Wed 3:30pm Building 99 Room 1927 From Circuits to RAM Programs in Malicious 2-party Computation Sarah Meiklejohn UCSD 7/23 Wed 3:30pm Building 99 Room 1927 Key-Versatile Signatures and Applications Douglas Stebila Queensland University of Technology 7/18 Fri 10:30am Building 99 Room 1919 Provable security of advanced properties of TLS and SSH Craig Costello Microsoft Research 6/11 Wed 10:30am Building 99 Room 1915 Curves and Lattices: putting number-theoretic cryptography into practice Huseyin Hisil Yasar University 6/9 Mon 3:00pm Building 99 Room 1915 Jacobian Coordinates on Jacobians Naveed Muhammad University of Illinois at Urbana Champaign 4/2 Wed 1:30pm Building 99 Room 1927 Dynamic Searchable Encryption via Blind Storage Mariana Raykova SRI International 2/19 Wed 1:30pm Building 99 Room 1927 Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits

Visitors and Speakers (Fall 2012 – Summer 2013): Benjamin Smith INRIA and Ecole Polytechnique 8/27 Tues 10:30am Building 99 Room 1915 Explicit Isogenies and Endomorphisms of Low-Genus Jacobians: Theory and Cryptographic Applications Peter Schwabe Radboud University Nijmegen 8/26 Mon 10:30am Building 99 Room 1927 Who is Afraid of Vectors – Optimizing Cryptography Using SSE, AVX, NEON, and Co. Damien Robert University of Bordeaux 8/8 Thurs 1:30pm Building 99 Room 1915 Optimal Pairings on Abelian Varieties with Theta Functions Jung Hee Cheon Seoul National University 8/6 Tues 1:30pm Building 99 Room 1915 Homomorphic Encryption and Erroneous Number Theory Alptekin Kupcu Koc University 8/1 Thurs 1:30pm Building 99 Room 1927 Efficient Cryptography for the Next Generation Secure Cloud Joseph Silverman Brown University 7/29 Mon 1:30pm Building 99 Room 1919 Public Key Cryptography Based on Partial Knowledge of Finite Fourier Transforms Nigel Smart University of Bristol 7/23 Tues 1:30pm Building 99 Room 1919 Multi-Party Computation: From Theory to Practice Steven Galbraith University of Auckland 5/7 Tues 1:30pm Building 99 Room 1915 Lattice-based cryptography: What they don’t want you to know Christiane Peters Technical University of Denmark 3/14 Thurs 1:30pm Building 99 Room 1927 Applications of Information-set Decoding in Cryptanalysis Guang Gong University of Waterloo 2/20 Wed 3:00pm Building 99 Room 1915 Securing RFID Systems Using Lightweight Stream Cipher Raluca Ada Popa MIT 11/27 Tues 1:30pm Building 99 Room 1927 CryptDB: Processing Queries on an Encrypted Database Ran Gelles UCLA 9/5 Wed 1:30pm Building 99 Room 1915 Optimal Coding for Streaming Authentication

Visitors and Speakers (Fall 2011 – Summer 2012): Martijn Stam University of Bristol 8/16 Thurs 10:00am Building 99 Room 1927 Security of Symmetric Encryption in the Presence of Ciphertext Fragmentation Sarah Meiklejohn UCSD 8/14 Tues 1:30pm Building 99 Room 1927 Rethinking Verifiably Encrypted Signatures: A Gap in Functionality and Potential Solutions Olivier Pereira UCL 8/13 Mon 1:30pm Building 99 Room 1915 Vote Privacy, Revisited: New Definitions, Tools and Constructions Peter Ryan University of Luxembourg 8/10 Fri 1:30pm Building 99 Room 1915 The Evolution of Pret a Voter Barbara Simons Former Pres of ACM 8/8 Wed 1:30pm Building 99 Room 1915 Internet Voting: An Idea Whose Time Has Not Come Anna Lysyanskaya Brown University 8/7 Tues 3:30pm Building 99 Room 1927 On the Security of One-Witness Blind Signature Schemes Yossef Oren Tel-Aviv University 8/7 Tues 1:30pm Building 99 Room 1927 The Mechanical Cryptographer: Tolerant Algebraic Side-Channel Attacks using pseudo-Boolean Solvers Kevin Fu UMass Amherst 8/2 Thurs 1:30pm Building 99 Room 1927 TARDIS: Time and Remanence Decay in SRAM to Implement Secure Protocols on Embedded Devices without Clocks Tom Ristenpart University of Wisconsin 7/31 Tues 1:30pm Building 99 Room 1915 Practice-Driven Cryptographic Theory Alyson Deines University of Washington 7/31 Tues 10:30am Building 115 Room 3381 Computing Elliptic Curves over Q(√5) Summer Number Theory Day 7/24 Tues 9am-5pm Building 99 Room 1919 Talks by William Stein, Kiran Kedlaya, Alina Bucur, Francois Rodier, Sorina Ionica , and Benjamin Lundell Sharon Goldberg Boston University 7/19 Thurs 1:30pm Building 99 Room 1927 A Workflow for Differentially-Private Graph Synthesis Claus Diem University of Leipzig 7/2 Mon 1:30pm Building 99 Room 1927 Index calculus and the elliptic curve discrete logarithm problem Ivan Visconti Univerity of Salerno 6/14 Thurs 1:30pm Building 99 Room 1927 The Round Complexity of (concurrent, resettable, efficient) Zero Knowledge in the Bare Public-Key Model Bryan Parno MSR 5/17 Thurs 1:30pm Building 99 Room 1927 Verifiable Computation via Quadratic Span Programs Sanjam Garg UCLA 5/3 Thurs 1:30pm Building 99 Room 1927 Adaptively Secure Multi-Party Computation, Revisited Brett Hemenway University of Michigan 4/26 Thurs 1:30pm Building 99 Room 4050 New Constructions of Lossy Trapdoor Functions Femi Olumofin Pitney Bowes 4/19 Thurs 1:30pm Building 99 Room 1915 Practical Private Information Retrieval Eleanor Birrell Cornell University 3/1 Thurs 2:00pm Building 99 Room 1927 Approximately Strategy-Proof Voting Olya Ohrimenko Brown University 2/21 Tues 1:30pm Building 99 Room 1915 Oblivious Access to Remote Data Storage Sarah Meiklejohn UCSD 2/2 Thurs 1:30pm Building 99 Room 1915 ZKPDL: A Language-Based System for Efficient Zero-Knowledge Proofs and Electronic Cash Samuel Ranellucci University of Montreal 1/4 Wed 1:30pm Building 99 Room 1927 Generalized oblivious Transfer (GOT) Xin Li University of Washington 11/10 Thurs 2:00pm Building 99 Room 1927 Privacy Amplification and Non-Malleable Extractors Via Character Sums Joppe Bos EPFL 10/13 Thurs 1:30pm Building 99 Room 1927 How to solve a 112-bit ECDLP using game consoles Marina Blanton University of Notre Dame 9/1 Thurs 1:30pm Building 99 Room 1915 Secure Biometric Computation and Outsourcing Payman Mohassel University of Calgary (Note: Unusual day/time) 8/30 Tues 1:30pm Building 99 Room 1915 Efficient Oblivious Automata Evaluation and Its Application

Visitors and Speakers (Spring 2011 – Summer 2011): Workshop on Symmetric Cryptanalysis Mon 8/8 – Wed 8/10 Building 99 Room 1919 More Info Bhavana Kanukurthi UCLA 8/4 Thurs 1:30pm Building 99 Room 1915 Cryptography with Imperfect Randomness Vanessa Teague The University of Melbourne (Note: Unusual day/time) 8/1 Monday 1:30pm Building 99 Room 1915 Pretty Good Democracy for a variety of voting schemes Sean Hallgren Pennsylvania State University 7/28 Thurs 1:30pm Building 99 Room 1915 Computing the unit group, class group and compact representations in algebraic function fields Matthew Green Johns Hopkins University (Note: Unusual day/time) 7/19 Tues 1:30pm Building 99 Room 1927 Charm: A Framework for Rapidly Prototyping Cryptosystems Brent Waters University of Texas, Austin (Note: Unusual day/time) 7/19 Tues 10:30am Building 99 Room 1927 Unbounded HIBE and Attribute-Based Encryption Leo Reyzin Boston University 7/14 Thur 1:30pm Building 99 Room 1915 Using Extensions of Min-Entropy to Help with Key Agreement and Leakage Resilience Mariana Raykova Columbia University (Note: Unusual day/time) 7/8 Fri 1:30pm Building 99 Room 1919 Secure Computation with Sublinear Amortized Work Seny Kamara MSR Redmond 7/7 Thurs 1:30pm Building 99 Room TBA Outsourcing Multi-Party Computation Avradip Mandal University of Luxembourg 6/30 Thurs 1:30pm Building 99 Room 1927 Fully Homomorphic Encryption over the integers with Shorter Public Keys Yevgeniy Dodis New York University 6/23 Thurs 1:30pm Building 99 Room 1915 Leftover Hash Lemma, Revisited Sharon Goldberg Boston University (Note: Unusual day/time) 6/22 Wed 1:30pm Building 99 Room 1927 Finding Incentives to Secure Internet Routing Daniel Wichs New York University 6/2 Thurs 1:30pm Building 99 Room 1927 Separating Succinct Non-Interactive Arguments From All Falsifiable Assumptions Zvika Brakerski Weizmann Institute (Note: Unusual day/time) 5/13 Fri 12:15pm Building 99 Room 1915 Fully Homomorphic Encryption from (Standard) LWE Andrey Bogdanov K.U.Leuven (Note: Unusual day/time) 5/6 Fri 1:30pm Building 99 Room 1915 Lightweight Cryptographic Algorithms Manoj Prabhakaran UIUC (Note: Unusual day/time) 4/29 Fri 1:30pm Building 99 Room 1927 Efficient Non-Interactive Secure Computation Huijia (Rachel) Lin Cornell 4/28 Thu 1:30pmBuilding 99 Room 1915 Concurrent Security No Colloquium: TCC 2011 (opens in new tab) at Providence RI 3/31 Thu 1:30pm Building 99 Room 1915 Canceled Jonathan Katz University of Maryland 3/24 Thu 1:30pm Building 99 Room 1915 Toward (More) Efficient Secure Two-Party Computation Lan Nguyen MSR Redmond 3/17 Thu 1:30pm Building 99 Room 1915 Revocation for Delegatable Anonymous Credentials Yevgeniy Vahlis Columbia University (Note: Unusual day/time) 3/14 Mon 1:30pm Building 99 Room 1915 Verifiable Delegation of Computation over Large Datasets Allison Lewko University of Texas, Austin (Note: Unusual day/time) 3/11 Fri 12:15 pm Building 99 Room 1927 Decentralizing Attribute-Based Encryption Bryan Parno Microsoft Research 3/3 Thu 1:30pmBuilding 99 Room 1915 Non-Interactive Verifiable Computing Zvika Brakerski Weizmann Institute and MIT 2/24 Thu 1:30pm Building 99 Room 1915 Overcoming the Hole in the Bucket: Public-Key Cryptography Resilient to Continual Memory Leakage Nishanth Chandran UCLA 2/3 Thu 10:30am Building 99 Room 1915A Position Based Cryptography Hoeteck Wee Queens College, NY 2/1 Tue 1:30pm Building 99 Room 1927 Black-Box, Round-Efficient Secure Computation Christian Rechberger KU Leuven 1/27 Thu 1:30pm Building 99 Room 1915 The SHA-3 competition through the rebound lens Vinod Vaikuntanathan MSR Redmond 1/20 Thu 1:30pm Building 99 Room 1927 Password-based Authenticated Key Exchange at the Cost of Diffie-Hellman

Summer and Fall 2010: Gil Segev MSR Silicon Valley 12/13 3:30pm Building 99 Room 1915A Leakage-Resilient Cryptography: Modeling and Combating Side-Channel Attacks Shweta Agrawal University of Texas at Austin 12/2 10:30am Building 99 Room 1919C Expressive encryption from hard lattice problems Payman Mohassel University of Calgary 10/28 1:30pm Building 99 Room 1927B Secure and Efficient Evaluation of Multivariate Polynomials and Applications Elliptic Curve Cryptography Conference 10/18 – 10/22 Building 99 Room 1919C More info (opens in new tab)    Videos now available (opens in new tab) Markulf Kohlweiss KULeuven/MSR Cambridge 9/24 1:30pm Building 115 Room 4381 Secure Revocation with Efficient Updates of Anonymous Credentials Cloud Cryptography Workshop 8/5 – 8/6 Building 99 Room 1919C Juan Garay ATT Labs 8/11 10:30am Building 99 Room TBA A Framework for the Sound Specification of Cryptographic Tasks Ed Dawson Queensland University of Technology 8/2 1:30pm Building 99 Room 1915A Elliptic Curves, Group Law, and Efficient Computation Kevin Fu UMass Amherst 7/20 1:30pm Building 99 Room 1915A Trustworthy Medical Device Software Jung Hee Cheon Seoul National Unviersity 6/29 2:30pm Building 99 Room 1927B Generalized Algorithm for DLP with Auxiliary Inputs Giuseppe Ateniese Johns Hopkins Unviersity 6/2 1:30pm Building 99 Room 1915A The Cloud was tipsy and ate my files!

Abstracts

Ring-Learning with Errors Katherine Stange (University of Colorado) 8/4 10:30am

ABSTRACT: New proposals for Homomorphic Encryption allow for outsourcing computation on encrypted data to the cloud. The security of these constructions is based on the hardness of a relatively new hard problem in lattice-based cryptography ‘Ring-Learning With Errors’. This talk will describe the problem, its applications, and discuss its security from the perspective of recent attacks.

BIO: Katherine Stange is an assistant professor at the University of Colorado Boulder, and was a student of Joseph H. Silverman. She is a number theorist with interests ranging from cryptography to elliptic curves to Apollonian circle packings.

Centrally Banked Cryptocurrencies Sarah Meiklejohn (University College London) 7/28 1:30pm

ABSTRACT: Current cryptocurrencies, starting with Bitcoin, build a decentralized blockchain-based transaction ledger, maintained through proofs-of-work that also generate a monetary supply. Such decentralization has benefits, such as independence from national political control, but also significant limitations in terms of scalability and computational cost. We introduce RSCoin, a cryptocurrency framework in which central banks maintain complete control over the monetary supply, but rely on a distributed set of authorities, or mintettes, to prevent double-spending. While monetary policy is centralized, RSCoin still provides strong transparency and auditability guarantees. We demonstrate, both theoretically and experimentally, the benefits of a modest degree of centralization, such as the elimination of wasteful hashing and a scalable system for avoiding double-spending attacks.

BIO: Sarah Meiklejohn is a Lecturer in the Departments of Computer Science and Security and Crime Science at University College London. She has broad research interests in computer security and cryptography, and has worked on topics such as anonymity and criminal abuses in virtual currencies, anonymous credentials, and understanding the interface between cryptographic primitives and their mathematical underpinnings. Previously, Sarah received a PhD from University of California, San Diego in May 2014 under the guidance of Mihir Bellare and Stefan Savage, as well as an Sc.B. in Mathematics in 2008 and an Sc.M. in Computer Science in 2009, both from Brown University.

Sieving for shortest vectors in lattices using locality-sensitive hashing Thijs Laarhoven (Eindhoven University of Technology) 6/22 1:30pm

ABSTRACT: Most lattice-based cryptographic primitives rely on the shortest vector problem (SVP) on lattices being hard. To assess the computational hardness of SVP and breaking these schemes, one commonly relies on the estimated time complexity of enumeration for solving SVP. In 2001 the breakthrough work of Ajtai et al. showed that SVP can actually be solved faster in high dimensions, using a technique called sieving. Although this technique seemed impractical at first, various improvements have since shown that sieving may be competitive with enumeration after all. In this talk we will look at recent advances in sieving using a technique from nearest neighbor searching, locality-sensitive hashing.

BIO: Thijs is a fourth-year Ph.D. student at the Eindhoven University of Technology in the Netherlands, studying the unrelated topics of fingerprinting and group testing algorithms, lattice algorithms, and the Collatz conjecture.

Towards Practical ORAM Tarik Moataz (Colorado State University and Telecom Bretagne) 11/19 1:30pm

ABSTRACT: Although Oblivious RAM (ORAM) has recently received a lot of attention, its high communication and storage cost still render it impractical for real-world scenarios. We present a general construction to reduce the communication cost of all recent tree-based ORAMs. The main idea behind our new construction dubbed “r-ORAM” is a recursive ORAM tree structure, where nodes in the tree are roots of other trees. We demonstrate that the expected cost saving is around 35% for any binary tree ORAMs. Besides reducing communication cost, r-ORAM also reduces storage overhead on the server by 20%. r-ORAM is general and can be applied to all recent tree ORAMs, both constant memory or poly-log client memory ORAMs. Furthermore, we will introduce first steps towards “Resizable ORAM”, enabling a client to adapt and change their ORAM’s storage requirement and therefore cost in any tree based ORAM.

BIO: Tarik Moataz is a second year Ph.D. student in a French-American joint Ph.D. program between Colorado State University and Telecom Bretagne. His main interest lies in designing new cryptographic protocols for operating on outsourced data. Tarik received his M.S. degree in information technology from Telecom Bretagne and an M.S. in mathematics and computer science from the University of Rennes 1. His master thesis on searchable encryption was done while at Bell Labs France. Currently, he is a visiting scholar at Northeastern University.

Toward Robust Hidden Volumes Using Write-Only Oblivious RAM Travis Mayberry (Northeastern University) 10/30 1:30pm

ABSTRACT: With sensitive data being increasingly stored on mobile devices and laptops, hard disk encryption is more important than ever. In particular, being able to plausibly deny that a hard disk contains certain encrypted information is a very useful and interesting research goal. However, it has been known for some time that existing ?hidden volume? solutions, like TrueCrypt, fail in the face of an adversary who is able to observe the contents of a disk on multiple, separate occasions. In this talk, I will explore more robust constructions for hidden volumes and present HIVE, which is resistant to more powerful adversaries with multiple-snapshot capabilities. At the core of HIVE, I will present a new write-only Oblivious RAM, which is of independent interest. I will show that, when only hiding writes, it is possible to achieve ORAM with optimal O(1) communication complexity and only poly-logarithmic user memory, a significant improvement over existing work. I will go on to show that this write-only ORAM is specially equipped to provide hidden volume functionality with low overhead and significantly increased security compared to existing solutions.

BIO: I started my academic career at the University of Maryland, Baltimore County where I worked with Alan Sherman and others on the secure cryptographic voting system Scantegrity. From there, I entered the PhD program at Northeastern University working with Agnes Chan and Erik-Oliver Blass. My research is currently on cryptographic protocols for efficient secure cloud computation and data retrieval, focusing specifically on practical Oblivious RAM schemes and their real-world applications.

From Circuits to RAM Programs in Malicious 2-party Computation Mike Rosulek (Oregon State University) 8/27 3:30pm

ABSTRACT: Secure 2-party computation (2PC) is becoming practical in some domains. However, most approaches are limited by the fact that the desired functionality must be represented as a boolean circuit. In response, the random-access machine (RAM) model has recently been investigated as a promising alternative to circuits. In this talk, I will discuss some pitfalls of basing malicious-secure 2PC on the RAM model rather than circuits. I will then describe two new protocols for malicious-secure 2PC of RAM programs, whose performance relative to the semi-honest model matches the state of the art for circuit-based 2PC techniques. For malicious security with statistical security parameter $2^{-s}$, our protocol without preprocessing has overhead $s$ compared to the semi-honest model; our protocol with preprocessing has overhead $sim 2s/log T$, where $T$ is the running time of the RAM program. This is joint work with Arash Afshar, Payman Mohassel, and Zhangxiang Hu.

BIO: Mike Rosulek is an Assistant Professor in the School of EECS at Oregon State University. He holds a Ph.D. in Computer Science from the University of Illinois and a B.S. in Computer Science from Iowa State University. His research interests are in cryptography, focusing on protocols for secure computation.

Key-Versatile Signatures and Applications Sarah Meiklejohn (UCSD) 7/23 3:30pm

ABSTRACT: This talk will discuss key-versatile signatures. Key-versatile signatures allow us to sign with keys already in use for another purpose, without changing the keys and without impacting the security of the original purpose. This allows us to obtain advances across a collection of challenging domains including joint encryption and signatures, security against related-key attack (RKA), and security for key-dependent messages (KDM). Specifically, we can (1) add signing capability to existing encryption capability with zero overhead in the size of the public key; (2) obtain RKA-secure signatures from any RKA-secure one-way function, yielding new RKA-secure signature schemes; and (3) add integrity to encryption while maintaining KDM-security.

BIO: As of September 2014, Sarah Meiklejohn will be a Lecturer at University College London with broad research interests in cryptography and security. Previously, she obtained her Ph.D. in Computer Science at UC San Diego, where she was co-advised by Mihir Bellare and Stefan Savage. Before that, she received an Sc.M. in Computer Science and an Sc.B. in Mathematics from Brown University.

Provable security of advanced properties of TLS and SSH Douglas Stebila (Queensland University of Technology) 7/18 10:30am

ABSTRACT: Cryptographic protocols are fundamental to securing communication on the Internet. The protocols that are used in practice tend to be more complicated than the protocols in academic papers and have more complex security goals. As a result, there has been a significant gap between our mathematical understanding of their security and their real-world security. In this talk, I’ll discuss a series of results aimed at reducing this gap.

I’ll begin by giving an introduction for non-cryptographers to “provable security”, which is the tool we use to formally describe and analyze the security properties of cryptographic schemes. Then I’ll discuss two important security properties that have not received a systematic treatment in the cryptographic literature—long-term key reuse and renegotiation—and connect these properties with real-world protocols: the Transport Layer Security (TLS) protocol used to secure billions of transactions on the web and the Secure Shell (SSH) protocol used for remote logins. I’ll present security models that better define the properties expected of these complex protocols, and results that demonstrate the conditions under which they have these properties.This talk covers joint work with Ben Dowling (QUT), and Florian Giesen, Florian Kohlar, and Jorg Schwenk (Ruhr-Universitat Bochum).

BIO: Dr Douglas Stebila is a researcher in information security and cryptography at the Queensland University of Technology in Brisbane, Australia. His primary research interest is cryptography, with a focus on the security of Internet and web authentication protocols such as SSL/TLS. He holds an MSc from the University of Oxford and a PhD from the University of Waterloo.

Curves and Lattices: putting number-theoretic cryptography into practice Craig Costello (Microsoft Research) 6/11 10:30am

ABSTRACT: This talk will give a brief overview of some of the hot topics in curve-and lattice-based cryptography, and will particularly focus on my work with various coauthors on putting these number-theoretic primitives into practice.

BIO: Craig Costello is a post-doctoral researcher at Microsoft Research who is known for his contributions to elliptic and hyperelliptic curve cryptography, and pairing-based cryptography. His current research interests include explicit cryptographic algorithms on genus 2 curves, and efficient cryptography based on lattices. His research has attracted several awards and grants, including an Australian-American Fulbright Scholarship.

Jacobian Coordinates on Jacobians Huseyin Hisil (Yasar University) 6/9 3:00pm

ABSTRACT: This talk presents a new projective coordinate system and new explicit algorithms which together boost the speed of arithmetic in the divisor class group of genus 2 curves. The proposed formulas generalize the use of Jacobian coordinates on elliptic curves, and their application improves the speed of performing cryptographic scalar multiplications in Jacobians of genus 2 curves over prime fields by an approximate factor of 1.25x. For example, on a single core of an Intel Core i7-3770M (Ivy Bridge), we show that replacing the previous best formulas with our new set improves the cost of generic scalar multiplications from 243,000 to 195,000 cycles, and drops the cost of specialized GLV-style scalar multiplications from 166,000 to 129,000 cycles.

BIO: Huseyin Hisil is an Assistant Professor at Yasar University in Izmir, Turkey, who is known for contributions to curve-based cryptography. He was awarded a PhD from the Queensland University of Technology in Australia in 2008, where among other things, he derived formulas for working on twisted Edwards curves that give rise to the overall fastest implementations of elliptic curve cryptography. In recent times, his work has focused on speeding up the hyperelliptic setting.

Dynamic Searchable Encryption via Blind Storage Naveed Muhammad (University of Illinois at Urbana Champaign) 4/2 1:30pm

ABSTRACT: Dynamic Searchable Symmetric Encryption allows a client to store a dynamic collection of encrypted documents with a server, and later quickly carry out keyword searches on these encrypted documents, while revealing minimal information to the server. In this paper we present a new dynamic SSE scheme that is simpler and more efficient than existing schemes while revealing less information to the server than prior schemes, achieving fully adaptive security against honest-but-curious servers. We implemented a prototype of our scheme and demonstrated its efficiency on datasets from prior work. Apart from its concrete efficiency, our scheme is also simpler: in particular, it does not require the server to support any operation other than upload and download of data. Thus the server in our scheme can be based solely on a cloud storage service, rather than a cloud computation service as well, as in prior work. In building our dynamic SSE scheme, we introduce a new primitive called Blind Storage, which allows a client to store a set of files on a remote server in such a way that the server does not learn how many files are stored, or the lengths of the individual files; as each file is retrieved, the server learns about its existence (and can notice the same file being downloaded subsequently), but the file’s name and contents are not revealed. This is a primitive with several applications other than SSE, and is of independent interest.

BIO: Muhammad Naveed is a third year PhD student in computer science at the University of Illinois at Urbana-Champaign. He is interested in cryptography, security, and privacy. His current research focuses on secure cloud storage, secure multiparty computation, functional encryption, smartphone security and genomics privacy.

Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits Mariana Raykova (SRI International) 2/19 1:30pm

ABSTRACT: In this work, we study indistinguishability obfuscation and functional encryption for general circuits:Indistinguishability obfuscation requires that given any two equivalent circuits $C_0$ and $C_1$ of similar size, the obfuscations of $C_0$ and $C_1$ should be computationally indistinguishable.

In functional encryption, ciphertexts encrypt inputs $x$ and keys are issued for circuits $C$. Using the key $SK_C$ to decrypt a ciphertext $CT_x=enc(x)$, yields the value $C(x)$ but does not reveal anything else about $x$. Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually.We give constructions for indistinguishability obfuscation and functional encryption that supports all polynomial-size circuits. We accomplish this goal in three steps:

We describe a candidate construction for indistinguishability obfuscation for $NC^1$ circuits. The security of this construction is based on a new algebraic hardness assumption. The candidate and assumption use a simplified variant of multilinear maps, which we call Multilinear Jigsaw Puzzles.

We show how to use indistinguishability obfuscation for $NC^1$ together with Fully Homomorphic Encryption (with decryption in $NC^1$) to achieve indistinguishability obfuscation for all circuits.Finally, we show how to use indistinguishability obfuscation for circuits, public-key encryption, and non-interactive zero knowledge to achieve functional encryption for all circuits. The functional encryption scheme we construct also enjoys succinct ciphertexts, which enables several other applications.

Joint work with Sanjam Garg, Craig Gentry, Shai Halevi, Amit Sahai, Brent Waters

BIO: Mariana Raykova is a researcher in cryptography at SRI International. She received her PhD in 2012 from Columbia University advised by Tal Malkin and Steve Bellovin. Her PhD work focused on secure computation and bringing cryptographic constructions closer to practical uses. She spent a year as a postdoc in the cryptography group at IBM Research Watson, where she worked on obfuscation, functional encryption and verifiable computation. She did three summer internships during her PhD at MSR Redmond working in the cryptography and security groups.

Explicit Isogenies and Endomorphisms of Low-Genus Jacobians: Theory and Cryptographic Applications Benjamin Smith (INRIA and Ecole Polytechnique) 8/27 10:30am

ABSTRACT: The last few decades have seen the development of many computational tools for algebraic curves and their Jacobians: algorithms for divisor class arithmetic, point counting and zeta functions, explicit Riemann-Roch spaces… On the other hand, algorithms for the mappings between these objects remain relatively underdeveloped. From a category-theoretic point of view: we’ve got a reasonably good handle on (most of) the objects in our diagrams, but we have a chronic shortage of effective arrows!

In this talk, we consider some of the problems involved in computing with isogenies and endomorphisms of low-genus Jacobians, with a special focus on their applications in cryptography. For example: isogenies can be used to accelerate point counting, to relate ostensibly different discrete logarithm problems, and to improve the efficiency of cryptographic operations on elliptic and genus 2 curves. We will survey these constructions, consider their limitations, and give an idea of some open problems.

BIO: Benjamin Smith is a research scientist at INRIA (France) and an adjunct assistant professor at the Ecole Polytechnique. He has made a number of contributions to the field of curve-based cryptography, including novel attacks on genus 3 curves, accelerated methods of point counting on genus 2 curves, and very recently, a new way of obtaining and exploiting endomorphisms on genus 1 elliptic curves.

Who is Afraid of Vectors – Optimizing Cryptography Using SSE, AVX, NEON, and Co. Peter Schwabe (Radboud University Nijmegen) 8/26 10:30am

ABSTRACT: Most computer architectures, for example, x86, AMD64 and ARMv7 support efficient operations on vectors of data. The computational power of these instructions are most easily exploited if the same long streams of computations are carried out on independent sets of data. This is, for example, the case in many cryptanalytic computations. However, also single cryptographic computations can benefit from the computational power of vector instructions. In my talk I will consider various examples of such cryptographic computations and describe what implementation techniques are required to make best use of the vector instruction sets of various computer architectures.

BIO: Peter Schwabe is an assistant professor at Radboud University Nijmegen in the Netherlands. He graduated from RWTH Aachen University in computer science in 2006 and received a Ph.D. from the Faculty of Mathematics and Computer Science of Eindhoven University of Technology in 2011. Afterwards he worked for two years as a postdoctoral researcher at the Institute for Information Science and the Research Center for Information Technology Innovation of Academia Sinica, Taiwan and at National Taiwan University.

His research area is the optimization of cryptographic and cryptanalytic algorithms in software. The target architectures of this software range from high-end desktop and server CPUs through parallel architectures such as the Cell Broadband Engine and graphics processing units to embedded processors such as ARM and AVR. He has published articles at several international conferences on fast software for a variety of cryptographic primitives including AES, hash functions, elliptic-curve cryptography, and cryptographic pairings. He has also published articles on fast cryptanalysis, in particular attacks on the discrete-logarithm problem.

Optimal Pairings on Abelian Varieties with Theta Functions Damien Robert (University of Bordeaux) 8/8 1:30pm

ABSTRACT: Pairings on elliptic curves have allowed the development of new cryptographic protocols like anonymous certificates, multicanal broadcasting… For an elliptic curve, or more generally a Jacobian, computing the pairing uses an algorithm due to Miller that explicitly compute some functions associated to divisors on the curve.

In this talk, we show how one can use Riemann relations on the Theta model to compute the Tate and Weil pairings on abelian varieties that are not necessarily Jacobians. We show how to generalize this to pairings reducing the loop length of Miller’s algorithm (ate, twisted ate, optimal ate), and also how to compute symmetric pairings on Kummer varieties.While elaborated for general abelian varieties, this algorithm is surprisingly fast in low dimension, and is almost competitive with the fastest known pairings computation on elliptic curves.This is a joint work with David Lubicz.

BIO: Damien Robert is an INRIA researcher in the LFANT team at University of Bordeaux. Previously, he was a postdoctoral researcher at Microsoft Research (MSR) in the cryptography group. Damien works in the field of applications of abelian varieties in public key cryptography, with main subjects of interest Jacobians of hyperelliptic curves (and more specifically genus 2 curves), computing isogenies and point counting, and also arithmetic with theta functions and class polynomials generation. Damien Robert worked on his PhD thesis under the supervision of Guillaume Hanrot in the Caramel team at Nancy.

Homomorphic Encryption and Erroneous Number Theory Jung Hee Cheon (Seoul National University) 8/6 1:30pm

ABSTRACT: This talk provides an easy introduction of somewhat homomorphic encryptions. After the talk, anyone should be able to memorize at least one homomorphic scheme and understand how it works. We start with privacy homomorphisms proposed by Rivest et al in 1978. As those schemes, homomorphic encryptions could be vulnerable to the known plaintext attack with several pairs of plaintext and ciphertext. To repair previous weak schemes, we may consider a technique to insert errors intentionally as in Gentry’s fully homomorphic encryption. We introduce how to repair the privacy homomorphisms with this approach. Interestingly, the base hard problems of somewhat homomorphic encryptions can be regarded as number theoretic problems whose input contains some errors. This opens a new area about approximate computation in number theory, and raise a lot of interesting problems. We introduce some of them.

BIO: Jung Hee Cheon is a Professor in the Department of Mathematical Sciences and a director of Cryptographic Hard Problems Research Initiatives at Seoul National University (SNU). He received his B.S. and Ph.D. degrees in mathematics at KAIST in 1991, and 1997, respectively. He received the best paper award in Asiacrypt 2008 and the distinguished paper award from the Korean Mathematical Society in 2011. His research focuses on computational number theory, cryptology and their applications to practical problems.

Efficient Cryptography for the Next Generation Secure Cloud Alptekin Kupcu (Koc University) 8/1 1:30pm

ABSTRACT: Peer-to-peer (P2P) systems, and client-server type storage and computation outsourcing constitute some of the major applications that the next generation cloud schemes will address. Since these applications are just emerging, it is the perfect time to design them with security and privacy in mind. Furthermore, considering the high-churn characteristics of such systems, the cryptographic protocols employed must be efficient and scalable.

In this talk, I will focus on an efficient and scalable fair exchange protocol that can be used for exchanging files between participants of a P2P file sharing system. It has been shown that fair exchange cannot be done without a trusted third party (called the Arbiter). Yet, even with a trusted Arbiter, it is still non-trivial to come up with an efficient solution, especially one that can be used in a P2P file sharing system with a high volume of data exchanged. Our protocol is optimistic, removing the need for the Arbiter’s involvement unless a dispute occurs. While the previous solutions employ costly cryptographic primitives for every file or block exchanged, our protocol employs them only once per peer, therefore achieving O(n) efficiency improvement when n blocks are exchanged between two peers. In practice, this corresponds to one-two orders of magnitude improvement in terms of both computation and communication (42 minutes vs. 40 seconds, 225 MB vs. 1.8 MB). Thus, for the first time, a provably secure (and privacy respecting when payments are made using e-cash) fair exchange protocol is being used in real bartering applications (e.g., BitTorrent) without sacrificing performance.

Finally, if time permits, I will briefly mention some of our other results on cloud security including ways to securely outsource computation and storage to untrusted entities, official arbitration in the cloud, impossibility results on distributing the Arbiter, and keeping the user passwords safe (joint work at Microsoft Research). I will also be available to talk on these other projects after the presentation.

BIO: Alptekin Kupcu has received his Ph.D. degree from Brown University Computer Science Department in 2010. Since then, he has been working as an assistant professor at Koc University College of Engineering, and leading the Cryptography, Security & Privacy Research Group he has founded. His research mainly focuses on applied cryptography, and its intersection with cloud security, privacy, peer-to-peer networks, game theory, and mechanism design. He has led the development of the Brownie Cashlib cryptographic library, which is available as open source online. He is a member of IACR, ACM, and IEEE. Dr. Kupcu has various accomplishments including 2 patents pending, and has been part of 7 funded national/international/industrial/NSF/European Union research projects up to now, for 5 of which he was the principal investigator. For more information, visit http://crypto.ku.edu.tr

Dr. Kupcu has been an active collaborator of Microsoft Research since 2009. He has a joint publication with Dr. Tolga Acar and Dr. Mira Belenkiy of Microsoft Research, and ongoing or planned collaboration activities with Dr. Seny Kamara and Dr. Melissa Chase. He is currently a Visiting Scholar in the cryptography research group of Dr. Kristin Lauter.

Public Key Cryptography Based on Partial Knowledge of Finite Fourier Transforms Joseph Silverman (Brown University) 7/29 1:30pm

ABSTRACT: The finite Fourier transform (FFT) sends vectors v = (x_1,…,x_n) to vectors F(v) = (F_1(v),…,F_n(v)). The FFT map is a bijection of the space of n-dimensional vectors that respects addition and changes convolution multiplication into coordinate-wise multiplication. If n is large, it is a difficult problem to recover a small vector v from partial knowledge of its FFT. We describe how to use this hard problem to create both a public key cryptosystem and a digital signature scheme. An earlier digital signature scheme based on this problem suffered from information leakage in trascripts, We explain how to use rejection sampling to avoid such leakage. Finally, we describe how the partial-FFT problem is naturally equivalent to a certain closest vector lattice problem, which can be used to (heuristically) analyze the security. (This is joint work with Jeff Hoffstein, John Schanck, and William Whyte.)

BIO: Joseph Silverman received an Sc.B. from Brown University in 1977 and a Ph.D. from Harvard University in 1982 under the direction of John Tate. He held positions at M.I.T. and Boston University before moving to Brown University in 1988, where he is currently a professor of mathematics. Silverman works primarily in number theory, arithmetic geometry, arithmetic dynamics and cryptography. He has published more than 100 research articles in these areas, and has written or coauthored seven books, including several on elliptic curves and one on cryptography. Two of his books on elliptic curves were awarded the Steele Prize by the American Mathematical Society in 1998. He is a past recipient of Sloan and Guggenheim fellowships, and is a co-founder of NTRU Cryptosystems (now merged with Security Innovation).

Multi-Party Computation: From Theory to Practice Nigel Smart (University of Bristol) 7/23 1:30pm

ABSTRACT: In the last couple of years amazing advances have been made on techniques to perform computation on encrypted data. Some of the techniques are even becoming practical. In this talk I will show a novel technique which utilizes techniques used in Fully Homomorphic Encryption (FHE) schemes to provide efficiency improvements in Multi-Party Computation (MPC) protocols.

BIO: Nigel Smart is a Professor of Cryptology at the University of Bristol. Before that he worked for Hewlett-Packard Laboratories. He is a Director of the IACR, and a holder of a Royal Society Wolfson Merit Award, and an ERC Advanced Grant. He has conducted work in various areas of cryptography ranging from elliptic curves, to pairings, to fully homomorphic encryption and to multi-party computation. His work is unified by the goal of turning cryptographic theory into practice.

Lattice-based cryptography: What they don’t want you to know Steven Galbraith (University of Auckland) 5/7 1:30pm

ABSTRACT: Lattice-based cryptography is currently the hottest research area in theoretical cryptography. There have been a number of amazing results (homomorphic encryption, attribute-based encryption for general circuits, multilinear maps) that were not previously possible. Hence, the area is extremely active, with major new papers appearing almost every month. However, a few inconvenient truths have been swept under the carpet along the way. Although known to the experts, some of these issues are possibly not well-known in the wider community.

BIO: Steven Galbraith is a Professor in the Mathematics Department at the University of Auckland. His main research interests lie in elliptic curve cryptography and on related mathematical topics. He completed his PhD in mathematics at the University of Oxford in 1996 under the supervision of Bryan Birch. He has recently written an advanced graduate textbook titled “Mathematics of Public Key Cryptography”, which covers everything from the Pollard algorithms, isogenies and hyperelliptic curves, to algebraic tori and lattices.

Applications of Information-set Decoding in Cryptanalysis Christiane Peters (Technical University of Denmark) 3/14 1:30pm

ABSTRACT: The security of code-based cryptography is based on the hardness of the generic decoding problem: given a random linear code find a codeword within fixed Hamming distance from a given vector. The corresponding decision problem is NP-hard and the most efficient algorithms for solving the computational problem all take exponential time. This talk discusses the complexity of the best known algorithms which are based on information-set decoding and the implications for code-based cryptography as well as the Learning Parity with Noise (LPN) problem.

BIO: Christiane Peters is a postdoctoral researcher at the Technical University of Denmark, and visiting researcher at Microsoft Research, Redmond. She obtained her Ph.D. in applied cryptography at Technische Universiteit Eindhoven, the Netherlands, supervised by Tanja Lange and Daniel J. Bernstein. Her research focuses on error-correcting codes in cryptography as well as number-theoretic and cryptographic applications of elliptic curves.

Securing RFID Systems Using Lightweight Stream Cipher Guang Gong (University of Waterloo) 2/20 3:00pm

ABSTRACT: Radio frequency identification (RFID) is a technology for the automated identification of physical entities using radio frequency transmissions. In the past ten years, RFID systems have gained popularity in many applications, such as supply chain management, library systems, e-passports, contactless cards, identification systems, and human implantation. RFID is one of the most promising technologies in the field of ubiquitous and pervasive computing. Many new applications can be created by embedding an object with RFID tags. However, the rapid development of RFID systems raises serious privacy and security concerns that could prevent the benefits of RFID technology from being fully utilized. In this talk, first I will give an overview for the proposed methods in the literature for authentications in RFID systems, then I will present a lightweight WG stream cipher for securing RFID systems, and provide the security analysis and efficient implementation of an instance of WG-8 on microcontroller.

BIO: Guang Gong received a B.S. degree in Mathematics in 1981, an M.S. degree in Applied Mathematics in 1985, and a Ph.D. degree in Electrical Engineering in 1990, from Universities in China. She received a Postdoctoral Fellowship from the Fondazione Ugo Bordoni, in Rome, Italy, and spent the following year there. After returning from Italy, she was promoted to an Associate Professor at the University of Electrical Science and Technology of China. During 1995-1998, Dr. Gong worked with several internationally recognized, outstanding coding experts and cryptographers, including Dr. Solomon W. Golomb, at the University of Southern California. Dr. Gong joined the University of Waterloo, Canada in 1998, as an Associate Professor in the Dept. of Electrical and Computer Engineering in September 2000. She has been a full Professor since 2004. Dr. Gong’s research interests are in the areas of sequence design, cryptography, and communication security. She has authored or co-authored more than 240 technical papers and two books, one co-authored with Dr. Golomb, entitled as Signal Design for Good Correlation for Wireless Communication, Cryptography and Radar, published by Cambridge Press in 2005, and the other coauthored with Dr. Lidong Chen, Communication System Security, published by CRC 2012. Dr. Gong serves/served as Associate Editors for several journals including Associate Editor for Sequences for IEEE Transactions on Information Theory, and served on a number of technical program committees and conferences as co-chairs or committee members. Dr. Gong has received several awards including the Best Paper Award from the Chinese Institute of Electronics in 1984, Outstanding Doctorate Faculty Award of Sichuan Province, China, in 1991, the Premier’s Research Excellence Award, Ontario, Canada, in 2001, NSERC Discovery Accelerator Supplement Award, 2009, Canada, and Ontario Research Fund – Research Excellence Award, 2010, Canada, Best Paper Award of IEEE ICC 2012. She currently serves as the Managing Director of the Center of Applied Cryptographic Research (CACR) at University of Waterloo.

CryptDB: Processing Queries on an Encrypted Database Raluca Ada Popa (MIT) 11/27 1:30pm

ABSTRACT: Online applications are vulnerable to theft of sensitive information because adversaries can exploit software bugs to gain access to private data, and because curious or malicious administrators may capture and leak data. CryptDB is a system that provides practical confidentiality in the face of these attacks for applications backed by SQL databases. CryptDB’s approach is to execute SQL queries over encrypted data. It can do so practically with two techniques: using a collection of efficient SQL-aware encryption schemes, two of which are new, and onions of encryptions which allow dynamic adjustment of encryption schemes. An analysis of a trace of 126 million SQL queries from a production MySQL server shows that CryptDB can support operations over encrypted data for 99.5% of the 128,840 columns seen in the trace. Our evaluation shows that CryptDB has low overhead, reducing throughput by only 26% for queries from the standard SQL benchmark TPC-C when compared to unmodified MySQL.

BIO: Raluca Ada Popa is a third year Ph.D. student in computer science at MIT, advised by Prof. Nickolai Zeldovich. Her research interests are in building secure systems with solid cryptographic foundations, her work thus spanning from systems security to theoretical cryptography. Raluca received the 2011 Google Ph.D. Fellowship for Secure Cloud Computing and the 2009 CRA Outstanding Undergraduate Award for research.

Optimal Coding for Streaming Authentication Ran Gelles (UCLA) 9/5 1:30pm

ABSTRACT: Message authentication is well studied in the literature, and various efficient solutions have been suggested and analyzed. This is however not the case for authentication of data streams in which the message is very long, possibly infinite, and not known in advance to the sender. Trivial solutions for authenticating data streams either suffer from a long delay at the receiver?s end or cannot perform well when the communication channel is noisy.

We suggest an efficient, constant rate, authentication scheme for data streams over a noisy channel in the shared-randomness model. We show that for every given noise rate c < 1, there exists a scheme that correctly decodes and authenticates a (1-c)-fraction of the stream sent so far, with high probability. We also show that no constant-rate authentication scheme recovers more than a (1-c)-fraction of the stream, which implies that our scheme is optimal.Joint work with Matthew Franklin, Rafail Ostrovsky, and Leonard Schulman.

BIO: Ran Gelles is a PhD student in the Computer Science Department at UCLA. He works in the Theory and Cryptography lab with Professor Rafail Ostrovsky and Professor Amit Sahai. He received B.Sc. in Computer Engineering in 2003, and M.Sc. in Computer Science in 2009, both from Technion, Israel.

Security of Symmetric Encryption in the Presence of Ciphertext Fragmentation Martijn Stam (University of Bristol) 8/16 10:00am

ABSTRACT: In recent years, a number of standardized symmetric encryption schemes have fallen foul of attacks exploiting the fact that in some real world scenarios ciphertexts can be delivered in a fragmented fashion. We initiate the first general and formal study of the security of symmetric encryption against such attacks. We extend the SSH-specific work of Paterson and Watson (Eurocrypt 2010) to develop security models for the fragmented setting. We also develop security models to formalize the additional desirable properties of ciphertext boundary hiding and robustness against Denial-of-Service (DoS) attacks for schemes in this setting.

We illustrate the utility of each of our models via efficient constructions for schemes using only standard cryptographic components, including constructions that simultaneously achieve confidentiality, ciphertext boundary hiding and DoS robustness.

Joint work with Alexandra Boldyreva, Jean Paul Degabriele, and Kenneth G. Paterson

BIO: Martijn Stam joined the University of Bristol as a Lecturer in the Computer Science Department in February 2011. Prior to that, he obtained his Master’s Degree and PhD in Mathematics from the Technische Universiteit Eindhoven. Over the years, he has been a post-doctoral researcher at the University of Bristol, EPFL (Switzerland), and Royal Holloway, University of London.His main academic interest is cryptology. Cryptology is an ever expanding field that mostly sits in between mathematics and computer science, with elements from other disciplines as well. Parts of cryptology are firmly grounded as an exact science, while other parts still have a strong engineering aspect to them. His expertise ranges over a relatively wide area of cryptology. During his PhD and early postdoc years, his research was centered around the efficient implementation of subgroup cryptosystems, such as XTR or torus-based cryptosystems. Currently his research is focused on the provable security of modes-of-operation for symmetric cryptography.

Rethinking Verifiably Encrypted Signatures: A Gap in Functionality and Potential Solutions Sarah Meiklejohn (University of California, San Diego) 8/14 1:30pm

ABSTRACT: Verifiably encrypted signatures (VES) were originally introduced by Boneh, Gentry, Lynn, and Shacham in 2003. Since then, many new constructions have been provided, as well as new security definitions that seek to refine and strengthen the ones originally proposed. As the name suggests, the desired functionality of a VES scheme intuitively allows a user to encrypt, in a publicly verifiable manner, a signature on a message, coupled with the ability for either that user or some trusted third party (such as an arbiter) to later pull out the underlying signature. Such schemes allow for the fair exchange of digital signatures, in which two untrusted parties interact in the hopes of obtaining each others’ signatures on some message (e.g., a contract), and either both parties get what they want or neither does.

In this paper, we argue that even the refined definitions for VES security do not sufficiently capture this desired functionality. To support this claim, we generically construct a secure VES scheme using only signatures; this immediately suggests that the existing security notions are not capturing the “verifiable encryption” part of VES. To therefore bridge this gap between the desired functionality and the existing definitions, we propose a new definition called resolution independence and show that our signature-based construction cannot satisfy this definition, whereas all existing VES schemes can; resolution independence therefore provides a separation of sorts between our contrived construction and those that do provide the desired functionality. As further support for our new definition, we then show that any secure VES scheme satisfying a slightly stronger notion of resolution independence implies the existence of encryption.

This is joint work with Theresa Calderon, Hovav Shacham, and Brent Waters.

BIO: Sarah is a PhD candidate in Computer Science at the University of California, San Diego, entering her fourth year and working in the Security and Cryptography Group. Before starting at UCSD, she obtained a Sc.B. in Mathematics and an Sc.M. in Computer Science from Brown University under the guidance of Anna Lysyanskaya. Her research interests focus on the interface between security and cryptography; i.e., trying to improve the way in which cryptographic protocols are incorporated into secure systems, as well as coming up with cryptographic models that accurately reflect real-world attacks. Most recently, Sarah spent the summer of 2011 at MSR Redmond, working in the cryptography group with Melissa Chase.

Security of Symmetric Encryption in the Presence of Ciphertext Fragmentation Olivier Pereira (Université Catholique de Louvain) 8/13 1:30pm

ABSTRACT: Vote privacy is a central aspect of most of our elections. It is however not an absolute property: it will depend on the ballot format, tallying rules, voter turnout and preferences. Furthermore, it is achieved using various techniques, creating new trade-offs with the adoption of end-to-end verifiable voting systems for instance.

We describe various contributions to the analysis of the privacy properties that voting systems provide:

• We propose privacy metrics, inspired from classical information theoretic (IT) quantities, and illustrate their use on the public audit data provided for the 2009 Takoma Park election based on Scantegrity.
• We propose computational analogs of our IT metrics, together with a more traditional style cryptographic game-based privacy definition and show that this game-based definition can be conveniently used to bridge the gap between our IT and computational metrics.
• Focusing on a large class of voting protocols where voters interact with the authorities in one single pass, we identify conditions that guarantee that an encryption scheme is appropriate for the submission of ballots and apply these conditions to analyze the security of the Helios voting system.
• Finally, we propose a new type of encryption schemes, as well as efficient constructions that can be used to build voting schemes that offer an IT private audit trail and computational privacy towards authorities.

This talk is based on joint works with David Bernhard, Veronique Cortier, Edouard Cuvelier, Thomas Peters and Bogdan Warinschi.

BIO: Olivier Pereira is a professor at Université catholique de Louvain and a research associate of the Belgian Science Research Foundation FNRS. He led the development of the voting system to be used in 2009 in the first multi-thousand voters, end-to-end verifiable, legally binding election. This voting system has been used in dozen of elections since then.

The Evolution of Pret a Voter Peter Ryan (University of Luxembourg) 8/10 1:30pm

ABSTRACT: The challenge of making elections demonstrably accurate while guaranteeing ballot secrecy with minimal trust assumptions has been taken up by the crypto/security community. One of the approaches is the “Pret a Voter” concept, in which the vote is encoded by randomising the order of candidates. In this talk I will outline the Pret a Voter concept and describe its development over the roughly eight years since its inception. The design has evolved in the face of newly identified threats, advances in cryptographic primitives and demands for greater flexibility and efficiency. I will also outline the Pretty Good Democracy scheme and the incorporation of ideas from PGD in Pret a Voter, giving rise to Pret a Voter with Confirmation Codes.

BIO: Peter Ryan is Professor of Applied Security at the University of Luxembourg. He has over 20 years of experience in information assurance and formal verification. He pioneered the application of process algebras to modelling and analysis of secure systems and initiated and led the project that pioneered the application of process algebra (CSP) and model-checking to the analysis of security protocols. He has published extensively on cryptography, cryptographic protocols, mathematical models of computer security and, most recently, high assurance voting systems. He is the creator of Pr�t � Voter, Pretty Good Democracy (with Vanessa Teague) and OpenVote (with Feng Hoa) verifiable voting schemes. Prior to joining the University of Luxembourg, he was a Professor of Computing Science at Newcastle University. He has worked at GCHQ, the Defence Research Agency, the Stanford Research Institute in Cambridge and the Software Engineering Institute, CMU Pittsburgh. He holds a PhD in mathematical physics from the University of London.

Internet Voting: An Idea Whose Time Has Not Come Barbara Simons 8/8 1:30pm

ABSTRACT: Properly designed and engineered computerized voting systems can facilitate voting and increase the security and reliability of our voting systems. Unfortunately, in their eagerness to have the most modern and best election equipment and to take advantage of almost $4 billion in federal funding, well-meaning election officials were quick to accept accuracy and security claims of computerized voting system vendors. Few questions were asked about crucial issues. How secure, accurate, and reliable are these machines? How easy are they to use, especially by people with disabilities? How could an election audit or recount be conducted? There was little or no consultation with independent technical experts on these questions, and remarkably little scientific research. Standards and regulations were inadequate to nonexistent. The implicit assumption appears to have been that no recount would ever be needed, because the new systems were so completely secure and accurate that there would no longer be any reason to challenge an election result.

There is now a widespread perception that Internet voting is the wave of the future and the way to save money while increasing voter participation, especially participation of young people. (I can bank online; why can’t I vote online?) Not having learned from previous mistakes and against the advice of essentially all computer security experts, Internet voting is currently being used in several countries and in some U.S. States. There is also strong pressure to adopt Internet voting in the U.S. for members of the military and civilians living abroad. In this talk I examine some of the threats of Internet voting in the hope of encouraging the technical community to oppose Internet voting unless and until these threats can be eliminated.

BIO: An expert on electronic voting, Dr. Barbara Simons recently published Broken Ballots: Will Your Vote Count?, a book on voting machines co-authored with Douglas Jones. She is on the Board of Advisors of the U.S. Election Assistance Commission, and she was a member of the workshop, convened at the request of President Clinton, that produced a report on Internet Voting in 2001. She also co-authored the report that led to the cancellation of Department of Defense’s Internet voting project (SERVE) because of security concerns. Simons, a former President of the Association for Computing Machinery (ACM), co-chaired the ACM study of statewide databases of registered voters, and co-authored the League of Women Voters report on election auditing. Simons is retired from IBM Research.

On the Security of One-Witness Blind Signature Schemes Anna Lysyanskaya (Brown University) 8/7 3:30pm

ABSTRACT: Blind signatures have proved an essential building block for applications that protect privacy while ensuring unforgeability, e.g., electronic cash and electronic voting. One of the oldest, and most efficient blind signature schemes is the one due to Schnorr that is based on his famous identification scheme. Although it was proposed over twenty years ago, its unforgeability remains an open problem, even in the random-oracle model. In this work, we show that current techniques for proving security in the random oracle model do not work for the Schnorr blind signature. Our results generalize to other important blind signatures, such as the one due to Brands. Brands’ blind signature is at the heart of Microsoft’s UProve system, which makes this work relevant to cryptographic practice as well.Joint work with Foteini Baldimtsi

BIO: Anna Lysyanskaya is an Associate Professor of Computer Science at Brown University. She received her Ph.D. in Computer Science and Electrical Engineering from MIT and joined the faculty of Brown in 2002. She is a recipient of an NSF CAREER award and a Sloan Foundation fellowship; she is also an MIT Technology Review Magazine’s “35 under 35” honoree. Her research interests are in cryptography, theoretical computer science, and computer security. A theme of her research is on balancing anonymity with accountability.

The Mechanical Cryptographer: Tolerant Algebraic Side-Channel Attacks using pseudo-Boolean Solvers Yossef Oren (Tel-Aviv University) 8/7 1:30pm

ABSTRACT: Machine solvers are a class of general-purpose software tools which input a set of equations and output a satisfying assignment to these equations (or a proof of unsatisfiability). Solvers are used for a variety of practical applications, from VLSI verification to transportation route planning. Recently several authors have attempted to use solvers to perform one of the most challenging tasks in modern computer science – cryptanalysis of symmetric block ciphers such as AES. To use a solver for cryptanalysis, we provide it with a known plaintext, a known ciphertext and the set of mathematical equations which use an unknown secret key to transform between the two. The solver is then expected to output the secret key which links the given plaintext and ciphertext, thus satisfying the equation set. Fortunately, solvers are not currently capable of directly attacking modern ciphers. However, the situation is drastically different when side-channel data (information leaked from the cryptographic device due to its internal structure) is introduced into the equation.This talk will introduce side-channel cryptographic attacks, survey our latest efforts in using machine solvers to attack cryptosystems, and conclude with a successful attack on the AES cipher which requires surprisingly little side-channel data and computation time.

Joint work with Mathieu Renauld, Francois-Xavier Standaert and Avishai Wool

BIO: Yossi Oren is a Ph.D. student at the Computer Network and Security Lab at Tel-Aviv University. His research interests are: – Secure Hardware: Power analysis and other hardware attacks and countermeasures on cryptographic devices; Low-resource cryptographic constructions for lightweight computers such as RFID tags – Cryptography in the real world: Consumer and voter privacy in the digital era; Web application security

TARDIS: Time and Remanence Decay in SRAM to Implement Secure Protocols on Embedded Devices without Clocks Kevin Fu (UMass Amherst) 8/2 1:30pm

ABSTRACT: Lack of a locally trustworthy clock makes security protocols challenging to implement on batteryless embedded devices such as contact smartcards, contactless smartcards, and RFID tags. A device that knows how much time has elapsed between queries from an untrusted reader could better protect against attacks that depend on the existence of a rate-unlimited encryption oracle. The TARDIS (Time and Remanence Decay in SRAM) helps to locally maintain a sense of time elapsed without power and without special-purpose hardware. The TARDIS software computes the expiration state of a timer by analyzing the decay of existing on-chip SRAM memory. The TARDIS enables coarse-grained, hourglass-like timers such that cryptographic software can more deliberately decide how to throttle its response rate. Our experiments demonstrate that the TARDIS can measure time ranging from seconds to several hours depending on hardware parameters. Key challenges to implementing a practical TARDIS include compensating for temperature and handling variation across hardware. Our contributions are (1) the algorithmic building blocks for computing elapsed time from SRAM decay; (2) characterizing TARDIS behavior under different temperatures, capacitors, SRAM sizes, and chips; and (3) three proof of concept implementations that use the TARDIS to enable privacy-preserving RFID tags, to deter double swiping of contactless credit cards, and to increase the difficulty of brute force attacks against e-Passports. Joint work with Amir Rahmati, Mastooreh Salajegheh, Dan Holcomb, Jacob Sorber, Wayne Burleson. To appear at USENIX Security 2012.

BIO: Kevin Fu will join the University of Michigan as Associate Professor of Computer Science and Engineering in January 2013. His research is in the area of trustworthy computing and low-power embedded devices. In addition to systems security, RFID-scale computation, and energy-aware architectures, Dr. Fu’s interests include medical devices and health IT.Dr. Fu received his PhD in Electrical Engineering and Computer Science from MIT in 2005 and is currently Associate Professor of Computer Science at University of Massachusetts Amherst.

Dr. Fu has served as a visiting scientist at the Food & Drug Administration, the Beth Israel Deaconess Medical Center of Harvard Medical School, and MIT CSAIL, and is a member of the NIST Information Security and Privacy Advisory Board. He previously worked for Bellcore, Cisco, HP Labs, Microsoft Research, and Holland Community Hospital. He is the recipient of a Sloan Research Fellowship, the NSF CAREER award, and best paper awards from USENIX Security, IEEE S&P, and ACM SIGCOMM. Dr. Fu was named MIT Technology Review’s TR35 Innovator of the Year in 2009, and is a Senior Member of the Association for Computing Machinery.

Practice-Driven Cryptographic Theory Tom Ristenpart (University of Wisconsin) 7/31 1:30pm

ABSTRACT: Cryptographic standards abound: TLS, SSH, IPSec, XML Encryption, PKCS, and so many more. In theory the cryptographic schemes used within these standards solve well understood problems, yet a parade of damaging attacks leave us with the question: What gives? Theoreticians often suggest (at least in private) that the problems are well-understood and attacks arise because standardizers misunderstand cryptographic theory. I’ll use some of my recent work which uses provable-security techniques to analyze important standards (including TLS, HMAC, and PKCS#5) to argue that, just as often, it is the theoreticians who don’t have all the answers: analyzing practically-useful cryptography requires pushing models and proof techniques in never-before-considered directions. We’ll see how (what I’ll call) practice-driven cryptographic theory can lead to new understanding and improved confidence in cryptographic practice.

This talk will cover joint work with Mihir Bellare, Scott Coull, Yevgeniy Dodis, Kevin Dyer, Kenneth Paterson, Thomas Shrimpton, John Steinberger, and Stefano Tessaro.

Computing Elliptic Curves over Q(√5) Alyson Deines (University of Washington) 7/31 10:30am

ABSTRACT: I will discuss creating (conjectural) tables of elliptic curves over Q(√5) ordered by conductor up to the first curve of rank 2. We computed these curves by first computing weight (2,2) Hilbert modular forms over Q(√5) using an algorithm of Lassina Dembélé. Using various methods we constructed the (conjecturally) corresponding elliptic curves. I will also discuss newer work towards partially extending these results to the first curve of rank 3. This is joint work with Jonathan Bober, Joanna Gaski, Ariah Klages-Mundt, Benjamin LeVeque, R. Andrew Ohana, Sebastian Pancratz, Ashwath Rabindranath, Paul Sharaba, Ari Shnidman, William Stein, and Christelle Vincent.

BIO: Alyson Deines is a graduate student at the University of Washington.

Summer Number Theory Talk 6: Derivatives of p-adic L-functions Benjamin Lundell (University of Washington) 7/24 4:00pm

ABSTRACT: We will discuss a new approach to proving the Ferrero-Greenberg formula for the derivative of a Kubota-Leoplodt $p$-adic $L$-function at $s=0$. The aim is to provide a proof which uses two-variable $p$-adic $L$-functions in a manner analogous to the Greenberg-Stevens proof of the Mazur-Tate-Teitelbaum conjecture for elliptic curves. In the Kubota-Leopldt setting, we use the Katz two-variable $p$-adic $L$-function attached to an imaginary quadratic field $K$. This is joint work with Ralph Greenberg and Shaowei Zhang.

BIO: Benjamin Lundell is Acting Assistant Professor at the University of Washington. His primary research interests lie in algebraic number theory specifically the study of modular forms and Galois representations. Before coming to Washington, he studied at Cornell University, under the supervision of Ravi Ramakrishna, the University of Cambridge, and the University of Illinois at Urbana-Champaign.

Summer Number Theory Talk 5: Pairing-based methods for genus 2 curve jacobians with maximal endomorphism ring Sorina Ionica (LORIA) 7/24 2:30pm

ABSTRACT: Algorithms for constructing jacobians of genus 2 curves with nice cryptographic properties involve the computation of Igusa class polynomials for CM quartic fields. The CRT method used to compute these polynomials needs to find first a jacobian with maximal endomorphism ring over a finite field, and then enumerates all others jacobians having maximal endomorphism ring using horizontal isogenies. For $ell> 2$, we use Galois cohomology and the Tate pairing to compute the action of the Frobenius on the $ell$-torsion. In view of application to Igusa class polynomials computation, we deduce an algorithm to verify whether the jacobian of a genus 2 curve has locally maximal endomorphism ring at $ell$. Moreover, we derive a method to construct horizontal isogenies starting from a jacobian with maximal endomorphism ring.

Summer Number Theory Talk 4: Asymptotic nonlinearity of Boolean functions Francois Rodier (IML) 7/24 2:30pm

ABSTRACT: The nonlinearity of Boolean functions on the space Fm2 is important in cryptography. It is used to measure the strength of cryptosystems when facing linear attacks. In the case low degree of approximation attacks, we examine the nonlinearity of order r of a Boolean function, which equals the number of necessary substitutions in its truth table needed to change it into a function of degree at most r. Studies aimed at the distribution of Boolean functions according to the r-th order nonlinearity. Asymptotically, a lower bound is established in the higher order cases for almost all Boolean functions, whereas a concentration point is shown in the first and second order nonlinearity case. In the case of vectorial Boolean functions, a concentration point is shown in the first order nonlinearity case.

Summer Number Theory Talk 3: The distribution of zeroes of the zeta functions of Artin-Schreier covers over finite fields Alina Bucur (UC San Diego) 7/24 11:30am

ABSTRACT: I will give a quick overview of some new developments in studying the distribution of points and zeroes of the zeta functions for curves over finite fields. Then we will concentrate on the distribution of the zeroes of the zeta functions of the family of Artin-Schreier covers of the projective line over a fixed finite field as the genus goes to infinity. We consider both the global and the mesoscopic regimes, proving that in the limit, the number of zeroes with angles in a prescribed interval of $[-pi,pi)$ has a standard Gaussian distribution (when properly normalized).

BIO: Dr. Bucur received her Ph.D. from Brown University in 2006, and has since held a postdoctoral fellowship at the Institute for Advanced Study and a Moore Instructorship at MIT. Dr. Bucur’s research is in analytic number theory, specifically in multiple Dirichlet series and moments of L-functions. Dr. Bucur is undertaking an ambitious research program aimed at a better understanding of multiple Dirichlet series, and her work has been recognized with a Focused Research Grant from the National Science Foundation.

Dr. Bucur has a strong record of excellent teaching at Brown University and MIT, and received a Mathematics Outstanding Teaching Award at Brown. Dr. Bucur has been active in mentoring students and promoting participation by women graduate students and postdoctoral researchers in mathematics. At UCSD, Dr. Bucur will teach both undergraduate and graduate courses, including lower division calculus courses, and upper division and research-level graduate courses in number theory, algebra, and other subjects.

Summer Number Theory Talk 2: The Robbins phenomenon: unexpected numerical stability in p-adic arithmetic Kiran Kedlaya (UC San Diego) 7/24 10:30am

ABSTRACT: Since one cannot represent an arbitrary real number on a computer, it is standard to approximate real-number arithmetic using floating-point approximations. The situation is similar for p-adic numbers; we begin by introducing the analogue of floating-point arithmetic for p-adics. We then describe some known and conjectural examples of p-adic numerical stability in which algebraic structures (e.g., cluster algebras) work behind the scenes to keep the loss of numerical precision much lower than one might initially expect. A key example is the Dodgson (Lewis Carroll) condensation algorithm for computing determinants, for which we obtain a partial result towards a conjecture of Robbins. Joint work with Joe Buhler (CCR La Jolla).

BIO: Dr. Kedlaya received his Ph.D. in Mathematics from MIT in 2000. For the next three years, he held postdoctoral positions at the Mathematical Sciences Research Institute in Berkeley, at the University of California at Berkeley, and at the Institute for Advanced Study in Princeton. Since then, Dr. Kedlaya has been a faculty member at MIT, first as Assistant Professor and then as Associate Professor. Dr. Kedlaya is an expert on a broad range of topics related to arithmetic algebraic geometry and number theory, especially p-adic cohomology, p-adic Hodge theory, and computational number theory. He is the author of 49 research papers, and his research has been recognized with a highly prestigious five year Presidential Early Career Award for Scientists and Engineers (PECASE) from the NSF. In addition, he has been awarded a Sloan Research Fellowship, and a Clay Liftoff Fellowship.

Dr. Kedlaya has an outstanding record of dedicated teaching, has served as a mentor to numerous undergraduate and graduate students, and has been active in nurturing talented high school students in mathematics, with active involvement in organizational aspects for the International Mathematics Olympiad and as the author of a Putnam Exam problem book. At UCSD, Dr. Kedlaya will teach a range of courses, ranging from lower division calculus to research-level courses in algebra and number theory.

Dr. Kedlaya’s research is in the area of number theory and arithmetic algebraic geometry. His specialties include p-adic analytic methods, p-adic Hodge theory, algorithms, and applications in computer science (including cryptography).

Summer Number Theory Talk 1: Computing many rational Hilbert modular forms over Q(sqrt(5)) William Stein (University of Washington) 7/24 9:00am

ABSTRACT: I will talk about an ongoing computation to enumerate all (modular) elliptic curves over Q(sqrt(5)) up to the first of rank 4.

BIO: William Stein is a professor of mathematics at the University of Washington. In his mathematics research, he uses the Birch and Swinnerton-Dyer conjecture as motivation to understand the constellation of arithmetic invariants associated to optimal quotients of J0(N). He also uses computers to do explicit computations on modular abelian varieties, and is the main author of SAGE.

In May 2000 he received a Ph.D. degree in mathematics from UC Berkeley (here is his Ph.D. genealogy tree). His thesis involved the Birch and Swinnerton-Dyer conjecture for modular abelian varieties. From May 2000 until May 2001 he was an NSF Postdoctoral Fellow at Harvard, during which time he traveled a huge amount. From 2001 to 2005, he was a Benjamin Peirce Assistant Professor of Mathematics at Harvard University. He joined the UW mathematics department in the Spring of 2006.

A Workflow for Differentially-Private Graph Synthesis Sharon Goldberg (Boston University) 7/19 1:30pm

ABSTRACT: We present a new workflow for differentially-private publication of graph topologies. First, we produce differentially private measurements of interesting graph statistics using our new version of the PINQ programming language, Weighted PINQ, which is based on a generalization of differential privacy to weighted sets. Next, we show how to generate graphs that fit any set of measured graph statistics, even if they are inconsistent (due to noise), or if they are only indirectly related to actual statistics that we want our synthetic graph to preserve. We do this by combining the answers to Weighted PINQ queries with a probabilistic inference technique that allows us to synthesize graphs where the statistic of interest aligns with that of the protected graph. I will show how to cast a few graph statistics (degree distribution, edge multiplicity, joint degree distribution) as queries in Weighted PINQ, and then present experimental results of synthetic graphs generated from the answers to these queries.

Joint work with Davide Proserpio (BU) and Frank McSherry (MSR).

BIO: Sharon Goldberg is an Assistant Professor in the Department of Computer Science at Boston University. Her research focuses on finding practical solutions to problems in network security, by leveraging formal techniques from cryptography and game theory. She received her Ph.D. from Princeton University in 2009, and her B.A.Sc. from the University of Toronto in 2003.

Index calculus and the elliptic curve discrete logarithm problem Claus Diem (University of Leipzig) 7/2 1:30 pm

ABSTRACT: Let p be a prime number and B a primitive root modulo p. This means by definition that for every natural number A coprime to p there is a natural number e with A^e equiv B bmod p. The smallest such exponent is classically called the index of A modulo p with respect to the base B. Indices are discrete analoga to logarithms, and accordingly nowadays they are usually called discrete logarithms. The question for their efficient computation was already raised in the 19th century but it gained particular relevance because the security of a great number of cryptographic protocols is based on the difficulty of index computation, or, as one says, on the difficulty of the discrete logarithm problem.Index calculus is a method to compute indices efficiently. Now indices or discrete logarithms can be defined in any finite group, and the question arises if one can substitute the group Fp by another group in which index calculus is not possible. This question lead to the development of elliptic curve cryptography.In the talk I will present the index calculus method and discuss the question if index calculus is possible in elliptic curves.

BIO: Claus Diem is visiting from the University of Leipzig. His work is supported by a scholarship from the Deutsche Forschungsgemeinschaft.

The Round Complexity of (concurrent, resettable, efficient) Zero Knowledge in the Bare Public-Key Model Ivan Visconti (University of Salerno) 6/14 1:30 pm

ABSTRACT: This talk will first revisit previous work in the Bare Public-Key (BPK) model pointing out subtle problems concerning their security proofs of concurrent and resettable zero knowledge.Then the talk will focus on showing a new technique to achieve round-optimal concurrent and resettable zero knowledge in the BPK model.

Next the talk will focus on efficient instantiations of the above constructions. It will point out a major limitation of the OR composition of Sigma protocols [CDS94] and an interesting open problem.Finally the talk will present a new technique for OR composition of Sigma protocols that solve the above open problem and can be of broader interest.

Note: Joint work with Alessandra Scafuro. The first part of this work has been published in EUROCRYPT 2012; the second part is a manuscript in preparation.

BIO: Ivan Visconti is an assistant professor at the Dipartimento di Informatica ed Applicazioni, Faculty of Mathematical, Physical and Natural Sciences of the University of Salerno (ITALY). His research focuses on foundations of cryptography and is supported by national grants and EU networks of excellence ECRYPT, ECRYPT II.Ivan Visconti got his PhD in Computer Science in 2003 from Università di Salerno and has been a Post-Doctoral fellow at the Département d’Informatique of the École Normale Supérieure, Paris (FRANCE). Since October 2010 he is on sabbatical leave visiting University of California at Los Angeles.

Verifiable Computation via Quadratic Span Programs Bryan Parno (MSR) 5/17 1:30 pm

ABSTRACT: We introduce a new characterization of the NP complexity class, called Quadratic Span Programs (QSPs), which is a natural extension of span programs defined by Karchmer and Wigderson. Our main motivation is the construction of succinct arguments of NP-statements that are quick to construct and verify. QSPs seem well-suited for this task, perhaps even better than Probabilistically Checkable Proofs (PCPs).

In 2010, Groth constructed a NIZK argument in the common reference String (CRS) model for Circuit-SAT consisting of only 42 elements in a bilinear group. Interestingly, his argument does not (explicitly) use PCPs. But his scheme has some disadvantages — namely, the CRS size and prover computation are both quadratic in the circuit size. In 2011, Lipmaa reduced the CRS size to quasi-linear, but with prover computation still quadratic.

Using QSPs we construct a NIZK argument in the CRS model for Circuit-SAT consisting of just 7 group elements. The CRS size is linear in the circuit size, and prover computation is quasi-linear, making our scheme seemingly quite practical. (The prover only needs to do a linear number of group operations; the quasi-linear computation is a multipoint evaluation and interpolation.)

Our results are complementary to those of Valiant (TCC 2008) and Bitansky et al. (2012), who use “bootstrapping” (recursive composition) of arguments to reduce CRS size and prover and verifier computation. QSPs also provide a crisp mathematical abstraction of some of the techniques underlying Groth’s and Lipmaa’s constructions.

BIO: Bryan Parno is a researcher in Microsoft Research’s Security and Privacy Research Group. He received his PhD and Master’s degrees at Carnegie Mellon University, where he was advised by Adrian Perrig, and a Bachelor’s degree from Harvard University. His current work focuses on the foundations of trust on modern computers. His research interests include computer security, systems, networks, and applied cryptography. In his spare time, he enjoys photography and volunteering as an Emergency Medical Technician.

Adaptively Secure Multi-Party Computation, Revisited Sanjam Garg (UCLA) 5/3 1:30 pm

ABSTRACT: Adaptively secure multiparty computation is an essential and fundamental notion in cryptography. In this work we focus on the basic question of constructing a multiparty computation protocol secure against a malicious, adaptive adversary in the stand-alone setting without honest majority in the plain model.It has been believed that this question can be resolved by composing known protocols from the literature. We show that in fact, this belief is fundamentally mistaken. In particular, we show:

• Round inefficiency is unavoidable when using black-box simulation: There does not exist any o(frac{n}{log{n}}) round protocol that adaptively securely realizes a (natural) n-party functionality with a black-box simulator. Note that most previously known protocols in the adaptive security setting relied on black-box simulators.
• A constant round protocol using non-black-box simulation: We construct a constant round adaptively secure multiparty computation protocol in a setting without honest majority that makes crucial use of non-black box techniques.Taken together, these results give the first resolution to the question of adaptively secure multiparty computation protocols with a malicious dishonest majority in the plain model, open since the first formal treatment of adaptive security for multiparty computation in 1996. (Joint work with Amit Sahai)

BIO: Sanjam Garg is a PhD student in Cryptography at University of California Los Angeles. He is a recipient of the Chancellor’s Prize at UCLA. He received his Bachelors in Computer Science and Engineering from Indian Institute of Technology Delhi in 2008. Sanjam has published several papers in top cryptography and security conferences such as Crypto, Eurocrypt, TCC, CCS, and so on. He has given talks at NTT Labs (Japan), Technion (Israel) and Tel Aviv University (Israel).

New Constructions of Lossy Trapdoor Functions Brett Hemenway (University of Michigan) 4/26 1:30 pm

ABSTRACT: Lossy Trapdoor Functions (LTFs) were introduced by Peikert and Waters in STOC ’08, and since that time they have become an extremely useful cryptographic primitive. Lossy Trapdoor Functions yield simple constructions of pseudorandom generators, collision resistant hash functions, IND-CCA secure cryptosystems, deterministic encryption, leaky pseudoentropy functions and more.

In this talk, I’ll show a number of new constructions of LTFs from a variety of cryptographic primitives and number theoretic assumptions. These constructions can be cast into two broad categories: exploiting (group) homomorphisms of common cryptosystems, and derandomizing randomized lossy primitives.

BIO: Brett Hemenway received his Bachelor’s degree from Brown University in 2004 and his PhD in mathematics from UCLA in 2010 under Rafail Ostrovsky. He is currently a postdoctoral assistant professor at the University of Michigan. His research focuses on coding theory and cryptography.

Practical Private Information Retrieval Femi Olumofin (Mathematical Sciences, Strategic Technology & Innovation Center, Pitney Bowes) 4/19 1:30 pm

ABSTRACT: The subject of online privacy has been attracting a lot of attention in recent years, especially as more users are beginning to care about the privacy of their online activities. This increased privacy awareness has renewed the interest of the research community on cryptographic primitives, such as private information retrieval, oblivious transfer, oblivious RAM, and searchable encryption, which are designed to help users preserve the privacy of their queries and/or access to curious or malicious hosts. In this talk, I will show how we revisited the computational practicality of private information retrieval schemes and found the end-to-end response times of a single-server lattice-based scheme and two multi-server information-theoretic PIR schemes to be one to three orders of magnitude (10 — 1000 times) smaller than the trivial scheme for realistic computation power and network bandwidth. Then, I will describe how we utilized PIR to enhance the scalability of the Tor anonymous communication network by two orders of magnitude. We clarify existing result on the computational practicality of PIR and provide an extension to multi-server PIR schemes and single-server PIR schemes that do not rely heavily on number theory.

BIO: Femi Olumofin earned his PhD in computer science from the University of Waterloo in 2011. He completed his thesis work on private information retrieval at the Cryptography, Security, and Privacy (CrySP) research group, under the supervision of Prof. Ian Goldberg. Previously, he earned MS and BS degrees in computer science from the University of Manitoba and the University of Benin, respectively. His research interest is in the areas of security, privacy, and applied cryptography. He is currently focused on applying cryptographic protocols to solve security and privacy problems in the domains of databases, location-based services, cloud computing, online behavioural advertising, and onion routing. Recently, he joined the Mathematical Sciences group at the Strategic Technology and Innovation Center of Pitney Bowes to help drive privacy research.

Approximately Strategy-Proof Voting Eleanor Birrell (Cornell University) 3/1 2:00 pm

ABSTRACT: The classic Gibbard-Satterthwaite Theorem establishes that only dictatorial voting rules are strategy-proof; under any other voting rule, players have an incentive to lie about their true preferences. We introduce a new approach to circumventing this result: we consider randomized voting rules that approximate a deterministic voting rule and are approximately strategy-proof. We show that any deterministic voting rule can be approximated by an approximately strategy-proof randomized voting rule, and we provide bounds on the parameters that can be achieved.

BIO: Eleanor Birrell is currently a PhD student at Cornell University, where she works with Rafael Pass and Fred Schneider.

Oblivious Access to Remote Data Storage Olya Ohrimenko (Brown University) 2/21 1:30 pm

ABSTRACT: The ”cloud” is emerging as the next generation of data storage where users can remotely keep their data and leave its management to a third party, e.g. Amazon S3 or Microsoft Azure. However, the fact that users no longer have physical possession of the data raises new challenges in terms of data privacy. Storing the data in encrypted form is a key component in maintaining the privacy of the data. However, encrypting the data is not enough since information about the data may be leaked through the pattern in which users access the data. We show how to achieve efficient privacy-preserving data access using a combination of encryption, which directly hides data values, and stateless oblivious RAM simulation, which hides the pattern of data accesses.

In this talk we propose a method with O(log n) worst-case access overhead for simulating users’ requests to outsourced data of size n, using a scheme that is data-oblivious with very high probability. We assume that the simulation has access to a small private workspace but does not maintain state in between data access requests. Our simulation makes use of pseudo-random hash functions and is based on a novel hierarchy of cuckoo hash tables that all share a common stash. The method outperforms all previous techniques for stateless clients in terms of access overhead.

Existing oblivious storage solutions typically involve small amortized overheads for obscuring the access pattern, but nevertheless involve potentially huge variations in access times, depending on when they occur. To this end, we show how to de-amortize oblivious storage simulations so that each request takes a worst-case bounded amount of time.

We also provide experimental results from a prototype implementation of our scheme. We show that the involved constants are small resulting in at most 2log n round trips for each client request. Finally, we demonstrate that the performance of our stateless scheme is comparable to a more powerful scheme where a client is allowed to keep a state.Joint work with: Michael T. Goodrich, Michael Mitzenmacher and Roberto Tamassia

BIO: Olya Ohrimenko is a Ph.D. candidate in the Department of Computer Science at Brown University working with Professor Roberto Tamassia. Her research interests include designing algorithms and data structures to ensure user privacy and data integrity in the cloud-based storage model. Olya received a BCS (Hons) degree from The University of Melbourne in 2007 and her M.Sc. degree from Brown University in 2010.

ZKPDL: A Language-Based System for Efficient Zero-Knowledge Proofs and Electronic Cash Sarah Meiklejohn (UCSD) 2/2 1:30 pm

ABSTRACT: In recent years, many advances have been made in cryptography, as well as in the performance of communication networks and processors. As a result, many advanced cryptographic protocols are now efficient enough to be considered practical, yet research in the area remains largely theoretical and little work has been done to use these protocols in practice, despite a wealth of potential applications.

This paper introduces a simple description language, ZKPDL, and an interpreter for this language. ZKPDL implements non-interactive zero-knowledge proofs of knowledge, a primitive which has received much attention in recent years. Using our language, a single program may specify the computation required by both the prover and verifier of a zero-knowledge protocol, while our interpreter performs a number of optimizations to lower both computational and space overhead.Our motivating application for ZKPDL has been the efficient implementation of electronic cash. As such, we have used our language to develop a cryptographic library, Cashlib, that provides an interface for using e-cash and fair exchange protocols without requiring expert knowledge from the programmer.

This is joint work with C. Chris Erway, Alpetkin Kupcu, Theodora Hinkle, and Anna Lysyanskaya, and appeared at USENIX Security 2010.

BIO: Sarah is a third-year PhD student in Computer Science at the University of California, San Diego. She is a member of the Security and Cryptography Group and is advised by Hovav Shacham and supported by a fellowship from the Charles Lee Powell Foundation. Before starting at UCSD, she obtained an Sc.B. in Mathematics and an Sc.M. in Computer Science from Brown University under the guidance of Anna Lysyanskaya. Her research interests focus on the interface between security and cryptography; i.e., trying to improve the way in which cryptographic protocols are incorporated into secure systems, as well as coming up with cryptographic models that accurately reflect real-world attacks. Most recently, Sarah spent the summer of 2011 at MSR Redmond, working in the cryptography group with Melissa Chase.

Generalized oblivious Transfer (GOT) Samuel Ranellucci (University of Montreal) 1/4 1:30 pm

ABSTRACT: In this paper, we introduce a primitive known as Verifiable Oblivious Transfer. It is similar to oblivious transfer except that the sender is commited to its input. We then generate protocols for Generalized Oblivious Transfer by secret sharing using the Verifiable Oblivious Transfer primitive based on previous work. The protocols are universally composable. The GOT protocol is used to instantiate Batch Single-Choice Cut-And-Choose OT which in conjunction with a modification to the main protocol of [LP11], achieves constant round secure function evaluation based on Yao’s Garbled Circuit. In addition, the idea of GOT is used in conjunction with linear secret sharing and commitments to instantiate a primitive known as Multi-Sender K-Out-of-N OT. This primitive is the most important building block of the optimization of the IPS compiler presented in [LOP11]. In contrast to their specific computational assumptions, our protocols only require black-box Verifiable OT. In addition, the GOT protocols can be used to execute Priced Oblivious Transfer.

Privacy Amplification and Non-Malleable Extractors Via Character Sums Xin Li (University of Washington) 11/10 2:00 pm

ABSTRACT: In studying how to communicate over a public channel with an active adversary, Dodis and Wichs introduced the notion of a non-malleable extractor. A non-malleable extractor dramatically strengthens the notion of a strong extractor in the sense that it requires the output to be close to uniform given the seed as well as the output of the extractor on an arbitrarily related different seed.

We construct the first explicit non-malleable extractor. Our extractor works for sources with entropy rate above half. To achieve a polynomial running time when outputting many bits, we rely on a widely-believed conjecture about the distribution of prime numbers in arithmetic progressions.

Using our non-malleable extractor, we obtain protocols for “privacy amplification”: key agreement between two parties who share a weakly-random secret. Our protocols work in the presence of an active adversary with unlimited computational power, and have asymptotically optimal entropy loss. When the secret has entropy rate greater than 1/2, the protocol takes two rounds. When the secret has entropy rate delta for any constant delta>0, our protocol takes a constant (polynomial in 1/delta) number of rounds. Our protocols run in polynomial time under the above well-known conjecture about primes.Joint work with Yevgeniy Dodis, Trevor D. Wooley and David Zuckerman.

BIO: Xin Li is a postdoctoral researcher in the theory group of the computer science & engineering department at the University of Washington, Seattle. His main research interests include the use of randomness in computation, complexity theory and theory of computation in general. He received his B.S. and M.S. from Tsinghua University, China and his Ph.D. from the University of Texas at Austin.

How to solve a 112-bit ECDLP using game consoles Joppe Bos (EPFL) 10/13 1:30 pm

ABSTRACT: In this presentation I will outline two projects which I have been working on during my PhD. Both projects are related to the elliptic curve discrete logarithm problem (ECDLP): the theoretical foundation of many modern cryptosystems. First I will outline how we have set a new record by solving the ECDLP over a 112-bit prime field using a cluster of PlayStation 3 game consoles in 2009. Next, the negation map optimization is discussed: this is an technique to speed up the Pollard rho method when solving the ECDLP. It is well known that the random walks used by Pollard rho when combined with the negation map get trapped in fruitless cycles. I will present that previously published approaches to deal with this problem are plagued by recurring cycles: effective alternative countermeasures are proposed.

BIO: Joppe Bos is a PhD student under supervision of Prof. Arjen Lenstra at the laboratory for cryptologic algorithms, EPFL, Switzerland. His research interest include public-key cryptanalysis, fast arithmetic and efficient implementations of cryptologic algorithms with a focus on elliptic curve cryptography and integer factorization algorithms. Currently he is doing an internship with Peter Montgomery at MSR and works on factoring large integers using graphics cards.

Secure Biometric Computation and Outsourcing Marina Blanton (University of Notre Dame) 9/1 1:30 pm

ABSTRACT: Recent advances in biometric recognition and the increasing use of biometric data prompt significant privacy challenges associated with the possible misuse, loss, or theft of biometric data. There are legitimate reasons for biometric matching to be performed by two mutually distrustful parties, where due to privacy and liability considerations, neither party is willing to share its data. Alternatively, biometric experiments run by a single entity are often so large in scale that they are inevitably placed on an untrusted computational cloud or grid, where sensitive biometric data must also be protected. This gives rise to the need to develop secure computation and outsourcing techniques over biometric data where no information is revealed to the participants except the desired outcome of the computation and the outcome of the computation can be trusted. In this talk, I will describe our recent results for securely comparing biometric images and outsourcing computation over biometric data in a robust manner. Most of the talk discusses techniques for matching of iris codes.

BIO: Marina Blanton is an Assistant Professor in the Department of Computer Science and Engineering at the University of Notre Dame. She received her Ph.D. in CS from Purdue University in 2007, MS in CS from Purdue University in 2004, and MS in EECS from Ohio University in 2002. Dr. Blanton’s research interests lie in information security, privacy, and applied cryptography. She has over 40 research publications, is a co-editor of a recently published two-volume “Algorithms and Theory of Computation Handbook,” and is actively involved in professional service.

Efficient Oblivious Automata Evaluation and Its Application Payman Mohassel (University of Calgary) 8/30 1:30 pm

ABSTRACT: Abstract: Oblivious Automata Evaluation allows two parties -a client who holds an input string X and a server who holds an Automata G- to learn the result of evaluating G on X but nothing else. In this talk, I will describe a simple and efficient, secure two-party construction for this problem. I will also explain some applications of our construction to pattern matching and intrusion detection. Finally, I report on the results of some experiments based on a prototype implementation.Joint work with Salman Niksefat and Saeed Sadeghian.

BIO: Payman Mohassel is an assistant professor in the Department of Computer Science at University of Calgary. He received his Ph.D. from University of California Davis, in 2009 under the supervision of Matthew Franklin. His research interests are in both practical and theoretical aspects of cryptography, and information security. Some of his more recent projects include “efficient and privacy-preserving computation”, “provably secure encryption and signature schemes”, and “privacy in genomic computation”.

Cryptography with Imperfect Randomness Bhavana Kanukurthi (UCLA) 8/4 1:30 pm

ABSTRACT: Cryptographic protocols, though powerful theoretically, are typically built for certain ideal conditions that are frequently violated in practice. For instance, it is commonly assumed that a user wishing to perform secure computation has access to perfect randomness and is performing his computation on a device whose internals are completely shielded from adversarial observation and tampering. This talk will survey some of my recent results on designing cryptographic primitives that are secure under less-than-ideal conditions. I will first present a brief overview of my work on enabling even users with just weak secrets such as biometrics and passwords to do cryptography. I will then present the details of my work on tamper-resilient cryptography which removes the assumption that cryptographic computation is performed in a perfectly sealed black box.

This talk is based on joint works with Yael Kalai and Amit Sahai (CRYPTO 2011) and Nishanth Chandran, Rafail Ostrovsky and Leonid Reyzin (STOC 2010).

BIO: Bhavana Kanukurthi is a post-doctoral researcher at UCLA, working under the guidance of Prof. Rafail Ostrovsky. She recently received her PhD in Computer Science at Boston University, where she was advised by Prof. Leonid Reyzin. She is a recipient of the 2010 Boston University Computer Science Research Excellence award. Her research lies in the area of cryptography.

Cryptography with Imperfect Randomness Vanessa Teague (University of Melbourne) 8/1 1:30 pm

ABSTRACT: Code voting seeks to address the issues of privacy and integrity for Remote Internet Voting. It sidesteps many of the inherent vulnerabilities of the Internet and client platforms but it does not provide end-to-end verification that votes are counted as cast. In this paper, we propose a simple technique to enhance the verifiability of code voting by ensuring that the Vote Server can only access the acknowledgement codes if the vote code is correctly registered by a threshold set of Trustees. The mechanism adds an extra level of verifiability in registering and counting the vote. Voter-verification is simple and direct: the voters need only check that the acknowledgement code returned to them agrees with the value on their code sheet. To ensure receipt-freeness we propose the use of a single acknowledgement code per code sheet, rather than individual acknowledgement codes for each candidate as with usual code voting.

I will first present Pretty Good Democracy for voting schemes in which the voter selects a single candidate, then show how it can be extended to more expressive voting schemes such as Borda, approval voting and STV.(Joint work with Peter Ryan, University of Luxembourg, and James Heather, University of Surrey.)

BIO: Dr Vanessa Teague is a researcher at the University of Melbourne. After completing her PhD thesis at Stanford on cryptographic protocols for rational participants, she returned to Australia and focused on end-to-end verifiable protocols for secure electronic voting, particularly those suitable for the obscure and complicated voting system used in Aus. She is co-chair of this year’s USENIX/ACCURATE Electronic Voting Technologies workshop and Workshop on Trustworthy Elections (EVT/WOTE 2011). She has also recently made a hobby of public criticism of insecure electronic voting protocols that are unsuitable for use in Australian elections but were used anyway.

Computing the unit group, class group and compact representations in algebraic function fields Sean Hallgren (Penn State University) 7/28 1:30 pm

ABSTRACT: Number fields and global function fields have many similar properties. Both have many applications to cryptography and coding theory, and the main computational problems for number fields, such as computing the ring of integers and computing the class group and the unit group, have analogues over function fields. The complexity of the number field problems has been studied extensively and these problems have been the source of some exponential speedups by quantum computation. In this paper we study the analogous problems in function fields. We show that there are efficient quantum algorithms for computing the unit group, the class group and for solving the principal ideal problem in function fields of arbitrary degree. We show that compact representations exist, which allows us to show that the principal ideal problem is in NP. Unlike the number field case, we are also able to show that these compact representatives can be computed efficiently.

BIO: Sean Hallgren is an Associate Professor at Penn State University. He works on quantum computation, with an emphasis on understanding when there are exponential speedups by quantum algorithms. He received his B.S. from Carnegie Mellon University and his Ph.D. from the University of California, Berkeley. Prior to joining Penn State he ran the quantum computing group at NEC Laboratories. He is a recipient of the NSF CAREER award, the PECASE award and several teaching awards.

Charm: A Framework for Rapidly Prototyping Cryptosystems Matthew Green (Johns Hopkins University) 7/19 1:30 pm

ABSTRACT: Over the past decade the cryptographic research community has made impressive progress in developing new cryptographic protocols. This work has advanced our understanding of basic technologies such as public key encryption, key agreement, and digital signatures. Moreover, it has given us entirely new paradigms for securing data, such as Attribute Based Encryption, anonymous credentials and techniques for computing on encrypted data.

Despite these advances, only a trickle of new cryptographic technology has filtered down to the systems community in the form of useable cryptographic implementations. Even supported prototype research implementations are few and far between. This is a major loss for researchers, to say nothing of industry and the open source community.

In this talk we introduce Charm, an extensible Python-based framework for rapidly prototyping cryptographic systems. Charm was designed from the ground up to support the development of advanced cryptographic schemes. It includes support for multiple cryptographic settings, an extensive library of re-usable code, along with the infrastructure necessary to quickly implement interactive protocols. Our framework also provides a series of specialized tools that enable different cryptosystems to interoperate.

This paper describes Charm and the various capabilities provided through our modular architecture. Through several examples, we show that our approach produces a potential order of magnitude decrease in code size compared to standard C implementations, while inducing an acceptable performance impact.

BIO: Matthew Green is an Assistant Research Professor at the Johns Hopkins University Information Security Institute. His research focus is on cryptographic techniques for maintaining users’ privacy, and on technologies that enable the deployment of privacy-preserving protocols. He is also a co-founder of Independent Security Evaluators (ISE), a custom security evaluation firm with a global client base.

Along with a team at Johns Hopkins and RSA Laboratories, he discovered flaws in the Texas Instruments Digital Signature Transponder, a cryptographically-enabled RFID device used in the Exxon Speedpass payment system and in millions of vehicle immobilizers. He is a recipient of the PET Award for his contribution to privacy enhancing technologies.

Unbounded HIBE and Attribute-Based Encryption Brent Waters (University of Texas, Austin) 7/19 10:30 am

ABSTRACT: We present HIBE and ABE schemes which are “unbounded” in the sense that the public parameters do not impose additional limitations on the functionality of the systems. In all previous constructions of HIBE in the standard model, a maximum hierarchy depth had to be fixed at setup. In all previous constructions of ABE in the standard model, either a small universe size or a bound on the size of attribute sets had to be fixed at setup.

Our constructions avoid these limitations. We use a nested dual system encryption argument to prove full security for our HIBE scheme and selective security for our ABE scheme, both in the standard model and relying on static assumptions. Our ABE scheme supports LSSS matrices as access structures and also provides delegation capabilities to users.This is joint work with Allison Lewko.

BIO: Dr. Brent Waters received his Ph.D. in Computer Science from Princeton University in 2004. From 2004-2005, he was a post-doctoral at Stanford University then worked at SRI as a Computer Scientist in the Principled Systems group. In 2008 he joined the faculty at The University of Texas at Austin as an assistant professor. Dr. Waters’ research interests are in the areas of computer security and applied cryptography. His work has focused on Identity-Based Cryptography, security of broadcast systems, and authentication of remote systems. He has award and invited papers. He is noted as a founder of functional encryption. Dr. Waters both publishes and has served on the program committees of the top technical security venues (CRYPTO, Eurocrypt, the ACM Conference on Computer and Communications Security (CCS), Usenix Security and the IEEE Conference on Security and Privacy). Dr. Waters has been an invited speaker in industry and at research Universities, including MIT, CMU, and Stanford. He was the keynote speaker on functional encryption at the2008 NIST workshop on Identity-Based Encryption. Dr. Waters is a National Academy of Sciences Kavli Fellow and recipient of the NSF CAREER award, a Microsoft Faculty Fellow, and a Sloan Research Fellowship.

Using Extensions of Min-Entropy to Help with Key Agreement and Leakage Resilience Leo Reyzin (Boston University) 7/14 1:30 pm

ABSTRACT: There are many different notions of information-theoretic entropy and its computational analogues. The right notion and a toolbox of lemmas can make for beautifully simple proofs. Drawing on examples from information-theoretic key agreement and leakage-resilient cryptography (no background in either is assumed), I will show how various extensions of min-entropy can help analyze cryptographic constructions. I will also present some (not always well-formed) open problems.

BIO: Leo Reyzin is an Associate Professor of Computer Science at Boston University, conducting research on extending cryptographic techniques to provide protection in more hostile environments. He received his A.B. in computer science from Harvard, and S.M. and Ph.D. in cryptography at MIT. He is a recipient of the National Science Foundation’s CAREER award and of Boston University’s Neu Family Award for Excellence in Teaching.

Secure Computation with Sublinear Amortized Work Mariana Raykova (Columbia University) 7/8 1:30 pm

ABSTRACT: We present the first protocol for secure two-party computation that allows a client and a server to evaluate an arbitrary function f with an amortized poly-logarithmic computational overhead over the insecure version of f. For functions that can be computed in sublinear time, this yields the first general secure protocol with sublinear amortized complexity. We provide a generic and simple protocol that achieves the asymptotic improvement, as well as a vastly optimized practical protocol, using new techniques for oblivious memory access, and relying on existing two-party computation protocols to evaluate a small number of carefully selected simple operations. We achieve orders of magnitude performance improvements, even on today’s moderate input sizes, for (amortized) execution of important tasks, such as binary search on a large dataset – a core building block for secure DB access, location-based services, etc. In general, our approach will likely be advantageous in amortized computations where the server’s input is large, and the client’s input and the computed program are small.Joint work with Dov Gordon, Jonathan Katz, Vladimir Kolesnikov, Tal Malkin, Yevgeniy Vahlis

BIO: Mariana is a PhD student at Columbia University working in the areas of cryptography and security with Tal Malkin and Steve Bellovin. Her research focuses on secure computation and more specifically on improving efficiency that aims to make secure multiparty computation protocols usable in practice. This includes considering new computational models, specific functionalities, relaxed security notions. The last two years she was an intern with the crypto group at MSR, and this summer she is working in the security group.

Outsourcing Multi-Party Computation Seny Kamara (MSR Redmond) 7/7 1:30 pm

ABSTRACT: We initiate the study of secure multi-party computation (MPC) in a server-aided setting, where the parties have access to a single server that (1) does not have any input to the computation; (2) does not receive any output from the computation; but (3) has a vast (but bounded) amount of computational resources. In this setting, we are concerned with designing protocols that minimize the computation of the parties at the expense of the server.

We develop new definitions of security for this server-aided setting, that generalize the standard simulation-based definitions for MPC, and allow us to formally capture the existence of dishonest but non-colluding participants. This requires us to introduce a formal characterization of non-colluding adversaries that may be of independent interest.

We then design general-purpose server-aided multi-party protocols that are more efficient (in terms of computation and communication) for the parties than the alternative of running a standard MPC protocol (i.e., without the server). Finally, we give a general transformation from any secure delegated computation scheme to a server-aided two-party protocol. Our transformation formalizes the intuitive connection between the problems of server-aided computation and verifiable computation by interpreting the former as a means for verifiably and privately outsourcing a secure multi-party computation protocol to an untrusted worker.

Joint work with Payman Mohassel and Mariana Raykova.

BIO: Seny Kamara is a researcher in the Crypto Group in XCG at Microsoft Research. He received his Ph.D. in Computer Science from Johns Hopkins University under the supervision of Fabian Monrose. His main research interests are in security and cryptography and his recent work has focused on designing new cryptographic models and techniques to alleviate security and privacy concerns that arise in the context of cloud computing. In 2006, he was a research fellow at the UCLA Institute for Pure and Applied Mathematics and has been the recipient of the Johns Hopkins Phillips and Camille Bradford fellowship and of the Bell Labs Graduate Research fellowship.

Fully Homomorphic Encryption over the integers with Shorter Public Keys Avradip Mandal (University of Luxembourg) 6/30 1:30 pm

ABSTRACT: At Eurocrypt 2010 van Dijk {sl et al.} described a fully homomorphic encryption scheme over the integers. The main appeal of this scheme (compared to Gentry’s) is its conceptual simplicity. This simplicity comes at the expense of a public key size in ${cal tilde O}(lambda^{10})$ which is too large for any practical system. In this paper we reduce the public key size to ${cal tilde O}(lambda^{7})$ by encrypting with a quadratic form in the public key elements, instead of a linear form. We prove that the scheme remains semantically secure, based on a stronger variant of the approximate-GCD problem, already considered by van Dijk {sl et al}.

We also describe the first implementation of the resulting fully homomorphic scheme. Borrowing some optimizations from the recent Gentry-Halevi implementation of Gentry’s scheme, we obtain roughly the same level of efficiency. This shows that fully homomorphic encryption can be implemented using simple arithmetic operations.

BIO: Avradip Mandal is a PhD student at University of Luxembourg, Luxembourg under the supervision of Jean-Sebastien Coron. Currently he is an intern at eXtreme Computing Group, Microsoft Research with Lan Nguyen as his mentor. Before he obtained M.Math and B.Tech from University of Waterloo, Canada and Indian Institute of Technology Kharagpur, India respectively.

Leftover Hash Lemma, Revisited Yevgeniy Dodis (New York University) 6/23 1:30 pm

ABSTRACT: The famous Leftover Hash Lemma (LHL) states that (almost) universal hash functions are good randomness extractors. Despite its numerous applications, LHL-based extractors suffer from the following two drawbacks: (1) Large Entropy Loss: to extract v bits from distribution X of min-entropy m which are e-close to uniform, one must set v= 2*log(1/e). (2) Large Seed Length: the seed length n of universal hash function required by the LHL must be linear in the length of the source. Quite surprisingly, we show that both limitations of the LHL — large entropy loss and large seed — can often be overcome (or, at least, mitigated) in various quite general scenarios. First, we show that entropy loss could be reduced to L=log(1/e) for the setting of deriving secret keys for most cryptographic applications, including signatures/MACs, CPA/CCA-secure encryption, etc. Specifically, the security of these schemes gracefully degrades from e to at most e + sqrt(e * 2^{-L}). (Notice that, unlike standard LHL, this bound is meaningful even for negative entropy loss, when we extract more bits than the the min-entropy we have!) Second, we study the soundness of the natural *expand-then-extract* approach, where one uses a pseudorandom generator (PRG) to expand a short “input seed” S into a longer “output seed” S’, and then use the resulting S’ as the seed required by the LHL (or, more generally, any randomness extractor). Unfortunately, we show that, in general, expand-then-extract approach is not sound if the Decisional Diffie-Hellman assumption is true. Despite that, we show that it is sound either: (1) when extracting a “small” (logarithmic in the security of the PRG) number of bits; or (2) in *minicrypt*. Implication (2) suggests that the sample-then-extract approach is likely secure when used with “practical” PRGs, despite lacking a reductionist proof of security! The paper will appear at CRYPTO 2011 and can be found at http://eprint.iacr.org/2011/088

BIO: Yevgeniy Dodis is an Associate Professor of computer science at New York University. Dr. Dodis received his summa cum laude Bachelors degree in Mathematics and Computer Science from New York University in 1996, and his PhD degree in Computer Science from MIT in 2000. Dr. Dodis was a post-doc at IBM T.J.Watson Research center in 2000, and joined New York University as an Assistant Professor in 2001. Dr. Dodis’ research is primarily in cryptography and network security. In particular, he worked in a variety of areas including exposure-resilient cryptography, cryptography and imperfect randomness, cryptography with biometrics and other noisy data, authenticated encryption, hash functions and information-theoretic cryptography. Dr. Dodis has more than 70 scientific publications at various conferences, journals and other venues, has been on program committees of many international conferences (including FOCS, STOC, CRYPTO and Eurocrypt), and gave numerous invited lectures and courses at various venues. Dr. Dodis is the recipient of National Science Foundation CAREER Award, IBM Faculty Award and Best Paper Award at 2005 Public Key Cryptography Conference. As an undergraduate student, he was also a winner of the US-Canada Putnam Mathematical Competition.

Finding Incentives to Secure Internet Routing Sharon Goldberg (Boston University) 6/22 1:30 pm

ABSTRACT: Despite a decade of research, the problem of securing the global Internet’s routing system is far from solved. Indeed, a key hurdle for the transition to secure routing is the fact that the Internet consists of thousands of autonomous systems (e.g. backbone providers like AT&T, content providers like Google, business networks like Bank of America), that will make deployment decisions according to their own local business objectives. Worse yet, the security benefits provided by secure routing protocols tend not to kick in until they have been adopted by a large number of autonomous systems. As a result, the conventional wisdom argues that global deployment of routing security protocols is infeasible.

This talk overviews a series of our results that challenge this conventional wisdom. We shall use both theoretical arguments and simulations to show how local incentives can be harnessed to secure the majority of autonomous systems in the Internet. No background will be assumed.

BIO: Sharon Goldberg is an assistant professor of computer science at Boston University. Her research focuses on finding practical solutions to problems in network security, by leveraging formal techniques from cryptography, algorithms, and game theory. She obtained her PhD from Princeton University in July 2009, and her BASc from the University of Toronto in June 2003.

Separating Succinct Non-Interactive Arguments From All Falsifiable Assumptions Daniel Wichs (New York University) 6/2 1:30 pm

ABSTRACT: In this paper, we study succinct computationally sound proofs (arguments) for NP, whose communication complexity is poly-logarithmic the instance and witness sizes. The seminal works of Kilian ’92 and Micali ’94 show that such arguments can be constructed under standard cryptographic hardness assumptions with four rounds of interaction, and that they be made non-interactive in the random-oracle model. The latter construction also gives us some evidence that succinct non interactive arguments (SNARGs) may exist in the standard model with a common reference string (CRS), by replacing the oracle with a sufficiently complicated hash function whose description goes in the CRS. However, we currently do not know of any construction of SNARGs with a formal proof of security under any simple cryptographic assumption.

In this work, we give a broad black-box separation result, showing that black-box reductions cannot be used to prove the security of any SNARG construction based on any falsifiable cryptographic assumption. This includes essentially all common assumptions used in cryptography (one-way functions, trapdoor permutations, DDH, RSA, LWE etc.). More generally, we say that an assumption is falsifiable if it can be modeled as an interactive game between an adversary and an efficient challenger that can efficiently decide if the adversary won the game. This is similar, in spirit, to the notion of falsifiability of Naor ’03, and captures the fact that we can efficiently check if an adversarial strategy breaks the assumption.Our separation result also extends to designated verifier SNARGs, where the verifier needs a trapdoor associated with the CRS to verify arguments, and slightly succinct SNARGs, whose size is only required to be sub-linear in the statement and witness size.

Joint work with Craig Gentry.

BIO: Daniel is a PhD student at NYU under the supervision of Yevgeniy Dodis. His research focuses on various theoretical and practical aspects of cryptography, with a recent focus on building cryptosystems that remain secure even in the presence of side-channel leakage on their secret keys. Daniel will be graduating this June and joining IBM research as a Josef Raviv Memorial postdoctoral fellow.

Efficient Fully Homomorphic Encryption from (Standard) LWE Zvika Brakerski (Weizmann) 5/13 12:15 pm

ABSTRACT: In fully homomorphic encryption, it is possible to transform an encryption of a message, m, into an encryption of any (efficient) function of that message, f(m), without knowing the secret key. This property makes it into a very useful cryptographic building block.

We present a fully homomorphic encryption scheme that is based solely on the (standard) learning with errors (LWE) assumption. Applying known results on LWE, the security of our scheme is based on the worst-case hardness of short vector problems on arbitrary lattices. As icing on the cake, our scheme is quite efficient, and has very short ciphertexts.Our construction improves upon previous works in two aspects:

1. We show that “somewhat homomorphic” encryption can be based on LWE, using a new re-linearization technique. In contrast, all previous schemes relied on complexity assumptions related to ideals in various rings.
2. More importantly, we deviate from the “squashing paradigm” used in all previous works. We introduce a new dimension reduction technique, which shortens the ciphertexts and reduces the decryption complexity of our scheme, without introducing additional assumptions. In contrast, all previous works required an additional, very strong assumption (namely, the sparse subset sum assumption).

Since our scheme has very short ciphertexts, we use it to construct an asymptotically-efficient LWE-based single-server private information retrieval (PIR) protocol. The communication complexity of our protocol (in the public-key model) is k ⋅ polylog, k+log |DB| bits per single-bit query, which is better than any known scheme. Previously, it was not known how to achieve a communication complexity of even poly(k, log|DB|) based on LWE.Joint work with Vinod Vaikuntanathan.

BIO: Zvika Brakerski is a PhD student at the Weizmann Institute of Science, Israel, where he is supervised by Prof. Shafi Goldwasser. He is a visiting student at MIT this Spring.

Lightweight Cryptographic Algorithms Andrey Bogdanov (K.U. Leuven) 5/6 1:30 pm

ABSTRACT: As crucial applications go pervasive, the need for security in RFID and sensor networks is dramatically increasing, which requires secure yet efficiently implementable cryptographic primitives including secret-key ciphers and hash functions. In such constrained environments, the area and power consumption of a primitive usually comes to the fore and standard algorithms are often prohibitively expensive to implement. Once this research problem was identified, the cryptographic community was quick to design a number of tailored lightweight cryptographic algorithms to specifically address this challenge: stream ciphers like Trivium and Grain, block ciphers like DESL, DESXL, KATAN/KTANTAN, PrintCipher and PRESENT, as well as hash functions like Quark and Spongent. In this talk, I will revisit the technical framework behind the lightweight cryptographic algorithms and discuss the specific challenges arising in the design and cryptanalysis of such primitives.

BIO: Andrey Bogdanov is a postdoctoral researcher at K.U.Leuven in Belgium and a Visiting Researcher with Microsoft Research. He received his PhD in Computer Science and Electrical Engineering from the Ruhr University of Bochum in Germany under the supervision of Christof Paar. Andrey’s primary research area is the design and cryptanalysis of symmetric-key cryptographic algorithms. He is also interested in provable aspects of symmetric-key ciphers, side-channel cryptanalysis as well as efficient implementations of secret- and public-key cryptography. Andrey has co-designed several ciphers including the award-winning lightweight block cipher PRESENT which is filed to be become an ISO standard. He proposed the first attack on the KeeLoq automotive authentication system – a major and widely used solution for keyless entry. He holds an IACR best paper award for his work on efficient implementations of post-quantum signature schemes. Andrey is leading the Cryptographic Algorithms work group within the Belgian Fundamental Research Network on Cryptology and Information Security (BCRYPT).

Efficient Non-Interactive Secure Computation Manoj Prabhakaran (UIUC) 4/29 1:30 pm

ABSTRACT: Suppose that a receiver R wishes to publish an encryption of her secret input x so that every sender S, holding an input y, can reveal f(x,y) to R by sending her a single message. This should be done while simultaneously protecting the secrecy of y against a corrupted R and preventing a corrupted S from having an unfair influence on the output of R beyond what is allowed by f .

When the parties are semi-honest, practical solutions can be based on Yao’s garbled circuit technique. However, for the general problem when the parties, or even S alone, may be malicious, all known polynomial-time solutions are highly inefficient. This is due in part to the fact that known solutions make a non-black-box use of cryptographic primitives, e.g., for providing non-interactive zero- knowledge proofs of statements involving cryptographic computations on secrets.Motivated by the above question, we consider the problem of secure two-party computation in a model that allows only parallel calls to an ideal oblivious transfer (OT) oracle with no additional interaction. We obtain the following results.

• Feasibility: We present the first general protocols in this model which only make a black-box use of a pseudorandom generator (PRG). All previous OT-based protocols either make a non-black-box use of cryptographic primitives or require multiple rounds of interaction.
• Efficiency: We also consider the question of minimizing the asymptotic number of PRG calls made by such protocols. We show that polylog(k) calls are sufficient for each gate in a (large) boolean circuit computing f, where k is a statistical security parameter guaranteeing at most 2^{-k} simulation error of a malicious sender. Furthermore, the number of PRG calls per gate can be made constant by settling for a relaxed notion of security which allows a malicious S to arbitrarily correlate the event that R detects cheating with the input of R. This improves over the state of the art also for interactive constant-round black-box protocols, which required Omesdfsdfk) PRG calls per gate, even with similar relaxations of the notion of security.

Combining the above results with 2-message (parallel) OT protocols in the CRS model, we get the first solutions to the initial motivating question which only make a black-box use of standard cryptographic primitives.Joint work with Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai.

BIO: Manoj Prabhakaran is an assistant professor in the Computer Science department at the University of Illinois, Urbana-Champaign. He obtained a Ph.D. in computer science from Princeton University in 2005, and a B.Tech. in computer science and engineering from the Indian Institute of Technology, Bombay in 2000. His primary research interests are in theoretical cryptography.

Concurrent Security Huijia (Rachel) Lin (Cornell) 4/28 1:30 pm

ABSTRACT: Cryptographic protocols have been developed for a variety of tasks, including electronic auctions, electronic voting systems, privacy preserving data mining and more. The Internet allows for the concurrent execution of cryptographic protocols. Such concurrency severely challenges their security.

In this talk we introduce a novel technique for transforming any “stand-alone” secure protocol (i.e., one whose security is only guaranteed if executed in isolation) into one that is secure under concurrent executions. Contrary to previous results in the literature, this result is established without relying on additional trusted infrastructure or cryptographic hardness assumptions.

BIO: Huijia Lin is a Ph.D. candidate in the Department of Computer Science at Cornell. Her research interests are in the field of Cryptography. She is a recipient of the Microsoft Graduate Student Fellowship.

Toward (More) Efficient Secure Two-Party Computation Jonathan Katz (University of Maryland) 3/24 1:30 pm

ABSTRACT: I will survey several recent efforts aimed at bringing secure two-party computation (at least in the semi-honest setting) closer to practice. The main focus of the talk will be on private function evaluation (PFE), where one party holds an input $x$ and the other holds a function $f$; the goal is to compute $f(x)$ while revealing nothing more to either party. I show the first constant-round protocol for PFE with complexity *linear* in the size of the circuit computing the function; in particular, the protocol avoids universal circuits.

As time permits, I will also discuss the possibility of secure computation with (amortized) poly-logarithmic complexity, and some recent implementation results showing that generic protocols based on Yao’s garbled-circuit approach can be more efficient than ‘optimized’ protocols based on homomorphic encryption.

BIO: Jonathan Katz is an associate professor in the Department of Computer Science at the University of Maryland. He is a co-author of the widely used textbook “Introduction to Modern Cryptography”.

Revocation for Delegatable Anonymous Credentials Lan Nguyen (MSR Redmond) 3/17 1:30 pm

ABSTRACT: This paper introduces and formalizes homomorphic proofs that allow “adding” proofs and proof statements to get a new proof of the “sum” statement. Additionally, we introduce a construction of homomorphic proofs, and show an accumulator scheme with delegatable non-membership proofs (ADNMP) as one of its applications with provable security. Finally, the proposed accumulator method extends the BCCKLS scheme [C:BCCKLS09] to create a new provably secure revocable delegatable anonymous credential (RDAC) system. Intuitively, the new accumulator’s delegatable non-membership (NM) proofs enable user A, without revealing her identity, to delegate to user B the ability to prove that A’s identity is not included in a blacklist that can later be updated. The delegation is redelegatable, unlinkable, and verifiable.

BIO: Lan Nguyen is a Software Engineer in the XCG Security and Cryptography Group, Microsoft. He has a Bachelor of Computer Science from the University of New South Wales and a Ph.D. in Information Security from the University of Wollongong and did a Post-Doc at CSIRO, all in Australia. His research is mainly on Cryptographic Privacy Enhancing Technologies, such as Anonymous Credentials and Revocation, Group/Ring Signatures and Mix-nets. In industry, he has been working on different areas such as Distributed Key Management, TPM, Software Licensing and Protection, Security Testing, Hard Disk Encryption and Strong Authentication.

Verifiable Delegation of Computation over Large Datasets Yevgeniy Vahlis (Columbia University) 3/14 12 pm

ABSTRACT: We study the problem of computing on large datasets that are stored on an untrusted server. We follow the approach of amortized verifiable computation introduced by Gennaro, Gentry, and Parno in CRYPTO 2010. We present the first practical verifiable computation scheme for high degree polynomial functions. Such functions can be used, for example, to make predictions based on polynomials fitted to a large number of sample points in an experiment. In addition to the many non-cryptographic applications of delegating high degree polynomials, we use our verifiable computation scheme to obtain new solutions for verifiable keyword search, and proofs of retrievability. Our constructions are based on the DDH assumption and its variants, and achieve adaptive security, which was left as an open problem by Gennaro et al. (albeit for general functionalities).Our second result is a primitive which we call a verifiable database (VDB). Here, a weak client outsources a large table to an untrusted server, and makes retrieval and update queries. For each query, the server provides a response and a proof that the response was computed correctly. The goal is to minimize the resources required by the client. This is made particularly challenging if the number of update queries is unbounded. We present a VDB scheme based on the hardness of the subgroup membership problem in composite order bilinear groups.

BIO: Yevgeniy Vahlis is a postdoctoral research scientist at Columbia University, where he works under the direction of Professor Tal Malkin. Yevgeniy completed his Ph.D. at the University of Toronto in 2010 under the supervision of Professor Charles Rackoff. 

Decentralizing Attribute-Based Encryption Allison Lewko (UT Austin) 3/11 12:15 pm

ABSTRACT: We present a Multi-Authority Attribute-Based Encryption (ABE) system. In our system, any party can become an authority and there is no requirement for any global coordination other than the creation of an initial set of common reference parameters. A party can simply act as an ABE authority by creating a public key and issuing private keys to different users that reflect their attributes. A user can encrypt data in terms of any boolean formula over attributes issued from any chosen set of authorities. Finally, our system does not require any central authority.In this talk, I will present our system and discuss its proof, which employs dual system encryption techniques. Our system uses bilinear groups of composite order, and we prove security under static assumptions in the random oracle model.This is joint work with Brent Waters.

BIO: Allison Bishop is currently a PhD student at the University of Texas at Austin, advised by Brent Waters.

Non-Interactive Verifiable Computing Bryan Parno (MSR Redmond) 3/3 1:30 pm

ABSTRACT: We introduce and formalize the notion of Verifiable Computation, which enables a computationally weak client to “outsource” the computation of a function F on various dynamically-chosen inputs to one or more workers. The primary constraint is that the verification of the results should require substantially less effort than computing F from scratch.We present a protocol that allows the worker to return a computationally-sound, non-interactive proof that can be verified in O(m * poly(lambda)) time, where m is the bit-length of the output of F, and lambda is a security parameter. The protocol requires a one-time pre-processing stage by the client which takes O(|C| * poly(lambda)) time, where C is the smallest known Boolean circuit computing F.

Finally, we present new constructions that promise substantially better performance in practice, though current instantiations do not achieve the full set of desirable properties for verifiable computing.

BIO: Bryan Parno is a researcher in Microsoft Research’s Security and Privacy Research Group. He received his PhD and Master’s degrees at Carnegie Mellon University, where he was advised by Adrian Perrig, and a Bachelor’s degree from Harvard University. His current work focuses on the foundations of trust on modern computers. His research interests include computer security, systems, networks, and applied cryptography. In his spare time, he enjoys photography and volunteering as an Emergency Medical Technician.

Overcoming the Hole in the Bucket: Public-key Cryptography Resilient to Continual Memory Leakage Zvika Brakerski (Weizmann Institute and MIT) 2/24 1:30 pm

ABSTRACT: In recent years, there has been a major effort to design cryptographic schemes that remain secure even when arbitrary information about the secret key is leaked (e.g., via side-channel attacks). We explore the possibility of achieving security under continual leakage from the entire secret key by designing schemes in which the secret key is updated over time.In this model, we construct public-key encryption schemes, digital signatures, and identity-based encryption schemes that remain secure even if an attacker can leak a constant fraction of the secret memory (including the secret key) in each time period between key updates. We also consider attackers who may probe the secret memory during the updates themselves.In the talk I will present the model and explain the main ideas in this work. I will also present developments and follow-up works and the remaining open problems in the area.

Joint work with Yael Tauman Kalai, Jonathan Katz and Vinod Vaikuntanathan.

BIO: Zvika Brakerski is a PhD student at the Weizmann Institute of Science, Israel, where he is supervised by Prof. Shafi Goldwasser. He is a visiting student at MIT this Spring.

Position-based Cryptography Nishanth Chandran (UCLA) 2/3 10:30am

ABSTRACT: What constitutes an identity in cryptography? Typical examples include your name and your social-security number, or your fingerprint/iris-scan, or your public-key coming from some trusted public-key infrastructure. However, in many situations, your identity is defined by where you are. For example, we know the role of a bank-teller behind a bank window not because she shows us her credentials but by merely knowing her location. In this work, we initiate the study of cryptographic protocols where the identity (or other credentials and inputs) of a party is derived from its geographic location.

We explore the possibility of “Position Based Cryptography” and construct secure protocols for two fundamental tasks: secure positioning and position based key exchange. Position based cryptography has several fascinating applications — for example, two military bases can securely talk to each other with a guarantee on the physical location of one another.

This talk is based on joint work with Vipul Goyal, Ryan Moriarty, and Rafail Ostrovsky

BIO: Nishanth Chandran is a doctoral candidate at UCLA working with Prof. Rafail Ostrovsky and Prof. Amit Sahai. His research interests are cryptography, security and theory. He has published several papers in leading conferences such as STOC, FOCS, CRYPTO, EUROCRYPT and so on. Nishanth was awarded the Graduate Student Fellowship as well as the Dissertation Year Fellowship from the Graduate Division at UCLA. He received the Chorafas International Award for research in 2010. Nishanth obtained a Bachelors in Computer Science and Engineering from Anna University, India in 2005 and a Masters in Computer Science from UCLA in 2007. He is expected to receive his doctoral degree in June 2011.

Black-box, Round-efficient Secure Computation Hoeteck Wee (Queens College, CUNY) 2/1 1:30pm

ABSTRACT: We present round-efficient protocols for secure multi-party computation with a dishonest majority that rely on *black-box* access to the underlying primitives. Our main contributions are:

• a O(log^* n)-round protocol that relies on black-box access to dense cryptosystems, homomorphic encryption schemes, or lossy encryption schemes. This improves upon the recent O(1)^{log^* n} -round protocol of Lin, Pass and Venkitasubramaniam (STOC 2009) that relies on non-black-box access to a smaller class of primitives.
• a O(1)-round protocol requiring in addition, black-box access to a one-way function with sub-exponential hardness, improving upon the recent work of Pass and Wee (Eurocrypt 2010).

These are the first black-box constructions for secure computation with sublinear round complexity. Our constructions build on and improve upon the work of Lin and Pass (STOC 2009) on non-malleability amplification, as well as that of Ishai et al. (STOC 2006) on black-box secure computation.

(Based on work appearing at FOCS 2010.)

BIO: Hoeteck Wee is an assistant professor at Queens College, CUNY. He received his PhD from UC Berkeley and his BSc from MIT. He was previously a post-doc at Columbia University and a visiting student at Tsinghua University and IPAM. Hoeteck received the NSF career award in 2010. His research revolves around the design and analysis of cryptographic algorithms and protocols.

The SHA-3 competition through the rebound lens Christian Rechberger (K U Leuven, Belgium) 1/27 1:30pm

ABSTRACT: After the MD5 disaster and related breakthroughs in hash cryptanalysis, the cryptographic community as well as practitioners are searching for a next generation hash function standard. This culminated in a large ongoing international effort, the SHA-3 competition, that started in 2008.

In this talk we survey the remaining candidates in this competition and discuss how this competition led to a new way of doing hash cryptanalysis: the rebound attack. Hash functions that allow for simple differential analysis were benefiting from early scrutiny. Recently we started to apply this method also to very different constructions, and still consistently get results that beat the best known attacks. We survey those results and the main ideas behind them, comment on their impact on the SHA-3 competition, and discuss future applications outside of hash cryptanalysis.

BIO: Christian Rechberger is currently a postdoctoral researcher at KU Leuven, Belgium, and visiting researcher at Microsoft Research, Redmond. He obtained his Ph.D. in applied cryptography at Graz University of Technology, Austria, with Vincent Rijmen, the developer of the Advanced Encryption Standard (AES), as advisor. His research interests span various topics in IT-security, cryptography, and algorithms, including design and analysis of cryptographic primitives, RFID security, and efficient implementations.

Rechberger is known for his work on the international standard SHA-1, is co-developer of the rebound attack, and co-designer of the SHA-3 finalist Grostl, received two IACR best paper awards, and is leading the hash function work group within the ECRYPT network of excellence of the European commission.

Password-based Authenticated Key Exchange at the Cost of Diffie-Hellman Vinod Vaikuntanathan 1/20 1:30pm

ABSTRACT: Public-key Cryptography was born in the 1970s with the work of Diffie and Hellman where they defined and realized a foundational primitive called key exchange. In key exchange, two parties – Alice and Bob – who have never met each other before, can exchange messages over a public channel and agree on a shared secret key!

Although the original proposal of Diffie and Hellman is secure only against passive eavesdropping adversaries, much effort has since been devoted  to developing key-exchange protocols resisting active adversaries (this is also called the “authenticated key exchange” problem). Active adversaries can not only listen in on the communication channel, but also interfere with it arbitrarily — modifying, inserting or deleting messages, but also impersonating the communicating entities. To resist such malice, it is necessary for Alice and Bob to share some prior, common setup information.

A variety of setup assumptions have been considered in the literature. In this talk, I will focus on a very realistic and extremely challenging setting – one where Alice and Bob share a low-entropy password (think of an ATM pin, or a computer login password). Such a password has too little entropy to be cryptographically useful, yet we will present protocols that use the shared password to “bootstrap” a cryptographically strong shared key. Furthermore, our protocol will expend essentially the same amount of resources as the original Diffie-Hellman protocol, while also offering protection against active adversaries. Thus, in a sense, we obtain authenticated key exchange “for free” in the challenging password-based setting.

This is joint work with Jonathan Katz (UMD).

BIO: Vinod Vaikuntanathan is a researcher in the XCG group at MSR Redmond since July 2010. In previous avatars, he was a postdoctoral fellow at IBM T.J. Watson (where he held the Josef Raviv postdoctoral fellowship from 2008-2010) and a Ph.D. student at MIT (where he was awarded the George Sprowls award for the best Ph.D. thesis in Computer Science in 2009).

The Cloud was tipsy and ate my files! Giuseppe Ateniese 6/2 1:30pm

ABSTRACT: Our entire digital life will be stored on remote storage servers such as Amazon S3, Microsoft Azure, Google, MobileMe, etc. Our emails, pictures, calendars, documents, music/video playlists, and generic files will be readily available, anytime and anywhere.

In this talk, we will answer the following question: How can we check whether the entire content of our digital life is actually intact and accessible, even though we have no local copy of it?BIO: Giuseppe Ateniese is an Associate Professor of Computer Science at the Johns Hopkins University. He is currently a visiting researcher at Microsoft Research.

Generalized Algorithm for DLP with Auxiliary Inputs Jung Hee Cheon 6/29 2:30pm

ABSTRACT: The DLP with auxiliary inputs is to find $alpha$ when $g^{alpha^i}$ (i=0,1,2,dots,d)$ as well as $g, g^{alpha}$ are given. Recently, numerous cryptosystems are designed on a weaker variant of this problem. One example is the strong Diffie-Hellman problem. It has been shown that the complexity of this problem is lower than the original DLP by upto $sqrt d$ group operations when $p-1$ or $p+1$ has an appropriate divisor. In this talk, we present a generalization of this algorithm, which can be applied even when $p-1$ and $p+1$ are almost prime. We also discuss how many parameters are susceptible to this attack.

BIO: Jung Hee Cheon received the B.S. and Ph.D. degrees in Mathematics from KAIST in 1991, and 1997, respectively. He is a professor of Mathematical Sciences at the Seoul National University (SNU). Before joining to SNU, he was in ETRI, Brown university, and ICU. He is on the editorial board of Journal of KIISC and CSI. He received the best paper award in Asiacrypt 2008. His research interests include computational number theory, cryptography, and information security.

Trustworthy Medical Device Software Kevin Fu 7/20 1:30pm

ABSTRACT: This talk will summarize what is known about the trustworthiness of medical device system software. A version of this talk will be presented at an Institute of Medicine workshop on evaluation of present-day FDA regulatory practices for medical devices.

Today it would be difficult to find a medical device that does not critically rely on computer software in its function, manufacture, or use in clinical decision making. Despite the lessons learned by the radiation accidents of the Therac-25 twenty years ago, medical devices that rely on software (e.g., drug infusion pumps, linear accelerators for radiation) continue to injure or kill patients in preventable ways. Why is it so hard to create trustworthy software for medical devices? First, devices are not isolated devices. They are systems of systems. And software plays a significant role for control of these critical systems that can significantly affect patient safety, either positively or negatively, depending on its trustworthiness. Failure to meaningfully specify requirements, complacency, and lack of care for human factors further erode trustworthiness. The lack of trustworthy medical device software leads to shortfalls in properties such as safety, effectiveness, dependability, reliability, security, and privacy. Good systems engineering and the adoption of modern software engineering techniques can address many of the risks of medical device software—leading to devices that help patients lead more normal, healthy lives.BIO: Kevin Fu is an assistant professor in the Department of Computer Science at the University of Massachusetts Amherst in the beautiful northeastern region of the United States.

Reasons to chat with Kevin: security and privacy, ultra low-power RFID-scale computing, mHealth security and privacy, cardiac arrhythmias, European hearth breads, and/or coffee roasting.

Kevin’s current research interests include trustworthy medical device software and low-power storage for flash memory. He primarily investigates how to ensure the security and privacy of pervasive devices that must withstand determined, malicious parties. Recent projects range from security analysis of embedded devices to compiler techniques for energy-aware programs on RFID-scale computers. The security analysis spans several systems ranging from contactless no-swipe credit cards and implantable cardiac defibrillators to access-controlled Web sites and automated software updates.

Kevin is an Alfred P. Sloan Research Fellow, MIT Technology Review TR35 Innovator of the Year, and recipient of the NSF CAREER award. His research appears in computer science conferences, medical journals, and has been featured in media such as The New York Times, The Wall Street Journal, and various news programs. He served on numerous program committees of leading conferences in secure systems, and has given dozens of invited talks world-wide to industry, government, and academia.Prof. Fu leads the UMass Amherst Security and Privacy Research (SPQR) lab. He serves as director of the RFID Consortium on Security and Privacy (RFID-CUSP.org) and co-director of the Medical Device Security Center (secure-medicine.org). He is also a frequent visiting faculty member at Microsoft Research and the Beth Israel Deaconess Medical Center. Fu received his Ph.D. in Electrical Engineering and Computer Science from MIT. He also holds a certificate of achievement in artisanal bread making from the French Culinary Institute and maintains an active participation in the study of Latin and the Classics. Kevin’s son consumes as much material as he can from CACM. For more information, visit http://www.cs.umass.edu/~kevinfu/

A Framework for the Sound Specification of Cryptographic Tasks Juan Garay 8/11 10:30am

ABSTRACT: Nowadays it is widely accepted to formulate the security of a protocol carrying out a given task via the “trusted-party paradigm,” where the protocol execution is compared with an ideal process where the outputs are computed by a trusted party that sees all the inputs. A protocol is said to securely carry out a given task if running the protocol with a realistic adversary amounts to “emulating” the ideal process with the appropriate trusted party. In the Universal Composability (UC) framework the program run by the trusted party is called an /ideal functionality/. While this simulation-based security formulation provides strong security guarantees, its usefulness is contingent on the properties and correct specification of the ideal functionality, which, as demonstrated in recent years by the coexistence of complex, multiple functionalities for the same task as well as by their “unstable” nature, does not seem to be an easy task.

In this work we address this problem, by introducing a general methodology for the sound specification of ideal functionalities. First, we introduce the class of /canonical/ ideal functionalities for a cryptographic task, which unifies the syntactic specification of a large class of cryptographic tasks under the same basic template functionality. Furthermore, this representation enables the isolation of the individual properties of a cryptographic task as separate members of the corresponding class. By endowing the class of canonical functionalities with an algebraic structure we are able to combine basic functionalities to a single final canonical functionality for a given task. Effectively, this puts forth a bottom-up approach for the specification of ideal functionalities: first one defines a set of basic constituent functionalities for the task at hand, and then combines them into a single ideal functionality taking advantage of the algebraic structure.

We showcase our methodology by applying it to a variety of basic cryptographic tasks, including commitments, digital signatures, zero-knowledge proofs, and oblivious transfer. While in some cases our derived canonical functionalities are equivalent to existing formulations, thus attesting to the validity of our approach, in others they differ, enabling us to “debug” previous definitions and pinpoint their shortcomings.This is joint work with Aggelos Kiayias (Univ. of Athens and Univ. of Connecticut) and Hong-Sheng Zhou (Univ. of Maryland).

BIO: Juan A. Garay received his Ph.D. in Computer Science from Penn State in 1989, and is currently a Lead Member of Technical Staff at AT&T Labs – Research. Before joining AT&T he was a a Member of Technical Staff at Bell Labs, and from 1990 to 1998 a Research Staff Member at the IBM T.J. Watson Research Center. In 1992 he was a postdoctoral fellow at The Weizmann Institute of Science in Israel, and he spent 1996 as a visiting scientist at the Centrum voor Wiskunde en Informatica (CWI) in Amsterdam. His current research interests include theoretical and practical aspects of cryptographic protocols and schemes and privacy-preserving computation. Besides many contributions of a foundational nature, he has been involved in the design, analysis and implementation of a variety of secure systems. He has published extensively in the areas of cryptography, network security, distributed computing, and algorithms; been awarded two dozen patents; and served on the committees of many conferences and international panels.

Solving Revocation with Efficient Updates of Anonymous Credentials Markulf Kohlweiss 9/24 1:30pm

ABSTRACT: Anonymous credential system promise efficient, ubiquitous access to digital services while preserving user privacy. However, their diffusion is impaired by the lack of efficient revocation techniques. Traditional credential revocation measures based on certificate revocation lists or online certification authorities do not provide privacy and cannot be used in privacy-sensitive contexts. Existing revocation techniques specifically geared towards anonymous credential systems are more involved — for the credential issuer, users, as wells as credential consumers — as users have to prove that their credential is still valid, e.g., not included in a revocation list.

We introduce a novel, non-interactive technique to update issuer-controlled attributes of anonymous credentials. Revocation is implemented by encoding the validity time of a credential into one of these attributes. With the proposed protocol, credential issuers can periodically update valid credentials off-line and publish a small per-credential update value on a public bulletin-board. Users can later download their values and re-validate their credentials to prove possession of a valid credential for the current time period. We compare such a solution with revocation mechanisms based on cryptographic accumulators. For certain scenarios our solution outperforms prior solutions for credential revocation in terms of communication and computational costs for the users and credentials consumers while the issuer’s effort is comparable to the best prior proposals.BIO: Markulf is Austrian expat who did his PhD at KU Leuven, Belgium. Starting from October, he will be a Postdoc at MSR, Cambridge, UK.

Since his master thesis, he has been working on protocols related to anonymous credentials. Some protocols he contributed to are: e-cash, anonymous credential revocation, delegatable anonymous credentials, private-information retrieval/oblivious transfer, and private searching.

Markulf’s cryptographic interests lie primarily in zero-knowledge, two-party computation protocols, and definitional issues. One goal is to find and define those cryptographic building blocks that are most valuable for constructing larger privacy enhancing protocols. A good example for such a building block is a signature scheme that allows for an efficient proof of knowledge. Markulf is also happy to talk about about weird properties of the GS proof system, different ways of achieving simulation-sound NIZK proofs, or CCA secure encryption schemes that combine well with GS proofs and two party computation protocols.

Secure and Efficient Evaluation of Multivariate Polynomials and Applications Payman Mohassel 10/28 1:30pm

ABSTRACT: In this talk, I will describe an efficient and secure protocol for secure two-party evaluation of private inputs on a public multivariate polynomial. The focus is on designing a protocol with security against malicious adversaries, with low round and communication complexity.

First, I motivate the problem by showing how a number of interesting protocols can be formulated in this framework. Then, I will go into more detail about the techniques we use for designing our protocol.

BIO: Payman is an assistant professor in the computer science department at University of Calgary Since July 2009. Before that, he recieved his Ph.D. at UC Davis under the supervision of Matthew Franklin.Payman’s research interests are in cryptograhpy, information security and theoretical computer science. Some of his more recent projects include efficient and secure multiparty computation, provably secure encryption and signatures schemes, and privacy in genomic computation

Expressive encryption from hard lattice problems Shweta Agrawal 12/2 10:30am

ABSTRACT: Traditionally, in cryptography, lattices have been used for cryptanalysis, i.e. in breaking cryptosystems. However, since Ajtai’s breakthrough result (in 1996) which established surprising connections between average case and worst case hardness of various lattice problems, there has been great interest in constructing cryptosystems from hard lattice problems.We will describe the first Identity Based Encryption system (in which any arbitrary string, usually name or email address, can be one’s public key) from lattices in the standard model (independently discovered by Cash, Hofheinz, Kiltz, Peikert) . Next, we will present methods to substantially improve the above IBE construction to make it more space and time efficient. We will also present a new method for “lattice basis delegation” which allows the construction of more expressive IBE (hierarchical IBE), and compare this new technique with the earlier basis delegation mechanism of CHKP.

To conclude, we will discuss future directions in building even more expressive encryption systems from lattices.The material discussed is from joint work with Dan Boneh and Xavier Boyen.

BIO: Shweta Agrawal is a graduate student at UT Austin. Her research interests lie in Cryptography and Information Theory. Her recent work in cryptography includes constructions of secure encryption systems from hard lattice problems.

Leakage-Resilient Cryptography: Modeling and Combating Side-Channel Attacks Gil Segev 12/13 3:30pm

ABSTRACT: Most of the work in the analysis of cryptographic schemes has traditionally focused on abstract adversarial models that do not capture “side-channel attacks”. Such attacks exploit various forms of unintended leakage of sensitive information, which is inherent to almost all physical implementations. Inspired by extremely devastating real-life attacks, in this talk I will describe a recent approach for modeling and combating side-channel attacks. I will focus on a framework for modeling a wide range of attacks that rely on partial leakage of secret keys. In particular, I will present a simple and efficient construction of a public-key encryption scheme that is resilient to leakage of almost its whole secret key, as well as a generic method for constructing leakage-resilient encryption schemes that can be based on a variety of number-theoretic assumptions.In addition, if time permits I will describe a recent line of research on the design of data structures that enjoy constant-time operations in the worst case, as an approach for combating timing attacks.

BIO: Gil Segev is currently a postdoctoral researcher at Microsoft Research Silicon Valley. He joined Microsoft in the summer of 2010 after receiving a Ph.D. from the Weizmann Institute of Science, where he was advised by Prof. Moni Naor. Gil’s research focuses on the foundations of computer science with a significant emphasize on cryptography. Motivated by cryptographic applications, Gil is constantly exploring a variety of research areas other than cryptography, including data structures and hashing schemes, computations over massive data sets, and their interface with security and privacy.

Opens in a new tab