OBZORNIK
ZA MATEMATIKO IN FIZIKO
IZDAJA DRUŠTVO MATEMATIKOV, FIZIKOV IN ASTRONOMOV SLOVENIJE
ISSN 0473-7466
MAJ 2020STR 81-120ŠT. 3LETNIK 67LJUBLJANAOBZORNIK MAT. FIZ.
C  KM Y 
2020
Letnik 67
3
i
i
“kolofon” — 2020/11/10 — 9:53 — page 1 — #1 i
i
i
i
i
i
OBZORNIK ZA MATEMATIKO IN FIZIKO
Glasilo Društva matematikov, fizikov in astronomov Slovenije
Ljubljana, MAJ 2020, letnik 67, številka 3, strani 81–120
Naslov uredništva: DMFA–založništvo, Jadranska ulica 19, p. p. 2964, 1001 Ljubljana
Telefon: (01) 4766 633, 4232 460 Telefaks: (01) 4232 460, 2517 281 Elektronska
pošta: zaloznistvo@dmfa.si Internet: http://www.obzornik.si/ Transakcijski
račun: 03100–1000018787 Mednarodna nakazila: SKB banka d.d., Ajdovščina 4,
1513 Ljubljana SWIFT (BIC): SKBASI2X IBAN: SI56 0310 0100 0018 787
Uredniški odbor: Peter Legiša (glavni urednik), Sašo Strle (urednik za matematiko in
odgovorni urednik), Aleš Mohorič (urednik za fiziko), Mirko Dobovišek, Irena Drevenšek
Olenik, Damjan Kobal, Petar Pavešić, Marko Petkovšek, Marko Razpet, Nada Razpet,
Peter Šemrl, Matjaž Zaveršnik (tehnični urednik).
Jezikovno pregledal Grega Rihtar.
Računalniško stavila in oblikovala Tadeja Šekoranja.
Natisnila tiskarna COLLEGIUM GRAPHICUM v nakladi 1100 izvodov.
Člani društva prejemajo Obzornik brezplačno. Celoletna članarina znaša 24 EUR, za druge
družinske člane in študente pa 12 EUR. Naročnina za ustanove je 35 EUR, za tujino 40 EUR.
Posamezna številka za člane stane 3,99 EUR, stare številke 1,99 EUR.
DMFA je včlanjeno v Evropsko matematično društvo (EMS), v Mednarodno matematično
unijo (IMU), v Evropsko fizikalno društvo (EPS) in v Mednarodno združenje za čisto in
uporabno fiziko (IUPAP). DMFA ima pogodbo o recipročnosti z Ameriškim matematič-
nim društvom (AMS).
Revija izhaja praviloma vsak drugi mesec. Sofinancira jo Javna agencija za raziskovalno
dejavnost Republike Slovenije iz sredstev državnega proračuna iz naslova razpisa za sofi-
nanciranje domačih znanstvenih periodičnih publikacij.
© 2020 DMFA Slovenije – 2126 Poštnina plačana pri pošti 1102 Ljubljana
NAVODILA SODELAVCEM OBZORNIKA ZA ODDAJO PRISPEVKOV
Revija Obzornik za matematiko in fiziko objavlja izvirne znanstvene in strokovne članke iz mate-
matike, fizike in astronomije, včasih tudi kak prevod. Poleg člankov objavlja prikaze novih knjig
s teh področij, poročila o dejavnosti Društva matematikov, fizikov in astronomov Slovenije ter vesti
o drugih pomembnih dogodkih v okviru omenjenih znanstvenih ved. Prispevki naj bodo zanimivi in
razumljivi širšemu krogu bralcev, diplomantov iz omenjenih strok.
Članek naj vsebuje naslov, ime avtorja (oz. avtorjev), sedež institucije, kjer avtor(ji) dela(jo), izvle-
ček v slovenskem jeziku, naslov in izvleček v angleškem jeziku, klasifikacijo (MSC oziroma PACS)
in citirano literaturo. Slike in tabele, ki naj bodo oštevilčene, morajo imeti dovolj izčrpen opis, da jih
lahko večinoma razumemo tudi ločeno od besedila. Avtorji člankov, ki želijo objaviti slike iz drugih
virov, si morajo za to sami priskrbeti dovoljenje (copyright). Prispevki so lahko oddani v računalni-
ški datoteki PDF ali pa natisnjeni enostransko na belem papirju formata A4. Zaželena velikost črk
je 12 pt, razmik med vrsticami pa vsaj 18 pt.
Prispevke pošljite odgovornemu uredniku ali uredniku za matematiko oziroma fiziko na zgoraj na-
pisani naslov uredništva. Vsak članek se praviloma pošlje dvema anonimnima recenzentoma, ki
morata predvsem natančno oceniti, kako je obravnavana tema predstavljena, manj pomembna pa je
originalnost (in pri matematičnih člankih splošnost) rezultatov. Če je prispevek sprejet v objavo,
potem urednik prosi avtorja še za izvorne računalniške datoteke. Le-te naj bodo praviloma napisane
v eni od standardnih različic urejevalnikov TEX oziroma LATEX, kar bo olajšalo uredniški postopek.
Avtor se z oddajo članka strinja tudi z njegovo kasnejšo objavo v elektronski obliki na internetu.
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
i
i
“Razpet” — 2020/11/10 — 9:45 — page 98 — #1 i
i
i
i
i
i
VRTENJE ZRCAL
NADA RAZPET
Pedagoška fakulteta
Univerza v Ljubljani
Ključne besede: ravno zrcalo, konkavno cilindrično zrcalo, konstrukcije slik, lege slik
Najprej bomo vrteli dve med seboj pravokotni zrcali, ki z vodoravno ravnino oklepata
kot 45◦, okrog navpične osi, nato pa bomo vrteli konkavno cilindrično zrcalo. Pokazali
bomo, da se pri zasuku zrcal za kot α slika v obeh primerih zavrti za kot 2α.
ROTATION OF MIRRORS
We first consider rotation about a vertical axis of two mutually perpendicular mirrors
making an angle of 45◦ with the horizontal plane, then we consider rotation of a concave
cylindrical mirror. We show that, in both cases, rotating mirrors by an angle α produces
rotation of the image by an angle 2α.
Geometrijska optika je v vseh izobraževalnih programih na koncu študij-
skega leta. V osnovni šoli pokažemo nekaj poskusov z ravnimi in krogelnimi
zrcali ter konstruiramo nekaj slik, ki nastanejo pri preslikavah s temi zr-
cali. Za konstrukcijo slik uporabljamo le karakteristične žarke. Večinoma
preslikujemo pokončne predmete, najraje na optično os pravokotne daljice,
pravzaprav le krajǐsča daljic z dvema žarkoma: z žarkom, ki je vzporeden z
optično osjo, in žarkom, ki gre skozi teme zrcal.
V srednji šoli geometrijsko optiko »na hitro« ponovimo. Da pojmi niso
razčǐsčeni, se hitro pokaže pri preverjanjih znanja, pa tudi naše izkušnje s
tekmovanj v znanju fizike kažejo, da se tematiki ne posveča posebne po-
zornosti. Še več, opuščajo se tudi osnovni poskusi, ki pa so lahko še kako
zanimivi.
Ravna in krogelna zrcala so lahko dostopna in so na voljo v različnih
velikostih. S cilindričnimi se v šoli ne ukvarjamo, brez težav pa jih izdelamo
sami iz zrcalne folije, ki jo dobimo tudi pri nas.
Ravno zrcalo
Navadno je ravno zrcalo obešeno na navpični steni. Pri poskusih pa ga
postavimo pravokotno na mizo, kjer med poskusom miruje. Kaj pa se zgodi,
če ravno zrcalo zasučemo? Ali je vseeno, okoli katere osi sučemo zrcalo?
Kako naj bo postavljeno? Če sučemo le eno ravno zrcalo okrog osi, ki je
pravokotna na ravnino zrcala, ne opazimo nič posebnega. Drugače pa je,
če sučemo dve ravni zrcali, ki se stikata po eni stranici in sta med seboj
98 Obzornik mat. fiz. 67 (2020) 3
i
i
“Razpet” — 2020/11/10 — 9:45 — page 99 — #2 i
i
i
i
i
i
Vrtenje zrcal
pravokotni. Lahko bi bili tudi pod drugačnim kotom, recimo 30◦, 45◦ ali
60◦. To so koti, ki so delitelji polnega kota. Medsebojni kot vpliva na število
slik, ki jih vidimo.
Dve med seboj pravokotni ravni zrcali
Obravnavo poskusov z dvema, med seboj pravokotnima zrcaloma, najdemo
v številnih učbenikih fizike, recimo v [1]. Pogosto avtorji predstavijo tudi
konstrukcije slik v poševni projekciji ali pa v tlorisu. Pri tem sta zrcali
postavljeni pravokotno na podlago in pri poskusih mirujeta. Izjemoma so
predstavljeni kalejdoskopi, kjer pa se hkrati z vrtenjem zrcal spreminja tudi
lega predmetov.
V članku [3] je opisan poskus z dvema pravokotnima zrcaloma v ška-
tli, ki jo vrtimo okrog vodoravne osi. Naš poskus je enostavneǰsi, saj ne
potrebujemo škatle in lepljenja zrcal.
Dve ravni zrcali postavimo na nosilec tako, da sta med seboj pravokotni
in z vodoravno ravnino – mizo – oklepata kot 45◦, kot kaže slika 1.
Slika 1. Dve, med seboj pravokotni ravni zrcali postavimo na vodoravno podlago, ki je
vrtljiva okoli navpične osi.
Nad zrcali obesimo figuro prometnika. Na začetku poskusa je telo promet-
nika vzporedno z mizo in stično stranico zrcal. Zrcali vrtimo v vodoravni
ravnini (x, y) okrog navpične osi z. Najprej ju zavrtimo za kot α = 45◦
(slika 2), nato pa za α = 90◦. Opazujemo sliko, ki nastane po odboju od
obeh zrcal.
Kaj smo opazili? Ko zrcali zasučemo za kot α, se slika zavrti za kot 2α.
Račun za dve med seboj pravokotni zrcali
Zdaj pa izide poskusov utemeljimo še z računom. Najprej ponovimo, kako
točko zrcalimo preko premice. Izberemo premico p, ki gre skozi koordinatno
izhodǐsče. Točko D s krajevnim vektorjem −⇀rD preslikamo preko premice p
98–111 99
i
i
“Razpet” — 2020/11/10 — 9:45 — page 100 — #3 i
i
i
i
i
i
Nada Razpet
Slika 2. Prometnik je obešen nad zrcaloma tako, da leži vodoravno in se med poskusom
ne premika. Ko zrcalo zavrtimo za 45◦, se slika zavrti za 90◦. Tudi slika fotografove glave
se je zavrtela, čeprav fotografira vedno z istega mesta. Opazujemo le sliko, ki nastane po
odboju od obeh zrcal.
v točko D′ s krajevnim vektorjem −⇀rD′ . Enotski normalni vektor na premici
p je vektor −⇀n (slika 3). Veljata zvezi:
Slika 3. Preslikava točke preko premice.
d(DD′) = 2−⇀rD · −⇀n , −⇀rD′ = −⇀rD − 2(−⇀rD · −⇀n )−⇀n . (1)
Pri zrcaljenju točke preko ravnine velja enaka povezava kot za preslikavo
preko premice (enačba (1)), kjer je vektor −⇀n zdaj enotski normalni vektor
na ravnino.
Narǐsimo še ustrezno skico (slika 4). Namesto celega predmeta bomo
prezrcalili le eno točko in pogledali, kako se spreminja lega slike točke po
odboju od obeh zrcal v odvisnosti od zasuka zrcal.
100 Obzornik mat. fiz. 67 (2020) 3
i
i
“Razpet” — 2020/11/10 — 9:45 — page 101 — #4 i
i
i
i
i
i
Vrtenje zrcal
Slika 4. Če zrcali zavrtimo za kot α okrog navpične osi, se slika točke, po odboju od obeh
zrcal, zavrti za kot 2α.
Normalna vektorja na ravninah Z1 in Z2 sta:
−⇀n1(α) =
√
2
2
(− sinα, cosα, 1), −⇀n2(α) =
√
2
2
(sinα,− cosα, 1),
−⇀n2(α) = −⇀n1(π + α).
Najprej točko T prezrcalimo preko ravnine Z1 :
−⇀r ′ = −⇀r − 2(−⇀r · −⇀n1)−⇀n1 ,
−⇀r ′ = (x0, y0, z0)− (−x0 sinα+ y0 cosα+ z0) · (− sinα, cosα, 1).
Krajevni vektor točke T ′ je
−⇀r ′ =
 x0 cos2 α+ y0 sinα cosα+ z0 sinαx0 sinα cosα+ y0 sin2 α− z0 cosα
