Merkle Puzzles Revisited — Finding Matching Elements between Lists

B. Christianson; D. Wheeler

doi:10.1007/3-540-45807-7_13

Merkle Puzzles Revisited — Finding Matching Elements between Lists

B. Christianson, D. Wheeler

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

26 Downloads (Pure)

Abstract

Consider the following problem. A and B each have a N-element set of bit-strings. They wish to find all collisions, in other words to find the common strings of their sets or to establish that there are none. How much data must A and B exchange to do this? Problems of this type arise in the context of Merkle puzzles, for example where A and B propose to use the collision between two randomly constructed lists to construct a cryptographic key. Here we give a protocol for finding all the collisions. Provided the number of collisions is small relative to N/ log2 N the protocol requires on the order of log2 N messages and the total amount of data which A and B need exchange is about 4.5N bits. The collision set can also be determined in three messages containing a total of at most 9N bits provided N < 21023.

Original language	English
Pages (from-to)	87-94
Journal	Lecture Notes in Computer Science (LNCS)
Volume	2467
DOIs	https://doi.org/10.1007/3-540-45807-7_13
Publication status	Published - 2002

Access to Document

10.1007/3-540-45807-7_13

903862.pdf

Cite this

@article{a6d576c17fb84036bf7297ee866193c8,

title = "Merkle Puzzles Revisited — Finding Matching Elements between Lists",

abstract = "Consider the following problem. A and B each have a N-element set of bit-strings. They wish to find all collisions, in other words to find the common strings of their sets or to establish that there are none. How much data must A and B exchange to do this? Problems of this type arise in the context of Merkle puzzles, for example where A and B propose to use the collision between two randomly constructed lists to construct a cryptographic key. Here we give a protocol for finding all the collisions. Provided the number of collisions is small relative to N/ log2 N the protocol requires on the order of log2 N messages and the total amount of data which A and B need exchange is about 4.5N bits. The collision set can also be determined in three messages containing a total of at most 9N bits provided N < 21023.",

author = "B. Christianson and D. Wheeler",

note = "“The original publication is available at www.springerlink.com”. Copyright Springer.",

year = "2002",

doi = "10.1007/3-540-45807-7_13",

language = "English",

volume = "2467",

pages = "87--94",

journal = "Lecture Notes in Computer Science (LNCS)",

issn = "0302-9743",

publisher = "Springer Nature Link",

}

TY - JOUR

T1 - Merkle Puzzles Revisited — Finding Matching Elements between Lists

AU - Christianson, B.

AU - Wheeler, D.

N1 - “The original publication is available at www.springerlink.com”. Copyright Springer.

PY - 2002

Y1 - 2002

N2 - Consider the following problem. A and B each have a N-element set of bit-strings. They wish to find all collisions, in other words to find the common strings of their sets or to establish that there are none. How much data must A and B exchange to do this? Problems of this type arise in the context of Merkle puzzles, for example where A and B propose to use the collision between two randomly constructed lists to construct a cryptographic key. Here we give a protocol for finding all the collisions. Provided the number of collisions is small relative to N/ log2 N the protocol requires on the order of log2 N messages and the total amount of data which A and B need exchange is about 4.5N bits. The collision set can also be determined in three messages containing a total of at most 9N bits provided N < 21023.

AB - Consider the following problem. A and B each have a N-element set of bit-strings. They wish to find all collisions, in other words to find the common strings of their sets or to establish that there are none. How much data must A and B exchange to do this? Problems of this type arise in the context of Merkle puzzles, for example where A and B propose to use the collision between two randomly constructed lists to construct a cryptographic key. Here we give a protocol for finding all the collisions. Provided the number of collisions is small relative to N/ log2 N the protocol requires on the order of log2 N messages and the total amount of data which A and B need exchange is about 4.5N bits. The collision set can also be determined in three messages containing a total of at most 9N bits provided N < 21023.

U2 - 10.1007/3-540-45807-7_13

DO - 10.1007/3-540-45807-7_13

M3 - Article

SN - 0302-9743

VL - 2467

SP - 87

EP - 94

JO - Lecture Notes in Computer Science (LNCS)

JF - Lecture Notes in Computer Science (LNCS)

ER -

Merkle Puzzles Revisited — Finding Matching Elements between Lists

Abstract

Access to Document

Fingerprint

Cite this