Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Post-quantum security in the presence of superposition queries

Ehsan Ebrahimi

Published Nov 26, 2018• 1 citation
OpenAlex

Abstract

Teadlased ja insenerid on juba mõnda aega püüdnud ehitada kvantseadustel põhinevat arvutit. See uus masin (kvantarvuti) on võimeline lahendama arvutuslikult keerulisi ülesandeid, nagu näiteks täisarvude tegurdamine, palju kiiremini kui ükski klassikaline arvuti. Tegurdamisel tuleb täisarv esitada väiksemate täisarvude korrutisena. Näiteks arvu 15 tegurdamiseks tuleb see esitada korrutisena 3 x 5. Suure arvu tegurdamine klassikalisel arvutil võtab väga kaua aega, samas kui kvantarvuti suudab selle ülesande raskusteta oluliselt kiiremini lahendada. Suure ajalise keerukusega probleemide kiire lahendamine on küll põnev saavutus, kuid paraku põhinevad praegu laialdases kasutuses olevad krüpteerimisalgoritmid, nagu näiteks RSA, just tegurdamise keerukusel. Keegi ei saa meie krüpteeritud andmeid dekrüpteerida, kui tal puudub võimekus kiiresti tegurdada. RSA algoritmi kasutamine krüptosüsteemides on väga levinud. Näiteks Eesti ID-kaart kasutab RSA algoritmi digitaalseks allkirjastamiseks ja ka muude teenuste jaoks. Kuna kvantarvuti suudab aga kiiresti tegurdada, ei ole RSA algoritm suurte kvantarvutite vastu turvaline. Postkvant-krüptograafia on uus valdkond, mis tegeleb just selliste probleemidega. Eesmärgiks on konstrueerida krüpteerimisalgoritm, mis on turvaline isegi kvantründajate vastu. Esimeseks sammuks on leida matemaatiline probleem, mis on keeruline ka kvantarvutite jaoks. Seejärel on võimalik konstrueerida krüptograafilisi algoritme, mis põhinevad neil probleemidel. Lõpuks tuleb tõestada, et meie krüptograafiline skeem on turvaline. Selles väitekirjas keskendume eelnimedatud sammudest just viimasele. Me verifitseerime osade krüptosüsteemide turvalisuse kvantründajate suhtes ja tõestame, et osad krüptograafilised konstruktsioonid on kvantturvalised.

Related papers

Efficient multiparty computation secure against covert and active adversaries

Alisa Pankova

Turvaline ühisarvutus on tänapäevase krüptograafia üks tähtsamaid kasutusviise, mis koondab elegantsed matemaatilised lahendused praktiliste rakenduste ehitamiseks, võimaldades mitmel erineval andmeomanikul sooritada oma andmetega suvalisi ühiseid arvutusi, ilma neid andmeid üksteisele avaldamata. \nPassiivse ründaja vastu turvalised protokollid eeldavad, et kõik osapooled käituvad ausalt. Aktiivse ründaja vastu turvalised protokollid ei lekita privaatseid andmeid sõltumata ründaja käitumisest. Käesolevas töös esitatakse üldine meetod, mis teisendab passiivse ründaja vastu turvalised ühisarvutusprotokollid turvaliseks aktiivse ründaja vastu. Meetod on optimeeritud kolme osapoolega arvutusteks üle algebraliste ringide; praktikas on see väga efektiivne mudel, mis teeb reaalse maailma rakendused teostatavateks. Meetod lisab esialgsele arvutusprotokollile täitmisjärgse verifitseerimisfaasi, mis muudab valesti käitunud osapooltel vahelejäämise vältimise tõenäosuse kaduvväikseks, säilitades esialgse protokolli turvagarantiid. \nLisaks uurib käesolev töö rünnete uut eesmärki, mis seisneb mingi ausa osapoole vaate manipuleerimises sellisel viisil, et ta saaks midagi teada teise ausa osapoole privaatsete andmete kohta. Ründaja ise ei tarvitse seda infot üldse teada saada. Sellised ründed on olulised, sest need kohustavad ausat osapoolt tühjendama oma süsteemi teiste osapoolte andmetest, kuid see ülesanne võib olla päris mittetriviaalne. Eelnevalt pakutud verifitseerimismehhanisme täiendatakse nii, et privaatsed andmed oleksid kaitstud ka ausate osapoolte eest. \nPaljud ühisarvutusplatvormid on varustatud programmeerimiskeelega, mis võimaldab kirjutada privaatsust säilitavaid rakendusi ilma allolevale krüptograafiale mõtlemata. Juhul, kui programm sisaldab tingimuslauseid, kus arvutusharu valik sõltub privaatsetest andmetest, ei tohi ükski osapool haru valikust midagi teada, nii et üldjuhul peavad osapooled täitma kõik harud. Harude suure arvu kor-ral võib arvutuslik lisakulu olla ülisuur, sest enamik vahetulemustest visatakse ära. Käesolevas töös pakutakse selliseid lisakulusid vähendavat optimeerimist.

