Problém batohu a jeho aplikace
| Thesis title in Czech: | Problém batohu a jeho aplikace |
|---|---|
| Thesis title in English: | The knapsack and its applications |
| Key words: | problém batohu, NP úplné problémy, LLL algoritmus |
| English key words: | knapsack problem, NP complete problems, LLL algorithm |
| Academic year of topic announcement: | 2016/2017 |
| 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: | 01.02.2017 |
| Date of assignment: | 14.02.2017 |
| Confirmed by Study dept. on: | 21.03.2017 |
| Date and time of defence: | 13.09.2017 00:00 |
| Date of electronic submission: | 19.07.2017 |
| Date of submission of printed version: | 21.07.2017 |
| Date of proceeded defence: | 13.09.2017 |
| Opponents: | doc. Mgr. et Mgr. Jan Žemlička, Ph.D. |
| Guidelines |
| Práce se bude zabývat problémem batohu v následujících souvislostech.
1. Shrnutí známých výsledků o složitosti problému batohu (NP úplnost, které instance jsou snadné, souvislost se složitostí dalších problémů). 2. Klasický Merkle-Hellmanův kryptosystém, útoky na něj, různé modifikace kryptosystému a útoky na tyto modifikace. 3. Konstrukce jednosměrných funkcí, které svou bezpečnost zakládají na zobecněném knapsacku. 4. Bude-li čas, je též možno zpracovat shrnutí modernějších kryptosystémů založených na problému batohu a útoků na ně. |
| References |
| V. Lyubashevsky, D. Micciano, Generalized Compact Knapsacks are Collision Resistant, Electronic Colloquium
on Computational Complexity, Report No. 142 (2005) A. Odlyzko, The Rise and Fall of Knapsack Cryptosystems, http://www.dtc.umn.edu/~odlyzko/doc/arch/knapsack.survey.pdf M.R. Garey, D. S. Johnson, Computers and intractability: a guide to the theory of NP-completeness. New York: W. H. Freeman and Company, c1979. další literatura podle toho, kam se bude práce ubírat |