Microsoft Research Redmond Cryptography Colloquium

Past Speakers

[ Summer 2008 | Fall 2008 | Spring 2009 | Summer 2009 | Fall 2009 | Spring 2010 | Summer 2010 | Fall 2010 ]

   (For current and future speakers, see MSR Redmond Cryptography Colloquium)

Summer and Fall 2010:

Gil Segev
MSR Silicon Valley

12/13 3:30pm
Building 99
Room 1915A

Leakage-Resilient Cryptography: Modeling and Combating Side-Channel Attacks

Shweta Agrawal
University of Texas at Austin

12/2 10:30am
Building 99
Room 1919C

Expressive encryption from hard lattice problems    (video)

Payman Mohassel
University of Calgary

10/28 1:30pm
Building 99
Room 1927B

Secure and Efficient Evaluation of Multivariate Polynomials and Applications

Elliptic Curve Cryptography Conference

10/18 - 10/22
Building 99
Room 1919C

More info

Markulf Kohlweiss
KULeuven/MSR Cambridge

9/24 1:30pm
Building 115
Room 4381

Secure Revocation with Efficient Updates of Anonymous Credentials

Cloud Cryptography Workshop

8/5 - 8/6
Building 99
Room 1919C

More info

Juan Garay
ATT Labs

8/11 10:30am
Building 99
Room TBA

A Framework for the Sound Specification of Cryptographic Tasks

Ed Dawson
Queensland University of Technology

8/2 1:30pm
Building 99
Room 1915A

Elliptic Curves, Group Law, and Efficient Computation

Kevin Fu
UMass Amherst

7/20 1:30pm
Building 99
Room 1915A

Trustworthy Medical Device Software

Jung Hee Cheon
Seoul National Unviersity

6/29 2:30pm
Building 99
Room 1927B

Generalized Algorithm for DLP with Auxiliary Inputs

Giuseppe Ateniese
Johns Hopkins Unviersity

6/2 1:30pm
Building 99
Room 1915A

The Cloud was tipsy and ate my files!

 

 

 

 

Summer 2008:

Mihir Bellare
University of California, San Diego
6/13 - 7/18

Alexandra Boldyreva
Georgia Institute of Technology
7/28 - 7/30

7/29 10:30am
Building 99
Room 1919 C

Deterministic Encryption: Theory and Application

Kenneth A. Ribet
University of California, Berkeley
8/13

8/13 3:30pm
Building 99
Room 1919 C

Two-dimensional mod p Galois representations attached to modular forms

Alptekin Küpçü
Brown University
8/25

8/25 1:30pm
Building 99
Room 1927 B

Incentivizing Outsourced Computation

Adi Shamir
Weizmann Institute of Science
8/22 - 9/3

8/27 1:30pm
Building 99
Room 1927

How cryptosystems get broken - new side channel attacks on the implementation of cryptography

Peter Montgomery
Microsoft Research, Redmond

8/28 3:30pm
Building 99
Room 1919

Preliminary Design of Post-Sieving Processing for RSA-768

Adi Shamir
Weizmann Institute of Science
8/22 - 9/3

8/29 1:30pm
Building 99
Room 1919

New algebraic attacks on cryptosystems represented by systems of low degree polynomial equations

 

 

Fall 2008:

Petr Lisonek
Simon Fraser University
9/24

9/24 1:30pm
Building 99
Room 1927

Non-linear functions and Kloosterman sums

Kevin Fu
University of Massachusetts, Amherst
9/29

9/29 10:30am
Building 99
Room 1919C

Implantable Medical Devices: Security and Privacy for Pervasive, Wireless Healthcare

Mihir Bellare
University of California, San Diego
10/6-10/8

10/6 10:30am
Building 99
Room 1919C

Cryptography: From Theory to Practice

Yevgeniy Dodis
New York University
10/9-10/10

10/9 1:30pm
Building 99
Room 1505

Deniable Authentication

Abhi Shelat
University of Virginia
10/13-10/16

10/13 1:30pm
Building 99
Room 2535

A Rational Defense Against Concurrent Attacks

Robert Rolland
ERISC and Institut de Mathématiques
10/13-10/20

10/15 1:30pm
Building 99
Room 1927

Bilinear Complexity of the Multiplication in a Finite Extention of a Finite Field

Cédric Fournet
Microsoft Research Cambridge
10/22-10/24

10/22 1:30 pm
Building 99
Room 1919

A Cryptographic Compiler for Information-Flow Security

Cormac Herley
Microsoft Research Redmond

10/29 1:30 pm
Building 99
Room 1927

One Time Password Access to Any Server Without Changing the Server

Neal Koblitz
University of Washington
11/12

11/12 1:30 pm
Building 99
Room 1919C

Special vs Random Curves: Could the Conventional Wisdom Be Wrong?

Ivan Visconti
Università di Salerno
11/17-11/21

11/18 1:30 pm
Building 99
Room 1915

Simulation-Based Concurrent Non-Malleable Commitments and Decommitments

Drew Sutherland
MIT
11/19

11/19 1:30 pm
Building 99
Room 1927B

Computing class polynomials with the Chinese Remainder Theorem

Anna Lysyanskaya
Brown University
12/10-12/16

12/10 1:30 pm
Building 99
Room 1919

Fair Exchange with a Distributed Offline TTP

Eyal Goren
McGill University
12/15-12/19

12/15 1:30 pm
Building 99
Room 2535

Singular Moduli

Hovav Shacham
UC San Diego
12/16-12/18

12/16 1:30 pm
Building 99
Room 1927

Return-Oriented Programming: Exploits Without Code Injection

Hovav Shacham
UC San Diego
12/16-12/18

12/17 1:30 pm
Building 99
Room 1919

Compact Proofs of Retrievability

 

Spring 09:

Tonghai Yang
University of Wisconsin, Madison
1/12-1/16

1/13 10:30 am
Building 99
Room 1927

Arithmetic Intersection and a conjecture of Lauter

William Stein
University of Washington
2/3

2/3 10:30 am
Building 99
Room 1919C

The Sage Mathematical Software Project

Rene Schoof
University of Rome

2/19 10:30 am
Building 99
Room 1919C

Buchmann's algorithms and Arakelov class groups

Peter Stevenhagen
Leiden University

3/10 1:30 pm
Building 99
Room 1915A

Abelian surfaces with a given number of points

Everett Howe
CCR, San Diego

3/10 3:30 pm
Building 99
Room 1915A

Genus-2 curves with a given number of points

Francois Morain
Ecole polytechnique

4/22 1:30pm
Building 99
Room 1919C

Advances in the CM method for elliptic curves

Nils Bruin
Simon Fraser University

4/23 3:30pm
Building 99
Room 1919C

(4,4)-split Jacobians of curves of genus 2

 

Summer 09:

Tomoyoshi Ibukiyama
Osaka University

6/3 1:30pm
Building 99
Room 1927

Supersingular abelian varieties and modular forms

Paul Zimmermann
INRIA

6/12 10:30am
Building 99
Room 1927

Modern Computer Arithmetic

Rich Schroeppel
Sandia National Laboratories

7/16 10:30am
Building 99
Room 1919C

SANDstorm, Elliptic Curves, and a Bit of Fun

Dan Shumow
University of Washington

7/16 3:30pm
Building 99
Room 1919C

Elliptic Curve Isogenies: A Computational Approach

Mastooreh Salajegheh
University of Massachusetts, Amherst

7/22 10:30am
Building 99
Room 1919C

CCCP: Secure remote storage for computational RFIDs

Tal Malkin
Columbia University

8/11 1:30pm
Building 99
Room 1915A

Public Key Cryptosystems: Stronger Security from General Assumptions

Jens Groth
University College London

8/26 1:30pm
Building 99
Room 1927B

Pairing-based Non-interactive Zero-Knowledge Proofs

 

Fall 09:

Nishanth Chandran
UCLA

9/28 10:30am
Building 99
Room 1927B

Position-based Cryptography

Thomas Ristenpart
UC San Diego

10/4 10:30am
Building 99
Room 1927B

Exploring Information Leakage in Third-Party Compute Clouds

Kazue Sako
NEC

11/4 1:30pm
Building 99
Room 1927B

How can cryptographic protocols serve the real world?--the case of privacy enhanced authentication--group signatures

Orr Dunkelman
Technion, Israel institute of technology

12/1 10:30am
Building 99
Room 1927B

Key Recovery Attacks of Practical Complexity on AES Variants With Up To 10 Rounds

Alina Oprea
RSA Laboratories

12/2 3:30pm
Building 99
Room 1915A

HAIL (High-Availability and Integrity Layer) for Cloud Storage

 

Spring 10:

Claudio Orlandi
University of Arhus

2/3 3:30pm
Building 99
Room 1915A

Multiparty Computation for Dishonest Majority: from Passive to Active Security at Low Cost

Michael Naehrig
MSR Redmond

3/2 10:30am
Building 99
Room 1919C

Choosing curves, coordinates and algorithms for computing cryptographic pairings

Neeraj Kayal
MSR India

3/2 1:30pm
Building 99
Room 1919C

