Microsoft Research Redmond Cryptography
Colloquium
The MSR Redmond Cryptography Group invites
researchers to visit the group and speak in our colloquium series.
Below are some recent and future visitors. Unless otherwise listed,
the colloquia are open to the public. For directions or other questions
contact
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.
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.
