|
We are very interested in interacting with the research and academic community. In fact, we run the Cryptography Research Seminar series where you can tell us about your interesting new results.
Upcoming Seminars
Thursday May 8, 11am, Hawthorne 3N-J21
TITLE: On Basing Lower-Bounds for Learning on Worst-Case Assumptions
SPEAKER: Benny Applebaum, Princeton University
ABSTRACT: We consider the question of whether P \neq NP implies that there exists some concept class that is efficiently representable but is still hard to learn in the PAC model of Valiant (CACM '84). We show that unless the Polynomial Hierarchy collapses, such a statement cannot be proven via a large class of reductions including Karp reductions, truth-table reductions, and a restricted form of non-adaptive Turing reductions. Also, a proof that uses a Turing reduction of constant levels of adaptivity would imply an important consequence in cryptography as it yields a transformation from any average-case hard problem in NP to a one-way function. Our results hold even in the stronger model of agnostic learning.
These results are obtained by showing that lower bounds for improper learning are intimately related to the complexity of zero-knowledge arguments and to the existence of weak cryptographic primitives. In particular, we prove that if a language L reduces to the task of improper learning circuits, then, depending on the type of the reduction in use, either (1) L has a statistical zero-knowledge argument system, or (2) the worst-case hardness of L implies the existence of a weak variant of one-way functions defined by Ostrovsky-Wigderson (ISTCS '93). Interestingly, we observe that the converse implication also holds. Namely, if (1) or (2) hold then the intractability of L implies that improper learning is hard.
Joint work with Boaz Barak and David Xiao
Previous Seminars
Wednesday April 2
TITLE: On the Difficulty of Enforcing Routing Policies with BGP and Traffic Attraction
SPEAKER: Sharon Goldberg, Princeton University
ABSTRACT: Prior work on modeling interdomain routing assumed that autonomous systems (ASes) are interested only in obtaining the best possible *outgoing path* for their traffic to a destination. In reality, many more factors can influence "a rational behavior" of an AS; here we consider a natural model in which ASes are also interested in *attracting incoming traffic*, either out of greed (since other ASes pay it to carry their traffic), or malice (so it can spoof or tamper with packets).
This model of rationality induces a number of situations where an AS has an *incentive* to send Border Gateway Protocol (BGP) announcements that do not correspond to the paths that packets actually traverse in the data plane. In this work, we ask what enhancements to BGP and/or restricted classes of routing policies can ensure that ASes will not have an incentive to lie about data-plane paths. We find that while protocols like secure BGP are necessary, they are in general not sufficient unless ASes are only interested in the next hop that their traffic takes to its destination. Our game-theoretic analysis highlights the high cost of enforcing routing policies in the Internet's data plane.
Joint work with Shai Halevi.
Monday March 17
TITLE: Towards a theory of white box security
SPEAKER: Amir Herzberg, Bar-Ilan University
ABSTRACT: Program hardening for secure execution in remote untrusted environment is an important yet elusive goal of security, with numerous attempts and efforts of practitioners to produce secure solutions. Obfuscation is the prevailing practical technique employed to tackle this issue. However Barak et al. showed that not all programs can be obfuscated.
We present a rigorous approach to program hardening, based on a new white box primitive, the White Box Remote Program Execution (WBRPE), whose security specifications include confidentiality and integrity of local and the remote hosts . We show how WBRPE can be used to address the needs of a wide range of applications, e.g. grid computing and mobile agents. Next, we construct a universal program UP and reduce the security of the WBRPE for every program to the security of WBRPE for the UP, thus establishing the white box notion of security.
Joint works with Haya Shulman, Amitabh Saxanna, Bruno Crispo
Tuesday March 4
TITLE: On the optimality of Merkle (key exchange) and Lamport (one-time signature) schemes in the random oracle model.
SPEAKER: Mohammad Mahmoody-Ghidary, Princeton U.
ABSTRACT: I will talk about the following two results:
I) Optimality of Merkle scheme:
We prove that every key exchange protocol in the RO model in which the honest users make at most n queries to the oracle can be broken with probability close to 1 by an adversary making O(q^2) queries to the oracle. This improves on the previous O(q^6) query attack given by Impagliazzo and Rudich (STOC' 89). Our bound is optimal up to a constant factor since Merkle (CACM '78) gave a q query key exchange protocol in this model that cannot be broken by an adversary making o(q^2) queries.
II) Optimality of Lamport scheme:
We prove that any one-time signature scheme in the RO model in which q is the total number of queries asked by key generation, signing, and verification algorithms can be broken with probability close to 1 by an adversary making poly(q)2^q queries to the oracle. This is tight up to a constant factor in the number of queries, since a simple modification of Lamport's one-time signature scheme (Lamport '79) can not be broken by any adversary making 2^{q/2} queries to the oracle.
Note that the only computational limit over the mentioned adversaries is the number of queries they ask. Hence, in other words we show that the black-box security of the mentioned schemes in the random oracle are indeed optimal.
Joint work with Boaz Barak.
Friday February 8
TITLE: Efficient Protocols with Security against Malicious and Covert Adversaries
SPEAKER: Carmit Hazay, Bar-Ilan University
ABSTRACT: In this talk we present efficient secure protocols for a variety of tasks, including oblivious transfer, set intersection and pattern matching. Our protocols for securely computing the set intersection functionality are based on secure pseudorandom function evaluations, in contrast to previous protocols that used secure polynomial evaluation. We also use secure pseudorandom function evaluation in order to achieve secure pattern matching.
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.
Thursday January 31
TITLE: Almost-Everywhere Secure Computation
SPEAKER: Juan Garay, Bell Labs
ABSTRACT: Secure multi-party computation (MPC) is a central problem in cryptography. At a high level, the problem is concerned with n parties, each holding a private input, who want to compute a function of those inputs so that each party learns his own output, but no other information is revealed, even in the presence of malicious parties that may deviate from the protocol arbitrarily. Instances of MPC include password authentication, distributed auctions, on-line bidding, contract signing, electronic voting, etc.
Unfortunately, it is well known that MPC is possible if and only if the underlying communication network has very large connectivity---specifically, \Omega(t), where t is the number of potential corrupted parties (or nodes) in the network. This impossibility result renders existing MPC results far less applicable in practice, since most deployed networks have in fact a very small degree.
In this talk, we show how to circumvent this impossibility result and achieve meaningful security guarantees for graphs with small degree (such as butterfly networks, expander graphs and several other topologies). In fact, the notion we introduce, which we call almost-everywhere MPC, building on the notion of almost-everywhere agreement due to Dwork, Peleg, Pippenger and Upfal, allows the degree of the network to be much smaller than the total number of allowed corrupted nodes. In essence, our definition allows the adversary to implicitly wiretap some of the good nodes by corrupting sufficiently many nodes in the ``neighborhood'' of those nodes. We show protocols that satisfy our new definition, retaining both correctness and privacy for most nodes despite small connectivity, no matter how the adversary chooses his corruptions.
Instrumental in our constructions is a new model and protocol for the secure message transmission (SMT) problem, which we call SMT by public discussion, and which we use for the establishment of pair-wise secure channels in limited connectivity networks.
This is joint work with Rafail Ostrovsky (UCLA).
Thursday November 8
TITLE: Isodual Reduction of Lattices.
SPEAKER: Nick Howgrave-Graham (NTRU)
ABSTRACT: The theory of lattices is a very well established mathematical discipline, but the concept of lattice basis reduction is not in as good a shape. Even from a mathematical point we don't definitively have an answer to whether one lattice basis is "more reduced" than another one (there are several seemingly sensible partial ordering one can impose on lattice bases). The most well established partial ordering is the lexicographic ordering on the size of the Gram-Schmidt vectors, which is due to Korkine and Zolotarev. We introduce a new one, based on a quantity introduced in the seminal "LLL" paper by Lenstra, Lenstra and Lovasz. We show that the new quantity has the nice property of being isodual, i.e. if one basis is more reduced than another one, then the dual of the first is more reduced that the dual of the second (a property not held by the Korkine-Zolotarev notion). We then show that all of the theory that has been built around the Korkine-Zolotarev notion of a reduced lattice can also be built around this new notion, e.g. there is a natural analogue of Hermite's constants to this new measure.
On the computational side we show that Schnorr's extension of the LLL algorithm to larger "blocks" can also be generalized to the new measure. We describe a practical algorithm to reduce lattices with respect to this new measure, and show that it outperforms all other known techniques when applied to the NTRU family of lattices. We remark that "outperforming" in the NTRU sense corresponds to finding smaller vectors in the NTRU lattice in a given amount of time, i.e. our method also recovers smaller lattices in the Korkine-Zolotarev sense than was previously thought possible.
Friday November 2nd
TITLE: Split-Ballot Voting: Everlasting Privacy With Distributed Trust.
SPEAKER: Tal Moran, Weizmann Institute
ABSTRACT: "Split-Ballot" is a new voting protocol in the family of "end-to-end verifiable" protocols. The voting stage of the protocol can be performed by humans without computers; it provides every voter with the means to verify that all the votes were counted correctly (universal verifiability) while preserving ballot secrecy. The protocol has ``everlasting privacy'': even a computationally unbounded adversary gains no information about specific votes from observing the protocol's output. Unlike previous protocols with these properties, this protocol distributes trust between two authorities: a single corrupt authority will not cause voter privacy to be breached. Finally, the protocol is "receipt-free": a voter cannot prove how she voted even she wants to do so. We can formally prove the security of the protocol in the Universal Composability framework, based on number-theoretic assumptions.
Wednesday October 24
TITLE: Space-Efficient Identity Based Encryption without Pairings
SPEAKER: Craig Gentry, Stanford University
ABSTRACT: Identity Based Encryption (IBE) systems are often constructed using bilinear maps (a.k.a. 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.
In this paper we present an IBE system in which ciphertext size is short: an encryption of an l-bit message consists of a single element in ZN plus l+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 and as a result, encryption and decryption are slower than in the Cocks system.
Friday October 19
TITLE: Finding Collisions in Interactive Protocols -- A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments.
SPEAKER: Iftach Haitner, Weizmann Institute
ABSTRACT: We study the round complexity of various cryptographic protocols. Our main result is a tight lower bound on the round complexity of any fully-black-box construction of a statistically-hiding commitment scheme from one-way permutations, and even from trapdoor permutations. This lower bound matches the round complexity of the statistically-hiding commitment scheme due to Naor, Ostrovsky, 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 may be found useful in proving additional black-box separation results.
Joint work with Jonathan J. Hoch, Gil Segev and Omer Reingold
Friday October 5
TITLE: Traitor Tracing with Optimal Transmission Rate
SPEAKER: Nelly Fazio, IBM Research
ABSTRACT: We present the first traitor tracing scheme with efficient black-box traitor tracing in which the ratio of the ciphertext and plaintext lengths (the _transmission rate_) is asymptotically 1, which is optimal. Previous constructions in this setting either obtained constant (but not optimal) transmission rate [KiYu02], or did not support black-box tracing [CPP05].
Our treatment improves the standard modeling of black-box tracing by additionally accounting for pirate strategies that attempt to escape tracing by purposedly rendering the transmitted content at lower quality.
Our construction relies on the Decisional Bilinear Diffie-Hellman assumption, and attains the same features of public traceability as (a repaired variant of) [CPP05], which is less efficient and requires non-standard assumptions for bilinear groups.
Joint work with Antonio Nicolosi and Duong Hieu Phan.
Thursday August 16th
TITLE: Modes of operation for storage encryption
SPEAKER: Shai Halevi, IBM Research
ABSTRACT: The first half of this talk is a practice talk for my Crypto paper titled "Invertible Universal Hashing and the TET Encryption Mode" (see below). Then I will talk about other modes of operation that considered for encryption of storage.
Invertible Universal Hashing and the TET Encryption Mode
This work describes a mode of operation, TET, that turns a regular
block cipher into a length-preserving enciphering scheme for messages of (almost) arbitrary length. When using an n-bit block cipher, the resulting scheme can handle input of any bit-length between n and 2^n and associated data of arbitrary length.
The mode TET is a concrete instantiation of the generic mode of operation that was proposed by Naor and Reingold, extended to handle tweaks and inputs of arbitrary bit length. The main technical tool is a construction of invertible "universal hashing" on wide blocks, which is as efficient to compute and invert as polynomial-evaluation hash.
Friday August 10
TITLE: On the Structure of Multi-party Computation Functionalities
SPEAKER: Manoj Prabhakaran, University of Illinois at Urbana-Champaign
ABSTRACT: We identify and study certain structural properties of multi-party computation tasks (functionalities). In particular we introduce a property called "splittability," which can be used to precisely characterize which functionalities are {\em securely realizable} under the plain (original) definition of UC security. We use this characterization to show that non-interactive 2-party functionalities that are securely realizable all have a simple deterministic, one-message protocol, extending the impossibility results of Canetti et al. [CKL'03].
We also consider multi-party functionalities (more than 2 parties). In this case we do not necessarily have such simple protocols for all securely realizable functionalities. Broadcast is an example of such a functionality. We present more functionalities and non-trivial protocols for them. However, using our results on 2-party functionalities, we do significantly narrow down the kind of non-interactive multi-party functionalities which could be securely realizable.
We generalize the splittability property into a relation between functionalities and study its transitivity and symmetry. Then we generalize our results on secure realizability to secure realizability using other functionalities.
For 2-party non-interactive functionalities we also define a property called "hiding", which is analogous to "one-wayness" (but with unconditional instantiations, and meaningful in computationally unbounded settings too). We show that the Goldreich-Levin bit is a "hardcore predicate" for hiding functionalities; such a predicate helps in realizing functionalities like commitment using hiding functionalities.
Finally, we propose complexity classes and hierarchies for multi-party functionalities. Several open problems remain in relating the various complexity classes with each other.
This is joint work with Mike Rosulek.
Thursday June 15
TITLE: Average Case Complexity, Good Codes and SHA
SPEAKER: Charanjit S. Jutla , IBM Research
ABSTRACT: We show a search problem which is similar to inverting SHA on uniform distribution over its outputs to be average case hard for distributional search-NP. On the other hand we believe showing a problem to be one-way even based on average case NP-hardness seems unlikely. To this end, we define novel complexity classes Avg-NP and Avg-AM (not to be confused with distributional-NP and AM), and we show (following Akavia et al) that for pre-image size-verifiable functions f, if there is an oblivious randomized Turing reduction from average case inverting f to average case NP hard problem, then distribution NP is in Avg-co-AM ( a hardness assumption).
The second part of the talk will focus on why collision finding is easier than inversion problem. We characterize local-collision strategies, and prove that complexity of a general class of recent attacks strategies is related to the minimum weight of a linear code given as sum of two low density parity codes. We describe novel techniques to lower bound minimum weight of such low density parity codes, and argue that it leads to a good (computational) bound on finding low weight codeword in the sum of the two codes.
Obviously, the aim is to design a hash function, where this last argument can be made more rigorous, which is an open problem.
(joint work with Anindya Patthak)
Thursday June 7
TITLE: Mistyping in Password-assisted Key Exchange
SPEAKER: Vladimir Kolesnikov, Bell Labs
ABSTRACT: We study the problem of Key Exchange (KE), where authentication is in part based on human-supplied credentials, such as passwords and biometrics. In contrast with electronically stored credentials, such as secret keys, the former may be occasionally (in general, adversarily) mistyped. Our main contribution is the first formal treatment of mistyping in this setting.
Ensuring security in presence of mistyping is subtle. We show mistyping-related vulnerabilities of previous KE definitions and constructions.
We concentrate on the practical two-factor authenticated KE setting where servers exchange keys with clients, who use short passwords (memorized) and long cryptographic keys (stored on a card). Our work is thus a natural extension of Halevi-Krawczyk and Kolesnikov-Rackoff. We discuss the challenges that arise due to mistyping. We propose the
first KE definitions in this setting, and formally discuss their guarantees. We present efficient KE protocols and prove their security.
Thursday April 12,
TITLE: Pseudorandomness: New Results and Applications.
SPEAKER: Emanuele Viola, Institute for Advanced Studies, Princeton
ABSTRACT: Pseudorandomness is the theory that studies probability distributions that ``look random'' despite having little entropy. Besides addressing the philosophical problem of the nature of randomness, pseudorandomness has a striking variety of applications. For example, most modern cryptography relies
on pseudorandom distributions, and the study of pseudorandomness has led to several algorithmic breakthroughs, such as Reingold's space-efficient algorithm
for finding the exit from a given maze.
In this talk we survey some of our results in pseudorandomness, focusing on pseudorandom generators, which are objects that stretch a short truly random seed into a longer sequence that ``looks random.''
First we address cryptographic pseudorandom generators, interpreting ``looks random'' as ``random enough for cryptography.'' We present new trade-offs between the (parallel) complexity of the generator and its output length. Then
we move to special-purpose pseudorandom generators, interpreting ``looks random'' as ``looks random to a restricted computational model.'' We develop a new application of such generators to the study of the foundations of cryptography, specifically to the study of the average-case complexity of NP: We
show how to take any function in NP that is `mildly' hard on average and transform it into one that is `extremely' hard on average. Finally, we discuss some new state-of-the-art pseudorandom generators whose output looks random to constant-depth circuits and low-degree polynomials.
No previous knowledge of cryptography or complexity theory is required for this talk.
Thursday March 29th
TITLE: A Cryptographic Study of Secure Internet Measurement.
SPEAKER: David Xiao, Princeton University
ABSTRACT: The Internet is an indispensable part of our information society, 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, and then sketch a composition technique used to construct secure FL protocols out of secure FD protocols.
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. To conclude, we will discuss consequences of our results on the real-world development and deployment of secure Internet measurement.
This is joint work with Sharon Goldberg, Boaz Barak, and Jennifer
Rexford.
Thursday January 11,
TITLE: Encryption at the Speed of Light? Cryptanalysis of an
optical CDMA encryption scheme.
SPEAKER: Sharon Goldberg, Princeton University
ABSTRACT: Because optical signals operate at extremely high frequencies, it is practically infeasible to measure all of their information content. Optical encryption systems attempt leverage this fact in order to achieve extremely fast encryption speeds. However, despite the intense interest in this area in the optics community, to date there has been little contribution to this
area from the security and cryptanalysis community.
In this talk, we overview a non-trivial optical encryption system proposed by [R. Menendez et.al. J. Lightwave Technology, 2005] and others. While the scheme has the potential to perform encryption at extremely high speed, we present a cryptanalysis of the system that shows situations in which the key can be learned with only two known plaintexts.
Thursday November 30
TITLE: Plaintext awareness in the common random string model.
SPEAKER: Alex Dent, Royal Holloway U.
ABSTRACT: Plaintext awareness is a simple concept with a complicated technical explanantion. Conceptually, an encryption scheme is plaintext aware if every polynomial-time algorithm that outputs a ciphertext "knows" the corresponding plaintext. This means that a decryption oracle is essentially useless to an attacker and any plaintext aware scheme that is IND-CPA is also necessarily IND-CCA2 secure. The concept of plaintext awareness was originally defined for the random oracle model (Bellare, Desai, Pointcheval, Rogaway 1998) and later in the standard model (Bellare and Palacio 2004).
Unfortunately, all known schemes that satisfy the standard model definition of plaintext awareness require the use of non-standard extractor assumptions such as the Diffie-Hellman Knowledge of Exponant Assumption. These assumptions are not efficiently falsifiable and so should be avoided wherever possible.
In this talk we discuss the problems with defining a notion of plaintext awareness for the common random string model. It seems difficult to do this in general, but we show that a natural definition exists for encryption schemes with a certain structure. We show that several important encryption schemes in the literature already have this structure and satisfy our definition of plaintext awareness. Thus we not only propose a useful new definition, but also shed some light on the security of several existing algorithms.
Monday August 14
TITLE: Construction of a Non-Malleable Encryption Scheme from Any Semantically Secure One
SPEAKER: Vinod Vaikuntanathan, MIT
ABSTRACT: There are several candidate semantically secure encryption schemes, yet in many applications non-malleability of encryptions is crucial. We show how to transform any encryption scheme that is semantically secure against chosen-plaintext (CPA) attacks into one that is non-malleable for arbitrarily many messages, against CPA attacks.
Monday August 7
TITLE: Simulation-Based Security with Inexhaustible Interactive Turing Machines
SPEAKER: Ralf Küsters, University of Kiel, Germany.
ABSTRACT: Recently, there has been much interest in extending models for simulation-based security in such a way that the runtime of protocols may depend on the length of their input. Finding such extensions has turned out to be a non-trivial task. In this talk, we present a simple, yet expressive general computational model for systems of Interactive Turing Machines (ITMs) where the runtime of the ITMs may be polynomial per activation and may depend on the length of the input received. Based on our general computational model, we state different notions of simulation-based security in a uniform and concise way, including universal composability (UC) and black-box simulatability, study their relationships, and present a general composition theorem for composing a polynomial number of copies of protocols, where the polynomial is determined by the environment. The simplicity of our model is demonstrated by the fact that many of our results can be proved by mere equational reasoning based on a few equational principles on systems. This will be illustrated in the talk by the proof of the composition theorem in case of a constant number of protocols.
The talk is based on work presented at CSFW 2006.
Thursday July 27
TITLE: On Expected Constant-Round Protocols for Byzantine Agreement
SPEAKER: Chiu-Yuen Koo, University of Maryland, College Park
ABSTRACT: In a seminal paper, Feldman and Micali (STOC '88) show an $n$-party Byzantine agreement protocol tolerating $t < n/3$ malicious parties that runs in expected constant rounds. Here, we show an expected constant-round protocol for authenticated Byzantine agreement assuming honest majority (i.e., $t < n/2$), and relying only on the existence of a secure signature scheme and a public-key infrastructure (PKI). Combined with existing results, this gives the first expected constant-round protocol for secure computation with honest majority in a point-to-point network assuming only one-way functions and a PKI. Our key technical tool --- a new primitive we introduce called moderated VSS --- also yields a simpler proof of the Feldman-Micali result.
We also show a simple technique for sequential composition of protocols without simultaneous termination (something that is inherent for Byzantine agreement protocols using $o(n)$ rounds) for the case of $t<n/2$.
Joint work with Jonathan Katz.
Wednesday May 17
TITLE: On Basing One-Way Function on NP-Hardness
SPEAKER: Adi Akavia, MIT
ABSTRACT: One-way functions (i.e., polynomial-time computable functions that are hard to invert on the average case) are the cornerstone of modern cryptography. The hardness condition on the task of inverting a one-way function is an *average-case* complexity condition; this clearly implies a *worst-case* hardness condition. A puzzling question of fundamental nature is whether the necessary worst-case condition is also a sufficient one. In particular: Can one-way functions be based on NP-hardness? Namely, is there a reduction from a (worst case) NP-complete problem to the task of (average case) inverting a polynomial-time computable function?
We prove two results on the impossibility of basing one-way functions on NP-hardness. Both results hold under the (widely believed) complexity assumption that coNP is not contained in AM:
1. One-way functions cannot be based on NP-hardness via *non-adaptive* reductions (unless coNP is contained in AM).
2. Size-verifiable one-way functions cannot be based on NP-hardness via *any* (possibly *adaptive*) reduction (unless coNP is contained in AM); where we call f *size-verifiable* if given y, the number of pre-image $|f^{-1}(y)|$ is efficiently computable, or more generally, efficiently verifiable via an AM protocol.
Our results improve on previously known negative results of [Feigenbaum-Fortnow, Bogdanov-Trevisan] by (i) handling *adaptive* reductions (whereas previous works were essentially confined to *non-adaptive* reductions) and by (ii) relying on a seemingly weaker complexity assumption.
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 [Fortnow, Aiello-Hastad] works only in a settings 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 [Fortnow, 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
Thursday, April 27, 2006
SPEAKER: Shien Jin Ong (Harvard U.)
TITLE: Statistical Zero-Knowledge Arguments for NP from One-Way Functions
ABSTRACT:
We show that every language in NP has a statistical zero-knowledge argument system under the (minimal) complexity assumption that nonuniformly-secure one-way functions exist. In such protocols, even a computationally unbounded verifier cannot learn anything other than the fact that the assertion being proven is true, whereas a polynomial-time prover cannot convince the verifier to accept a false assertion except with negligible probability.
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 imply all the above 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).
Joint work with Minh-Huyen Nguyen and Salil Vadhan.
Thursday, March 16, 2006
SPEAKER: Leonid Reyzin (Boston U.)
TITLE: Upper and Lower Bounds on Black-Box Steganography
ABSTRACT:
We study the limitations of steganography when the sender is not using any properties of the underlying channel beyond its entropy and the ability to sample from it. On the negative side, we show that the number of samples the sender must obtain from the channel is exponential in the rate of the stegosystem. On the positive side, we present the first secret-key stegosystem that essentially matches this lower bound regardless of the entropy of the underlying channel. Furthermore, for high-entropy channels, we present the first secret-key stegosystem that matches this lower bound statelessly (i.e., without requiring synchronized state between sender and receiver).
Joint work with Nenad Dedic, Gene Itkis, and Scott Russell
Tuesday, March 14
SPEAKER: Amir Herzberg (Bar-Ilan U.)
TITLE: Preventing Spoofing, Phishing and Spamming by Secure Usability
ABSTRACT:
Spoofing, phishing and spamming are of the worst security problems in the Internet. We explain vulnerabilities of the current email and web systems, causing the prolifiration of such attacks. We then discuss some recent proposals to improving security against these threats and security systems: some of them promising, other less so. Some solutions involve secure usability, some use (simple) cryptographic protocols, and some involve both areas.
The talk does not require prior expertise in either cryptography or usability.
Friday March 3, 2006
SPEAKER: Hoeteck Wee (U. California Berkeley)
TITLE: Zero knowledge in the random oracle model, revisited
ABSTRACT:
We revisit previous formulations of zero knowledge in the random oracle model, due to Bellare and Rogaway (CCS '93) and Pass (Crypto '03), and present a hierarchy for zero knowledge that includes both of these formulations. The hierarchy relates to the programmability of the random oracle, previously studied by Nielsen (Crypto '02).
* We prove a subtle separation between the Bellare-Rogaway formulation and a weaker formulation, which refines the separation in Nielsen's work.
* We show that zero-knowledge according to each of these formulations is not preserved under sequential composition. We introduce stronger definitions wherein the adversary may receive auxiliary input that depends on the random oracle and establish closure under sequential composition for these definitions. We also present round-optimal protocols for NP satisfying the stronger requirements.
* Motivated by our study of zero knowledge, we introduce a new definition of proof of knowledge in the random oracle model that accounts for oracle-dependent auxiliary input. We show that two rounds of interaction are necessary and sufficient to achieve zero-knowledge proofs of knowledge according to this new definition, whereas one round of interaction is sufficient in previous definitions.
* Extending our work on zero knowledge, we present a hierarchy for circuit obfuscation in the random oracle model, the weakest being that achieved in the work of Lynn, Prabhakaran and Sahai (Eurocrypt '04). We show that the stronger notions capture precisely the class of circuits that is efficiently and exactly learnable under membership queries.
Thursday March 2, 2006
SPEAKER: Danny Harnik (Weizman Institute)
TITLE: On the power of the randomized iterate
ABSTRACT:
We consider two of the most fundamental theorems in Cryptography. The first, due to Haastad, Impagliazzo, Levin and Luby (known as HILL), is that pseudorandom generators can be constructed from any one-way function. The second, due to Yao in 1982, states that the existence of weak one-way functions implies the existence of full fledged one-way functions. The above reductions,however, are not as security preserving as one may desire. The main reason for the security deterioration is the input blow up in both of these constructions.
This work revisits a technique that we call the Randomized Iterate, produced by Goldreich, Krawczyk and Luby. Informally, the randomized iterate is a method that transfers any regular one-way function into a function that maintains its hardness through self iterations. The technique was used to give a construction of pseudorandom generators from regular one-way functions.
We simplify and strengthen this technique in order to obtain a similar reduction where the seed length of the resulting generators is as short as O(nlog n) rather than $\Omega(n^3)$ in the original proposed generator. We give a reduction with similar parameters for security amplification of regular one-way functions.
We also show that the randomized iterate may even be useful in the context of an arbitrary one-way function. In particular, we use the randomized iterate to replace the basic building block of the HILL construction. This modification improves the efficiency by an $O(n^3)$ factor and reduces the seed length by a factor of $n$ (which also implies improvement in the security of the construction).
Joint work with Iftach Haitner and Omer Reingold.
February 15, 2006
SPEAKER: Yevgeniy Dodis (NYU)
TITLE: On Extractors, Error-Correction and Hiding All Partial Information.
ABSTRACT:
Randomness extractors allow one to obtain nearly perfect randomness from highly imperfect sources randomness, which are only known to contain "scattered" entropy. Not surprisingly, such extractors have found numerous applications in many areas of computer science including cryptography. Aside from extracting randomness, a less known usage of extractors comes from the fact that they hide all deterministic functions of their (high-entropy) input: in other words, extractors provide certain level of privacy for the imperfect source that they use. In the latter kind of applications, one typically needs extra properties of extractors, such as invertibility, collision-resistance, error-correction or unforgeability.
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.
February 9, 2006
SPEAKER: Benjamin Arazi, Ben-Gurion University
TITLE: Self-referenced Public Key Cryptography
ABSTRACT:
In self-certified public key cryptographic applications, authenticity of parameters submitted by a user is implicitly established as a part of executing the application served by these parameters. Under the basic principle, secret values, embedded by the CA in issued users' keys, are subsequently processed together with the CA's public key during the implicit verification, closing a trust loop controlled by the CA. An extended version of self-certification, termed 'self-referenced' certification, pertaining to Diffie-Hellman key-establishment procedures, is introduced in this paper.
Here, Alice refers to the CA's public key prior to her communication with Bob, and based on her user keys. The loop controlled by the CA is closed by a session-key-confirmation. Alice's logic is then: "If my user keys are certified, and finally I have a confirmed joint session key with Bob, he is certified too, without referring to the CA's public key concerning values received from Bob". Beside its fundamental significance, self-referenced certification reduces on-line computational complexity. While the methodology is mainly suitable for the case where users rely on the same CA, the case of relying on different CAs is treated as well.
January 26, 2006
SPEAKER: Antonio Nicolosi (NYU)
TITLE: Non-Interactive Zero-Knowledge from Homomorphic Encryption
ABSTRACT: We propose a method for compiling a class of Sigma-protocols (3-move public-coin protocols) into non-interactive zero-knowledge arguments. The method is based on homomorphic encryption and _does not_ use random oracles. It only requires that a private/public key pair is set up for the verifier. The method applies to all known discrete-log-based Sigma-protocols.
As applications, we obtain non-interactive threshold RSA without random oracles, and non-interactive zero-knowledge for NP more efficiently than by previous methods.
To appear at TCC'06. Joint work with Ivan Damgaard and Nelly Fazio.
January 12, 2006.
SPEAKER: David Xiao, Princeton University
TITLE: Using sampling to get from one expander to another
ABSTRACT: Sampling is the problem of using randomness to approximate the average of a function. The Chernoff bound tells us that, by choosing a small random set S of inputs, we can estimate the average over the entire input domain with exponentially small probability of deviation. Usually the function considered is real-valued; Ahlswede-Winter showed that there is an analogue of the Chernoff bound for matrix-valued functions, i.e. functions mapping to real symmetric d x d matrices.
In this talk we will show how to improve the randomness-efficiency of sampling matrix-valued functions by taking the samples according to a random walk on an expander graph. This idea was introduced by Ajtai-Komlos-Szmeredi and was shown by Gillman to perform essentially as well as independent samples for real-valued functions. Our results thus extend both Ahlswede-Winter and Gillman.
We will then show how to apply this sampler to the problem of Alon-Roichman: given an arbitrary group H, find a set S of size O(log n) such that the Cayley graph Cay(H; S) is a good expander. Alon-Roichman showed this is possible by random sampling; we apply our sampler to get a poly-time deterministic algorithm.
Finally we will discuss the main ideas behind the proof that our sampler achieves exponentially small probability of deviation. Our main technical results relies on facts from perturbation theory, an interesting field of analysis that we believe may be relevant to theoretical computer scientists in other ways.
This is joint work with Avi Wigderson.
|