A + B = C

Christophe Petit
UC Louvain

3/5 10:30am
Building 115
Room 3381

Hash functions and Cayley graphs: the end of the story?

Satya Lokam
MSR India

3/16 10:30am
Building 99
Room 1927B

Matrix Rigidity and Complexity of Linear Transformations

Ben Adida
Children's Hospital Boston
and Harvard Medical School

3/18 3:30pm
Building 99
Room 1919C

Privacy-Protecting Health Software Platforms

Workshop on Voting Technology

3/19 10am -- 5pm
Building 99
Room 1927B

More info






Deterministic Encryption: Theory and Application
Alexandra Boldyreva

7/29 10:30am
ABSTRACT:
The focus of the talk is deterministic public-key encryption schemes. Besides being interesting from theoretical and historical perspectives, the deterministic encryption primitive has applications to fast and secure search on remote data. We study several new notions of security for deterministic encryption and relations among them. We present several very efficient deterministic encryption schemes that provably satisfy the strongest-possible security definition (in the random oracle model). We finally provide the constructions that achieve security for many practical settings, without relying on the idealized random oracle model. The talk is based on joint papers with Mihir Bellare, Serge Fehr and Adam O'Neill.
BIO:
Alexandra Boldyreva is an Assistant Professor in the School of Computer Science at the Georgia Institute of Technology. She received a Ph.D. in Computer Science from the University of California at San Diego in 2004. She is a recipient of the NSF CAREER award. Her research interests are in cryptography and information security.


Two-dimensional mod p Galois representations attached to modular forms
Kenneth A. Ribet

8/13 3:30pm
ABSTRACT:
Classical newforms are cusp forms on congruence subgroups of SL(2,Z) that are eigenvectors for the Hecke operators. These modular forms give rise to two-dimensional representations of the absolute Galois group of the rational field. Conversely, if one starts with a semisimple two-dimensional representation of this Galois group over a finite field, the representation should arise from a newform if a mild necessary condition (involving complex conjugation) is satisfied. When the representation is irreducible, Serre's conjecture (which is essentially a theorem) predicts the modularity and specifies that possible weights and levels of newforms that give rise to the representation. When the representation is reducible, the set of weights and levels that give rise to it is apparently more complicated to describe. I will discuss the simplest possible examples of this phenomenon, where the representation is about as uncomplicated as possible, the weight is 2 and the level is either a prime number or the product of two distinct primes.
BIO:
Kenneth Ribet studied at Brown University and Harvard University. He received his PhD in 1973 from Harvard, where his advisor was John Tate. After three years of teaching in Princeton and two years of research in Paris, Ribet joined the Berkeley faculty in 1978. He received his department's Distinguished Teaching Award in 1985.
Ribet is known for his work in number theory and algebraic geometry. He played a prominent role in the proof of Fermat's Last Theorem by showing that this statement was a logical consequence of a conjecture about elliptic curves. (Andrew Wiles proved this conjecture in 1995, thereby obtaining Fermat's Last Theorem as a corollary.) Ribet is a member of the scientific advisory board of the Institute for Pure & Applied Mathematics at UCLA and a member of the editorial boards of the following three Springer book series: Graduate Texts in Mathematics, Universitext, Undergraduate Texts in Mathematics. He serves also on the editorial boards of Mathematische Annalen, the Annales de l'Institut Fourier, the Journal of Number Theory and Mathematics Research Letters.
Ribet was elected to the American Academy of Arts and Sciences in 1997 and the National Academy of Sciences in 2000. He was awarded the Fermat Prize in 1989 and received an honorary PhD from Brown University in 1998. Ribet was inducted as a Vigneron d'honneur by the Jurade de Saint Emilion in 1988.


Incentivising Outsourced Computation
Alptekin Küpçü

8/25 1:30pm
ABSTRACT:
We describe different strategies a central authority, the boss, can use to distribute computation to untrusted contractors. Our problem is inspired by volunteer distributed computing projects such as SETI@home, which outsource computation to large numbers of participants. For many tasks, verifying a task's output requires as much work as computing it again; additionally, some tasks may produce certain outputs with greater probability than others. A selfish contractor may try to exploit these factors, by submitting potentially incorrect results and claiming a reward. Further, malicious contractors may respond incorrectly, to cause direct harm or to create additional overhead for result-checking.
We consider the scenario where there is a credit system whereby users can be rewarded for good work and fined for cheating. We show how to set rewards and fines that incentivize proper behavior from rational contractors, and mitigate the damage caused by malicious contractors. We analyze two strategies: random double-checking by the boss, and hiring multiple contractors to perform the same job.
We also present a bounty mechanism when multiple contractors are employed; the key insight is to give a reward to a contractor who catches another worker cheating. Furthermore, if we can assume that at least a small fraction h of the contractors are honest (1% - 10%), then we can provide graceful degradation for the accuracy of the system and the work the boss has to perform. This is much better than the Byzantine approach, which typically assumes h > 60%.
BIO:
Alptekin Küpçü is a Ph.D. candidate in the Brown University Computer Science Department. His research focuses on cryptography and its intersection with security, peer-to-peer networks, and mechanism design. Apart from the featured work, he is developing security solutions for outsourced dynamic storage systems, investigating efficient optimistic fair exchange methods and their limits, and supervising development of an electronic cash library.


How cryptosystems get broken - new side channel attacks on the implementation of cryptography
Adi Shamir

8/27 1:30pm
ABSTRACT:
After 30 years of public research, we currently have an excellent collection of cryptographic schemes which seem to be exceedingly difficult to break via mathematical cryptanalytic techniques. However, their concrete implementations on PC's or smart cards can often be broken via physical side-channel attacks. In this talk I will survey and demonstrate some of the latest attacks which can bypass the security of strong (and even provably unbreakable) cryptosystems in practice.
The talk will be self contained, requiring no prior knowledge of cryptography or cryptanalysis.
BIO:
Adi Shamir has made diverse and influential contributions to cryptography, making and breaking codes. He was a co-inventor of the RSA public key system. He made fundamental cryptanalytic contributions such as Lattice Reduction attacks and Differential attacks. He is well known for theoretical contributions such as IP=PSPACE. Recently he has studied hardware aspects, side channel attacks and new paradigms such as a broadcast encryption, ring signatures and T-functions. Dr Shamir has been awarded numerous prizes including the 2002 ACM Turing Award (along with Rivest and Adleman), Erdos Prize, the Vatican’s PIUS XI Gold Medal and 2008 Israel Prize. He is a faculty at the Mathematics and Computer Science department of Weizmann Institute.


Preliminary Design of Post-Sieving Processing for RSA-768
Peter Montgomery

8/28 3:30pm
ABSTRACT:
The security of the RSA cryptosystem relies on the believed difficulty of factoring large composite integers. Some European sites are attempting to factor RSA-768, a 768-bit challenge number. The best known algorithm is Number Field Sieve, whose current record is 665 bits. Existing software needs upgrades to 64-bit manycore systems. I will describe some proposed algorithmic adjustments as we work to meet this challenge on state-of-the-art hardware.
BIO:
Peter Montgomery is famous among computational number theorists for his work on integer factorization. The inventor of Montgomery multiplication, Peter taught himself algebra in the summer after fifth grade. Peter joined Microsoft Research in 1998, and authored most of the msbignum library used by Vista. Earlier Peter spent 17 years at Unisys. Peter is a Putnam fellow and leads Microsoft Research Problems Group, which attempts to submit solutions to problems in the American Mathematical Monthly.


New algebraic attacks on cryptosystems represented by systems of low degree polynomial equations
Adi Shamir

8/29 1:30pm
ABSTRACT:
In this talk I will describe a new algebraic attack which is very powerful and very general. It can solve large systems of low degree polynomial equations with surprisingly low complexity. For example, solving dense random-looking equations of degree 16 in several thousand variables over GF(2) (which correspond to many types of LFSR-based stream ciphers) can now be practically done in less than 2^{32} complexity by the new technique.


Non-linear functions and Kloosterman sums
Petr Lisonek

9/24 1:30pm
ABSTRACT:
A function defined on GF(q) is called highly non-linear if it is very far from any linear function defined on the same field. One major application of non-linear functions is in Cryptography, where they are used to protect the symmetric (private key) ciphers against certain types of attacks. For example, the S-boxes of the Advanced Encryption Standard (AES) cipher are based on a certain non-linear function. Other application areas include Coding Theory and Quantum Computing.
The Kloosterman sum K(a) is a certain exponential sum defined on GF(q). Kloosterman sums appear in many interesting formulas. An element a in GF(q) such that K(a)=0 is called a zero of the Kloosterman sum. Zeros of Kloosterman sums correspond to one type of monomial bent functions (a class of highly non-linear functions).
When q is a power of 2 or 3, values of the Kloosterman sums can be associated with the number of points on certain elliptic curves defined over GF(q). We will show several applications of this association, including divisibility results for K(a), finding zeros of K(a), and non-existence results for zeros of K(a) in certain subfields of GF(q).
BIO:
Dr. Petr Lisonek is an Associate Professor in the Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada. He obtained his Ph.D. in 1994 at RISC-Linz (Research Institute for Symbolic Computation), J. Kepler University, Linz, Austria. He held Postdoctoral appointments at Technical University of Denmark and at Simon Fraser University, where he has been a faculty member since 2000. His main research interest are algebraic methods in Discrete Mathematics, with applications in Coding Theory, Cryptography and Steganography (information hiding).


