TBA

This property is well-known for some weaker notions of secure encryption. However, for chosen-ciphertext secure (CCA2) encryption---i.e., the notion of encryption that is strong enough for the Internet---the question has remained open since the notion of CCA2 security was introduced by Rackoff and Simon in 1992.

The importance of this work is two-fold: we extend our understanding of encryption by establishing that bit-encryption is complete, and we introduce a novel technique that may help resolve remaining open questions about encryption.
Joint work with Steven Myers at Indiana.

As our main technical tool, we introduce the concept of an Identity-Based Hash Proof System (IB-HPS), which generalizes the notion of hash proof systems of Cramer and Shoup [CS02] to the identity-based setting. We give three different constructions of this primitive based on: (1) bilinear groups, (2) lattices, and (3) quadratic residuosity. As a result of independent interest, we show that an IB-HPS almost immediately yields an Identity-Based Encryption (IBE) scheme which is secure against (small) partial leakage of the target identity¢s decryption key. As our main result, we use IB-HPS to construct public-key encryption (and IBE) schemes in the Bounded-Retrieval Model.

A common assumption made by cryptographers is that computers are built using secure hardware, i.e. an adversary can only interact with the device in a black box manner and does not have access to its internals. The reality is less friendly. Indeed, in many cases an adversary can perform side-channel attacks by making physical measurements on and around the device. Such attacks include measuring power consumption, sound emanation, and timing as well as attacks where the adversary gains access to the RAM of the device after it has been powered off (often referred to as "Cold Boot" attacks).

A common approach to protecting against such attacks is to design more secure hardware. However, in recent years cryptographers have been increasingly focused on algorithmic approaches for protecting against side channel attacks, thus trying to minimize the assumptions about the security of the underlying hardware.

In this work we define and construct a Leakage Resilient "Key Proxy" -- a cryptographic primitive that allows a secret key to be stored and computed on repeatedly in an environment susceptible to side-channel attacks. We assume that every time a function is evaluated on the key, a bounded amount of information about the "active" part of memory leaks to the adversary, and that the total number of invocations is unrestricted. Our construction uses the recently achieved Fully Homomorphic Public Key Encryption of Gentry, and makes use of a small memory-less leak free component of fixed complexity. Consequently, our result can be viewed as reducing the task of protecting stateful computation of arbitrary complexity to that of protecting stateless computation of fixed complexity against leakage.
Joint work with Ali Juma and Charles Rackoff.

It's been almost 25 years since Victor Miller and Neal Koblitz proposed using elliptic curves for cryptography. Since that time, ECC has become a primary source of cryptographic primitives in both theory and practice. In this talk I will survey the mathematical theory of elliptic curves and discuss some of the ways in which they are used in cryptography, including classical constructions such as key exchange and digital signatures and more recent innovations that fall under the rubric of pairing-based cryptography. This talk will be expository and should be accessible to graduate students and postdocs.

We study the necessary and sufficient assumptions for universally composable (UC) computation, both in terms of setup and computational assumptions. We look at the common reference string model, the common random string model and the public-key infrastructure (PKI) model, and provide new result for all of them. Perhaps most interestingly we show that:

- For even the minimal meaningful PKI, where we only assume that the secret key is a value which is hard to compute from the public key, one can UC securely compute any poly-time functionality if there exists a passive secure oblivious-transfer protocol for the stand-alone model. Since a PKI where the secret keys can be computed from the public keys is useless, and some setup assumption is needed for UC secure computation, this establishes the best we could hope for the PKI model: any non-trivial PKI is sufficient for UC computation.

- We show that in the PKI model one-way functions are sufficient for UC commitment and UC zero-knowledge. These are the first examples of UC secure protocols for non-trivial tasks which do not assume the existence of public-key primitives. In particular, the protocols show that non-trivial UC computation is possible in Minicrypt.

This is joint work with Ivan Damgaard and Jesper Nielsen.

JOINT CIS/MICROSOFT TALK at MIT
Open To The Public

Date: Friday, September 18, 2009
Time: 10:30 am - 12:30 pm
Place: 32-G449 (Kiva), Stata Center, 32 Vassar Street
Title: Protecting Circuits from Computationally-Bounded Leakage
Speaker: Eran Tromer, CSAIL, MIT

Abstract:

Physical computational devices leak side-channel information that may, and often does, reveal secret internal states. We present a general transformation that compiles any circuit into a device that maintains secrecy even in the presence of well-defined classes of side-channel leakage. Our construction requires only a minimal leak-proof component: one that draws random elements from a simple distribution. We thus reduce the problem of shielding arbitrary complex circuits to the problem of shielding a single simple component.

Our approach is based on modeling the adversary as a powerful observer that inspects the device via a "limited" measurement apparatus. We capture the notion of "limited" measurements using computational complexity classes, and our proofs of security rely on the hardness of certain functions for these classes. Thus, for example, AC^0 lower bounds yield a construction that is resilient to any leakage that can be computed by constant-depth circuits. More generally, we give a generic composition theorem that shows how to build a provably secure devices of arbitrary complexity out of components that satisfy a simulatability condition. Several applications are shown.

In contrast to previous works, we allow the side-channel leakage to depend on the whole state and on all the wires in the device, and to grow unbounded over time.

Joint work with Sebastian Faust and Leonid Reyzin.

JOINT CIS/MICROSOFT TALK at Microsoft
Open To The Public

Date: Friday, August 7th, 2009
Time: 4:00 pm - 5:00 pm
Place: First Floor Conference Center, Microsoft Research NE
Title: A New Protocol Compiler
Speaker: Amit Sahai, UCLA

Abstract:

One of the most fundamental goals in cryptography is to design protocols that remain secure when adversarial participants can engage in arbitrary malicious behavior. In 1986, Goldreich, Micali, and Wigderson presented a powerful paradigm for designing such protocols: their approach reduced the task of designing secure protocols to designing protocols that only guarantee security against "honest-but-curious" participants. By making use of zero-knowledge proofs, the GMW paradigm enforces honest behavior without compromising secrecy. Over the past two decades, this approach has been the dominant paradigm for cryptographic protocol design.

In this talk, we present a new general paradigm/protocol compiler for secure protocol design. Our approach also reduces the task of designing secure protocols to designing protocols that only guarantee security against honest-but-curious participants. However, our approach avoids the use of zero-knowledge proofs, and instead makes use of multi-party protocols in a much simpler setting - where the majority of participants are completely honest (such multi-party protocols can exist without requiring any computational assumptions).
Our paradigm yields protocols that rely on Oblivious Transfer (OT) as a building block. This offers a number of advantages in generality and efficiency.

In contrast to the GMW paradigm, by avoiding the use of zero-knowledge proofs, our paradigm is able to treat all of its building blocks as "black boxes". This allows us to improve over previous results in the area of secure computation. In particular, we obtain:
* Conceptually simpler and more efficient ways for basing unconditionally secure cryptography on OT.
* More efficient protocols for generating a large number of OTs using a small number of OTs.
* Secure and efficient protocols which only make a black-box use of cryptographic primitives or underlying algebraic structures in settings where no such protocols were known before.
This talk is based primarily on joint works with Yuval Ishai (Technion and UCLA) and Manoj Prabhakaran (UIUC).

Speaker Bio:
Professor Amit Sahai received his Ph.D. in Computer Science from MIT in 2000. From 2000 to 2004, he was a professor at Princeton University; in 2004 he joined UCLA as an Associate Professor of Computer Science, and as Associate Director of the Center for Information and Computation Security.
His research interests are in security and cryptography, and theoretical computer science more broadly. He has published more than 75 original technical research papers at venues such as the ACM Symposium on Theory of Computing (STOC), CRYPTO, and the Journal of the ACM. He has given a number of invited talks at institutions such as MIT, Stanford, and Berkeley, including the 2004 Distinguished Cryptographer Lecture Series at NTT
Labs, Japan. Professor Sahai is the recipient of numerous honors; he was named an Alfred P. Sloan Foundation Research Fellow in 2002, and received an Okawa Research Award in 2007. His research has been covered by several news agencies including the BBC World Service.

When and how can a weak device verify that a computational task was completed correctly? For example, how can such a device verify that a computation server performed a costly computation correctly?

This practically motivated question touches on foundational questions in cryptography and complexity theory. In the talk I will present recent progress and tools for delegating computational tasks reliably and survey applications of these new tools to cryptography and complexity theory.

(1) A symmetric encryption scheme whose encryption and decryption algorithms are computable by circuits of quasilinear size (in the message length). The scheme provides security against key-dependent messages and achieves circular security. This provides a highly efficient alternative in the private-key setting to the circular-secure \emph{public-key} encryption scheme of Boneh, Halevi, Hamburg, and Ostrovsky (CRYPTO 2008).

(2) A pseudorandom generator (PRG) that expands an n-bit seed into a 2n-bit pseudorandom sequence and can be computed in quasilinear time. By plugging our PRG in the reductions of Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC 2008) we get commitments and encryption scheme (both in the public and symmetric setting) with polylogarithmic computational overhead and constant communication overhead.

(3) A simple construction of weak randomized pseudorandom function -- a relaxation of standard PRF -- which can be obliviously computed in quasilinear time.
To appear in CRYPTO 2009.

JOINT CIS/MICROSOFT TALK at MIT
Open To The Public

Date: Friday, May 15, 2009
Time: 10:30 am - 12:00 pm
Place: 32-G449 (Kiva), Stata Center, 32 Vassar St
Title: Non-malleability Amplification
Speaker: Rafael Pass, Cornell

Abstract:
We present a technique for amplifying commitment schemes that are non-malleable with respect to identities of length t, into ones that are non-malleable with respect to identities of length \Omega(2^t), while only incurring a constant overhead in round-complexity. As a result we obtain a construction of O(1)^{log* n}-round (i.e., ``essentially'' constant-round) non-malleable commitments from any one-way function, and using a black-box proof of security.
Joint work with Huijia Lin

We examine this question in the specific case of secret sharing. We begin by reviewing work from 2006 showing a protocol for rational secret sharing under the (somewhat unrealistic) assumption of simultaneous broadcast. We then discuss more recent results giving rational secret sharing protocols for asynchronous, point-to-point networks that achieve a stronger notion of equilibrium (namely, (computational) strict Nash equilibrium).

