Publications
in Reverse Chronological Order

Itay Berman and Iftach Haitner and
Aris Tentes
Coin Flipping of Any Constant Bias Implies OneWay
Functions
[Abstract]
[Slides]
STOC 2014
[PDF]
We show that the existence of a coinflipping protocol safe against any nontrivial constant bias (e.g., .499), implies the existence of one
way functions. This improves upon a recent result of Haitner and Omri [FOCS ’11], who proved this implication for protocols with bias √ 2−^{1}⁄_{2} ~.207. Unlike the result of Haitner and Omri, our result holds also for
weak coinflipping protocols.

Iftach Haitner and Eliad Tsfadia An
AlmostOptimally Fair ThreeParty CoinFlipping Protocol [Abstract]
STOC 2014
[PDF]
In a multiparty, fair coinflipping protocol, the parties output a common
(close to) unbiased bit, even when some corrupted parties try to bias the
output. Cleve [STOC 1986] has shown that in the
case of dishonest majority (i.e., at least half of the parties can be
corrupted), the corrupted parties can bias the honest parties common output bit
by Ω(1/m), in any
mround, coinflipping protocol. For more than two decades,
however, the best known coinflipping protocols had bias
Θ(t/√ m) against
dishonest majority, where t is the number of corrupted parties. This was changed
by a recent breakthrough result of Moran et al. [TCC 2009], who constructed an
mround, twoparty coinflipping protocol with optimal bias
Θ(1/m). Where in a
subsequent work, Beimel et al. [Crypto 2010] extended this result for the
multiparty case, in which less than
^{2}⁄_{3} of the parties can be corrupted. More
specifically, for any t <
^{2}⁄_{3}
· k, they presented an mround,
kparty protocol,
with bias Θ( 2^{2t−k}/m) against (up to) t corrupted parties. Still for the case
^{2}⁄_{3} (or more) corrupted parties, the best known protocol had bias
Θ(t/√ m). In
particular, this was the state of affairs for the natural threeparty case
(against two corrupted parties).
We make a step towards eliminating the above gap, presenting an
mround, threeparty, coinflipping protocol, with bias
O(log 2 m)/m. Our
approach (which we also apply for the twoparty case), does not follow the
“threshold round” paradigm used in the work of Moran et al. and Beimel et al.,
but rather is a takeoff of the majority protocol of Cleve (used to obtain the
Θ(t/√ m )bias protocol, mentioned above).

Iftach Haitner,
Jonathan J.
Hoch,
Omer
Reingold
and Gil Segev
Finding Collisions in Interactive Protocols — Tight
Lower Bounds on the Round Complexity and Communication
Complexity of Statistically Hiding Commitments [Abstract]
Manuscript 2013
[PDF]
We study the round complexity and communication complexity of various cryptographic protocols. We give tight lower bounds on the round complexity and
communication complexity of any fully blackbox reduction of a statistically
hiding commitment scheme from oneway permutations, and from trapdoor permutations. As a corollary, we derive similar
tight lower bounds for several other cryptographic protocols, such as
singleserver private information retrieval, interactive hashing, and oblivious
transfer that guarantees statistical security for one of the parties. Our techniques extend the collisionfinding oracle due to Simon (EUROCRYPT ’98) to the setting of
interactive protocols, and the reconstruction paradigm of Gennaro and Trevisan (FOCS ’00).

Itay Berman and Iftach Haitner and Ilan Komargodski
and Moni Naor
Hardness Preserving Reductions via Cuckoo Hashing
[Abstract]
TCC 2013
[PDF]
Draft of full version
[PDF]
A common method for increasing the usability and uplifting the security of
pseudorandom function families (PRFs) is to “hash” the inputs into a smaller
domain before applying the PRF.
This approach, known as “Levin’s trick”, is used to achieve “PRF domain
extension” (using a short, e.g., fixed, input length PRF to get a
variablelength PRF), and more recently to transform
nonadaptive PRFs to adaptive ones. Such reductions, however, are vulnerable to
a “birthday attack”: after √U queries to the resulting
PRF, where U being the hash function range, a
collision (i.e., two distinct inputs have the same hash value) happens with high
probability. As a consequence, the resulting PRF is insecure against an attacker
making this number of queries.
In this work we show how to go beyond the birthday attack barrier, by replacing
the above simple hashing approach with a variant of cuckoo hashing
— a hashing paradigm typically used
for resolving hash collisions in a table, by using two hash functions and two
tables and cleverly assigning each element into one of the two tables. We use
this approach to obtain:
(i) A domain extension method that requires just two calls to
the original PRF, can withstand as many queries as the original domain size and
has a distinguishing probability that is exponentially small in the non
cryptographic work.
(ii) A securitypreserving reduction from nonadaptive to
adaptive PRFs.