•May 12, 2017•1 citation

Quantum query algorithms

Taisija Miščenko-Slatenkova

Anotācija\nKvantu skaitļošana ir datorzinātnes apakšnozare, kas balstās uz kvantu mehānikas likumiem.\nKvantu vaicājošais algoritms ir galvenais pētāmais objekts. Galvenais darba mērķis ir padarīt\nkvantu algoritma konstruēšanu pēc iespējas vienkāršāku.\nPētījumā ir aprakstīti kvantu vaicājošie algoritmi, kas rēķina Būla funkcijas uzdodot nelielu\nskaitu vaicājumu, un tiek piedāvāti kvantu vaicājošie algoritmi daudzvērtīgu funkciju\naprēķināšanai. Darbā ir aprakstīti vairāki efektīvi kvantu algoritmi konkrētu uzdevumu veikšanai.\nPaši nozīmīgākie ir kvantu vaicājošie algoritmi ar ierobežotu kļūdu, piemēram, piedāvāts algoritms\ndivu bitu AND Būla funkcijai, kas izmanto vienu vienīgu vaicājumu un izsniedz pareizu atbildi ar\nvarbūtību 9/10. Katrai aprakstītajai funkciju kopai ir veikta pamatīga kvantu un klasiskās\nsarežģītības analīze.\nPēdējā pētījuma daļa ir veltīta Būla funkcijām ar zemas pakāpes polinomiem, kuri\nreprezentē dotās funkcijas. Darbā piedāvātie paņēmieni ļauj uzkonstruēt Būla funkcijas ar\npietiekami lielu intervālu starp funkcijas determinēto sarežģītību un reprezentējošā polinoma\npakāpi.\nAtslēgas vārdi: kvantu skaitļošana, vaicājošais modelis, vaicājošais algoritms, daudzvērtīga\nfunkcija, zemas pakāpes Būla funkcija

•Jan 1, 2013•3 citations

Quantum algorithm complexity

Vasilijs Kravcevs

Kvantu algoritmu veiktspējas pārākums par klasiskajiem algoritmiem ir galvenais iemesls pašreizējai lielai ieinteresētībai par kvantu skaitļošanu. Vieni no slavenākiem kvantu algoritmiem ir Grovera meklēšanas algoritms un šora skaitļu faktorizācijas algoritms. Piemēram, Grovera algoritms atrisina elementa meklēšanas problēmu N elementu sarakstā ar laiku Ø(pN), kaut klasiskam algoritmam ir nepieciešams ¬(N) laiks, lai atrisinātu šo problēmu. Tātad mēs esam ļoti ieinteresēti atrast šādas problēmas, kurām kvantu algoritms var būt pārāks par klasisko analogu. Kvantu skaitļošanas centrālais jautājums ir, cik spēcīgi ir kvantu algoritmi? Cik liels veiktspējas uzlabo jums ir iespējams? Šajā darbā mēs sniedzam dažus jautājumus uz šīm jautājumiem. Mēs aplūkojam divas lielas problēmas. Pirmkārt, mēs aplūkojam cikla eksistences grafā problēmu. Mēs piedāvājam kvantu vaicājošo algo ritmu, kas atrisina šo problēmu efektīvāk par jebkuru klasisko analogu, un pierādām, ka mūsu piedāvātais algoritms ir optimāls. Otrkārt mēs turpinām pētījumus par varbūtiskiem apgriežamiem automātiem, izpētot apstādināmo varbūtisko apgriežamo automātu (DH-PRA) īpašības. Mēs parādām vispārējo valodu klasi, ko nevar pazīt ar DH-PRA, un kas ir ļoti līdzīga valodu klasei, ko nevar pazīt ar daudzmērījumu kvantu automātiem (MM-QFA). Mēs arī parādām, ka valodu klase, kuru pazīst DH-PRA nav slēgta pret apvienojuma operāciju. Tas ļauj mums izteikt minējumu, ka valodu klase, ko pazīst DH-PRA automāti iekļauj valodu klasi, ko pazīst MM- QFA vai nu šīs klases ir ekvivalentas. Mēs turpinām strādāt pie šī minējuma pierādīšanas.

