Důkazy bezpečností hashovacích funkcí

• Název práce v češtině: Důkazy bezpečností hashovacích funkcí
• Název v anglickém jazyce: Proving security of hash functions
• Akademický rok vypsání: 2018/2019
• Typ práce: diplomová práce
• Jazyk práce: čeština
• Ústav: Katedra algebry (32-KA)
• Vedoucí / školitel: doc. Mgr. Pavel Příhoda, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 25.11.2018
• Datum zadání: 06.12.2018
• Datum potvrzení stud. oddělením: 20.12.2018
• Datum a čas obhajoby: 11.06.2019 09:00
• Datum odevzdání elektronické podoby: 09.05.2019
• Datum odevzdání tištěné podoby: 10.05.2019
• Datum proběhlé obhajoby: 11.06.2019
• Oponenti: doc. Mgr. et Mgr. Jan Žemlička, Ph.D.

Zásady pro vypracování

Práce by se měla zaměřit na Ajtaiovu redukci hledání kolize určité množiny hashovacích funkcí v průměrném případě na problém hledání krátké báze mřížky. Student by se měl pokusit přepsat původní důkaz to matematicky korektní formy a určit aproximační faktory, které jsou zaručny důkazem. V další práci by se bylo možno zaměřit na různá vylepšení Ajtaiova výsledku, modernější metody poskytující lepší aproximační faktory. Pokud by toto bylo příliš obtížné, lze se též věnovat různým modifikacím Ajtaiova hashování vedoucí k efektivnějším návrhům.

Seznam odborné literatury

M. Ajtai: Generating hard instances of lattice problems. Quaderni di Matematica, 13:1–32, 2004.

D. Micciancio. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Computational Complexity, 16(4):365–411, 2007.

D. Micciancio, O. Regev. Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput., 37(1):267–302, 2007.

C. Peikert, A. Rosen. Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In TCC, pages 145–166. 2006.