dc.contributor.author | Christianson, B. | |
dc.contributor.author | Wheeler, D. | |
dc.date.accessioned | 2010-03-17T15:40:27Z | |
dc.date.available | 2010-03-17T15:40:27Z | |
dc.date.issued | 2002 | |
dc.identifier.citation | Christianson , B & Wheeler , D 2002 , ' Merkle Puzzles Revisited — Finding Matching Elements between Lists ' , Lecture Notes in Computer Science (LNCS) , vol. 2467 , pp. 87-94 . https://doi.org/10.1007/3-540-45807-7_13 | |
dc.identifier.issn | 0302-9743 | |
dc.identifier.other | dspace: 2299/4353 | |
dc.identifier.other | ORCID: /0000-0002-3777-7476/work/76728349 | |
dc.identifier.uri | http://hdl.handle.net/2299/4353 | |
dc.description | “The original publication is available at www.springerlink.com”. Copyright Springer. | |
dc.description.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. | en |
dc.format.extent | 358417 | |
dc.language.iso | eng | |
dc.relation.ispartof | Lecture Notes in Computer Science (LNCS) | |
dc.title | Merkle Puzzles Revisited — Finding Matching Elements between Lists | en |
dc.contributor.institution | School of Computer Science | |
dc.contributor.institution | Science & Technology Research Institute | |
dc.description.status | Peer reviewed | |
rioxxterms.versionofrecord | 10.1007/3-540-45807-7_13 | |
rioxxterms.type | Journal Article/Review | |
herts.preservation.rarelyaccessed | true | |