•Jan 1, 2008•1 citation

Kvanttitietokoneiden vaikutus moderneihin salausmenetelmiin

Nettanora Nurmi

Tämän insinöörityön keskeinen tutkimuskysymys on, miten kvanttitietokoneiden kehitys vaikuttaa nykyisiin salausmenetelmiin ja millä tavoin post-kvanttinen kryptografia vastaa näihin uhkiin. Lisäksi työ tarkastelee post-kvanttisten ratkaisujen käyttöönottoon liittyviä teknisiä ja organisatorisia haasteita. Tutkimuskysymykseen vastaamiseksi työssä tarkastellaan kvanttilaskennan keskeisiä periaatteita, kuten superpositiota, lomittumista ja interferenssiä, jotka mahdollistavat laskentatehon, johon klassiset tietokoneet eivät kykene. Näiden ilmiöiden hyödyntäminen tekee kvanttitietokoneista erityisen tehokkaita ratkaisemaan matemaattisia ongelmia, jotka muodostavat nykyisten epäsymmetristen salausmenetelmien, kuten RSA:n ja ECC:n, turvallisuuden perustan. Työssä analysoitiin modernien salausalgoritmien toimintaa ja kvanttiuhkia, jotka kohdistuvat erityisesti julkisen avaimen menetelmiin. Symmetristen algoritmien, kuten AES:n, todettiin säilyttävän turvallisuutensa kvanttiuhkia vastaan avainpituuksia kasvattamalla, kun taas epäsymmetriset menetelmät ovat haavoittuvaisia Shorin algoritmille. Lisäksi työssä esiteltiin NIST:n standardoimat post-kvanttiset algoritmit, kuten Kyber ja Dilithium, sekä niiden keskeiset ominaisuudet ja käyttöönottoon liittyvät haasteet. Työn johtopäätökset osoittavat, että siirtyminen post-kvanttiseen kryptografiaan on välttämätöntä tulevien vuosien aikana. Kvanttiuhkien aikataulu on epävarma, ja erityisesti Harvest Now, Decrypt Later -skenaario korostaa tarvetta aloittaa valmistelut ajoissa. Työ tarjoaa kokonaiskuvan kvanttiajan tietoturvahaasteista ja toimii lähtökohtana organisaatioille, jotka suunnittelevat kvanttiturvallisten järjestelmien käyttöönottoa.

•Jan 1, 2026•0 citations

Post quantum cryptography

Veysel Gültekin