Iftach Haitner and
Eran Omri
and Hila Zarosim
Limits on the Usefulness of
Random Oracles [Abstract]
TCC 2013
[PDF] Draft of full version
[PDF]
In the random oracle model, parties are given oracle access
to a random function (i.e., a uniformly chosen function from the set of all
functions), and are assumed to have unbounded computational power (though they
can only make a bounded number of oracle queries). This model provides powerful
properties that allow proving the security of many protocols, even such that
cannot be proved secure in the standard model (under any hardness assumption).
The random oracle model is also used for showing that a given cryptographic
primitive cannot be used in a blackbox way to construct another primitive; in
their seminal work, Impagliazzo and Rudich [STOC ’89]
showed that no keyagreement protocol exists in the random oracle model,
yielding that keyagreement cannot be blackbox reduced to oneway functions.
Their work has a long line of followup works (Simon
[EC ’98], Gertner et al. [STOC ’00] and
Gennaro et al. [SICOMP ’05], to name a few), showing that given oracle
access to a certain type of function family (e.g., the family that “implements”
publickey encryption) is not sufficient for building a given cryptographic
primitive (e.g., oblivious transfer). Yet, the following question remained open:
What is the exact power of the random oracle model?
We make progress towards answering the above question, showing that,
essentially, any no private input, semihonest twoparty functionality that can
be securely implemented in the random oracle model, can be securely implemented
information theoretically (where parties are assumed to be all powerful, and no
oracle is given). We further generalize the above result to function families
that provide some natural combinatorial property.
Our result immediately yields that that the only noinput functionalities that
can be securely realized in the random oracle model (in the sense of secure
function evaluation), are the trivial ones (ones that can be securely realized
information theoretically). In addition, we use the recent information theoretic
impossibility result of McGregor et al. [FOCS ’10],
to show the existence of functionalities (e.g., inner product) that cannot be
computed both accurately and in a differentially private manner in the random
oracle model; yielding that protocols for computing these functionalities cannot
be blackbox reduced to the existence of oneway functions.

Itay Berman
and Iftach Haitner
From NonAdaptive to Adaptive Pseudorandom Functions [Abstract]
TCC 2012
[PDF]
Draft of full version
[PDF]
Unlike the standard notion of pseudorandom functions (PRF), a
nonadaptive PRF is only required to be indistinguishable from a random
function in the eyes of a nonadaptive 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 nonadaptive ones, where direct means that the constructed adaptive
PRF uses only few (ideally, constant number of) calls to the underlying
nonadaptive 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 nonadaptive ones. The suggested construction is
extremely simple, a composition of the nonadaptive PRF with an appropriate
pairwise independent hash function.