Bio:
Jonathan Katz is an associate professor of computer science at the University of Maryland, and a co-author of the textbook "Introduction to Modern Cryptography". He received his bachelors degrees in chemistry and mathematics from MIT in 1996, and a PhD in computer science from Columbia University in 2002. He enjoys rock climbing in his free time.

Next, we describe a public key encryption scheme using ideal lattices that is almost bootstrappable. Lattice-based cryptosystems typically have decryption algorithms with low circuit complexity, often dominated by an inner product computation that is in NC1. Also, ideal lattices provide both additive and multiplicative homomorphisms (modulo a public-key ideal in a polynomial ring that is represented as a lattice), as needed to evaluate general circuits.

Unfortunately, our initial scheme is not quite bootstrappable - i.e., the depth that the scheme can correctly evaluate can be logarithmic in the lattice dimension, just like the depth of the decryption circuit, but the latter is greater than the former. In the final step, we show how to modify the scheme to reduce the depth of the decryption circuit, and thereby obtain a bootstrappable encryption scheme, without reducing the depth that the scheme can evaluate. Abstractly, we accomplish this by enabling the encrypter to start the decryption process, leaving less work for the decrypter, much like the server leaves less work for the decrypter in a server-aided cryptosystem.

JOINT CIS/MICROSOFT TALK- AT MIT
Open To The Public

Date: Friday, April 10, 2009
Time: 10:30 am - 12:00 pm
Place: 32-G449 (Kiva), Stata Center, 32 Vassar St
Title: Order-preserving symmetric encryption
Speaker: Alexandra Boldyreva, GeorgiaTech

Abstract:
We initiate the cryptographic study of order-preserving symmetric encryption (OPE), a primitive suggested in the database community for allowing efficient range queries on encrypted data. We first show that a straightforward relaxation of standard security notions for encryption such as indistinguishability against chosen-plaintext attack is unachievable by a practical OPE scheme. Instead, we propose a security notion in the spirit of pseudorandom functions and related primitives asking that an OPE scheme look ``as-random-as-possible" subject to the order-preserving constraint.

We then design an efficient OPE scheme and prove its security under our notion based on pseudorandomness of an underlying blockcipher. Our construction is based on a natural relation we uncover between a random order-preserving function and the hypergeometric probability distribution.

In particular, it makes black-box use of an efficient sampling algorithm for the latter.
This is joint work with Nate Chenette, Adam O'Neill and Younho Lee.