x0 sinα− y0 cosα
 .
Točko T ′ potem prezrcalimo še preko Z2, da dobimo točko T
′′. Krajevni
vektor točke T ′′ je:
−⇀r ′′ = −⇀r ′ − 2(−⇀r ′ · −⇀n2)−⇀n2 . (2)
Izračunamo vektor, ki kaže iz točke T ′ do točke T ′′, pri čemer upoštevamo
povezavo
−2(−⇀r ′ · −⇀n2)−⇀n2 = −
 x0 sin2 α− y0 sinα cosα+ z0 sinα−x0 sinα cosα+ y0 cos2 α− z0 cosα
x0 sinα− y0 cosα+ z0
 .
98–111 101
i
i
“Razpet” — 2020/11/10 — 9:45 — page 102 — #5 i
i
i
i
i
i
Nada Razpet
Vstavimo v enačbo (2) in upoštevamo, da velja
sin2 α+ cos2 α = 1, 2 sinα cosα = sin(2α), cos2 α− sin2 α = cos(2α).
(3)
Nazadnje dobimo:
−⇀r ′′ =
 x0 cos(2α) + y0 sin(2α)x0 sin(2α)− y0 cos(2α)
−z0
 =
=
 cos(2α) − sin(2α) 0sin(2α) cos(2α) 0
0 0 1
 1 0 00 −1 0
0 0 −1
 x0y0
z0
 .
