Iftach Haitner

Publications 

• Iftach Haitner, Omer Reingold, and Salil Vadhan
  Efficiency Improvements in Constructions of Pseudorandom Generators from One-way Functions
  Annual ACM Symposium on Theory of Computing (STOC), 2010.
  [Abstract]

  We give a new construction of pseudorandom generators from any one-way function. The construction achieves better parameters and is simpler than that given in the seminal work of Håstad, Impagliazzo, Levin and Luby [SICOMP '99]. The key to our construction is a new notion of next-block pseudoentropy, which is inspired by the notion of ``inaccessible entropy'' recently introduced in [Haitner, Reingold, Vadhan and Wee STOC '09]. An additional advantage over all previous constructions is that our pseudorandom generators are highly parallelizable and invoke the one-way function in a non-adaptive manner. Using [Applebaum, Ishai and Kushilevitz SICOMP '06], this implies the existence of pseudorandom generators in NC⁰ based on the existence of one-way functions in NC¹.

• Boaz Barak, Iftach Haitner, Dennis Hofheinz and Yuval Ishai
  Bounded Key-Dependent Message Security
  To appear in Advances in Cryptology - Eurocrypt, 2010.
  [Abstract] [PDF]

  We construct the first public-key encryption scheme that is proven secure (in the standard model,
  under standard assumptions) even when the attacker gets access to encryptions of arbitrary
  efficient functions of the secret key. Specifically, under either the DDH or LWE assumption, for
  every polynomials L and N we obtain a public-key encryption scheme that resists key-dependent
  message (KDM) attacks for up to N(k) public keys and functions circuit size up to
  L(k), where k denotes the size of the secret key. We call such a scheme bounded KDM
  secure. Moreover, we show that our scheme suffices for one of the important applications of KDM
  security: ability to securely instantiate symbolic protocols with axiomatic proofs of security.
  
  We also observe that any fully homomorphic encryption scheme which additionally enjoys circular
  security and circuit privacy is fully KDM secure in the sense that the encryption and
  decryption algorithms can be independent of the polynomials L and N as above. Thus, the recent
  fully homomorphic encryption scheme of Gentry (STOC 2009) is fully KDM secure under certain
  non-standard hardness assumptions.
  
  Previous works obtained either full KDM security in the random oracle model
  (Black et al., SAC 2002) or security with respect to a very restricted class of
  functions (e.g., clique/circular security and affine functions, Boneh et al., CRYPTO 2008,
  and Applebaum et al., CRYPTO 2009).
  
  Our main result is based on a combination of the circular-secure encryption scheme of either
  Boneh et al. or Applebaum et al. with Yao's garbled circuit construction.
  
  Finally, we extend the impossibility result of Haitner and Holenstein (TCC 2009), showing that it
  is impossible to prove KDM security against a family of query functions that contains exponentially
  hard pseudorandom functions, using only black-box access to the query function and the
  adversary attacking the scheme. This proves that the non-black-box usage of the query function in
  our proof of security makes to the KDM query function is inherent.

• Iftach Haitner, Omer Reingold, Salil Vadhan and Hoeteck Wee
  Universal One-Way Hash Functions via Inaccessible Entropy
  To appear in Advances in Cryptology - Eurocrypt, 2010.
  [Abstract]

  This paper revisits the construction of Universally One-Way Hash Functions (UOWHFs) from any one-way function due to Rompel (STOC 1990). We give a simpler construction of UOWHFs which also obtains better efficiency and security. The construction exploits a strong connection to the recently introduced notion of inaccessible entropy (Haitner et al. STOC 2009). With this perspective, we observe that a small tweak of any one-way function f is already a weak form of a UOWHF: Consider F(x,i) that outputs the i-bit long prefix of f(x). If F were a UOWHF then given a random x and i it would be hard to come up with x' ≠ x such that F(x,i)=F(x',i). While this may not be the case, we show (rather easily) that it is hard to sample x' with almost full entropy among all the possible such values of x'. The rest of our construction simply amplifies and exploits this basic property.
  
  With this and other recent works we have that the constructions of three fundamental cryptographic primitives (Pseudorandom Generators, Statistically Hiding Commitments and UOWHFs) out of one-way functions are to a large extent unified. In particular, all three constructions rely on and manipulate computational notions of entropy in similar ways. Pseudorandom Generators rely on the well-established notion of pseudoentropy, whereas Statistically Hiding Commitments and UOWHFs rely on the newer notion of inaccessible entropy.