On the other hand, for arbitrary values of k, we design a communication efficient two-message protocol extracting nearly k random bits. This dramatically improves the only previously known protocol of Renner and Wolf [RW03], which required O(s) rounds where s is the security parameter. Our solution takes a new approach by studying and constructing **non-malleable seeded randomness extractors ** --- if an attacker sees a random seed X and comes up with an arbitrarily related seed X', then we bound the relationship between R= Ext(W;X) and R' = Ext(W;X').

We also extend our one-round key agreement protocol to the "fuzzy" setting, where Alice and Bob share "close'' (but not equal) secrets W_A and W_B, and to the Bounded Retrieval Model (BRM) where the size of the secret W is huge.

Joint work with Daniel Wichs from STOC 2009. Paper available at http://eprint.iacr.org/2008/503

JOINT CIS/MICROSOFT TALK- AT MICROSOFT
Open To The Public

Date: Friday, March 6, 2009
Time: 10:30 am - 12:00 pm
Place: 14th Floor Tea Lounge, Microsoft Research NE
Title: Cryptography against Memory Attacks
Speaker: Vinod Vaikuntanathan, IBM, TJ Watson

Abstract:
The absolute privacy of the secret keys associated with cryptographic algorithms has been the corner-stone of modern cryptography. Still, there is ample evidence in practice that keys do get compromised at times, by various means. In a particularly devastating side-channel attack proposed recently, termed the ``memory attack'', a significant fraction of the bits of the secret key can be measured if the secret key is {\em ever stored} in a part of memory which can be accessed. Such an attack has been shown to completely compromise the security of various crypto-systems in use, including RSA and AES.

We show two *public-key encryption schemes* secure against memory attacks that leak upto (1-\epsilon) bits of information about the secret-key (for any constant epsilon>0). The first of these is the lattice-based encryption scheme of Regev, and the second is a DDH-based encryption scheme recently proposed by Boneh, Halevi, Hamburg and Ostrovsky. This is done without increasing the size of the secret key, and without introducing any complication of the natural encryption and decryption routines.
Based on joint work with Adi Akavia, Yael Kalai, Chris Peikert and Shafi Goldwasser.

In this work we investigate the computational complexity of such non-interactive privacy mechanisms, mapping the boundary between feasibility and infeasibility. We show:

1. For any query set C and data universe X there is an efficient sanitizer that outputs a synthetic dataset and runs in time poly(|C|,|X|). The sanitizer works even when the size of the original dataset is sub-polynomial in |C|.

2. Under standard cryptographic assumptions, there is no sanitizer that outputs synthetic datasets and works for general classes of counting queries and runs in time sub-polynomial in |C| or |X|. In particular, this is a case where the exponential mechanism cannot, in general, be implemented efficiently.

3. Turning to the potentially easier problem of privately generating an arbitrary data structure (not necessarily synthetic data), there is a tight connection between hardness of sanitization and the existence of traitor tracing schemes.
Joint work with Cynthia Dwork, Moni naor, Omer Reingold and Salil Vadhan.

This talk will briefly review the state of cryptographic election protocols and then delve into recent work on how to bring human voters into the verification process.

Such key agreement, also known as information reconciliation and privacy amplification over unsecured channels, was shown to be theoretically feasible by Renner and Wolf (Eurocrypt 2004), although no protocol that runs in polynomial time was described. We propose a protocol that is not only polynomial-time, but actually practical, requiring only a few seconds on consumer-grade computers.

Our protocol can be seen as an interactive version of robust fuzzy extractors (Dodis et al., Crypto 2006). While robust fuzzy extractors, due to their noninteractive nature, require w to have entropy at least half its length, we have no such constraint. In fact, unlike in prior solutions, in our solution the entropy loss is essentially unrelated to the length or the entropy of w, and depends only on the security parameter.

The paper appears in Eurocrypt 2009 and is available at
http://eprint.iacr.org/2008/494.
This is joint work with Leonid Reyzin.

As applications of this notion, we:
- Give a much simpler and more efficient construction of statistically hiding commitment schemes from arbitrary one-way functions, and
- Prove that constant-round statistically hiding commitments are necessary for constructing constant-round zero-knowledge proof systems for NP that remain secure under parallel composition (assuming the existence of one-way functions).

Joint work with Omer Reingold, Salil Vadhan and Hoeteck Wee.

Joint work with Mohammad Mahmoody-Ghidary.

In this talk, I give a formal treatment of the path-quality monitoring problem, and discuss new secure protocols that allow a sender to raise an alarm when packet loss and corruption exceeds some threshold, even when an adversary tries to bias monitoring results. Our protocols are designed to be lightweight enough to be deployed in the resource-constrained environment of high-speed routers.

I will present our -Y´secure sketch¡ protocol, that combines second-moment estimation techniques with ideas from cryptography, and requires O(log(T)) storage in order to monitor T packets sent on an Internet data path; e.g., monitoring billions of packets requires 200-600 bytes of storage and a single IP packet of extra communication. Time permitting, I will present another protocol that scales well with number of routers in the network, and discuss connections between the path-quality monitoring problem and the adversarial sketch model of Mironov, Naor, and Segev.
This is joint work with David Xiao, Eran Tromer, Boaz Barak, and Jennifer Rexford.

In this work we present a local self correcting algorithm for homomorphism codes Hom(Z_N^k,Z_N) that reads O(k) *bits* to output a single bit of the value of the closest codeword on the given entry (in a non standard binary representation); the algorithm is restricted to codewords C and entries s corresponding to invertible group elements, and extends to other codes Hom(G,H). Our algorithm improves over prior works as long as k = o(log N). In particular, for Hom(Z_N,Z_N) our algorithm reduces the number of read bits from O(log N) to O(1).

In addition, we use our algorithm to obtain the first local self correcting algorithm for the MPC codes of Akavia-Goldwasser-Safra FOCS'03, and for their generalizations defined here.

In terms of techniques, we develop a new approach for local self correcting in which we first reduce the self correcting problem into a property testing problem concerning the location of significant Fourier transform coefficients (aka, SFT-testing), and then give an efficient algorithm solving SFT-testing with O(k) read bits. The SFT-testing algorithm may be of independent interest.

Our main technical innovation is a reduction from certain variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. In addition, we construct new cryptosystems based on LWE, including a very natural chosen ciphertext-secure system that has a much simpler description and tighter underlying worst-case approximation factor than prior constructions.

The validity and strength of the assumptions raise interesting new algorithmic and pseudorandomness questions, and we explore their relation to the current state-of-art. Joint work with Boaz Barak and Avi Wigderson.

We will describe in this talk two recent advances in implementing secure computation. The first is a system for secure two-party computation which has fully-simulatable security against malicious adversaries. Experiments with this system reveal interesting results about the overhead of different parts of the computation, and about the efficiency of using components which are secure in the standard model.

We also present FairplayMP (for "Fairplay Multi-Party"), a system for multi-party computation secure against semi-honest adversaries. The underlying protocol of FairplayMP is the Beaver-Micali-Rogaway (BMR) protocol, which is modified in order to improve its efficiency. This protocol was chosen since it runs in a constant number of communication rounds. We also report on different experiments which measure the effect of different parameters on the performance of the system and demonstrate its scalability.

Based on joint work with Yehuda Lindell and Nigel Smart, and with Assaf Ben-David and Noam Nisan.

In Katz's original protocol, instead of trusting a third party to correctly generate setup information, each party creates its own hardware token, which it sends to the other party. Each party only needs to trust that its own token is tamper-proof.

Our protocols only require a single party (Goliath) to be capable of generating tokens. We construct a version of the protocol that is secure for computationally unbounded parties, and a more efficient version that makes computational assumptions only about David (we require only the existence of a one-way function). Our protocols are simple enough to be performed by hand on David's side.

These properties may allow such protocols to be used in situations which are inherently asymmetric in real-life, especially those involving individuals versus large organizations. Classic examples include voting protocols (voters versus ``the government'') and protocols involving private medical data (patients versus insurance-agencies or hospitals).
This is joint work with Gil Segev.

Computational limitations to proper and improper learning have been extensively studied, starting with the seminal works of Pitt-Valiant (JACM '88) and Kearns-Valiant (JACM '94). However, while the hardness of proper learning can be based on worst case assumptions on the power of NP (e.g. NP != RP), all known limitations on improper learning are based on cryptographic assumptions (e.g., the existence of one-way functions). It is natural to ask whether this gap is inherent, specifically: is it possible to base hardness of improper learning on worst case assumptions such as NP != RP?

Unfortunately this problem has remained open and seems difficult to solve. In this work we show that it is related to questions of average-case vs. worst-case complexity and weak cryptographic primitives. In particular, we prove the following: if there exists a black-box reduction R from deciding a language L to learning small circuits, then there exists a reduction R' from deciding L to inverting a family of auxiliary-input one-way functions (as defined by Ostrovsky-Wigderson). Furthermore, if R is non-adaptive, then in fact we can adapt the results of Akavia et al. to show that this implies L is contained in coAM. As a corollary, if L is NP-complete then PH collapses and so such a reduction is unlikely to exist. Our results hold even in the stronger model of agnostic learning.
This is joint work with Benny Applebaum and Boaz Barak.

Instead, we ask whether one can save on the (expensive) secret random bits at the cost of adding (inexpensive) public random bits. Our first main result shows that if the number of output elements of f is at most 2^k, then a simple construction using pairwise-independent hash functions results in a new one-way function that uses only k secret bits (or even just a secret of entropy k). We also demonstrate that this is optimal, in a sense, for black-box reductions.

Our second main result is an application of the public-randomness approach: we show a construction of a pseudorandom generator based on any regular one-way function with output range of known size 2^k. The construction requires a seed of only 2n+O(k log k) bits (as opposed to O(n log n in previous constructions); the savings come from the reusability of public randomness. The secret part of the seed is of length only k (as opposed to n in previous constructions), less than the length of the one-way function input.

This has led NIST to propose a "hash function contest" to design what may be selected as a new national hash function standard, called SHA-3. Proposals for this contest are due in October of this year.

This talk describes the MD6 hash function, which will be submitted to this contest. MD6 has a high degree of parallelizability (it is tree-based), and provable resistance to standard differential collision-finding attacks. We discuss the design principles and security of MD6.

This work is joint with quite a few colleagues and students, whose names will be listed in the talk.

Venkatesan and Yung (CRYPTO '92). As a corollary, we derive similar tight lower bounds for several other cryptographic protocols, such as single-server private information retrieval, interactive hashing, and oblivious transfer that guarantees statistical security for one of the parties.

Our techniques extend the collision-finding oracle due to Simon (EUROCRYPT '98) to the setting of interactive protocols (our extension also implies an alternative proof for the main property of the original oracle). In addition, we substantially extend the reconstruction paradigm of Gennaro and Trevisan (FOCS `00). In both cases, our extensions are quite delicate and were found useful inproving additional black-box separation results. Joint work with Jonathan J. Hoch, Gil Segev and Omer Reingold

JOINT CIS/MICROSOFT TALK
Open To The Public

Date: Friday, Aug 15, 2008
Time: 10:30 am - 12:00 pm
Place: 32-G449, Kiva, Stata Center, 32 Vassar St.
Title: "Probabilistically Checkable Arguments"
Speaker: Yael Kalai, Microsoft

Abstract:
We give two results. The first is a general reduction converting any public-coin interactive proof into a one-round (two-message) argument. It is based on a method of Aiello et al, using a Private-Information-Retrieval (PIR) scheme to collapse rounds in interactive proofs. For example, the reduction implies that for any security parameter t, the membership in any language in PSPACE can be proved by a one-round (two-message) argument of size poly(n,t), which is sound for malicious provers of size 2^t.

(Note that the honest prover in this construction runs in exponential time, since she has to prove membership in PSPACE, but we can choose t such that 2^t is significantly larger than the running time of the honest prover).

We then define the notion of a *probabilistically checkable argument* (PCA).
This is a relaxation of the notion of probabilistically checkable proof (PCP).
It is defined analogously to PCP, except that the soundness property is required to hold only computationally.
We consider the model where each verifier is associated with a public key, and each PCA is verifier-dependent, i.e., it depends on the verifier's public key. (The key does not need to be certified, and we can assume that the verifier simply publishes it on his web-page). We show that every NP language, verifiable by a poly-size formula, has a PCA (with efficient honest prover) of size polynomial in the size of the *witness*. This compares to the best PCPs that are of size polynomial in the size of the *instance* (that may be significantly larger). The number of queries to these PCAs is poly-logarithmic.
This result is proved via a general reduction that converts any *interactive-PCP* (with certain properties) into a PCA, together with a very recent interactive-PCP construction of Goldwasser et al.
The soundness property, in all our results, relies on exponential hardness assumptions.
This is joint work with Ran Raz.

JOINT CIS/MICROSOFT TALK
Open To The Public

Date: Friday, Aug 08, 2008
Time: 10:30 am - 12:00 pm
Place: Microsoft, Charles Rm, 1st flr, 1 Mem Drive
Title: "A Framework for Efficient and Composable Oblivious Transfer"
Speaker: Vinod Vaikuntanathan, CSAIL, MIT
Host: Yael Kalai

Abstract:
We propose a simple and general framework for constructing *oblivious transfer* (OT) protocols that are efficient, universally composable, and generally realizable from a variety of cryptographic assumptions, such as the decisional Diffie-Hellman assumption, the Quadratic Residuosity assumption and worst-case complexity assumptions relating to *lattices*. Our OT protocols are round-optimal (one message each way) and efficient in the parties' communication and local computation, and use only one reference string for an unbounded number of executions.

One of our key technical contributions is a unified view of several encryption schemes in the literature that have what we call *message-lossy* public keys, whose defining property is that a cipher-text produced under such a key carries *no information* (even statistically) about the encrypted message.

Joint work with Chris Peikert (SRI) and Brent Waters (SRI).

BIO:
Vinod Vaikuntanathan is a Ph.D. candidate in the Theory of Computation group at MIT. His research interests lie in cryptography, distributed algorithms and complexity theory.
*Upon arrival at One Memorial Drive, kindly approach the Lobby Security Desk and show a picture ID and sign the Building Visitor Log.

We provide evidence that security under correlated products is achievable by demonstrating that any collection of lossy trapdoor functions, a powerful primitive introduced by Peikert and Waters (STOC '08), yields a collection of injective trapdoor functions that is secure under the above mentioned natural correlated products. Although we eventually base security under correlated products on lossy trapdoor functions, we argue that the former notion is potentially weaker as a general assumption. Specifically, there is no fully-black-box construction of loss trapdoor functions from trapdoor functions that are secure under correlated products.
Joint work with Gil Segev.

In this case, we utilize specific properties of the Naor-Reingold pseudorandom function in order to achieve high efficiency. Finally, we show that using standard smartcards it is possible to construct truly practical secure protocols, and demonstrate this on the problem of set intersection.

We consider a variety of adversary models and definitions of security in our results. Some of our protocols are secure in the presence of malicious adversaries with full simulation (via the ideal/real paradigm), and some provide only privacy. We also present protocols that are secure in the presence of covert adversaries. Loosely speaking, this means that a malicious adversary can cheat, but will then be caught with good probability.

We formulate two quite different flavors of non-malleability requirements for program obfuscation, and construct non-malleable obfuscators of both flavors for some program families of interest. Some of our constructions are in the Random Oracle model, whereas another one is in the common reference string model. We also define the notion of verifiable obfuscation which is of independent interest. This is joint work with Ran Canetti.

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. All previous provably secure solutions require that a prover send O(l) authenticator values (i.e., MACs or signatures) to verify a file, for a total of O(l²) bits of communication, where l is the security parameter. The extra cost over the ideal O(l) communication can be prohibitive in systems where a verifier needs to check many files.

We create the first compact and provably secure proof of retrievability systems. Our solutions allow for compact proofs with just one authenticator value -- in practice this can lead to proofs with as little as 40 bytes of communication. We present two solutions with similar structure. The first one is privately verifiable and builds elegantly on pseudorandom functions (PRFs); the second allows for publicly verifiable proofs and is built from the signature scheme of Boneh, Lynn, and Shacham in bilinear groups. Both solutions rely on homomorphic properties to aggregate a proof into one small authenticator value.

Non-transferability of digital signatures is an important security concern, traditionally achieved via interactive verification protocols. Such protocols, however, are vulnerable to "online transfer attacks" -- i.e. attacks mounted during the protocols' executions.

In this paper, we show how to guarantee online untransferability of signatures, via a reasonable public-key infrastructure and general assumptions, without random oracles. Our untransferable signatures are comparable in efficiency to the best prior schemes that provide provably weaker forms of security; in particular, we make no use of general zero-knowledge proofs.

Joint work with Silvio Micali; paper published at PKC 2008.

Bio: Moses Liskov received his PhD from MIT in 2004 and is now an assistant professor in the computer science department of the College of William and Mary in Williamsburg, Virginia.

Open To The Public

Date: Friday, April 4, 2008
Time: 10:30 am - 12 pm
Place: 32-G449, Patil/Kiva, Stata Center, 32 Vassar St.
Title: Isolated Proofs of Knowledge and Isolated Zero Knowledge
Speaker: Daniel Wichs, NYU
Authors: Ivan Damgaard and Jesper Buus Nielsen and Daniel Wichs
http://eprint.iacr.org/2007/331

Abstract:
We introduce a new notion called $\ell$-isolated proofs of knowledge ($\ell$-IPoK). These are proofs of knowledge where a cheating prover is allowed to exchange up to $\ell$ bits of communication with some external adversarial environment during the run of the proof.

Without any additional setup assumptions, no witness hiding protocol can be an $\ell$-IPoK for \emph{unbounded} values of $\ell$. However, for any \emph{pre-defined} threshold $\ell$, and any relation in NP and we construct an $\ell$-IPoK protocol for that relation. The resulting protocols are zero knowledge (ZK) in the standard sense, i.e., w.r.t. a verifier that communicates only with the prover during the proof. The cost of having a large threshold $\ell$ is a large communication complexity of the constructed protocol. We analyze these costs and present a solution that is asymptotically optimal.

If a cheating verifier is allowed to communicate arbitrarily with an external environment, it is not possible to construct an $\ell$-IPoK that is also ZK with respect to such a verifier. As another new notion, we define $\ell$-isolated zero knowledge ($\ell$-IZK) where the verifier is $\ell$-isolated. For every relation in NP and every $\ell$, we construct an $\ell$-IPoK protocol that is also $\ell$-IZK.

We describe several applications of $\ell$-IPoK protocols under the physical assumption that one can $\ell$-isolate a prover for the duration of the proof phase. Firstly, we can use a witness indistinguishable (WI) $\ell$-IPoK to prevent ``man-in-the-middle'' attacks on identification schemes. Prior results for this scenario required all verifiers to register keys under a PKI, or the ability to fully isolate the prover. Secondly, a partially isolated prover can register a public key and use a WI $\ell$-IPoK to prove knowledge of the corresponding secret key to another party acting as a verifier. This allows us to set up a PKI where the key registrant does not need to trust the Certificate Authority. The PKI is not perfect since the proof is only witness indistinguishable and not zero knowledge. In a companion paper, we show how to set up such a PKI and use it to implement arbitrary multiparty computation securely in the UC framework without relying on any trusted third parties.

We present an extension of the Universal Composability framework that allows to model the security of cryptographic protocols against coercion. The framework allows to model general protocol tasks as ideal functionalities and guarantees secure composition.

Various degrees of incoercibility can be expressed, ranging from deniability (where the honest party only has to deny after the protocol execution that it performed some actions) to full incoercibility (where the attacker may force the party to deviate from the protocol to produce proofs of its actions).

We compare the framework with the Global UC framework by Canetti, Dodis, Pass and Walfish which also models deniability. We argue that the Global UC framework models deniability against an outside adversary, while our framework models deniability or incoercibility against an inside adversary partaking in the protocol.

Finally, we investigate composable incoercible commitments.
(Joint work with Jorn Muller-Quade.)

One-time programs serve many of the same purposes of program obfuscation, the obvious one being software protection. However, the applications of one-time programs go beyond those of obfuscation. One-time programs only allow a user to learn the program's output on a bounded number of inputs, whereas obfuscated programs can be run an arbitrary number of times. For example, one-time programs lead naturally to electronic cash or token schemes: coins are generated by a program that can only be run once, and thus cannot be double spent.

Moreover, the new paradigm of one-time computing opens new avenues for conceptual research. We explore one such avenue, presenting the new concept of ``one-time proofs'', proofs that can only be verified once and then become useless and unconvincing.

All the above tasks are impossible using software alone, as any piece of software can be copied and run again, enabling the user to execute the program on more than one input. Our solutions employ a very simple and cheap secure hardware device. We show that any standard program (Turing Machine) can be efficiently compiled into a functionally equivalent one-time program that employs this simple hardware device. We can similarly transform a classic NP witness for a statement into a one-time proof for the statement, this one-time proof employs the same hardware device.

Joint work with Shafi Goldwasser and Yael Kalai

In this talk, we ask what types of *learning* problems can be solved (and their results, published) while preserving rigorous notions of privacy. Learning problems form an important category of computational tasks that includes many of the computations applied to large, real-life datasets.

Roughly, our study corresponds to asking: what learning problems can be solved by algorithms that do not depend heavily on any single input?

Some highlights:
a) Ignoring computation time, but retaining the restrictions of polynomial sample complexity and a polynomially-sized output, the class of solvable classification problems (roughly, Valiant's "PAC" model) is the same with and without the constraint of preserving privacy.
b) There are polynomial-time *private* learning algorithms for the PARITY problem.Together with earlier results on "statistical query" (SQ) learning, this implies that all commonly studied learning classes have efficient private learners.
c) The power of "local" privacy-preserving publication mechanisms is equivalent to SQ. Local mechanisms, in which each contributing individual anonymizes his/her own data, generalize "randomized response" and other techniques. The data mining community has studied local mechanisms extensively. Our results imply that these popular mechanisms are strictly less powerful than the more general model used above for learning parity.

Based on joint work with Shiva Kasivswanathan, Homin Lee, Kobbi Nissim and Sofya Raskhodnikova.
*The talk will be self-contained.* However, attendees may also be interested in a talk to be given by Sofya Raskhodnikova (on different, but related, results) on Thursday, 2/ 28 in the algorithms seminar.

Our construction departs from the oft-used paradigm of re-encrypting the same message with different keys and then proving consistency of encryptions in zero-knowledge. Instead, we encrypt an encoding of the message with certain locally testable and self-correcting properties. In this talk, I will focus on how we exploit properties of low-degree polynomials to compute such an encoding.

This is joint work with MIT alumni Tal Malkin and her students Seung Geol Choi and Dana Dachman-Soled.

Open To The Public

Date: Friday, Feb 8, 2008
Time: 10:30 am - 12 pm
Place: 32-G449, Patil/Kiva, Stata Center, 32 Vassar St.
Title: Towards the Bare Bones of Trust: A Tour of Trust Assumptions for Obtaining Universally Composable Security
Speaker: Ran Canetti, IBM, CSAIL

Abstract:
A desirable goal for cryptographic protocols is to guarantee security when the protocol is composed with other protocol instances. Universally Composable (UC) security provides this guarantee in a strong sense: A UC-secure protocol maintains its security properties even when composed concurrently with an unbounded number of instances of arbitrary protocols. However, many interesting cryptographic tasks are provably impossible to realize with UC security, unless some trusted set-up is assumed.

We review the basic impossibility results and examine a number of quite different trust models that were recently demonstrated to suffice for constructing UC-secure protocols that realize practically any cryptographic task.
(This is a re-run of a talk given at Asiacrypt 2007.)

In addition, I'll describe how to realize lossy TDFs under number theoretic assumptions, including hardness of the decisional Diffie-Hellman (DDH) problem and the worst-case hardness of standard lattice problems. Taken all together, these results resolve some long-standing open problems in cryptography. They give the first known (injective) trapdoor functions based on problems not directly related to integer factorization, and provide the first known CCA-secure cryptosystem based solely on worst-case lattice assumptions.

We propose a simple and general framework for constructing *oblivious transfer* (OT) protocols that are efficient, universally composable, and generally realizable from a variety of cryptographic assumptions, such as the decisional Diffie-Hellman assumption, the Quadratic Residuosity assumption and worst-case complexity assumptions relating to *lattices*. Our OT protocols are round-optimal (one message each way) and efficient in the parties' communication and local computation, and use only one reference string for an unbounded number of executions.

One of our key technical contributions is a unified view of several encryption schemes in the literature that have what we call "message-lossy" public keys, whose defining property is that a ciphertext produced under such a key carries *no information* (even statistically) about the encrypted message.

Joint work with Chris Peikert and Brent Waters.

CANCELLED - To Be Rescheduled in the Spring

Date: Friday, December 14, 2007
Time: 10:30 am - 12 pm
Place: 32-G449, Patil/Kiva, Stata Center, 32 Vassar St.
Title: Sampling, Learning and Data Privacy
Speaker: Adam Smith, PSU

A grid builds for a resource-scarce user a virtual organization (VO) of unbounded computational and/or storage capacity by pooling heterogeneous resources from real organizations. A VO is a multitenancy environment in two senses: (i) a user is a tenant of multiple resource providers (lessors) for one batch of jobs and (ii) each lessor can host multiple tenants. Ideally, commercial organizations in particular resource-under-utilized financial institutions, should ``go for grid'' to become lessors. However currently such multitenancy grids are not in commercial adoption yet. Inadequate grid security is a main hurdle holding commercial organizations from becoming lessors. A missing security service is behavior conformity: a tenant mustn't cause damage to the lessor or other tenants, and conversely, the lessor mustn't compromise the proprietary code/data of a tenant.

Project Daoli attempts to strengthen grid security by adding behavior conformity. We will apply Trusted Computing Group's (TCG) technology as our means to behavior conformity and we do so by working on virtualization in two layers in the software stack. In the OS layer, a highly-privileged hypervisor for memory arbitration will be measured by a Trusted Platform Module (TPM) to achieve isolation between processes of different tenants. Above OSes a grid middleware will achieve virtualization of hardware platforms and commodity OSes so that a unique VO code of a tenant for remote policy enforcement can run across a heterogeneous environment. The VO code and/or data which need confidentiality and/or integrity protection are secured by cryptographic credentials. By calling the standard credential migration function of TCG, VO's credentials can be migrated from one TPM to another along the leased platforms.

We give the first construction of a practical non-interactive anonymous credential system whose security does not rely on the random oracle model. We introduce P-signatures (Signatures with efficient Protocols) as our main building block. A P-signature scheme consists of a signature scheme, a commitment scheme, and
(1) an interactive protocol for obtaining a signature on a committed value;
(2) a non-interactive proof system for proving that the contents of a commitment has been signed;
(3) a non-interactive proof system for proving that a pair of commitments are commitments to the same value. P-signatures are a powerful tool that may serve as a useful building block for other privacy-preserving authentication mechanisms.

Our constructions makes extensive use of the recently developed Groth-Sahai proof system. We present some new notation that makes it easier to use Groth-Sahai proofs as a building block, which may be of independent interest.

Open To The Public

Date: Friday, November 9, 2007
Time: 10:30 am - 12 pm
Place: 32-G449, Patil/Kiva, Stata Center, 32 Vassar St.
Title: Trapdoors for Hard Lattices, with Cryptographic Applications
Speaker: Chris Peikert, SRI International

Abstract:
Cryptographic schemes based on *lattices* are attractive for several reasons: their computations are simple and of low complexity, they have thus far resisted quantum attacks, and their security can be based on the *worst-case* hardness of lattice problems. To date, constructions of such primitives have unfortunately been limited mainly to collision-resistant hashing and public-key encryption.

This talk will describe how to securely generate and exploit "trapdoors" in lattices. The cryptographic applications include various kinds of trapdoor functions, simple "hash-and-sign" digital signature schemes, and identity-based encryption, all based on worst-case lattice assumptions. The talk will be self-contained.
Joint work with Craig Gentry and Vinod Vaikuntanathan.

In this talk we extend the Universal Composability (UC) framework to properly model global setup, such as Common Reference String (CRS), Public-Key Infrastructure (PKI) and Random Oracle (RO) models. The new, Generalized UC (GUC) framework has many advatages over the traditional UC framework.

1) it gurantees deniability.
2) it allows one to use the same setup with *arbitrary* protocols, as opposed to specially designed protocols (as in ordinary UC).
3) it is more natural than UC. For example, it removes artificial restrictions of the former, resulting in shorter definitions.
4) one can still model UC setup in GUC, but the resulting setup assumptions become very hard to realize. This explains several existing criticisms of the UC modeling of the CRS/PKI models.