Kaj smo ugotovili?
V začetni legi zrcal, ko je kot α = 0, dobimo sliko T ′′ točke T tako, da
jo prezrcalimo preko osi x. Ko pa zrcali zasukamo za kot α, se prezrcaljena
točka še zavrti okrog osi z za kot 2α.
Ker je predmet na začetku poskusa ležal vzporedno z mizo, tudi izbrana
slika predmeta – slika po odboju od obeh zrcal – leži v ravnini, ki je vzpo-
redna z mizo in od nje enako oddaljena kot predmet.
Poudarimo še to, da na sliki leva in desna roka prometnika nista zame-
njani – lopar še vedno drži v desni roki, kot je to pri preslikavi z enim ravnim
zrcalom.
Konkavno cilindrično zrcalo
Naredimo še poskus s konkavnim cilindričnim zrcalom. O tem lahko beremo
v [2].
Konkavno cilindrično zrcalo izdelamo iz pravokotnega kosa zrcalne fo-
lije, ki ga pritrdimo na obroč. Mi smo vzeli pravokotnik z osnovnico, ki meri
približno polovico obsega obroča. Obroč poteka po polovici vǐsine pravoko-
tnika. Zrcalna folija je torej del plašča valja, katerega os je pravokotna na
ravnino obroča. Obroč vrtljivo pritrdimo na nosilec tako, da se vrti okrog
vodoravne osi, ki gre skozi sredǐsče obroča. Os valja se potem vrti v navpični
ravnini. Razdalja d prometnika do zrcala naj bo med r in 2r, pri čemer je
r polmer obroča, na katerem je pritrjena folija. Na začetku je obroč vodo-
ravno, prometnik pa stoji navpično. Ravnino obroča zavrtimo najprej za
45◦, nato pa za 90◦ (slika 5).
Kaj opazimo? Opazimo, da se slika predmeta tudi zavrti. V prvem
primeru leži slika prometnika vodoravno, v drugem pa je obrnjen na glavo.
Opazimo še, da leva in desna stran nista zamenjani. Na sliki prometnik še
vedno drži lopar v desni roki. Da je slika res realna, bomo pokazali kasneje.
102 Obzornik mat. fiz. 67 (2020) 3
i
i
“Razpet” — 2020/11/10 — 9:45 — page 103 — #6 i
i
i
i
i
i
Vrtenje zrcal
Slika 5. Predmet je pred konkavnim cilindričnim zrcalom in se med poskusom ne premika.
Ko zrcalo zavrtimo za kot 45◦, se slika zavrti za kot 90◦, ko pa zrcalo zasukamo za kot
90◦, se slika zasuka za 180◦.
Ponazorimo si to še s skicama (slika 6 in 7), ki smo jih naredili s pro-
gramom GeoGebra. Predmet je štirikotnik, ki leži v ravnini vzporedni z
ravnino (y, z). Slika štirikotnika pa ni ravninski lik. Preslikani štirikotnik je
»ukrivljen«, kar kaže slika 7.
Pokažimo še, da je slika realna. Poǐsčimo sliko točke T , katere odda-
ljenost od zrcala je med r in 2r. Opazujemo žarke, ki ležijo v ravnini, ki
je pravokotna na os valja. Na sliki 8 sta vpadni pravokotnici označeni črt-
kano. Slika točke T je točka T ′. Sekata se odbita žarka, torej je slika realna.
Za ozek trak konkavnega cilindričnega zrcala lahko privzamemo, da je del
konkavnega krogelnega zrcala, za katerega velja:
1
a
+
1
b
=
1
f
98–111 103
i
i
“Razpet” — 2020/11/10 — 9:45 — page 104 — #7 i
i
i
i
i
i
Nada Razpet
Slika 6. Leva slika kaže začetno lego predmeta – štirikotnika – in njegovo sliko. Desno:
Ko zrcalo zavrtimo za kot 45◦, se slika štirikotnika zavrti za kot 90◦. Slika je realna.
Slika 7. Projekcija štirikotnika – daljica – in njegove slike – ukrivljena črta – na vodoravno
ravnino (x, y) pri zasuku osi zrcala za 45◦. Stranice slike štirikotnika so zakrivljene in ne
ležijo v isti ravnini. Slika je realna.
Gorǐsčna razdalja takega zrcala je r/2. Točke, ki so od temena oddaljene za
r ≤ a < 2r, se preslikajo v točke, za katere je oddaljenost od temena 2r/3 ≤
b < r. Pri računanju bomo tudi privzeli, da je oddaljenost y0 vpadnega
žarka od osi valja majhna v primerjavi s polmerom valja. Posledično to
pomeni, da so vpadni koti žarkov majhni. Pri večjih vpadnih kotih bi morali
upoštevati, da slika točke pri vrtenju zrcala opisuje krivuljo, ki ni ravninska
(slika 7).
104 Obzornik mat. fiz. 67 (2020) 3
i
i
“Razpet” — 2020/11/10 — 9:45 — page 105 — #8 i
i
i
i
i
i
Vrtenje zrcal
Slika 8. Sliko točke T dobimo s presečǐsčem odbitih žarkov. Vpadni pravokotnici sta
označeni črtkano.
Račun za konkavno cilindrično zrcalo
Ugotovitve podkrepimo še z računom. Vrtilna os naj bo kar os x, kot vrtenja
bomo označili z α, os valja, katerega del je zrcalo, pa naj leži v ravnini (y, z).
Zapǐsimo enačbo zrcala v parametrični obliki, kjer sta u in v parametra, kot
α pa kot nagiba osi valja;
−⇀r (u, v) = (a cosu, a sinu cosα+ v sinα,−a sinu sinα+ v cosα). (4)
Pri tem je a polmer valja, parametra pa zavzemata naslednje vrednosti:
u ∈ [−π/2, π/2] in v ∈ [−h, h]. S h smo označili polovično vǐsino valja.
Brez škode za splošnost lahko privzamemo, da je polmer valja a = 1.
Smerni vektor na osi valja je −⇀n = (0, sinα, cosα). Preslikujemo točko
T (0, y0, 0). Vpadni žarek naj bo vzporeden z osjo x in naj leži na premici p:
−⇀p = (0, y0, 0) + λ(1, 0, 0). (5)
Pri tem je λ parameter. Točka A(x1, y0, 0) je prebodǐsče vpadnega žarka s
plaščem valja, torej leži tako na premici p, ki je vzporedna z osjo x, kot na
ploskvi −⇀r (u, v), zato mora veljati:
λ = cosu0,
y0 = sinu0 cosα+ v0 sinα, (6)
0 = − sinu0 sinα+ v0 cosα. (7)
Vpadni žarek prebada plašč valja v točki A. Lega vpadnega žarka se pri
nagibanju osi ne spreminja. Spremeni pa se lega vpadne pravokotnice, to je
premice, ki gre skozi prebodǐsče A in je pravokotna na os valja. Vpadni žarek
p, prebodǐsče A, vpadna pravokotnica n in odbiti žarek p′ ležijo v ravnini, ki
je pravokotna na os valja. Slika točke T , točka T ′, leži na odbitem žarku p′.
98–111 105
i
i
“Razpet” — 2020/11/10 — 9:45 — page 106 — #9 i
i
i
i
i
i
Nada Razpet
Slika 9. Uporabljene oznake v računih.
Lega odbitega žarka pa je odvisna od lege vpadne pravokotnice n, ki pa jo
lahko hitro zapǐsemo. Omenimo še, da sliko točke T dobimo s presečǐsčem
odbitih žarkov, v našem primeru premic p′ in t, torej je slika realna [6].
Prebodǐsče A se pri zasuku osi za kot α premika po premici p. Iz enačb
(6) in (7) izrazimo v0 in sinu0. Dobimo:
v0 = y0 sinα, (8)
sinu0 = y0 cosα. (9)
Potrebujemo še ploskovno normalo, ki je vpadna pravokotnica za žarek, ki
leži na premici p. Najprej izračunamo iz enačbe (4) parcialna odvoda:
∂−⇀r
∂u
= (− sinu, cosu cosα,− cosu sinα), ∂
−⇀r
∂v
= (0, sinα, cosα),
nato pa normalni vektor −⇀n dobimo z vektorskim produktom parcialnih
odvodov:
−⇀n = ∂
−⇀r
∂u
× ∂
−⇀r
∂v
= (cosu, sinu cosα,− sinu sinα).
Za normalni vektor tangentne ravnine v točki A torej velja:
−⇀n1 = (cosu0, sinu0 cosα,− sinu0 sinα). (10)
106 Obzornik mat. fiz. 67 (2020) 3
i
i
“Razpet” — 2020/11/10 — 9:45 — page 107 — #10 i
i
i
i
i
i
Vrtenje zrcal
Vstavimo za sinu0 izraz (9) in upoštevamo, da veljajo povezave (3);
−⇀n1 =
 √1− y20 cos2 αy0 cos2 α
−y0 cosα sinα
 . (11)
