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

• Thesis title in Czech: Důkazy bezpečností hashovacích funkcí
• Thesis title in English: Proving security of hash functions
• Academic year of topic announcement: 2018/2019
• Thesis type: diploma thesis
• Thesis language: čeština
• Department: Department of Algebra (32-KA)
• Supervisor: doc. Mgr. Pavel Příhoda, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 25.11.2018
• Date of assignment: 06.12.2018
• Confirmed by Study dept. on: 20.12.2018
• Date and time of defence: 11.06.2019 09:00
• Date of electronic submission: 09.05.2019
• Date of submission of printed version: 10.05.2019
• Date of proceeded defence: 11.06.2019
• Opponents: doc. Mgr. et Mgr. Jan Žemlička, Ph.D.

Guidelines

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.

References

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.