Iftach Haitner
and Eran Omri
Coin Flipping with Constant Bias Implies OneWay
Functions [Abstract]
[Slides]
SIAM
Journal of Computing 2013
[link]
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 oneway functions. An important exception where the above implication is not
known, however, is the case of coinflipping 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
coinflipping protocols that are safe against negligible bias do imply oneway functions, and, very recently, Maji,
Prabhakaran, and Sahai [FOCS '10] proved the same for constantround protocols
(with any nontrivial bias). For the general case, however, no such implication was known.
We make progress towards answering the above fundamental question, showing that
(strong) coinflipping protocols safe against a constant bias (concretely,
\frac{\sqrt2 1}2  o(1)) imply oneway functions.

Yevgeniy Dodis,
Iftach Haitner
and
Aris Tentes
On the Instantiability of
HashandSign RSA Signatures [Abstract]
[Slides]
TCC 2012 [PDF]
Draft of full version [PDF]
The hashandsign 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
(RSAFDH). In fact, prior work has shown several ``uninstantiability'' results
for various abstractions of RSAFDH, 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 RSAbased schemes.
Motivated by closing this gap, we consider the setting where the RSA
function representation is generic (i.e., blackbox) 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 RSAbased 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
RSAFDH to any natural assumption even in our model. Thus, our result suggests
that in order to prove the security of a given instantiation of RSAFDH, one should use
a nonblack 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 RSAFDH signatures can be proven secure under the standard RSA assumption, provided that the number
of signing queries is apriori bounded.

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 oneway trapdoor permutation) in a blackbox way, treating it as an oracle, or must it be nonblackbox (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 blackbox way only, there are some constructions that are inherently nonblackbox. 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 nonblackbox way (requiring to prove in zeroknowledge statements that relate to the primitive).
In this paper, we study whether such nonblackbox use is essential. We answer this question in the negative. Concretely, we present a fully blackbox reduction from oblivious transfer with security against malicious parties to oblivious transfer with security against semihonest 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 blackbox use of semihonest oblivious transfer,
or alternatively a blackbox use of lowerlevel primitives such as enhanced trapdoor permutations or homomorphic encryption.

Iftach
Haitner,
Omer
Reingold, and
Salil Vadhan
Efficiency Improvements in Constructing Pseudorandom
Generators from Oneway Functions [Abstract]
SIAM
Journal of Computing 2013
[link]
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 oneway
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 nextblock 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 oneway function in a nonadaptive manner. Using
[Applebaum, Ishai and Kushilevitz SICOMP '06], this implies the existence of
pseudorandom generators in NC^{0} based on the existence of oneway functions in
NC^{1}.

Boaz Barak,
Iftach Haitner,
Dennis Hofheinz and
Yuval Ishai
Bounded KeyDependent Message Security
[Abstract]
Advances in Cryptology  Eurocrypt,
2010
[PDF]
Draft of full version
[PDF]
We construct the first publickey 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 publickey encryption scheme that resists keydependent
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
nonstandard 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 circularsecure 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 blackbox access to the
query function and the
adversary attacking the scheme. This proves that the nonblackbox 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 OneWay Hash Functions via
Inaccessible Entropy
[Abstract]
Advances in Cryptology  Eurocrypt,
2010 [PDF]
Draft of full version
[PDF]
This paper revisits the construction of Universally OneWay Hash Functions
(UOWHFs) from any oneway 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 oneway function
f is already a weak form of a UOWHF: Consider
F(x,i) that outputs the ibit
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 oneway 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 wellestablished 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 collisionfinding oracle. Such an oracle can be used to break
collisionresistant hash
functions or, more generally, statistically hiding commitments. The oracle we
consider Sam_{d,}
where d is the recursion depth, is based on the identicallynamed oracle defined
in the work of
Haitner et al. (FOCS '07). Our main result is a constantround publiccoin
protocol AMSam
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. AMSam allows us to conclude that if
L is decidable by a
kadaptive
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 constantround statistically hiding commitment on NPhardness, then
NP ⊆ coAM and
the polynomial hierarchy collapses. The same result holds for any primitive that
can be broken
by Sam_{O(1)} including collisionresistant hash functions and
O(1)round oblivious
transfer where
security holds statistically for one of the parties. We also obtain nontrivial
(though weaker)
consequences for kadaptive reductions for any
k = poly(n). Prior to our work,
most results in
this research direction either applied only to nonadaptive 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 constantround
publiccoin
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 allpowerful 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}^{n} (such
D are called efficiently samplable with
postselection), 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]
SIAM
Journal of Computing 2013
[link]
IEEE Symposium on Foundations of Computer Science
(FOCS), 2009 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., 3message
protocols  Bellare, Impagliazzo and Naor [FOCS '97], and
publiccoin 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,
MinhHuyen Nguyen, Shien Jin Ong,
Omer Reingold and
Salil Vadhan
Statistically Hiding Commitments and Statistical
ZeroKnowledge Arguments from Any OneWay Function
[Abstract]
SIAM
Journal of Computing 2009
[link]
Draft of full version
[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 polynomialtime 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 oneway functions.
 Prove that constantround statistically hiding commitments are necessary
for constructing constantround zeroknowledge proof systems for NP that remain secure under parallel composition (assuming the existence of oneway functions).

Iftach Haitner,
Alon Rosen and
Ronen Shaltiel
On the (Im)Possibility of ArthurMerlin Witness
Hiding Protocols
[Abstract]
[Slides] Theory of Cryptography Conference (TCC), 2009
[PDF]
The concept of witnesshiding suggested by Feige and
Shamir is a natural relaxation of zeroknowledge. In this paper we identify
languages and distributions for which many known constantround publiccoin
protocols with negligible soundness cannot be shown to witnesshiding using
blackbox techniques.
In particular, our results imply that it is impossible to prove that parallel
repetition of 3Colorability or Hamiltonicity is witnesshiding for
distributions that support instances with exactly one witness, if the proof of
security is by a blackbox 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
blackbox reduction to show that parallel repetition of 3Colorability or
Hamiltonicity is
witnesshiding for distributions with ``two independent witnesses.
We also consider blackbox reductions for 3Colorability 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 witnesshiding, however, presents new technical and
conceptual difficulties that do not come up in the setup of zeroknowledge. The
high level idea is that if a blackbox reduction establishes the witnesshiding
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
hashfunctions. There exists no fullyblackbox reduction
from an encryption scheme secure against keydependent messages to
oneway 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 keydependent 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 Oneway Functions
PhD. Thesis, 2008
[PDF]

Iftach Haitner
SemiHonest to Malicious Oblivious Transfer 
The
BlackBox Way [Abstract]
[Slides]
Theory of Cryptography Conference
(TCC), 2008 [PDF]
Full version is part of
[BlackBox
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 blackbox manner (i.e.,
the construction uses only the input/output behavior of the
primitive guaranteed by the assumption) to construct a
semihonest 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
nonblack techniques (a Karp reduction is carried in order
to prove an NP statement in zeroknowledge). In their recent
breakthrough result, Ishai, Kushilevitz, Lindel and Petrank
(STOC '06) deviated from the above paradigm, presenting a
blackbox reduction from oblivious transfer to enhanced
trapdoor permutations and to homomorphic encryption. Here we
generalize their result, presenting a blackbox reduction
from oblivious transfer to semihonest oblivious transfer.
Consequently, oblivious transfer can be blackbox reduced to
each of the hardness assumptions known to imply a
semihonest oblivious transfer in a blackbox 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 singleserver
private information retrieval.

We study the
communication complexity of singleserver Private
Information Retrieval (PIR) protocols that are based on
fundamental cryptographic primitives in a blackbox manner.
In this setting, we establish a tight lower bound on the
number of bits communicated by the server in any
polynomiallypreserving 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
blackbox construction of a statisticallyhiding
bitcommitment 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 statisticallyhiding
commitment schemes to lowcommunication singleserver 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
singleserver PIR protocol.


We give a construction of
statisticallyhiding commitment schemes (ones where the
hiding property holds information theoretically), based on
the minimal cryptographic assumption that oneway functions
exist. Our construction employs twophase commitment
schemes, recently constructed by Nguyen, Ong and Vadhan
(FOCS `06), and universal oneway 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]
Journal of Cryptology
2014
[link]
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 oneway permutations and oneway functions)
of statistically hiding commitment schemes and of statistical
zeroknowledge arguments. Interactive hashing with respect to a oneway
permutation f, is a
twoparty 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 twotoone 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
[link]
Advanced in Cryptology  CRYPTO, 2006
[PDF]
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 oneway function. The second,
due to Yao (FOCS '82), states that the existence of weak
oneway functions implies the existence of full fledged
oneway 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 oneway 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^{3}) achieved by Goldreich et al. Our technique has
the potential of implying seedlength Θ(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 oneway 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 oneway function that has seed length of
only Θ(n^{2}). This improves a recent result of
Holenstein (TCC '06) that shows a construction with seed
length Θ(n^{5}) based on such oneway 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^{3} factor and reduces the seed length to
Θ(n^{7})
(which also implies improvement in the security of the
construction).

Iftach Haitner,
Danny Harnik and
Omer Reingold
On Efficient Pseudorandom Generators from
Exponentially Hard OneWay Functions [Abstract]
[Slides]
International
Colloquium on
Automata,
Languages and
Programming  ICALP, 2006
[PDF]
Full version is part of
[On
the Power of the Randomized Iterate]
We show a construction of
a pseudorandom generator from any exponentially hard oneway
function with a blowup of only Θ(n^{2}). This Improves the
recent Θ(n^{5}) construction of Holenstein (TCC '06). Our
technique uses the tools recently presented in Haitner et
al. (Crypto '06) for the setting of regular oneway
functions, and further develops them.

Iftach Haitner, Omer Horvitz,
Jonathan Katz,
ChiuYuen Koo,
Ruggero Morselli and
Ronen Shaltiel
Reducing Complexity Assumptions for
StatisticallyHiding Commitment [Abstract]
[Slides]
Journal of Cryptology 2009
[link] Advances in Cryptology  Eurocrypt,
2005
[PDF]
Draft of full version
[PDF]
We revisit the following
question: what are the minimal assumptions needed to construct
statisticallyhiding commitment schemes? Naor et al. show how
to construct such schemes based on any oneway permutation. We
improve upon this by showing a construction based on any approximable preimagesize oneway function. These are
oneway functions for which it is possible to efficiently
approximate the number of preimages of a given output. A special
case is the class of regular oneway functions where all
points in the image of the function have the same (known) number
of preimages.
We also prove two additional results related to
statisticallyhiding 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 honestbutcurious 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]
