Algoritmy pro hledání vektorů v mřížích
| Název práce v češtině: | Algoritmy pro hledání vektorů v mřížích |
|---|---|
| Název v anglickém jazyce: | Searching for vectors in lattices |
| Akademický rok vypsání: | 2022/2023 |
| Typ práce: | diplomová práce |
| Jazyk práce: | |
| Ú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.09.2022 |
| Datum zadání: | 26.09.2022 |
| Datum potvrzení stud. oddělením: | 05.10.2022 |
| Zásady pro vypracování |
| Hlavním cílem práce je provést rešerši některých známých algoritmů pro řešení mřížových problémů relevantních pro kryptografii (SVP, CVP, SIVP a jejich aproximační verze).
Studentka se pokusí alespoň experimentálně porovnat efektivitu těchto algoritmů na vstupech speciálního tvaru (například na mřížích používaných pro kryptoanalýzu konkrétních schémat). |
| Seznam odborné literatury |
| A. Becker, N. Gama and A. Joux: A sieve algorithm based on overlattices, LMS J. Comput. Math. 17 (Special issue A) (2014) 49–70.
D. Micciancio, S. Goldwasser: Complexity of Lattice problems - a cryptographic perspective, Kluwer, 2002. D. Micciancio, P. Voulgaris: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computation, SIAM J. Comput., Vol. 42, No. 3, pp. 1364–1391. R. Kanan: Improved algorithms for integer programming and related lattice problems, STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory of computing, December 1983. |