prikaz prve stranice dokumenta Klasični i kvantni napadi na problem diskretnog logaritma
  Download
PDF 304.2 KB
master's thesis
Klasični i kvantni napadi na problem diskretnog logaritma
Zagreb: University of Zagreb, Faculty of Science, 2018. urn:nbn:hr:217:220837
Vlašić, Petar
University of Zagreb
Faculty of Science
Department of Mathematics

Institutional repository: Repository of the Faculty of Science

Cite this document

Vlašić, P. (2018). Klasični i kvantni napadi na problem diskretnog logaritma (Master's thesis). Zagreb: University of Zagreb, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:217:220837

Vlašić, Petar. "Klasični i kvantni napadi na problem diskretnog logaritma." Master's thesis, University of Zagreb, Faculty of Science, 2018. https://urn.nsk.hr/urn:nbn:hr:217:220837

Vlašić, Petar. "Klasični i kvantni napadi na problem diskretnog logaritma." Master's thesis, University of Zagreb, Faculty of Science, 2018. https://urn.nsk.hr/urn:nbn:hr:217:220837

Vlašić, P. (2018). 'Klasični i kvantni napadi na problem diskretnog logaritma', Master's thesis, University of Zagreb, Faculty of Science, accessed 22 November 2024, https://urn.nsk.hr/urn:nbn:hr:217:220837

Vlašić P. Klasični i kvantni napadi na problem diskretnog logaritma [Master's thesis]. Zagreb: University of Zagreb, Faculty of Science; 2018 [cited 2024 November 22] Available at: https://urn.nsk.hr/urn:nbn:hr:217:220837

P. Vlašić, "Klasični i kvantni napadi na problem diskretnog logaritma", Master's thesis, University of Zagreb, Faculty of Science, Zagreb, 2018. Available at: https://urn.nsk.hr/urn:nbn:hr:217:220837

Metadata
TitleKlasični i kvantni napadi na problem diskretnog logaritma
AuthorPetar Vlašić
MentorAndrej Dujella (mentor)
Committee memberAndrej Dujella (predsjednik povjerenstva)
Committee memberNikola Sandrić (član povjerenstva)
Committee memberZvonimir Bujanović (član povjerenstva)
Committee memberFranka Miriam Bruckler (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Science
(Department of Mathematics)
Zagreb
Defense date and country2018-09-27, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Abstract
Ovaj rad proučava problem diskretnog logaritma (DLP) koji je zanimljiv jer je težak u općenitom slučaju. U prvom poglavlju uvode se pojmovi prostorne i vremenske složenosti na klasičnom računalu i navode se odnosi između osnovnih klasa složenosti. Zatim smo pričali o kvantnim računalima koja su zasnovana na karakteristikama kvantnih fenomena, poput kvantnih interferencija i kvantnih sprezanja. Slično kao za klasična računala definirali smo klase vremenske i prostorne složenosti za kvantna računala. U drugom poglavlju prvo je dana definicija problema diskretnog logaritma. U radu se nakon toga obraduju klasični napadi na DLP. Klasične napade možemo podijeliti u tri skupine. Algoritmi koji rade na proizvoljnim grupama, dakle ne iskorištavaju nikakva posebna svojstva algoritama. To su Shanksova baby-step giant-step metoda i Pollardova \(\rho\)-metoda. Onda imamo algoritme koji rade dobro u konačnim grupama za koje je red grupe gladak. U ovoj kategoriji se nalazio Silver-Pohlig-Hellman algoritam. Konačno, postoje algoritmi koji iskorištavaju metode za reprezentiranje grupe elemenata iz relativno malog skupa. U ovu grupu spadaju Adelmanov index calculus algoritam i Gordonov NFS algoritam. No ipak, nijedan od ovih algoritama nije primjenjiv u praksi što povlaci da je kriptografija bazirana na DLP-u sigurna. Kad bi uspjeli efikasno riješiti DLP onda bi i razbili kriptografiju baziranu na DLP-u. Shor je pokazao da se DLP može riješiti u \(\mathcal{BQP}\) vremenskoj složenosti, gdje je \(\mathcal{BQP}\) klasa problema koji su efikasno rješivi na kvantnom Turingovom stroju. Prema tome, kvantna računala mogu razbiti kriptografiju baziranu na DLP-u u polinomnom vremenu. S ovim se bavi treće poglavlje. Dajemo ideju kvantnog napada na DLP. Zatim radimo lakši slučaj kvantnog napada koji je, u stvari, kvantna verzija Pohlig-Hellmanovog algoritma. Iako nema stvarne potrebe za kvantnim algoritmom za lakši slučaj DLP-a, to smo napravili da pokažemo da kvantna računala jednako dobro rade za lakši slučaj kao i klasična. Na kraju pokazujemo da kvantna računala mogu riješiti i općeniti slučaj DLP- u polinomnom vremenu.
Abstract (english)
This thesis studies discrete logarithm problem (DLP) which is interesting because it is hard in general case. In the first chapter we introduce concepts of time and space complexity on a classical computer and we discuss relations between complexity classes. Than we discuss about quantum computers which rely on quantum phenomena, such as quantum interference and quantum entanglement. Than we define time and space complexity classes, in a similar way as for conventional computers. In the second chapter first we introduce definition of the discrete logarithm problem. Next, in the thesis we describe classical attacks on the DLP. There are three different categories of classical attacks. Algorithms that work for arbitrary groups, that is, those that do not exploit any specific properties of groups. Algorithms in this category are Shanks baby-step giant-step method and \(\rho\)-method. Then there are algorithms that work well in finite groups that have smooth order. Silver-Pohlig-Hellman is in this category. At last, we have algorithms that exploit methods for representing group elements as products of elements form relatively small set. In this category are Adleman’s index calculus algorithm and Gordon’s NFS algortihm. However, none of these methods is not effective in practice so this would imply that the DLP-based cryptography is secure. Solving DLP is equivalent to breaking DLP-based cryptography. Shor showed that DLP can be solved in \(\mathcal{BQP}\), where \(\mathcal{BQP}\) is the class of problem that is efficiently solvable in polynomial time on a quantum Turing machine. Hence, all DLP-based cryptography systems can be broken in polynomial time on a quantum computer. This is discussed in third chapter. We give idea for quantum attack on DLP. Then we do easy case of DLP, we did that to show that quantum computers compute easy case equally good as conventional computers. At last, we show that quantum computers can solve general case of DLP in polynomial time.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:217:220837
Study programmeTitle: Computer Science and Mathematics
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2019-07-05 10:19:51