We also show that the global CRS model in insufficient to realize most useful tasks in GUC. However, we introduce a slight strengthing of the CRS setup --- augmented CRS (ACRS) --- which allows one to GUC-realize any cryptographic task. This novel setup (necessarily) introduces a semi-passive trusted party into the CRS model, but has the following win-win guarantee: if the trusted party is present, we get (very strong) GUC security; if it is not, we get a functional equivalent of the CRS model in the UC framework, but with provably stronger security guarantees!
The paper is available at http://eprint.iacr.org/2006/432

Identity Based Encryption (IBE) systems are often constructed using pairings on elliptic curves. One exception is an elegant system due to Cocks which builds an IBE based on the quadratic residuosity problem modulo an RSA composite N. The Cocks system, however, produces long ciphertexts. Since the introduction of the Cocks system in 2001 it has been an open problem to construct a space efficient IBE system without pairings.

We present an IBE system in which ciphertext size is short: an encryption of an s-bit message consists of a single element in Z_N plus s+1 additional bits. Security, as in the Cocks system, relies on the quadratic residuosity problem. The system is based on the theory of ternary quadratic forms.

Joint work with Mihir Bellare.
Paper appeared in EUROCRYPT '06.

The Common Reference String (CRS) model enables otherwise-impossible cryptographic goals such as removing interaction from protocols and guaranteeing composable security. However, the CRS model requires the reference string to be sampled from a fixed and known distribution (e.g., the uniform distribution); security analyses of all current protocols fail when the actual distribution of the reference string differs from the specified one even by a small amount.

