ńňđ. 15 |

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 |