Iftach Haitner יפתח הייטנר

Publications
in Reverse Chronological Order

• Itay Berman and Iftach Haitner
  From Non-Adaptive to Adaptive Pseudorandom Functions [Abstract] 
  TCC 2012 [PDF]

Unlike the standard notion of pseudorandom functions (PRF), a non-adaptive PRF is only required to be indistinguishable from a random function in the eyes of a non-adaptive distinguisher (i.e., one that prepares its oracle calls in advance). A recent line of research has studied the possibility of a direct construction of adaptive PRFs from non-adaptive ones, where direct means that the constructed adaptive PRF uses only few (ideally, constant number of) calls to the underlying non-adaptive PRF. Unfortunately, this study has only yielded negative results, showing that ``natural" such constructions are unlikely to exist (e.g.,  Myers [EUROCRYPT '04], Pietrzak [CRYPTO '05, EUROCRYPT '06]).

We give an affirmative answer to the above question, presenting a direct construction of adaptive PRFs from non-adaptive ones. The suggested construction is extremely simple, a composition of the non-adaptive PRF with an appropriate pairwise independent hash function.

• Iftach Haitner and Eran Omri 
  Coin Flipping with Constant Bias Implies One-Way Functions [Abstract]  [Slides] 
  FOCS 2011 [PDF]
  Draft of full version [PDF]