Implantable Medical Devices: Security and Privacy for Pervasive, Wireless Healthcare
Kevin Fu

9/29 10:30am
ABSTRACT:
An incredible array of implantable medical devices treat chronic ailments such as cardiac arrhythmia, diabetes, Parkinson's disease, seizures, and even obesity with various combinations of electrical therapy and drug infusion. These devices use tiny embedded computers to control therapies and collect physiological data. To improve patient care and detect early warning signs, implantable medical devices are rapidly embracing wireless communication and Internet connectivity. Implantable cardioverter defibrillators (ICDs) are wirelessly reprogrammable and relay medical telemetry over the Internet via at-home monitors. Such devices will vastly improve care for chronic disease, but will also introduce fundamentally new risks because of global computing infrastructures such as the Internet that are physically infeasible to secure. Thus, new devices must not only prevent accidental malfunctions, but must also prevent *intentional* malfunctions caused by malicious parties lurking on the network.
Our interdisciplinary research team implemented several software radio-based methods that could compromise patient safety and patient privacy (e.g., disclosing patient data or inducing ventricular fibrillation via a wireless command). Addressing these new risks, our zero-power approaches help to mitigate the risk of intentional malfunctions. Attendees will learn about (1) the challenging security and privacy risks that result from the incorporation of wireless communication and Internet connectivity in healthcare; (2) the key factors for balancing medical safety and effectiveness with security and privacy; and (3) three new zero-power defenses based on RF power harvesting that balance security and power consumption to improve patient safety. This line of research is an important step in understanding how to provide better security and privacy as more medical devices rely on wireless communication. Wireless communication has the potential to improve patient care, but researchers have yet to fully understand the effects of wireless communication on security and privacy of pervasive devices. We do not believe that our discovery poses a significant threat today, but we are certain that the risks will grow as the technology develops. This research was carried out at the University of Massachusetts Amherst in collaboration with the University of Washington and the Harvard Medical School.
BIO:
Kevin Fu is an assistant professor in the Department of Computer Science at the University of Massachusetts Amherst, and is the co-director of the Medical Device Security Center and the director of the RFID Consortium on Security and Privacy (RFID CUSP). Kevin investigates the security and privacy of pervasive and invasive computation --- including RFID, implantable medical devices, and file systems. Kevin's contributions include the security analysis of an implantable cardioverter defibrillator, RFID-enabled credit cards, Web authentication, and software updates; the SFS read-only file system for fast integrity-protected content distribution; key regression for efficient decentralized access control of storage; and proxy re-encryption file systems for managing distributed access control.
Kevin received his M.Eng. and Ph.D. in Electrical Engineering and Computer Science at the Massachusetts Institute of Technology in 1999 and 2005 respectively, and his S.B. in Computer Science and Engineering from MIT in 1998. Kevin's research received a number of best paper awards from premiere conferences in computer security and cryptography. His research has appeared in The New York Times and The Wall Street Journal. Kevin also holds a certificate of achievement in artisanal bread making from the French Culinary Institute.



Cryptography: From Theory to Practice
Mihir Bellare

10/6 10:30am
ABSTRACT:
You use cryptography every time you make a credit card-based Internet purchase or use an ATM machine. But what is it? How does it work and how do we know when it is secure? This talk is an introduction to the problems, issues, colorful personalities and advances in this area. We will explain how cryptography is a marriage of mathematics and computer science. We will explain what are proofs of security and their value and limitations in providing security assurance. We will see how gaps between theory and practice are rooted in the culture of the field and how they have been lifted to the point where proven secure schemes are present in Microsoft products. We will present case studies that explain the theory and origins of some cryptographic schemes now in use. We will then discuss some future directions.
BIO:
Mihir Bellare received his Ph.D. at MIT and then worked at IBM Research. He is currently a professor in the computer science department at UCSD. He and his colleague Phillip Rogaway originated practice-oriented provable-security as a way to create practical, high-assurance cryptography. Bellare is a recipient of a RSA conference award in mathematics and a David and Lucille Packard Fellowship in science and engineering. Algorithms that he has coinvented and are now in widespread use include HMAC, OAEP, PSS and DHIES. Webpage: http://www.cs.ucsd.edu/~mihir/


Deniable Authentication
Yevgeniy Dodis

10/9 1:30pm
ABSTRACT:
We revisit the question of deniable cryptographic primitives, where, intuitively, a malicious party observing the interaction, cannot later prove to a third party that the interaction took place. Example include deniable message authentication, key exchange and identification. While these question was heavily studied in the literature, we argue that none of the existing definitions (and solutions) to this question is satisfactory.
We propose the strongest and, arguably, the most natural and intuitive definition of deniability for these tasks: the proposed protocol should be secure in the recently proposed Generalized Universal Composability (GUC) Framework of Canetti, Dodis, Pass and Walfish. Among other things, our definition guarantees on-line deniability and concurrent composition. Quite remarkably, our main result shows that none of the above mentioned tasks (identification, key exchange, authentication) is realizable against adaptive attackers, even in the REGISTERED PUBLIC KEY MODEL (registered PKI), and even if data erasures are allowed. Registered PKI is the strongest setup assumption which is assumed to be "reasonable". Thus, our result explains why all the previous attempts to solve deniability felt short of achieving the strongest form of deniability.
We also show that various slight relaxation of our notion ARE achievable, and discuss implications of our results to the general task of designing deniable protocols.
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.


A Rational Defense Against Concurrent Attacks
Abhi Shelat

10/13 1:30pm
ABSTRACT:
It has been a long standing goal to build more communication-efficient concurrent zero-knowledge protocols. A lower bound by CKPR01 shows that "black-box" constructions of such protocols---i.e., those that are simpler to analyze and implement---must use \omega(log n) rounds of communication.
Prior work has circumvented this lower bound by either
(1) relying on additional trust assumptions [DNS98, DS98, D99, CGGM00]
(2) relaxing the definition of security [P03,PS04,PV08], or
(3) employing more complicated non-blackbox techniques [B01] (and also restricting the number of concurrent sessions).
All three involve sacrifices.
We propose a new way: we study protocols in a model where communicationis costly and players are rational. In this model, we present a concurrent zero-knowledge protocol that requires only a small constant number of rounds in expectation.
Our techniques are inspired by well studied ideas from distributed computation (e.g., Fast Paxos) and recent ideas in cryptographic game theory.
In particular, we design protocols that:
(a) recognize best case situations and optimize for them, and
(b) create incentives for inducing best-case situations.
BIO:
Abhi Shelat completed his Ph.D. at MIT in 2005 under Professor Silvio Micali. He then worked at the IBM Zurich Research Lab as a Research Staff Member until 2007 when he joined the UVa Department of Computer Science as an Assistant Professor. He was awarded the NSF Graduate Research Fellowship while he was a graduate student.
Abhi’s research focuses on the modern study of cryptography. He investigates techniques for facilitating interactions between distrustful entities (e.g., automated tellers, wireless networks, internet banking, satellite radio/TV, etc). He emphasizes rigorous methods in combination with precise yet practical definitions and assumptions. Recent works considers topics such as exploiting imperfect reference strings, efficient access to untrusted shared memory, adaptive oblivious transfer, obfuscation, non-interactive and fair zero-knowledge proofs, collusion-free protocols, digital fingerprinting, and data compression.


Bilinear Complexity of the Multiplication in a Finite Extention of a Finite Field
Robert Rolland

10/15 1:30pm
ABSTRACT:
Let $q=p^r$ be a prime power and $\F_q$ be the finite field with $q$ elements. We study the multiplication of two polynomials in $\F_q [X]$, with degree $\leq n-1$, modulo an irreducible polynomial of degree $n$, namely the multiplication in the finite field $\F_{q^n}$.
We want to find a multiplication algorithm involving two variables in $\F_{q^n}$ minimizing the number of bilinear multiplications (i.e. involving two variables) in $\F_q$. We don't take in account multiplications of a variable in $\F_q$ by a constant in $\F_q$ (However these linear operations have a cost).
It turns out that the number of bilinear operations is related to a tensor expression of the multiplication and that the problem is to find the rank of this tensor.
We will give, using interpolation on algebraic curves over the finite field $\F_q$, a sharp estimate for this bilinear complexity.
BIO:
Robert Rolland was Professor at the Université de la Méditerranée (Marseille - France) and researcher in the laboratory Institut de Mathématiques de Luminy. He is now honorary member of the laboratories ERISC and Institut de Mathématiques de Luminy. Its research domain is algebraic geometry over finite fields and applications.


A Cryptographic Compiler for Information-Flow Security
Cédric Fournet

