Microsoft Research
Redmond Cryptography Colloquium
Past Speakers
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 (n^{1+δ},
ε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 (n^{1+δ}, εn)-rigid
matrix requires superlinear size arithmetic circuits
of logarithmic depth.
We recently constructed several families of (Ω(n^{2}), ε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.