Klasični i kvantni napadi na problem diskretnog logaritma

diplomski rad

• Autor: Petar Vlašić
• Mentor: Andrej Dujella (mentor)
• Član povjerenstva: Andrej Dujella (predsjednik povjerenstva)
• Član povjerenstva: Nikola Sandrić (član povjerenstva)
• Član povjerenstva: Zvonimir Bujanović (član povjerenstva)
• Član povjerenstva: Franka Miriam Bruckler (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2018-09-27, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: problem diskretnog logaritma; DLP; klasično računalo; kvantno računalo; klasični napadi na DLP; kriptografija; kvantni napad na DLP
• Ključne riječi (engleski): discrete logarithm problem; DLP; classical computer; quantum computer; classical attacks on DLP; cryptography; quantum attack on DLP
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:220837
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2019-07-05 10:19:51