10/22 1:30pm
ABSTRACT:
   Joint work with Tamara Rezk and Gurvan le Guernic (MSR-INRIA Joint Centre http://msr-inria.inria.fr/projects/sec).
   We relate two notions of security: one simple and abstract, based on information flows in programs, the other more concrete, based on cryptography.
   In language-based security, confidentiality and integrity policies specify the permitted flows of information between parts of a system with different levels of trust. These policies enable a simple treatment of security, but their enforcement is delicate.
   We consider cryptographic enforcement mechanisms for distributed programs with untrusted components. Such programs may represent, for instance, distributed systems connected by some untrusted network. We develop a compiler from a small imperative language with locality and security annotations down to cryptographic implementations in F#. In source programs, security depends on a policy for reading and writing the shared variables. In their implementations, shared memory is unprotected, and security depends instead on encryption and signing.
   We rely on standard primitives and hypotheses for cryptography, stated in terms of probabilistic polynomial-time algorithms and games. Relying on a new type system, we show that our compiler preserves all information-flow properties: an adversary that interacts with the trusted components of our code and entirely controls its untrusted components gains illegal information only with negligible probability.
BIO:
   See http://research.microsoft.com/~fournet.


One Time Password Access to Any Server Without Changing the Server
Cormac Herley and Dinei Florencio

10/29 1:30pm
ABSTRACT:
   This talk introduces a service that allows users one-time password access to any Web account, without any changes to the server, without changing anything on the client, and without storing user credentials in-the-cloud. The user pre-encrypts their password using an assigned set of keys, and these encryptions are sent as one-time passwords to a cell phone or carried. To login, the user enters one of the encryptions as prompted, and the service decrypts before forwarding to the log-in server. Because credentials are not stored, there is no need to authenticate users. Thus, while the user must trust the service, there are no additional passwords to remember. The system requires no server changes, so it can be used on a trust-appropriate basis—the user can login normally from trusted machines, but when roaming use one-time passwords. No installation of any software or alteration of any settings is required at the untrusted machine. The robust reverse proxy architecture of the service means that the user requires only access to the address bar of a browser. The system allows safe access even from keylogger- or spyware-infected machines. We’ve tested on a wide variety of sites (e.g. PayPal, live, yahoo, gmail, facebook, etc) and all major browsers. The service is up and running and attendees can try it for themselves.
BIOS:
   Cormac Herley is a Principal Researcher at Microsoft Research, Redmond, where he has been since 1999. He has published in the areas of Signal and Image Processing, Multimedia, Information Retrieval, Networking, and Computer and Web Security. He received the PhD from Columbia University, the MSEE from Georgia Tech, and the BE(Elect.) from University College Cork, Ireland. Before Microsoft he was at Hewlett Packard Labs for five years. He is a former editor of the IEEE Transactions on Information Theory, a former adjunct at UC Berkeley and is inventor of 60 or so patents.
   Dinei Florencio received the B.S. and M.S. from University of Brasília (Brazil), and the Ph.D. from Georgia Tech, all in Electrical Engineering. He is a researcher in the signal processing group at Microsoft Research since 1999. From 1996 to 1999, he was a member of the research staff at the David Sarnoff Research Center. He was also a co-op student with AT&T Human Interface Lab (now part of NCR) from 1994 to 1996, and a Summer intern at the (now defunct) Interval Research in 1994. He is a senior member of the IEEE, and reviewer for the IEEE transactions on Speech, on Signal Processing, on image Processing, and for the IEEE signal processing letters. He has published over 25 referred papers, and 17 granted US patents (with another 13 currently pending), and received the 1998 Sarnoff Achievement Award.


Special vs Random Curves: Could the Conventional Wisdom Be Wrong?
Neal Koblitz

11/12 1:30pm
ABSTRACT:
   The conventional wisdom in cryptography is that for greatest security one should choose parameters as randomly as possible. In particular, in elliptic and hyperelliptic curve cryptography this means making random choices of the coefficients of the defining equation. One can often achieve greater efficiency by working with special curves, but that should be done only if one is willing to risk a possible lowering of security. Namely, the extra structure that allows for greater efficiency could also some day lead to specialized attacks that would not apply to random curves.
   This way of thinking is reasonable, and it is uncontroversial. However, some recent work opens up the possibility that it might sometimes be wrong.
   This talk is based on a joint paper with Alfred Menezes and Ann Hibner Koblitz.
BIO:
   Neal Koblitz received his Ph.D. in mathematics at Princeton in 1974, and since 1979 he has been at the University of Washington. He has been working in cryptography since 1985, when he and Victor Miller independently proposed elliptic curve cryptography. He has written six books, of which two are on cryptography and one (whose title "Random Curves" has nothing to do with the topic of the above talk) consists of autobiographical memoirs. In recent years he has been more successful at making enemies than friends, especially after publication of "The Uneasy Relationship Between Mathematics and Cryptography" in the AMS Notices last year.


Simulation-Based Concurrent Non-Malleable Commitments and Decommitments
Ivan Visconti

11/18 1:30pm
ABSTRACT:
    In this work we consider commitment schemes that are secure against concurrent man-in-the-middle (cMiM) attacks. Under such attacks, two possible notions of security for commitment schemes have been proposed in the literature: concurrent non-malleability with respect to commitment and concurrent non-malleability with respect to decommitment (i.e., opening).
   After the original notion of non-malleability introduced by [Dolev, Dwork and Naor STOC 91] that is based on the independence of the committed and decommitted message, a new and stronger simulation-based notion of non-malleability has been given in [Pass and Rosen STOC 05] by requiring that for any man-in-the-middle adversary there is a stand-alone adversary that succeeds with the same probability. When commitment schemes are used as subprotocols (which is often the case) the simulation-based notion is much more powerful and simplifies the task of proving the security of the larger protocols.
   Under this stronger security notion, a constant-round commitment scheme that is concurrent non-malleable only with respect to commitment has been given in [Pass and Rosen FOCS 05] for the plain model, thus leaving as an open problem the construction of constant-round commitments that are concurrent non-malleable with respect to decommitment. In other words, in [Pass and Rosen FOCS 05] security against adversaries that mount concurrent man-in-the-middle attacks is guaranteed only during the commitment phase (under the simulation-based notion of non-malleability).
   The main result of this work is a commitment scheme that simulation-based concurrent non-malleable with respect to both commitment and decommitment. This property protects against cMiM attacks mounted during both commitments and decommitments which is a crucial security requirement in several applications, as in some digital auctions, in which players have to perform both commitments and decommitments. Our scheme uses a constant number of rounds of interaction in the plain model and is the first scheme that enjoys all these properties under the simulation-based definitions of [Pass and Rosen FOCS 05].
   We stress that, exactly as in [Pass and Rosen FOCS 05], we assume that commitments and decommitments are performed in two distinct phases that do not overlap in time.
   Joint work with Rafail Ostrovsky (UCLA) and Giuseppe Persiano (University of Salerno).
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). In summer 2002, he visited the IBM Zurich Research Laboratory.


Computing class polynomials with the Chinese Remainder Theorem
Drew Sutherland

11/19 1:30pm
ABSTRACT:
   Class polynomials play a key role in the CM-method for constructing elliptic curves with known order. This has many applications to cryptography and is the primary means of obtaining pairing-friendly curves. The CM-method is unfortunately constrained by practical limits on the size of the CM discriminant, with |D| < 10^10 an accepted upper bound.
   I will present a new algorithm, based on the CRT-approach to computing Hilbert class polynomials [Belding-Broker-Enge-Lauter 2008], one that is faster than existing methods and able to handle much larger discriminants. For suitable D, this algorithm can also compute class polynomials for more favorable class invariants (derived from those of Weber and Ramanujan), yielding a further improvement in the constant factors.
   These results have been used to construct many pairing-friendly curves with large CM-discriminant, including examples with |D| > 10^14.
BIO:
   Andrew Sutherland is a Research Scientist in the mathematics department at MIT, with a passion for computational number theory. His work includes results for elliptic and hyperelliptic curves, ideal class groups, and generic group algorithms. He received his PhD from MIT in 2007, following a successful career as an entrepreneur in the software industry.



Fair Exchange with a Distributed Offline TTP
Anna Lysyanskaya

12/10 1:30pm
ABSTRACT:
   Fair exchange is one of the most fundamental problems in secure distributed computation. Alice has something that Bob wants, and Bob has something that Alice wants. A fair exchange protocol would guarantee that, even if one of them maliciously deviates from the protocol, either both of them get the desired content, or neither of them do. It is known that no two-party protocol can guarantee fairness; therefore the presence of a trusted arbiter is necessary. In optimistic fair exchange, the arbiter only gets involved in case of faults.
   A very natural question is how to achieve fairness in the absence of a single trusted arbiter; for example, what if we have n arbiters of whom at most k may be malicious? It is clear that this can be achieved with secure multi-party computation using Omega(n^2) communication, but can we do better than that?
   Inspired by state-of-the-art optimistic fair exchange protocols with a single arbiter, we define a general class of optimistic fair exchange protocols with multiple arbiters, called "distributed arbiter fair exchange" (DAFE) protocols. Informally, in a DAFE protocol, if Alice fails to send a correctly formed message to Bob, Bob must contact some subset of the arbiters and get correctly formed responses from them. In a DAFE protocol the arbiters need not talk to each other, but only to Alice and Bob. We prove that no DAFE protocol can exist. However, our impossibility results can be overcome in the timing model (where all participants have access to a clock and all clocks are loosely synchronized) and also in case the arbiters can communicated through Alice and Bob.
   Joint work with Alp Kupcu.
