i
i
“Marc” — 2020/11/10 — 11:31 — page 81 — #1 i
i
i
i
i
i
PROBLEM UČENJA Z NAPAKAMI IN SODOBNI
KRIPTOSISTEMI
TILEN MARC
Fakulteta za matematiko in fiziko
Univerza v Ljubljani
Math. Subj. Class. (2020): 94A60, 68P25, 81P94
Sodobni kriptosistemi so osnovani na matematičnih problemih in njihova varnost je
zagotovljena samo, dokler ne obstajajo algoritmi, ki bi te probleme učinkovito rešili. V
članku predstavimo nedavno vpeljan algoritmičen problem učenja z napakami, ki se izkaže
za izjemno uporabnega v kriptografiji, saj omogoča sestavo novih kriptosistemov z zanimi-
vimi in uporabnimi lastnostmi. Taki kriptosistemi veljajo tudi za varne pred nasprotniki,
ki imajo dostop do kvantnega računalnika, kar za večino drugih ne velja. Predstavljena
sta kvantno varen kriptosistem z javnim ključem in kriptosistem, ki omogoča računanje
na šifriranih podatkih, kar je znano pod imenom homomorfno šifriranje. Konstrukcija
slednjega je bila odprt problem več desetletij in dosežena šele s pomočjo problema učenja
z napakami.
PROBLEM OF LEARNING WITH ERRORS AND MODERN CRYPTOSYSTEMS
Modern cryptosystems are based on mathematical problems and their security is gu-
aranteed only as long as there are no efficient algorithms solving these problems. We
present a recently introduced algorithmic problem of learning with errors (LWE). The
problem is crafted for the use in cryptography and allows to construct new cryptosy-
stems with interesting and useful properties. Such cryptosystems are considered safe even
against adversaries with access to quantum computers, which does not hold for most of
the other systems. We explain how to construct two cryptosystems: a quantumly secure
cryptographic scheme with public key, and a scheme that enables computation on encryp-
ted data, known as homomorphic encryption. The construction of the latter was a long
standing open problem and was solved only recently with the help of LWE problem.
Uvod
Problem učenja z napakami (ang. learning with errors – LWE ) je vpeljal
Regev v [4] kot nov algoritmičen problem in dokazal, da je vsaj tako težek
kot nekateri drugi znani problemi. Članek je povzročil pravo revolucijo,
saj je bilo v zadnjem desetletju napisanih na tisoče znanstvenih člankov,
ki temeljijo na problemu LWE. Regev je bil leta 2018 za svoj prispevek
nagrajen s prestižno Gödelovo nagrado, ki jo vsako leto podelijo za doprinos
k teoretičnemu računalnǐstvu.
Glavni razlog za priljubljenost problema LWE je njegova uporabnost v
kriptografiji. Eden izmed osnovnih temeljev sodobne kriptografije je t. i.
asimetrična kriptografija. Ta omogoča, da uporabnik izračuna svoj javni
Obzornik mat. fiz. 67 (2020) 3 81
i
i
“Marc” — 2020/11/10 — 11:31 — page 82 — #2 i
i
i
i
i
i
Tilen Marc
ključ, s pomočjo katerega mu lahko vsakdo pošlje šifrirano sporočilo, ki
ga lahko dešifrira le lastnik javnega ključa s pomočjo svojega skrivnega
ključa. Taki kriptosistemi se dandanes uporabljajo v računalnǐski komuni-
kaciji, bančnǐstvu in praktično na vseh področjih, kjer je tajnost podatkov
pomembna. Varnost asimetrične kriptografije temelji na predpostavki, da
iz javnega ključa ne moremo izračunati skrivnega, saj bi v nasprotnem pri-
meru lahko vsak dešifriral sporočila. Zato so kriptosistemi z javnim ključem
osnovani na matematičnih problemih, za katere ne poznamo učinkovitih al-
goritmov za reševanje.
V praksi daleč najbolj uporabljana matematična problema sta t. i. pro-
blem razcepa naravnega števila in z njim povezan problem diskretnega lo-
garitma. Problema, ki ju lahko uvrstimo na področje teorije števil, sta omo-
gočila slavne kriptografske sheme, kot so RSA, ElGamalov sistem in DSA,
pa tudi sodobneǰse konstrukte, ki temeljijo na eliptičnih krivuljah. Najve-
čjo grožnjo vsem omenjenim tehnologijam predstavlja razvoj t. i. kvantnega
računalnika in kvantnih algoritmov. Glavni razlog je, da je Shor že leta
1999 v [6] opisal kvantni algoritem, ki zmore v polinomskem času razbiti
naravno število in poiskati diskretni logaritem. Torej obstaja algoritem, s
katerim lahko s pomočjo kvantnega računalnika razbijemo skoraj vsak dan-
danes uporabljan kriptosistem z javnim ključem, vdremo v bančne račune
itd. V trenutku pisanja članka kvantni računalniki že obstajajo, vendar je
njihova zmogljivost še zelo omejena. Ali se bo to v prihodnje spremenilo,
lahko samo ugibamo.
Problem LWE ne temelji na zgoraj omenjenih problemih in je zaenkrat
varen pred kvantnimi računalniki, saj (trenutno) ne poznamo kvantnega
algoritma, ki bi ga v polinomskem času uspel rešiti. Še več – kot bomo
videli, je Regev dokazal, da je problem LWE vsaj tako težek kot nekateri
problemi na t. i. rešetkah. Ti so poznani že dlje časa in veljajo za težke,
zato je zaupanje v neobstoj polinomskih (kvantnih) algoritmov za reševanje
problema LWE še večje.
V članku bomo predstavili enega izmed načinov, kako je mogoče sesta-
viti kriptosistem z javnim ključem, katerega varnost temelji na težavnosti
problema LWE. Tak kriptosistem torej velja za kvantno varnega, razvoj
tovrstnih kriptosistemov pa je ena izmed najpomembneǰsih tem sodobne
kriptografije. To dokazuje tudi dejstvo, da v času pisanja članka poteka
pomemben izbor amerǐskega Nacionalnega inštituta za standarde in tehno-
logijo (NIST) [7] za določitev kvantnih kriptografskih standardov, ki se bodo
uporabljali v bližnji prihodnosti. Večina shem, ki so se uvrstile v ožji izbor,
temelji na problemu LWE ali njegovih izpeljankah.
Problem LWE poleg kvante varnosti kriptosistemov z javnim ključem
prinaša tudi druge novosti. Tako lahko sestavimo nove kriptosisteme, kate-
rih varnost temelji na težavnosti problema LWE, z lastnostmi, ki jih stareǰsi
82 Obzornik mat. fiz. 67 (2020) 3
i
i
“Marc” — 2020/11/10 — 11:31 — page 83 — #3 i
i
i
i
i
i
Problem učenja z napakami in sodobni kriptosistemi
kriptosistemi ne omogočajo. Področje simetrične kriptografije omogoča ši-
friranje podatkov s pomočjo skrivnega ključa, tako da jih lahko dešifriramo
samo ob poznavanju le-tega. Taki sistemi se uporabljajo za hitro prenašanje
sporočil med uporabniki, ki so si izmenjali skrivni ključ, pa tudi za varno
hrambo podatkov. V sodobnem svetu veliko podatkov hranimo v oblaku,
in če želimo ohraniti osebne podatke varne, morajo biti taki podatki šifri-
rani. Poleg hrambe ponudniki omogočajo tudi urejanje, analizo, napovedi,
priporočila in druge storitve, ki temeljijo na računanju s podatki. A če so
podatki šifrirani, take storitve niso mogoče, saj ponudnik storitev v oblaku
podatkov ne pozna. Želeli bi torej na videz nemogoče – računanje (in s tem
vse storitve, ki smo jih vajeni) brez poznavanja podatkov. Čeprav opisano
zveni kot sodobni problem, je bil izziv sestaviti kriptosistem, ki bi omogočal
računanje s šifriranimi podatki, brez poznavanja le-teh, predlagan že leta
1978 v [5]. Tak kriptosistem imenujemo homomorfno šifriranje. Problem je
bil dolgo časa odprt, dokler ni prvi tak sistem opisal Gentry v [3]. Obja-
vljen kriptosistem je bil osnovan na problemu LWE in od njegove objave je
bilo predlaganih več različic in izbolǰsav. Eno izmed teh bomo predstavili v
članku.
Preostanek članka je strukturiran na naslednji način: v razdelkih Pro-
blem LWE in Težavnost problema LWE definiramo problem LWE in poka-
žemo, zakaj je to težek problem, v razdelku Kriptosistem z javnim ključem,
osnovan na problemu LWE predstavimo kriptosistem z javnim ključem, ki
temelji na problemu LWE, in ga nato v razdelku Homomorfno šifriranje
nadgradimo v kriptosistem za homomorfno šifriranje. Da lahko to storimo,
konstruiramo t. i. generator psevdonaključnih vektorjev s stranskimi vrati
in razložimo, kako uporabiti dvojǐsko kodiranje pri konstrukciji.
Problem LWE
Začnimo s preprostim matematičnim problemom reševanja linearnih enačb.
Naj bo p praštevilo in z Zp označimo polje s p elementi. Torej, elementi
Zp so števila {0, 1, . . . , p− 1}, operaciji seštevanja in množenja pa izvajamo
po modulu p. Naj bo A ∈ Zm×np poljubna matrika in b ∈ Zmp vektor za
m ≥ n ≥ 1. Problem iskanja x ∈ Znp v matrični enačbi nad Zp
Ax = b
ni težek, saj ga lahko rešimo z Gaussovo eliminacijo, četudi je p velik.
Otežimo zgornji problem z dodajanjem napake. Za vrednost y ∈ Zp
označimo |y| = min(y, p− y) in recimo, da je vrednost y ∈ Zp majhna, če je
vrednost |y| = min(y, p− y) občutno manǰsa od p: za vse uporabe v članku
lahko bralec predpostavi, da je |y| manǰsi od √p. Naj bo e ∈ Zmp vektor
z majhnimi vrednostmi, torej je vrednost vsake komponente v e občutno
81–97 83
i
i
“Marc” — 2020/11/10 — 11:31 — page 84 — #4 i
i
i
i
i
i
Tilen Marc
manǰsa od p. Naj bosta A ∈ Zm×np in b ∈ Zmp dana kot prej. Iskanje
vrednosti x, da velja
Ax+ e = b,
kjer je e neznan, je osnova problema učenja z napakami (LWE).
Oglejmo si zgornji problem nekoliko natančneje. Na prvi pogled je pro-
blem enostavneǰsi, saj imamo m linearnih enačb in m+n neznank – neznana
sta tako x kot e. V primeru, da je m = n, lahko izberemo e = 0 in rešimo
Ax = b, kot v zgornjem primeru z Gaussovo eliminacijo. Problem postane
težji, če je m večji kot n, saj nismo zadovoljni z vsako rešitvijo, ampak
samo s tistimi, v katerih je e majhen. Reševanje problema s standardnimi
metodami linearne algebre nam ne zagotavlja take rešitve. Na problem
lahko pogledamo tudi drugače: podprostor vseh vektorjev {Ay | y ∈ Znp}
je največ n-dimenzionalni podprostor m-dimenzionalnega prostora Zmp . Če
želimo najti x, da velja Ax+ e = b, potem moramo najti tak majhen e, da
je b− e ∈ {Ay | y ∈ Znp}.
Definirajmo sedaj iskalni problem LWE natančneje. Da bo problem
uporaben v kriptografiji, mora biti take narave, da lahko enostavno generi-
ramo naključne vrednosti (recimo nove skrite in javne ključe), za katere je
problem težek. Zato problem definiramo za naključne vrednosti, izbrane iz
vnaprej določenih porazdelitev. Torej problema LWE ne bomo definirali za
poljubne vrednosti A, x, e, b, ampak za naključne, kar je precej drugače od
mnogih drugih algoritmičnih problemov, ki jih rešujemo za poljubne vho-
dne podatke. Razlog za tako definicijo je, da je marsikateri (tudi NP-poln)
problem težek, če so vhodni podatki poljubni, vendar lahek za naključne.
Označimo s χ porazdelitev naključnih majhnih vektorjev, izbranih iz
Zp (v naslednjem razdelku bomo natančneje definirali, kako izbrati χ). Za
vrednost (vektor, matriko itd.) x bomo rekli, da je izbrana enakomerno
naključno, če so verjetnosti izbire vseh mogočih vrednosti enake.
Definicija 1. Naj bo p praštevilo, m ≥ n ≥ 1, A ∈ Zm×np enakomerno
naključno izbrana matrika, x ∈ Znp enakomerno naključno izbran vektor in
e ∈ Znp vektor, naključno izbran iz porazdelitve χ. Definirajmo b ∈ Zmp kot
b := Ax + e. Iskalni problem LWEn,m,p,χ je problem najti x, če poznamo
samo A in b.
Pozoren bralec bi lahko opazil, da ima sistem b = Ax+e lahko več rešitev.
Spomnimo se – najti moramo tak majhen e, da je b−e ∈ {Ay | y ∈ Znp}. Če
določimo parametre tako, da je m občutno večji od n, je po številu elementov
prostor {Ay | y ∈ Znp} občutno manǰsi od celega prostora. Intuicija nam
zato pravi, da je verjetnost (za naključno izbrane A, x, e), da ima enačba
več kot eno rešitev, majhna. Kot bomo videli, je za kriptografsko uporabo
pomembno le, da je problem tako težek, da ne moremo najti nobene rešitve
x, e, kjer je e majhen.
84 Obzornik mat. fiz. 67 (2020) 3
i
i
“Marc” — 2020/11/10 — 11:31 — page 85 — #5 i
i
i
i
i
i
Problem učenja z napakami in sodobni kriptosistemi
Težavnost problema LWE
V tem razdelku bomo definirali odločitveno verzijo problema LWE, natanč-
neje določili porazdelitev χ, ki se uporablja za izbiro vektorja e, in predstavili
pomemben rezultat glede težavnosti problema LWE.
Odločitveni problem LWE
Izkaže se, da je za kriptografsko uporabo prikladno, da definiramo odloči-
tveno verzijo problema LWE.
Definicija 2. Odločitveni problem je problem, ki ima le dve možni rešitvi: 0
ali 1.
Torej, če želimo rešiti odločitveni problem, želimo izpeljati algoritem, ki za
vhodne podatke vrne odgovor 0 ali 1. V primeru odločitvenega problema
LWE je naloga razlikovati med vrednostmi, izbranimi iz dveh različnih po-
razdelitev.
Definicija 3. Naj bo p praštevilo, m ≥ n ≥ 1, A ∈ Zm×np enakomerno
naključno izbrana matrika, x ∈ Znp enakomerno naključno izbran vektor in
e ∈ Zmp vektor, naključno izbran iz porazdelitve χ. Naj bo b ∈ Zmp definiran
kot b := Ax + e in c ∈ Zmp izbran iz enakomerne porazdelitve. Odločitveni
problem LWEn,m,p,χ je problem, katerega vhod je ena izmed vrednosti (A, b)
ali (A, c), algoritem pa mora določiti, katera izmed vrednosti je bila vhod.
Torej, algoritem prejme vrednost (A, z) in mora določiti, ali je vektor z
vektor vrednosti enakomerne porazdelitve ali je z dobljen iz porazdelitve
enačbe LWE.
Za razliko od iskalnega problema tukaj naloga ni, da dobimo (A, z) in
poǐsčemo x, e, da velja Ax + e = z, ampak da lahko razločimo, ali je bil
z naključno izbran prek izbire A, x, e, ali je preprosto vektor enakomerno
naključnih vrednosti. Ti dve porazdelitvi seveda nista enaki; recimo, vektor
z, izbran iz prve porazdelitve, je vedno tak, da obstaja rešitev enačbe Ax+
e = z, kjer je e majhen, medtem ko za enakomerno naključen vektor z
rešitev morda (in tudi zelo verjetno) ne obstaja. Izkaže se, da sta iskalni
in odločitveni problem podobne težavnosti, saj lahko prevedemo enega na
drugega [4]. Za uporabo v kriptografiji bi želeli, da je odločitveni problem
LWE (in zato tudi iskalni) težek, torej da algoritem, ki bi deloval dovolj
hitro in rešil problem pravilno v več primerih kot napačno, ne obstaja.
Definirajmo matematično, kaj pravzaprav mislimo, ko rečemo, da je od-
ločitveni problem LWEn,m,p,χ težek. Označimo z Pr(X) verjetnost dogodka
X. Za algoritem A, ki rešuje odločitveni problem LWE, označimo z A(A, z)
vrednost, ki jo vrne A ob vhodu (A, z).
81–97 85
i
i
“Marc” — 2020/11/10 — 11:31 — page 86 — #6 i
i
i
i
i
i
Tilen Marc
Definicija 4. Naj bo n > 0 parameter in naj bo m ≥ n, p praštevilo in
χ porazdelitev, ki so lahko določeni v odvisnosti od n. Naj bosta (A, b)
in (A, c) para, kjer je b ∈ Zmp definiran kot b := Ax + e ∈ Zmp in c ∈ Zmp
enakomerno naključen, torej sta (A, b) in (A, c) generirana kot možna vhoda
odločitvenega problema LWEn,m,p,χ. Predpostavka LWE pravi, da za vsak
polinomski algoritem A, ki vrača 0 ali 1, velja
|Pr(A(A, b) = 1)− Pr(A(A, c) = 1)| < 2−Cn
za neko konstanto C > 0.
Predpostavka LWE pravi, da ne obstaja algoritem, ki bi mu v polinom-
skem času uspelo razlikovati (torej vrniti 0 ali 1) med naključnima vhodoma
odločitvenega problema LWEn,m,p,χ bolje kot z eksponentno majhno verje-
tnostjo. Intuitivno to v neformalnem jeziku pomeni, da če predpostavka
LWE drži in izračunamo b = Ax+ e z naključno izbranimi A, x, e, potem se
b zdi kot enakomerno naključen vektor. Če predpostavka LWE drži, potem
bomo rekli, da je b = Ax+ e računsko neločljiv od enakomerno naključnega
vektorja.
Definicija vsebuje verjetnosti, da algoritem vrne pravilno ali napačno
odločitev, saj je problem definiran na naključnih podatkih in bi lahko na-
ključno sprejemal odločitve. Da bi bolje razumeli definicijo, si oglejmo pre-
več preprost algoritem za reševanje odločitvenega problema LWE. Recimo,
da algoritem B problem reši tako, da preprosto vrže kovanec in izbere 0 ali
1. Seveda tak algoritem ne bi bil preveč uporaben. Oglejmo si vrednost:
|Pr(B(A, b) = 1)− Pr(B(A, c) = 1)| =
∣∣∣∣12 − 12
∣∣∣∣ = 0.
Slednje lahko razumemo tako, da tak algoritem ne bi uspel razlikovati pra-
vilne odločitve od napačne. Če predpostavka LWE drži, potem vsak algo-
ritem, ki bi deloval v polinomskem času, ne bi deloval veliko bolje, kot da
vržemo kovanec.
V nadaljevanju razdelka bomo razložili, za kakšne parametre n,m, p, χ
se verjame, da predpostavka LWE drži.
Diskretna Gaussova porazdelitev
Do sedaj smo vprašanje, kako izbrati m, p, χ, da bo predpostavka LWE
smiselna, pustili odprto. V tem podrazdelku bomo opisali, kako izbrati
porazdelitev χ, s katero izberemo vektor e v Ax+ e.
Definicija 5. Diskretna Gaussova porazdelitev Dσ, ki ima vrednosti v Z, je
taka porazdelitev, da je za vsak x ∈ Z verjetnost izbire x enaka Ce−
x2
2σ2 ,
86 Obzornik mat. fiz. 67 (2020) 3
i
i
“Marc” — 2020/11/10 — 11:31 — page 87 — #7 i
i
i
i
i
i
Problem učenja z napakami in sodobni kriptosistemi
kjer je σ > 0 in C taka konstanta, da se verjetnosti vseh dogodkov seštejejo
v 1.
Z D̄σ označimo diskretno Gaussovo porazdelitev, ki ima vrednosti v
Zp, ki jih dobimo tako, da izberemo y ∈ Z iz Dσ in izračunamo ȳ = (y
mod p) ∈ Zp.
Verjetnost izbire vrednosti iz Dσ, katerih absolutna vrednost je večja od
σ, eksponentno hitro pada. Če je σ občutno manǰsi kot praštevilo p, bodo
tudi absolutne vrednosti števil, generiranih z Dσ, z zelo veliko verjetnostjo
občutno manǰse od p. To pomeni, da bodo vrednosti y, generirane z D̄σ,
majhne. Torej, vrednost min(y, p − y) bo občutno manǰsa od p. Take
vrednosti želimo v problemu LWE.
Problemi na rešetkah
V tem podrazdelku bomo odgovorili, kako izbrati preostale parametre pro-
blema LWEn,m,p,χ s pomočjo v uvodu omenjenega rezultata Regeva [4]. Naj-
prej potrebujemo dve definiciji:
Definicija 6. Naj bodo v1, . . . , vn linearno neodvisni vektorji v Rn. Množico
L(v1, . . . , vn) = {a1v1 + · · ·+ anvn | ai ∈ Z za 1 ≤ i ≤ n}
imenujemo rešetka.
Spomnimo se, da je 2-norma vektorja x definirana kot ||x|| =√
x21 + · · ·+ x2n, kjer so x1, . . . , xn koordinate x. Recimo, da imamo podane
vektorje v1, . . . , vn, ki imajo vsi 2-normo večjo od nekega a ∈ R. S sestavlja-
njem linearnih kombinacij a1v1 + · · ·+anvn, z ai ∈ Z za vsak 1 ≤ i ≤ n, je v
določenih primerih možno sestaviti neničelen vektor, ki ima normo manǰso
od a. Kot preprost primer navedimo v1 = (100, 99), v2 = (100, 100), kjer
ima −v1 + v2 = (0, 1) manǰso normo od začetnih vektorjev.
Če za dane v1, . . . , vn lahko najdemo koeficiente ai ∈ Z, da je a1v1+· · ·+
anvn neničeln vektor z majhno normo, potem velja, da v rešetki L(v1, . . . , vn)
obstaja element z majhno normo. To, kako učinkovito najti take koeficiente
oziroma se odločiti, ali sploh obstajajo, je pomemben algoritmičen problem.
Definicija 7. Odločitveni problem GapSVP(n, s), kjer je n ∈ N in s ≥ 1, je
problem, katerega vhod so poljubni neodvisni vektorji v1, . . . , vn, ki
definirajo rešetko L(v1, . . . , vn), in pravilni izhod je vrednost 1, če
obstaja v ∈ L(v1, . . . , vn)\{(0, . . . , 0)} z ||v|| ≤ 1, in 0, če za vsak
v ∈ L(v1, . . . , vn)\{(0, . . . , 0)} velja ||v|| > s. Če noben izmed pogojev
ne velja, je izhod lahko poljuben.
81–97 87
i
i
“Marc” — 2020/11/10 — 11:31 — page 88 — #8 i
i
i
i
i
i
Tilen Marc
Opomba: Ime GapSVP je bilo izbrano, saj v problemu odločamo o ob-
stoju najkraǰsega neničelnega vektorja (ang. shortest vector problem) z raz-
makom (ang. gap) s. Natančneje, treba je določiti, ali v rešetki obstaja
kratek neničeln vektor z normo največ 1, ali pa so vsi neničelni vektorji
dalǰsi od s. Večji kot je s, lažji je problem.
Z naslednjim izrekom je Regev pokazal, da sta problema LWEn,m,p,χ in
GapSVP(n, s) povezana.
Izrek 8 ([4]). Naj bo n ∈ N in p,m, α vrednosti, ki so odvisne od n, da velja:
p je praštevilo, m ∈ N ne več kot polinomsko večji od n in α ∈ (0, 1) tak,
da je σ := αp > 2
√
n. Če obstaja algoritem, ki za vsak n reši odločitveni
problem LWEn,m,p,D̄σ v polinomskem času (v parametru n), potem obstaja
kvantni polinomski algoritem, ki reši problem GapSVP(n, n/α).
Izrek pravi, da je problem LWEn,m,p,D̄σ vsaj tako težek, kot je problem
GapSVP(n, n/α), če imamo dostop do kvantnega računalnika. Ker je pro-
blem GapSVP(n, s) že dlje časa preučevan in ne poznamo kvantnega algo-
ritma, ki bi rešil GapSVP(n, n/α) v polinomskem času, izrek vliva upanje,
da polinomskega algoritma za reševanje LWEn,m,p,D̄σ ni.
Zgornji rezultat nam torej zagotavlja, da vsi znani algoritmi za reševanje
LWEn,m,p,D̄σ s parametri, izbranimi tako, da zadoščajo pogojem iz izreka
8, potrebujejo eksponentno mnogo korakov (glede na n), da rešijo problem.
Za praktično uporabo v kriptografiji bi želeli konkretne parametre: npr.
na podlagi natančne analize znanih algoritmov za reševanje problemov na
rešetkah v [1] ocenjujejo, da je za parametre n = 256, p 16-bitno praštevilo
in σ ≈ 26 časovna zahtevnost reševanja ustreznega problema LWE vsaj 2153.
Kriptosistem z javnim ključem, osnovan na problemu LWE
Priljubljenost problema LWE izhaja iz dejstva, da omogoča konstrukcijo
novih kriptografskih shem, katerih varnost temelji na težavnosti reševanja
odločitvenega problema LWE. Prvo tako shemo je opisal že Regev v članku
[4].
Naj bo n > 1 parameter, ki določa varnost, p praštevilo, da velja n2 ≤
p ≤ 2n2, m = (1 + )(n + 1) log(p) za neko malo konstanto  > 0 (izbrano
tako, da je m ∈ N) in naj bo χ = D̄σ, torej diskretna Gaussova porazdelitev
nad Zp, kjer je σ = p/(
√
n log2(n)). Izbrani parametri ustrezajo pogojem
izreka 8, tako da bi rešitev odločitvenega problema LWEn,m,p,χ pomenila
velik preboj na področju reševanja problemov na rešetkah.
Opǐsimo kriptosistem z javnim ključem, ki temelji na problemu LWE.
Vse aritmetične operacije v shemi opravimo po modulu p, torej v Zp:
88 Obzornik mat. fiz. 67 (2020) 3
i
i
“Marc” — 2020/11/10 — 11:31 — page 89 — #9 i
i
i
i
i
i
Problem učenja z napakami in sodobni kriptosistemi
• Generiranje ključev: Naj bo s ∈ Znp enakomerno naključen vektor in
A ∈ Zm×np enakomerno naključna matrika. Naj bo e ∈ Zm vektor, kate-
rega komponente so izbrane naključno iz porazdelitve D̄σ. Izračunajmo
b = As + e. Potem je vektor s skrivni ključ in par (A, b) javni ključ
kriptosistema.
• Šifriranje: Naj bo M ∈ {0, 1} sporočilo, ki ga želimo šifrirati. Če po-
znamo javni ključ (A, b), lahko izberemo vektor r ∈ {0, 1}m enakomerno
naključno in izračunamo
C = (c0, c1) = (r
TA, rT b+M · bp/2c),
ki ga obravnavamo kot šifriran M .
• Dešifriranje: S pomočjo skrivnega ključa s izračunamo d = c1 − c0s,
kar dešifriramo kot vrednost 0, če je d bližje 0, in 1, če je bližje bp/2c.
Zgoraj opisani kriptosistem omogoča šifriranje sporočila M ∈ {0, 1}, torej
enega bita. Če želimo poslati dalǰse sporočilo (256-bitno sporočilo je v praksi
pogost primer), potem preprosto pošljemo več različnih sporočil, pri čemer
za vsako izberemo nov naključen r. Slednje je računsko zahtevneǰse kot
šifriranje s pomočjo standardnih kriptosistemov z javnim ključem, vendar
praktično izvedljivo s sodobnimi računalniki.
Vsak kriptosistem mora izpolnjevati dve zahtevi: po pravilnosti in varno-
sti. Za kriptosistem pravimo, da deluje pravilno, če je dešifrirano sporočilo
enako prvotnemu sporočilu. Za določitev varnosti kriptosistema obstaja
več matematičnih definicij. Najmanǰsa zahteva je, da napadalec samo iz
kriptograma in javnih parametrov ne sme biti sposoben dešifrirati sporo-
čila. Vendar to za sodobne standarde varnosti ne zadošča več: želimo, da
napadalec iz kriptograma in javnih parametrov ne more izvedeti (skoraj)
ničesar. Temu se približa naslednja definicija. Za kriptosistem pravimo, da
je IND-CPA varen (ang. indistinguishability of ciphertext), če napadalec, ki
ne pozna skrivnega ključa, na podlagi javnih parametrov in kriptograma C
ne more razlikovati med dvema besediloma enake dolžine, ki sta bili šifrirani
(v našem primeru, ali je bil šifriran bit M = 0 ali M = 1).
Skicirajmo, zakaj je kriptosistem, osnovan na problemu LWE, varen.
Več podrobnosti o dokazu lahko bralec najde v [4].
Izrek 9. Zgoraj opisan kriptosistem za dovolj velik n deluje pravilno – torej
dešifrirana vrednost ustreza šifrirani – ter je IND-CPA varen pri predpo-
stavki LWE s parametri n,m, p, χ.
81–97 89
i
i
“Marc” — 2020/11/10 — 11:31 — page 90 — #10 i
i
i
i
i
i
Tilen Marc
Skica dokaza. Dokažimo, da sistem pravilno dešifrira vrednosti:
d = c1 − c0s = rT b+M · bp/2c − rTAs = rT (As+ e) +M · bp/2c − rTAs
= M · bp/2c+ rT e.
Omejimo vrednost rT e. Komponente e so izbrane iz porazdelitve D̄σ, kjer
je σ = p/(
√
n log2(n)). Naj bodo i1, . . . , ik, k ≤ m indeksi komponent
vektorja r, ki so neničelni. Potem je rT e =
∑k
j=1 eij . Slednje je vsota
neodvisnih diskretnih Gaussovih porazdelitev, kar ima porazdelitev račun-
sko neločljivo diskretni Gaussovi porazdelitvi s standardno deviacijo
√
kσ ≤√
mσ ≤
√
2n log(2n2)p/(
√
n log2(n)) = αp, kjer je α v O(1/ log(n)). Za
dovolj velik n je verjetnost, da je vrednost iz porazdelitve D̄p/ log(n) večja od
p/4, zanemarljivo majhna. Torej je d = M · bp/2c+ rT e bližje bp/2c kot 0,
če je M = 1, in bližje 0, če je M = 0. Sledi, da je dešifriranje pravilno.
Skicirajmo še, zakaj je kriptosistem varen. Pokazati moramo, da napa-
dalec, ki ne pozna skrivnega ključa, na podlagi javnih parametrov in kripto-
grama ne more razlikovati, ali je bil šifriran bit M = 0 ali M = 1. Oglejmo
si kriptogram C = (rTA, rT b+M ·bp/2c). Če velja predpostavka LWE, je za
napadalca vrednost b neločljiva od enakomerno naključnega vektorja iz Zmp .
Tako imenovana »leftover hash lemma« [4] pravi, da je potem porazdelitev
rT b za enakomerno naključen r ∈ {0, 1}m statistično zelo blizu enakomerne
porazdelitve. Enako velja za rTA; napadalec torej ne more razločiti vredno-
sti (rTA, rT b) od enakomerno naključno izbranih vrednosti. Potem je tudi
porazdelitev (rTA, rT b+M · bp/2c) za napadalca neločljiva od enakomerno
naključne in ne more razločiti, ali je šifriran bit M = 0 ali M = 1.
Homomorfno šifriranje
V preǰsnjem razdelku smo spoznali, kako sestaviti kvantno varen kriptosis-
tem z javnim ključem s pomočjo problema LWE. V tem razdelku pa bomo
pokazali, da se tak kriptosistem z nekaj truda da nadgraditi v t. i. sistem
homomorfnega šifriranja. Osnovna naloga klasičnih kriptosistemov je, da
omogočajo varen prenos oziroma hrambo podatkov. Homomorfno šifriranje
poleg slednjega omogoča še varno računanje na šifriranih podatkih.
V naslednjih podrazdelkih bomo natančneje spoznali homomorfno šifri-
ranje in njegove uporabe. V podrazdelku Aditivno šifriranje bomo doka-
zali, da že kriptosistem, opisan v razdelku Kriptosistem z javnim ključem,
osnovan na problemu LWE, vsebuje nekatere lastnosti homomorfnega šifri-
ranja. Podrazdelka Generator psevdonaključnih vektorjev s stranskimi vrati
in Dvojǐsko kodiranje sta tehnične narave, saj predstavita vse potrebno za
nadgradnjo v kriptosistem za homomorfno šifriranje, ki je opisan v podraz-
delku Homomorfno šifriranje.
90 Obzornik mat. fiz. 67 (2020) 3
i
i
“Marc” — 2020/11/10 — 11:31 — page 91 — #11 i
i
i
i
i
i
Problem učenja z napakami in sodobni kriptosistemi
Aditivno šifriranje
Kriptosistem, opisan v preǰsnjem razdelku, ima zanimivo lastnost. Recimo,
da z istim javnim ključem (A, b) šifriramo dve vrednosti: m1,m2 ∈ {0, 1},
tj.
(c10, c
1
1) = (r
T
1 A, r
T
1 b+m1 · bp/2c), (c20, c21) = (rT2 A, rT2 b+m2 · bp/2c).
Potem lahko brez poznavanja skrivnega ključa izračunamo:
(c0, c1) = (c
1
0, c
1
1) + (c
2
0, c
2
1) = ((r1 + r2)
TA, (r1 + r2)
T b+ (m1 +m2) · bp/2c).
Opazimo, da lahko (c0, c1) obravnavamo kot šifro in jo poskusimo dešifrirati
s pomočjo skrivnega ključa s. Dobimo:
d = c0s− c1 = (r1 + r2)T (As+ e) + (m1 +m2) · bp/2c)− (r1 + r2)TAs
= (r1 + r2)
T e+ (m1 +m2) · bp/2c).
Če so vrednosti e dovolj majhne v primerjavi s p (kar pri kriptosistemu
zahtevamo), potem je vrednost d bližje 0 kot bp/2c, natanko tedaj, ko je
m1 + m2 = 0 ali pa m1 + m2 = 2. Torej, par (c0, c1) ustreza kodiranemu
sporočilu m1 +m2 mod 2. Ali z drugimi besedami, dobimo šifrirano XOR-
operacijo bitov m1 in m2.
Recimo, da imamo podatke, podane z biti m1, . . . ,mk, in bi želeli izra-
čunati neko funkcijo f(m1, . . . ,mk). Omejimo se na funkcije, ki se jih da
opisati z zaporedno uporabo operacije XOR. Potem lahko podatke šifriramo
in jih pošljemo ponudniku računanja v oblaku, ki nam pretvori šifrirane po-
datke v šifrirano vrednost f(m1, . . . ,mk), ne da bi kakorkoli poznal podatke.
Tako lahko računanje funkcij prenesemo na ponudnika takih storitev, brez
ogrožanja osebnih podatkov.
Seveda so funkcije, ki jih lahko opǐsemo samo z uporabo vrat XOR, zelo
omejene, pravzaprav neuporabne. Želeli bi kriptosistem, ki omogoča raču-
nanje poljubnih funkcij na šifriranih podatkih. Osnovna teorija računanja
nam zagotavlja, da lahko poljubno funkcijo izrazimo z zaporedno uporabo
NAND-vrat (znana tudi kot Shefferjev veznik). V naslednjih razdelkih bomo
predstavili kriptosistem, ki omogoča seštevanje in množenje šifriranih podat-
kov in s tem uporabo NAND-vrat.
Generator psevdonaključnih vektorjev s stranskimi vrati
Problem LWE nam omogoča sestaviti nepričakovano orodje, ki ga bomo
uporabili v shemi za homomorfno šifriranje. Tako kot prej naj bo m ≥ n ≥
1, A ∈ Zm×np enakomerno naključno izbrana matrika, x ∈ Znp enakomerno
naključno izbran vektor in e ∈ Zn vektor z majhnimi vrednostimi, naključno
81–97 91
i
i
“Marc” — 2020/11/10 — 11:31 — page 92 — #12 i
i
i
i
i
i
Tilen Marc
izbran iz porazdelitve χ. Naj bo b = Ax + e in naj bo β = bp/2c−1, torej
inverz bp/2c v Zp. definirajmo matriko B ∈ Zm×(n+1)p , katere prvi stolpec je
−βb, ostali stolpci pa ustrezajo A. Prav tako definirajmo s ∈ Zn+1p , katerega
prva komponenta je bp/2c, ostale komponente pa ustrezajo x.
Predpostavimo, da je odločitveni problem LWEn,m,p,χ težek; npr. izbe-
rimo vrednosti n,m, pχ tako, da je problem vsaj tako težek kot problem na
rešetkah, opisan v izreku 8. Potem nihče, ki ne pozna s, ne more razlikovati
matrike B od enakomerno naključno generirane matrike, saj je b (in zato
tudi −βb) neločljiv od enakomerno naključnega vektorja. Po drugi strani,
če poznamo s, lahko izračunamo
Bs = −bp/2cβb+Ax = −(Ax+ e) +Ax = −e.
Po izreku 8 lahko parametre izberemo tako, da je |ei| <
√
p za vsako ko-
ordinato ei vektorja e, saj lahko izberemo porazdelitev χ = Dσ z dovolj
majhno standardno deviacijo. Torej je −e vektor z majhnimi vrednostmi.
Če poznamo s, lahko določimo, ali je B resnično enakomerna naključna ma-
trika ali pa je bila generirana, kot je opisano zgoraj, saj lahko preprosto
preverimo, če je vsaka komponenta Bs od 0 oddaljena za največ
√
p.
Zgornji postopek nam ob pravilni izbiri parametrov n,m, p, χ omogoča
naslednje. Če naključno izberemo s, potem lahko generiramo n+1-dimenzi-
onalne vektorje bi (vrstice matrike B), ki jih nihče, ki ne pozna s, ne more
razlikovati od enakomerno naključnih. Vendar porazdelitev teh vektorjev
ni enakomerno naključna (je samo psevdonaključna), saj za njih velja, da
je skalarni produkt bi in s manǰsi od
√
p. Psevdonaključni vektorji imajo
torej t. i. stranska vrata: čeprav se zdijo naključno izbrani, imajo posebne
lastnosti, ki jih lahko izkoristimo.
Definicija 10. LWE-generator psevdonaključnih vektorjev s stranskimi vrati
je par (Gs, s), kjer je Gs algoritem, ki generira naključne vektorje bi ∈ Znp ,
katerih porazdelitev je brez poznavanja s računsko neločljiva od enakomerno
naključnih vrednosti, ter s ∈ Znp s prvo komponento s1 = bp/2c tak, da je
|bTi s| <
√
p za vsak bi generiran z Gs.
Zgoraj smo opisali, kako sestaviti LWE-generator psevdonaključnih vek-
torjev s stranskimi vrati, ki lahko generira vsaj m psevdonaključnih vektor-
jev pri predpostavki LWEn,m,p,χ. Rekli bomo, da tak generator izberemo
naključno, če naključno izberemo s, e in A iz ustreznih porazdelitev.
Dvojǐsko kodiranje
Preden spoznamo kriptosistem, ki omogoča homomorfno šifriranje, potrebu-
jemo še zadnje orodje. Kodiranje je injektivna funkcija, ki vhodne podatke
92 Obzornik mat. fiz. 67 (2020) 3
i
i
“Marc” — 2020/11/10 — 11:31 — page 93 — #13 i
i
i
i
i
i
Problem učenja z napakami in sodobni kriptosistemi
pretvori v vektorje izbrane oblike. Za razliko od šifriranja kodiranje ne
skrije podatkov, ampak jih samo preoblikuje. Da sestavimo kriptosistem s
homomorfnim šifriranjem, potrebujemo orodje, ki nam bo vektorje nad Zp
pretvorilo v (dalǰse) vektorje z majhnimi vrednostmi.
Dvojǐsko kodiranje je funkcija, ki naravna števila pretvori v vektorje
ničel in enk, t. i dvojǐski zapis. Omejimo se na naravna števila, manǰsa od
nekega p ∈ N, torej števila iz Zp. Za vsak x ∈ Zp lahko enolično določimo
vrednosti yi ∈ {0, 1} za 0 ≤ i < dlog2(p)e, da velja
x =
dlog2(p)e−1∑
i=0
2iyi.
Preslikavo x 7→ x̂, kjer je x̂ = (y0, y1, . . . , ydlog2(p)e−1) ∈ {0, 1}
dlog2(p)e tak,
da velja zgornja enačba, imenujemo dvojǐsko kodiranje z dlog2(p)e biti.
Inverzno preslikavo imenujemo dekodiranje in je po zgornji enačbi line-
arna preslikava, tj. x dobimo iz x̂ kot skalarni produkt x = q · x̂, kjer je
q = (1, 2, 4, . . . , 2dlog2(p)e−1).
Poleg elementov Zp bi želeli dvojǐsko kodirati tudi vektorje in matrike
nad Zp. Za vektorje nad Znp dvojǐsko kodiranje definiramo kot preslikavo iz
Znp v {0, 1}ndlog2(p)e. Dvojǐsko kodiranje vektorja x ∈ Znp označimo z x̂ in ga
definiramo kot vektor dolžine ndlog2(p)e s komponentami iz množice {0, 1},
katerega bloki dolžine dlog2(p)e predstavljajo dvojǐski zapis komponent x:
x = (x1, x2, . . . , xn) 7→ (x̂1, x̂2, . . . , x̂n) = x̂.
Za tako definirano dvojǐsko kodiranje vektorjev je operacija dekodiranja
linearna. Zato lahko s Q označimo matriko dimenzij n×ndlog2(p)e, da velja
Qx̂ = x za vsak x ∈ Znp . Iz zgoraj opisanega je razvidno, da lahko matriko
Q zapǐsemo kot
Q=