• Iftach Haitner, Mohammad Mahmoody and David Xiao
  A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of NP
  Manuscript, 2009.
  [Abstract]  [PDF]

  We investigate the question of what languages can be decided efficiently with the help of a
  recursive collision-finding oracle. Such an oracle can be used to break collision-resistant hash
  functions or, more generally, statistically hiding commitments. The oracle we consider Sam_d,
  where d is the recursion depth, is based on the identically-named oracle defined in the work of
  Haitner et al. (FOCS '07). Our main result is a constant-round public-coin protocol AM-Sam
  that allows an efficient  verifier to emulate a Sam_d oracle for any constant depth d = O(1) with the
  help of a BPP^NP prover. AM-Sam allows us to conclude that if L is decidable by a k-adaptive
  randomized oracle algorithm with access to a  Sam_O(1) oracle, then L∈AM[k]∩coAM[k].
  The above yields the following corollary: assume there exists an O(1)-adaptive reduction that
  bases constant-round statistically hiding commitment on NP-hardness, then NP ⊆ coAM and
  the polynomial hierarchy collapses. The same result holds for any primitive that can be broken
  by Sam_O(1) including collision-resistant hash functions and O(1)-round oblivious transfer where
  security holds statistically for one of the parties. We also obtain non-trivial (though weaker)
  consequences for k-adaptive reductions for any k = poly(n). Prior to our work, most results in
  this research direction either applied only to non-adaptive reductions (Bogdanov and Trevisan,
  SIAM J. of Comp. '06) or to primitives with special regularity properties (Brassard FOCS '79,
  Akavia et al., FOCS '06).
  The main technical tool we use to prove the above is a new constant-round public-coin
  protocol (SampleWithSize) that we believe may be interesting in its own right, and that guarantees the following. Given an efficient function f on n bits, let D be the output distribution
  D = f(U_n), then SampleWithSize allows an efficient verifier Arthur to use an all-powerful prover
  Merlin's help to sample a random y ← D along with a good multiplicative approximation of the
  probability p_y = Pr_{y' ← D}[y' = y]. The crucial feature of SampleWithSize is that it extends even
  to distributions of the form D = f(U_S), where U_S is the uniform distribution on an efficiently
  decidable subset S ⊆{0.1}ⁿ (such D are called efficiently samplable with post-selection), as
  long as the verifier is also given a good approximation of the value |S|.

• Iftach Haitner
  A Parallel Repetition Theorem for Any Interactive Argument
  IEEE Symposium on Foundations of Computer Science (FOCS), 2009.
  Invited to the FOCS 2009 special issue of SICOMP
  [Abstract] [PDF] [Slides]
  Draft of full version [PDF]

  The question whether or not parallel repetition reduces the soundness error is a fundamental question in the theory of protocols. While parallel repetition reduces (at an exponential rate) the error in interactive proofs and (at a weak exponential rate) in special cases of interactive arguments (e.g., 3-message protocols - Bellare, Impagliazzo and Naor [FOCS '97], and public-coin protocols - Håstad, Pass, Pietrzak and WikstrÄom [Manuscript '08]), Bellare et. al gave example of interactive arguments for which parallel repetition does not reduce the soundness error at all.
  We show that by slightly modifying any interactive argument, in a way that preserves its completeness and only slightly deteriorates its soundness, we get a protocol for which parallel repetition does reduce the error at a weak exponential rate. In this modified version, the verifier flips at the beginning of each round an (1 - (1/4m), 1/4m) biased coin (i.e., 1 is tossed with probability 1/4m), where m is the round complexity of the (original) protocol. If the coin is one, the verifier halts the interaction and accepts, otherwise it sends the same message that the original verifier would. At the end of the protocol (if reached), the verifier accepts if and only if the original verifier would.

• Iftach Haitner, Omer Reingold, Salil Vadhan and Hoeteck Wee
  Inaccessible Entropy
  Annual ACM Symposium on Theory of Computing (STOC), 2009.
  [Abstract] [PDF] [Slides] [Video (appx. 1 hour)]
  Draft of full version [PDF]

  We put forth a new computational notion of entropy, which measures the
  (in)feasibility of sampling high entropy strings that are consistent with a
  given protocol. Specifically, we say that the i’th round of a protocol
  (A,B) has accessible entropy at most k, if no polynomial-time strategy
  A* can generate messages for A such that the entropy of its message in the i’th round has entropy greater than k when conditioned both on prior
  messages of the protocol and on prior coin tosses of A*. As applications of this notion, we

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

• Iftach Haitner, Alon Rosen and Ronen Shaltiel
  On the (Im)Possibility of Arthur-Merlin Witness Hiding Protocols
  Theory of Cryptography Conference (TCC), 2009.
  [Abstract] [PDF] [Slides]

  The concept of witness-hiding suggested by Feige and Shamir is a natural relaxation of zero-knowledge. In this paper we identify languages and distributions for which many known constant-round public-coin protocols with negligible soundness cannot be shown to witness-hiding using black-box techniques.
  
  In particular, our results imply that it is impossible to prove that parallel repetition of 3-Colorability or Hamiltonicity is witness-hiding for distributions that support instances with exactly one witness, if the proof of security is by a black-box reduction that is independent of the choice of the commitment scheme used in the protocol. This lower bound conceptually matches an upper bound of Feige and Shamir that uses such a black-box reduction to show that parallel repetition of 3-Colorability or Hamiltonicity is witness-hiding for distributions with ``two independent witnesses.
  
  We also consider black-box reductions for 3-Colorability or Hamiltonicity that depend on a specific implementation of the commitment scheme. While we cannot rule out such reductions completely, we show that ``natural reductions" cannot bypass the limitations above.
  
  Our proofs use techniques developed by Goldreich and Krawczyk for the case of zero knowledge. The setup of witness-hiding, however, presents new technical and conceptual difficulties that do not come up in the setup of zero-knowledge. The high level idea is that if a black-box reduction establishes the witness-hiding property for a protocol that is also a proof of knowledge, then this latter property can be used ``against the reduction" to find witnesses unconditionally.

• Iftach Haitner and  Thomas Holenstein
  On the (Im)Possibility of Key Dependent Encryption
  Theory of Cryptography Conference (TCC), 2009.
  [Abstract] [PDF] [Slides]
  Draft of full version [PDF]

  We study the possibility of constructing encryption schemes secure
  under messages that are chosen depending on the key k of the
  encryption scheme itself. We give the following separation results that
  hold both in the private and in the public key settings:

  • Let H be the family of poly(n)-wise independent
    hash-functions. There exists no fully-black-box reduction from an
    encryption scheme secure against key-dependent messages to one-way
    permutations (and also to families of trapdoor permutations) if the
    adversary can obtain encryptions of h(k) for h ∈ H.
  •  There exists no reduction from an encryption scheme secure
    against key-dependent messages to, essentially, any
    cryptographic assumption, if the adversary can obtain an encryption
    of g(k) for an arbitrary g, as long as the reduction's
    proof of security treats both the adversary and the function g as
    black boxes.

• Iftach Haitner
  New Implications and Improved Efficiency of Constructions Based on One-way Functions
  PhD. Thesis, 2008. [PDF]

• Iftach Haitner
  Semi-Honest to Malicious Oblivious Transfer - The Black-Box Way
  Theory of Cryptography Conference (TCC), 2008.
  [Abstract] [PDF] [Slides]

  Until recently, all known constructions of oblivious transfer protocols based on general hardness assumptions had the following form. First, the hardness assumption is used in a black-box manner (i.e., the construction uses only the input/output behavior of the primitive guaranteed by the assumption) to construct a semi-honest oblivious transfer, a protocol whose security is guaranteed to hold only against adversaries that follow the prescribed protocol. Then, the latter protocol is ``compiled" into a (malicious) oblivious transfer using non-black techniques (a Karp reduction is carried in order to prove an NP statement in zero-knowledge). In their recent breakthrough result, Ishai, Kushilevitz, Lindel and Petrank (STOC '06) deviated from the above paradigm, presenting a black-box reduction from oblivious transfer to enhanced trapdoor permutations and to homomorphic encryption. Here we generalize their result, presenting a black-box reduction from oblivious transfer to semi-honest oblivious transfer. Consequently, oblivious transfer can be black-box reduced to each of the hardness assumptions known to imply a semi-honest oblivious transfer in a black-box manner. This list currently includes beside the hardness assumptions used by Ishai et al. also the existence of families of dense trapdoor permutations and of non trivial single-server private information retrieval.

• Iftach Haitner, Jonathan J. Hoch and  Gil Segev
  A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval
  Theory of Cryptography Conference (TCC), 2008.
  [Abstract] [PDF] [Slides]

  We study the communication complexity of single-server Private Information Retrieval (PIR) protocols that are based on fundamental cryptographic primitives in a black-box manner. In this setting, we establish a tight lower bound on the number of bits communicated by the server in any polynomially-preserving construction that relies on trapdoor permutations. More specifically, our main result states that in such constructions Ω(n) bits must be communicated by the server, where n is the size of the server's database, and this improves the Ω(n / log n) lower bound due to Haitner, Hoch, Reingold and Segev (FOCS '07). Therefore, in the setting under consideration, the naive solution in which the user downloads the entire database turns out to be optimal up to constant multiplicative factors. We note that the lower bound we establish holds for the most generic form of trapdoor permutations, including in particular enhanced trapdoor permutations.
  
  Technically speaking, this paper consists of two main contributions from which our lower bound is obtained. First, we derive a tight lower bound on the number of bits communicated by the sender during the commit stage of any black-box construction of a statistically-hiding bit-commitment scheme from a family of trapdoor permutations. This lower bound asymptotically matches the upper bound provided by the scheme of Naor, Ostrovsky, Venkatesan and Yung (CRYPTO '92). Second, we improve the efficiency of the reduction of statistically-hiding commitment schemes to low-communication single-server PIR, due to Beimel, Ishai, Kushilevitz and Malkin (STOC '99). In particular, we present a reduction that essentially preserves the communication complexity of the underlying single-server PIR protocol.

• Iftach Haitner, Jonathan J. Hoch, Omer Reingold and Gil Segev
  Finding Collisions in Interactive Protocols -- A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments
  IEEE Symposium on Foundations of Computer Science (FOCS), 2007.
  [Abstract] [PDF] [Slides]
  Draft of full version [PDF]

  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.

• Iftach Haitner, Minh-Huyen Nguyen, Shien Jin Ong, Omer Reingold and Salil Vadhan
  Statistically-Hiding Commitments and Statistical Zero-Knowledge Arguments from Any One-Way Function
  To appear in SIAM Journal of Computing (SICOMP), STOC 2007 special issue.
  [Abstract] [PDF]

  We give a construction of statistically hiding commitment schemes (ones where the hiding property holds against even computationally unbounded adversaries) under the minimal complexity assumption that one-way functions exist. Consequently, one-way functions suffice to give statistical zero-knowledge arguments for any NP statement (whereby even a computationally unbounded adversarial verifier learns nothing other than the fact the assertion being proven is true, and a polynomial-time adversarial prover cannot convince the verifier of a false statement). These results resolve an open question posed by Naor, Ostrovsky, Venkatesan, and Yung (CRYPTO `92, J. Cryptology `98).

• Iftach Haitner and Omer Reingold
  Statistically Hiding Commitment from Any One-Way Function
  Annual ACM Symposium on Theory of Computing (STOC), 2007.
  Invited to the STOC 2007 special issue of SICOMP
  [Abstract] [PDF] [Slides]

  We give a construction of statistically-hiding commitment schemes (ones where the hiding property holds information theoretically), based on the minimal cryptographic assumption that one-way functions exist. Our construction employs two-phase commitment schemes, recently constructed by Nguyen, Ong and Vadhan (FOCS `06), and universal one-way hash functions introduced and constructed by Naor and Yung (STOC `89) and Rompel (STOC `90).

• Iftach Haitner and Omer Reingold
  A New Interactive Hashing Theorem
  IEEE Conference on Computational Complexity  (CCC), 2007.
  [Abstract] [PDF] [Slides]
  Draft of full version [PDF]

  Interactive hashing, introduced by Naor, Ostrovsky, Venkatesan and Yung (CRYPTO '92), plays an important role in many cryptographic protocols. In particular, interactive hashing is a major component in all known constructions (which are based on general one-way permutations and one-way functions) of statistically hiding commitment schemes and of statistical zero-knowledge arguments. Interactive hashing with respect to a one-way permutation f, is a two-party protocol that enables a sender that knows y=f(x) to transfer a random hash z=h(y) to a receiver. The receiver is guaranteed that the sender is committed to y (in the sense that it cannot come up with x and x' such that f(x) ≠ f(x'), but h(f(x))=h(f(x'))=z). The sender is guaranteed that the receiver does not learn any additional information on y. In particular, when h is a two-to-one hash function, the receiver does not learn which of the two preimages {y,y'}=h^-1(z) is the one the sender can invert with respect to f.
  
  This paper reexamines the notion of interactive hashing. We give an alternative proof for the Naor et al. protocol, which seems significantly simpler and more intuitive than the original one. Moreover, the new proof achieves much better parameters (in terms of how security preserving the reduction is). Finally, by applying our new proof to a close variant of the Naor et al. protocol, we achieve a more versatile interactive hashing theorem for a more general setting than that of the Naor et al. protocol.

  sssss

• Iftach Haitner, Danny Harnik and Omer Reingold
  On the Power of the Randomized Iterate
  Advanced in Cryptology - CRYPTO, 2006.
  [Abstract] [PDF] [Slides]
  Winner of best paper award CRYPTO 2006
  Draft of full version [PDF]

  We consider two of the most fundamental theorems in Cryptography. The first, due to Håstad, Impagliazzo, Levin and Luby (STOC '89, STOC '90, SIAM J. on Computing '99), is that pseudorandom generators can be constructed from any one-way function. The second, due to Yao (FOCS '82), states that the existence of weak one-way functions implies the existence of full fledged one-way functions. These powerful plausibility results shape our understanding of hardness and randomness in Cryptography, but unfortunately their proofs are not as tight (i.e., security preserving) as one may desire.
  
  This work revisits a technique that we call the randomized iterate, introduced by Goldreich, Krawczyk and Luby (SIAM J. on Computing '93). This technique was used by Goldreich et al. to give a construction of pseudorandom generators from regular one-way functions. We simplify and strengthen this technique in order to obtain a similar construction where the seed length of the resulting generators is as short as Θ(n log n) rather than Θ(n³) achieved by Goldreich et al. Our technique has the potential of implying seed-length Θ(n), and the only bottleneck for such a result is the parameters of current generators against space bounded computations. We give a construction with similar parameters for security amplification of regular one-way functions. This improves upon the construction of Goldreich, Impagliazzo, Levin, Venkatesan and Zuckerman (FOCS '90) in that the construction does not need to ``know" the regularity parameter of the functions (in terms of security, the two reductions are incomparable). In addition, we use the randomized iterate to show a construction of a pseudorandom generator based on an exponentially hard one-way function that has seed length of only Θ(n²). This improves a recent result of Holenstein (TCC '06) that shows a construction with seed length Θ(n⁵) based on such one-way functions. Finally, we show that the randomized iterate may even be useful in the general context of Håstad et al. In particular, we use the randomized iterate to replace the basic building block of the Håstad et al. construction. Interestingly, this modification improves efficiency by an n³ factor and reduces the seed length to Θ(n⁷) (which also implies improvement in the security of the construction).

• Iftach Haitner, Danny Harnik and Omer Reingold
  On Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions
  International Colloquium on Automata, Languages and Programming - ICALP, 2006.
  Winner of best paper award ICALP 2006 track C
  [Abstract] [PDF] [Slides]

  We show a construction of a pseudorandom generator from any exponentially hard one-way function with a blowup of only Θ(n²). This Improves the recent Θ(n⁵) construction of Holenstein (TCC '06). Our technique uses the tools recently presented in Haitner et al. (Crypto '06) for the setting of regular one-way functions, and further develops them.

• Iftach Haitner, Omer Horvitz, Jonathan Katz, Chiu-Yuen Koo, Ruggero Morselli and Ronen Shaltiel
  Reducing Complexity Assumptions for Statistically-Hiding Commitment
  Journal of Cryptology 2009. [PDF]
  Advances in Cryptology - Eurocrypt, 2005.
  [Abstract] [PDF] [Slides]

  We revisit the following question: what are the minimal assumptions needed to construct statistically-hiding commitment schemes? Naor et al. show how to construct such schemes based on any one-way permutation. We improve upon this by showing a construction based on any approximable preimage-size one-way function. These are one-way functions for which it is possible to efficiently approximate the number of pre-images of a given output. A special case is the class of regular one-way functions where all points in the image of the function have the same (known) number of pre-images.
  
  We also prove two additional results related to statistically-hiding commitment. First, we prove a (folklore) showing, roughly speaking, that the statistical hiding property of any such commitment scheme is amplified exponentially when multiple independent parallel executions of the scheme are carried out. Second, we show a compiler which transforms any commitment scheme which is statistically hiding against an honest-but-curious receiver into one which is statistically hiding even against a malicious receiver.

• Iftach Haitner
  Implementing Oblivious Transfer Using a Collection of Dense Trapdoor Permutations
  Theory of Cryptography Conference (TCC), 2004.
  [Abstract] [PDF] [Slides]
  Draft of full version [PDF]

  Until recently, the existence of family of trapdoor permutations (TDP) was believed (and claimed) to imply oblivious transfer. It was recently realized, however, that the commonly accepted general definition of TDP needs to be strengthened slightly in order to make the security proofs of TDP-based oblivious transfer go through. The strengthening is in the ``security" requirement of the TDP (i.e., the hardness to invert condition). Here we present an alternative construction that only requires the TDP to have ``dense domains". Specifically we present an implementation of oblivious transfer based on any dense TDP.