BIO:
Anna Lysyanskaya is an Associate Professor of Computer Science at Brown University. She received an A.B. in Computer Science and Mathematics from Smith College in 1997, and a Ph.D. in Computer Science and Electrical Engineering from MIT in 2002. She is a recipient of an NSF CAREER award and a Sloan Foundation fellowship. Her research interests are in cryptography, theoretical computer science, and computer security.



Singular Moduli
Eyal Goren

12/15 1:30pm
ABSTRACT:
   The values of the elliptic modular function $j$ at imaginary quadratic numbers $\tau$ are called singular moduli. They are of fundamental importance in the study of elliptic curves and in algebraic number theory, including the study of elliptic curves over finite fields.
   The theorem of Gross and Zagier has provided striking congruences satisfied by these numbers. Various aspects of this theorem were generalized in recent years by Jan Bruinier and Tonghai Yang and by Kristin Lauter and the speaker. These may be viewed as concerning the theory of curves of genus 2 and their singular moduli that are obtained by evaluating the Igusa invariants at certain 2x2 complex matrices $\tau$. I will describe some of the recent ideas introduced in this area and, time allowing, describe some current projects.
BIO:
   Eyal Goren is an associate professor of mathematics at McGill University. His area of expertise is arithmetic geometry and in particular modular forms and moduli spaces of abelian varieties and their various applications to class field theory, p-adic modular forms, Galois representations and expander graphs. See
http://www.math.mcgill.ca/goren/ for publications, students and other information.



Return-Oriented Programming: Exploits Without Code Injection
Hovav
Shacham
12/16 1:30pm
ABSTRACT:
   We describe return-oriented programming, a generalization of return-into-libc that allows an attacker to undertake arbitrary, Turing-complete computation without injecting code.
   New computations are constructed by linking together code snippets that end with a "ret" instruction. The ret instructions allow an attacker who controls the stack to chain instruction sequences together. Because the executed code is stored in memory marked executable, W^X and DEP will not prevent it from running.
   W^X and DEP, along with many other security systems, make the assumption that preventing the introduction of malicious code is sufficient to prevent the introduction of malicious computation. With the return-oriented computing approach, this assumption is false: subverting control flow on the stack is sufficient to construct arbitrary computation from "known-good" code.
   On the x86 one can obtain useful instruction sequences by jumping into the middle of intended instructions, but return-oriented programming is possible even on RISC platforms that are very different from the x86.
   Joint work with By Erik Buchanan, Ryan Roemer, and Stefan Savage (UC San Diego).
BIO:

   Hovav Shacham is an Assistant Professor in the department of Computer Science & Engineering at the University of California, San Diego.
   Dr. Shacham received his Ph.D. in computer science in 2005 from Stanford University, where he had also earned, in 2000, an A.B. in English. In 2006 and 2007, he was a Koshland Scholars Program postdoctoral fellow at the Weizmann Institute of Science.
   Dr. Shacham's research interests are in applied cryptography, systems security, and tech policy.
   He is one of the pioneers in using pairings -- computable bilinear maps over certain elliptic curves -- to construct cryptographic systems. His thesis, "New Paradigms in Signature Schemes," was runner up for the Stanford Department of Computer Science's Arthur L. Samuel Thesis Award, and was nominated for the ACM Doctoral Dissertation Competition. At the Weizmann, Shacham taught a survey on pairings in cryptography, one of the first such courses to be offered.
   Dr. Shacham is the inventor of "return-oriented programming," an attack against the class of protective measures that attempt to prevent malicious computation by distinguishing between "good code" present in the system and "bad code" introduced by the attacker. With return-oriented programming, the attacker combines short snippets of preexisting good code into gadgets from which he can synthesize arbitrary functionality without introducing any new code. One defensive measure threatened is Data Execution Prevention (DEP), implemented in Windows Vista and supported by changes to Intel processors. DEP makes it impossible for an attacker to execute code injected into a compromised process; but in the face of return-oriented programming it provides no security benefits.
   In 2007, Dr. Shacham participated in California Secretary of State Debra Bowen's "Top-to-Bottom" of the voting machines certified for use in California. He was a member of the team reviewing Hart InterCivic source code; the report he co-authored was cited by the Secretary in her decision to withdraw approval from Hart voting machines.



Compact Proofs of Retrievability
Hovav Shacham

12/17 1:30pm
ABSTRACT:
   In a proof-of-retrievability system, a data storage center must prove to a verifier that he is actually storing all of a client's data. The central challenge is to build systems that are both efficient and provably secure -- that is, it should be possible to extract the client's data from any prover that passes a verification check.
   We present the first proof-of-retrievability schemes with full proofs of security against arbitrary adversaries in the strongest model, that of Juels and Kaliski. Our first scheme, built from BLS signatures and secure in the random oracle model, has the shortest query and response of any proof-of-retrievability with public verifiability. Our second scheme, which builds elegantly on pseudorandom functions (PRFs) and is secure in the standard model, has the shortest response of any proof-of-retrievability scheme with private verifiability (but a longer query). Both schemes rely on homomorphic properties to aggregate a proof into one small authenticator value.
   Joint work with Brent Waters (UT Austin).
BIO:
see above


Intersection and a conjecture of Lauter
Tonghai Yang

1/14 1:30pm
ABSTRACT:
   Motivated by her joint work with H. Cohn on genus two curve crypotosystem, Lauter gave a very inspiring conjecture on the CM value of Igusa invariants. They need to compute these values to construct `good' genus two curves. This conjecture led to study of arithmetic intersection on an arithmetic 3-fold (Hilbert modular surface). Recently, I proved an arithmetic intersection formula, which leads to proof of Lauter's conjecture. The formula also leads to the first non-abelian generalization of the celebrated Chowla-Selberg formula.
BIO:
   Dr. Tonghai Yang is a professor of mathematics at the University of Wisconsin at Madison. He graduated in 1995 from the University of Maryland and had his postdoc experience at the Institute for Advanced Study at Princeton in 1995-96, and at the University of Michigan as an Hildebrandt research assistant professor in 1996-98. He became a tenure-track assistant professor at SUNY at Stony Brook in 1998 and was awarded an American Mathematical Society Centenial Fellowship in 1999 to visit Harvard University. He moved to the University of Wisconsin at Madison in 2000 and stayed there ever since. He published about 30 research papers and one joint research book with S. Kudla and M. Rapoport at the prestigious `Annals of Mathematics Studies' series.
   Dr. Yang is an editor of the` Quarterly Journal of Pure and Applied Mathematics' and is on the advisory board of `Abhandlungen aus dem mathematischen Seminar der Universitaet Hamburg'.
   Dr. Yang is the founder of the public charity Hometown Education Foundation.



The Sage Mathematical Software Project
William Stein

2/3 10:30am
ABSTRACT:
   Sage is a large mathematical software project based at the University of Washington that is funded by Microsoft, the National Science Foundation, and other organizations. The longterm goal of Sage is provide a viable free alternative to Matlab, Maple, Mathematica, and Magma. In this talk I will answer the question "what does Sage do right now?" If you're a Matlab, Maple, Mathematica, or Magma user, you won't want to miss this talk.
http://sagemath.org
BIO:
   William Stein is an Associate Professor of Mathematics at the University of Washington. He is also the author of two books on number theory, many papers, and the lead developer of the open source software project, Sage.



Buchmann's algorithms and Arakelov class groups
Rene Schoof

2/19 10:30am
ABSTRACT:
   Class groups have been proposed as the basis for public key cryptosystems. A natural setting for Buchmann's algorithm for computing class groups and unit groups of number fields, is provided by Arakelov theory. We take this point of view in order to explain the `scanning algorithm', which is an alternative to another algorithm due to Buchmann for computing class groups.
BIO:
   Rene Schoof, is a professor at the university of Rome "Tor Vergata". He is working in number theory, computational aspects as well as arithmetical geometry aspects. Schoof’s algorithm was the first polynomial time algorithm for counting points on elliptic curves over finite fields, which are now widely used in cryptography. He is the author of a book on Catalan's conjecture.



Abelian surfaces with a given number of points
Peter Stevenhagen

3/10 1:30pm
ABSTRACT:
   This is a report on joint work with Everett Howe and Kristin Lauter.
   I will discuss the genus 2 analogue of the problem of efficiently constructing an elliptic curve over a finite field with a prescribed number N of points. If N is provided with its prime factorization, the elliptic construction I gave with Broker is heuristically polynomial time outside a zero density subset of input values N. I will explain why the analogous construction to obtain abelian surfaces of given order N is intrinsically exponential.
