Problém batohu a jeho aplikace

• Název práce v češtině: Problém batohu a jeho aplikace
• Název v anglickém jazyce: The knapsack and its applications
• Klíčová slova: problém batohu, NP úplné problémy, LLL algoritmus
• Klíčová slova anglicky: knapsack problem, NP complete problems, LLL algorithm
• Akademický rok vypsání: 2016/2017
• 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í: 01.02.2017
• Datum zadání: 14.02.2017
• Datum potvrzení stud. oddělením: 21.03.2017
• Datum a čas obhajoby: 13.09.2017 00:00
• Datum odevzdání elektronické podoby: 19.07.2017
• Datum odevzdání tištěné podoby: 21.07.2017
• Datum proběhlé obhajoby: 13.09.2017
• Oponenti: doc. Mgr. et Mgr. Jan Žemlička, Ph.D.

Zásady pro vypracování

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ě.

Seznam odborné literatury

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