Kuantum bilgisayarların keşfi ile klasik kriptografi olarak adlandırdığımız ve günümüzde tüm kriptografik cihazlarda kullanılan kriptosistemlerin güvenliği tartışılır hale gelmiştir. Kuantum bilgisayarlardaki hızlı gelişme sonucunda kriptografideki çalışma alanı kuantum bilgisayarlara karşı güvenli sistemlerin tasarlanması ve analiz edilmesi yönünde değişmiştir. Shor Algoritması ile çarpanlara ayırma probleminin çözümünün üstel zamandan polinom zamana indirilmesiyle özellikle asimetrik kriptosistemler tehdit altına girmiştir. Günümüzde verilerin büyük çoğunluğu klasik kriptografide kullanılan anahtar anlaşma algoritmaları ile paylaşılan anahtar kullanılarak simetrik şifreleme algoritmaları ile şifreli olarak saklanmaktadır. Kuantum kriptografinin esas etkisi asimetrik kriptografiye olmasına rağmen simetrik şifreleme algoritmalarının anahtarları asimetrik kriptografi ile paylaşıldığı için tüm veriler kuantum tehtidinden etkilenmektedir. Özellikle şifrelenen verilerin geriye dönük olarak tutulabileceği göz önünde bulundurulursa ve yakın zamanda kuantum bilgisayların çarpanlara ayırma problemini etkili bir şekilde çözecek seviyeye gelmesi durumunda şu andan itibaren simetrik şifreleme algoritmaları ile şifrelenen veriler de ileride çözülebilecektir. İmza algoritmalarının etkilenmesi ise imzanın kimlik doğrulama mekanizmaları veya mesajın kaynağını doğrulamak gibi o ana ait bir kriptografik hizmeti sağladığı için daha kısıtlı olacaktır. Bu yüzden kuantum tehtidi için anahtar paylaşma probleminin çözümü imza probleminin çözümüne nazaran daha acil bir ihtiyaç olarak görülmektedir. Bu sebeplerle bu çalışmada kuantum sonrası kriptografinin anahtar paylaşma problemine getirdiği çözümler üzerinde durulacaktır. Burada bahsedilen her iki problem için de daha önceden AES'i blok şifreleme algoritması olarak bir yarışma aracılığıyla standartlaştıran NIST (Ulusal Standartlar ve Teknoloji Enstitüsü), standart bir algoritma seçmek için 2016 yılında bir yarışma başlatarak standart bir kuantum sonrası anahtar değişim algoritması ve imza algoritması seçme kararı almıştır. Bu süreçten sonra algoritma tasarımı ve analizi üzerine çalışmalar hızlanmıştır. Yarışmaya katılan algoritmalar dayandıkları zorluklara göre farklı gruplara ayrılabilir. Bunlar kafes tabanlı kriptosistemler, kod tabanlı kriptosistemler, isojeni tabanlı kriptosistemler, özet tabanlı kriptosistemler ve çok değişkenli polinom tabanlı kriptosistemlerdir. Bunların içinden en çok dikkat çeken ve üzerine çalışan homomorfik şifreleme gibi yapılarda da kullanılabilmesi itibariyle kafes tabanlı kriptosistemlerdir. Ayrıca yarışma neticesinde standart olarak seçilen Kyber Algoritması da kafes tabanlı bir anahtar değişim algoritmasıdır. Kod tabanlı kriptosistemler McEliece tarafından ortaya atılılmıştır ve asimetrik kriptografinin en eski problemlerinden biri olan kod çözme problemine dayanmaktadır. Anahtar boyutlarının büyük olması dezavantajından dolayı, kuantum tehditi ortaya çıkana kadar, görece az çalışılan bir alan olarak kalmıştır. Niederreiter kriptosisteminin ortaya çıkması ve anahtar boyutlarında iyileştirmeler yapılması ile kuantum sonrası anahtar değiştirme algoritmaları için önemli bir aday durumuna gelmişlerdir. Izojeni tabanlı algoritmalar klasik bilgisayarlarla kırılabilen bir saldırının ortaya çıkmasıyla riskli duruma düşmüştür. Her ne kadar NIST SIKE anahtar anlaşma algoritmasını alternatif algoritma adaylarına alsa da saldırı bu tarihten sonra ortaya çıktığı için kullanılması önerilmez ibaresi eklemiştir. Ayrıca bazı kriptosistemlerin analizi için üzerine yeterince çalışılmadığı düşünüldüğü için kuantum sonrası anahtar anlaşma algoritmalarının tek başına kullanılmasına şüpheyle bakılmaya başlanmıştır. Bu sebeple anahtar paylaşım problemini çözmek için kuantum sonrası algoritmalar, asimetrik kriptografi ve daha önce paylaşılmış ortak simetrik anahtarlardan en az iki tanesini kullanan hibrit anahtar paylaşım protokolleri de önerilmiştir. Bu çalışma kapsamında anahtar anlaşma problemini çözmek için geliştirilen önerilerden kabaca bahsedilecektir. Kafes tabanlı kriptosistemler ile Kod tabanlı kriptosistemlerin dayandıkları problemler ve bu problemler üzerine anahtar değişim mekanizmalarının nasıl kurulduğu anlatılacaktır. Ayrıca bazı analiz metotları anlatılarak standartta bulunan bazı algoritmaların güvenlik seviyeleri ve analizi hakkında bilgi verilecektir.

•Jan 26, 2023•0 citations

Postkvantkrüptograafia alused NIST standardiseerimisprogrammi põhjal

Helen Tera

Tänapäeval on andmeturve paljudes valdkondades määrava tähtsusega, kuid hiljutised edusammud kvantmehhaanika valdkonnas võivad tänased interneti turvaprotokollid ohtu seada. Kuna kvantvutid on tõenäoliselt võimelised murdma meie praeguseid krüptostandardeid, tekib vajadus tugevamate krüpteerimisalgoritmide järele. Viimaste kümnendite jooksul on postkvantkrüptograafia saanud palju tähelepanu, kuid siiani pole ükski postkvantkrüptograafiline algoritm standardiseeritud ulatuslikuks kasutamiseks. Seetõttu algatati NIST programm, mille eesmärk on valida uued krüptostandardid, mis säilitaks oma turvalisuse ka kvantarvutite vastu. Käesolev lõputöö annab ülevaate postkvantkrüptograafia erinevatest valdkondadest - võrepõhine, koodipõhine, räsipõhine ja mitmemuutujaline krüptograafia - kasutades näiteid NIST standardiseerimisprogrammist. Lõputöö eesmärk on koostada ülevaatlik materjal, mis annaks informaatika või matemaatika taustaga tudengile laiahaardelised algteadmised postkvantkrüptograafia valdkonnast.