BIO:
   Peter Stevenhagen is professor of mathematics at the Universiteit Leiden. His research concerns problems and algorithms in algebraic number theory. He is proud to be advisor of both a postdoc and an intern at Microsoft Research.



Genus-2 curves with a given number of points
Everett Howe

3/10 3:30pm
ABSTRACT:
   This is a report on joint work with Kristin Lauter and Peter Stevenhagen.
   Broker and Stevenhagen have shown that in practice it is not hard to produce an elliptic curve (over some finite field) with a given number N of points, provided that the factorization of N is known. In his talk this week, Stevenhagen will show that the natural generalization of this method to produce genus-2 curves with a given number of points on their Jacobian is an exponential algorithm.
   I will consider the related problem of constructing a genus-2 curve over some finite field such that the curve itself has a given number N of points. The idea of "explicit gluings" of pairs of elliptic curves leads to a solution for most values of N; I will discuss this, and other, applications of explicit gluings.
BIO:
   Everett Howe has worked at the Center for Communications Research in San Diego, California, since 1996. His published research is mainly concerned with problems involving curves and Jacobians over finite fields and number fields. He is proud to be a coauthor of the work that produces the top hit when one Googles "worst limerick in the world".



Advances in the CM method for elliptic curves
Francois Morain

4/22 1:30pm
ABSTRACT:
   The complex multiplication method (CM method) builds an algebraic curve over a given finite field GF(q) and having an easily computable cardinality. Used at first for elliptic curves, this method is one of the building blocks of the ECPP algorithm that proves the primality of large integers, and it appeared interesting for other applications, the most recent of which being the construction of pairing friendly curves. The aim of the talk is to recall the method, give some applications, and survey recent advances on several parts of the method, due to various authors, concentrating on elliptic curves. This includes class invariant computations, and the potential use of the Montgomery/Edwards parametrization of elliptic curves.
BIO:
   F. Morain is Professor at École polytechnique in France, and head of the Project-Team TANC (Algorithmic Number Theory for Cryptology) of INRIA Saclay Ile de France. His main interests involve the application of elliptic curves to various problems in number theory, including primality proving of large integers (ECPP and fastECPP), and cardinality computations. He holds two records: the largest ordinary number proven prime (> 20,000 decimal digits) and the computation of cardinalities of elliptic curves over large finite fields (2,500 decimal digits), both obtained using distributed computations.



(4,4)-split Jacobians of curves of genus 2
Nils Bruin

4/24 3:30pm
ABSTRACT:
    Curves of genus 2 have an associated abelian surface, their jacobian. One can classify genus 2 curves according to special properties of their jacobians. For instance, a jacobian can be split: isogenous to a product of elliptic curves. There are several ways in which jacobians can be split. In this talk we will give a precise description of one of them. Having such a precise description helps in understanding various number-theoretic and cryptographic constructions. This is joint work with my student Kevin Doerksen.
BIO:
   Nils Bruin is a professor in Mathematics at Simon Fraser University (BC, Canada). His work revolves around developing explicit methods to determine the set of rational solutions to polynomial equations. Many of these methods have been implemented in the computer algebra system MAGMA.
Supersingular abelian varieties and modular forms
Tomoyoshi Ibukiyama

6/3 1:30pm
ABSTRACT:
    We give a survey on old and new results on relations between geometric invariants of principally polarized supersingular abelian varieties and arithmetic invariants of quaternion hermitian forms (such as the numbers of polarizations and irreducible components of the supersingular locus, the field of definition, existence of curves with many rational points, class numbers, type numbers, and Hecke operators). Conjecturally quaternion hermitian forms are related with Siegel modular forms by Langlands philosophy. So we also see where Siegel modular forms appear in the above theory.
BIO:
   Born in 1948. Education: Undergraduate and Graduate course in the University of Tokyo under guidance of Professor Yasutaka Ihara. Employment: Assistant Prof. of Univ. Tokyo, Associate Prof. of Kyushu Univ., then Professor of Osaka Univ. until now. Mathematics: My Speciality is Number Theory, in particular Siegel modular forms, quadratic forms, various related zeta functions, and explicit calculation of all of them and their invariants.



Modern Computer Arithmetic
Paul Zimmermann

6/12 10:30am
ABSTRACT:
    This talk is about a book in progress with Richard Brent (ANU, Canberra, Australia). "Modern Computer Arithmetic" collects in the same document all state-of-the-art algorithms in multiple precision arithmetic (integers, integers modulo n, floating-point numbers). The best current reference on that topic is volume 2 from Knuth's "The art of computer programming", which misses some new important algorithms (divide and conquer division, other variants of FFT multiplication, floating-point algorithms, ...) Our aim is to give detailed algorithms: (i) for all operations (not just multiplication as many text books), (ii) for all size ranges (not just schoolbook methods or FFT-based methods), (iii) and including all details (for example how to properly deal with carries for integer algorithms, or a rigorous analysis of roundoff errors for floating-point algorithms). The talk will say a few words about the history of this book, and then will focus on a few algorithms from the book, some of which are not well known. Url of the book: http://www.loria.fr/~zimmerma/mca/pub226.html
BIO:
    Paul Zimmermann did his PhD in 1991 on the automatic average case analysis of algorithms under the supervision of Ph. Flajolet. He then worked on the random generation of computer algebra structures, and starting from the end of the 90s his interests moved to arbitrary precision floating- point computations and computational number theory. He is the author or co-author of several computer packages, in particular the MPFR library for computing with huge floating-point numbers with correct rounding, and the GMP-ECM program for factoring integers with the Elliptic Curve Method.



SANDstorm, Elliptic Curves, and a Bit of Fun
Rich Schroeppel

7/16 10:30am
ABSTRACT:
    I'll begin by describing SANDstorm, the Sandia entry in the NIST Hash Function competition. Next, I borrow an idea of Peter Montgomery's to speed up elliptic curve calculations (Affine Strikes Back!). Finally, I'll offer a frisson of lighter math fare.
BIO:
    Rich Schroeppel works as a crypto-mathematician at Sandia National Laboratories, and moderates the Math-Fun email list. He works with algorithms, developing an early factoring method, and the Hasty Pudding Cipher. He's a co-inventor of point-halving for elliptic curves.



Elliptic Curve Isogenies: A Computational Approach
Dan Shumow

7/16 3:30pm
ABSTRACT:
    Isogenies are maps that preserve the structure of elliptic curves, and as such are an important mathematical tool. Unsurprisingly, this once almost entirely theoretical tool has found uses in elliptic curve cryptography. These applications include the Schoof-Elkies-Atkins point counting algorithm, uses in the MOV attack and pairing based cryptography, constructing provably secure hash functions and random number generators (a result from the MSR Crypto team), and also as a tool for analyzing the complexity of reducing the discrete log problem between elliptic curves (also a result by MSR cryptography researchers). With these cryptographic applications as a motivation, I set out to study some of the computational aspects of isogenies. This talk presents some algorithms for computational aspects of Isogenies, and some background for understanding these results. I’ll also show how to compute isogenies with Sage (functionality that was added as part of this project.)
BIO:
    I am presently an intern on the Crypto Tools team, last summer I was an intern on the MSR Crypto team. I am just finishing up my MS in mathematics at the University of Washington. Prior to attending the UW, I was a developer on the Windows crypto team. I got my BS in Mathematics and Computer Science from the University of Wisconsin in 2004.



CCCP: Secure remote storage for computational RFIDs
Mastooreh Salajegheh

7/22 10:30am
ABSTRACT:
    Passive RFID tags harvest their operating energy from an interrogating reader, but constant energy shortfalls severely limit their computational and storage capabilities. We propose Cryptographic Computational Continuation Passing (CCCP), a mechanism that amplifies programmable passive RFID tags’ capabilities by exploiting an often overlooked, plentiful resource: low-power radio communication. While radio communication is more energy intensive than flash memory writes in many embedded devices, we show that the reverse is true for passive RFID tags. A tag can use CCCP to checkpoint its computational state to an untrusted reader using less energy than an equivalent flash write, thereby allowing it to devote a greater share of its energy to computation. Security is the major challenge in such remote checkpointing. Using scant and fleeting energy, a tag must enforce confidentiality, authenticity, integrity, and data freshness while communicating with potentially untrustworthy infrastructure. Our contribution synthesizes well known cryptographic and low-power techniques with a novel flash memory storage strategy, resulting in a secure remote storage facility for an emerging class of devices. Our evaluation of CCCP consists of energy measurements of a prototype implementation on the batteryless, MSP430-based WISP platform. Our experiments show that—despite cryptographic overhead— remote checkpointing consumes less energy than checkpointing to flash for data sizes above roughly 64 bytes. CCCP enables secure and flexible remote storage that would otherwise outstrip batteryless RFID tags’ resources. This work will appear at USENIX Security 2009. Paper: http://www.cs.umass.edu/~negin/files/salajegheh-CCCP-usenix09.pdf
BIO:
   Mastooreh Salajegheh is a PhD student in the Computer Science Department of the University of Massachusetts Amherst. Her research interest lies in analyzing/providing security in the resource constrained devices such as RFIDs, implantable medical devices, wireless sensor nodes and mobile phones. Mastooreh is a member of RFID CUSP (Consortium for Security and Privacy) and works under the supervision of Professor Kevin Fu. She received her Master in information networking from Carnegie Mellon University. http://www.cs.umass.edu/~negin