This fact rules out a large class of potential implementations of the CRS model such as measurements of physical phenomena (like sunspots), or alternatively using random sources that might be adversarially influenced.

We study the possibility of obtaining universally composable (UC) security in a relaxed variant of theCRS model in which the reference string it sampled from an *arbitrary, adversarially specified* distribution that is unknown to the protocol. On the positive side, we demonstrate that UC general secure computation is obtainable in this model as long as:
(a) this distribution has some minimal min-entropy,
(b) it is efficiently samplable,
(c) the sampling algorithm has not too long a description, and
(d) the sampling algorithm is known to the adversary (and simulator).
On the negative side, we show that if any one of these four conditions is removed then general UC secure computation becomes impossible.

The seminal work of Goldwasser, Micali and Rackoff put forward a computational approach to knowledge in interactive systems, providing the foundation of modern Cryptography. Their notion, and its refinement by Goldriech, Micali and Wigderson, bounds the knowledge of a player in terms of his *potential* computational power, technically defined as its worst-case running-time. We put forward a stronger notion that precisely bounds the knowledge gained by a player in an interaction in terms of the *actual* computation it has performed in that *particular* interaction.

Our approach---which is exemplified in the contexts of zero-knowledge proofs, proofs of knowledge, encryption and secure computation----not only remains valid even if P= NP, but is most meaningful when modeling knowledge of computationally easy properties.

We consider a new model of an Evaluator Prover who receives input values from parties P_1, ..., P_n, performs a computation on these values and publishes the result together with a ZKP of its correctness. The efficiency is achieved by working directly with input numbers rather than at the bit/circuit level. It achieves a hundred-fold efficiency improvement over methods employing homomorphic encryptions.
Classical ZKPs can be made a special case as n =0. Applications include practical secure and secrecy preserving auctions. Presentation will be self contained.

Joint work with Rocco Servidio and Chris Thorpe.

We establish complexity-theoretic characterization of the classes of languages in NP having zero-knowledge argument systems. Using these characterizations, we show that for languages in NP:
- -- Instance-dependent commitment schemes are necessary and sufficient for zero-knowledge protocols. Instance-dependent commitment schemes for a given language are commitment schemes that can depend on the instance of the language, and where the hiding and binding properties are required to hold only on the YES and NO instances of the language, respectively.
- -- Computational zero knowledge and computational soundness (a property held by argument systems) are symmetric properties. Namely, we show that the class of languages in NP intersect co-NP having zero-knowledge arguments is closed under complement, and that a language in NP has a statistical zero-knowledge **argument** system if and only if its complement has a **computational** zero-knowledge proof system.
- -- A method of transforming any zero-knowledge protocol that is secure only against an honest verifier that follows the prescribed protocol into one that is secure against malicious verifiers. In addition, our transformation gives us protocols with desirable properties like having public coins, being black-box simulatable, and having an efficient prover.

The novelty of our results above is that they are **unconditional**, meaning that they do not rely on any unproven complexity assumptions such as the existence of one-way functions.

Joint work with Iftach Haitner, Minh-Huyen Nguyen, Omer Reingold, and Salil Vadhan.

Three types of corruptions are usually considered: active, passive, and fail corruptions. The adversary's corruption power is characterized by a constraint on which players he can potentially corrupt, and in which way. One is interested in the exact condition for which SFE and MPC are possible. So far, only restricted settings were considered where either the condition is a threshold condition or where not all three corruption types were considered at the same time. For all these models, the exact conditions are identical for perfectly secure SFE and MPC.

We present a very simple approach to secure computation and, based on it, establish the exact conditions for perfectly secure SFE and MPC for the natural general adversary model allowing active, passive, and fail corruptions of players. Surprisingly, these two conditions are distinct, i.e., there exist adversaries against which secure SFE is possible, but secure MPC is not possible.

This is joint work with Zuzana Beerliova-Trubiniova, Matthias Fitzi, Martin Hirt, Vassilis Zikas.

Open To The Public

Date: Friday, April 20, 2007
Time: 10:30 am - 12 pm
Place: 32-G449, Patil/Kiva, Stata Center, 32 Vassar St.
Title: ``Order Computations in Generic Groups: Beating the Birthday Paradox''
Speaker: Andrew Sutherland, MIT

Abstract:
Computing the order of an element in a generic group is a provably hard problem (assuming no information about the group is available) requiring exponential time. The two standard methods used to solve this problem, Pollard's rho method and Shanks' baby-steps giant-steps algorithm, both have complexity \Theta(\sqrt{N}). An \Omega(\sqrt{N}) lower bound exists for the discrete log problem and has been conjectured for order computation.

We show this conjecture to be false by presenting a new algorithm with complexity o(\sqrt{N}). The constant factors involved are small, and in practice the new algorithm is substantially faster than existing methods.

Open To The Public

Date: Friday, April 13, 2007
Time: 10:30 am - 12 pm
Place: 32-G449, Patil/Kiva, Stata Center, 32 Vassar St.
Title: A Cryptographic Study of Secure Internet Measurement
Speaker: David Xiao, Princeton U.

Abstract:
The Internet is an indispensable part of our information society, and yet its basic foundations remain vulnerable to simple attacks, and one area that remains especially susceptible to attack is routing. There have been increasing efforts in the networking community to incorporate security into current routing protocols, and secure Internet measurement is necessary to inform any routing protocol. In this talk we will show how to use theoretical tools to give a rigorous treatment of this security problem. We believe our work shows that rigorous techniques, and even tools for negative results such as reducing to one-way functions or black-box separations, can have an immediate impact on the study of security problems of real-world importance.

We describe two definitions for this problem: fault detection (FD) where the honest parties only want to know if the packets they sent were dropped or modified or not, and fault localization (FL) where the honest parties want to know in addition where exactly their packets were modified or dropped. Besides traditional per-packet definitions where we want to know the fate of every packet, we also propose *statistical* definitions that reduce the communication and storage overhead of protocols yet retain useful security properties. We will sketch constructions of schemes that satisfy our security definitions and have desirable practical properties.

Next, we show the negative results implied by our definitions. In particular, we can show the necessity of keys, cryptography, and storage in any secure FD or FL scheme. We will describe in detail the proof of our result that any secure black-box construction of a FL protocol requires cryptography to be performed at each nodes. This result uses a novel application of the black-box separation technique of Impagliazzo-Rudich and the learning algorithm of Naor-Rothblum.

This is joint work with Sharon Goldberg, Boaz Barak, and Jennifer Rexford.

We resolve this question for the case of (information-theoretic) private-key encryption, where parties wish to encrypt a b-bit value using an n-bit shared secret key sampled from some imperfect source of randomness S. Our main result shows that if such n-bit source S allows for a secure encryption of b bits, where b > log n, then one can deterministically extract nearly b almost perfect random bits from S. Moreover, the restriction that b > log n is nearly tight.

Hence, to a large extent, true randomness is inherent for encryption: either the key length must be exponential in the message length b, or one can deterministically extract nearly b almost unbiased random bits from the key. In particular, * the one-time pad scheme is essentially "universal"*.

Our technique also extends to related *computational* primitives which are "perfectly-binding", such as perfectly-binding commitment and computationally secure private- or public-key encryption, showing the necessity to *efficiently* extract almost b *pseudorandom* bits.
Joint work with Carl Bosley.

Open To The Public

Date: Friday, March 16, 2007
Time: 10:30 am - 12 pm
Place: 32-G449, Patil/Kiva, Stata Center, 32 Vassar St.
Title: Robust Fuzzy Extractors and Authenticated Key Agreement from Close Secrets
Speaker: Leonid Reyzin, Boston University
(Joint work with Yevgeniy Dodis, Jonathan Katz and Adam Smith)

Abstract:
Consider the problem of deriving high-quality keys from noisy data in the presense of an active adversary: two parties (or the same party at two different times), holding correlated secret inputs W and W', wish to agree on a uniformly distributed secret key R by sending a single message over an insecure channel.