Slika 10. Slika točke T je točka T ′. Poljubna točka na premici p′ in poljubna točka na
normali se zavrtijo za 180◦ (zaporedno od zgoraj navzdol), ko os valja zasukamo za 90◦.
Zdaj pa poglejmo, kam se preslikajo nekatere točke. Ker gledamo žarke
v ravninah, ki so pravokotne na os valja, izračunajmo sredǐsče krožnice,
ki jo ta ravnina odreže od valja. Sredǐsče S leži na osi valja, ta pa je v
ravnini (y, z). Poiskati moramo torej presečǐsče med osjo valja in premico,
ki gre skozi točko T in je pravokotna na os valja. Teh dveh premic ni težko
zapisati, saj obe ležita v isti ravnini.
z = y cotα, z = −(y − y0) tanα
z =
y0 tanα
1 + tan2 α
, y =
y0 tan
2 α
1 + tan2 α
.
Presečǐsče teh dveh premic je točka
S(0, y0 sin
2 α, y0 sinα cosα).
Ko je os valja navpično, je sredǐsče kroga v izhodǐsču (S = O = (0, 0, 0))
(slika 11). Ko os zasukamo za kot 90◦, preide točka S v točko S1 =
98–111 107
i
i
“Razpet” — 2020/11/10 — 9:45 — page 108 — #11 i
i
i
i
i
i
Nada Razpet
(0, y0, 0) = T . Vzemimo, da potuje točka S po krožnici. Sredǐsče je točka
M = (0, y0/2, 0). Da zares potuje po krožnici, mora biti
∣∣∣∣−⇀OS −−−⇀OM ∣∣∣∣ = y0/2.
Pa poglejmo:
−⇀
OS−−−⇀OM =
(
0, y0 sin
2 α− y0
2
, y0 sinα cosα
)
=
(
0,−cos 2α
2
y0,
sin 2α
2
y0
)
,
∣∣∣∣−⇀OS −−−⇀OM ∣∣∣∣ = |y0|2 .
Absolutna vrednost razlike teh dveh vektorjev je konstantna, torej se točka S
giblje po krožnici. Ko se os valja zavrti za kot 90◦, točka S opǐse polkrožnico.
Slika 11. Točka S opisuje polkrožnico, ko os valja zavrtimo za 90◦.
To lahko zapǐsemo še drugače:
−⇀
OS −−−⇀OM =
 1 0 00 cos 2α sin 2α
0 − sin 2α cos 2α
 0−1
0
 y0
2
.
Točka S se torej pri zasuku valja – zrcala – za kot α zavrti za kot 2α.
Poǐsčimo še enačbo premice p′, na kateri leži odbiti žarek. V ta namen
najprej eno točko prezrcalimo preko vpadne pravokotnice. Vzemimo kar
točko T (0, y0, 0). Pomagamo si s skico 12.
Naj bo točka B pravokotna projekcija točke T na vpadno pravokotnico.
Iz skice razberemo, da velja:
−⇀
ST = (0, y0 cos
2 α,−y0 sinα cosα),
−⇀
SB = (
−⇀
ST · −⇀n1)−⇀n1 .
108 Obzornik mat. fiz. 67 (2020) 3
i
i
“Razpet” — 2020/11/10 — 9:45 — page 109 — #12 i
i
i
i
i
i
Vrtenje zrcal
Slika 12. Točko T prezrcalimo preko vpadne pravokotnice. Dobimo točko T1.
Pri tem je vektor −⇀n1 enotski vektor na vpadni pravokotnici. Dobimo:
−⇀
SB = y20 cos
2 α
(√
1− y20 cos2 α, y0 cos
2 α, −y0 sinα cosα
)
.
In končno
−−⇀
ST1 =
−⇀
ST + 2
−⇀
TB = 2
−⇀
SB −−⇀ST, −−⇀OT1 =
−⇀
OS +
−−⇀
ST1,
−−⇀
OT1 =
 2y
2
0
√
1− y20 cos2 α · cos2 α
y0 cos
2 α(2y20 cos
2 α− 1) + y0 sin2 α
−2y0 sinα cosα(y20 cos2 α− 1)
 .