Public Key Cryptosystems: Stronger Security from General Assumptions
Tal Malkin

8/11 1:30pm
ABSTRACT:
    Public key encryption (PKE) allows parties that had never met in advance to communicate over an unsafe channel. The notion was conceived in the 1970s, followed by the discovery that one could provide formal definitions of security for this and other cryptographic problems, and that such definitions were achievable by assuming the hardness of some computational problem (e.g., factoring large numbers). For PKE, the most basic security definition -- semantic security -- guarantees privacy, namely that it is infeasible to learn anything about the plaintext from its encryption. However, as cryptographic applications grew more sophisticated, this level of security is often not sufficient, since it does not protect against active attacks arising in networked environments.
   In this talk I will review some of my work aimed at achieving stronger security notions for public key encryption, including protections against adaptive corruptions, man-in-the-middle attacks (non-malleability), chosen ciphertext security, and, if time allows, tampering attacks. The emphasis of this line of work is on achieving the stronger notion from as general an assumption as possible (e.g., directly from semantically secure PKE), as well as achieving a black box construction, namely using the underlying scheme as a subroutine, without assuming it has any special structure or algebraic properties. This allows for more efficient cryptosystems that can be instantiated with a larger set of assumptions.
   Based on several joint works with different coauthors. The main part of the talk will be based on joint works with Seung Geol Choi, Dana Dachman-Soled, and Hoeteck Wee.
BIO:
   Tal Malkin is an assistant professor of Computer Science at Columbia University, where she directs the cryptography lab. She received her Ph.D. in Computer Science from the Massachusetts Institute of Technology in 2000, and joined Columbia after three years as a research scientist in the Secure Systems Research Department at AT&T Shannon Laboratory. Her research interests are in cryptography, security, complexity theory, and related areas. She has served on program committees and steering committees for over a dozen international conferences on cryptography, theoretical computer science, and security, she chaired the CT-RSA conference, and is on the editorial board for the Theory of Computing Journal. Prof. Malkin is the recipient an NSF Faculty Early Career Development award, an IBM faculty partnership award, and a research fellowship of the Columbia University Diversity Initiative. Her research is primarily funded by NSF, but she has also received research grants from NSA, NYSIA, IARPA, and Mitsubishi research lab.



Pairing-based Non-interactive Zero-Knowledge Proofs
Jens Groth

8/26 1:30pm
ABSTRACT:
    Non-interactive zero-knowledge proofs make it possible to prove the truth of a statement without revealing any other information. They have been used widely in the theory of cryptography, but due to efficiency problems have not yet found many practical applications. In this talk, we will cover recent pairing-based constructions of non-interactive zero-knowledge proofs that yield the necessary efficiency for practical applications as well as the possibility to have perfect and everlasting privacy.
BIO:
   Dr. Jens Groth received his PhD in Computer Science from Aarhus University. He went on to UCLA, where he received the 2007 Chancellor's Award for Postdoctoral Research. Currently, he is an Assistant Professor in the Computer Science Department of University College London.
   Dr. Groth is interested in both theoretical cryptography as well as practical applications of cryptographic techniques. His research has included areas such as electronic voting, anonymization, advanced digital signatures, public-key encryption and zero-knowledge proofs.



Position-based Cryptography
Nishanth Chandran

9/28 10:30am
ABSTRACT:
    We consider what constitutes identities in cryptography. Typical examples include your name and your social-security number, or your fingerprint/iris-scan, or your address, or your (non-revoked) public-key coming from some trusted public-key infrastructure. In many situations, however, where you are defines your identity. For example, we know the role of a bank-teller behind a bullet-proof bank window not because she shows us her credentials but by merely knowing her location. In this paper, we initiate the study of cryptographic protocols where the identity (or other credentials and inputs) of a party are 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.
   Based on joint work with Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky.
BIO:
   Nishanth Chandran is a doctorate student at UCLA working with Prof. Rafail Ostrovsky and Prof. Amit Sahai. His research interests are cryptography, security and theory in general. He has published several papers in leading conferences such as 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 obtained a Bachelors in Computer Science and Engineering from Anna University, India in 2005 and a Masters in Computer Science from UCLA in 2007.



Exploring Information Leakage in Third-Party Compute Clouds
Thomas Ristenpart

11/4 10:30am
ABSTRACT:
    Third-party cloud computing represents the promise of outsourcing as applied to computation. Services, such as Microsoft's Azure and Amazon's EC2, allow users to instantiate virtual machines (VMs) on demand and thus purchase precisely the capacity they require when they require it. In turn, the use of virtualization allows third-party cloud providers to maximize the utilization of their sunk capital costs by multiplexing many customer VMs across a shared physical infrastructure. However, we'll see how this approach can also introduce new vulnerabilities. Using the Amazon EC2 service as a case study, we show that it is possible to map the internal cloud infrastructure, identify where a particular target VM is likely to reside, and then instantiate new VMs until one is placed co-resident with the target. We explore how such placement can then be used to mount cross-VM side-channel attacks to extract information from a target VM on the same machine.
   This talk covers joint work with Stefan Savage, Hovav Shacham and Eran Tromer
BIO:
   Thomas Ristenpart is a PhD student at the University of California, San Diego. His research spans a wide range of computer security topics, including threat assessment in new technologies such as cloud computing, privacy issues of Internet-based device tracking, and the design of theoretically-sound cryptography that meets the requirements of practical use. His work has been featured in the New York Times, MIT Technology Review, ABC News, U.S. News and World Report, PC Magazine, and others. Before coming to UC San Diego, he completed his masters degree at the University of California, Davis.



How can cryptographic protocols serve the real world?--the case of privacy enhanced authentication--group signatures
Kazue Sako

11/4 1:30pm
ABSTRACT:
   In this talk, possible applications of group signatures is discussed. Group signature scheme is a digital signature scheme that has two-levels of verification. The first level is a typical verification of a digital signature scheme, that is, to verify who signed which message. It has been pointed out that in the ordinary digital signature scheme, the property that anyone can verify the signature threatens privacy of the signer. In group signature schemes, the first level is restricted to authorized entity. On the other hand, the second level of verification is open to public. In the second level, verifier can verify that the message was signed by someone who has privilege to sign, but the signer is not identified. Thus group signature scheme is thus regarded as privacy enhanced technology in authenticating messages and entities.
BIO:
   Kazue Sako is a research fellow at NEC in Tokyo. Her principal research interests are in pragmatic cryptographic protocols such as electronic voting, auctions, and lotteries. Kazue has served on numerous program committees for Crypto, Eurocrypt, Asiacrypt, Financial Cryptography, PKC, and ACMCCS and was an associate editor of Journal of Cryptology until March 2009. She is now editing an ISO standard document on relatively anonymous authentication at ISO/IEC JTC1 SC27 WG5.