1 2 4 . . . 2dlog2(p)e−1 0 0 0 . . . 0 . . . 0 0 0 . . . 0
0 0 0 . . . 0 1 2 4 . . . 2dlog2(p)e−1 . . . 0 0 0 . . . 0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 0 0 . . . 0 0 0 0 . . . 0 . . . 1 2 4 . . . 2dlog2(p)e−1
 .
Podobno lahko dvojǐsko kodiramo tudi matrike. Za matriko C ∈ Zm×np
označimo s Ĉ matriko dimenzij m× ndlog2(p)e, ki predstavlja dvojǐsko ko-
diranje vrstic ci, za 1 ≤ i ≤ m, v C:
C =

c1
c2
...
cm
 7→

ĉ1
ĉ2
...
ĉm
 = Ĉ.
81–97 93
i
i
“Marc” — 2020/11/10 — 11:31 — page 94 — #14 i
i
i
i
i
i
Tilen Marc
Po definiciji velja ĈQT = C za vsako matriko C ∈ Zk×np , kjer je k > 0
poljuben.
Homomorfno šifriranje
V tem razdelku bomo opisali kriptosistem za homomorfno šifriranje. Ta
omogoča, da lastnik skrivnega ključa šifrira podatke, ki jih lahko nato (v
šifrirani obliki) ne samo seštevamo, temveč tudi množimo. Za dešifriranje se
uporabi isti ključ, tako da je tak sistem simetrične narave. Dokazali bomo,
da sistem omogoča varno računanje v oblaku.
Varnost kriptosistema bo temeljila na težavnosti problema LWE, torej
bo tak kriptosistem tudi kvantno varen ob pravilni izbiri parametrov:
• Generiranje ključev: Ključe, ki nam bodo omogočili šifriranje do k bi-
tov, izberemo na naslednji način. Določimo n, p,m = kndlog2(p)e in χ
tako, da je odločitveni problem LWEn,m,p,χ težek – po izreku 8 to lahko
storimo. Naključno izberemo LWE-generator psevdonaključnih vektor-
jev s stranskimi vrati (Gs, s) (torej izberemo A, e, s, kot opisano v po-
drazdelku Generirator psevdo-naključnih vektorjev s stranskimi vrati),
ki temelji na težavnosti problema LWEn,m,p,χ. Par (Gs, s) je skrivni
ključ.
• Šifriranje: Da šifriramo bit b ∈ {0, 1}, uporabimo skrivni ključ (Gs, s),
tako da s pomočjo Gs generiramo vektorje d1, . . . , dndlog2(p)e ∈ Z
n
p in
sestavimo matriko D ∈ Zndlog2(p)e×n, katere vrstice so vektorji di. Izra-
čunamo matriko bQT +D in jo podamo v dvojǐskem kodiranju:
C = ̂bQT +D.
• Dešifriranje: S skrivnim ključem s in danim kriptogramom C izraču-
namo vektor x = CQT s. Če je prva komponenta x bližje 0 kot bp/2c,
potem vrnemo 0, sicer vrnemo 1.
Kriptosistem šifrira vsak bit b v dvojǐsko matriko C dimenzij ndlog2(p)e ×
mdlog2(p)e. Kot bomo videli, lahko tako šifrirane podatke (matrike) sešte-
vamo in množimo ter tako varno računamo funkcije brez poznavanja po-
datkov. Seveda je tako računanje časovno in prostorsko veliko zahtevneǰse
kot računanje na nešifriranih podatkih. Presenetljivo je, da je tak kripto-
sistem sploh teoretično mogoč. Še več; za ne preveč zahtevne funkcije je s
sodobnimi računalniki računanje tudi praktično izvedljivo.
Analizirajmo varnost in pravilnost sheme:
94 Obzornik mat. fiz. 67 (2020) 3
i
i
“Marc” — 2020/11/10 — 11:31 — page 95 — #15 i
i
i
i
i
i
Problem učenja z napakami in sodobni kriptosistemi
Lema 11. Če je C kriptogram, ki šifrira b, potem velja:
CQT s = bQT s+ e,
kjer je vsaka komponenta vektorja e manǰsa od
√
p.
Dokaz. Ker velja M̂QT = M za vsako matriko M , lahko izračunamo:
CQT s = ( ̂bQT +D)QT s = (bQT +D)s = bQT s+Ds.
Vrstice D so generirane z LWE-generatorjem psevdonaključnih vektorjev s
stranskimi vrati (Gs, s), tako da za vsako vrstico di ∈ Z1×np velja |dis| <
√
p.
Izrek 12. Zgoraj opisan kriptosistem deluje pravilno in je IND-CPA varen.
Dokaz. Pokažimo, da kriptosistem deluje pravilno. Ko v postopku dešifri-
ranja izračunamo x = CQT s, dobimo vektor x, katerega prva komponenta
ustreza prvi komponenti bQT s + e po lemi 11. Spomnimo se, da je prva
komponenta vektorja s enaka bp/2c, medtem ko je prva vrstica QT enaka
[1, 0, . . . , 0]. Torej je prva komponenta m1 = bbp/2c+ e1, kjer je |e1| <
√
p.
Sledi, da če je b = 1, je m1 bližje bp/2c kot 0, in obratno, če je b = 0.
Varnost kriptosistema se dokaže tako, da se argumentira, da nihče, ki ne
pozna skrivnosti s, ne more računsko razlikovati šifrirane vrednosti b = 0 od
šifrirane vrednosti b = 1. Ker je matrika D generirana z LWE-generatorjem
psevdonaključnih vektorjev, je za vsakega, ki ne pozna s, računsko neločljiva
od enakomerno naključne matrike. Torej je tudi vrednost bQT +D neločljiva
od enakomerno naključne matrike. Sledi, da nihče, ki ne pozna s, ne more
ločiti, katera vrednost je bila šifrirana.
Pripravljeni smo, da predstavimo, kako opisan kriptosistem omogoča
homomorfno šifriranje. Naj bosta C1 in C2 kriptograma, ki šifrirata bita b1
in b2:
• Seštevanje: definirajmo C1⊕C2 = C1 +C2 in obravnavajmo slednje kot
nov kriptogram. Za dešifriranje izračunamo
(C1 ⊕ C2)QT s = (C1 + C2)QT s = (b1 + b2)QT s+ (e1 + e2),
kjer je ||ei||∞ <
√
p, po lemi 11. Vidimo, da se C1 ⊕ C2 dešifrira v
vrednost b1 + b2 mod 2, torej v XOR-operacijo bitov b1 in b2, le da je
šum e1 + e2, ki pri tem nastane, povečan.
81–97 95
i
i
“Marc” — 2020/11/10 — 11:31 — page 96 — #16 i
i
i
i
i
i
Tilen Marc
• Množenje: definirajmo C1⊗C2 = Ĉ1QTC2. Prav tako lahko izračunamo
(C1 ⊗ C2)QT s = Ĉ1QTC2QT s = Ĉ1QT (b2QT s+ e2)
= b2C1Q
T s+ Ĉ1QT e2 = b1b2Q
T s+ b2e1 + Ĉ1QT e2,
kjer prva enakost velja po definiciji C1 ⊗ C2, druga in četrta po lemi
11 in tretja velja, saj je X̂QT = X za vsako matriko X po lastnostih
dvojǐskega kodiranja. Po lemi 11 je ||ei||∞ <
√
p. Tudi tokrat lahko na
zgoraj navedeno gledamo kot na dešifriranje vrednosti b1b2 mod 2 s šu-
mom b2e1+Ĉ1QT e2. Prepričajmo se, da je slednja vrednost res majhna,
torej da jo res lahko obravnavamo kot šum in ne pokvari dešifriranja.
Ker velja ||e1||∞ <
√
p in b2 ∈ {0, 1}, je prvi člen res majhen. Po drugi
strani je Ĉ1QT dvojǐsko kodiranje matrike C1Q
T , torej so njene kompo-
nente iz {0, 1}. Ker ima ndlog2(p)e stolpcev in je ||e2||∞ <
√
p, vidimo,
da je vsaka komponenta drugega člena omejena z ndlog2(p)e
√
p. Za
primerno izbrane parametre je taka vrednost še vedno manǰsa od p/4,
torej dešifriranje C1⊗C2 uspe in vrne b1b2 mod 2, torej AND-operacijo
bitov b1 in b2.
Kot vidimo, nam kriptosistem omogoča operaciji seštevanja in množenja
kriptogramov in s tem operaciji XOR in AND na šifriranih podatkih. Želeli
bi kriptosistem, ki bi lahko izračunal vsako funkcijo. Kot smo omenili v raz-
delku Aditivno šifriranje, zadošča, da sistem omogoča zaporedno izvajanje
NAND-vrat (Shefferjevega veznika) na šifriranih podatkih, saj lahko s tem
veznikom predstavimo vsako funkcijo. Uporabimo množenje za definicijo
nove operacije na šifriranih podatkih:
• NAND: definirajmo C1 Z C2 = I − C1 ⊗ C2. Če slednje obravnavamo
kot nov kriptogram in dešifriramo, dobimo
(C1 Z C2)Q
T s = (I − C1 ⊗ C2)QT s = (1− b1b2)QT s− b2e1 − Ĉ1QT e2.
V izračunu smo uporabili enakost, ki smo jo dobili pri operaciji množe-
nja. Vidimo, da se C1 Z C2 dešifrira v vrednost 1 − b1b2 mod 2, torej
NAND-vrednost bitov b1 in b2.
S takim kriptosistemom lahko torej (teoretično) izračunamo poljubno
funkcijo na šifriranih podatkih, vendar pri tem šum narašča in z večkratnim
ponavljanjem operacije lahko naraste do takih vrednosti, da dešifriranje ni
več uspešno. Zato je treba vnaprej omejiti število zaporednih operacij, ki
96 Obzornik mat. fiz. 67 (2020) 3
i
i
“Marc” — 2020/11/10 — 11:31 — page 97 — #17 i
i
i
i
i
i
Problem učenja z napakami in sodobni kriptosistemi
jih sistem še omogoča, oziroma v primeru kompleksneǰsih funkcij parametre
povečati tako, da še sprejmejo izbrano funkcijo.
Takemu kriptosistemu pravimo tudi delno homomorfno šifriranje. Gen-
try je v [3] dokazal, da se v nekaterih primerih da delno homomorfno šifrira-
nje spremeniti v polno homomorfnega s tehniko, ki jo je imenoval bootstra-
ping. Tehnika deluje na vsakem delno homomorfnem sistemu, ki zadošča
tako imenovani ciklični varnosti. Vendar je prehod na polno homomorfen
sistem računsko zelo zahteven in zato počasneǰsi, tako da se večina praktič-
nih uporab omeji na delno homomorfno šifriranje. Zainteresiranega bralca,
ki bi želel izvedeti več o uporabi problema LWE v kriptografiji, usmerimo k
branju [2].
V času pisanja tega članka že obstaja več implementacij delno in polno
homomorfnih kriptosistemov. Veliko truda je bilo vloženega v razvoj učinko-
viteǰsega homomorfnega šifriranja, kot je bil opisan v tem razdelku. Glavni
steber trenutnega razvoja predstavljajo problem LWE in njegove izpeljanke.
LITERATURA
[1] M. R. Albrecht, R. Player in S. Scott, On the concrete hardness of learning with errors,
Journal of Mathematical Cryptology 9(3) (2015), 169–203.
[2] B. Barak, An intensive introduction to cryptography, dostopno na intensecrypto.
org/public/index.html, ogled 3. 11. 2020.
[3] C. Gentry, Fully homomorphic encryption using ideal lattices, v Proceedings of the
forty-first annual ACM symposium on Theory of computing, 2009, 169–178.
[4] O. Regev, On lattices, learning with errors, random linear codes, and cryptography,
Journal of the ACM 56(6) (2009), 1–40.
[5] R. L. Rivest, L. Adleman in M. L. Dertouzos, On data banks and privacy homomor-
phisms, Foundations of secure computation 4(11) (1978), 169–180.
[6] P. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms
on a quantum computer, SIAM review 41(2) (1999), 303–332.
[7] Post-Quantum Cryptography, dostopno na csrc.nist.gov/Projects/Post-Quantum-
Cryptography, ogled 3. 11. 2020.
http://www.dmfa-zaloznistvo.si/
81–97 97