| Cryptography and Information Security Group: Seminars and Talks |
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.
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.
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(l2) 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.