Key Recovery Attacks of Practical Complexity on AES Variants With Up To 10 Rounds
Orr
Dunkelman
12/1 10:30am
ABSTRACT:
    AES is the best known and most widely used block cipher. Its three versions (AES-128, AES-192, and AES-256) differ in their key sizes (128 bits, 192 bits and 256 bits) and in their number of rounds (10, 12, and 14, respectively). In the case of AES-128, there is no known attack which is faster than the 2^{128} complexity of exhaustive search. However, AES-192 and AES-256 were recently shown to be breakable by attacks which require 2^{176} and 2^{100} time, respectively. While these complexities are much faster than exhaustive search, they are completely non-practical, and do not seem to pose any real threat to the security of AES-based systems. In this talk we describe several attacks which can break with practical complexity variants of AES-256 whose number of rounds are comparable to that of AES-128. One of our attacks uses only two related keys and 2^{39} time to recover the complete 256-bit key of a 9-round version of AES-256 (the best previous attack on this variant required 4 related keys and 2^{120} time). Another attack can break a 10 round version of AES-256 in 2^{45} time, but it uses a stronger type of related subkey attack (the best previous attack on this variant required 64 related keys by these attacks, the fact that their hybrid (which combines the smaller number of rounds from AES-128 along with the larger key size from AES-256) can be broken with such a low complexity raises serious concern about the remaining safety margin offered by the AES family of cryptosystems. This is joint work with Alex Biryukov, Nathan Keller, Dmitry Khovratovich, and Adi Shamir.
BIO:
    Orr Dunkelman has received his Ph.D. in computer sceince from the Technion, Israel institute of technology, where he did his studies under Prof. Biham. Orr is the author of more than 40 international research papers in cryptography, and specificially, in cryptanalysis of symmetric key primitives. Orr has served as the program chair of the top venue for symmetric key cryptography, FSE 2009, and has served in committees of almost 30 international conferences. Orr is well known for his attacks on widely deployed ciphers, such as AES, A5/1 (used in GSM communications), KASUMI (used in the 3GPP communication protocols), IDEA (used in PGP), keeloq (used in cars as an anti-theft mechanism), etc. Finally, Orr is co-designer of the SHAvite-3 hash function that was selected to the second round of the SHA-3 competition held by NIST.


HAIL (High-Availability and Integrity Layer) for Cloud Storage
Alina Oprea

12/2 3:30pm
ABSTRACT:
    Cloud computing for enterprises and consumers alike relies increasingly on remote, geographically distributed storage platforms. Remote storage services pose distinct challenges, including heterogeneous quality, single points for massive failure and cyber-attacks, and lack of easy inspection of hardware and administrators. We meet these challenges by designing HAIL (High-Availability and Integrity Layer), a reliable and cost-effective distributed cloud storage architecture built on top of inexpensive cloud storage services. HAIL provides its clients assurance of data availability through a cryptographic protocol called "proofs of retrievability". Proofs of file availability are efficiently computable by providers and highly compact, typically tens or hundreds of bytes, irrespective of file size. HAIL is robust against an active, mobile adversary, one that may progressively corrupt the full set of providers. We propose a strong, formal adversarial model for HAIL, and rigorous analysis and parameter choices. In this talk, we discuss the HAIL architecture and some of the technical challenges we encountered in designing HAIL.
BIO:
    Alina Oprea is a Principal Research Scientist at RSA Laboratories, the security division of EMC. Alina's research interests span multiple areas in computer security including storage security, applied cryptography, network security and security in distributed systems. Alina holds a B.S. degree in Mathematics and Computer Science from University of Bucharest, Romania, and has obtained a Ph.D. in Computer Science from Carnegie Mellon University in May 2007.



Multiparty Computation for Dishonest Majority: from Passive to Active Security at Low Cost
Claudio Orlandi

2/3 3:30pm
ABSTRACT:
    Multiparty computation protocols have been known for more than twenty years now, but due to their lack of efficiency their use is still limited in real-world applications. In this talk we present some recent developments in the area of efficient two and multi party computation aimed to fill the gap between theory and practice. We propose a new protocol to securely evaluate reactive arithmetic circuits, that offers security against an active adversary in the universally composable security framework. Instead of the "do-and-compile" approach (where the parties use zero-knowledge proofs to show that they are following the protocol) our key ingredient is an efficient version of the "cut-and-choose" technique, that allow us to achieve active security for just a (small) constant amount of work more than for passive security.
BIO:
    Claudio Orlandi is a PhD student from University of Aarhus, Denmark, under the supervision of Ivan Damgård and Jesper Nielsen. His research interests span in the area of theory and practice of multiparty computation, efficient cryptographic protocols design and foundations of cryptography.



Choosing curves, coordinates and algorithms for computing cryptographic pairings
Michael Naehrig

3/2 10:30am
ABSTRACT:
    For almost a decade now, pairings are used in cryptographic protocols that provide special functionality. In the meantime, many improvements to Miller's algorithm for computing pairings on elliptic curves have led to remarkable increase in the efficiency of such protocols.
    In this talk, we will discuss the options for choosing pairing-friendly elliptic curves, corresponding coordinate systems and algorithms for implementing cryptographic pairings efficiently. We include recent developments like pairings on Edwards curves, new explicit formulas for pairing functions on curves with high degree twists and a possible revival of affine coordinates in pairing computation.
BIO:
    Michael Naehrig is a Post Doc Researcher in the Cryptography Group at MSR Redmond. He conducted his undergraduate studies in Mathematics at RWTH Aachen University, Germany, and received his Ph.D. from Eindhoven University of Technology, The Netherlands, under the supervision of Tanja Lange. His main research interests are the construction of pairing-friendly elliptic curves, pairing algorithms and the efficient implementation of cryptographic pairings.



A + B = C
Neeraj Kayal

3/2 1:30pm
ABSTRACT:
    Dvir and Shpilka had conjectured the following: If A,B and C are coprime multivariate polynomials each of whose zero sets (the set of points at which a polynomial evaluates to zero) is a union of hyperplanes and if A + B = C, then the number of variables occurring in ABC is upperbounded by a constant. We prove this conjecture and show that in such a situation, the number of variables is at most 5.
    We then discuss generalizations of this result with an application to arithmetic circuit identity testing. This is joint work with Shubhangi Saraf.
BIO:
    Neeraj Kayal obtained his PhD from the Indian Institute of Technology, Kanpur. He has been awarded the Gödel prize, the Fulkerson prize and the Distinguished Alumnus award of IITK for devising the first efficient deterministic primality testing algorithm along with his co-authors. He subsequently did a joint postdoctoral fellowship with the Institute for Advanced Study, Princeton and Rutgers University, New Jersey. He has been working with Microsoft Research Lab, India since 2008.



Hash functions and Cayley graphs: the end of the story?
Christophe Petit

3/5 10:30am
ABSTRACT:
    Hash functions are a fundamental primitive in cryptography, practically used for digital signatures, message authentication codes and password storage.
    In this talk, we review a mathematical construction of hash functions that is based on finite groups and Cayley graphs. We describe the advantages and drawbacks of this construction. The mathematical structure helps in understanding the security properties and improving the efficiency of the functions, but it is also useful to the attacker who wants to break it. In particular, we present three attacks specific to these hash functions, trapdoor attacks, subgroup attacks and lifting attacks, and illustrate their use in old and recent attacks against particular functions.
    Although most concrete proposals have been broken, we point out that each of these proposals was also particularly weak in some sense. Since the generic design has very interesting properties, its security definitely deserves further studies.
BIO:
    Christophe Petit is a post-doctoral researcher at UCL Crypto Group, under a research grant of the Belgian NSF. He finished his PhD dissertation on "Cryptographic hash functions based on expander graphs" in 2009, under direction of Prof. Jean-Jacques Quisquater.He is mainly interested in cryptography, graph theory and algorithmic number theory. His research focuses on the hardness of the representation problem in non-Abelian groups as well as on its applications in cryptography, especially for hash functions. He has also worked on physical cryptography, including the modeling of side-channel attacks and the development of new fault attacks.



Matrix Rigidity and Complexity of Linear Transformations
Satya Lokam

3/16 10:30am
ABSTRACT:
    A matrix A is said to be (k,r)-rigid if at least k entries of A must be altered to reduce its rank to a value ≤ r . A counting/dimension argument shows that almost all n × n matrices over an infinite field are ((n-r)2,r) -rigid. The challenge is to construct explicit matrices that are (n1+δ, εn)-rigid for positive constants δ and ε. Initial motivation for this goal comes from a result due to Valiant (1977), who introduced the notion of rigidity and proved that the linear transformation given by an (n1+δ, εn)-rigid matrix requires superlinear size arithmetic circuits of logarithmic depth.
    We recently constructed several families of (Ω(n2), εn)-rigid matrices with algebraic numbers as entries. While these matrices have a succinct mathematical description, e.g., entries are square roots of distinct primes, they are not explicit in the sense of being efficiently constructible in a Boolean model of computation. The techniques used to prove rigidity lower bounds on these matrices also help us prove nearly-quadratic lower bounds on the arithmetic circuit complexity of the corresponding linear transformations. These bounds are stronger than those implied by Valiant's criterion. In this talk, we will discuss some of these results.
    Some results reported here are joint work with Abhinav Kumar (MIT), Vijay Patankar (MSR India), and Jayalal Sharma (Tsinghua).
BIO:
    Satya Lokam is the head of the Cryptography, Security, and Applied Mathematics group at Microsoft Research India. His research interests include Cryptography and Complexity Theory. Specifically, he is interested in applying combinatorial and algebraic techniques in cryptographic constructions and in proving lower bounds in various models of computation. Satya received his Ph.D. from the University of Chicago and held postdoctoral fellowships at the University of Toronto and at the Institute for Advanced Study in Princeton. Before moving to Microsoft Research, Satya was a faculty member at the University of Michigan in Ann Arbor.



Privacy-Protecting Health Software Platforms
Ben Adida

3/18 3:30pm
ABSTRACT:
    Medical informaticians are keenly receptive to privacy needs, because hospital oversight boards and the public-at-large are particularly sensitive to the issue. As a result, judicious use of applied security and cryptography can enable novel, sometimes ground-breaking medical research initiatives and even improved health outcomes which, without proper patient-data protection, would simply never be approved.
    This talk presents ongoing work at Children's Hospital Boston's Informatics Program centered on personally controlled health records, where cryptographic techniques and secure software design are enabling new, more flexible, and more effective research protocols. Most notable is the Gene Partnership Project (GPP), which communicates to patients new, clinically relevant research results that pertain specifically to them, using a targeted encrypted broadcast channel that does not require researchers to re-identify their subjects.
    Joint work with Isaac Kohane and Kenneth Mandl.
BIO:
    Ben Adida is Research Faculty at Harvard Medical School / Children's Hospital Boston. His research focuses on autonomy, or how to empower individuals with secure, private, irrevocable, and efficient access to their data. Specifically, Dr. Adida studies security and privacy of personal health records, the security of web applications, interoperable web-based structured data, and the design of secure voting systems. Ben received his PhD from MIT's Cryptography and Information Security group.