Zapǐsimo še krajevna vektorja točke T1 pri kotih α = 0
◦ in α = 90◦:
−⇀r1 = (2y20
√
1− y20, y0(2y
2
0 − 1), 0), −⇀r2 = (0, y0, 0).
Točka T1 leži na premici p
′, to je na odbitem žarku. Enačbe te premice ne
bomo računali, je pa ni težko najti, saj sta na njej točka A, to je prebodǐsče,
in točka T1. Poglejmo, kakšno krivuljo opǐse, ko se os valja zavrti za kot
90◦. Privzemimo, da potuje po krožnici, ki ima sredǐsče v točki B. Potem
mora biti ∣∣∣∣−−⇀OT1 −−⇀OB∣∣∣∣ = ∣∣∣∣−⇀BT ∣∣∣∣ .
Po dalǰsem računu pokažemo, da leva stran ni enaka desni. Lahko pa z
uporabo enega od grafičnih programov hitro ugotovimo, da se krivulja pri
majhnih vpadnih kotih kar dobro prilega krožnici.
Še ena zanimivost cilindričnega konkavnega zrcala
V članku [6] je napisan komentar na članek [2], kjer je opisano vrtenje
opazovalčeve glave pri vrtenju konkavnega cilindričnega zrcala in narisana
konstrukcija slike, ko je os valja horizontalna.
98–111 109
i
i
“Razpet” — 2020/11/10 — 9:45 — page 110 — #13 i
i
i
i
i
i
Nada Razpet
V komentarju avtor opozarja, da je treba opazovati ne le žarke, ki ležijo
v ravninah, ki so pravokotne na os valja, ampak tudi tiste vpadne žarke,
ki ležijo v ravninah, ki so vzporedne z osjo valja. Ti žarki namreč določajo
navidezno sliko predmeta.
Slika 13. Levo: realna slika figure. Desno: navidezna slika figure. Figura je bila ves čas
na istem mestu.
Ali res lahko vidimo obe sliki? Kažeta ju fotografiji na sliki 13. Poskus
smo naredili z zrcalom, ki leži na valju s polmerom r ≈ 20 cm. Figuro smo
postavili pred sredǐsče osnovne ploskve valja. Leva fotografija kaže realno
sliko – prometnik na sliki drži znak v desni roki, desna fotografija pa kaže
navidezno sliko figure – prometnik na sliki drži znak v levi roki. Ta slika ni
ostra in je nekoliko »raztegnjena«. Da vidimo navidezno sliko, se moramo
zelo približati zrcalu. Oči morajo biti na razdalji, ki je manǰsa r/2. Med
poskusoma figure nismo premikali.
Naredimo še konstrukcijo te slike. Kaže jo slika 14. Štirikotnik leži v
ravnini, ki je pravokotna na os x. Njegova oddaljenost od plašča valja je med
r in 2r. Premica p je presečǐsče ravnine, ki je pravokotna na os y in ravnino
štirikotnika ter gre skozi točko O, s plaščem valja. Na premici izberemo
dve točki, narǐsemo vpadna žarka, poǐsčemo vpadni pravokotnici in odbita
110 Obzornik mat. fiz. 67 (2020) 3
i
i
“Razpet” — 2020/11/10 — 9:45 — page 111 — #14 i
i
i
i
i
i
Vrtenje zrcal
žarka. Presečǐsče podalǰskov odbitih žarkov je točka O′. Ko točka O potuje
po štirikotniku, točka O′ rǐse navidezno sliko štirikotnika. Poudarimo še, da
vpadni žarek, vpadna pravokotnica in odbiti žarek ležijo v isti ravnini, ki
pa ni vzporedna s premico p in z osjo valja.
Pri velikem r bi lahko privzeli, da je del plašča valja raven. Tedaj bi vsi
trije žarki ležali v ravnini, vzporedni z osjo valja.
Slika 14. Levo: Konstrukcija navidezne slike. Desno: Lega realne in navidezne slike
štirikotnika. Navidezna slika leži za zrcalom, realna pa pred njim in za predmetom.
Poskus s konkavnim cilindričnim zrcalom, ko je slika obrnjena na glavo,
kažejo predavatelji na začetku predavanj iz optike [7]. Primer narobe obr-
njene glave s konkavnim cilindričnim zrcalom je opisan tudi v knjigi [4]
angleškega pisatelja detektivskih zgodb R. Austina Freemana.
Take poskuse kažejo tudi v hǐsah eksperimentov, kjer obiskovalci, ki
stojijo pred zrcalom, vidijo svojo obrnjeno glavo. Nismo pa našli zapisov,
da bi zrcalo vrteli. Ker sta poskusa primerna za ustvarjanje optičnih iluzij,
bo morda naš prispevek vzpodbudil koga, da ju bo postavil v katero od
slovenskih hǐs eksperimentov ali pa v hǐso iluzij.
LITERATURA
[1] P. Chagnon, Animated displays II: Multiple reflections, Phys. Teach. 30 (1992), 488–
492.
[2] S. Derman, An optical puzzle that will make your head spin, Phys. Teach. 19 (1981),
str. 395.
[3] A. J. DeWeerd, S. E. Hill, Reflections on Handedness, Phys. Teach. 42 (2004), 275–
279.
[4] R. A. Freeman, The Apparition of Burling Court, in The Famous Cases of Dr. Thorn-
dyke, Hodder & Stoughton, London, 1929, 818–852.
[5] T. B. Greenslade Jr., A Scientific Mystery, Phys. Teach. 67 (2019), str. 221.
[6] T. M. Holzberlein, How to become dizzy with Derman’s optical puzzle, Phys. Teach.
20 (1982), 401–402.
[7] Real image from a concave mirror, dostopno na www.berkeleyphysicsdemos.net/
node/723, ogled 22. 9. 2020.
98–111 111
i
i
“Legisa” — 2020/11/9 — 7:08 — page 112 — #1 i
i
i
i
i
i
NOVE KNJIGE
John Urschel in Louisa Thomas, Mind and Matter, A Life in Math and
Football, Penguin Press, New York, 2019, 238 str.
Pred nami je nova, res zanimiva knjiga.
John Urschel je več let presenetljivo
združeval kariero igralca amerǐskega no-
gometa in študenta matematike, tako na
dodiplomski kot podiplomski ravni. Zelo
kmalu je postal tudi soavtor in edini av-
tor znanstvenih člankov, ki sodijo na po-
dročja teorije grafov, linearne algebre in
numerične analize. Trenutno je doktor-
ski študent uporabne matematike na pre-
stižni univerzi MIT v Bostonu. Soavto-
rica knjige je njegova žena Louisa Tho-
mas, pisateljica in novinarka.
Urschelov oče je kanadski kirurg.
Mati je sprva delala kot bolnǐska sestra,
nato pa je končala pravo in postala od-
vetnica. Sina je stimulirala z matematič-
nimi ugankami, računanjem na pamet in
poljudnoznanstvenimi knjigami. Urschel se v družbi sošolcev ni preveč zna-
šel. Tudi šola se mu je zdela dolgočasna in ni sodeloval pri pouku, zato je bil
razrednik mnenja, da je navadna šola zanj prezahtevna. Mati je posredo-
vala s predlogom, da testirajo njegove sposobnosti, čemur je sledil nasprotni
predlog, naj sin preskoči razred – a se mati s tem ni strinjala.
John Urschel je veselje do matematike začutil že v vǐsjih razredih osnovne
šole, vendar se je pri pouku dolgočasil. Poleti, v času počitnic pred osmim
razredom ga je oče, ki se je po ločitvi v Johnovem zgodnjem otroštvu spet
preselil bliže, poslal poslušat predavanja iz, kot bi temu rekli mi, Matematike
1 (z odvodom in integralom) za ekonomiste na Univerzi v Buffalu, kjer je
oče takrat na tej univerzi vpisal magisterij iz ekonomije. Sinu, ki je že takrat
imel 180 cm, je dal kar svojo študentsko izkaznico. Za mladega Johna so
bila predavanja zahtevna, a je snov kmalu obvladal bolje od večine in celo
pomagal drugim pri domačih nalogah.
Amerǐski nogomet je za gledalce zelo privlačna športna panoga, ki ima
bolj malo skupnega z našim nogometom. Ekipa ima na razpolago štiri po-
skuse, da prenese žogo vsaj deset jardov na nasprotno stran. Na igrǐsču
112 Obzornik mat. fiz. 67 (2020) 3
i
i
“Legisa” — 2020/11/9 — 7:08 — page 113 — #2 i
i
i
i
i
i
Mind and Matter, A Life in Math and Football
so zato črte v oddaljenosti deset jardov. Igralec teče z žogo, stisnjeno ob
sebi, ali pa jo poda soigralcu. Nasprotniki mu poskušajo izbiti žogo ali pre-
streči podajo. Če ekipa ne napreduje deset jardov, dobi žogo druga ekipa.
Če je videti, da ne bo šlo do naslednje črte, v četrtem poskusu streljajo z
nogo skozi dvignjen okvir na nasprotni strani, kar prinese nekaj točk. Naj-
več točk prinese prenos žoge do konca polja nasprotne ekipe (to imenujemo
touchdown).
Občasno se kakšnemu izmed bolj atletskih igralcev posreči, da z žogo teče
in se kot po čudežu izogiba nasprotnikom, dokler ne doseže konca igrǐsča.
To seveda dvigne stadion na noge.
Šport igra pomembno vlogo na amerǐskih univerzah in moštvo ameri-
škega nogometa je običajno najpomembneǰsa ekipa. Diplomanti tudi de-
setletja kasneje obiskujejo tekme in navijajo za svojo univerzo. Šport je
torej pomemben člen pri povezavi univerze z alumni, ki zbirajo denar za
svojo univerzo in jo podpirajo tudi na druge načine. Alma mater (blago-
rodna mati) je izraz, ki ga diplomanti uporabljajo za univerzo, na kateri
so študirali. (Morda bo čez nekaj desetletij kdo ta izraz uporabil tudi v
Sloveniji.)
Univerze rekrutirajo igralce iz srednješolskih moštev, jim dajejo štipen-
dije in nudijo pomoč pri študiju, denimo inštrukcije iz matematike. Odlični
športniki obidejo običajno selekcijo glede na intelektualne sposobnosti, kar
včasih povzroča slabo voljo pri drugih študentih. Pred desetletji je bil pi-
sec teh vrstic na univerzi Tulane priča odmevni aferi. Na izpitu je nekaj
igralcev amerǐskega nogometa goljufalo, a asistent prekrška ni opazil. Do-
godek so nekaj mesecev kasneje prijavili drugi študenti in kljub privilegijem
je krivcem takrat grozil izpis z univerze.
Igralci amerǐskega nogometa so skoraj brez izjeme veliki, močni, eksplo-
zivni in, kot pravi sam Urschel, med igro praktično nimajo časa za razmi-
šljanje: delujejo bolj ali manj instinktivno. Pogosto skušajo izvesti vnaprej
natrenirane strategije podaj in premikov. Igra je že v osnovi groba in vzrok
mnogih poškodb. V zadnjih letih pa je, podobno kot boks, prǐsla na slab
glas zaradi številnih pretresov možganov in hudih dolgotrajnih posledic, kot
je demenca. Več študij pravi, da so še posebej destruktivni udarci, pri kate-
rih pride do naglega sukanja glave in posledičnega zvijanja možganov okrog
dela, ki se nadaljuje v hrbtenjačo. Urschel ima verjetno srečo, da je čokat
in ima izredno močan vrat, kar zmanǰsuje možnost takega vrtenja. Tudi
pri našem tipu nogometa so iz tega razloga fantje precej manj ogroženi kot
dekleta.
Knjiga amerǐski nogomet obravnava s stalǐsča poznavalca igre in v dolo-
čenih delih vsebuje precej tehničnega žargona, ki ga je pisec teh vrstic bolj
Obzornik mat. fiz. 67 (2020) 3 113
i
i
“Legisa” — 2020/11/9 — 7:08 — page 114 — #3 i
i
i
i
i
i
Nove knjige
ali manj preskočil. (Kot pravi Urschel, je s temi pojmi imela težave tudi
njegova mama.) Za Neameričane je bolje uživati v preostali pripovedi, ki je
zelo lepo napisana, kar sam Urschel pripisuje soavtorici. (Dodaja pa, da je
za morebitne napake v matematičnih delih odgovoren sam.)
John je začel amerǐski nogomet igrati v gimnaziji. Kot izrazito tekmo-
valna oseba je zagrizeno treniral in uspelo mu je dobiti športno štipendijo
na univerzi Penn State (Pennsylvania State University). Tu je njegovo na-
darjenost za matematiko opazil profesor Vadim Kaloshin, ki mu je zastavil
nalogo iz problema treh teles, torej nebesne mehanike. Tudi tu je Urschel
zagrizel in skupaj s profesorjem sta napisala znanstveni članek.
Ob tem je tudi vneto treniral, se zelo dobro počutil v tesno povezanem
nogometnem moštvu in užival v agresivni igri ter odzivu stotisočglave mno-
žice na stadionu (Penn State ima ogromen stadion). A kot trdi v knjigi,
je bil pri 191 centimetrih in 135 kilogramih med manǰsimi in je moral zato
trenirati še toliko bolj kot ostali.
Za magisterij ga je pod svoje okrilje vzel profesor matematike Ludmil
Zikatanov, po rodu iz Bolgarije. Spet je za magistrsko nalogo dobil origina-
len rezultat iz teorije grafov, a je kasneje v dokazu našel napako. Vendar je
to po več mesecih dela odpravil in skupaj z mentorjem objavil članek.
Leta 2014 je začel igrati kot profesionalec v znanem moštvu Ravens
(Krokarji) iz Baltimora. Mnogi, vključno z mamo, so ga opozarjali, naj raje
izbere znanstveno kariero. Za podpis pogodbe je dobil 144 tisoč dolarjev.
Glede na to, koliko bi igral, pa bi lahko v treh letih zaslužil še 2,3 milijona
dolarjev. Dejansko je igral tri sezone in po [3] zaslužil 1,6 milijona dolarjev.
Večino denarja je prihranil. A kot pravi, je bil v tem položaju bolj ali manj
plačanec. Solidarnosti v moštvu je bilo bolj malo: če nisi bil izbran za igro,
je bil zaslužek precej manǰsi. Kljub treningom je obdržal matematične stike
in celo položaj mladega raziskovalca na Penn Statu.
Dejstvo, da nadarjen matematik igra v profesionalni ligi, je zbudilo veliko
pozornosti v medijih. Opravil je veliko intervjujev, ki jih je izkoristil za
reklamo za matematiko. Tudi Amerǐsko matematično društvo (American
Mathematical Society) je izdalo plakat [4] z njegovo podobo in zgodbo, leta
2016 pa v reviji Notices objavilo intervju [2] z njim.
Leta 2015 se je potegoval za vpis v doktorski program na univerzi MIT
– Massachusetts Institute of Technology. Pri tem sploh ni nameraval pre-
nehati igrati, kar je spravilo v zadrego predstojnike oddelkov, ki so se prvič
srečali s takim primerom. Vendar je imel za podiplomskega študenta zelo
dobro bibliografijo in na koncu so ga vendarle sprejeli v program uporabne
matematike, z začetkom študija spomladi 2016.
114 Obzornik mat. fiz. 67 (2020) 3
i
i
“Legisa” — 2020/11/9 — 7:08 — page 115 — #4 i
i
i
i
i
i
Mind and Matter, A Life in Math and Football
Med treningom v letu 2015 se je obrnil in nasprotni igralec ga je z glavo
od strani zadel v sence. Izgubil je zavest in se zbudil z vsemi simptomi
resnega pretresa možganov. Tri tedne ni mogel trenirati, še precej dlje pa se
ni mogel ukvarjati z matematiko. Sposobnosti vizualizacije so ga zapustile,
reševati ni mogel niti lažjih problemov. (Tudi naš boksar Dejan Zavec je
po prejetem direktu v svojem zadnjem dvoboju izjavil, da ima težave z
orientacijo in lahko do doma pride le s pomočjo navigacije.)
Urschel je eno leto nekako vzporedno vodil šport in študij, tako da je
vpisal predmete, ki jih je že deloma obvladal in so imeli predpisan učbenik.
Na predavanja ni hodil, domače naloge pa je pošiljal po elektronski pošti.
V februarju 2017 je opravil zahteven doktorski izpit. Univerzitetna admini-
stracija mu je sporočila, da se bo jeseni moral posvetiti le študiju. Obenem
je zaročenka pričakovala otroka. Opazil je, da so se mu začeli kriviti prsti,
nabral pa si je tudi nekaj drugih poškodb.
Spomladi 2017 je izšla odmevna študija 111 možganov umrlih igralcev
amerǐskega nogometa, od katerih je 110 imelo nevrodegenerativne spre-
membe, značilne za ljudi, ki pogosto prejmejo udarce v glavo. (Kot pravi
Urschel, so to bili skoraj zagotovo predvsem možgani ljudi, ki so tako in tako
imeli težave.) Vse to je privedlo do nepričakovane odločitve maja 2017, da
preneha igrati. Čeprav se je skušal izogniti publiciteti, je njegova poteza
doživela velik odmev v medijih [3], ki so stvar takoj povezali z omenjeno
zdravstveno študijo.
Zdaj Urschel dela na področju kombinatorične optimizacije. Njegov
mentor je Michel Goemans. Očitno pa ima John preveč energije in se zdaj
poskuša izkazati tudi v šahu. Svojo športno preteklost in impozantno po-
stavo še naprej uporablja v prizadevanjih za popularizacijo matematike. V
prostem času za matematiko in naravoslovne znanosti navdušuje otroke iz
revnih okolij. V prispevku [5] za New York Times je izrazil mnenje, da bi
učitelji matematike lahko bili bolj podobni trenerjem. Dijakom bi lahko
razložili, da nadarjene matematike in druge znanstvenike čaka privlačna
kariera, če so se seveda pripravljeni potruditi. Seznam njegovih objav in
intervjujev v medijih je impresiven in si ga lahko ogledate na [4].
Knjiga vsebuje tudi precej matematične snovi, in sicer tako zgodovino
matematike kot tudi opis nekaterih sodobnih študij ter celo raziskave. Ta del
je zelo dobro in jasno napisan. Poskuša prikazati uporabo matematike, pa
tudi njene omejitve. Nogometna moštva pri izbiranju igralcev uporabljajo
statistiko. Ta mašinerija je odločala o njegovi usodi, a v njeno učinkovitost
John Urschel ni bil preveč prepričan. O pasteh statistike pǐse na straneh
172–174:
Obzornik mat. fiz. 67 (2020) 3 115
i
i
“Legisa” — 2020/11/9 — 7:08 — page 116 — #5 i
i
i
i
i
i
Nove knjige
Srečal sem slavno študijo [1], objavljeno leta 1975, o vpisu na podi-
plomski študij na kalifornijski univerzi (Berkeley). Avtorji študije
so iskali dokaz o pristranskosti na podlagi spola prosilcev v po-
stopku odobritve vpisa. Našli so ga – ali pa se je tako vsaj zdelo.
Od 12.763 prijav za jesen 1973 je bilo sprejetih približno 44 od-
stotkov moških in le 35 odstotkov žensk. Tako je bilo sprejetih
277 žensk manj in 277 moških več, kot če bi bil vpisni postopek
»spolno slep«, ob upoštevanju podobnih kvalifikacij za moške in
ženske . . . (Opomba prevajalca: skoraj vsi študenti so v tem času
morali opraviti identični test: Graduate Record Examination.) Na
tej univerzi o vpisu odloča profesorski zbor oddelka, na katerega se
študent/študentka prijavi . . . Avtorji so se odločili, da pogledajo,
kateri oddelki so najbolj odgovorni za diskriminacijo, in potem in-
dividualno skušajo najti dokaze zanjo. Rezultat jih je šokiral. Uni-
verza je imela 101 oddelek. Šestnajst oddelkov ni imelo prijav s
strani žensk ali pa so sprejeli vse, ne glede na spol . . . Med preo-
stalimi 85 oddelki so našli štiri, pri katerih so bila vidna pomembna
znamenja pristranskosti proti ženskam. Vsi ti oddelki so skupaj
dali deficit 26 žensk. Našli pa so tudi šest oddelkov s pristransko-
stjo v nasprotni smeri, kar je dalo deficit 64 moških. Zmeda je bila
zdaj popolna. Kaj se je zgodilo s pribitkom moških? In kje so bile
manjkajoče ženske?
Avtorji so spoznali, da so zadeli ob nekaj, kar se v statistiki imenuje
Simpsonov paradoks ali zavajajoča korelacija . . . Izkazalo se je, da
se je na nekatere oddelke prijavilo mnogo več ljudi kot na druge.
Skoraj dve tretjini prijavljenih za anglistiko je bilo žensk, medtem
ko je bilo med prijavljenimi za strojnǐstvo le dva odstotka žensk.
Več žensk se je prijavljalo na oddelke, kjer je bil naval prošenj velik,
in manj na oddelke, ki so odobrili velik delež prošenj. Ko so avtorji
to upoštevali, se je izkazalo, da je bila pristranskost proti ženskam
zelo majhna.
Kako je v Sloveniji? Zahteven študij matematike (ali fizike) in naporni
športni treningi ter potovanja na tekme niso ravno kompatibilni. Spomnim
se kolega, ki je bil velik up v lahki atletiki. Po treningih pa je bil tako
utrujen, da je lahko šel le spat, zato je športno kariero obesil na klin. Moj
drugi kolega, fizik in odličen študent, je kot vrhunski plezalec dobil povabilo
na himalajsko odpravo, a se mu je tveganje ozeblin in nesreč vseeno zdelo
preveliko, zato se je raje posvetil zelo uspešni znanstveni in univerzitetni
karieri.
116 Obzornik mat. fiz. 67 (2020) 3
i
i
“Legisa” — 2020/11/9 — 7:08 — page 117 — #6 i
i
i
i
i
i
Mind and Matter, A Life in Math and Football
Tudi pri nas pa najdemo izjeme. Prijetno sem bil presenečen nad vr-
hunskima športnico in športnikom, ki sta bila pri meni na obeh delih izpita
med najbolǰsimi. Maja Pohar je imela množico naslovov državne prvakinje
v badmintonu. Redno se je uvrščala med najbolǰsih 25 na svetu, kar je ob
silni priljubljenosti badmintona v Aziji velik dosežek. Tekmovala je tudi na
olimpijskih igrah leta 2000. Nima vsak, tako kot ona, volje in sposobnosti
za študiranje med vožnjami na tekme. (Vendarle se je tudi njej študij ma-
tematike zaradi športa nekoliko zavlekel.) Zdaj je profesorica statistike na
Medicinski fakulteti.
Fizik Aleš Česen je vrhunski alpinist, ki je ob plezanju doktoriral na
Fakulteti za gradbenǐstvo in geodezijo.
Med »našimi« mlaǰsimi športniki omenimo poklicno boksarko Emo Ko-
zin, rojeno leta 1998 in trenutno študentko tretjega letnika finančne mate-
matike. Je svetovna prvakinja kar v dveh kategorijah. V 21 dvobojih v
poklicni karieri (od leta 2016) je bil izid enkrat neodločen (leta 2018), sicer
pa je dvajsetkrat zmagala, dvakrat tudi v letu 2020.
Živa Dvoršak je diplomirala iz finančne matematike na Fakulteti za ma-
tematiko in fiziko. Na olimpijskih igrah 2012 je v streljanju z zračno puško
na 10 metrov zasedla enajsto mesto. Naslednje leto je osvojila bronasto
kolajno na evropskem prvenstvu. Na olimpijskih igrah leta 2016 je zasedla
sedemnajsto mesto.
LITERATURA
[1] P. J. Bickel, E. A. Hammel in J. W. O’Connel, Sex Bias in Graduate Admissions
Data from Berkeley, Science 187 (1975), 398–404.
[2] S. D. Miller, »I plan to be a great mathematician«: An NFL Offensive Lineman
Shows He’s One of Us, Notices AMS 63(2) 2016, 148–151, dostopno na www.ams.
org/publications/journals/notices/201602/rnoti-p148.pdf, ogled 3. 11. 2020.
[3] T. Rohan, A Calculated Decision: Why John Urschel Chose Math Over
Football, Sports Illustrated, dostopno na www.si.com/nfl/2017/11/21/
john-urschel-nfl-ravens-mit-mathematics, ogled 3. 11. 2020.
[4] John Urschel – Mathematician and Former Pro Football Player, plakat, delo Ame-
rican Mathematical Society, 2017, dostopno na www.ams.org/publicoutreach/
posters/urschel, ogled 3. 11. 2020.
[5] J. Urschel, Math Teachers Should Be More Like Football Coaches, podna-
slov: That style of motivation could help in the classroom, too, The New
York Times, 2019, dostopno na www.nytimes.com/2019/05/11/opinion/sunday/
math-teaching-football.html, ogled 3. 11. 2020.
Peter Legǐsa
Obzornik mat. fiz. 67 (2020) 3 117
i
i
“vesti” — 2020/11/10 — 9:45 — page 118 — #1 i
i
i
i
i
i
VESTI
Aktualna vabila za mednarodne nominacije v matematiki
Odbor za matematiko pri DMFA Slovenije lahko v mednarodnih združenjih
bodisi samostojno bodisi v sodelovanju z drugimi sorodnimi slovenskimi ali
tujimi ustanovami sodeluje pri različnih nominacijah za nagrade ali predlo-
gih za funkcije v mednarodnih telesih. V trenutnem obdobju so aktualni
spodnji razpisi oziroma povabila k vložitvi nominacij. Člani DMFA Slo-
venije ali predstavniki slovenskih znanstvenih ustanov, ki bi želeli vložiti
predlog nominacije preko DMFA Slovenije, lahko pošljejo ustrezno pobudo
na naslov tajnik@dmfa.si in mathematics@dmfa.si.
Nagrade Mednarodne matematične unije (IMU prizes) se podelijo vsaka
štiri leta na Mednarodnem matematičnem kongresu (ICM). Naslednji kon-
gres bo predvidoma poleti 2022 v Sankt Petersburgu, rok za nominacije
prejemnikov nagrad je 31. december 2020. Gre za naslednje nagrade:
• Fieldsova medalja se podeli 2 do 4 matematikom do 40. leta z name-
nom prepoznavanja izjemnih matematičnih dosežkov in podpore nadalj-
njemu delu. Predsednik komisije je Carlos E. Kenig, predsednik IMU,
več podrobnosti na www.mathunion.org/imu-awards/fields-medal.
• Medalja IMU Abacus se podeli za izjemne prispevke posameznika v
matematičnih vidikih informacijskih znanosti. Predsednik komisije je
James Demmel, več podrobnosti na www.mathunion.org/imu-awards/
imu-abacus-medal.
• Nagrada Carla Friedricha Gaussa se podeli z namenom počastitve znan-
stvenika, katerega matematične raziskave so imele izjemen vpliv na dru-
gih področjih, bodisi v tehnologiji, poslovnem svetu ali preprosto v vsak-
danjem življenju. Predsednica komisije je Eva Tardos, več podrobnosti
na www.mathunion.org/imu-awards/carl-friedrich-gauss-prize.
• Chernova medalja se podeli posamezniku za izjemne življenjske dosežke
na področju matematike. Predsednik komisije je Yakov Eliashberg, več
podrobnosti na www.mathunion.org/imu-awards/chern-medal-award.
118 Obzornik mat. fiz. 67 (2020) 3
i
i
“vesti” — 2020/11/10 — 9:45 — page 119 — #2 i
i
i
i
i
i
Vabilo na 73. občni zbor DMFA Slovenije
• Nagrada Leelavati je nagrada za izjemne prispevke k povǐsanju družbe-
nega zavedanja matematike kot intelektualne discipline in ključne vloge,
ki jo igra v raznovrstnih človeških podvigih. Predsednik komisije je
Pavel Etingof, več podrobnosti na www.mathunion.org/imu-awards/
leelavati-prize.
• ICM predavanje Emmy Noether je posebno predavanje v okviru kon-
gresa IMU, namenjeno počastitvi žensk, ki so ustvarile temeljne in
trajne prispevke k matematičnim znanostim. Predsednica komisije je
Sylvia Serfaty, več podrobnosti na www.mathunion.org/imu-awards/
icm-emmy-noether-lecture.
Nominacije za člane Nominacijskega odbora IMU, rok za vložitev je 1. de-
cember 2020. Nominacijski odbor je mednarodno telo, ki pripravi seznam
nominacij in skrbi za izvedbo volitev Izvršnega odbora IMU na kongresu
ICM 2022. Nominacijski odbor sestavljajo predsednik IMU, predsednik NO
(ki ga izbere predsednik IMU), dve osebi s preteklimi izkušnjami pri IMU
(ki ju izbereta predsednika IMU in NO) ter še tri naključno izbrane nomi-
nirane osebe po regionalnem ključu, več podrobnosti na www.mathunion.
org/fileadmin/IMU/EC/Procedures_for_Election_2020-08-19.pdf.
Nagrada Shaw Prize 2021 za matematične znanosti, rok za nominacije
30. november 2020. Nagrade Shaw Prize za področja matematike, astro-
nomije ter znanosti o življenju in medicini veljajo za ekvivalent Nobelove
nagrade Daljnega vzhoda. Predsednik komisije za matematiko v letu 2021 je
Sir Timothy Gowers. Več podrobnosti o nagradah na www.shawprize.org.
Boštjan Kuzman
Vabilo na 73. občni zbor DMFA Slovenije
Vse člane DMFA Slovenije vabim k udeležbi na rednem letnem občnem
zboru Društva matematikov, fizikov in astronomov Slovenije. Občni zbor
bo organiziran na daljavo prek spletne aplikacije ZOOM dne 3. decembra
2020 z začetkom ob 17. uri.
Povezava za udeležbo na občnem zboru bo tri dni pred sestankom po-
slana po elektronski pošti vsem članom društva. Hkrati pozivam vse člane,
Obzornik mat. fiz. 67 (2020) 3 119
i
i
“vesti” — 2020/11/10 — 9:45 — page 120 — #3 i
i
i
i
i
i
Vesti
ki smo jih zaprosili za dopolnitev osebnih podatkov, pa tega še niste storili,
da na naslov tajnik@dmfa.si čimprej posredujete svoj elektronski naslov.
Dnevni red občnega zbora
1. Otvoritev
2. Izvolitev delovnega predsedstva
3. Društvena priznanja
4. Poročila o delu društva
5. Razprava o poročilih
6. Vprašanja in pobude
7. Računovodsko in poslovno poročilo DMFA
8. Razrešitve in volitve
9. Razno
V okviru občnega zbora nam bosta dva prejemnika Zoisove nagrade 2019
v kratkem 20-minutnem predavanju predstavila svoje delo: prof. dr. Denis
Arčon o raziskavah kvantnega magnetizma in prof. dr. Enes Pasalic o krip-
tografiji in informacijski varnosti.
Letošnji Občni zbor je tudi volilni. Predlagana kandidatna lista za vo-
ljene organe DMFA Slovenije za obdobje 2020–2022 je naslednja.
UPRAVNI ODBOR
Predsednica DMFA Slovenije: Nežka Mramor Kosta
Podpredsednica DMFA Slovenije: Marjeta Kramar Fijavž
Tajnik DMFA Slovenije: Janez Krušič
Tajniki oz. tajnici stalnih komisij DMFA Slovenije za:
• popularizacijo matematike v osnovni šoli: Aljoša Brlogar
• popularizacijo matematike v srednji šoli: Sandra Cigula
120 Obzornik mat. fiz. 67 (2020) 3
i
i
“vesti” — 2020/11/10 — 9:45 — page 121 — #4 i
i
i
i
i
i
Vabilo na 73. občni zbor DMFA Slovenije
• popularizacijo fizike v osnovni šoli: Barbara Rovšek
• popularizacijo fizike v srednji šoli: Jurij Bajc
• popularizacijo astronomije: Andrej Guštin
• »Mednarodni matematični kenguru«: Gregor Dolinar
• pedagoško dejavnost: Aleš Mohorič
• informacijsko tehnologijo: Matjaž Željko
• upravne in administrativne zadeve: Ciril Dominko
Predsedniki stalnih strokovnih odborov
• Slovenskega odbora za matematiko: Boštjan Kuzman
• Slovenskega odbora za fiziko: Martin Klanǰsek
• Slovenskega odbora za astronomijo: Andreja Gomboc
Predstavnik Študentske sekcije DMFA Slovenije: Nejc Zajc
Predstavnica Odbora za ženske: Marjetka Conradi
NADZORNI ODBOR
Andrej Likar
Matej Brešar
Dragan Mihailović
ČASTNO RAZSODIŠČE
Maja Klavžar
Anton Suhadolc
Zvonko Trontelj
Člani DMFA Slovenije lahko predlagate dodatne kandidate. Predloge
hkrati s pisno privolitvijo predlaganega kandidata pošljite na društveni na-
slov najkasneje do 26. novembra 2020.
Dragan Mihailović
predsednik DMFA Slovenije
Obzornik mat. fiz. 67 (2020) 3 XI
i
i
“kolofon” — 2020/11/10 — 9:53 — page 2 — #2 i
i
i
i
i
i
OBZORNIK ZA MATEMATIKO IN FIZIKO
LJUBLJANA, MAJ 2020
Letnik 67, številka 3
ISSN 0473-7466, UDK 51+ 52 + 53
VSEBINA
Članki Strani
Problem učenja z napakami in sodobni kriptosistemi (Tilen Marc) . . . . . 81–97
Vrtenje zrcal (Nada Razpet) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98–111
Nove knjige
John Urschel in Louisa Thomas, Mind and Matter, A Life in Math
and Football (Peter Legiša) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112–117
Vesti
Aktualna vabila za mednarodne nominacije v matematiki
(Boštjan Kuzman) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118–119
Vabilo na 73. občni zbor DMFA Slovenije (Dragan Mihailović) . . . . . . . . . 119–XI
CONTENTS
Articles Pages
Problem of learning with errors and modern cryptosystems
(Tilen Marc) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81–97
Rotation of mirrors (Nada Razpet) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98–111
New books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112–117
News . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118–XI
Na naslovnici: Zrcala odpirajo pogled v nov, navidezni svet. Foto: Aleš Mohorič