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] <company-name> [DOT] com
|
|
|
|
Abstracts:
Lattice-based cryptography: What they don't want you to know
Steven Galbraith (University of Auckland)
5/7 1:30pm
ABSTRACT:
Lattice-based cryptography is currently the hottest research area in theoretical cryptography. There have been a number of amazing results (homomorphic encryption, attribute-based encryption for general circuits, multilinear maps) that were not previously possible. Hence, the area is extremely active, with major new papers appearing almost every month. However, a few inconvenient truths have been swept under the carpet along the way. Although known to the experts, some of these issues are possibly not well-known in the wider community.
BIO:
Steven Galbraith is a Professor in the Mathematics Department at the University of Auckland. His main research interests lie in elliptic curve cryptography and on related mathematical topics. He completed his PhD in mathematics at the University of Oxford in 1996 under the supervision of Bryan Birch. He has recently written an advanced graduate textbook titled "Mathematics of Public Key Cryptography", which covers everything from the Pollard algorithms, isogenies and hyperelliptic curves, to algebraic tori and lattices.
Applications of Information-set Decoding in Cryptanalysis
Christiane Peters (Technical University of Denmark)
3/14 1:30pm
ABSTRACT:
The security of code-based cryptography is based on the hardness of the generic decoding problem: given a random linear code find a codeword within fixed Hamming distance from a given vector. The corresponding decision problem is NP-hard and the most efficient algorithms for solving the computational problem all take exponential time. This talk discusses the complexity of the best known algorithms which are based on information-set decoding and the implications for code-based cryptography as well as the Learning Parity with Noise (LPN) problem.
BIO:
Christiane Peters is a postdoctoral researcher at the Technical University of Denmark, and visiting researcher at Microsoft Research, Redmond. She obtained her Ph.D. in applied cryptography at Technische Universiteit Eindhoven, the Netherlands, supervised by Tanja Lange and Daniel J. Bernstein. Her research focuses on error-correcting codes in cryptography as well as number-theoretic and cryptographic applications of elliptic curves.
Securing RFID Systems Using Lightweight Stream Cipher
Guang Gong (University of Waterloo)
2/20 3:00pm
ABSTRACT:
Radio frequency identification (RFID) is a technology for the automated identification of physical entities using radio frequency transmissions. In the past ten years, RFID systems have gained popularity in many applications, such as supply chain management, library systems, e-passports, contactless cards, identification systems, and human implantation. RFID is one of the most promising technologies in the field of ubiquitous and pervasive computing. Many new applications can be created by embedding an object with RFID tags. However, the rapid development of RFID systems raises serious privacy and security concerns that could prevent the benefits of RFID technology from being fully utilized. In this talk, first I will give an overview for the proposed methods in the literature for authentications in RFID systems, then I will present a lightweight WG stream cipher for securing RFID systems, and provide the security analysis and efficient implementation of an instance of WG-8 on microcontroller.
BIO:
Guang Gong received a B.S. degree in Mathematics in 1981, an M.S. degree in Applied Mathematics in 1985, and a Ph.D. degree in Electrical Engineering in 1990, from Universities in China. She received a Postdoctoral Fellowship from the Fondazione Ugo Bordoni, in Rome, Italy, and spent the following year there. After returning from Italy, she was promoted to an Associate Professor at the University of Electrical Science and Technology of China. During 1995-1998, Dr. Gong worked with several internationally recognized, outstanding coding experts and cryptographers, including Dr. Solomon W. Golomb, at the University of Southern California. Dr. Gong joined the University of Waterloo, Canada in 1998, as an Associate Professor in the Dept. of Electrical and Computer Engineering in September 2000. She has been a full Professor since 2004. Dr. Gong's research interests are in the areas of sequence design, cryptography, and communication security. She has authored or co-authored more than 240 technical papers and two books, one co-authored with Dr. Golomb, entitled as Signal Design for Good Correlation for Wireless Communication, Cryptography and Radar, published by Cambridge Press in 2005, and the other coauthored with Dr. Lidong Chen, Communication System Security, published by CRC 2012. Dr. Gong serves/served as Associate Editors for several journals including Associate Editor for Sequences for IEEE Transactions on Information Theory, and served on a number of technical program committees and conferences as co-chairs or committee members. Dr. Gong has received several awards including the Best Paper Award from the Chinese Institute of Electronics in 1984, Outstanding Doctorate Faculty Award of Sichuan Province, China, in 1991, the Premier's Research Excellence Award, Ontario, Canada, in 2001, NSERC Discovery Accelerator Supplement Award, 2009, Canada, and Ontario Research Fund - Research Excellence Award, 2010, Canada, Best Paper Award of IEEE ICC 2012. She currently serves as the Managing Director of the Center of Applied Cryptographic Research (CACR) at University of Waterloo.
CryptDB: Processing Queries on an Encrypted Database
Raluca Ada Popa (MIT)
11/27 1:30pm
ABSTRACT:
Online applications are vulnerable to theft of sensitive information because adversaries can exploit software bugs to gain access to private data, and because curious or malicious administrators may capture and leak data. CryptDB is a system that provides practical confidentiality in the face of these attacks for applications backed by SQL databases. CryptDB's approach is to execute SQL queries over encrypted data. It can do so practically with two techniques: using a collection of efficient SQL-aware encryption schemes, two of which are new, and onions of encryptions which allow dynamic adjustment of encryption schemes. An analysis of a trace of 126 million SQL queries from a production MySQL server shows that CryptDB can support operations over encrypted data for 99.5% of the 128,840 columns seen in the trace. Our evaluation shows that CryptDB has low overhead, reducing throughput by only 26% for queries from the standard SQL benchmark TPC-C when compared to unmodified MySQL.
BIO:
Raluca Ada Popa is a third year Ph.D. student in computer science at MIT, advised by Prof. Nickolai Zeldovich. Her research interests are in building secure systems with solid cryptographic foundations, her work thus spanning from systems security to theoretical cryptography. Raluca received the 2011 Google Ph.D. Fellowship for Secure Cloud Computing and the 2009 CRA Outstanding Undergraduate Award for research.
Optimal Coding for Streaming Authentication
Ran Gelles (UCLA)
9/5 1:30pm
ABSTRACT:
Message authentication is well studied in the literature, and various efficient solutions have been suggested and analyzed. This is however not the case for authentication of data streams in which the message is very long, possibly infinite, and not known in advance to the sender. Trivial solutions for authenticating data streams either suffer from a long delay at the receiver?s end or cannot perform well when the communication channel is noisy.
We suggest an efficient, constant rate, authentication scheme for data streams over a noisy channel in the shared-randomness model. We show that for every given noise rate c < 1, there exists a scheme that correctly decodes and authenticates a (1-c)-fraction of the stream sent so far, with high probability. We also show that no constant-rate authentication scheme recovers more than a (1-c)-fraction of the stream, which implies that our scheme is optimal.
Joint work with Matthew Franklin, Rafail Ostrovsky, and Leonard Schulman.
BIO:
Ran Gelles is a PhD student in the Computer Science Department at UCLA. He works in the Theory and Cryptography lab with Professor Rafail Ostrovsky and Professor Amit Sahai. He received B.Sc. in Computer Engineering in 2003, and M.Sc. in Computer Science in 2009, both from Technion, Israel.
Security of Symmetric Encryption in the Presence of Ciphertext Fragmentation
Martijn Stam (University of Bristol)
8/16 10:00am
ABSTRACT:
In recent years, a number of standardized symmetric encryption schemes have fallen foul of attacks exploiting the fact that in some real world scenarios ciphertexts can be delivered in a fragmented fashion.
We initiate the first general and formal study of the security of symmetric encryption against such attacks. We extend the SSH-specific work of Paterson and Watson (Eurocrypt 2010) to develop security models for the fragmented setting. We also develop security models to formalize the additional desirable properties of ciphertext boundary hiding and robustness against Denial-of-Service (DoS) attacks for schemes in this setting.
We illustrate the utility of each of our models via efficient constructions for schemes using only standard cryptographic components, including constructions that simultaneously achieve confidentiality, ciphertext boundary hiding and DoS robustness.
Joint work with Alexandra Boldyreva, Jean Paul Degabriele, and Kenneth G. Paterson
BIO:
Martijn Stam joined the University of Bristol as a Lecturer in the Computer Science Department in February 2011. Prior to that, he obtained his Master's Degree and PhD in Mathematics from the Technische Universiteit Eindhoven. Over the years, he has been a post-doctoral researcher at the University of Bristol, EPFL (Switzerland), and Royal Holloway, University of London.
His main academic interest is cryptology. Cryptology is an ever expanding field that mostly sits in between mathematics and computer science, with elements from other disciplines as well. Parts of cryptology are firmly grounded as an exact science, while other parts still have a strong engineering aspect to them. His expertise ranges over a relatively wide area of cryptology. During his PhD and early postdoc years, his research was centered around the efficient implementation of subgroup cryptosystems, such as XTR or torus-based cryptosystems. Currently his research is focused on the provable security of modes-of-operation for symmetric cryptography.
Rethinking Verifiably Encrypted Signatures: A Gap in Functionality and Potential Solutions
Sarah Meiklejohn (University of California, San Diego)
8/14 1:30pm
ABSTRACT:
Verifiably encrypted signatures (VES) were originally introduced by Boneh, Gentry, Lynn, and Shacham in 2003. Since then, many new constructions have been provided, as well as new security definitions that seek to refine and strengthen the ones originally proposed. As the name suggests, the desired functionality of a VES scheme intuitively allows a user to encrypt, in a publicly verifiable manner, a signature on a message, coupled with the ability for either that user or some trusted third party (such as an arbiter) to later pull out the underlying signature. Such schemes allow for the fair exchange of digital signatures, in which two untrusted parties interact in the hopes of obtaining each others’ signatures on some message (e.g., a contract), and either both parties get what they want or neither does.
In this paper, we argue that even the refined definitions for VES security do not sufficiently capture this desired functionality. To support this claim, we generically construct a secure VES scheme using only signatures; this immediately suggests that the existing security notions are not capturing the “verifiable encryption” part of VES. To therefore bridge this gap between the desired functionality and the existing definitions, we propose a new definition called resolution independence and show that our signature-based construction cannot satisfy this definition, whereas all existing VES schemes can; resolution independence therefore provides a separation of sorts between our contrived construction and those that do provide the desired functionality. As further support for our new definition, we then show that any secure VES scheme satisfying a slightly stronger notion of resolution independence implies the existence of encryption.
This is joint work with Theresa Calderon, Hovav Shacham, and Brent Waters.
BIO:
Sarah is a PhD candidate in Computer Science at the University of California, San Diego, entering her fourth year and working in the Security and Cryptography Group. Before starting at UCSD, she obtained a Sc.B. in Mathematics and an Sc.M. in Computer Science from Brown University under the guidance of Anna Lysyanskaya. Her research interests focus on the interface between security and cryptography; i.e., trying to improve the way in which cryptographic protocols are incorporated into secure systems, as well as coming up with cryptographic models that accurately reflect real-world attacks. Most recently, Sarah spent the summer of 2011 at MSR Redmond, working in the cryptography group with Melissa Chase.
Security of Symmetric Encryption in the Presence of Ciphertext Fragmentation
Olivier Pereira (Université Catholique de Louvain)
8/13 1:30pm
ABSTRACT:
Vote privacy is a central aspect of most of our elections. It is however not an absolute property: it will depend on the ballot format, tallying rules, voter turnout and preferences. Furthermore, it is achieved using various techniques, creating new trade-offs with the adoption of end-to-end verifiable voting systems for instance.
We describe various contributions to the analysis of the privacy properties that voting systems provide:
- We propose privacy metrics, inspired from classical information theoretic (IT) quantities, and illustrate their use on the public audit data provided for the
2009 Takoma Park election based on Scantegrity.
- We propose computational analogs of our IT metrics, together with a more traditional style cryptographic game-based privacy definition and show that this game-based definition can be conveniently used to bridge the gap between our IT and computational metrics.
- Focusing on a large class of voting protocols where voters interact with the authorities in one single pass, we identify conditions that guarantee that an encryption scheme is appropriate for the submission of ballots and apply these conditions to analyze the security of the Helios voting 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 multi-thousand voters, end-to-end verifiable, legally binding election. This voting system has been used in dozen of elections since then.
The Evolution of Pret a Voter
Peter Ryan (University of Luxembourg)
8/10 1:30pm
ABSTRACT:
The challenge of making elections demonstrably accurate while guaranteeing ballot secrecy with minimal trust assumptions has been taken up by the crypto/security community. One of the approaches is the "Pret a Voter" concept, in which the vote is encoded by randomising the order of candidates. In this talk I will outline the Pret a Voter concept and describe its development over the roughly eight years since its inception. The design has evolved in the face of newly identified threats, advances in cryptographic primitives and demands for greater flexibility and efficiency. I will also outline the Pretty Good Democracy scheme and the incorporation of ideas from PGD in Pret a Voter, giving rise to Pret a Voter with Confirmation Codes.
BIO:
Peter Ryan is Professor of Applied Security at the University of Luxembourg. He has over 20 years of experience in information assurance and formal verification. He pioneered the application of process algebras to modelling and analysis of secure systems and initiated and led the project that pioneered the application of process algebra (CSP) and model-checking to the analysis of security protocols. He has published extensively on cryptography, cryptographic protocols, mathematical models of computer security and, most recently, high assurance voting systems. He is the creator of Prêt à Voter, Pretty Good Democracy (with Vanessa Teague) and OpenVote (with Feng Hoa) verifiable voting schemes. Prior to joining the University of Luxembourg, he was a Professor of Computing Science at Newcastle University. He has worked at GCHQ, the Defence Research Agency, the Stanford Research Institute in Cambridge and the Software Engineering Institute, CMU Pittsburgh. He holds a PhD in mathematical physics from the University of London.
Internet Voting: An Idea Whose Time Has Not Come
Barbara Simons
8/8 1:30pm
ABSTRACT:
Properly designed and engineered computerized voting systems can facilitate voting and increase the security and reliability of our voting systems. Unfortunately, in their eagerness to have the most modern and best election equipment and to take advantage of almost $4 billion in federal funding, well-meaning election officials were quick to accept accuracy and security claims of computerized voting system vendors. Few questions were asked about crucial issues. How secure, accurate, and reliable are these machines? How easy are they to use, especially by people with disabilities? How could an election audit or recount be conducted? There was little or no consultation with independent technical experts on these questions, and remarkably little scientific research. Standards and regulations were inadequate to nonexistent. The implicit assumption appears to have been that no recount would ever be needed, because the new systems were so completely secure and accurate that there would no longer be any reason to challenge an election result.
There is now a widespread perception that Internet voting is the wave of the future and the way to save money while increasing voter participation, especially participation of young people. (I can bank online; why can't I vote online?) Not having learned from previous mistakes and against the advice of essentially all computer security experts, Internet voting is currently being used in several countries and in some U.S. States. There is also strong pressure to adopt Internet voting in the U.S. for members of the military and civilians living abroad. In this talk I examine some of the threats of Internet voting in the hope of encouraging the technical community to oppose Internet voting unless and until these threats can be eliminated.
BIO:
An expert on electronic voting, Dr. Barbara Simons recently published Broken Ballots: Will Your Vote Count?, a book on voting machines co-authored with Douglas Jones. She is on the Board of Advisors of the U.S. Election Assistance Commission, and she was a member of the workshop, convened at the request of President Clinton, that produced a report on Internet Voting in 2001. She also co-authored the report that led to the cancellation of Department of Defense’s Internet voting project (SERVE) because of security concerns. Simons, a former President of the Association for Computing Machinery (ACM), co-chaired the ACM study of statewide databases of registered voters, and co-authored the League of Women Voters report on election auditing. Simons is retired from IBM Research.
On the Security of One-Witness Blind Signature Schemes
Anna Lysyanskaya (Brown University)
8/7 3:30pm
ABSTRACT:
Blind signatures have proved an essential building block for applications that protect privacy while ensuring unforgeability, e.g., electronic cash and electronic voting. One of the oldest, and most efficient blind signature schemes is the one due to Schnorr that is based on his famous identification scheme. Although it was proposed over twenty years ago, its unforgeability remains an open problem, even in the random-oracle model. In this work, we show that current techniques for proving security in the random oracle model do not work for the Schnorr blind signature. Our results generalize to other important blind signatures, such as the one due to Brands. Brands’ blind signature is at the heart of Microsoft’s UProve system, which makes this work relevant to cryptographic practice as well.
Joint work with Foteini Baldimtsi
BIO:
Anna Lysyanskaya is an Associate Professor of Computer Science at Brown University. She received her Ph.D. in Computer Science and Electrical Engineering from MIT and joined the faculty of Brown in 2002. She is a recipient of an NSF CAREER award and a Sloan Foundation fellowship; she is also an MIT Technology Review Magazine's "35 under 35" honoree. Her research interests are in cryptography, theoretical computer science, and computer security. A theme of her research is on balancing anonymity with accountability.
The Mechanical Cryptographer: Tolerant Algebraic Side-Channel Attacks using pseudo-Boolean Solvers
Yossef Oren (Tel-Aviv University)
8/7 1:30pm
ABSTRACT:
Machine solvers are a class of general-purpose software tools which input a set of equations and output a satisfying assignment to these equations (or a proof of unsatisfiability). Solvers are used for a variety of practical applications, from VLSI verification to transportation route planning. Recently several authors have attempted to use solvers to perform one of the most challenging tasks in modern computer science - cryptanalysis of symmetric block ciphers such as AES. To use a solver for cryptanalysis, we provide it with a known plaintext, a known ciphertext and the set of mathematical equations which use an unknown secret key to transform between the two. The solver is then expected to output the secret key which links the given plaintext and ciphertext, thus satisfying the equation set. Fortunately, solvers are not currently capable of directly attacking modern ciphers. However, the situation is drastically different when side-channel data (information leaked from the cryptographic device due to its internal structure) is introduced into the equation.
This talk will introduce side-channel cryptographic attacks, survey our latest efforts in using machine solvers to attack cryptosystems, and conclude with a successful attack on the AES cipher which requires surprisingly little side-channel data and computation time.
Joint work with Mathieu Renauld, François-Xavier Standaert and Avishai Wool
BIO:
Yossi Oren is a Ph.D. student at the Computer Network and Security Lab at Tel-Aviv University. His research interests are:
• Secure Hardware: Power analysis and other hardware attacks and countermeasures on cryptographic devices; Low-resource cryptographic constructions for lightweight computers such as RFID tags
• Cryptography in the real world: Consumer and voter privacy in the digital era; Web application security
TARDIS: Time and Remanence Decay in SRAM to Implement Secure Protocols on Embedded Devices without Clocks
Kevin Fu (UMass Amherst)
8/2 1:30pm
ABSTRACT:
Lack of a locally trustworthy clock makes security protocols challenging to implement on batteryless embedded devices such as contact smartcards, contactless smartcards, and RFID tags. A device that knows how much time has elapsed between queries from an untrusted reader could better protect against attacks that depend on the existence of a rate-unlimited encryption oracle. The TARDIS (Time and Remanence Decay in SRAM) helps to locally maintain a sense of time elapsed without power and without special-purpose hardware. The TARDIS software computes the expiration state of a timer by analyzing the decay of existing on-chip SRAM memory. The TARDIS enables coarse-grained, hourglass-like timers such that cryptographic software can more deliberately decide how to throttle its response rate. Our experiments demonstrate that the TARDIS can measure time ranging from seconds to several hours depending on hardware parameters. Key challenges to implementing a practical TARDIS include compensating for temperature and handling variation across hardware. Our contributions are (1) the algorithmic building blocks for computing elapsed time from SRAM decay; (2) characterizing TARDIS behavior under different temperatures, capacitors, SRAM sizes, and chips; and (3) three proof of concept implementations that use the TARDIS to enable privacy-preserving RFID tags, to deter double swiping of contactless credit cards, and to increase the difficulty of brute force attacks against e-Passports. Joint work with Amir Rahmati, Mastooreh Salajegheh, Dan Holcomb, Jacob Sorber, Wayne Burleson. To appear at USENIX Security 2012.
BIO:
Kevin Fu will join the University of Michigan as Associate Professor of Computer Science and Engineering in January 2013. His research is in the area of trustworthy computing and low-power embedded devices. In addition to systems security, RFID-scale computation, and energy-aware architectures, Dr. Fu's interests include medical devices and health IT.
Dr. Fu received his PhD in Electrical Engineering and Computer Science from MIT in 2005 and is currently Associate Professor of Computer Science at University of Massachusetts Amherst.
Dr. Fu has served as a visiting scientist at the Food & Drug Administration, the Beth Israel Deaconess Medical Center of Harvard Medical School, and MIT CSAIL, and is a member of the NIST Information Security and Privacy Advisory Board. He previously worked for Bellcore, Cisco, HP Labs, Microsoft Research, and Holland Community Hospital. He is the recipient of a Sloan Research Fellowship, the NSF CAREER award, and best paper awards from USENIX Security, IEEE S&P, and ACM SIGCOMM. Dr. Fu was named MIT Technology Review's TR35 Innovator of the Year in 2009, and is a Senior Member of the Association for Computing Machinery.
Practice-Driven Cryptographic Theory
Tom Ristenpart (University of Wisconsin)
7/31 1:30pm
ABSTRACT:
Cryptographic standards abound: TLS, SSH, IPSec, XML Encryption, PKCS, and so many more. In theory the cryptographic schemes used within these standards solve well understood problems, yet a parade of damaging attacks leave us with the question: What gives?
Theoreticians often suggest (at least in private) that the problems are well-understood and attacks arise because standardizers misunderstand cryptographic theory. I'll use some of my recent work which uses provable-security techniques to analyze important standards (including TLS, HMAC, and PKCS#5) to argue that, just as often, it is the theoreticians who don't have all the answers: analyzing practically-useful cryptography requires pushing models and proof techniques in never-before-considered directions. We'll see how (what I'll call) practice-driven cryptographic theory can lead to new understanding and improved confidence in cryptographic practice.
This talk will cover joint work with Mihir Bellare, Scott Coull, Yevgeniy Dodis, Kevin Dyer, Kenneth Paterson, Thomas Shrimpton, John Steinberger, and Stefano Tessaro.
Computing Elliptic Curves over Q(√5)
Alyson Deines (University of Washington)
7/31 10:30am
ABSTRACT:
I will discuss creating (conjectural) tables of elliptic curves over Q(√5) ordered by conductor up to the
first curve of rank 2. We computed these curves by first computing weight (2,2) Hilbert modular forms over
Q(√5) using an algorithm of Lassina Dembélé. Using various methods we constructed the (conjecturally)
corresponding elliptic curves. I will also discuss newer work towards partially extending these results to the first curve of rank 3. This is joint work with Jonathan Bober, Joanna Gaski, Ariah Klages-Mundt, Benjamin LeVeque, R. Andrew Ohana, Sebastian Pancratz, Ashwath Rabindranath, Paul Sharaba,
Ari Shnidman, William Stein, and Christelle Vincent.
BIO:
Alyson Deines is a graduate student at the University of Washington.
Summer Number Theory Talk 6: Derivatives of p-adic L-functions
Benjamin Lundell (University of Washington)
7/24 4:00pm
ABSTRACT:
We will discuss a new approach to proving the Ferrero-Greenberg formula for the derivative of a Kubota-Leoplodt $p$-adic $L$-function at $s=0$. The aim is to provide a proof which uses two-variable $p$-adic $L$-functions in a manner analogous to the Greenberg-Stevens proof of the Mazur-Tate-Teitelbaum conjecture for elliptic curves. In the Kubota-Leopldt setting, we use the Katz two-variable $p$-adic $L$-function attached to an imaginary quadratic field $K$. This is joint work with Ralph Greenberg and Shaowei Zhang.
BIO:
Benjamin Lundell is Acting Assistant Professor at the University of Washington. His primary research interests lie in algebraic number theory specifically the study of modular forms and Galois representations. Before coming to Washington, he studied at Cornell University, under the supervision of Ravi Ramakrishna, the University of Cambridge, and the University of Illinois at Urbana-Champaign.
Summer Number Theory Talk 5: Pairing-based methods for genus 2 curve jacobians with maximal endomorphism ring
Sorina Ionica (LORIA)
7/24 2:30pm
ABSTRACT:
Algorithms for constructing jacobians of genus 2 curves with nice cryptographic properties involve the computation of Igusa class polynomials for CM quartic fields. The CRT method used to compute these polynomials needs to find first a jacobian with maximal endomorphism ring over a finite field, and then enumerates all others jacobians having maximal endomorphism ring using horizontal isogenies. For $\ell> 2$, we use Galois cohomology and the Tate pairing to compute the action of the Frobenius on the $\ell$-torsion. In view of application to Igusa class polynomials computation, we deduce an algorithm to verify whether the jacobian of a genus 2 curve has locally maximal endomorphism ring at $\ell$. Moreover, we derive a method to construct horizontal isogenies starting from a jacobian with maximal endomorphism ring.
Summer Number Theory Talk 4: Asymptotic nonlinearity of Boolean functions
Francois Rodier (IML)
7/24 2:30pm
ABSTRACT:
The nonlinearity of Boolean functions on the space Fm2 is important in cryptography. It is used to measure the strength of cryptosystems when facing linear attacks. In the case low degree of approximation attacks, we examine the nonlinearity of order r of a Boolean function, which equals the number of necessary substitutions in its truth table needed to change it into a function of degree at most r. Studies aimed at the distribution of Boolean functions according to the r-th order nonlinearity. Asymptotically, a lower bound is established in the higher order cases for almost all Boolean functions, whereas a concentration point is shown in the first and second order nonlinearity case. In the case of vectorial Boolean functions, a concentration point is shown in the first order nonlinearity case.
Summer Number Theory Talk 3: The distribution of zeroes of the zeta functions of Artin-Schreier covers over finite fields
Alina Bucur (UC San Diego)
7/24 11:30am
ABSTRACT:
I will give a quick overview of some new developments in studying the distribution of points and zeroes of the zeta functions for curves over finite fields. Then we will concentrate on the distribution of the zeroes of the zeta functions of the family of Artin-Schreier covers of the projective line over a fixed finite field as the genus goes to infinity. We consider both the global and the mesoscopic regimes, proving that in the limit, the number of zeroes with angles in a prescribed interval of $[-\pi,\pi)$ has a standard Gaussian distribution (when properly normalized).
BIO:
Dr. Bucur received her Ph.D. from Brown University in 2006, and has since held a postdoctoral fellowship at the Institute for Advanced Study and a Moore Instructorship at MIT. Dr. Bucur's research is in analytic number theory, specifically in multiple Dirichlet series and moments of L-functions. Dr. Bucur is undertaking an ambitious research program aimed at a better understanding of multiple Dirichlet series, and her work has been recognized with a Focused Research Grant from the National Science Foundation.
Dr. Bucur has a strong record of excellent teaching at Brown University and MIT, and received a Mathematics Outstanding Teaching Award at Brown. Dr. Bucur has been active in mentoring students and promoting participation by women graduate students and postdoctoral researchers in mathematics. At UCSD, Dr. Bucur will teach both undergraduate and graduate courses, including lower division calculus courses, and upper division and research-level graduate courses in number theory, algebra, and other subjects.
Summer Number Theory Talk 2: The Robbins phenomenon: unexpected numerical stability in p-adic arithmetic
Kiran Kedlaya (UC San Diego)
7/24 10:30am
ABSTRACT:
Since one cannot represent an arbitrary real number on a computer, it is standard to approximate real-number arithmetic using floating-point approximations. The situation is similar for p-adic numbers; we begin by introducing the analogue of floating-point arithmetic for p-adics. We then describe some known and conjectural examples of p-adic numerical stability in which algebraic structures (e.g., cluster algebras) work behind the scenes to keep the loss of numerical precision much lower than one might initially expect. A key example is the Dodgson (Lewis
Carroll) condensation algorithm for computing determinants, for which we obtain a partial result towards a conjecture of Robbins. Joint work with Joe Buhler (CCR La Jolla).
BIO:
Dr. Kedlaya received his Ph.D. in Mathematics from MIT in 2000. For the next three years, he held postdoctoral positions at the Mathematical Sciences Research Institute in Berkeley, at the University of California at Berkeley, and at the Institute for Advanced Study in Princeton. Since then, Dr. Kedlaya has been a faculty member at MIT, first as Assistant Professor and then as Associate Professor. Dr. Kedlaya is an expert on a broad range of topics related to arithmetic algebraic geometry and number theory, especially p-adic cohomology, p-adic Hodge theory, and computational number theory. He is the author of 49 research papers, and his research has been recognized with a highly prestigious five year Presidential Early Career Award for Scientists and Engineers (PECASE) from the NSF. In addition, he has been awarded a Sloan Research Fellowship, and a Clay Liftoff Fellowship.
Dr. Kedlaya has an outstanding record of dedicated teaching, has served as a mentor to numerous undergraduate and graduate students, and has been active in nurturing talented high school students in mathematics, with active involvement in organizational aspects for the International Mathematics Olympiad and as the author of a Putnam Exam problem book. At UCSD, Dr. Kedlaya will teach a range of courses, ranging from lower division calculus to research-level courses in algebra and number theory.
Dr. Kedlaya's research is in the area of number theory and arithmetic algebraic geometry. His specialties include p-adic analytic methods, p-adic Hodge theory, algorithms, and applications in computer science (including cryptography).
Summer Number Theory Talk 1: Computing many rational Hilbert modular forms over Q(sqrt(5))
William Stein (University of Washington)
7/24 9:00am
ABSTRACT:
I will talk about an ongoing computation to enumerate all (modular) elliptic curves over Q(sqrt(5)) up to the first of rank 4.
BIO:
William Stein is a professor of mathematics at the University of Washington. In his mathematics research, he uses the Birch and Swinnerton-Dyer conjecture as motivation to understand the constellation of arithmetic invariants associated to optimal quotients of J0(N). He also uses computers to do explicit computations on modular abelian varieties, and is the main author of SAGE.
In May 2000 he received a Ph.D. degree in mathematics from UC Berkeley (here is his Ph.D. genealogy tree). His thesis involved the Birch and Swinnerton-Dyer conjecture for modular abelian varieties. From May 2000 until May 2001 he was an NSF Postdoctoral Fellow at Harvard, during which time he traveled a huge amount. From 2001 to 2005, he was a Benjamin Peirce Assistant Professor of Mathematics at Harvard University. He joined the UW mathematics department in the Spring of 2006.
A Workflow for Differentially-Private Graph Synthesis
Sharon Goldberg (Boston University)
7/19 1:30pm
ABSTRACT:
We present a new workflow for differentially-private publication of graph topologies. First, we produce differentially private measurements of interesting graph statistics using our new version of the PINQ programming language, Weighted PINQ, which is based on a generalization of differential privacy to weighted sets. Next, we show how to generate graphs that fit any set of measured graph statistics, even if they are inconsistent (due to noise), or if they are only indirectly related to actual statistics that we want our synthetic graph to preserve. We do this by combining the answers to Weighted PINQ queries with a probabilistic inference technique that allows us to synthesize graphs where the statistic of interest aligns with that of the protected graph. I will show how to cast a few graph statistics (degree distribution, edge multiplicity, joint degree distribution) as queries in Weighted PINQ, and then present experimental results of synthetic graphs generated from the answers to these queries.
Joint work with Davide Proserpio (BU) and Frank McSherry (MSR).
BIO:
Sharon Goldberg is an Assistant Professor in the Department of Computer Science at Boston University. Her research focuses on finding practical solutions to problems in network security, by leveraging formal techniques from cryptography and game theory. She received her Ph.D. from Princeton University in 2009, and her B.A.Sc. from the University of Toronto in 2003.
Index calculus and the elliptic curve discrete logarithm problem
Claus Diem (University of Leipzig)
7/2 1:30 pm
ABSTRACT:
Let p be a prime number and B a primitive root modulo p. This means by definition that for every natural number A coprime to p there is a natural number e with A^e \equiv B \bmod p. The smallest such exponent is classically called the index of A modulo p with respect to the base B. Indices are discrete analoga to logarithms, and accordingly nowadays they are usually called discrete logarithms. The question for their efficient computation was already raised in the 19th century but it gained particular relevance because the security of a great number of cryptographic protocols is based on the difficulty of index computation, or, as one says, on the difficulty of the discrete logarithm problem.
Index calculus is a method to compute indices efficiently. Now indices or discrete logarithms can be defined in any finite group, and the question arises if one can substitute the group Fp by another group in which index calculus is not possible. This question lead to the development of elliptic curve cryptography.
In the talk I will present the index calculus method and discuss the question if index calculus is possible in elliptic curves.
BIO:
Claus Diem is visiting from the University of Leipzig. His work is supported by a scholarship from the Deutsche Forschungsgemeinschaft.
The Round Complexity of (concurrent, resettable, efficient) Zero Knowledge in the Bare Public-Key Model
Ivan Visconti (University of Salerno)
6/14 1:30 pm
ABSTRACT:
This talk will first revisit previous work in the Bare Public-Key (BPK) model pointing out subtle problems concerning their security proofs of concurrent and resettable zero knowledge.
Then the talk will focus on showing a new technique to achieve round-optimal concurrent and resettable zero knowledge in the BPK model.
Next the talk will focus on efficient instantiations of the above constructions. It will point out a major limitation of the OR composition of Sigma protocols [CDS94] and an interesting open problem.
Finally the talk will present a new technique for OR composition of Sigma protocols that solve the above open problem and can be of broader interest.
Note: Joint work with Alessandra Scafuro. The first part of this work has been published in EUROCRYPT 2012; the second part is a manuscript in preparation.
BIO:
Ivan Visconti is an assistant professor at the Dipartimento di Informatica ed Applicazioni, Faculty of Mathematical, Physical and Natural Sciences of the University of Salerno (ITALY). His research focuses on foundations of cryptography and is supported by national grants and EU networks of excellence ECRYPT, ECRYPT II.
Ivan Visconti got his PhD in Computer Science in 2003 from Università di Salerno and has been a Post-Doctoral fellow at the Département d'Informatique of the École Normale Supérieure, Paris (FRANCE). Since October 2010 he is on sabbatical leave visiting University of California at Los Angeles.
Verifiable Computation via Quadratic Span Programs
Bryan Parno (MSR)
5/17 1:30 pm
ABSTRACT:
We introduce a new characterization of the NP complexity class, called Quadratic Span Programs (QSPs), which is a natural extension of span programs defined by Karchmer and Wigderson. Our main motivation is the construction of succinct arguments of NP-statements that are quick to construct and verify. QSPs seem well-suited for this task, perhaps even better than Probabilistically Checkable Proofs (PCPs).
In 2010, Groth constructed a NIZK argument in the common reference String (CRS) model for Circuit-SAT consisting of only 42 elements in a bilinear group. Interestingly, his argument does not (explicitly) use PCPs. But his scheme has some disadvantages -- namely, the CRS size and prover computation are both quadratic in the circuit size. In 2011, Lipmaa reduced the CRS size to quasi-linear, but with prover computation still quadratic.
Using QSPs we construct a NIZK argument in the CRS model for Circuit-SAT consisting of just 7 group elements. The CRS size is linear in the circuit size, and prover computation is quasi-linear,
making our scheme seemingly quite practical. (The prover only needs to do a linear number of group operations; the quasi-linear computation is a multipoint evaluation and interpolation.)
Our results are complementary to those of Valiant (TCC 2008) and Bitansky et al. (2012), who use "bootstrapping" (recursive composition) of arguments to reduce CRS size and prover and verifier computation. QSPs also provide a crisp mathematical abstraction of some of the techniques underlying Groth's and Lipmaa's constructions.
BIO:
Bryan Parno is a researcher in Microsoft Research's Security and Privacy Research Group. He received his PhD and Master's degrees at Carnegie Mellon University, where he was advised by Adrian Perrig, and a Bachelor's degree from Harvard University. His current work focuses on the foundations of trust on modern computers. His research interests include computer security, systems, networks, and applied cryptography. In his spare time, he enjoys photography and volunteering as an Emergency Medical Technician.
Adaptively Secure Multi-Party Computation, Revisited
Sanjam Garg (UCLA)
5/3 1:30 pm
ABSTRACT:
Adaptively secure multiparty computation is an essential and fundamental notion in cryptography. In this work we focus on the basic question of constructing a multiparty computation protocol secure against a malicious, adaptive adversary in the stand-alone setting without honest majority in the plain model.
It has been believed that this question can be resolved by composing known protocols from the literature. We show that in fact, this belief is fundamentally mistaken. In particular, we show:
- Round inefficiency is unavoidable when using black-box simulation: There does not exist any o(\frac{n}{\log{n}}) round protocol that adaptively securely realizes a (natural) n-party functionality with a black-box simulator. Note that most previously known protocols in the adaptive security setting relied on black-box simulators.
- A constant round protocol using non-black-box simulation: We construct a constant round adaptively secure multiparty computation protocol in a setting without honest majority that makes crucial use of non-black box techniques.
Taken together, these results give the first resolution to the question of adaptively secure multiparty computation protocols with a malicious dishonest majority in the plain model, open since the first formal treatment of adaptive security for multiparty computation in 1996. (Joint work with Amit Sahai)
BIO:
Sanjam Garg is a PhD student in Cryptography at University of California Los Angeles. He is a recipient of the Chancellor's Prize at UCLA. He received his Bachelors in Computer Science and Engineering from Indian Institute of Technology Delhi in 2008. Sanjam has published several papers in top cryptography and security conferences such as Crypto, Eurocrypt, TCC, CCS, and so on. He has given talks at NTT Labs (Japan), Technion (Israel) and Tel Aviv University (Israel).
New Constructions of Lossy Trapdoor Functions
Brett Hemenway (University of Michigan)
4/26 1:30 pm
ABSTRACT:
Lossy Trapdoor Functions (LTFs) were introduced by Peikert and Waters in STOC '08, and since that time they have become an extremely useful cryptographic primitive. Lossy Trapdoor Functions yield simple constructions of pseudorandom generators, collision resistant hash functions, IND-CCA secure cryptosystems, deterministic encryption, leaky pseudoentropy functions and more.
In this talk, I'll show a number of new constructions of LTFs from a variety of cryptographic primitives and number theoretic assumptions. These constructions can be cast into two broad categories: exploiting (group) homomorphisms of common cryptosystems, and derandomizing randomized lossy primitives.
BIO:
Brett Hemenway received his Bachelor's degree from Brown University in 2004 and his PhD in mathematics from UCLA in 2010 under Rafail Ostrovsky. He is currently a postdoctoral assistant professor at the University of Michigan. His research focuses on coding theory and cryptography.
Practical Private Information Retrieval
Femi Olumofin (Mathematical Sciences, Strategic Technology & Innovation Center, Pitney Bowes)
4/19 1:30 pm
ABSTRACT:
The subject of online privacy has been attracting a lot of attention in recent years, especially as more users are beginning to care about the privacy of their online activities. This increased privacy awareness has renewed the interest of the research community on cryptographic primitives, such as private information retrieval, oblivious transfer, oblivious RAM, and searchable encryption, which are designed to help users preserve the privacy of their queries and/or access to curious or malicious hosts. In this talk, I will show how we revisited the computational practicality of private information retrieval schemes and found the end-to-end response times of a single-server lattice-based scheme and two multi-server information-theoretic PIR schemes to be one to three orders of magnitude (10 -- 1000 times) smaller than the trivial scheme for realistic computation power and network bandwidth. Then, I will describe how we utilized PIR to enhance the scalability of the Tor anonymous communication network by two orders of magnitude. We clarify existing result on the computational practicality of PIR and provide an extension to multi-server PIR schemes and single-server PIR schemes that do not rely heavily on number theory.
BIO:
Femi Olumofin earned his PhD in computer science from the University of Waterloo in 2011. He completed his thesis work on private information retrieval at the Cryptography, Security, and Privacy (CrySP) research group, under the supervision of Prof. Ian Goldberg. Previously, he earned MS and BS degrees in computer science from the University of Manitoba and the University of Benin, respectively. His research interest is in the areas of security, privacy, and applied cryptography. He is currently focused on applying cryptographic protocols to solve security and privacy problems in the domains of databases, location-based services, cloud computing, online behavioural advertising, and onion routing. Recently, he joined the Mathematical Sciences group at the Strategic Technology and Innovation Center of Pitney Bowes to help drive privacy research.
Approximately Strategy-Proof Voting
Eleanor Birrell (Cornell University)
3/1 2:00 pm
ABSTRACT:
The classic Gibbard-Satterthwaite Theorem establishes that only dictatorial voting rules are strategy-proof; under any other voting rule, players have an incentive to lie about their true preferences. We introduce a new approach to circumventing this result: we consider randomized voting rules that approximate a deterministic voting rule and are approximately strategy-proof. We show that any deterministic voting rule can be approximated by an approximately strategy-proof randomized voting rule, and we provide bounds on the parameters that can be achieved.
BIO:
Eleanor Birrell is currently a PhD student at Cornell University, where she works with Rafael Pass and Fred Schneider.
Oblivious Access to Remote Data Storage
Olya Ohrimenko (Brown University)
2/21 1:30 pm
ABSTRACT:
The ''cloud" is emerging as the next generation of data storage where users can remotely keep their data and leave its management to a third party, e.g. Amazon S3 or Microsoft Azure. However, the fact that users no longer have physical possession of the data raises new challenges in terms of data privacy. Storing the data in encrypted form is a key component in maintaining the privacy of the data. However, encrypting the data is not enough since information about the data may be leaked through the pattern in which users access the data. We show how to achieve efficient privacy-preserving data access using a combination of encryption, which directly hides data values, and stateless oblivious RAM simulation, which hides the pattern of data accesses.
In this talk we propose a method with O(log n) worst-case access overhead for simulating users' requests to outsourced data of size n, using a scheme that is data-oblivious with very high probability. We assume that the simulation has access to a small private workspace but does not maintain state in between data access requests. Our simulation makes use of pseudo-random hash functions and is based on a novel hierarchy of cuckoo hash tables that all share a common stash. The method outperforms all previous techniques for stateless clients in terms of access overhead.
Existing oblivious storage solutions typically involve small amortized overheads for obscuring the access pattern, but nevertheless involve potentially huge variations in access times, depending on when they occur. To this end, we show how to de-amortize oblivious storage simulations so that each request takes a worst-case bounded amount of time.
We also provide experimental results from a prototype implementation of our scheme. We show that the involved constants are small resulting in at most 2log n round trips for each client request. Finally, we demonstrate that the performance of our stateless scheme is comparable to a more powerful scheme where a client is allowed to keep a state.
Joint work with: Michael T. Goodrich, Michael Mitzenmacher and Roberto Tamassia
BIO:
Olya Ohrimenko is a Ph.D. candidate in the Department of Computer Science at Brown University working with Professor Roberto Tamassia. Her research interests include designing algorithms and data structures to ensure user privacy and data integrity in the cloud-based storage model. Olya received a BCS (Hons) degree from The University of Melbourne in 2007 and her M.Sc. degree from Brown University in 2010.
ZKPDL: A Language-Based System for Efficient Zero-Knowledge Proofs and Electronic Cash
Sarah Meiklejohn (UCSD)
2/2 1:30 pm
ABSTRACT:
In recent years, many advances have been made in cryptography, as well as in the performance of communication networks and processors. As a result, many advanced cryptographic protocols are now efficient enough to be considered practical, yet research in the area remains largely theoretical and little work has been done to use these protocols in practice, despite a wealth of potential applications.
This paper introduces a simple description language, ZKPDL, and an interpreter for this language. ZKPDL implements non-interactive zero-knowledge proofs of knowledge, a primitive which has received much attention in recent years. Using our language, a single program may specify the computation required by both the prover and verifier of a zero-knowledge protocol, while our interpreter performs a number of optimizations to lower both computational and space overhead.
Our motivating application for ZKPDL has been the efficient implementation of electronic cash. As such, we have used our language to develop a cryptographic library, Cashlib, that provides an interface for using e-cash and fair exchange protocols without requiring expert knowledge from the programmer.
This is joint work with C. Chris Erway, Alpetkin Kupcu, Theodora Hinkle, and Anna Lysyanskaya, and appeared at USENIX Security 2010.
BIO:
Sarah is a third-year PhD student in Computer Science at the University of California, San Diego. She is a member of the Security and Cryptography Group and is advised by Hovav Shacham and supported by a fellowship from the Charles Lee Powell Foundation. Before starting at UCSD, she obtained an Sc.B. in Mathematics and an Sc.M. in Computer Science from Brown University under the guidance of Anna Lysyanskaya. Her research interests focus on the interface between security and cryptography; i.e., trying to improve the way in which cryptographic protocols are incorporated into secure systems, as well as coming up with cryptographic models that accurately reflect real-world attacks. Most recently, Sarah spent the summer of 2011 at MSR Redmond, working in the cryptography group with Melissa Chase.
Generalized oblivious Transfer (GOT)
Samuel Ranellucci (University of Montreal)
1/4 1:30 pm
ABSTRACT:
In this paper, we introduce a primitive known as Verifiable Oblivious Transfer. It is similar to oblivious
transfer except that the sender is commited to its input. We then generate protocols for Generalized Oblivious Transfer by secret
sharing using the Verifiable Oblivious Transfer primitive based on previous work. The protocols are universally composable.
The GOT protocol is used to instantiate Batch Single-Choice Cut-And-Choose OT which in conjunction with a modification to the main protocol of
[LP11], achieves constant round secure function evaluation based on Yao's Garbled Circuit. In addition, the
idea of GOT is used in conjunction with linear secret sharing and commitments to instantiate a primitive
known as Multi-Sender K-Out-of-N OT. This primitive is the most important building block
of the optimization of the IPS compiler presented in [LOP11]. In contrast to their specific computational
assumptions, our protocols only require black-box Verifiable OT. In addition, the GOT protocols can be used
to execute Priced Oblivious Transfer.
Privacy Amplification and Non-Malleable Extractors Via Character Sums
Xin Li (University of Washington)
11/10 2:00 pm
ABSTRACT:
In studying how to communicate over a public channel with an active adversary, Dodis and Wichs introduced the
notion of a non-malleable extractor. A non-malleable extractor dramatically strengthens the notion of a strong
extractor in the sense that it requires the output to be close to uniform given the seed as well as the output
of the extractor on an arbitrarily related different seed.
We construct the first explicit non-malleable extractor. Our extractor works for sources with entropy rate above
half. To achieve a polynomial running time when outputting many bits, we rely on a widely-believed conjecture
about the distribution of prime numbers in arithmetic progressions.
Using our non-malleable extractor, we obtain protocols for "privacy amplification": key agreement between two
parties who share a weakly-random secret. Our protocols work in the presence of an active adversary with
unlimited computational power, and have asymptotically optimal entropy loss. When the secret has entropy rate
greater than 1/2, the protocol takes two rounds. When the secret has entropy rate delta for any constant delta>0,
our protocol takes a constant (polynomial in 1/delta) number of rounds. Our protocols run in polynomial time
under the above well-known conjecture about primes.
Joint work with Yevgeniy Dodis, Trevor D. Wooley and David Zuckerman.
BIO:
Xin Li is a postdoctoral researcher in the theory group of the computer science & engineering department at the
University of Washington, Seattle. His main research interests include the use of randomness in computation,
complexity theory and theory of computation in general. He received his B.S. and M.S. from Tsinghua University,
China and his Ph.D. from the University of Texas at Austin.
How to solve a 112-bit ECDLP using game consoles
Joppe Bos (EPFL)
10/13 1:30 pm
ABSTRACT:
In this presentation I will outline two projects which I have been working on during my PhD.
Both projects are related to the elliptic curve discrete logarithm problem (ECDLP): the theoretical foundation of many modern cryptosystems.
First I will outline how we have set a new record by solving the ECDLP over a 112-bit prime field using a cluster of PlayStation 3 game consoles in 2009.
Next, the negation map optimization is discussed: this is an technique to speed up the Pollard rho method when solving the ECDLP. It is well known that the random walks used by Pollard rho when combined with the negation map get trapped in fruitless cycles. I will present that previously published approaches to deal with this problem are plagued by recurring cycles: effective alternative countermeasures are proposed.
BIO:
Joppe Bos is a PhD student under supervision of Prof. Arjen Lenstra at the laboratory for cryptologic algorithms, EPFL, Switzerland. His research interest include public-key cryptanalysis, fast arithmetic and efficient implementations of cryptologic algorithms with a focus on elliptic curve cryptography and integer factorization algorithms. Currently he is doing an internship with Peter Montgomery at MSR and works on factoring large integers using graphics cards.
Secure Biometric Computation and Outsourcing
Marina Blanton (University of Notre Dame)
9/1 1:30 pm
ABSTRACT:
Recent advances in biometric recognition and the increasing use of biometric data prompt significant privacy challenges associated with the possible misuse, loss, or theft of biometric data. There are legitimate reasons for biometric matching to be performed by two mutually distrustful parties, where due to privacy and liability considerations, neither party is willing to share its data. Alternatively, biometric experiments run by a single entity are often so large in scale that they are inevitably placed on an untrusted computational cloud or grid, where sensitive biometric data must also be protected. This gives rise to the need to develop secure computation and outsourcing techniques over biometric data where no information is revealed to the participants except the desired outcome of the computation and the outcome of the computation can be trusted. In this talk, I will describe our recent results for securely comparing biometric images and outsourcing computation over biometric data in a robust manner. Most of the talk discusses techniques for matching of iris codes.
BIO:
Marina Blanton is an Assistant Professor in the Department of Computer Science and Engineering at the University of Notre Dame. She received her Ph.D. in CS from Purdue University in 2007, MS in CS from Purdue University in 2004, and MS in EECS from Ohio University in 2002. Dr. Blanton's research interests lie in information security, privacy, and applied cryptography.
She has over 40 research publications, is a co-editor of a recently published two-volume "Algorithms and Theory of Computation Handbook," and is actively involved in professional service.
Efficient Oblivious Automata Evaluation and Its Application
Payman Mohassel (University of Calgary)
8/30 1:30 pm
ABSTRACT:
Abstract: Oblivious Automata Evaluation allows two parties -a client who holds an input string X and a server who holds an Automata G- to learn the result of evaluating G on X but nothing else. In this talk, I will describe a simple and efficient, secure two-party construction for this problem. I will also explain some applications of our construction to pattern matching and intrusion detection. Finally, I report on the results of some experiments based on a prototype implementation.
Joint work with Salman Niksefat and Saeed Sadeghian.
BIO:
Payman Mohassel is an assistant professor in the Department of Computer Science at University of Calgary. He received his Ph.D. from University of California Davis, in 2009 under the supervision of Matthew Franklin. His research interests are in both practical and theoretical aspects of cryptography, and information security. Some of his more recent projects include "efficient and privacy-preserving computation", "provably secure encryption and signature schemes", and "privacy in genomic computation".
Cryptography with Imperfect Randomness
Bhavana Kanukurthi (UCLA)
8/4 1:30 pm
ABSTRACT:
Cryptographic protocols, though powerful theoretically, are typically built for certain ideal conditions that are
frequently violated in practice. For instance, it is commonly assumed that a user wishing to perform secure
computation has access to perfect randomness and is performing his computation on a device whose internals are
completely shielded from adversarial observation and tampering. This talk will survey some of my recent results
on designing cryptographic primitives that are secure under less-than-ideal conditions. I will first present a
brief overview of my work on enabling even users with just weak secrets such as biometrics and passwords to do
cryptography. I will then present the details of my work on tamper-resilient cryptography which removes the
assumption that cryptographic computation is performed in a perfectly sealed black box.
This talk is based on joint works with Yael Kalai and Amit Sahai (CRYPTO 2011) and Nishanth Chandran, Rafail
Ostrovsky and Leonid Reyzin (STOC 2010).
BIO:
Bhavana Kanukurthi is a post-doctoral researcher at UCLA, working under the guidance of Prof. Rafail Ostrovsky.
She recently received her PhD in Computer Science at Boston University, where she was advised by Prof. Leonid
Reyzin. She is a recipient of the 2010 Boston University Computer Science Research Excellence award. Her research
lies in the area of cryptography.
Cryptography with Imperfect Randomness
Vanessa Teague (University of Melbourne)
8/1 1:30 pm
ABSTRACT:
Code voting seeks to address the issues of privacy and integrity for Remote Internet Voting. It sidesteps many of
the inherent vulnerabilities of the Internet and client platforms but it does not provide end-to-end verification
that votes are counted as cast. In this paper, we propose a simple technique to enhance the verifiability of code
voting by ensuring that the Vote Server can only access the acknowledgement codes if the vote code is correctly
registered by a threshold set of Trustees. The mechanism adds an extra level of verifiability in registering and
counting the vote. Voter-verification is simple and direct: the voters need only check that the acknowledgement
code returned to them agrees with the value on their code sheet. To ensure receipt-freeness we propose the use
of a single acknowledgement code per code sheet, rather than individual acknowledgement codes for each candidate
as with usual code voting.
I will first present Pretty Good Democracy for voting schemes in which the voter selects a single candidate, then
show how it can be extended to more expressive voting schemes such as Borda, approval voting and STV.
(Joint work with Peter Ryan, University of Luxembourg, and James Heather, University of Surrey.)
BIO:
Dr Vanessa Teague is a researcher at the University of Melbourne. After completing her PhD thesis at Stanford on
cryptographic protocols for rational participants, she returned to Australia and focused on end-to-end verifiable
protocols for secure electronic voting, particularly those suitable for the obscure and complicated voting system
used in Aus. She is co-chair of this year’s USENIX/ACCURATE Electronic Voting Technologies workshop and Workshop
on Trustworthy Elections (EVT/WOTE 2011). She has also recently made a hobby of public criticism of insecure
electronic voting protocols that are unsuitable for use in Australian elections but were used anyway.
Computing the unit group, class group and compact representations in algebraic function fields
Sean Hallgren (Penn State University)
7/28 1:30 pm
ABSTRACT:
Number fields and global function fields have many similar properties. Both have many applications to cryptography
and coding theory, and the main computational problems for number fields, such as computing the ring of integers
and computing the class group and the unit group, have analogues over function fields. The complexity of the
number field problems has been studied extensively and these problems have been the source of some exponential
speedups by quantum computation. In this paper we study the analogous problems in function fields. We show that
there are efficient quantum algorithms for computing the unit group, the class group and for solving the principal
ideal problem in function fields of arbitrary degree. We show that compact representations exist, which allows
us to show that the principal ideal problem is in NP. Unlike the number field case, we are also able to show that
these compact representatives can be computed efficiently.
BIO:
Sean Hallgren is an Associate Professor at Penn State University. He works on quantum computation, with an
emphasis on understanding when there are exponential speedups by quantum algorithms. He received his B.S.
from Carnegie Mellon University and his Ph.D. from the University of California, Berkeley. Prior to joining
Penn State he ran the quantum computing group at NEC Laboratories. He is a recipient of the NSF CAREER award,
the PECASE award and several teaching awards.
Charm: A Framework for Rapidly Prototyping Cryptosystems
Matthew Green (Johns Hopkins University)
7/19 1:30 pm
ABSTRACT:
Over the past decade the cryptographic research community has made impressive progress in developing new cryptographic protocols. This work has advanced our understanding of basic technologies such as public key encryption, key agreement, and digital signatures. Moreover, it has given us entirely new paradigms for securing data, such as Attribute Based Encryption, anonymous credentials and techniques for computing on encrypted data.
Despite these advances, only a trickle of new cryptographic technology has filtered down to the systems community in the form of useable cryptographic implementations. Even supported prototype research implementations are few and far between. This is a major loss for researchers, to say nothing of industry and the open source community.
In this talk we introduce Charm, an extensible Python-based framework for rapidly prototyping cryptographic systems. Charm was designed from the ground up to support the development of advanced cryptographic schemes. It includes support for multiple cryptographic settings, an extensive library of re-usable code, along with the infrastructure necessary to quickly implement interactive protocols. Our framework also provides a series of specialized tools that enable different cryptosystems to interoperate.
This paper describes Charm and the various capabilities provided through our modular architecture. Through several examples, we show that our approach produces a potential order of magnitude decrease in code size compared to standard C implementations, while inducing an acceptable performance impact.
BIO:
Matthew Green is an Assistant Research Professor at the Johns Hopkins University Information Security Institute. His research focus is on cryptographic techniques for maintaining users' privacy, and on technologies that enable the deployment of privacy-preserving protocols. He is also a co-founder of Independent Security Evaluators (ISE), a custom security evaluation firm with a global client base.
Along with a team at Johns Hopkins and RSA Laboratories, he discovered flaws in the Texas Instruments Digital Signature Transponder, a cryptographically-enabled RFID device used in the Exxon Speedpass payment system and in millions of vehicle immobilizers. He is a recipient of the PET Award for his contribution to privacy enhancing technologies.
Unbounded HIBE and Attribute-Based Encryption
Brent Waters (University of Texas, Austin)
7/19 10:30 am
ABSTRACT:
We present HIBE and ABE schemes which are ``unbounded" in the sense that the public parameters do not impose additional limitations on the functionality of the systems. In all previous constructions of HIBE in the standard model, a maximum hierarchy depth had to be fixed at setup. In all previous constructions of ABE in the standard model, either a small universe size or a bound on the size of attribute sets had to be fixed at setup.
Our constructions avoid these limitations. We use a nested dual system encryption argument to prove full security for our HIBE scheme and selective security for our ABE scheme, both in the standard model and relying on static assumptions. Our ABE scheme supports LSSS matrices as access structures and also provides delegation capabilities to users.
This is joint work with Allison Lewko.
BIO:
Dr. Brent Waters received his Ph.D. in Computer Science from Princeton University in 2004. From 2004-2005, he was a post-doctoral at Stanford University then worked at SRI as a Computer Scientist in the Principled Systems group. In 2008 he joined the faculty at The University of Texas at Austin as an assistant professor. Dr. Waters'
research interests are in the areas of computer security and applied cryptography. His work has focused on Identity-Based Cryptography, security of broadcast systems, and authentication of remote systems.
He has award and invited papers. He is noted as a founder of functional encryption. Dr. Waters both publishes and has served on the program committees of the top technical security venues (CRYPTO, Eurocrypt, the ACM Conference on Computer and Communications Security (CCS), Usenix Security and the IEEE Conference on Security and Privacy).
Dr. Waters has been an invited speaker in industry and at research Universities, including MIT, CMU, and Stanford. He was the keynote speaker on functional encryption at the2008 NIST workshop on Identity-Based Encryption. Dr. Waters is a National Academy of Sciences Kavli Fellow and recipient of the NSF CAREER award, a Microsoft Faculty Fellow, and a Sloan Research Fellowship.
Using Extensions of Min-Entropy to Help with Key Agreement and Leakage Resilience
Leo Reyzin (Boston University)
7/14 1:30 pm
ABSTRACT:
There are many different notions of information-theoretic entropy and its computational analogues. The right notion and a toolbox of lemmas can make for beautifully simple proofs. Drawing on examples from information-theoretic key agreement and leakage-resilient cryptography (no background in either is assumed), I will show how various extensions of min-entropy can help analyze cryptographic constructions. I will also present some (not always well-formed) open problems.
BIO:
Leo Reyzin is an Associate Professor of Computer Science at Boston University, conducting research on extending cryptographic techniques to provide protection in more hostile environments. He received his A.B. in computer science from Harvard, and S.M. and Ph.D. in cryptography at MIT. He is a recipient of the National Science Foundation's CAREER award and of Boston University's Neu Family Award for Excellence in Teaching.
Secure Computation with Sublinear Amortized Work
Mariana Raykova (Columbia University)
7/8 1:30 pm
ABSTRACT:
We present the first protocol for secure two-party computation that allows a client and a server to evaluate an arbitrary function f with an amortized poly-logarithmic computational overhead over the insecure version of f. For functions that can be computed in sublinear time, this yields the first general secure protocol with sublinear amortized complexity. We provide a generic and simple protocol that achieves the asymptotic improvement, as well as a vastly optimized practical protocol, using new techniques for oblivious memory access, and relying on existing two-party computation protocols to evaluate a small number of carefully selected simple operations. We achieve orders of magnitude performance improvements, even on today’s moderate input sizes, for (amortized) execution of important tasks, such as binary search on a large dataset – a core building block for secure DB access, location-based services, etc. In general, our approach will likely be advantageous in amortized computations where the server’s input is large, and the client’s input and the computed program are small.
Joint work with Dov Gordon, Jonathan Katz, Vladimir Kolesnikov, Tal Malkin, Yevgeniy Vahlis
BIO:
Mariana is a PhD student at Columbia University working in the areas of cryptography and security with Tal Malkin and Steve Bellovin. Her research focuses on secure computation and more specifically on improving efficiency that aims to make secure multiparty computation protocols usable in practice. This includes considering new computational models, specific functionalities, relaxed security notions. The last two years she was an intern with the crypto group at MSR, and this summer she is working in the security group.
Outsourcing Multi-Party Computation
Seny Kamara (MSR Redmond)
7/7 1:30 pm
ABSTRACT:
We initiate the study of secure multi-party computation (MPC) in a server-aided setting, where the parties have access to a single server that (1) does not have any input to the computation; (2) does not receive any output from the computation; but (3) has a vast (but bounded) amount of computational resources. In this setting, we are concerned with designing protocols that minimize the computation of the parties at the expense of the server.
We develop new definitions of security for this server-aided setting, that generalize the standard simulation-based definitions for MPC, and allow us to formally capture the existence of dishonest but non-colluding participants. This requires us to introduce a formal characterization of non-colluding adversaries that may be of independent interest.
We then design general-purpose server-aided multi-party protocols that are more efficient (in terms of computation and communication) for the parties than the alternative of running a standard MPC protocol (i.e., without the server). Finally, we give a general transformation from any secure delegated computation scheme to a server-aided two-party protocol. Our transformation formalizes the intuitive connection between the problems of server-aided computation and verifiable computation by interpreting the former as a means for verifiably and privately outsourcing a secure multi-party computation protocol to an untrusted worker.
Joint work with Payman Mohassel and Mariana Raykova.
BIO:
Seny Kamara is a researcher in the Crypto Group in XCG at Microsoft Research. He received his Ph.D. in Computer Science from Johns Hopkins University under the supervision of Fabian Monrose. His main research interests are in security and cryptography and his recent work has focused on designing new cryptographic models and techniques to alleviate security and privacy concerns that arise in the context of cloud computing. In 2006, he was a research fellow at the UCLA Institute for Pure and Applied Mathematics and has been the recipient of the Johns Hopkins Phillips and Camille Bradford fellowship and of the Bell Labs Graduate Research fellowship.
Fully Homomorphic Encryption over the integers with Shorter Public Keys
Avradip Mandal (University of Luxembourg)
6/30 1:30 pm
ABSTRACT:
At Eurocrypt 2010 van Dijk {\sl et al.} described a fully homomorphic encryption scheme over the integers. The main appeal of this scheme (compared to Gentry's) is its conceptual simplicity. This simplicity comes at the expense of a public key size in ${\cal \tilde O}(\lambda^{10})$ which is too large for any practical system. In this paper we reduce the public key size to ${\cal \tilde O}(\lambda^{7})$ by encrypting with a quadratic form in the public key elements, instead of a linear form. We prove that the scheme remains semantically secure, based on a stronger variant of the approximate-GCD problem, already considered by van Dijk {\sl et al}.
We also describe the first implementation of the resulting fully homomorphic scheme. Borrowing some optimizations from the recent Gentry-Halevi implementation of Gentry's scheme, we obtain roughly the same level of efficiency. This shows that fully homomorphic encryption can be implemented using simple arithmetic operations.
BIO:
Avradip Mandal is a PhD student at University of Luxembourg, Luxembourg under the supervision of Jean-Sebastien Coron. Currently he is an intern at eXtreme Computing Group, Microsoft Research with Lan Nguyen as his mentor. Before he obtained M.Math and B.Tech from University of Waterloo, Canada and Indian Institute of Technology Kharagpur, India respectively.
Leftover Hash Lemma, Revisited
Yevgeniy Dodis (New York University)
6/23 1:30 pm
ABSTRACT:
The famous Leftover Hash Lemma (LHL) states that (almost) universal hash functions are good randomness extractors. Despite its numerous applications, LHL-based extractors suffer from the following two drawbacks: (1) Large Entropy Loss: to extract v bits from distribution X of min-entropy m which are e-close to uniform, one must set v<= m - 2*log(1/e), meaning that the entropy loss L = m-v>= 2*log(1/e). (2) Large Seed Length: the seed length n of universal hash function required by the LHL must be linear in the length of the source. Quite surprisingly, we show that both limitations of the LHL --- large entropy loss and large seed --- can often be overcome (or, at least, mitigated) in various quite general scenarios. First, we show that entropy loss could be reduced to L=log(1/e) for the setting of deriving secret keys for most cryptographic applications, including signatures/MACs, CPA/CCA-secure encryption, etc. Specifically, the security of these schemes gracefully degrades from e to at most e + sqrt(e * 2^{-L}). (Notice that, unlike standard LHL, this bound is meaningful even for negative entropy loss, when we extract more bits than the the min-entropy we have!) Second, we study the soundness of the natural *expand-then-extract* approach, where one uses a pseudorandom generator (PRG) to expand a short "input seed" S into a longer "output seed" S', and then use the resulting S' as the seed required by the LHL (or, more generally, any randomness extractor). Unfortunately, we show that, in general, expand-then-extract approach is not sound if the Decisional Diffie-Hellman assumption is true. Despite that, we show that it is sound either: (1) when extracting a "small" (logarithmic in the security of the PRG) number of bits; or (2) in *minicrypt*. Implication (2) suggests that the sample-then-extract approach is likely secure when used with "practical" PRGs, despite lacking a reductionist proof of security! The paper will appear at CRYPTO 2011 and can be found at http://eprint.iacr.org/2011/088
BIO:
Yevgeniy Dodis is an Associate Professor of computer science at New York University. Dr. Dodis received his summa cum laude Bachelors degree in Mathematics and Computer Science from New York University in 1996, and his PhD degree in Computer Science from MIT in 2000. Dr. Dodis was a post-doc at IBM T.J.Watson Research center in 2000, and joined New York University as an Assistant Professor in 2001.
Dr. Dodis' research is primarily in cryptography and network security. In particular, he worked in a variety of areas including exposure-resilient cryptography, cryptography and imperfect randomness, cryptography with biometrics and other noisy data, authenticated encryption, hash functions and information-theoretic cryptography. Dr. Dodis has more than 70 scientific publications at various conferences, journals and other venues, has been on program committees of many international conferences (including FOCS, STOC, CRYPTO and Eurocrypt), and gave numerous invited lectures and courses at various venues.
Dr. Dodis is the recipient of National Science Foundation CAREER Award, IBM Faculty Award and Best Paper Award at 2005 Public Key Cryptography Conference. As an undergraduate student, he was also a winner of the US-Canada Putnam Mathematical Competition.
Finding Incentives to Secure Internet Routing
Sharon Goldberg (Boston University)
6/22 1:30 pm
ABSTRACT:
Despite a decade of research, the problem of securing the global Internet's routing system is far from solved. Indeed, a key hurdle for the transition to secure routing is the fact that the Internet consists of thousands of autonomous systems (e.g. backbone providers like AT&T, content providers like Google, business networks like Bank of America), that will make deployment decisions according to their own local business objectives. Worse yet, the security benefits provided by secure routing protocols tend not to kick in until they have been adopted by a large number of autonomous systems. As a result, the conventional wisdom argues that global deployment of routing security protocols is infeasible.
This talk overviews a series of our results that challenge this conventional wisdom. We shall use both theoretical arguments and simulations to show how local incentives can be harnessed to secure
the majority of autonomous systems in the Internet. No background
will be assumed.
BIO:
Sharon Goldberg is an assistant professor of computer science at Boston University. Her research focuses on finding practical solutions to problems in network security, by leveraging formal techniques from cryptography, algorithms, and game theory. She obtained her PhD from Princeton University in July 2009, and her BASc from the University of Toronto in June 2003.
Separating Succinct Non-Interactive Arguments From All Falsifiable Assumptions
Daniel Wichs (New York University)
6/2 1:30 pm
ABSTRACT:
In this paper, we study succinct computationally sound proofs (arguments) for NP, whose communication complexity is poly-logarithmic the instance and witness sizes. The seminal works of Kilian '92 and Micali '94 show that such arguments can be constructed under standard cryptographic hardness assumptions with four rounds of interaction, and that they be made non-interactive in the random-oracle model. The latter construction also gives us some evidence that succinct non interactive arguments (SNARGs) may exist in the standard model with a common reference string (CRS), by replacing the oracle with a sufficiently complicated hash function whose description goes in the CRS. However, we currently do not know of any construction of SNARGs with a formal proof of security under any simple cryptographic assumption.
In this work, we give a broad black-box separation result, showing that black-box reductions cannot be used to prove the security of any SNARG construction based on any falsifiable cryptographic assumption. This includes essentially all common assumptions used in cryptography (one-way functions, trapdoor permutations, DDH, RSA, LWE etc.). More generally, we say that an assumption is falsifiable if it can be modeled as an interactive game between an adversary and an efficient challenger that can efficiently decide if the adversary won the game. This is similar, in spirit, to the notion of falsifiability of Naor '03, and captures the fact that we can efficiently check if an adversarial strategy breaks the assumption.
Our separation result also extends to designated verifier SNARGs, where the verifier needs a trapdoor associated with the CRS to verify arguments, and slightly succinct SNARGs, whose size is only required to be sub-linear in the statement and witness size.
Joint work with Craig Gentry.
BIO:
Daniel is a PhD student at NYU under the supervision of Yevgeniy Dodis. His research focuses on various theoretical and practical aspects of cryptography, with a recent focus on building cryptosystems that remain secure even in the presence of side-channel leakage on their secret keys. Daniel will be graduating this June and joining IBM research as a Josef Raviv Memorial postdoctoral fellow.
Efficient Fully Homomorphic Encryption from (Standard) LWE
Zvika Brakerski (Weizmann)
5/13 12:15 pm
ABSTRACT:
In fully homomorphic encryption, it is possible to transform an encryption of a message, m, into an encryption of any (efficient) function of that message, f(m), without knowing the secret key. This property makes it into a very useful cryptographic building block.
We present a fully homomorphic encryption scheme that is based solely on the (standard) learning with errors (LWE) assumption. Applying known results on LWE, the security of our scheme is based on the worst-case hardness of short vector problems on arbitrary lattices. As icing on the cake, our scheme is quite efficient, and has very short ciphertexts.
Our construction improves upon previous works in two aspects:
Since our scheme has very short ciphertexts, we use it to construct an asymptotically-efficient LWE-based single-server private information retrieval (PIR) protocol. The communication complexity of our protocol (in the public-key model) is k ⋅
polylog, k+log |DB| bits per single-bit query, which is better than any known scheme. Previously, it was not known how to achieve a communication complexity of even poly(k, log|DB|) based on LWE.
Joint work with Vinod Vaikuntanathan.
BIO:
Zvika Brakerski is a PhD student at the Weizmann Institute of Science, Israel, where he is supervised by Prof. Shafi Goldwasser. He is a visiting student at MIT this Spring.
Lightweight Cryptographic Algorithms
Andrey Bogdanov (K.U. Leuven)
5/6 1:30 pm
ABSTRACT:
As crucial applications go pervasive, the need for security in RFID and sensor networks is dramatically increasing, which requires secure yet efficiently implementable cryptographic primitives including secret-key ciphers and hash functions. In such constrained environments, the area and power consumption of a primitive usually comes to the fore and standard algorithms are often prohibitively expensive to implement. Once this research problem was identified, the cryptographic community was quick to design a number of tailored lightweight cryptographic algorithms to specifically address this challenge: stream ciphers like Trivium and Grain, block ciphers like DESL, DESXL, KATAN/KTANTAN, PrintCipher and PRESENT, as well as hash functions like Quark and Spongent. In this talk, I will revisit the technical framework behind the lightweight cryptographic algorithms and discuss the specific challenges arising in the design and cryptanalysis of such primitives.
BIO:
Andrey Bogdanov is a postdoctoral researcher at K.U.Leuven in Belgium and a Visiting Researcher with Microsoft Research. He received his PhD in Computer Science and Electrical Engineering from the Ruhr University of Bochum in Germany under the supervision of Christof Paar. Andrey’s primary research area is the design and cryptanalysis of symmetric-key cryptographic algorithms. He is also interested in provable aspects of symmetric-key ciphers, side-channel cryptanalysis as well as efficient implementations of secret- and public-key cryptography. Andrey has co-designed several ciphers including the award-winning lightweight block cipher PRESENT which is filed to be become an ISO standard. He proposed the first attack on the KeeLoq automotive authentication system – a major and widely used solution for keyless entry. He holds an IACR best paper award for his work on efficient implementations of post-quantum signature schemes. Andrey is leading the Cryptographic Algorithms work group within the Belgian Fundamental Research Network on Cryptology and Information Security (BCRYPT).
Efficient Non-Interactive Secure Computation
Manoj Prabhakaran (UIUC)
4/29 1:30 pm
ABSTRACT:
Suppose that a receiver R wishes to publish an encryption of her secret input x so that every sender S, holding an input y, can reveal f(x,y) to R by sending her a single message. This should be done while simultaneously protecting the secrecy of y against a corrupted R and preventing a corrupted S from having an unfair influence on the output of R beyond what is allowed by f .
When the parties are semi-honest, practical solutions can be based on Yao’s garbled circuit technique. However, for the general problem when the parties, or even S alone, may be malicious, all known polynomial-time solutions are highly inefficient. This is due in part to the fact that known solutions make a non-black-box use of cryptographic primitives, e.g., for providing non-interactive zero- knowledge proofs of statements involving cryptographic computations on secrets.
Motivated by the above question, we consider the problem of secure two-party computation in a model that allows only parallel calls to an ideal oblivious transfer (OT) oracle with no additional interaction. We obtain the following results.
Combining the above results with 2-message (parallel) OT protocols in the CRS model, we get the first solutions to the initial motivating question which only make a black-box use of standard cryptographic primitives.
Joint work with Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai.
BIO:
Manoj Prabhakaran is an assistant professor in the Computer Science department at the University of Illinois, Urbana-Champaign. He obtained a Ph.D. in computer science from Princeton University in 2005, and a B.Tech. in computer science and engineering from the Indian Institute of Technology, Bombay in 2000. His primary research interests are in theoretical cryptography.
Concurrent Security
Huijia (Rachel) Lin (Cornell)
4/28 1:30 pm
ABSTRACT:
Cryptographic protocols have been developed for a variety of tasks, including
electronic auctions, electronic voting systems, privacy preserving data mining
and more. The Internet allows for the concurrent execution of cryptographic
protocols. Such concurrency severely challenges their security.
In
this talk we introduce a novel technique for transforming any
"stand-alone" secure protocol (i.e., one whose security is only
guaranteed if executed in isolation) into one that is secure under concurrent
executions. Contrary to previous results in the literature, this result is
established without relying on additional trusted infrastructure or
cryptographic hardness assumptions.
BIO:
Huijia Lin is a Ph.D. candidate in
the Department of Computer Science at Cornell. Her research interests are in
the field of Cryptography. She is a recipient of the Microsoft Graduate Student
Fellowship.
Toward (More) Efficient Secure
Two-Party Computation
Jonathan
Katz (University of Maryland)
3/24 1:30 pm
ABSTRACT:
I will survey several recent efforts aimed at bringing secure two-party
computation (at least in the semi-honest setting) closer to practice. The main
focus of the talk will be on private function evaluation (PFE), where one party
holds an input $x$ and the other holds a function $f$; the goal is to compute
$f(x)$ while revealing nothing more to either party. I
show the first constant-round protocol for PFE with complexity *linear* in the
size of the circuit computing the function; in particular, the protocol avoids
universal circuits.
As time permits, I will also discuss the possibility of secure computation with
(amortized) poly-logarithmic complexity, and some recent implementation results
showing that generic protocols based on Yao's garbled-circuit approach can be
more efficient than 'optimized' protocols based on homomorphic encryption.
BIO:
Jonathan Katz is an associate professor in the Department of Computer Science
at the University of Maryland. He is a co-author of the widely used textbook
"Introduction to Modern Cryptography".
Revocation for Delegatable
Anonymous Credentials
Lan
Nguyen (MSR Redmond)
3/17 1:30 pm
ABSTRACT:
This paper introduces and formalizes homomorphic proofs that allow
"adding" proofs and proof statements to get a new proof of the
"sum" statement. Additionally, we introduce a construction of
homomorphic proofs, and show an accumulator scheme with delegatable
non-membership proofs (ADNMP) as one of its applications with provable
security. Finally, the proposed accumulator method extends the BCCKLS scheme [C:BCCKLS09] to create a new provably secure revocable delegatable anonymous credential (RDAC) system. Intuitively,
the new accumulator's delegatable non-membership (NM)
proofs enable user A, without revealing her identity, to delegate to user B the
ability to prove that A's identity is not included in a blacklist that can
later be updated. The delegation is redelegatable, unlinkable, and verifiable.
BIO:
Lan Nguyen is a Software Engineer in the XCG Security and Cryptography Group,
Microsoft. He has a Bachelor of Computer Science from the University of New
South Wales and a Ph.D. in Information Security from the University of
Wollongong and did a Post-Doc at CSIRO, all in Australia. His research is
mainly on Cryptographic Privacy Enhancing Technologies, such as Anonymous
Credentials and Revocation, Group/Ring Signatures and Mix-nets. In industry, he
has been working on different areas such as Distributed Key Management, TPM,
Software Licensing and Protection, Security Testing, Hard Disk Encryption and
Strong Authentication.
Verifiable Delegation of Computation
over Large Datasets
Yevgeniy
Vahlis (Columbia University)
3/14 12 pm
ABSTRACT:
We study the problem of computing on large datasets that are stored on an
untrusted server. We follow the approach of amortized verifiable computation
introduced by Gennaro, Gentry, and Parno in CRYPTO
2010. We present the first practical verifiable computation scheme for high
degree polynomial functions. Such functions can be used, for example, to make
predictions based on polynomials fitted to a large number of sample points in
an experiment. In addition to the many non-cryptographic applications of
delegating high degree polynomials, we use our verifiable computation scheme to
obtain new solutions for verifiable keyword search, and proofs of retrievability. Our constructions are based on the DDH
assumption and its variants, and achieve adaptive security, which was left as
an open problem by Gennaro et al. (albeit for general
functionalities).
Our second result is a primitive which we call a verifiable database (VDB).
Here, a weak client outsources a large table to an untrusted server, and makes
retrieval and update queries. For each query, the server provides a response
and a proof that the response was computed correctly. The goal is to minimize
the resources required by the client. This is made particularly challenging if the
number of update queries is unbounded. We present a VDB scheme based on the
hardness of the subgroup membership problem in composite
order bilinear groups.
BIO:
Yevgeniy Vahlis is a postdoctoral research scientist at Columbia University,
where he works under the direction of Professor Tal Malkin. Yevgeniy completed
his Ph.D. at the University of Toronto in 2010 under the supervision of
Professor Charles Rackoff.
Decentralizing
Attribute-Based Encryption
Allison
Lewko (UT Austin)
3/11 12:15 pm
ABSTRACT:
We present a Multi-Authority Attribute-Based Encryption (ABE) system. In our
system, any party can become an authority and there is no requirement for any
global coordination other than the creation of an initial set of common
reference parameters. A party can simply act as an ABE authority by creating a
public key and issuing private keys to different users that reflect their
attributes. A user can encrypt data in terms of any boolean formula over attributes issued from any
chosen set of authorities. Finally, our system does not require any central
authority.
In this talk, I will present our system and discuss its proof, which employs
dual system encryption techniques. Our system uses bilinear groups of composite order, and we prove security under static
assumptions in the random oracle model.
This is joint work with Brent Waters.
BIO:
Allison Bishop is currently a PhD student at the University of Texas at Austin,
advised by Brent Waters.
Non-Interactive
Verifiable Computing
Bryan
Parno (MSR Redmond)
3/3 1:30 pm
ABSTRACT:
We introduce and formalize the notion of Verifiable Computation, which enables
a computationally weak client to "outsource" the computation of a
function F on various dynamically-chosen inputs to one or more workers. The
primary constraint is that the verification of the results should require
substantially less effort than computing F from scratch.
We present a protocol that allows the worker to return a computationally-sound,
non-interactive proof that can be verified in O(m * poly(lambda))
time, where m is the bit-length of the output of F, and lambda is a security
parameter. The protocol requires a one-time pre-processing stage by the client
which takes O(|C| * poly(lambda)) time, where C is the smallest known Boolean
circuit computing F.
Finally, we present new constructions that promise substantially better
performance in practice, though current instantiations do not achieve the full
set of desirable properties for verifiable computing.
BIO:
Bryan Parno is a researcher in Microsoft Research's Security and Privacy
Research Group. He received his PhD and Master's degrees at Carnegie Mellon
University, where he was advised by Adrian Perrig,
and a Bachelor's degree from Harvard University. His current work focuses on
the foundations of trust on modern computers. His research interests include
computer security, systems, networks, and applied cryptography. In his spare
time, he enjoys photography and volunteering as an Emergency Medical
Technician.
Overcoming
the Hole in the Bucket: Public-key Cryptography Resilient to Continual Memory
Leakage
Zvika
Brakerski (Weizmann Institute and MIT)
2/24 1:30 pm
ABSTRACT:
In recent years, there has been a major effort to design cryptographic schemes
that remain secure even when arbitrary information about the secret key is
leaked (e.g., via side-channel attacks). We explore the possibility of
achieving security under continual leakage from the entire secret key by
designing schemes in which the secret key is updated over time.
In this model, we construct public-key encryption schemes, digital signatures,
and identity-based encryption schemes that remain secure even if an attacker
can leak a constant fraction of the secret memory (including the secret key) in
each time period between key updates. We also consider attackers who may probe
the secret memory during the updates themselves.
In the talk I will present the model and explain the main ideas in this work. I
will also present developments and follow-up works and the remaining open problems
in the area.
Joint work with Yael Tauman Kalai,
Jonathan Katz and Vinod Vaikuntanathan.
BIO:
Zvika Brakerski is a PhD student at the Weizmann Institute of Science, Israel,
where he is supervised by Prof. Shafi Goldwasser. He is a visiting student at MIT this Spring.
Position-based Cryptography
Nishanth Chandran (UCLA)
2/3
10:30am
ABSTRACT:
What constitutes an identity in cryptography?
Typical examples include your name and your social-security number, or
your fingerprint/iris-scan, or your public-key coming from some trusted
public-key infrastructure. However, in many situations, your identity is
defined by where you are. For example, we know the role of a bank-teller
behind a bank window not because she shows us her credentials but by
merely knowing her location. In this work, we initiate the study of
cryptographic protocols where the identity (or other credentials and inputs) of
a party is derived from its geographic location.
We explore the possibility of "Position Based
Cryptography" and construct secure protocols for two
fundamental tasks: secure positioning and position based key exchange.
Position based cryptography has several fascinating applications -- for
example, two military bases can securely talk to each other with a guarantee on
the physical location of one another.
This talk is based on
joint work with Vipul Goyal, Ryan Moriarty, and Rafail
Ostrovsky
BIO:
Nishanth Chandran is a doctoral candidate at UCLA
working with Prof. Rafail Ostrovsky
and Prof. Amit Sahai. His research
interests are cryptography, security and theory. He has published several
papers in leading conferences such as STOC, FOCS, CRYPTO, EUROCRYPT
and so on. Nishanth was awarded the Graduate Student Fellowship as well as the
Dissertation Year Fellowship from the Graduate Division at UCLA. He received
the Chorafas International Award for research in
2010. Nishanth obtained a Bachelors in Computer
Science and Engineering from Anna University, India in 2005 and a Masters in
Computer Science from UCLA in 2007. He is expected to receive his doctoral
degree in June 2011.
Black-box, Round-efficient Secure Computation
Hoeteck Wee (Queens College, CUNY)
2/1
1:30pm
ABSTRACT:
We present
round-efficient protocols for secure multi-party computation with a dishonest
majority that rely on *black-box* access to the underlying primitives. Our main
contributions are:
-- a
O(log^* n)-round protocol that relies on black-box access to dense
cryptosystems, homomorphic encryption schemes, or lossy
encryption schemes. This improves upon the recent O(1)^{log^*
n} -round protocol of Lin, Pass and Venkitasubramaniam
(STOC 2009) that relies on non-black-box access to a smaller class of
primitives.
-- a O(1)-round
protocol requiring in addition, black-box access to a one-way function with
sub-exponential hardness, improving upon the recent work of Pass and Wee (Eurocrypt 2010).
These are the first
black-box constructions for secure computation with sublinear
round complexity. Our constructions build on and improve upon the work of Lin
and Pass (STOC 2009) on non-malleability amplification, as well as that of Ishai et al. (STOC 2006) on black-box secure computation.
(Based
on work appearing at FOCS 2010.)
BIO:
Hoeteck Wee is an
assistant professor at Queens College, CUNY. He received his PhD from UC
Berkeley and his BSc from MIT. He was previously a post-doc at Columbia
University and a visiting student at Tsinghua University and IPAM. Hoeteck
received the NSF career award in 2010. His research revolves around the design
and analysis of cryptographic algorithms and protocols.
The SHA-3 competition through the rebound lens
Christian Rechberger (K U Leuven, Belgium)
1/27
1:30pm
ABSTRACT:
After the MD5
disaster and related breakthroughs in hash cryptanalysis, the cryptographic community as well as practitioners are searching for a next
generation hash function standard. This culminated in a large ongoing
international effort, the SHA-3 competition, that
started in 2008.
In this talk
we survey the remaining candidates in this competition and discuss how this
competition led to a new way of doing hash cryptanalysis: the rebound attack.
Hash functions that allow for simple differential analysis were benefiting from
early scrutiny. Recently we started to apply this method also to very different
constructions, and still consistently get results that beat the best known
attacks. We survey those results and the main ideas behind them, comment on
their impact on the SHA-3 competition, and discuss future applications outside
of hash cryptanalysis.
BIO:
Christian
Rechberger is currently a postdoctoral researcher at KU Leuven, Belgium, and
visiting researcher at Microsoft Research, Redmond. He obtained his Ph.D. in
applied cryptography at Graz University of Technology, Austria, with Vincent Rijmen, the developer of the Advanced Encryption Standard
(AES), as advisor. His research interests span various topics in IT-security,
cryptography, and algorithms, including design and analysis of cryptographic
primitives, RFID security, and efficient implementations.
Rechberger is
known for his work on the international standard SHA-1, is co-developer of the
rebound attack, and co-designer of the SHA-3 finalist Grostl, received two IACR best paper awards, and is leading
the hash function work group within the ECRYPT network of excellence of the
European commission.
Password-based Authenticated Key Exchange at the Cost of Diffie-Hellman
Vinod Vaikuntanathan
1/20
1:30pm
ABSTRACT:
Public-key Cryptography was born in the 1970s
with the work of Diffie and Hellman where they
defined and realized a foundational primitive called key exchange. In key
exchange, two parties – Alice and Bob – who have never met each
other before, can exchange messages over a public channel and agree on a shared
secret key!
Although the original proposal of Diffie and Hellman is secure only against passive
eavesdropping adversaries, much effort has since been devoted
to developing key-exchange protocols resisting active adversaries (this
is also called the “authenticated key exchange” problem). Active
adversaries can not only listen in on the communication channel, but also
interfere with it arbitrarily -- modifying, inserting or deleting messages, but
also impersonating the communicating entities. To resist such malice, it is
necessary for Alice and Bob to share some prior, common setup information.
A variety of setup assumptions have been
considered in the literature. In this talk, I will focus on a very realistic
and extremely challenging setting – one where Alice and Bob share a
low-entropy password (think of an ATM pin, or a computer login password). Such
a password has too little entropy to be cryptographically useful, yet we will
present protocols that use the shared password to “bootstrap” a
cryptographically strong shared key. Furthermore, our protocol will expend
essentially the same amount of resources as the original Diffie-Hellman
protocol, while also offering protection against active adversaries. Thus, in a
sense, we obtain authenticated key exchange “for free” in the challenging
password-based setting.
This is joint work with Jonathan Katz (UMD).
BIO:
Vinod Vaikuntanathan is a researcher in the
XCG group at MSR Redmond since July 2010. In previous avatars, he was a
postdoctoral fellow at IBM T.J. Watson (where he held the Josef Raviv postdoctoral fellowship from 2008-2010) and a Ph.D.
student at MIT (where he was awarded the George Sprowls
award for the best Ph.D. thesis in Computer Science in 2009).
The
Cloud was tipsy and ate my files!
Giuseppe Ateniese
6/2 1:30pm
ABSTRACT:
Our entire digital life will be stored on remote storage servers such as Amazon
S3, Microsoft Azure, Google, MobileMe, etc. Our
emails, pictures, calendars, documents, music/video playlists, and generic
files will be readily available, anytime and anywhere.
In this talk, we will answer the following question: How can we check whether
the entire content of our digital life is actually intact and accessible, even
though we have no local copy of it?
BIO:
Giuseppe Ateniese is an Associate Professor of
Computer Science at the Johns Hopkins University. He is currently a visiting
researcher at Microsoft Research.
Generalized
Algorithm for DLP with Auxiliary Inputs
Jung Hee Cheon
6/29 2:30pm
ABSTRACT:
The DLP with auxiliary inputs is to find $\alpha$ when $g^{\alpha^i}$
(i=0,1,2,\dots,d)$ as well as $g, g^{\alpha}$ are
given. Recently, numerous cryptosystems are designed on a weaker variant of
this problem. One example is the strong Diffie-Hellman
problem. It has been shown that the complexity of this problem is lower than
the original DLP by upto $\sqrt
d$ group operations when $p-1$ or $p+1$ has an appropriate divisor. In this
talk, we present a generalization of this algorithm, which can be applied even
when $p-1$ and $p+1$ are almost prime. We also discuss how many parameters are
susceptible to this attack.
BIO:
Jung Hee Cheon received the
B.S. and Ph.D. degrees in Mathematics from KAIST in 1991, and 1997,
respectively. He is a professor of Mathematical Sciences at the Seoul National
University (SNU). Before joining to SNU, he was in ETRI, Brown university, and ICU. He is on the editorial board of Journal
of KIISC and CSI. He received the best paper award in Asiacrypt
2008. His research interests include computational number theory, cryptography,
and information security.
Trustworthy
Medical Device Software
Kevin Fu
7/20 1:30pm
ABSTRACT:
This talk will summarize what is known about the trustworthiness of medical
device system software. A version of this talk will be presented at an
Institute of Medicine workshop on evaluation of present-day FDA regulatory
practices for medical devices.
Today it would be difficult to find a medical device that does not critically
rely on computer software in its function, manufacture, or use in clinical
decision making. Despite the lessons learned by the radiation accidents of the
Therac-25 twenty years ago, medical devices that rely on software (e.g., drug
infusion pumps, linear accelerators for radiation) continue to injure or kill
patients in preventable ways. Why is it so hard to create trustworthy software
for medical devices? First, devices are not isolated devices. They are systems
of systems. And software plays a significant role for control of these critical
systems that can significantly affect patient safety, either positively or
negatively, depending on its trustworthiness. Failure to meaningfully specify
requirements, complacency, and lack of care for human factors further erode
trustworthiness. The lack of trustworthy medical device software leads to
shortfalls in properties such as safety, effectiveness, dependability,
reliability, security, and privacy. Good systems engineering and the adoption
of modern software engineering techniques can address many of the risks of
medical device software---leading to devices that help patients
lead more normal, healthy lives.
BIO:
Kevin Fu is an assistant professor in the Department of Computer Science at the
University of Massachusetts Amherst in the beautiful northeastern region of the
United States.
Reasons to chat with Kevin: security and privacy, ultra low-power
RFID-scale computing, mHealth security and privacy,
cardiac arrhythmias, European hearth breads, and/or coffee roasting.
Kevin's current research interests include trustworthy medical device software
and low-power storage for flash memory. He primarily investigates how to ensure
the security and privacy of pervasive devices that must withstand determined,
malicious parties. Recent projects range from security analysis of embedded devices
to compiler techniques for energy-aware programs on RFID-scale computers. The
security analysis spans several systems ranging from contactless no-swipe
credit cards and implantable cardiac defibrillators to access-controlled Web
sites and automated software updates.
Kevin is an Alfred P. Sloan Research Fellow, MIT Technology Review TR35
Innovator of the Year, and recipient of the NSF CAREER award. His research
appears in computer science conferences, medical journals, and has been
featured in media such as The New York Times, The Wall Street Journal, and
various news programs. He served on numerous program committees of leading
conferences in secure systems, and has given dozens of invited talks world-wide
to industry, government, and academia.
Prof. Fu leads the UMass Amherst Security and Privacy Research (SPQR) lab. He
serves as director of the RFID Consortium on Security and Privacy
(RFID-CUSP.org) and co-director of the Medical Device Security Center
(secure-medicine.org). He is also a frequent visiting faculty member at
Microsoft Research and the Beth Israel Deaconess Medical Center. Fu received
his Ph.D. in Electrical Engineering and Computer Science from MIT. He also
holds a certificate of achievement in artisanal bread making from the French Culinary
Institute and maintains an active participation in the study of Latin and the
Classics. Kevin's son consumes as much material as he can from CACM.
For more information, visit http://www.cs.umass.edu/~kevinfu/
A
Framework for the Sound Specification of Cryptographic Tasks
Juan Garay
8/11 10:30am
ABSTRACT:
Nowadays it is widely accepted to formulate the security of a protocol carrying
out a given task via the "trusted-party paradigm," where the protocol
execution is compared with an ideal process where the outputs are computed by a
trusted party that sees all the inputs. A protocol is said to securely carry
out a given task if running the protocol with a realistic adversary amounts to
"emulating'' the ideal process with the appropriate trusted party. In the
Universal Composability (UC) framework the program
run by the trusted party is called an /ideal
functionality/. While this simulation-based security formulation provides
strong security guarantees, its usefulness is contingent on the properties and
correct specification of the ideal functionality, which, as demonstrated in
recent years by the coexistence of complex, multiple functionalities for the
same task as well as by their "unstable" nature, does not seem to be
an easy task.
In this work we address this problem, by introducing a general methodology for
the sound specification of ideal functionalities. First, we introduce the class
of /canonical/ ideal functionalities for a cryptographic task, which unifies
the syntactic specification of a large class of cryptographic tasks under the
same basic template functionality. Furthermore, this representation enables the
isolation of the individual properties of a cryptographic task as separate
members of the corresponding class. By endowing the class of canonical
functionalities with an algebraic structure we are able to combine basic
functionalities to a single final canonical functionality for a given task.
Effectively, this puts forth a bottom-up approach for the specification of
ideal functionalities: first one defines a set of basic constituent
functionalities for the task at hand, and then combines them into a single
ideal functionality taking advantage of the algebraic structure.
We showcase our methodology by applying it to a variety of basic cryptographic
tasks, including commitments, digital signatures, zero-knowledge proofs, and
oblivious transfer. While in some cases our derived canonical functionalities
are equivalent to existing formulations, thus attesting to the validity of our
approach, in others they differ, enabling us to "debug" previous
definitions and pinpoint their shortcomings.
This is joint work with Aggelos Kiayias
(Univ. of Athens and Univ. of Connecticut) and Hong-Sheng Zhou (Univ. of
Maryland).
BIO:
Juan A. Garay received his Ph.D. in Computer Science
from Penn State in 1989, and is currently a Lead Member of Technical Staff at
AT&T Labs - Research. Before joining AT&T he was a
a Member of Technical Staff at Bell Labs, and from
1990 to 1998 a Research Staff Member at the IBM T.J. Watson Research Center. In
1992 he was a postdoctoral fellow at The Weizmann Institute of Science in
Israel, and he spent 1996 as a visiting scientist at the Centrum voor Wiskunde en Informatica (CWI) in Amsterdam. His current research
interests include theoretical and practical aspects of cryptographic protocols
and schemes and privacy-preserving computation. Besides many contributions of a
foundational nature, he has been involved in the design, analysis and
implementation of a variety of secure systems. He has published extensively in
the areas of cryptography, network security, distributed computing, and
algorithms; been awarded two dozen patents; and served on the committees of
many conferences and international panels.
Solving
Revocation with Efficient Updates of Anonymous Credentials
Markulf Kohlweiss
9/24 1:30pm
ABSTRACT:
Anonymous credential system promise efficient, ubiquitous access to digital
services while preserving user privacy. However, their diffusion is impaired by
the lack of efficient revocation techniques. Traditional credential revocation
measures based on certificate revocation lists or online certification
authorities do not provide privacy and cannot be used in privacy-sensitive
contexts. Existing revocation techniques specifically geared towards anonymous
credential systems are more involved -- for the credential issuer, users, as
wells as credential consumers -- as users have to prove that their credential
is still valid, e.g., not included in a revocation list.
We introduce a novel, non-interactive technique to update issuer-controlled
attributes of anonymous credentials. Revocation is implemented by encoding the
validity time of a credential into one of these attributes. With the proposed
protocol, credential issuers can periodically update valid credentials off-line
and publish a small per-credential update value on a public bulletin-board.
Users can later download their values and re-validate their credentials to
prove possession of a valid credential for the current time period. We compare
such a solution with revocation mechanisms based on cryptographic accumulators.
For certain scenarios our solution outperforms prior solutions for credential
revocation in terms of communication and computational costs for the users and
credentials consumers while the issuer's effort is comparable to the best prior
proposals.
BIO:
Markulf is Austrian expat who did his PhD at KU Leuven, Belgium. Starting from
October, he will be a Postdoc at MSR, Cambridge, UK.
Since his master thesis, he has been working on protocols related to anonymous
credentials. Some protocols he contributed to are:
e-cash, anonymous credential revocation, delegatable
anonymous credentials, private-information retrieval/oblivious transfer, and
private searching.
Markulf's cryptographic interests lie primarily in
zero-knowledge, two-party computation protocols, and definitional issues. One
goal is to find and define those cryptographic building blocks that are most
valuable for constructing larger privacy enhancing protocols. A good example
for such a building block is a signature scheme that allows for an efficient
proof of knowledge. Markulf is also happy to talk about about
weird properties of the GS proof system, different ways of achieving
simulation-sound NIZK proofs, or CCA secure encryption schemes that combine
well with GS proofs and two party computation protocols.
Secure
and Efficient Evaluation of Multivariate Polynomials and Applications
Payman Mohassel
10/28 1:30pm
ABSTRACT:
In this talk, I will describe an efficient and secure protocol for secure
two-party evaluation of private inputs on a public multivariate polynomial. The
focus is on designing a protocol with security against malicious adversaries,
with low round and communication complexity.
First, I motivate the problem by showing how a number of interesting protocols
can be formulated in this framework. Then, I will go into more detail about the
techniques we use for designing our protocol.
BIO:
Payman is an assistant professor in the computer
science department at University of Calgary Since July 2009. Before
that, he recieved his Ph.D. at UC Davis under the
supervision of Matthew Franklin.
Payman's research interests are in cryptograhpy, information security and theoretical computer
science. Some of his more recent projects include efficient and secure
multiparty computation, provably secure encryption and signatures schemes, and
privacy in genomic computation
Expressive
encryption from hard lattice problems
Shweta Agrawal
12/2 10:30am
ABSTRACT:
Traditionally, in cryptography, lattices have been used for cryptanalysis, i.e.
in breaking cryptosystems. However, since Ajtai's
breakthrough result (in 1996) which established surprising connections between
average case and worst case hardness of various lattice problems, there has
been great interest in constructing cryptosystems from hard lattice problems.
We will describe the first Identity Based Encryption system (in which any
arbitrary string, usually name or email address, can be one's public key) from
lattices in the standard model (independently discovered by Cash, Hofheinz, Kiltz, Peikert) . Next, we will present
methods to substantially improve the above IBE construction to make it more
space and time efficient. We will also present a new method for "lattice
basis delegation" which allows the construction of more expressive IBE
(hierarchical IBE), and compare this new technique with the earlier basis
delegation mechanism of CHKP.
To conclude, we will discuss future directions in building even more expressive
encryption systems from lattices.
The material discussed is from joint work with Dan Boneh
and Xavier Boyen.
BIO:
Shweta Agrawal is a
graduate student at UT Austin. Her research interests lie in Cryptography and
Information Theory. Her recent work in cryptography includes constructions of
secure encryption systems from hard lattice problems.
Leakage-Resilient
Cryptography: Modeling and Combating Side-Channel Attacks
Gil Segev
12/13 3:30pm
ABSTRACT:
Most of the work in the analysis of cryptographic schemes has traditionally
focused on abstract adversarial models that do not capture "side-channel
attacks". Such attacks exploit various forms of unintended leakage of
sensitive information, which is inherent to almost all physical
implementations. Inspired by extremely devastating real-life attacks, in this
talk I will describe a recent approach for modeling and combating side-channel
attacks. I will focus on a framework for modeling a wide range of attacks that
rely on partial leakage of secret keys. In particular, I will present a simple
and efficient construction of a public-key encryption scheme that is resilient
to leakage of almost its whole secret key, as well as a generic method for
constructing leakage-resilient encryption schemes that can be based on a
variety of number-theoretic assumptions.
In addition, if time permits I will describe a recent line of research on the
design of data structures that enjoy constant-time operations in the worst
case, as an approach for combating timing attacks.
BIO:
Gil Segev is currently a postdoctoral researcher at Microsoft Research Silicon
Valley. He joined Microsoft in the summer of 2010 after receiving a Ph.D. from
the Weizmann Institute of Science, where he was advised by Prof. Moni Naor. Gil's research focuses
on the foundations of computer science with a significant emphasize on
cryptography. Motivated by cryptographic applications, Gil is constantly
exploring a variety of research areas other than cryptography, including data
structures and hashing schemes, computations over massive data sets, and their
interface with security and privacy.