The MSR Redmond Cryptography Group invites
researchers to visit the group and speak in our colloquium series. See here for a listing of past colloquia.
Unless otherwise listed, the
colloquia are open to the public. For directions or other questions contact: melissac [AT] <companyname> [DOT] com





Abstracts:
From Circuits to RAM Programs in Malicious 2party Computation
Mike Rosulek (Oregon State University)
8/27 3:30pm
ABSTRACT:
Secure 2party 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 randomaccess machine (RAM) model has recently been investigated as a promising alternative to circuits.
In this talk, I will discuss some pitfalls of basing malicioussecure 2PC on the RAM model rather than circuits. I will then describe two new protocols for malicioussecure 2PC of RAM programs, whose performance relative to the semihonest model matches the state of the art for circuitbased 2PC techniques. For malicious security with statistical security parameter $2^{s}$, our protocol without preprocessing has overhead $s$ compared to the semihonest 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.
KeyVersatile Signatures and Applications
Sarah Meiklejohn (UCSD)
7/23 3:30pm
ABSTRACT:
This talk will discuss keyversatile signatures. Keyversatile 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 relatedkey attack (RKA), and security for keydependent 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 RKAsecure signatures from any RKAsecure oneway function, yielding new RKAsecure signature schemes; and (3) add integrity to encryption while maintaining KDMsecurity.
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 coadvised 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 realworld security. In this talk, I'll discuss a series of results aimed at reducing this gap.
I'll begin by giving an introduction for noncryptographers 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 literaturelongterm key reuse and renegotiationand connect these properties with realworld 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 (RuhrUniversitat 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 numbertheoretic 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 curveand latticebased cryptography, and will particularly focus on my work with various coauthors on putting these numbertheoretic primitives into practice.
BIO:
Craig Costello is a postdoctoral researcher at Microsoft Research who is known for his contributions to elliptic and hyperelliptic curve cryptography, and pairingbased 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 AustralianAmerican 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 i73770M (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 GLVstyle 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 curvebased 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 honestbutcurious 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 UrbanaChampaign. 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 polynomialsize 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, publickey encryption, and noninteractive 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 LowGenus 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 RiemannRoch spaces... On the other hand, algorithms for the mappings between these objects remain relatively underdeveloped. From a categorytheoretic 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 lowgenus 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 curvebased 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 highend 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, ellipticcurve cryptography, and cryptographic pairings. He has also published articles on fast cryptanalysis, in particular attacks on the discretelogarithm 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:
Peertopeer (P2P) systems, and clientserver 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 highchurn 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 nontrivial 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 onetwo 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 ecash) 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, peertopeer 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 ndimensional vectors that respects addition and changes convolution multiplication into coordinatewise 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 partialFFT 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 cofounder of NTRU Cryptosystems (now merged with Security Innovation).
MultiParty 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 MultiParty Computation (MPC) protocols.
BIO:
Nigel Smart is a Professor of Cryptology at the University of Bristol. Before that he worked for HewlettPackard 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 multiparty computation. His work is unified by the goal of turning cryptographic theory into practice.
Latticebased cryptography: What they don't want you to know
Steven Galbraith (University of Auckland)
5/7 1:30pm
ABSTRACT:
Latticebased cryptography is currently the hottest research area in theoretical cryptography. There have been a number of amazing results (homomorphic encryption, attributebased 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 wellknown 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 Informationset Decoding in Cryptanalysis
Christiane Peters (Technical University of Denmark)
3/14 1:30pm
ABSTRACT:
The security of codebased 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 NPhard 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 informationset decoding and the implications for codebased 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 errorcorrecting codes in cryptography as well as numbertheoretic 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, epassports, 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 WG8 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 19951998, 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 coauthored more than 240 technical papers and two books, one coauthored 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 cochairs 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 SQLaware 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 TPCC 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 sharedrandomness model. We show that for every given noise rate c < 1, there exists a scheme that correctly decodes and authenticates a (1c)fraction of the stream sent so far, with high probability. We also show that no constantrate authentication scheme recovers more than a (1c)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 SSHspecific 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 DenialofService (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 postdoctoral 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 torusbased cryptosystems. Currently his research is focused on the provable security of modesofoperation 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 signaturebased 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 realworld 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 tradeoffs with the adoption of endtoend 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 gamebased privacy definition and show that this gamebased 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 sytem.
 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, Véronique 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 multithousand voters, endtoend 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 modelchecking 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, wellmeaning 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 coauthored 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 coauthored 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), cochaired the ACM study of statewide databases of registered voters, and coauthored the League of Women Voters report on election auditing. Simons is retired from IBM Research.
On the Security of OneWitness 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 randomoracle 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 SideChannel Attacks using pseudoBoolean Solvers
Yossef Oren (TelAviv University)
8/7 1:30pm
ABSTRACT:
Machine solvers are a class of generalpurpose 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 sidechannel data (information leaked from the cryptographic device due to its internal structure) is introduced into the equation.
This talk will introduce sidechannel 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 sidechannel data and computation time.
Joint work with Mathieu Renauld, FrançoisXavier Standaert and Avishai Wool
BIO:
Yossi Oren is a Ph.D. student at the Computer Network and Security Lab at TelAviv University. His research interests are:
• Secure Hardware: Power analysis and other hardware attacks and countermeasures on cryptographic devices; Lowresource 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 rateunlimited encryption oracle. The TARDIS (Time and Remanence Decay in SRAM) helps to locally maintain a sense of time elapsed without power and without specialpurpose hardware. The TARDIS software computes the expiration state of a timer by analyzing the decay of existing onchip SRAM memory. The TARDIS enables coarsegrained, hourglasslike 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 privacypreserving RFID tags, to deter double swiping of contactless credit cards, and to increase the difficulty of brute force attacks against ePassports. 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 lowpower embedded devices. In addition to systems security, RFIDscale computation, and energyaware 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.
PracticeDriven 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 wellunderstood and attacks arise because standardizers misunderstand cryptographic theory. I'll use some of my recent work which uses provablesecurity 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 practicallyuseful cryptography requires pushing models and proof techniques in neverbeforeconsidered directions. We'll see how (what I'll call) practicedriven 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 KlagesMundt, 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 padic Lfunctions
Benjamin Lundell (University of Washington)
7/24 4:00pm
ABSTRACT:
We will discuss a new approach to proving the FerreroGreenberg formula for the derivative of a KubotaLeoplodt $p$adic $L$function at $s=0$. The aim is to provide a proof which uses twovariable $p$adic $L$functions in a manner analogous to the GreenbergStevens proof of the MazurTateTeitelbaum conjecture for elliptic curves. In the KubotaLeopldt setting, we use the Katz twovariable $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 UrbanaChampaign.
Summer Number Theory Talk 5: Pairingbased 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 rth 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 ArtinSchreier 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 ArtinSchreier 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 Lfunctions. 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 researchlevel graduate courses in number theory, algebra, and other subjects.
Summer Number Theory Talk 2: The Robbins phenomenon: unexpected numerical stability in padic 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 realnumber arithmetic using floatingpoint approximations. The situation is similar for padic numbers; we begin by introducing the analogue of floatingpoint arithmetic for padics. We then describe some known and conjectural examples of padic 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 padic cohomology, padic 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 researchlevel courses in algebra and number theory.
Dr. Kedlaya's research is in the area of number theory and arithmetic algebraic geometry. His specialties include padic analytic methods, padic 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 SwinnertonDyer 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 SwinnertonDyer 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 DifferentiallyPrivate Graph Synthesis
Sharon Goldberg (Boston University)
7/19 1:30pm
ABSTRACT:
We present a new workflow for differentiallyprivate 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 PublicKey Model
Ivan Visconti (University of Salerno)
6/14 1:30 pm
ABSTRACT:
This talk will first revisit previous work in the Bare PublicKey (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 roundoptimal 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 PostDoctoral 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 NPstatements that are quick to construct and verify. QSPs seem wellsuited 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 CircuitSAT 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 quasilinear, but with prover computation still quadratic.
Using QSPs we construct a NIZK argument in the CRS model for CircuitSAT consisting of just 7 group elements. The CRS size is linear in the circuit size, and prover computation is quasilinear,
making our scheme seemingly quite practical. (The prover only needs to do a linear number of group operations; the quasilinear 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 MultiParty 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 standalone 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 blackbox simulation: There does not exist any o(\frac{n}{\log{n}}) round protocol that adaptively securely realizes a (natural) nparty functionality with a blackbox simulator. Note that most previously known protocols in the adaptive security setting relied on blackbox simulators.
 A constant round protocol using nonblackbox simulation: We construct a constant round adaptively secure multiparty computation protocol in a setting without honest majority that makes crucial use of nonblack 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, INDCCA 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 endtoend response times of a singleserver latticebased scheme and two multiserver informationtheoretic 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 multiserver PIR schemes and singleserver 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, locationbased 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 StrategyProof Voting
Eleanor Birrell (Cornell University)
3/1 2:00 pm
ABSTRACT:
The classic GibbardSatterthwaite Theorem establishes that only dictatorial voting rules are strategyproof; 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 strategyproof. We show that any deterministic voting rule can be approximated by an approximately strategyproof 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 privacypreserving 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) worstcase access overhead for simulating users' requests to outsourced data of size n, using a scheme that is dataoblivious 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 pseudorandom 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 deamortize oblivious storage simulations so that each request takes a worstcase 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 cloudbased 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 LanguageBased System for Efficient ZeroKnowledge 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 noninteractive zeroknowledge 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 zeroknowledge 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 ecash 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 thirdyear 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 realworld 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 SingleChoice CutAndChoose 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 MultiSender KOutofN 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 blackbox Verifiable OT. In addition, the GOT protocols can be used
to execute Priced Oblivious Transfer.
Privacy Amplification and NonMalleable 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 nonmalleable extractor. A nonmalleable 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 nonmalleable 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 widelybelieved conjecture
about the distribution of prime numbers in arithmetic progressions.
Using our nonmalleable extractor, we obtain protocols for "privacy amplification": key agreement between two
parties who share a weaklyrandom 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 wellknown 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 112bit 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 112bit 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 publickey 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 coeditor of a recently published twovolume "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 twoparty 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 privacypreserving 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 lessthanideal 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 tamperresilient 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 postdoctoral 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 endtoend 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. Voterverification 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 receiptfreeness 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 endtoend verifiable
protocols for secure electronic voting, particularly those suitable for the obscure and complicated voting system
used in Aus. She is cochair 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 Pythonbased 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 reusable 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 privacypreserving protocols. He is also a cofounder 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 cryptographicallyenabled 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 AttributeBased 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 20042005, he was a postdoctoral 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 IdentityBased 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 IdentityBased 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 MinEntropy to Help with Key Agreement and Leakage Resilience
Leo Reyzin (Boston University)
7/14 1:30 pm
ABSTRACT:
There are many different notions of informationtheoretic entropy and its computational analogues. The right notion and a toolbox of lemmas can make for beautifully simple proofs. Drawing on examples from informationtheoretic key agreement and leakageresilient cryptography (no background in either is assumed), I will show how various extensions of minentropy can help analyze cryptographic constructions. I will also present some (not always wellformed) 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 twoparty computation that allows a client and a server to evaluate an arbitrary function f with an amortized polylogarithmic 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 twoparty 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, locationbased 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 MultiParty Computation
Seny Kamara (MSR Redmond)
7/7 1:30 pm
ABSTRACT:
We initiate the study of secure multiparty computation (MPC) in a serveraided 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 serveraided setting, that generalize the standard simulationbased definitions for MPC, and allow us to formally capture the existence of dishonest but noncolluding participants. This requires us to introduce a formal characterization of noncolluding adversaries that may be of independent interest.
We then design generalpurpose serveraided multiparty 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 serveraided twoparty protocol. Our transformation formalizes the intuitive connection between the problems of serveraided computation and verifiable computation by interpreting the former as a means for verifiably and privately outsourcing a secure multiparty 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 approximateGCD 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 GentryHalevi 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 JeanSebastien 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, LHLbased extractors suffer from the following two drawbacks: (1) Large Entropy Loss: to extract v bits from distribution X of minentropy m which are eclose to uniform, one must set v<= m  2*log(1/e), meaning that the entropy loss L = mv>= 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/CCAsecure 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 minentropy we have!) Second, we study the soundness of the natural *expandthenextract* 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, expandthenextract approach is not sound if the Decisional DiffieHellman 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 samplethenextract 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 postdoc 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 exposureresilient cryptography, cryptography and imperfect randomness, cryptography with biometrics and other noisy data, authenticated encryption, hash functions and informationtheoretic 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 USCanada 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 NonInteractive 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 polylogarithmic 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 noninteractive in the randomoracle 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 blackbox separation result, showing that blackbox 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 (oneway 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 sublinear 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 sidechannel 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 worstcase 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:
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 secretkey 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 symmetrickey cryptographic algorithms. He is also interested in provable aspects of symmetrickey ciphers, sidechannel cryptanalysis as well as efficient implementations of secret and publickey cryptography. Andrey has codesigned several ciphers including the awardwinning 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 postquantum signature schemes. Andrey is leading the Cryptographic Algorithms work group within the Belgian Fundamental Research Network on Cryptology and Information Security (BCRYPT).
Efficient NonInteractive 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 semihonest, 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 polynomialtime solutions are highly inefficient. This is due in part to the fact that known solutions make a nonblackbox use of cryptographic primitives, e.g., for providing noninteractive zero knowledge proofs of statements involving cryptographic computations on secrets.
Motivated by the above question, we consider the problem of secure twoparty 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.
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
"standalone" 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
TwoParty Computation
Jonathan
Katz (University of Maryland)
3/24 1:30 pm
ABSTRACT:
I will survey several recent efforts aimed at bringing secure twoparty
computation (at least in the semihonest 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 constantround 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) polylogarithmic complexity, and some recent implementation results
showing that generic protocols based on Yao's garbledcircuit 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 coauthor 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
nonmembership 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 nonmembership (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 PostDoc at CSIRO, all in Australia. His research is
mainly on Cryptographic Privacy Enhancing Technologies, such as Anonymous
Credentials and Revocation, Group/Ring Signatures and Mixnets. 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 noncryptographic 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
AttributeBased Encryption
Allison
Lewko (UT Austin)
3/11 12:15 pm
ABSTRACT:
We present a MultiAuthority AttributeBased 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.
NonInteractive
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 dynamicallychosen 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 computationallysound,
noninteractive proof that can be verified in O(m * poly(lambda))
time, where m is the bitlength of the output of F, and lambda is a security
parameter. The protocol requires a onetime preprocessing 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: Publickey 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 sidechannel 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 publickey encryption schemes, digital signatures,
and identitybased 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 followup 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.
Positionbased Cryptography
Nishanth Chandran (UCLA)
2/3
10:30am
ABSTRACT:
What constitutes an identity in cryptography?
Typical examples include your name and your socialsecurity number, or
your fingerprint/irisscan, or your publickey coming from some trusted
publickey infrastructure. However, in many situations, your identity is
defined by where you are. For example, we know the role of a bankteller
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.
Blackbox, Roundefficient Secure Computation
Hoeteck Wee (Queens College, CUNY)
2/1
1:30pm
ABSTRACT:
We present
roundefficient protocols for secure multiparty computation with a dishonest
majority that rely on *blackbox* access to the underlying primitives. Our main
contributions are:
 a
O(log^* n)round protocol that relies on blackbox 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 nonblackbox access to a smaller class of
primitives.
 a O(1)round
protocol requiring in addition, blackbox access to a oneway function with
subexponential hardness, improving upon the recent work of Pass and Wee (Eurocrypt 2010).
These are the first
blackbox constructions for secure computation with sublinear
round complexity. Our constructions build on and improve upon the work of Lin
and Pass (STOC 2009) on nonmalleability amplification, as well as that of Ishai et al. (STOC 2006) on blackbox 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 postdoc 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 SHA3 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 SHA3 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 SHA3 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 ITsecurity,
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 SHA1, is codeveloper of the
rebound attack, and codesigner of the SHA3 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.
Passwordbased Authenticated Key Exchange at the Cost of DiffieHellman
Vinod Vaikuntanathan
1/20
1:30pm
ABSTRACT:
Publickey 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 keyexchange 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
lowentropy 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 DiffieHellman
protocol, while also offering protection against active adversaries. Thus, in a
sense, we obtain authenticated key exchange “for free” in the challenging
passwordbased 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 20082010) 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 DiffieHellman
problem. It has been shown that the complexity of this problem is lower than
the original DLP by upto $\sqrt
d$ group operations when $p1$ or $p+1$ has an appropriate divisor. In this
talk, we present a generalization of this algorithm, which can be applied even
when $p1$ 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 presentday 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
Therac25 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 softwareleading 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 lowpower
RFIDscale 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 lowpower 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 energyaware programs on RFIDscale computers. The
security analysis spans several systems ranging from contactless noswipe
credit cards and implantable cardiac defibrillators to accesscontrolled 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 worldwide
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
(RFIDCUSP.org) and codirector of the Medical Device Security Center
(securemedicine.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 "trustedparty 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 simulationbased 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 bottomup 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, zeroknowledge 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 HongSheng 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 privacypreserving 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 privacysensitive
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, noninteractive technique to update issuercontrolled
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 offline
and publish a small percredential update value on a public bulletinboard.
Users can later download their values and revalidate 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:
ecash, anonymous credential revocation, delegatable
anonymous credentials, privateinformation retrieval/oblivious transfer, and
private searching.
Markulf's cryptographic interests lie primarily in
zeroknowledge, twoparty 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
simulationsound 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
twoparty 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.
LeakageResilient
Cryptography: Modeling and Combating SideChannel 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 "sidechannel
attacks". Such attacks exploit various forms of unintended leakage of
sensitive information, which is inherent to almost all physical
implementations. Inspired by extremely devastating reallife attacks, in this
talk I will describe a recent approach for modeling and combating sidechannel
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 publickey encryption scheme that is resilient
to leakage of almost its whole secret key, as well as a generic method for
constructing leakageresilient encryption schemes that can be based on a
variety of numbertheoretic assumptions.
In addition, if time permits I will describe a recent line of research on the
design of data structures that enjoy constanttime 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.