It is well known (c.f., Impagliazzo and Luby [FOCS '89]) that the existence of almost all ``interesting" cryptographic applications, i,e., ones that cannot hold information theoretically, implies one-way functions. An important exception where the above implication is not known, however, is the case of coin-flipping protocols. Such protocols allow honest parties to mutually flip an unbiased coin, while guaranteeing that even a cheating (efficient) party cannot bias the output of the protocol by much. While Impagliazzo and Luby proved that coin-flipping protocols that are safe against negligible bias do imply one-way functions, and, very recently, Maji, Prabhakaran, and Sahai [FOCS '10] proved the same for constant-round protocols (with any non-trivial bias). For the general case, however, no such implication was known.
We make progress towards answering the above fundamental question, showing that (strong) coin-flipping protocols safe against a constant bias (concretely, \frac{\sqrt2 -1}2 - o(1)) imply one-way functions.

• Yevgeniy Dodis, Iftach Haitner and Aris Tentes
  On the Instantiability of Hash-and-Sign RSA Signatures [Abstract] [Slides] 
  TCC 2012 [PDF]
  Draft of full version [PDF]

The hash-and-sign RSA signature is one of the most elegant and well known signatures schemes, extensively used in a wide variety of cryptographic applications. Unfortunately, the only existing analysis of this popular signature scheme is in the random oracle model, where the resulting idealized signature is known as the RSA Full Domain Hash signature scheme (RSA-FDH). In fact, prior work has shown several ``uninstantiability'' results for various abstractions of RSA-FDH, where the RSA function was replaced by a family of trapdoor random permutations, or the hash function instantiating the random oracle could not be keyed. These abstractions, however, do not allow the reduction and the hash function instantiation to use the algebraic properties of RSA function, such as the multiplicative group structure of Z_n*. In contrast, the multiplicative property of the RSA function is critically used in many standard model analyses of various RSA-based schemes.

Motivated by closing this gap, we consider the setting where the RSA function representation is generic (i.e., black-box) but multiplicative, whereas the hash function itself is in the standard model, and can be keyed and exploit the multiplicative properties of the RSA function. This setting abstracts all known techniques for designing provably secure RSA-based signatures in the standard model, and aims to address the main limitations of prior uninstantiability results. Unfortunately, we show that it is still impossible to reduce the security of RSA-FDH to any natural assumption even in our model. Thus, our result suggests that in order to prove the security of a given instantiation of RSA-FDH, one should use a non-black box security proof, or use specific properties of the RSA group that are not captured by its multiplicative structure alone.

We complement our negative result with a positive result, showing that the RSA-FDH signatures can be proven secure under the standard RSA assumption, provided that the number
of signing queries is a-priori bounded.

• Iftach Haitner, Yuval Ishai, Eyal Kushilevitz, Yehuda Lindell and Erez Petrank
  Black-Box Constructions of Protocols for Secure Computation [Abstract] 
  SIAM Journal of Computing 2011 [PDF]

It is well known that secure computation without an honest majority requires computational assumptions. An interesting question that therefore arises relates to the way such computational assumptions are used. Specifically, can the secure protocol use the underlying primitive (e.g., a one-way trapdoor permutation) in a black-box way, treating it as an oracle, or must it be non-black-box (by referring to the code that computes the primitive)?
Despite the fact that many general constructions of cryptographic schemes refer to the underlying primitive in a black-box way only, there are some constructions that are inherently nonblack-box. Indeed, all known constructions of protocols for general secure computation that are secure in the presence of a malicious adversary and without an honest majority use the underlying primitive in a nonblack-box way (requiring to prove in zero-knowledge statements that relate to the primitive).
In this paper, we study whether such nonblack-box use is essential. We answer this question in the negative. Concretely, we present a fully black-box reduction from oblivious transfer with security against malicious parties to oblivious transfer with security against semi-honest parties. As a corollary, we get the first constructions of general multiparty protocols (with security against malicious adversaries and without an honest majority) which only make a black-box use of semi-honest oblivious transfer, or alternatively a black-box use of lower-level primitives such as enhanced trapdoor permutations or homomorphic encryption.

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

  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 [Abstract]
  Advances in Cryptology - Eurocrypt, 2010 [PDF]
  Draft of full version [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, Thomas Holenstein, Omer Reingold, Salil Vadhan and Hoeteck Wee
  Universal One-Way Hash Functions via Inaccessible Entropy [Abstract]
  Advances in Cryptology - Eurocrypt, 2010 [PDF]
  Draft of full version [PDF]  

  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 [Abstract]
  IEEE Conference on Computational Complexity  (CCC), 2010 [PDF] 
  Draft of full version [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 [Abstract] [Slides]
  IEEE Symposium on Foundations of Computer Science (FOCS), 2009 [PDF]
  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, Minh-Huyen Nguyen, Shien Jin Ong, Omer Reingold and Salil Vadhan
  Statistically Hiding Commitments and Statistical Zero-Knowledge Arguments from Any One-Way Function [Abstract]
  SIAM Journal of Computing 2009 [PDF]

• Iftach Haitner, Omer Reingold, Salil Vadhan and Hoeteck Wee
  Inaccessible Entropy [Abstract] [Slides] [Video (appx. 1 hour)]
  Annual ACM Symposium on Theory of Computing (STOC), 2009 [PDF]
  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 [Abstract] [Slides]
  Theory of Cryptography Conference (TCC), 2009 [PDF]

  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 [Abstract] [Slides]
  Theory of Cryptography Conference (TCC), 2009 [PDF]
  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 [Abstract] [Slides]
  Theory of Cryptography Conference (TCC), 2008  [PDF]
  Full version is part of [Black-Box Constructions of Protocols for Secure Computation]

  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 [Abstract]  [Slides]
  Theory of Cryptography Conference (TCC), 2008 [PDF]

  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
  [Abstract] [Slides]
  IEEE Symposium on Foundations of Computer Science (FOCS), 2007 [PDF]
  Draft of full version [PDF]

• Iftach Haitner and Omer Reingold
  Statistically Hiding Commitment from Any One-Way Function [Abstract] [Slides]
  Annual ACM Symposium on Theory of Computing (STOC), 2007 [PDF]
  Full version is part of [Statistically Hiding Commitments and Statistical Zero-Knowledge Arguments from Any One-Way Function]

  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 [Abstract] [Slides]
  IEEE Conference on Computational Complexity  (CCC), 2007 [PDF]
  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 [Abstract] [Slides]
  SIAM Journal of Computing 2011 [PDF] 
  Advanced in Cryptology - CRYPTO, 2006 [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..r>
  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 [Abstract] [Slides]
  International Colloquium on Automata, Languages and Programming - ICALP, 2006 [PDF]

  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 [Abstract] [Slides]
  Journal of Cryptology 2009 [PDF]
  Advances in Cryptology - Eurocrypt, 2005 [PDF]

  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 [Abstract] [Slides]
  Theory of Cryptography Conference (TCC), 2004 [PDF]
  Draft of full version [PDF]