Can we Construct Unbounded Time-Stamping Schemes from Collision-Free Hash Functions?

Käesolevas töös uurime piiranguteta ajatempliskeemi jaoks turvaliste räsifunktsioonide konstrueerimise võimalusi kollisioonivabadest räsifunktsioonidest. Kasutades Harberi ja Stornetta poolt loodud ajatembeldusskeemi ning Buldase ja Saarepera poolt selle jaoks konstrueeritud turvatingimust uurime nn. musta kasti konstruktsioonide võimatuse tõestuse võimalikkust. Kuna võimatuse tõestuse lihtsaim variant on oraakliga eraldus, keskendumegi just ühe selle eralduse jaoks sobivana tunduva oraakli omaduste ja võimaluste uurimisele. Me eeldame, et oraakel konstrueerib räsipuu, väljastab puu juurväärtuse ning annab seejärel sellest puust lähtuvalt ajatemplisertifikaate. Me tõestame, et kui oraakli argumendiks olev musta kasti meetodil koostatud räsifunktsioon ainult algse räsifunktsiooni kollisioonipaare kontrollib või nn. suurem-kui predikaati kasutab, ei saa seda oraaklit kasutada kollisioonide leidmiseks . Töö tulemused annavad lootust, et nimetatud oraakel on tõepoolest eralduseks sobiv ja lubavad oletada, et sarnaste oraaklite edasine uurimine võib lõpuks probleemi lahenduseni viia.It has been known for quite some time that collision-resistance of hash functions does not seem to give any actual security guarantees for unbounded hash-tree time-stamping, where the size of the hash-tree created by the time-stamping service is not explicitly restricted. We focus on the possibility of showing that there exist no black-box reductions of unbounded time-stamping schemes to collision-free hash functions. We propose an oracle that is probably suitable for such a separation and give strong evidence in support of that. However, the existence of a separation still remains open. We introduce the problem and give a construction of the oracle relative to which there seem to be no secure time-stamping schemes but there still exist collision-free hash function families. Although we rule out many useful collision-finding strategies (relative to the oracle) and the conjecture seems quite probable after that, there still remains a possibility that the oracle can be abused by some very smartly constructed wrappers. We also argue why it is probably very hard to give a correct proof for our conjecture