<<

. 15
( 19)



>>

the private key for ID by first picking random elements and
then setting




is a valid random private key for ID.
We note that
To see this, let Then we have that




It follows that the key defined in (2) satisfies:




where are uniform in This matches the definition for
a private key for ID and hence is a valid private key for ID.
The simulator gives this key to
TEAM LinG
Secure Identity Based Encryption Without Random Oracles 451

Challenge. outputs an identity and two messages Let
If there exists an such then
the simulator terminates the experiment and outputs abort. Otherwise, the
simulator responds with the challenge ciphertext



Suppose Then, we note that since for all we have
that:

Hence, if then the challenge C is a valid encryption
of under
Phase 2. issues more private key queries for identities The simu-
lator responds as before.
Guess. Finally, outputs a guess The simulator outputs as the
result of the experiment.
We define to be the random variable denoting the
simulator™s output in the above experiment. It takes one of three values: 0, 1, or
abort.

Experiment 2: Let be an algorithm, be a bit in {0,1},
F be a function F : and Define the following game
between a simulator and
Setup: To generate system parameters the simulator picks a random
and sets Next, it picks random and a random matrix
where each It gives the system parameters
and keeps to itself the master key
Phase 1: issues up to adaptive private key queries. Consider a query for
the private key If F(ID) = 1 the simulator terminates the
experiment and outputs abort. Otherwise, the simulator uses master-key to
generate the private key for ID and gives the result to
Challenge. outputs an identity and two messages If
F(ID) = 0 the simulator terminates the experiment and outputs abort. Oth-
erwise, the simulator creates the encryption of and gives the resulting
challenge ciphertext to
Phase 2. issues more private key queries for identities The simu-
lator responds as before (aborting as necessary).
Guess. Finally, outputs a guess The simulator outputs as the
result of the experiment.
We define to be the random variable denoting the simulator™s
output in the above experiment. It takes one of three values: 0, 1, or abort.
Next, we state four facts about these experiments, which we prove in the full
version of the paper. The proof of Theorem 1 will follow immediately from these
facts. We define the following notation:
TEAM LinG
452 Dan Boneh and Xavier Boyen


Define the random variable
1.
2. For define the random variable
For define the value
3.
We let denote the distribution sampled by the following algorithm:
4.
pick a random and a random and output the (function,
key) pair
5. We set and
Claim 1. Consider Then for the random variable
is identical to the random variable
Claim 2. For we have that is equal to
Claim 3. Let Then for


Claim 4. We have that
The proofs of these claims are given in the full version of the paper. The
main theorem follows easily.
Proof (Proof of Theorem 1). The theorem follows directly from Claims 2 and 4.
The two claims together show that for any algorithm that makes at
most private key queries, we have


as required.

5 Constructing Admissible Hash Functions
It remains to show how an admissible hash function family can be constructed
given a collision resistant hash function family. We do this in two steps: we first
present some idealized sufficient conditions for a hash function family to be ad-
missible, then show how these conditions can be achieved in the case of a binary
alphabet given a family of collision resistant hash functions. As previously men-
tioned, the Decision BDH assumption can be used to realize collision resistance,
although we are free to use more practical hash functions.
For simplicity, we define the following shorthand notation. We let be
the universe of the possible values of the secret index K. For a hash function H,
we respectively define the H-null-set and the H-kernel of any as:


Clearly, for any the sets and form a partition of such that
and For binary alphabets,
we have



Before delving into the construction, we need to precise the following notions.
TEAM LinG
Secure Identity Based Encryption Without Random Oracles 453

Adversarial Uncertainty. We formalize the information made available to the
adversary using the notion of knowledge state. At any time during the interaction
of an algorithm with a bias map oracle where H is public and K is
secret, the algorithm™s available knowledge about the oracle is captured by a
distribution of the secret K. Initially the distribution is uniform over
since K is chosen uniformly in this set. Now, suppose that prior to the next
interaction with the oracle the distribution is uniform over some set S, then the
distribution after the next oracle query is uniform over a subset
such that



It follows that after learning the responses to any set
of queries the algorithm™s knowledge state regarding K is
completely captured by the uniform distribution over the set given by




Here, and are respectively defined as the sets of values of
that are compatible with the “negative” and the “positive” responses from the
set of oracle responses Notice that reordering the
queries has no effect on the knowledge state.

Hamming Separation Property. For two vectors we write for
the Hamming distance between and We say that a hash function family
satisfies the separation property if and
such that it also holds that
In other words, any distinct and must take differing values in at
least coordinates (and thus have at most coordinates in common).
In Section 5.2, we show how to achieve the Hamming separation property
from collision resistance using coding theory.

5.1 Sufficient Conditions for Admissibility
The following theorem gives a set of sufficient conditions for a hash family to be
admissible as defined in Definition 6. We focus on binary alphabets
Theorem 2. Let be positive integers such that and Let
be an alphabet of size and let Assume that
is some resistant hash function
family that satisfies the separation property. Pose
If for some arbitrary then the family is
provided that and for some arbitrary

TEAM LinG
454 Dan Boneh and Xavier Boyen