•Jan 1, 2019•0 citations
Teadlased ja insenerid on juba mõnda aega püüdnud ehitada kvantseadustel põhinevat arvutit. See uus masin (kvantarvuti) on võimeline lahendama arvutuslikult keerulisi ülesandeid, nagu näiteks täisarvude tegurdamine, palju kiiremini kui ükski klassikaline arvuti. Tegurdamisel tuleb täisarv esitada väiksemate täisarvude korrutisena. Näiteks arvu 15 tegurdamiseks tuleb see esitada korrutisena 3 x 5. Suure arvu tegurdamine klassikalisel arvutil võtab väga kaua aega, samas kui kvantarvuti suudab selle ülesande raskusteta oluliselt kiiremini lahendada. Suure ajalise keerukusega probleemide kiire lahendamine on küll põnev saavutus, kuid paraku põhinevad praegu laialdases kasutuses olevad krüpteerimisalgoritmid, nagu näiteks RSA, just tegurdamise keerukusel. Keegi ei saa meie krüpteeritud andmeid dekrüpteerida, kui tal puudub võimekus kiiresti tegurdada. RSA algoritmi kasutamine krüptosüsteemides on väga levinud. Näiteks Eesti ID-kaart kasutab RSA algoritmi digitaalseks allkirjastamiseks ja ka muude teenuste jaoks. Kuna kvantarvuti suudab aga kiiresti tegurdada, ei ole RSA algoritm suurte kvantarvutite vastu turvaline. Postkvant-krüptograafia on uus valdkond, mis tegeleb just selliste probleemidega. Eesmärgiks on konstrueerida krüpteerimisalgoritm, mis on turvaline isegi kvantründajate vastu. Esimeseks sammuks on leida matemaatiline probleem, mis on keeruline ka kvantarvutite jaoks. Seejärel on võimalik konstrueerida krüptograafilisi algoritme, mis põhinevad neil probleemidel. Lõpuks tuleb tõestada, et meie krüptograafiline skeem on turvaline. Selles väitekirjas keskendume eelnimedatud sammudest just viimasele. Me verifitseerime osade krüptosüsteemide turvalisuse kvantründajate suhtes ja tõestame, et osad krüptograafilised konstruktsioonid on kvantturvalised.
Turvaline ühisarvutus on tänapäevase krüptograafia üks tähtsamaid kasutusviise, mis koondab elegantsed matemaatilised lahendused praktiliste rakenduste ehitamiseks, võimaldades mitmel erineval andmeomanikul sooritada oma andmetega suvalisi ühiseid arvutusi, ilma neid andmeid üksteisele avaldamata. \nPassiivse ründaja vastu turvalised protokollid eeldavad, et kõik osapooled käituvad ausalt. Aktiivse ründaja vastu turvalised protokollid ei lekita privaatseid andmeid sõltumata ründaja käitumisest. Käesolevas töös esitatakse üldine meetod, mis teisendab passiivse ründaja vastu turvalised ühisarvutusprotokollid turvaliseks aktiivse ründaja vastu. Meetod on optimeeritud kolme osapoolega arvutusteks üle algebraliste ringide; praktikas on see väga efektiivne mudel, mis teeb reaalse maailma rakendused teostatavateks. Meetod lisab esialgsele arvutusprotokollile täitmisjärgse verifitseerimisfaasi, mis muudab valesti käitunud osapooltel vahelejäämise vältimise tõenäosuse kaduvväikseks, säilitades esialgse protokolli turvagarantiid. \nLisaks uurib käesolev töö rünnete uut eesmärki, mis seisneb mingi ausa osapoole vaate manipuleerimises sellisel viisil, et ta saaks midagi teada teise ausa osapoole privaatsete andmete kohta. Ründaja ise ei tarvitse seda infot üldse teada saada. Sellised ründed on olulised, sest need kohustavad ausat osapoolt tühjendama oma süsteemi teiste osapoolte andmetest, kuid see ülesanne võib olla päris mittetriviaalne. Eelnevalt pakutud verifitseerimismehhanisme täiendatakse nii, et privaatsed andmed oleksid kaitstud ka ausate osapoolte eest. \nPaljud ühisarvutusplatvormid on varustatud programmeerimiskeelega, mis võimaldab kirjutada privaatsust säilitavaid rakendusi ilma allolevale krüptograafiale mõtlemata. Juhul, kui programm sisaldab tingimuslauseid, kus arvutusharu valik sõltub privaatsetest andmetest, ei tohi ükski osapool haru valikust midagi teada, nii et üldjuhul peavad osapooled täitma kõik harud. Harude suure arvu kor-ral võib arvutuslik lisakulu olla ülisuur, sest enamik vahetulemustest visatakse ära. Käesolevas töös pakutakse selliseid lisakulusid vähendavat optimeerimist.
Anotācija\nKvantu skaitļošana ir datorzinātnes apakšnozare, kas balstās uz kvantu mehānikas likumiem.\nKvantu vaicājošais algoritms ir galvenais pētāmais objekts. Galvenais darba mērķis ir padarīt\nkvantu algoritma konstruēšanu pēc iespējas vienkāršāku.\nPētījumā ir aprakstīti kvantu vaicājošie algoritmi, kas rēķina Būla funkcijas uzdodot nelielu\nskaitu vaicājumu, un tiek piedāvāti kvantu vaicājošie algoritmi daudzvērtīgu funkciju\naprēķināšanai. Darbā ir aprakstīti vairāki efektīvi kvantu algoritmi konkrētu uzdevumu veikšanai.\nPaši nozīmīgākie ir kvantu vaicājošie algoritmi ar ierobežotu kļūdu, piemēram, piedāvāts algoritms\ndivu bitu AND Būla funkcijai, kas izmanto vienu vienīgu vaicājumu un izsniedz pareizu atbildi ar\nvarbūtību 9/10. Katrai aprakstītajai funkciju kopai ir veikta pamatīga kvantu un klasiskās\nsarežģītības analīze.\nPēdējā pētījuma daļa ir veltīta Būla funkcijām ar zemas pakāpes polinomiem, kuri\nreprezentē dotās funkcijas. Darbā piedāvātie paņēmieni ļauj uzkonstruēt Būla funkcijas ar\npietiekami lielu intervālu starp funkcijas determinēto sarežģītību un reprezentējošā polinoma\npakāpi.\nAtslēgas vārdi: kvantu skaitļošana, vaicājošais modelis, vaicājošais algoritms, daudzvērtīga\nfunkcija, zemas pakāpes Būla funkcija
Kvantu algoritmu veiktspējas pārākums par klasiskajiem algoritmiem ir galvenais iemesls pašreizējai lielai ieinteresētībai par kvantu skaitļošanu. Vieni no slavenākiem kvantu algoritmiem ir Grovera meklēšanas algoritms un šora skaitļu faktorizācijas algoritms. Piemēram, Grovera algoritms atrisina elementa meklēšanas problēmu N elementu sarakstā ar laiku Ø(pN), kaut klasiskam algoritmam ir nepieciešams ¬(N) laiks, lai atrisinātu šo problēmu. Tātad mēs esam ļoti ieinteresēti atrast šādas problēmas, kurām kvantu algoritms var būt pārāks par klasisko analogu. Kvantu skaitļošanas centrālais jautājums ir, cik spēcīgi ir kvantu algoritmi? Cik liels veiktspējas uzlabo jums ir iespējams? Šajā darbā mēs sniedzam dažus jautājumus uz šīm jautājumiem. Mēs aplūkojam divas lielas problēmas. Pirmkārt, mēs aplūkojam cikla eksistences grafā problēmu. Mēs piedāvājam kvantu vaicājošo algo ritmu, kas atrisina šo problēmu efektīvāk par jebkuru klasisko analogu, un pierādām, ka mūsu piedāvātais algoritms ir optimāls. Otrkārt mēs turpinām pētījumus par varbūtiskiem apgriežamiem automātiem, izpētot apstādināmo varbūtisko apgriežamo automātu (DH-PRA) īpašības. Mēs parādām vispārējo valodu klasi, ko nevar pazīt ar DH-PRA, un kas ir ļoti līdzīga valodu klasei, ko nevar pazīt ar daudzmērījumu kvantu automātiem (MM-QFA). Mēs arī parādām, ka valodu klase, kuru pazīst DH-PRA nav slēgta pret apvienojuma operāciju. Tas ļauj mums izteikt minējumu, ka valodu klase, ko pazīst DH-PRA automāti iekļauj valodu klasi, ko pazīst MM- QFA vai nu šīs klases ir ekvivalentas. Mēs turpinām strādāt pie šī minējuma pierādīšanas.
Tämän insinöörityön keskeinen tutkimuskysymys on, miten kvanttitietokoneiden kehitys vaikuttaa nykyisiin salausmenetelmiin ja millä tavoin post-kvanttinen kryptografia vastaa näihin uhkiin. Lisäksi työ tarkastelee post-kvanttisten ratkaisujen käyttöönottoon liittyviä teknisiä ja organisatorisia haasteita. Tutkimuskysymykseen vastaamiseksi työssä tarkastellaan kvanttilaskennan keskeisiä periaatteita, kuten superpositiota, lomittumista ja interferenssiä, jotka mahdollistavat laskentatehon, johon klassiset tietokoneet eivät kykene. Näiden ilmiöiden hyödyntäminen tekee kvanttitietokoneista erityisen tehokkaita ratkaisemaan matemaattisia ongelmia, jotka muodostavat nykyisten epäsymmetristen salausmenetelmien, kuten RSA:n ja ECC:n, turvallisuuden perustan. Työssä analysoitiin modernien salausalgoritmien toimintaa ja kvanttiuhkia, jotka kohdistuvat erityisesti julkisen avaimen menetelmiin. Symmetristen algoritmien, kuten AES:n, todettiin säilyttävän turvallisuutensa kvanttiuhkia vastaan avainpituuksia kasvattamalla, kun taas epäsymmetriset menetelmät ovat haavoittuvaisia Shorin algoritmille. Lisäksi työssä esiteltiin NIST:n standardoimat post-kvanttiset algoritmit, kuten Kyber ja Dilithium, sekä niiden keskeiset ominaisuudet ja käyttöönottoon liittyvät haasteet. Työn johtopäätökset osoittavat, että siirtyminen post-kvanttiseen kryptografiaan on välttämätöntä tulevien vuosien aikana. Kvanttiuhkien aikataulu on epävarma, ja erityisesti Harvest Now, Decrypt Later -skenaario korostaa tarvetta aloittaa valmistelut ajoissa. Työ tarjoaa kokonaiskuvan kvanttiajan tietoturvahaasteista ja toimii lähtökohtana organisaatioille, jotka suunnittelevat kvanttiturvallisten järjestelmien käyttöönottoa.
Kuantum bilgisayarların keşfi ile klasik kriptografi olarak adlandırdığımız ve günümüzde tüm kriptografik cihazlarda kullanılan kriptosistemlerin güvenliği tartışılır hale gelmiştir. Kuantum bilgisayarlardaki hızlı gelişme sonucunda kriptografideki çalışma alanı kuantum bilgisayarlara karşı güvenli sistemlerin tasarlanması ve analiz edilmesi yönünde değişmiştir. Shor Algoritması ile çarpanlara ayırma probleminin çözümünün üstel zamandan polinom zamana indirilmesiyle özellikle asimetrik kriptosistemler tehdit altına girmiştir. Günümüzde verilerin büyük çoğunluğu klasik kriptografide kullanılan anahtar anlaşma algoritmaları ile paylaşılan anahtar kullanılarak simetrik şifreleme algoritmaları ile şifreli olarak saklanmaktadır. Kuantum kriptografinin esas etkisi asimetrik kriptografiye olmasına rağmen simetrik şifreleme algoritmalarının anahtarları asimetrik kriptografi ile paylaşıldığı için tüm veriler kuantum tehtidinden etkilenmektedir. Özellikle şifrelenen verilerin geriye dönük olarak tutulabileceği göz önünde bulundurulursa ve yakın zamanda kuantum bilgisayların çarpanlara ayırma problemini etkili bir şekilde çözecek seviyeye gelmesi durumunda şu andan itibaren simetrik şifreleme algoritmaları ile şifrelenen veriler de ileride çözülebilecektir. İmza algoritmalarının etkilenmesi ise imzanın kimlik doğrulama mekanizmaları veya mesajın kaynağını doğrulamak gibi o ana ait bir kriptografik hizmeti sağladığı için daha kısıtlı olacaktır. Bu yüzden kuantum tehtidi için anahtar paylaşma probleminin çözümü imza probleminin çözümüne nazaran daha acil bir ihtiyaç olarak görülmektedir. Bu sebeplerle bu çalışmada kuantum sonrası kriptografinin anahtar paylaşma problemine getirdiği çözümler üzerinde durulacaktır. Burada bahsedilen her iki problem için de daha önceden AES'i blok şifreleme algoritması olarak bir yarışma aracılığıyla standartlaştıran NIST (Ulusal Standartlar ve Teknoloji Enstitüsü), standart bir algoritma seçmek için 2016 yılında bir yarışma başlatarak standart bir kuantum sonrası anahtar değişim algoritması ve imza algoritması seçme kararı almıştır. Bu süreçten sonra algoritma tasarımı ve analizi üzerine çalışmalar hızlanmıştır. Yarışmaya katılan algoritmalar dayandıkları zorluklara göre farklı gruplara ayrılabilir. Bunlar kafes tabanlı kriptosistemler, kod tabanlı kriptosistemler, isojeni tabanlı kriptosistemler, özet tabanlı kriptosistemler ve çok değişkenli polinom tabanlı kriptosistemlerdir. Bunların içinden en çok dikkat çeken ve üzerine çalışan homomorfik şifreleme gibi yapılarda da kullanılabilmesi itibariyle kafes tabanlı kriptosistemlerdir. Ayrıca yarışma neticesinde standart olarak seçilen Kyber Algoritması da kafes tabanlı bir anahtar değişim algoritmasıdır. Kod tabanlı kriptosistemler McEliece tarafından ortaya atılılmıştır ve asimetrik kriptografinin en eski problemlerinden biri olan kod çözme problemine dayanmaktadır. Anahtar boyutlarının büyük olması dezavantajından dolayı, kuantum tehditi ortaya çıkana kadar, görece az çalışılan bir alan olarak kalmıştır. Niederreiter kriptosisteminin ortaya çıkması ve anahtar boyutlarında iyileştirmeler yapılması ile kuantum sonrası anahtar değiştirme algoritmaları için önemli bir aday durumuna gelmişlerdir. Izojeni tabanlı algoritmalar klasik bilgisayarlarla kırılabilen bir saldırının ortaya çıkmasıyla riskli duruma düşmüştür. Her ne kadar NIST SIKE anahtar anlaşma algoritmasını alternatif algoritma adaylarına alsa da saldırı bu tarihten sonra ortaya çıktığı için kullanılması önerilmez ibaresi eklemiştir. Ayrıca bazı kriptosistemlerin analizi için üzerine yeterince çalışılmadığı düşünüldüğü için kuantum sonrası anahtar anlaşma algoritmalarının tek başına kullanılmasına şüpheyle bakılmaya başlanmıştır. Bu sebeple anahtar paylaşım problemini çözmek için kuantum sonrası algoritmalar, asimetrik kriptografi ve daha önce paylaşılmış ortak simetrik anahtarlardan en az iki tanesini kullanan hibrit anahtar paylaşım protokolleri de önerilmiştir. Bu çalışma kapsamında anahtar anlaşma problemini çözmek için geliştirilen önerilerden kabaca bahsedilecektir. Kafes tabanlı kriptosistemler ile Kod tabanlı kriptosistemlerin dayandıkları problemler ve bu problemler üzerine anahtar değişim mekanizmalarının nasıl kurulduğu anlatılacaktır. Ayrıca bazı analiz metotları anlatılarak standartta bulunan bazı algoritmaların güvenlik seviyeleri ve analizi hakkında bilgi verilecektir.
Tänapäeval on andmeturve paljudes valdkondades määrava tähtsusega, kuid hiljutised edusammud kvantmehhaanika valdkonnas võivad tänased interneti turvaprotokollid ohtu seada. Kuna kvantvutid on tõenäoliselt võimelised murdma meie praeguseid krüptostandardeid, tekib vajadus tugevamate krüpteerimisalgoritmide järele. Viimaste kümnendite jooksul on postkvantkrüptograafia saanud palju tähelepanu, kuid siiani pole ükski postkvantkrüptograafiline algoritm standardiseeritud ulatuslikuks kasutamiseks. Seetõttu algatati NIST programm, mille eesmärk on valida uued krüptostandardid, mis säilitaks oma turvalisuse ka kvantarvutite vastu. Käesolev lõputöö annab ülevaate postkvantkrüptograafia erinevatest valdkondadest - võrepõhine, koodipõhine, räsipõhine ja mitmemuutujaline krüptograafia - kasutades näiteid NIST standardiseerimisprogrammist. Lõputöö eesmärk on koostada ülevaatlik materjal, mis annaks informaatika või matemaatika taustaga tudengile laiahaardelised algteadmised postkvantkrüptograafia valdkonnast.