dc.contributor.author | Christianson, B. | |
dc.contributor.author | Wheeler, D. | |
dc.date.accessioned | 2011-03-22T16:22:43Z | |
dc.date.available | 2011-03-22T16:22:43Z | |
dc.date.issued | 1999 | |
dc.identifier.citation | Christianson , B & Wheeler , D 1999 , Merkle puzzles revisited - finding matching elements between lists . UH Computer Science Technical Report , vol. 336 , University of Hertfordshire . | |
dc.identifier.other | dspace: 2299/5525 | |
dc.identifier.uri | http://hdl.handle.net/2299/5525 | |
dc.description.abstract | Consider the following problem. A and B 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/log2N the protocol requires on the order of log2N 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 | 354993 | |
dc.language.iso | eng | |
dc.publisher | University of Hertfordshire | |
dc.relation.ispartofseries | UH Computer Science Technical Report | |
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 | |
rioxxterms.type | Other | |
herts.preservation.rarelyaccessed | true | |