Proof. It suffices to show that, in the view of any algorithm interacting with a
bias map oracle for random and where K is secret, the
first outputs of the oracle are distributed identically to the first outcomes of
a binomial random process of expectation with probability at least
We henceforth omit the subscripts K and since there is no ambiguity, and
write for We use the abbreviations
and
We compute the distribution of the first oracle answers under the stated
assumptions, treating the algorithm as an adversary that adaptively selects
the points at which F is queried. For now, we assume that
(and by the separation property,
By the resistance assumption on this is true with probability
at least We correct for this assumption at the end.
Suppose that before step the adversary has learned the
values respectively taken by at arbitrary query points
Our goal is to find lower and upper bounds on the conditional probability that
given the history of past queries and answers, in the adversary™s view,
uniformly for all choices of the next query point
Let where
and and write
for the probability we seek to bound. Observe that the two sets and
together capture all relevant information about the query history just before the
query, since the order of the queries is irrelevant. We have




where we have posed and
We can use this general expression and the separation property
to bound for query histories that contain either zero or one positive answer.
We later show that the other cases are together very unlikely. Namely, we seek:
1. a uniform bounding interval on for all query histories with
(i.e., containing only negative answers);
2. a uniform upper bound on for all query histories such that
(i.e., containing one positive answer).
We obtain non-trivial uniform bounds of three different kinds, given by




Detailed calculations for these bounds are given in the full version of the paper.

TEAM LinG
Secure Identity Based Encryption Without Random Oracles 455

Subject to the above inequalities, we set out to bound the probability that
the biased PRF oracle F deviates from a sequence of outcomes from a genuine
memoryless binomial process of expectation over a sequence of length
Consider R, a binomial process of expectation We construct a modified
process whose outcome is defined as Here, M is a control
process whose purpose is to randomly decide whether should assume the
value of or its opposite, with a probability that depends on the previous
outcomes and the current drawing By properly choosing M,
we can make behave exactly as F, i.e., have the of achieve the
same joint distribution as the of F. In particular, this means that the
event that the processes R and F behave similarly over a sequence of length is
at least as likely as the event that for all since in this case
R and have the same first outcomes. It remains to bound such probability.
Here is the gist of the argument.
The goal is to devise an that perfectly simulates any of
for (unknown) random K, and bound the influence of M needed to do so.
Suppose that for some query history the conditional expectation
of as viewed by the adversary exceeds the
expectation of the binomial process One can make the
simulated process assume the expected law of conditionally on this specific
history by letting the control process take with conditional probability
when and with probability 0 when More
generally, we find that for the process to perfectly simulate F, it suffices that
for the conditional law of given satisfies




Let us write for the event We outline how to use the above
results to upper bound the unconditional probability for First, from
the law of M we get which we can
bound further using our previous bounds on in the cases where
Next, we need to bound the probabilities of the conditioning
events. The difficultly here is that the random variables derive from
the complicated process Fortunately, conditionally on the event the
process identifies with the binomial process R so that these probabilities have
nice expressions in function of and Note that these probabilities vanish
quickly as increases, which is why we bounded for only.
Thus, we have just reduced the upper bound computation of to that
of Carrying this idea through, after some calculations we obtain




The formal derivation of this result may be found in the full version of the paper.
TEAM LinG
456 Dan Boneh and Xavier Boyen

To conclude, we correct for the probability of finding a hash collision in the
allotted time which in the worst scenario could yield an infallible discriminator
between F and R. It follows that the probability that the F and R oracles can
be distinguished admits the upper bound as required.

5.2 Admissibility from Collision Resistance
We now show how to construct an admissible hash function family
in the sense of Theorem 2, given an “ordinary” family of
resistant hash functions We
give an explicit construction for the specific case of a binary alphabet
Theorem 3. Let be an efficiently com-
putable resistant hash function family. Then for any
there exists an efficiently computable function family
that satisfies both the resistance property and the
bitunse separation property, where and

Proof. Let be the smallest positive integer such that
and define
Let be any bijection. Define the injection
that, on input partitions in fragments of bits each (padding
the last fragment as necessary), applies the map to each fragment, and con-
catenates all the outputs.
Let be a Reed-Solomon error correcting code with parameters
i.e., a linear code that takes input words of size over the alphabet
and produces codewords of length with minimum pairwise Hamming
distance
Let be the injection that maps any field element
to the vector given by the row of a Hadamard
matrix. Recall that a binary Hadamard matrix is such that any two
distinct rows or columns agree on exactly coordinates; it is well known
that a Hadamard matrix exists and is easy to construct for all
Define the function that applies individually to each
coordinate of its input word and concatenates the resulting Hadamard vectors.
The desired hash family is then given by
where
It remains to show that has the desired properties.
First, since is an injection, the resistance of entails
the same for
Next, by the stated properties of the Reed-Solomon code, produces code-
words of size with minimum pairwise Hamming distance in Since
turns any two distinct elements of into vectors that differ in
positions, it follows that produces binary vectors of size with
minimum pairwise Hamming distance in The corresponding
TEAM LinG
Secure Identity Based Encryption Without Random Oracles 457

ratio is bounded as follows. Since is chosen such that
we have hence follows that
as claimed.
Last, we have that
as required.


5.3 Putting It All Together “ Concrete Bounds

It is useful to assign a more concrete meaning to the values taken by the parame-
ters intervening in Theorems 2 and 3. We assume to be given (the adversarial
advantage against the collision resistant hash functions), (the collision resis-
tant hash output length in bits), and (the allowed number of PRF queries),
under the “birthday paradox” constraint that Our task is to find a
suitable set of parameters so that (1) the security of the IBE system of Sec-
tion 4.2 is within a polynomial factor of and (2) the complexity of the four
IBE operations takes polynomial time in the security parameters. For we
require that and
We describe two settings of the parameters; one favoring security, the other
favoring performance.

Favoring security. We first show how to satisfy the requirements for the PRF
construction with a binary alphabet when the intrinsic PRF error prob-
ability (defined as in the notation of Theorem 2) is pegged to
We arbitrarily choose and successively derive:
s.t.
and
Evidently, the total PRF loss is
negligible and the bandwidth coefficient is polynomial
in and The price to pay for such a low value of is a fairly large

Favoring performance. We can attain better bounds by adjusting the PRF loss to
best match the intrinsic loss incurred by the IBE construction itself, in function of
as follows. Assuming that the loss due to hash collisions is negligible, under
the BDH assumption Theorem 1 gives a IBE
such that We can
minimize for a prescribed value of by seeking For
this gives us a total IBE security loss under the
improved bandwidth requirement
We note that the optimal value of varies and is tied to the coding construc-
tion. We defer to the full paper the question of optimizing for all parameters.

6 Extensions
We very briefly outline a few simple extensions of the IBE system of Section 4.2.
TEAM LinG
458 Dan Boneh and Xavier Boyen

Hierarchical IBE. Introduced by Horowitz and Lynn [HL02], HIBE was first
constructed by Gentry and Silverberg [GS02] in the random oracle model. The
IBE system of Section 4.2 generalizes naturally to give a semantically secure
HIBE under an adaptive chosen identity attack (IND-ID-CPA) without random
oracles. For a hierarchy of depth both the ciphertext and private key contain
blocks where each block contains components. Thus, a private key at depth
is an element of As our IBE, the HIBE uses collision resistant hash
functions and is provably secure without random oracles whenever the Decision
BDH assumption holds. The construction is similar to the construction of a
(selective identity secure) HIBE without random oracles based on Decision BDH
recently proposed by Boneh and Boyen [BB04]. The details are deferred to the
full version of the paper.

Chosen Ciphertext Security. A recent result of Canetti et al. [CHK04] gives
an efficient way to build a chosen ciphertext IBE (IND-ID-CCA) from a chosen
plaintext 2-HIBE (IND-ID-CPA). Thus, by the previous paragraph, we obtain a
full chosen identity, chosen ciphertext IBE (IND-ID-CCA) that is provably secure
without random oracles. More generally, by starting from an a
fully secure can be similarly constructed without random oracles.

Arbitrary Identities. We can extend our IBE system to handle identities
by first hashing ID using a collision resistant
(as opposed to
hash function prior to key generation and encryption. A
standard argument shows that if the scheme of Section 4.2 is IND-ID-CPA secure
then so is the scheme with the additional hash. This holds for the HIBE and the
chosen ciphertext secure system and as well.

7 Conclusions
We presented an Identity Based cryptosystem and proved its security without
using the random oracle heuristic under the decisional Bilinear Diffie-Hellman
assumption. Our results prove that secure IBE systems exist in the standard
model. This resolves an open problem posed by Boneh and Franklin in 2001.
However, the present system is not very practical and mostly serves as an exis-
tence proof. It is still a wonderful problem to find a practical IBE system secure
without random oracles based on Decision BDH or a comparable assumption.

References
[BB04] Dan Boneh and Xavier Boyen. Efficient selective-ID identity based encryp-
tion without random oracles. In Advances in Cryptology”EUROCRYPT
™04, volume 3027 of LNCS, pages 223“238. Springer-Verlag, 2004.
[BBP04] Mihir Bellare, Alexandra Boldyreva, and Adriana Palacio. An uninstantiable
random-oracle-model scheme for a hybrid-encryption problem. In Advances
in Cryptology”EUROCRYPT ™04, volume 3027 of LNCS, pages 171“188.
Springer-Verlag, 2004.

TEAM LinG
Secure Identity Based Encryption Without Random Oracles 459

[BF01] Dan Boneh and Matt Franklin. Identity-based encryption from the Weil
pairing. In Advances in Cryptology” CRYPTO ™01, volume 2139 of LNCS,
pages 213“229. Springer-Verlag, 2001.
[BF03] Dan Boneh and Matt Franklin. Identity-based encryption from the Weil
pairing. SIAM J. of Computing, 32(3):586“615, 2003.
[Boy03] Xavier Boyen. Multipurpose identity-based signcryption: A Swiss Army knife
for identity-based cryptography. In Advances in Cryptology”CRYPTO ™03,
volume 2729 of LNCS, pages 383“99. Springer-Verlag, 2003.
[BR93] Mihir Bellare and Phil Rogaway. Random oracle are practical: A paradigm
for designing efficient protocols. In Proceedings of ACM Conference on Com-
puter and Communications Security”CCS ™93, pages 62“73, 1993.
[CC03] Jae Choon Cha and Jung Hee Cheon. An identity-based signature from gap
Diffie-Hellman groups. In Practice and Theory in Public Key Cryptography”
PKC ™03, volume 2567 of LNCS. Springer-Verlag, 2003.
[CGH98] Ran Canetti, Oded Goldreich, and Shai Halevi. The random oracle model
revisited. In Proceedings of ACM Symposium on Theory of Computing”
STOC ™98. ACM, 1998.
[CHK03] Ran Canetti, Shai Halevi, and Jonathan Katz. A forward-secure public-key
encryption scheme. In Advances in Cryptology”EUROCRYPT ™03, volume
2656 of LNCS, pages 255“271. Springer-Verlag, 2003.
[CHK04] Ran Canetti, Shai Halevi, and Jonathan Katz. Chosen-ciphertext security
from identity-based encryption. In Advances in Cryptology”EUROCRYPT
™04, volume 3027 of LNCS, pages 207“222. Springer-Verlag, 2004.
[Coc01] Clifford Cocks. An identity based encryption scheme based on quadratic
residues. In Proceedings of the 8th IMA International Conference on Cryp-
tography and Coding, pages 26“28, 2001.
[GS02] Craig Gentry and Alice Silverberg. Hierarchical ID-based cryptography. In
Advances in Cryptology”ASIACRYPT ™02, volume 2501 of LNCS, pages
548“566. Springer-Verlag, 2002.
[HK04] Swee-Huay Heng and Kaoru Kurosawa. identity-based encryption
in the standard model. In Topic in Cryptology”CT-RSA ™04, volume 2964
of LNCS, pages 67“80, 2004.
[HL02] Jeremy Horwitz and Benjamin Lynn. Towards hierarchical identity-based
encryption. In Advances in Cryptology”EUROCRYPT ™02, pages 466“481,
2002.
[Jou00] Antoine Joux. A one round protocol for tripartite Diffie-Hellman. In Proceed-
ings of ANTS IV, volume 1838 of LNCS, pages 385“394. Springer-Verlag,
2000.
[MY96] Ueli M. Maurer and Yacov Yacobi. A non-interactive public-key distribution
system. Designs, Codes and Cryptography, 9(3):305“316, November 1996.
[Sha84] Adi Shamir. Identity-based cryptosystems and signature schemes. In Ad-
vances in Cryptology”CRYPTO ™84, volume 196 of LNCS, pages 47“53.
Springer-Verlag, 1984.
[SOK00] Ryuichi Sakai, Kiyoshi Ohgishi, and Masao Kasahara. Cryptosystems based
on pairings. In Proceedings of Symposium on Cryptography and Information
Security”SCIS ™00, Japan, 2000.
[Tan87] Hatsukazu Tanaka. A realization scheme for the identity-based cryptosys-
tem. In Advances in Cryptology”CRYPTO ™87, volume 293 of LNCS, pages
341“349. Springer-Verlag, 1987.


TEAM LinG
Non-interactive Timestamping
in the Bounded Storage Model

Tal Moran1, Ronen Shaltiel2,*, and Amnon Ta-Shma1
1
Department of Computer Science, Tel-Aviv University, Tel-Aviv, Israel
2
Department of Computer Science and Applied Mathematics,
Weizmann Institute of Science, Rehovot, Israel



Abstract. A timestamping scheme is non-interactive if a stamper can
stamp a document without communicating with any other player. The
only communication done is at validation time. Non-Interactive times-
tamping has many advantages, such as information theoretic privacy and
enhanced robustness. Unfortunately, no such scheme exists against poly-
nomial time adversaries that have unbounded storage at their disposal.
In this paper we show non-interactive timestamping is possible in the
bounded storage model. In this model it is assumed that all parties par-
ticipating in the protocol have small storage, and that in the beginning of
the protocol a very long random string (which is too long to be stored by
the players) is transmitted. To the best of our knowledge, this is the first
example of a cryptographic task that is possible in the bounded storage
model, but is impossible in the “standard cryptographic setting”, even
assuming cryptographic assumptions.
We give an explicit construction that is secure against all bounded stor-
age adversaries, and a significantly more efficient construction secure
against all bounded storage adversaries that run in polynomial time.
Keywords: timestamping, bounded storage model, expander graphs,
extractors


1 Introduction
The date on which a document was created is often a significant issue. Patents,
contracts, wills and countless other legal documents critically depend on the
date they were signed, drafted, etc. A timestamp for a document provides con-
vincing proof that it existed at a certain time. For physical documents, many
methods are known and widely used for timestamping: publication, witnessed
signing and placing copies in escrow are among the most common. Techniques
for timestamping digital documents, which are increasingly being used to replace
their physical counterparts, have also become necessary.
Loosely speaking, a timestamping scheme consists of two mechanisms: A
stamping mechanism which allows a user to stamp a document at some specific
time and a verification mechanism which allows a recipient to verify at a later
time that the document was indeed stamped at time
* Research supported by the Koshland Scholarship.

M. Franklin (Ed.): CRYPTO 2004, LNCS 3152, pp. 460“476, 2004.
© International Association for Cryptologic Research 2004
TEAM LinG
Non-interactive Timestamping in the Bounded Storage Model 461

Previous Work
Digital timestamping systems were first introduced in Haber and Stornetta [16],
where three timestamping systems are described. In the naïve timestamping
protocol, the stamper sends the document to all the verifiers during timestamp
generation. In the linking scheme, the stamper sends a one-way hash of the
document to a trusted timestamping server. The server holds a current hash,
which it updates by hashing it with the value sent by the stamper. This links
the document to the previous documents and to the succeeding ones. In the
distributed trust scheme, the document is used to select a subset of verifiers, to
which the stamper sends a hash of the document. Bayer, Haber and Stornetta
[3] improve upon the linking scheme, reducing the communication and storage
requirements of the system and increasing its robustness, by replacing the linear
list with a tree. Further work [17,7,6,8,5,4] is mainly focused on additional
improvements in terms of storage, robustness and reducing the trust required in
the timestamping server (s).
One common feature of all the above protocols is that they require the stam-
per to send messages to a central authority (or a distributed set of servers) at
timestamp generation.

Non-interactive Timestamping
We call a timestamping scheme non-interactive if it does not require the stam-
per to send messages at timestamp generation. Non-interactive timestamping
schemes, if they exist, have a number of obvious advantages over active schemes.
However, the notion of non-interactive timestamping seems self-contradictory.
How can we prevent an adversary from faking timestamps, if no action is taken
at timestamp generation? More precisely, suppose that an adversary “learns”
some document at time and wants to convince a verifier that he stamped
the document at time He can simulate the behavior of an “honest stamper”
who signs the document at time and generate a timestamp for the document.
Note that the “honest stamper” does not need to send any messages before
time and therefore the adversary will be able to convince a verifier that the
document was stamped at time
A crucial point in the argument above is that in order to perform this sim-
ulation the adversary must store all the information available to the “honest
stamper” at time We show that non-interactive timestamping is possible in a
scenario in which parties have bounded storage.

The Bounded Storage Model
In contrast to the usual approach in modern Cryptography, Maurer™s bounded
storage model [19] bounds the storage (memory size) of dishonest players rather
than their running time.
In a typical protocol in the bounded storage model a long random string of
length R is initially broadcast and the interaction between the polynomial-time
TEAM LinG
462 Tal Moran, Ronen Shaltiel, and Amnon Ta-Shma

participants is conducted based on storing small portions of The security of
such protocols should be guaranteed even against dishonest parties which have a
lot of storage (much more than the honest parties) as long as they cannot store
the whole string. Most of the previous work on the bounded storage model con-
centrated on private key encryption [19,10,2,1,14,15,18, 25], Key Agreement
[10] and Oblivious Transfer [9,12,13]. In contrast, the notion of non-interactive
timestamping cannot be implemented in the “standard cryptographic setting”.
To the best of our knowledge this is the first example of a protocol in the bounded
storage model which achieves a task that is impossible in the “standard crypto-
graphic setting”.

Non-interactive Timestamping in the Bounded Storage Model
We now explain our setting for non-interactive timestamping in the bounded
storage model. We assume that there are rounds and at every round
a long random string of length R is transmitted1.

The Stamping Mechanism: To stamp a document doc at time the scheme
specifies a function whose output is short. To stamp the document
doc, the stamper stores Intuitively, an adversary (who does not
know doc at time is not able to store the relevant information and therefore
is unable to stamp doc.

The Verification Mechanism: The verifier stores a short “sketch” of (denoted by
for every time At a later time the stamper can send the timestamp
and the verifier checks whether this timestamp is “consistent”
with his sketch.

Efficiency of a Timestamping Scheme: We say that a timestamping scheme is
(T, V) efficient if the stamper™s algorithm runs online (that is, in one pass) using
space T and polynomial time and the verifier™s algorithm runs online using space
V and polynomial time. We want T and V to be small as functions of R.

Our Notion of Security
Loosely speaking, we want to ensure that even an adversary with a lot of storage
(say storage for some constant cannot forge a timestamp.
Note, however, that a stamper with storage M > T can easily stamp
documents by running the stamping mechanism on some documents and
storing the generated timestamp (which is of length at most T). We will therefore
say that a scheme is secure if no adversary with space M can successfully stamp
significantly more than M/T documents.
1
One can imagine that random bits are transmitted at high rate continuously by a
trusted party, and that the string consists of the bits transmitted between time
and time

TEAM LinG
Non-interactive Timestamping in the Bounded Storage Model 463

One can also consider a probabilistic notion of security: given a randomly
chosen document, after the random string has passed, the adversary will not be
able to stamp the document with more than negligible probability. We note that
our notion of security implies this probabilistic notion as well.

Security of a Timestamping Scheme: Given a (T, V)-efficient timestamping
scheme. Let be the bound on the storage of the most powerful adver-
sary. The scheme is if, for every no adversary
with space M can successfully stamp more than documents (for a formal
definition of “successful stamping” see definition 4).
Notice that the definition above requires for every
Requiring for only, would have allowed adversaries with
to produce stamped documents, contradicting the definition™s
spirit. The definition in its current form assures us that any adversary, weak or
strong, with at most memory, can honestly stamp the same number of
documents if given slightly more resources (storage instead of M).

Our Results
In this paper we give two explicit constructions of non-interactive timestamping
schemes in the bounded storage model. The first is secure in an information-
theoretic sense (in the spirit of previous constructions in the bounded storage
model). It requires no unproven assumptions and is secure against any adversary
with arbitrary computational power as long as its storage capability is bounded.
We now state this result (precise definitions appear in Section 3).
Theorem 1 For every and large enough R there exists a timestamping
scheme that is and O(1)-optimal.
More precisely, every adversary with space has probabil-
ity at most to successfully stamp more than documents. The
timestamping scheme allows stamping documents of length and allows
rounds.
Our second system is more efficient. To achieve this efficiency it relies on
cryptographic assumptions and is therefore secure only against adversaries that,
in addition to being storage bounded, are required to run in polynomial time.
Theorem 2. Assume that there exist collision resistant hash functions. There
exists a timestamping scheme that is
and O(log R)-optimal. More precisely, every adversary with space
and running time polynomial in R has negligible probability to
successfully stamp more than documents. The timestamping
scheme allows stamping documents of length R and allows R rounds.
We remark that our technique can potentially reduce T and V to
This improvement requires an explicit construction of certain “expander graphs”
that is not known today. More details will appear in the full version of the paper.
TEAM LinG
464 Tal Moran, Ronen Shaltiel, and Amnon Ta-Shma

Advantages of Our Non-interactive Timestamping Scheme
Non-interactive timestamp systems have some significant advantages over the
interactive systems known to date. We summarize some of these below:
The only communication made before the verification process is the trans-
mission of the random string This allows the timestamp system to be
used in situations where communication is infeasible or undesirable. E.g.,
communication may be asymmetric: one central agency can broadcast all
other users, while the users can not send messages to the agency.
Everyone can stamp and everyone can verify and no central control or ac-
quaintance between stamper and verifier is needed. The decentralized na-
ture of this scheme overcomes many of the “trust” problems with interactive
timestamp systems. Even in distributed interactive systems, some measure
of trust must be given to third parties. Our non-interactive timestamp sys-
tem requires only that the random string be truly random and receivable by
all parties.
Privacy. The scheme hides the fact that timestamping occurred at all, e.g.,
an inventor can safeguard her inventions without revealing even the fact of
their existence. This also ensures privacy in an information-theoretic sense.
Our schemes solve some of the robustness problems that plague interactive
timestamping systems. In particular, it is much more difficult to mount a
denial-of-service attack: there is no central point that can shut down the sys-
tem, and even temporarily shutting down communications will not prevent
the creation of new timestamps. The lack of communication also makes it
difficult for an attacker to tell whether such an attack has succeeded.

Overview of the “Information-Theoretic” Construction
The setup is the following: A string of length R is transmitted and the stamper
wants to convince a verifier that he “knew” a document prior to the transmission
of this string.
Using the Document to Select Indices: We implement the function
as follows: Each document doc specifies some D indices that the stamper will
remember from the long string. For that we use a bipartite graph where the
left-hand vertices are all possible documents, the right-hand vertices are indices
and every left vertex has D neighbors. The indices selected by a
document doc are the neighbors of doc. We want to force a stamper who would
like to stamp documents to store many indices. Intuitively, this is equivalent
to the requirement that every documents on the left have many different
neighbors. This naturally leads to using an expander graph. (A bipartite graph
is a if every vertices on the left have at least kc neighbors
2
on the right) .
2
We stress that we need to use unbalanced graphs (graphs which have many more
vertices on the left than on the right-hand side). Such graphs were constructed in
[24, 23]. However, we need graphs with somewhat different parameters. We construct
such graphs by combining the constructions of [24] and a slight modification of [23,
21] (which in turn relies on explicit constructions of “randomness extractors” from
[21,22]).
TEAM LinG
Non-interactive Timestamping in the Bounded Storage Model 465

To stamp a document doc, the stamper stores the content of the long string
at the indices specified by doc. We use graphs with expansion therefore
to correctly stamp documents simultaneously an honest stamper must store
roughly kD bits.

Using Random Sets for Verification: The function is implemented as
follows. The verifier chooses a random subset of size from the indices
of and stores the content of at these indices. After the transmission of the
random string a stamper may send a timestamp of a document doc (that
consists of the content of at the D indices defined by doc). By the birthday
problem, with high probability (over the choice of the verifier™s random set)
some of these indices were also stored by the verifier. The verifier checks that
the content sent by the stamper is consistent with what he stored.
For a fixed string and document doc, we say that a timestamp is “incorrect”
if it differs from the “correct” timestamp of doc in many indices. The verification
process we described guarantees that, with high probability, the verifier will
reject an “incorrect” timestamp.
A Sketch of the Security Proof: The basic intuition for the security proof is
the following: Suppose that an adversary is able to successfully stamp some
documents. This means that he correctly stamped these documents (as
otherwise he is caught by the verifier). However, correctly stamping documents
requires storing kD indices, therefore if the storage of the adversary is
he can successfully stamp at most documents. This is the best we
can hope for (by our notion of security) as he could have stamped documents
by simply running the “stamping mechanism” on any documents.
However, the argument above is not sufficient. It does not rule out the pos-
sibility that the adversary can stamp many documents such that the identity of
these documents depend on the random string Our security definition requires
that for every adversary, with high probability (over the choice of there do
not exist documents which the adversary can successfully stamp. To prove
the security of our scheme we use a “reconstruction argument” and show that
any adversary which breaks the security guarantee can be used to compress the
string into a shorter string in a way that does not lose a lot of information. As
the string is random, we get a contradiction. The details are given in Section 4.

Overview of the “Computationally-Bounded” Construction
In the previous construction we chose so that a random subset of size
in [R] would intersect a subset of size D. We chose allowing
both the honest stamper and the verifier to store only bits. We now show
how to increase the efficiency and reduce the storage of honest parties to only
bits.
We use the same index selection mechanism as before. However, this time
we choose (this precise choice of parameters corresponds to
certain expander graphs). The verifier stores a short “hash” of the string When
stamping a document the stamper also supplies a short “proof” that the indices
TEAM LinG
466 Tal Moran, Ronen Shaltiel, and Amnon Ta-Shma

he sent are consistent with the hashed value held by the verifier. We implement
such a hashing scheme using Merkle trees [20]. We show that if collision resistant
hash functions exist then a polynomial time adversary with bounded storage
cannot produce an incorrect timestamp of a document. More precisely, we show
that after the transmission of the random string no polynomial time adversary
can generate many documents and stamp them correctly.

Hashing Documents Before Stamping Them: A bottleneck of our scheme is that
when using expanders of degree D we can only handle documents of length D 3.
However, in a computational setting (as we have already assumed the existence
of collision resistant hash functions) we can stamp longer documents by first
hashing them to shorter strings and then stamping them.

2 Preliminaries
2.1 Notation
The following conventions will be used throughout the paper.
Random String: We refer to the random string as its length is denoted by
R, and we think of it as composed of N blocks of length denoted
For any subset the expression will be taken to mean the string
generated by concatenating the blocks for all

Hamming Distance: The Hamming Distance between two strings and is
the number of blocks on which the two strings differ.

Online Space: For a family of functions F, we denote by Space(F) the maximum
space used by any function in F. We say a function can be computed online
with space if there is an algorithm using space at most which reads its input
bits one by one and computes in one pass.

2.2 Unbalanced Expander Graphs
A graph is expanding if every sufficiently small set has a lot of neighbors. Our
timestamping scheme relies on unbalanced expanders.
Definition 1 (unbalanced expander graphs). A bipartite graph
is if, for any set of cardinality at most
the set of its neighbors is of size at least
Note that we do not require that In fact, in our timestamping
scheme we will use graphs in which In this paper we need unbal-
anced expanders with very specific requirements. Loosely speaking we want a
3
This is because in unbalanced expander graphs, the degree must be logarithmic in
the number of left-hand vertices. Thus, shooting for degree D we can at most get
that the left-hand set (which is the set of documents) is of size

TEAM LinG
Non-interactive Timestamping in the Bounded Storage Model 467

graph with as small as possible degree D and right-
hand side of size roughly We use some existing constructions of unbal-
anced graphs [24] as well as a modification of [23] to prove the next theorem
(the proof will appear in the full version of the paper).
Theorem 3. There exists a fixed constant such that for every
there exists a bipartite graph with left degree D that is
expanding with and
Furthermore, this graph is explicit in the sense that given a vertex
and an integer one can compute the neighbor of in time
polynomial in


3 One Round Timestamping: The Model
In this section we formally define our model for timestamping in the bounded
storage model. The definitions are only for a single round. Definitions for multiple
rounds are straightforward generalizations and will appear in the full version.
A long random string of length R is transmitted. The verifier takes a short
sketch of the random string and remembers it. An honest stamper,
who wants to stamp a document calculates
When, at a later stage, the stamper wants to prove he knew the document doc at
stamping time, he sends to the verifier who computes
and decides whether to accept or reject. More formally,
Definition 2 (Non-Interactive timestamping scheme). A non-interactive
timestamping scheme consists of three functions:
A stamping function
A sketch function (we allow Sketch to be a probabilistic function).
A verification function
We require that for every string and document doc, the function
accepts.
We define efficiency:

Definition 3 (Efficiency). A non-interactive timestamping scheme is (T, V) -
efficient if Stamp can be computed online in space T = T(R) and time polynomial
in R, and Sketch can be computed online in space V = V(R) and time polynomial
in R.
An honest stamper with space M can easily stamp M/T documents by run-
ning the function Stamp in parallel. We require that no adversary with memory
M* can successfully stamp significantly more than documents. We first
define our model for adversaries:
Definition 4 (adversary). An adversary consists of two functions:
which produces a short string and which, given a document
TEAM LinG
468 Tal Moran, Ronen Shaltiel, and Amnon Ta-Shma

doc and attempts to produce a timestamp for doc. The space of an adver-
4
sary is the maximal length of . An adversary stamps a
document doc at (some fixed) if



Note that this probability is over the coin tosses of Sketch and the internal
random coins of the adversary. Note that when the adversary is not computation-
ally bounded, we can assume w.l.o.g. that the adversary is deterministic (does
not use random coins)

We define security as:

Definition 5 (Security). We say that a (T,V)-efficient timestamping scheme
is (for and if for every
and every adversary A with space




Definition 5 is very strong. It guarantees that whenever the sketch size is
small, no matter how powerful the adversary is, the number of documents the
adversary can successfully stamp is very small.


3.1 Security Against Feasibly Generated Documents

Until now, we have allowed the adversary to run in arbitrary time. When the
adversary is time-bounded, we can imagine scenarios where Definition 5 does
not hold, yet the system is secure because the adversary does not have the com-
putational power to find the documents he can illegally stamp. It makes sense to
require security only against “feasibly generated documents”. We model feasi-
bly generated documents by a probabilistic polynomial time machine
which, on input and an integer outputs documents (all different).

Definition 6 (Security against feasibly generated documents). We say
that a (T, V ) -efficient timestamping scheme is (for
and against feasibly generated documents, if for every
every adversary A with space and every polynomial time machine




where the probability is over the choice of and the random coins of
and A.
4
Note that the adversary is not required to run online in space The function
can be an arbitrary function of

TEAM LinG
Non-interactive Timestamping in the Bounded Storage Model 469

4 A Scheme with Information-Theoretic Security
In this section we describe a timestamping scheme which is information theoret-
ically secure against arbitrary adversaries with small storage.

4.1 The Stamping Scheme
Let R, N and be integers such that Given a string
we partition it into N blocks of bits. We use to denote the block of
Let denote the set of all documents which can be stamped. Let G be a
bipartite expander with left degree D, where the “left”
set is and the “right” set is [N]. We define the three procedures
Sketch, Stamp and Verify:

where has elements selected at random from [N].



Notice that contains the restriction of to the indices of and
therefore in particular contains the restriction of to the indices of
and contains the restriction of to and therefore in particular contains
the restriction of to the indices of
Theorem 4. Let G be a graph, and Fix
large enough such that and assume that If
then the scheme is and
for and
Plugging in parameters, a corollary of this is:
Corollary 1. For every and large enough R we construct a timestamping
scheme which is and O(1)-optimal with
and The timestamping scheme allows
stamping documents of length
We prove the corollary in the full version of the paper. We remark that
a probabilistic argument shows that there exist bipartite graphs of degree D
which have expansion (1 “ o(1))D and using such non-explicit graphs in our
construction (and setting gives optimality (whereas
the theorem below only achieves In the remainder of the section we
prove Theorem 4.

4.2 Efficiency
The verifier first chooses a random set and stores it, and then stores This
can indeed be done online with space We now explain how
TEAM LinG
470 Tal Moran, Ronen Shaltiel, and Amnon Ta-Shma

the stamper can run online in space T = Dn. Observe that it can calculate the
indices it will need to store before the random string goes by (since it knows doc
before it sees the random string). As the indices take D log N < Dn space, it
can work in place, replacing each index with the contents of the block as it goes
by. We now turn to proving security.

4.3 Security
In Definition 4 we defined “successful stamping”. Without loss of generality, we
assume the adversary is deterministic. Let denote
the set of random strings on which the adversary stamps at least
documents. We would like to prove that has small probability. We
first define a similar notion of “correct stamping”:
Definition 7. An adversary correctly stamps a document doc at if
An adversary correctly stamps a document
doc at with at most err errors, if the Hamming distance between
and is at most err.
We let denote the set of random strings for
which there are at least documents that the adversary correctly stamps with at
most err errors.
The security proof has two parts.
Lemma 1. Assume and For every
and any adversary with space we have


We then relate and
Lemma 2. Assume For every
Together,
Proof. (of Theorem 4) We need show that no adversary with space can
stamp more than documents. Notice that for
and Hence,
where the
first inequality follows by Lemma 2 and the second inequality follows by Lemma
1. The third inequality is because

4.4 The Proof of Lemma 1
We first define a compression function for Let
Suppose are the documents that the adversary cor-
rectly stamps at with at most err errors. Denote that
is the set of all indices which are selected by one of the documents. Denote
TEAM LinG
Non-interactive Timestamping in the Bounded Storage Model 471

that is the set of all indices which are bad for at
least one of the documents. We call an index useful. We choose
to be:


We define a “decompression” function that gets as input and
tries to recover Let be a string from i.e., a string on which the stam-
per correctly stamps with at most err errors. From
that appear in we recover the set and from we learn which
indices are in the subset Now, for every we recover as
follows:
If then we use the information in to find
If then we use the information in to find
If then we find an such that
We run and take from its output.
The only case where we do not take the value of directly from is for
However, all such indices are useful, and therefore we correctly
decode them. Therefore, for every we have
We now analyze the output length of the compression function Com. The
documents take bits space. by def-
inition. As G is expanding and and therefore
We represent by a binary vector of length which
has a “one” for indices in and a “zero” for indices in Each of
the documents is correctly stamped at with at most err errors, and therefore
for every such document we have and The
representation of is therefore bounded by We conclude that the
total length of the output of Com is at most
We denote this quantity
As every has a small description (of length we have
and therefore We have
(for large enough We also have and by our assump-
tion Altogether, We get
that As we get as
desired.

4.5 The Proof of Lemma 2
Claim. Fix an adversary, a string and a document doc. If the adversary
stamps doc at then it correctly stamps doc at with at most
errors.
Proof. We prove the contrapositive. Suppose for some and the
timestamp provided by the adversary for doc has incorrect indices.
Denote by the set of incorrect indices. The verifier catches the
TEAM LinG
472 Tal Moran, Ronen Shaltiel, and Amnon Ta-Shma

adversary iff i.e. if one of the incorrect indices is in (the
set of indices stored by Sketch). For each index in the probability that it
hits is and the probability that none of them hits is
(assuming the set is chosen with repetition). Hence,
the adversary stamps doc with Turning that around,
if the adversary stamps doc, then

In particular, for every and doc for which the stamper is successful,
Hence, the stamper correctly stamps doc at with at
most It follows that as desired.


5 An Efficient Scheme Secure
Against Polynomial Time Adversaries

The scheme suggested in Section 4 requires the honest parties (stamper and
verifier) to store many bits, namely TV >> R where T is the stamp size, V
the sketch size and R the random string length. In other words, if the stamp
size is very small then the sketch size V is almost all of the random string.
Our second scheme has small sketch and stamp size. This is achieved by using
the previous stamping scheme with a small T and using a different verification
method that allows the verifier to use much less storage. This verification method
is valid only against computationally bounded adversaries and takes advantage
of the bounded computational capabilities of the cheating party. In this section
we briefly describe the scheme and give a sketch of the proof. Due to space
constraints, the exact details will appear in the full version. We assume the
reader has some familiarity with collision resistant hash functions5 [11] (CRHFs)
and Merkle trees [20].


5.1 The Stamping Scheme

be a family of CRHFs6 and
Let
into N +1 blocks, denoted where
We partition a string
is of length log H and for is of length The string (which didn™t
appear in the previous scheme) serves as a “key” to the “hash function”. We use
the same “index selection” mechanism as in Section 4; G is a bipartite graph
with left degree D, where the left set is the set and the right set is the set
[N]. We now describe the stamp, sketch and verify procedures:
5
Also called “collision intractable” or “collision free” hash functions
6
Informally, this means that no computationally bounded adversary can find
such that when given a random function in the family. In this
paper we require hash functions which are hard even for adversaries which run in
time slightly super-polynomial in This is because the adversary runs in time
polynomial in R, whereas can be very small compared to R.

TEAM LinG
Non-interactive Timestamping in the Bounded Storage Model 473

The verifier stores and the root of a Merkle tree whose leaves are
using the hash function specified by 7. Note that is
deterministic (unlike the case of the previous section where Sketch is prob-
abilistic).
Given a document the stamper uses the function Stamp
of the previous section, and for every stores along with the
8
Merkle-path from to the root of the tree .
Given a document doc, a “root” and a stamp composed of D Merkle-
paths, the function accepts iff all paths are valid (that is,
the label of the tree root computed from the Merkle-paths is consistent with
that stored by the verifier).

We note that both and can be computed online in small
space, using the standard method for computing Merkle-trees online. For our
choice of parameters, this gives the required efficiency. Using the expander con-
struction of Theorem 3 for G, we obtain a scheme with efficiency
(and thus prove Theorem 2). It is possible to get an even more efficient scheme
with However, this result requires a better graph than the
one constructed in Theorem 3. It is folklore that such graphs exist by a proba-
bilistic argument. However, at this point no such explicit construction is known.
In the remainder of the section we sketch the proof of security of the scheme
(The complete proof of Theorem 2 appears in the full version of the paper).


5.2 Security

We follow the outline of the correctness proof of the information-theoretic version
of Section 4, except that now we work with security for generated documents. We
show that if the adversary successfully stamps many documents then he correctly
stamps many documents which is impossible by the “reconstruction argument”
of the previous section.
Fix some adversary with memory and running time polynomial in R. We
use coins to denote the concatenation of the random coins used by and
We define to be the set of pairs coins) such that, for
every the Merkle paths output by
are correct (i.e. that they are actual paths in the Merkle tree whose leaves are
the blocks of In particular, this implies that the leaves of the paths are a
“correct” timestamp for the documents output by in the sense
of Section 4.
7
Informally, a Merkle tree of using the hash function is a labeled binary
tree, where the leaves are labeled by and the label of each internal node
is given by applying to the concatenation of its children™s labels.
8
A Merkle-path from consists of along with the labels of the siblings of all
nodes on the path from to the root of the Merkle tree. Such as sequence contains
sufficient information to compute the labels of all nodes on the path to the root node
(by repeatedly applying the hash function).

TEAM LinG
474 Tal Moran, Ronen Shaltiel, and Amnon Ta-Shma

We now want to define the computational analogue of and relate it
to We define to be the set of all pairs coins) for which
the adversary successfully stamps the documents output by
(i.e. for all the the Merkle paths output by
are accepted by the verifier). This definition of success
corresponds to the notion of security in Definition 6.
We prove that (where
neg is a negligible function of This is because we can imagine a machine which,
when given a random hash function uniformly selects the pair coins) and
runs the adversary. The claim follows, as for every pair coins)
this machine can find a collision for Thus we have a computational
analogue of Lemma 2.
We then show (using Lemma 1) that every random string for which the
adversary can correctly stamp many documents can be compressed, which gives
a bound on the probability that this occurs.


6 Discussion and Open Problems
Dealing with Errors: Most protocols in the Bounded Storage Model, and ours
among them, assume the broadcast random string is received identically and
without errors by all parties. However, in many natural implementations of such
protocols, this assumption may not be realistic (e.g. when the random string has
a natural source).
Our information-theoretic scheme can be made to work even with errors
(provided the error rate is low enough) by allowing the verifier to accept a
timestamp even if the the blocks in the intersection differ by a small amount.
The proof of Lemma 1 already allows the adversary to make some errors when
stamping, and still be considered successful. Increasing the error rate by a small
amount will not invalidate the lemma (although the parameters suffer slightly).
The computational scheme, on the other hand, currently requires the random
string to be received perfectly by all parties. It is an interesting open question
whether this requirement can be removed.

Removing the Need for Constant Monitoring: Our timestamping schemes require
the verifier to run the Sketch function in every round for which it may, someday,
want to verify documents. The verifier must therefore constantly monitor the
random string, which is too much to ask from a casual user of the system.
An implementation of our timestamp systems can overcome this difficulty by
using “verification centers”: dedicated third parties who act as verifiers. In some
sense, such third parties appear in all previous timestamp protocols. This raises
the issue of how much trust the user must place in the verification center.
In the computational version of our protocol, the verification center is also
easily auditable by casual users: the verifier is deterministic and has no secret
information. Any user can act as a verifier for a single round, and compare its
state to that of the verification center: any inconsistency will be instantly visible.
TEAM LinG
Non-interactive Timestamping in the Bounded Storage Model 475

Online Versus Locally-Computable: The strategies for the honest players are
efficient in the sense that they work online using small space and polynomial
time. A stronger notion of efficiency called “locally-computable” was suggested in
[25]. It requires the honest players to store a small substring of the string More
precisely, the players need to choose a subset before the random string
is transmitted and only store We point out that the “information-theoretic”
scheme (Section 4) has this additional property, whereas the “computationally-
bounded” scheme (Section 5) does not9. Natural open problems are whether the
“information-theoretic” scheme can be improved to yield better parameters, and
whether the “computationally-bounded” scheme can be improved to run with
strategies that are locally computable.


Acknowledgements

We thank Danny Harnik, Moni Naor and Muli Safra for helpful discussions, and
the anonymous reviewers for their constructive comments.


References
1. Y. Aumann, Y.Z. Ding, and M. O. Rabin. Everlasting security in the bounded
storage model. IEEE Transactions on Information Theory, 48, 2002.
2. Y. Aumann and M. O. Rabin. Information theoretically secure communication
in the limited storage space model. In Advances in Crypology ” CRYPTO ™99,
volume 1666, pages 65“79, 1999.
3. D. Bayer, S. Haber, and W. S. Stornetta. Improving the efficiency and reliability of
digital time-stamping. In R. M. Capocelli et al., editor, Sequences II: Methods in
Communication, Security and Computer Science, pages 329“334. Springer-Verlag,
Berlin Germany , New York, 1992.
4. J. Benaloh and M. de Mare. Efficient broadcast time-stamping. Technical Report 1,
Clarkson University Department of Mathematics and Computer Science, August
1991.
5. Josh Cohen Benaloh and Michael de Mare. One-way accumulators: A decentralized
alternative to digital signatures. Lecture Notes in Computer Science, 765:274, 1994.
6. Ahto Buldas and Peeter Laud. New linking schemes for digital time-stamping. In
Information Security and Cryptology, pages 3“13, 1998.
7. Ahto Buldas, Peeter Laud, Helger Lipmaa, and Jan Villemson. Time-stamping
with Binary Linking Schemes. In Hugo Krawczyk, editor, Advances on Cryptology
” CRYPTO ™98, volume 1462 of Lecture Notes in Computer Science, pages 486“
501, Santa Barbara, USA, August 1998. Springer-Verlag.
8. Ahto Buldas, Helger Lipmaa, and Berry Schoenmakers. Optimally efficient ac-
countable time-stamping. In Public Key Cryptography, pages 293“305, 2000.
9
In the “computationally-bounded” scheme , both stamper and verifier read blocks
of the string online, and need to “hash them” quickly before reading the next
incoming blocks. Thus, to implement this scheme, one needs to use hash functions
which can be computed very efficiently.

TEAM LinG
Tal Moran, Ronen Shaltiel, and Amnon Ta-Shma
476

9. Christian Cachin, Claude Crepeau, and Julien Marcil. Oblivious transfer with
a memory-bounded receiver. In IEEE Symposium on Foundations of Computer
Science, pages 493“502, 1998.
10. Christian Cachin and Ueli Maurer. Unconditional security against memory-
bounded adversaries. In Burton S. Kaliski Jr., editor, Advances in Cryptology ”
CRYPTO ™97, volume 1294 of Lecture Notes in Computer Science, pages 292“306.
Springer-Verlag, 1997.
11. I.B. Damgard. Collision free hash functions and public-key signature schemes.
In Advances in Cryptology ” EUROCRYPT ™87, Proceedings, volume 304, pages
203“216. Springer-Verlag, 1987.
12. Yan Zong Ding. Oblivious transfer in the bounded storage model. Lecture Notes
in Computer Science, 2139:155, 2001.
13. Yan Zong Ding, Danny Harnik, Alon Rosen, and Ronen Shaltiel. Constant-round
oblivious transfer in the bounded storage model. In Theory of Cryptography ”
TCC ™04, volume 2951, Cambridge, MA, USA, February 2004. Springer-Verlag. To
appear.
14. Y.Z. Ding and M.O. Rabin. Hyper-encryption and everlasting security. In Annual
Symposium on Theoretical Aspects of Computer Science (STACS), pages 1“26,
2002.
15. Stefan Dziembowski and Ueli Maurer. Tight security proofs for the bounded-
storage model. In Proceedings of the 34th Annual ACM Symposium on Theory of
Computing, pages 341“350. ACM, May 2002.
16. Stuart Haber and W. Scott Stornetta. How to time-stamp a digital document.
Lecture Notes in Computer Science, 537:437, 1991.
17. Stuart Haber and W. Scott Stornetta. Secure names for bit-strings. In ACM
Conference on Computer and Communications Security, pages 28“35, 1997.
18. C. Lu. Hyper-encryption against space-bounded adversaries from on-line strong
extractors. In Advances in Cryptology ” CRYPTO ™02, volume 2442, pages 257“
271. Springer, 2002.
19. U. Maurer. Conditionally-perfect secrecy and a provably-secure randomized cipher.
Journal of Cryptology, 5(1):53“66, 1992.
20. Ralph C. Merkle. A certified digital signature. In Proceedings on Advances in
cryptology, pages 218“238. Springer-Verlag New York, Inc., 1989.
21. R. Raz, O. Reingold, and S. Vadhan. Error reduction for extractor. In 40th IEEE
Symposium on Foundations of Computer Science, pages 191“201, 1999.
22. A. Srinivasan and D. Zuckerman. Computing with very weak random sources.
SIAM Journal on Computing, 28:1433“1459, 1999.
23. Amnon Ta-Shma. Storing information with extractors. Information Processing
Letters, 83(5):267“274, September 2002.
24. Amnon Ta-Shma, Christopher Umans, and David Zuckerman. Loss-less condensers,
unbalanced expanders, and extractors. In ACM, editor, Proceedings of the 33rd
Annual ACM Symposium on Theory of Computing: Hersonissos, Crete, Greece,
July 6“8, 2001, pages 143“152, New York, NY, USA, 2001. ACM Press.
25. S.P. Vadhan. On constructing locally computable extractors and cryptosystems in
the bounded storage model. In Advances in Cryptology ” CRYPTO ™03. Springer,
2003.




TEAM LinG
IPAKE: Isomorphisms for Password-Based
Authenticated Key Exchange

Dario Catalano1, David Pointcheval1, and Thomas Pornin2
1
CNRS“LIENS, Ecole Normale Sup©rieure, Paris, France
{Dario.Catalano,David.Pointcheval}@ens.fr
2
Cryptolog, Paris, France
Thomas.Pornin@cryptolog.com



Abstract. In this paper we revisit one of the most popular password-
based key exchange protocols, namely the OKE (for Open Key Exchange)
scheme, proposed by Luck in 1997. Our results can be highlighted as fol-
lows. First we define a new primitive that we call trapdoor hard-to-invert
isomorphisms, and give some candidates. Then we present a generic
password-based key exchange construction, that admits a security proof
assuming that these objects exist. Finally, we instantiate our general
scheme with some concrete examples, such as the Diffie-Hellman func-
tion and the RSA function, but more interestingly the modular square
root function, which leads to the first scheme with security related to
the integer factorization problem. Furthermore, the latter variant is very
efficient for one party (the server). Our results hold in the random-oracle
model.


1 Introduction
Shortly after the introduction of the revolutionary concept of asymmetric cryp-
tography, proposed in the seminal paper by Diffie and Hellman [9], people real-
ized that properly managing keys is not a trivial task. In particular private keys
tend to be pretty large objects, that have to be safely stored in order to preserve
whatever kind of security. Specific devices have thus been developed in order
to help human beings in storing their secrets, but it is clear that even the most
technologically advanced device may become useless if lost or stolen. In principle
the best way to store a secret is to keep it in mind. In practice, however, human
beings are very bad at remembering large secrets (even if they are passwords or
pass-phrases) and very often they need to write passwords down on a piece of
paper in order to be able to keep track of them. As a consequence, either one
uses a short (and memorable) password, or writes/stores it somewhere. In the
latter case, security eventually relies on the mode of storage (which is often the
weakest part in the system: a human-controlled storage). In the former case, a
short password is subject to exhaustive search.
Indeed, by using a short password, one cannot prevent a brute force on-line
exhaustive search attack: the adversary just tries some passwords of its own
choice in order to try to impersonate a party. If it guesses the correct password,

M. Franklin (Ed.): CRYPTO 2004, LNCS 3152, pp. 477“493, 2004.
© International Association for Cryptologic Research 2004
TEAM LinG
478 Dario Catalano, David Pointcheval, and Thomas Pornin

it can get in, otherwise it has to try with another password. In many applications,
however, the number of such active attacks can be limited in various ways. For
example one may impose some delay between different trials, or even closing the
account after some fixed number of consecutive failures. Of course the specific
limitations depend very much on the context “ other kind of attacks, such as
Denial of Service ones, for example, should be made hard to mount either. In
any case, the important point we want to make here is that the impact of on-
line exhaustive search can be limited. However on-line attacks are not the only
possible threats to the security of a password-based system. Imagine for example
an adversary who has access to several transcripts of communication between a
server and a client. Clearly the transcript of a “real” communication somehow
depends on the actual password. This means that a valid transcript (or several
ones) could be used to “test” the validity of some password: the adversary chooses
a random password and simply checks if the produced transcript is the same as
the received one. In this way it is possible to mount an (off-line) exhaustive search
attack that can be much more effective than the on-line one, simply because, in
this scenario, the adversary can try all the possible passwords just until it finds
the correct one. Such an off-line exhaustive search is usually called “dictionary
attack”.

1.1 Related Work
A password-based key exchange is an interactive protocol between two parties
A and B, who initially share a short password pw, that allows A and B to
exchange a session key sk. One expects from this key to be semantically secure
w.r.t. any party, but A and B who should know it at the end of the protocol.
The study of password-based protocols resistant to dictionary attacks started
with the seminal work of Bellovin and Merritt [3], where they proposed the so-
called Encrypted Key Exchange protocol (EKE). The basic idea of their solution
is the following: A generates a public key and sends it to B encrypted “ using a
symmetric encryption scheme “ with the common password. B uses the password
to decrypt the received ciphertext. Then it proceeds by encrypting some value
using the obtained public key. The resulting ciphertext is then re-encrypted
(once again using the password) and finally sent to A. Now A can easily recover
using both his own private key and the common password. A shared session
key is then derived from using standard techniques.
A classical way to break password-based schemes is the partition attack [4].
The basic idea is that if the cleartexts encrypted with the password have any
redundancy, or lie in a strict subset, a dictionary attack can be successfully
mounted: considering one flow (obtained by eavesdropping) one first chooses a
password, decrypts the ciphertext and checks whether the redundancy is present
or not (or whether the plaintext lies in the correct range.) This technique allows
to quickly select probable passwords, and eventually extract the correct one.
The partition attack can be mounted on many implementations of EKE,
essentially because a public key usually contains important “redundancy” (as
a matter of fact a public key “ or at least its encoding “ is not in general
TEAM LinG
IPAKE: Isomorphisms for Password-Based Authenticated Key Exchange 479

a random-looking string). Note that in the described approach (for EKE), the
same symmetric encryption (using the same password) is used to encrypt both
the public key, and the ciphertext generated with this key. This may create ad-
ditional problems basically because these two objects (i.e. the public key and
the ciphertext) are very often defined on completely unrelated sets. A nice ex-
ception to this general rule are ElGamal keys [12]. This is thus the sole effective
application of EKE.
As noticed by the original authors [3], and emphasized by Lucks [17], it is
“counter-intuitive (. . .) to use a secret key to encrypt a public key”. For this
reason Lucks [17] proposed OKE, (which stands for Open Key Exchange). The
underlying idea of this solution is to send the public key in clear and to en-
crypt the second flow only. Adopting this new approach, additional public-key
encryption schemes can be considered (and in particular RSA [23] for instance).
However, one has to be careful when using RSA. The problem is that the RSA
function is guaranteed to be a permutation only if the user behaves honestly
and chooses his public key correctly. In real life, however, a malicious user may
decide to generate keys that do not lead to a permutation at all. In such a
case a partition attack becomes possible: an RSA-ciphertext would lie in a strict
subset if For this reason Lucks proposed a variant of his scheme, known
as Protected OKE, to properly deal with the case of RSA. Later on, however,
MacKenzie et al. [19,18] proved that the scheme was flawed by presenting a way
to attack it. At the same time they showed how to repair the original solution
by proposing a new protocol they called SNAPI (for Secure Network Authen-
tication with Password Identification), for which they provided a full proof of
security in the random-oracle model. This proof, however, is specific to RSA, in
the random-oracle model, and very intricate.
Interestingly enough, in the standard model, the problem of secure password-
based protocols was not treated rigorously until very recently. The first rigorous
treatment of the problem was proposed by Halevi and Krawczyk [15] who, how-
ever, proposed a solution that requires other setup assumptions on top of that
of the human password. Later on, Goldreich and Lindell [14] proposed a very
elegant solution that achieves security without any additional setup assumption.
The Goldreich and Lindell proposal is based on sole existence of trapdoor per-
mutations and, even though very appealing from a theoretical point of view, is
definitely not practical. The first practical solution was proposed by Katz, Os-
trovsky and Yung [16]. Their solution is based on the Decisional Diffie-Hellman
assumption and assumes that all parties have access to a set of public parameters
(which is of course a stronger set-up assumption than assuming that only human
passwords are shared, but still a weaker one with respect to the Halevi-Krawczyk
ones for example). Even more recently Gennaro and Lindell [13] presented an
abstraction of the Katz, Ostrovsky and Yung [16] protocol that allowed them to
construct a general framework for authenticated password-based key exchange
in the common reference string model.
We note here that even though from a mathematical point of view a proof in
the standard model is always preferable to a proof in the random-oracle model,

TEAM LinG
480 Dario Catalano, David Pointcheval, and Thomas Pornin

all the constructions in the standard model presented so far are way less efficient
with respect to those known in the random-oracle model. It is true that a proof
in the random-oracle model should be interpreted with care, more as a heuristic
proof than a real one. On the other hand in many applications efficiency is a big
issue and it may be preferable to have a very efficient protocol with a heuristic
proof of security than a much less efficient one with a complete proof of security.

1.2 Our Contributions
In this paper, we revisit the generic OKE construction by clearly stating the
requirements about the primitive to be used: we need a family of isomorphisms
with some specific computational properties that we call trapdoor hard-to-invert
isomorphisms (see next section for a formal definition for these objects). Very
roughly a trapdoor hard-to-invert isomorphism, can be seen as an isomorphic
function that is in general hard to invert, unless some additional information
(the trapdoor) is provided. Note that such an object is different with respect to
traditional trapdoor functions. A trapdoor one-way function is always easy to
compute, whereas a trapdoor hard-to-invert function may be not only hard to
invert, but “ at least in some cases “ also hard to compute [10]. As it will become
apparent in the next sections, this requirement is not strong because basically
all the classical public-key encryption schemes fit it (RSA [23], Rabin with Blum
moduli [22], ElGamal [12], and even the recent Okamoto-Uchiyama™s [20] and
Paillier™s schemes [21]). More precisely our results can be described as follows.
First, after having described our security model, we present a very general
construction “ denoted IPAKE for Isomorphism for Password-based Authenticated
Key Exchange “ and we prove it is secure. Our security result relies on the com-
putational properties of the chosen trapdoor hard-to-invert isomorphism family,
in the random-oracle model. As a second result we pass instantiating the general
construction with specific encryption schemes. We indeed show that trapdoor
hard-to-invert isomorphisms can be based on the Diffie-Hellman problem, on
the RSA problem, and even on integer factoring.
For lack of space, we refer to the full version [8] for the two first applications,
since they are not really new. Plugging ElGamal directly leads to one of the
AuthA variants, proposed to IEEE P1363 [2], or to PAK [5]. The security has
already been studied in several ideal models [5“7]. The case of RSA leads to
a scheme similar to RSA-OKE, SNAPI [19,18], or to the scheme proposed by
Zhu et al. [26].
More interestingly using such methods we can construct a very efficient solu-
tion from the Rabin function. To our knowledge this is the first efficient password-
based authenticated key exchange scheme based on factoring.

2 Preliminaries
Denote with the set of natural numbers and with the set of positive real
numbers. We say that a function is negligible if and only if for every
polynomial there exists an such that for all
TEAM LinG
IPAKE: Isomorphisms for Password-Based Authenticated Key Exchange 481

If A is a set, then indicates the process of selecting at random and
uniformly over A (which in particular assumes that A can be sampled efficiently).
2.1 Trapdoor Hard-to-Invert Isomorphisms
Let I be a set of indices. Informally a family of trapdoor hard-to-invert isomor-
phisms is a set satisfying the following conditions:
1. one can easily generate an index which provides a description of the func-
tion “ a morphism “, its domain and range (which are assumed
to be isomorphic groups), and a trapdoor
2. for a given one can efficiently sample pairs with uniformly
distributed in
3. for a given one can efficiently decide
4. given the trapdoor one can efficiently invert and thus recover
5. without the trapdoor, inverting is hard.
This is almost the same definition as for trapdoor one-way permutations with
homomorphic properties. There is a crucial difference however: one can sample
pairs, but may not necessarily be able to compute for a given (point 2
above). As a consequence, the function is hard-to-invert, but it may be hard to
compute as well.
More formally we say that F defined as above is a family of trapdoor hard-
to-invert isomorphisms if the following conditions hold:
1 There exist a polynomial and a probabilistic polynomial time Turing
Machine Gen which on input (where is a security parameter) outputs
pairs where is uniformly distributed in I and The
index defines and which are isomorphic groups, an isomorphism
from onto and a set of values uniformly samplable, which
will be used to sample pairs. The information is referred as
the trapdoor.
2.1 There exists a polynomial time Turing Machine which on input
and outputs Furthermore, for any the machine

<<

. 15
( 19)



>>