We study both the keyless case, where the parties share no additional secret information, and the keyed case, where the parties share a long-term secret SK that they can use to generate a sequence of session keys R_j using multiple pairs (W_j, W'_j). The former has applications to, e.g., biometric authentication, while the latter arises in, e.g., the bounded storage model with errors.

Our results improve upon previous work in several respects:
-> The best previous solution for the keyless case with no errors (i.e., W=W') required the min-entropy of W to exceed 2n/3, where n is the bit-length of W. Our solution applies whenever min-entropy of W exceeds the minimal possible threshold n/2, and yields a longer key.
-> Previous solutions for the keyless case in the presence of errors (i.e., W close, but not equal to, W') required random oracles. We give the first constructions in the standard model.
-> Previous solutions for the keyed case were stateful, thus requiring synchronization between the parties. We give the first stateless solution.

For over a century, the US has been using technological approaches to recording and counting votes: level machines, punch cards, optical readers, touch screen machines, prompted largely by widespread corruption with paper ballots. All have been prey to various scams and forms of corruption or just plain malfunctions. Reports from Johns Hopkins and Princeton have demonstrated that many of the touch screen devices currently deployed in the US are wide open to virtually undetectable corruption.

In this talk I will discuss recent advances in cryptographically based, voter-verifiable schemes. These strive to provide high assurance of accuracy whilst preserving ballot secrecy whilst requiring minimal trust in hardware, software, officials etc. Voters are able to confirm that their vote is included in the tally whilst having no way to prove to a third party how they voted, thus ensuring coercion-resistance.

In particular, I will outline the Prêt à Voter scheme and describe a number of vulnerabilities identified with the 2005 version. I will then describe enhancements designed to counter these vulnerabilities. These include the distributed generation of Prêt à Voter ballot forms in encrypted form, on demand decryption and printing of forms, re-encryption mixes for tabulation, and a variant of Adida/Rivest off-line auditing.

The zipper hash function is relatively simple, requiring two compression function evaluations per block of input, but it is not streamable. We also show how to create an ideal (strong) compression function from ideal weak compression functions, which can be used in the standard iterated way to make a streamable hash function.

Open To The Public

Date: Friday, October 13, 2006
Time: 10:30 am - 12 pm
Place: 32-D463, Star conf. rm, Stata Center, 32 Vassar St.
Title: Mitigating Dictionary Attacks on Password-Protected Local Storage
Authors: Ran Canetti, Shai Halevi, Michael Steiner
Speaker: Shai Halevi, IBM TJ Watson

Abstract:
We address the issue of encrypting data in local storage using a key that is derived from the user's password. The typical solution in use today is to derive the key from the password using a cryptographic hash function. This solution provides relatively weak protection, since an attacker that gets hold of the encrypted data can mount an off-line dictionary attack on the user's password, thereby recovering the key and decrypting the stored data.

We propose an approach for limiting off-line dictionary attacks in this setting without relying on secret storage or secure hardware. In our proposal, the process of deriving a key from the password requires the user to solve a puzzle that is presumed to be solvable only by humans (e.g, a CAPTCHA). We describe a simple protocol using this approach: many different puzzles are stored on the disk, the user's password is used to specify which of them need to be solved, and the encryption key is derived from the password and the solutions of the specified puzzles. Completely specifying and analyzing this simple protocol, however, raises a host of modeling and technical issues, such as new properties of human-solvable puzzles and some seemingly hard combinatorial problems. Here we analyze this protocol in some interesting special cases.

Security-critical systems are an important application area for formal methods. However, such systems often contain cryptographic subsystems. The natural definitions of these subsystems are probabilistic and in most cases computational. Hence it is not obvious how one can treat cryptographic subsystems in a sound way within formal methods, in particular if one does not want to encumber the proof of an overall system by probabilities and computational restrictions due only to its cryptographic subsystems.

We survey our progress on integrating cryptography into formal models, in particular our work on reactive simulatability (RSIM), a refinement notion suitable for cryptography. We also present the underlying system model which unifies a computational and a more abstract presentation and allows generic distributed scheduling. We show the relation of RSIM and other types of specifications.

In particular, we present soundness results as well as impossibility results for the classical abstractions of cryptography used in the formal-methods community, the abstraction by initial models of term algebras, also called Dolev-Yao models or symbolic cryptography.

Homepage: http://www.zurich.ibm.com/~bpf

This talk presents an overview of cryptographic voting techniques developed over the last 20 years and introduces two new ideas:
(1) Scratch & Vote, a practical, paper-based, cryptographic voting system that is particularly useful in illustrating the capabilities of cryptographic voting, and
(2) Public Mixing, a new theoretical definition and construction that achieves anonymization (of votes, for example) through public computation.
This work asks "if crypto voting is so good, why aren't we using it yet?" and offers some tentative answers.

Thesis Committee: Ronald L. Rivest, Srini Devadas, Shafi Goldwasser
http://ben.adida.net/thesis-defense/

Using these new techniques, we resolve a number of open questions about NIZK, such as:
* We show how to construct Perfect NIZK Arguments for any language in NP.
* We show how to construct Non-interactive Witness-Indistinguishable Proofs for any language in NP, without a common reference string (such a result was only known previously under a non-standard assumption).
* We show how to construct NIZK Proofs and Arguments for Circuit Satisfiability, where the length of the Common Reference String is O(k) and the length of the proof is O(k|C|), where |C| is the size of the circuit.

(Joint work with Jens Groth and Rafail Ostrovsky, appearing in Eurocrypt 2006 and Crypto 2006)

We have also developed software-based attestation mechanisms for legacy systems without relying on trusted hardware. Our approach enables a verifier to obtain the property of untampered code execution on a legacy Pentium IV workstation.

Adrian Perrig is an Assistant Professor in Electrical and Computer Engineering, Engineering and Public Policy, and Computer Science at Carnegie Mellon University. He earned his Ph.D. degree in Computer Science from Carnegie Mellon University, and spent three years during his Ph.D. degree at University of California at Berkeley. He received his B.Sc. degree in Computer Engineering from the Swiss Federal Institute of Technology in Lausanne (EPFL). Adrian's research interests revolve around building secure systems and include Internet security, security for sensor networks and mobile applications. More information about his research is available at:
Adrian
Adrian is a recipient of the NSF CAREER award in 2004, the IBM faculty fellowship in 2004 and 2005, and the Sloan research fellowship in 2006.

This resolves an open question posed by Naor, Ostrovsky, Venkatesan, and Yung (Crypto `92), who gave a construction based on one-way permutations. Constructions were also known under collision-resistant hashing and ``approximable preimage size'' one-way functions. The existence of one-way functions is implied by all the these assumptions, and is essentially the minimal assumption needed for nontrivial zero knowledge.
A key tool in our construction is the notion of 1-out-of-2-binding commitments, recently introduced by Nguyen and Vadhan (STOC `06).

The one-stage Rivest-Sherman (RS) Attack evaluates each candidate (rotor, initial position)-pair by computing a statistic equivalent to the Index of Coincidence (IC) on the character string that is generated by passing ciphertext through the candidate rotor starting in its candidate initial position. The attack computes this statistic separately for each block of 26 characters, during which only the fastest-moving rotor spins. The correct pair generates a string whose distribution is equivalent (up to permutation of the letter frequencies within each block) to that created by passing plaintext through the correct rotor. By contrast, incorrect rotors, and the correct rotor in any wrong initial position, generate strings formed by passing approximately uniform text through the candidate rotor. The full attack heuristically searches for the (rotor, initial position)-pair for each rotor in the scrambler, one rotor at a time, performing an iteratively-broadening tree search. For each rotor to be determined, the full attack orders all candidate pairs by their statistical scores. This search tests complete candidate keys by decrypting the ciphertext and checking for valid plaintext.

We evaluate the effectiveness of the RS-Attacks by determining relationships between their following parameters: ciphertext length, running time, and probability of success at finding the correct key. Contrary to predictions by Rivest and Sherman, the correct (rotor, initial-position)-pair tends to have a low statistical score rather than a high score. The reason stems from fact that, within each block, the statistic is a mixed-alphabet IC rather than a matching-alphabet IC. We extend and revise Sherman's 1981 theoretical analysis to explain all of our experimental findings.
Keywords. Ciphertext-only attacks, cryptanalysis, cryptography, cryptology, Enigma cryptograph, iteratively-broadening tree search, Railway Enigma, Rivest-Sherman Attacks, RS-Attacks, rotor machines, statistical cryptanalysis, wired-wheel machines.
Alan T. Sherman is associate professor of computer science at UMBC, director of the UMBC Center for Information Security and Assurance (CISA), editor of Cryptologia, and a cryptologic consultant.

We describe our findings and experiences from our technical review of vote verification systems for the Maryland State Board of Elections (SBE). The review included the following four systems for possible use together with Maryland's existing Diebold AccuVote-TS (touch screen) voting system: VoteHere Sentinel; SCYTL Pnyx.DRE; MIT-Selker audio system; Diebold voter verified paper audit trail. As a baseline, we also examined the SBE's procedures for "parallel testing" of its Diebold system. For each system, we examined how it enables voters who use touch screens to verify that their votes are cast as intended, recorded as cast, and reported as recorded. We also examined how well it permits post-election auditing. To this end, we considered implementation, impact on current state voting processes and procedures, impact on voting, functional completeness, security against fraud, attack and failure, reliability, accessibility, and voter privacy.

Our principal findings are, first, that each system we examined may at some point provide a degree of vote verification beyond what is available through the Diebold System as currently implemented, provided the system were fully developed, fully integrated with the Diebold system, and effectively implemented. Second, none of the systems is yet a fully developed, commercially ready product. This interdisciplinary study--the first of its kind--is of interest for the way in which it evaluates the systems, for the technical questions it raises about standard interfaces, and as a snapshot of the state of vote verification technologies and their commercial development.
Keywords. Diebold AccuvoteTS, Diebold VVPAT, Direct Recording Equipment (DRE), computer system security, electronic voting systems, information assurance, Maryland State Board of Elections, MIT Selker VVAATT, parallel testing, Scytl Pnyx.DRE, VoteHere Sentinel, vote verification technology.
Support for this research was provided in part by the Maryland State Board of Elections. For our full report, see Norris, et al. (www.umbc.edu/mipar). This work was carried out at the National Center for the Study of Elections of the Maryland Institute for Policy Analysis and Research at UMBC.
Alan T. Sherman is associate professor of computer science at UMBC and director of the UMBC Center for Information Security and Assurance (CISA).

In this talk, we show that using ``standard techniques'' it is not possible to construct a statistical NIZK argument for an $\np$-complete language with adaptive security unless \mbox{$\np \in \ppoly$}. This is a joint work with Serge Fehr (CWI).

The primary challenge with broadcast encryption is to design secure systems with small ciphertext size. For example, we could achieve a broadcast encryption scheme with ciphertexts linear in the number of receivers by simply encrypting a message (or symmetric encryption key) separately to each user the target set. However, this approach is inefficient and becomes infeasible in large systems where there could be many users in a target set.

In this talk I will present two recent developments in broadcast encryption. First, I will discuss my work with Dan Boneh and Craig Gentry on a broadcast encryption scheme that has constant ciphertext size and constant size private keys. Our scheme can be used to encrypt to arbitrary sets of users and is secure against an arbitrary number of colluding attackers. Somewhat surprisingly, the only previous fully-collusion resistant scheme is the trivial where we encrypt to each user separately.

Additionally, I will present some very recent work with Dan Boneh and Amit Sahai on a related problem known as "Tracing Traitors". Our tracing traitors construction allows us to trace a creator of a "pirate box". Our solution achieves O(\sqrt(n)) size ciphertexts and is secure against an arbitrary number of colluders.

Links: http://eprint.iacr.org/2006/045.pdf
http://eprint.iacr.org/2005/018.pdf

Our protocols are nearly optimal in several parameters, including the round complexity (as a function of $n$), the randomness complexity, the communication complexity, and the tradeoffs between the fraction of honest players, the probability that the output lies in a small subset of the universe, and the density of this subset.
Joint work with Salil Vadhan and David Zuckerman.

Consider a trusted server that holds a database of sensitive information. The server would like to reveal global statistics about the population in the database, and yet hide information specific to individuals. I will discuss a recent line of work exploring the tradeoff between these conflicting goals -- first, how the goals can be formulated precisely and second, to what extent they can both be satisfied. The technical results I will mention come mostly from a paper in TCC 2006.

The main contribution is a new, simple framework for "output perturbation". Given a query function F mapping databases to reals, we say the "true" query answer is the result of applying F to the database. To protect privacy, the server perturbs the true answer by adding random noise and sends the result as the query answer. In this setting, a strong notion of privacy can be guaranteed by calibrating the standard deviation of the noise to the "sensitivity" of the function F.

The second contribution is series of bounds on the power of special classes of privacy mechanisms. These show that various kinds of interaction add significantly to the "utility" of the mechanism from the users' point of view.
Based on joint work with Cynthia Dwork, Frank McSherry, Kobbi Nissim and Enav Weinreb.

Our results enhance the understanding of what is necessary for obtaining security under composition, as well as providing tools (i.e., composition theorems) that can be used for proving the security of protocols under composition while considering only the standard stand-alone definitions of security.
Joint work with: Eyal Kushilevitz and Yehuda Lindellw

In this talk we survey some of such usages of extractors, concentrating on several recent results by the speaker. The primitives we will survey include several flavors of randomness extractors (including "fuzzy extractors" and "extractor-macs"), entropically secure encryption and perfect one-way hash functions. The main technical tools will include several variants of the leftover hash lemma, error correcting codes, and the connection between randomness extraction and hiding all partial information.

We introduce a new flavor of commitment schemes, which we call mercurial commitments. Informally, mercurial commitments allow for soft decommitments, which, on the one hand, are not binding, but, on the other hand, cannot conflict with true decommitments.

We then demonstrate that a particular instantiation of mercurial commitments has been implicitly used by Micali, Rabin and Kilian [MRK] for the first ever construction of zero-knowledge sets. (A zero-knowledge set scheme allows a Prover to (1) commit to a set S in a way that reveals nothing about S; and (2) prove to a Verifier, in zero knowledge, statements of the form "x in S" and "x not in S.") The rather complicated construction of [MRK] becomes easy to understand when viewed as a more general construction with mercurial commitments as an underlying building block.

By providing mercurial commitments based on various assumptions, we obtain several new zero-knowledge set constructions.
This is joint work with Melissa Chase (Brown), Alex Healy (Harvard), Anna Lysyanskaya (Brown) and Tal Malkin (Columbia).

We study the problem of sub-linear authentication: suppose you would like to encode and store your file in a way that allows you to verify that it has not been corrupted, but without reading all of it. If you only want to read t bits of the file, how large does the size s of the fingerprint need to be? We define this problem formally, and show a tight lower bound on the relationship between s and t when the adversary is not computationally bounded, namely: s x t= Omega(n) where n is the file size. This is an easier case of the online memory checking problem, introduced by Blum, Evans, Gemmel, Kannan and Naor in 1991, and hence the same (tight) lower bound applies also to this problem.

It was previously shown that when the adversary is not computationally bounded, under the assumption that one-way functions exist, it is possible to construct much better online memory checkers and sub-linear authentication schemes. We show that the existence of one-way functions is also a necessary condition: even slightly breaking the s x t= Omega(n) lower bound in a computational setting implies the existence of one-way functions.
Joint work with Moni Naor.

1. For any polynomial time computable function f: the existence of a randomized *non-adaptive* reduction of worst case NP problems to the task of average-case inverting f implies that coNP\subseteq\AM. It is widely believed that coNP is not contained in AM. Thus, this result may be regarded as showing that such reductions cannot exist (unless coNP\subseteq\AM).
This result improves previous negative results that placed coNP in {\em non-uniform} AM.

2. For any polynomial time computable function f for which it is possible to efficiently compute pre-image sizes (\ie, |f^{-1}(y)| for a given y): the existence of a randomized reduction of worst case NP problems to the task of inverting f implies that coNP\subseteq\AM. Moreover, this is also true for functions for which it is possible to verify (via and AM protocol) the approximate size of pre-image sizes (\ie, |f^{-1}(y)| for a given y). These results holds for *any reduction*, including *adaptive* ones.

The previously known negative results regarding worst-case to average-case reductions were confined to *non-adaptive* reductions. In the course of proving the above results, two new AM protocols emerge for proving *upper bounds* on the sizes of NP sets. Whereas the known *lower* bound protocol on set sizes by [Goldwasser-Sipser] works for any NP set, the known *upper* bound protocol on set sizes by [Aiello-Hastad] works in a setting where the verifier knows a random secret element (unknown to the prover) in the $\NP$ set. The new protocols we develop here, each work under different requirements than that of [Aiello-Hastad], enlarging the settings in which it is possible to prove upper bounds on NP set size.

Joint work with Oded Goldreich, Shafi Goldwasser and Dana Moshkovitz

Though reasonably efficient, the Cramer-Shoup scheme is still substantially more expensive than basic semantically secure schemes: for example, compared to the basic ElGamal scheme it is almost 3 times less efficient in both computation and ciphertext length. For this reason practitioners are using encryption schemes which are more efficient than Cramer-Shoup, but for which chosen-ciphertext security is not proven in the standard computational model but rather in idealized ones such as the random oracle model. The central question then remains to improve as much as possible the efficiency of provably secure schemes.

In this talk we present a simple modification to the Cramer-Shoup scheme which improves its efficiency by 20% and discuss various interesting technical issues that arise in its security proof. We also present a theoretical framework that provides an insightful explanation for why this new more efficient scheme works and may produce further improvements. In particular, using this framework, we are able to construct the first efficient hybrid threshold encryption scheme which is chosen-ciphertext secure.

The new encryption scheme is joint work with Yvo Desmedt, Kaoru Kurosawa and Victor Shoup, while the theoretical framework is joint work with Masayuki Abe and Kaoru Kurosawa.

We also show that if a collision is obtained (as in the Wang et al attack) by putting together local collisions then the disturbance vector must be an xor of a non-zero message expansion codeword and a cipher codeword. We conclude that the modified SHA-1 is resistant to recent differential attacks and their natural extensions. This is joint work with Anindya Patthak, UT Austin.

HMAC combines simple design with sound cryptographic analysis that makes relatively mild security assumptions on the underlying hash function. In particular, this analysis shows that HMAC remains unaffected by the recent advancements in finding collisions in hash functions.

This talk will review the design of HMAC with some historic perspective, in an attempt to draw lessons on the impact of theoretical analysis on practical security and acceptability. We will also survey other common uses of HMAC today, such as for key derivation and randomness extraction in VPN protocols. Finally, we will use these lessons to propose requirements for a new cryptographic hash function, thus contributing to the current specification effort led by NIST.

HMAC is joint work with Mihir Bellare and Hugo Krawczyk.

In this talk, we will present a very efficient hash function for which finding collisions given a *random* key is at least as hard as approximating the shortest vector (SVP) in a cyclic lattice *in the worst case*. Each evaluation of our function requires only a small number (e.g., 3) of Fast Fourier Transforms. Thus, assuming that SVP is indeed hard for the special case of cyclic lattices, our function is efficient enough to be considered a candidate for practical usage.

Our worst-case to average-case reduction is non-standard, exploiting an intimate connection between the ring algebra of integer polynomials and the linear algebra of cyclic lattices. These new techniques enable us to provide a more efficient and conceptually simpler security reduction than previous ones, and to show tight connections among certain worst-case problems on cyclic lattices.
This is joint work with Alon Rosen.

I will first talk about our new constructions for privacy-preserving set operations (CRYPTO 05, joint work with Lea Kissner). We propose efficient techniques for privacy-preserving operations on multisets. By building a framework of set operations using polynomial representations and employing the mathematical properties of polynomials, we design efficient methods to enable privacy-preserving computation of the union, intersection, and element reduction operations.

I will also demonstrate how these operations can be arbitrarily composed, and thus used in a wide range of applications.

I will then describe more recent results on some other cryptographic constructions for privacy-preserving applications.
http://www.ece.cmu.edu/~dawnsong/bio.html

The soundness proof uses standard proof techniques from cryptography, in particular, complexity-theoretic reductions. PCL has been successfully applied to a number of internet, wireless and mobile network security protocols developed by the IEEE and IETF Working Groups, in several cases identifying serious security vulnerabilities.

We give rigorous definitions for transparently updatable zero- knowledge databases, and give a practical construction based on the Chase et al construction, assuming that verifiable random functions exist and that mercurial commitments exist, in the random oracle model. We also investigate the idea of updatable commitments, an attempt to make simple commitments transparently updatable. We define this new primitive and give a simple secure construction.

To our best of knowledge, these are the first constructions of concurrent zero-knowledge protocols in the asynchronous model (without timing assumptions) that do not require complexity assumptions (such as the existence of one-way functions).

The paper is available at http://eprint.iacr.org/2005/286, and is a joint work with Daniele Micciancio, Amit Sahai and Salil Vadhan

Potential benefits of this approach include:
- - A more rigorous specification of cryptographic protocols, as opposed to typical semi-formal pseudocode.
- - more modular and systematic proofs. we can decompose the proofs into different parts, completely separating the concurrency issues from the computational ones.

We hope using PIOAs for the analysis of security protocols will allow for proofs which are less error-prone and more amenable to mechanizatio nand eventual automation.

This is joint work with Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch and Roberto Segala.

The best previously known schemes require at least one of these complexities to be O(2^l k). In fact, compared to previous e-cash schemes, our whole wallet of 2^l coins has about the same size as one coin in these schemes. Our scheme also offers exculpability of users, that is, the bank can prove to third parties that a user has double-spent.

We then extend our scheme to our second result, the first e-cash scheme that provides traceable coins without a trusted third party. That is, once a user has double spent one of the 2^l coins in her wallet, all her spendings of these coins can be traced. We present two alternate constructions. One construction shares the same complexities with our first result but requires a strong bilinear map assumption that is only conjectured to hold on MNT curves.

The second construction works on more general types of elliptic curves, but the price for this is that the complexity of the spending and of the withdrawal protocols becomes O(lk) and O(lk + k^2) bits, respectively, and wallets take O(lk) bits of storage. All our schemes are secure in the random oracle model.

Joint work with Jan Camenisch and Anna Lysyanskaya from Eurocrypt 2005.

During the last decade, significant attention has been paid to the physical security evaluation of cryptographic implementations. In particular, it has been demonstrated that actual attackers may be much more powerful than what can be captured by the black box model.

Examples of extended capabilities include the physical tampering of cryptographic devices, the induction of faults during computations or the use of side-channel leakages such as time, power consumption and electromagnetic measurements. As a straightforward consequence, various cryptosystems implemented on various platforms have been corrupted by these physically enhanced attackers.

In this talk, we will question the physical security of cryptographic implementations with a focus on side-channel attacks, in which adversaries are enhanced with the possibility to exploit physical leakages such as power consumption or electromagnetic radiation. After reviewing the state of the art attacks, we will investigate some commonly proposed countermeasures and illustrate that they do not offer any theoretical guarantee of security.

We will finally discuss the possibility to consider a model of computation where side-channel leakages (and possibly other physical effects) would be formally considered.
Joint work with Tal G. Malkin and Moti Yung (Columbia University).

We provide a formal definition of onion-routing in the universally composable framework, and also discover a simpler definition (similar to CCA2 security for encryption) that implies security in the UC model. We then exhibit an efficient and easy to implement construction of an onion routing scheme satisfying this definition.
Joint work with Jan Camenisch.

We propose a new, lightweight PKI built specifically for email signatures. By limiting ourselves to this sole goal - in particular, by forgoing encryption and more general-purpose authentication - we are able to design a system that relies solely on already-deployed infrastructure. This system requires minimal end-user work, placing the onus, instead, on email domain administrators. Also, the adoption pattern for lightweight signatures is promising: large institutions and ISPs, particularly web-based email providers, can deploy the solution entirely at the mail server level, while more advanced users can obtain the same functionality solely through a mail client upgrade.

However, the addition of digital signatures suddenly makes emails strongly non-repudiable. While such strong authentication may be useful in certain cases, it is not necessary in most email exchanges, and it may in fact hamper deployment if users are forced to treat every email as a signed document. Privacy advocates, in particular, worry about this development. For this reason, we introduce a new type of repudiable signature usable in the lightweight framework: Separable Identity Based Ring signatures (SIBR, pronounced "cyber", signature), which authenticate a message only to the intended recipient.

In this talk, we present a collision search attack on SHA-1. Our attack is built upon existing attacks on its predecessor SHA-0 as well as new analytical techniques introduced in the recent attacks on the MDx family of hash functions. We estimate that collisions of SHA-1 can be found with a workload equivalent to about 2^69 hash operations. This is the first attack on the full 80-step SHA-1 with complexity less than the 2^{80} theoretical bound.

Our attack exploits some unexpected weaknesses in the design of SHA-1. First, the message preprocessing step does not have enough avalanche effect even with the inclusion of the extra shift operation compared with SHA-0. Second, the use of certain Boolean functions together with modular addition can facilitate, rather than preventing, differential-style attacks. We hope that the analysis on SHA-1 can provide useful insight on design criteria for more security hash functions.

The last statement above is our main result, which states that there is no black-box reduction from public-coin CRHFs to secret-coin CRHFs. Our proof for this result, while employing oracle separations, uses a novel approach, which demonstrates that there is no black-box reduction without demonstrating that there is no relativizing reduction.

This is joint work with Leonid Reyzin, and it appears in Crypto 2004.

Authors:
Nenad Dedic, Gene Itkis, Leonid Reyzin, Scott Russell: Boston University

Then I will illustrate the real power of the technique with a new analysis of the Kurosawa-Desmedt variant of the Cramer-Shoup cryptosytem, under weaker, and more realistic, assumptions than those originally made in the original proof by Kurosawa and Desmedt; this result is joint work with Rosario Gennaro.

We continue the study of obfuscation (initiated in [BGI+01]) in the context of point functions. A point function is a Boolean function that assumes the value 1 at exactly one point. Our main results are as follows:

* We provide a simple construction of efficient obfuscators for point functions for a slightly relaxed notion of obfuscation - wherein the size of the simulator has an inverse polynomial dependency on the distinguishing probability - which is nonetheless impossible for general circuits. This is the first known construction of obfuscators for a non-trivial family of functions under general computational assumptions. Our obfuscator is based on a probabilistic hash function constructed from a very strong one-way permutation, and can be realized in the standard model. Our construction also yields an obfuscator for point functions with multi-bit output.

* We also show that such a strong one-way permutation can be realized using a random permutation oracle. and that an assumption like the one we used is necessary for our obfuscator construction.

* Finally, we establish two impossibility results on obfuscating point functions which indicate that the limitations on our construction (in simulating only adversaries with single-bit output and in using non-uniform advice in our simulator) are in some sense inherent.

We stress that prior to this work, what is known about obfuscation are negative results for the general class of circuits [BGI+01] and positive results in the random oracle model [LPS04] or under non-standard number-theoretic assumptions [C97]. This work represents the first effort to bridge the gap between the two for a natural class of functionalities.

Preliminary version of the paper available at http://eprint.iacr.org/2005/001

I discuss some of the requirements and challenges in designing dependable voting systems. I present a scheme, based on an earlier proposal by David Chaum, that provides voter-verification whilst maintaining ballot secrecy and requiring minimal trust in the system components. This scheme appears to be simpler to understand and to implement that Chaum's original.

Electronic devices and systems potentially offer many of the same benefits to the process of conducting elections that they have already delivered to the worlds of business and finance. Unfortunately, the requirement for ballot secrecy, along with the high degree of complexity possible in today's devices, makes it impossible for the general voting population to directly infer that systems tasked with collecting and counting votes are behaving accurately and honestly.

Recently, verifiable mix net and homomorphic tabulation protocols have effectively solved the problem of publicly counting encrypted ballots, thereby eliminating the need to trust special vote counters -- people or machines. Our focus in this talk will be on describing a new protocol, executable by voters while in the poll booth, that eliminates the need for voters to trust the vote casting devices (DREs) as well. By way of a challenge-response scheme, the voting device is prevented from casting an encrypted ballot which is inconsistent with the voter's intent without showing contradictory evidence which the voter can easily detect by simple inspection.

To prevent vote tampering after ballots have been cast, each voter is given a receipt which can be used to audit the public ballot box. However, because part of the voter's proof of ballot correctness is derived from direct observation in the poll booth of the temporal sequence by which the receipt is formed, the receipt is meaningless to someone else -- even when the voter is faced with the threat of coercion. Hence we may obtain for our large scale secret ballot elections the same certainty one obtains when counting a simple show of hands.

We introduce and realize the notion of fully simulatable multiparty computation. Unlike any of the previous models, our notion simultaneously enjoys the following features:
* Main feature: The simulator does not have any extra power over the adversary. In particular, it cannot program any public parameters, learn secret keys not given to the adversary or run in super-polynomial time. Thus, our imple-mentation is fully deniable for tasks such as authentication and zero-knowledge.
* Universal composability (in particular, straight-line simulation).
* No PKI (although there exists one 'non-programmable' public key).
* Adaptive security.

We remark that it might seem impossible to realize all (or even the main) of the above features, even for relatively simple tasks such as zero-knowledge. The way we overcome this apparent contradiction is by introducing a polynomial-time, fully off-line trusted party T to our model. We believe that the addition of fully off-line T is a minimal and very realistic way to overcome the impossibility results in the standard model.

Joint work with Rafael Pass and Shabsi Walfish.

Broad impossibility results have recently been proven regarding the feasibility of obtaining protocols that remain secure under concurrent composition, unless an honest majority or trusted setup phase are assumed. These results hold both for the case of general composition (where a secure protocol is run many times concurrently with arbitrary other protocols) and self composition (where a single secure protocol is run many times concurrently).

One approach for bypassing these impossibility results is to consider more limited settings of concurrency that still realistically model real-world networks. In this paper, we investigate the feasibility of obtaining secure multiparty protocols in a network where certain time bounds are assumed. Specifically, the security of our protocols rely on the very reasonable assumption that local clocks do not ``drift'' too much (i.e., proceed at approximately the same rate). We show that under this timing assumption, it is possible to securely compute any multi-party functionality under concurrent general composition (as long as messages from the arbitrary other protocols are delayed for a specified amount of time).

This is joint work with Yehuda Lindell and Manoj Prabhakaran.