P026

Zapiski nauqnyh seminarov POMI Tom 293, 2002 g.

D. . Grigor~ev KRIPTOGRAFI S OTKRYTYM KLQOM I TEORI INVARIANTOV 1. Vvedenie. Osnovna zadaqa kriptografii s otkrytym klqom sostoit v tom, qtoby postroit~ kriptosistemu, imewu sleduwie komponenty: otkryty klq ke , sekretny klq kd , izvestna vsem kodiruwa funkci fe i dekodiruwa funkci fd . Esli otpravitel~ (nazovem ego Bor) hoqet poslat~ soobwenie m adresatu (nazovem ego Allo) po publiqnomu (otkrytomu) kanalu svzi, to Bor peredaet zakodirovannoe soobwenie u = fe (m; ke). Dl dekodirovani Alla vyqislet ishodnoe soobwenie m = fd (u; kd). Predpolagaets, qto kd izvesten tol~ko Alle, v to vrem kak ke, fe izvestny vsem, funkci fd izvestna Alle (inogda ona moet byt~ izvestna vsem). Drugoe vanoe trebovanie kriptosistemy sostoit v tom, qtoby postoronnee lico (nazovem ego Vova) ne imel by vozmonosti nati m po u (ne zna kd ). Massa usili byla predprinta po postroeni kriptosistem (nekotoru literaturu mono nati v [11, 13, 17]). Odnako do nastowego momenta ne dokazano nadenosti ni odno kriptosistemy, i dokazatel~stvo nadenosti ostaets odno iz central~nyh otkrytyh problem. Vse izvestnye rezul~taty o nadenosti kasats nevozmonosti dekodirovani kako-to kriptosistemy nekotorymi fiksirovannymi sredstvami, naprimer, v ramkah kako-to logiqesko sistemy dokazatel~stv. No qto okazalos~ privlekatel~nym v razvitii kriptografii s otkrytym klqom, { to to, qto obnaruilis~ ee svzi s samymi razliqnymi razdelami matematiki. Bolee togo, vo mnogih aspektah kriptografi s otkrytym klqom igraet rol~ mosta medu matematiko i informatiko. Naibol~xee priznanie poluqili kriptosistemy, osnovannye na ideh teorii qisel, v qastnosti RSA, protokol Diffi{Hellmana ili kriptosistemy, ispol~zuwie lliptiqeskie krivye (opisanie tih kriptosistem mono nati v kni-

26

KRIPTOGRAFI S OTKRYTYM KLQOM

27

ge [17], tam e rassmatrivats kriptosistemy, privlekawie kombinatorno-algebraiqeskie NP -trudnye zadaqi). V nastowe zametke vvodts kriptosistemy, osnovannye na ideh teorii invariantov grupp. Nekotorye suwestvuwie kriptosistemy ispol~zut gruppy (nie my privodim kratki obzor nekotoryh iz nih), no, na udivlenie, ranee ne bylo izvestno priloeni ponti invarianta predstavleni gruppy, hot ono horoxo podhodit celm kriptografii. Vse e, primenenie invariantov k kriptografii natalkivaets na rd trudnoste, potomu cel~ nastowe zametki { vvesti invarianty predstavleni grupp v kriptografi s otkrytym klqom, opisat~ vozmonye kriptosistemy, a take obsudit~ problemy ih nadenosti. Itak, izloim obwu ide ispol~zovani grupp (i ih invariantov) v kriptografii s otkrytym klqom. Oboznaqim qerez E mnoestvo zakodirovannyh soobweni i pust~ gruppa G : E ! E destvuet na E . Primerami E mogut sluit~ mnoestvo slov v nekotorom alfavite, a take vektornoe prostranstvo. Krome togo, vydeleno podmnoestvo M  E ishodnyh (nezakodirovannyh) soobweni, vlwees transversal~nym po otnoxeni k orbitam destvi G, t.e. vskie dva lementa iz M prinadleat razliqnym orbitam. Destvie G primenets dl verotnostnogo kodirovani [13, 14], kotoroe bolee ffektivno v plane \sokryti informacii", neeli determinirovannoe. Itak, dl kodirovani soobweni m 2 M Bor vybiraet sluqano lement g iz gruppy G i peredaet gm 2 E po otkrytomu kanalu. Zadaqa Ally sostoit v dekodirovanii gm, qtoby uznat~ m, ispol~zu ee sekretny klq. S drugo storony, Vova ne dolen umet~ nahodit~ m po gm. Obyqno, poslednie dva svostva dostigats za sqet podhodwego vybora G. V xiroko rasprostranenno kriptosisteme kvadratiqnyh vyqetov [13, 14] vybirat qislo n = pq dl bol~xih prostyh qisel p, q (kotorye predstavlt sobo sekretny klq Ally). V kaqestve gruppy G rassmatrivaets (Zn )2, mnoestvo E = fg 2 Zn : Jn (g) = 1g, gde Jn oboznaqaet simvol kobi (po modul n). Krome togo, vybiraets kvadratiqny nevyqet a 2 E G, poloim mnoestvo M = f1; ag. Otkryty klq sostoit iz n, a. Itak, qtoby zakodirovat~ 1, Bor sluqano vybiraet g 2 Zn , kodom 1 vlets g2 2 G  E (kotory Bor peredaet po

28

D. . GRIGOR^EV

kanalu), kodom a vlets g2 a 2 E , tem samym E = G [ Ga. Zadaqa Ally po dekodirovani sostoit v tom, qtoby proverit~, vlets li peredannoe Bore zakodirovannoe soobwenie b 2 E kvadratom. Alla moet to proverit~, zna p, q i ispol~zu simvoly Leandra{kobi Jp , Jq . S drugo storony, imeets obwee mnenie, qto Vova ne moet raspoznat~, vlets li b kvadratom, ne zna p, q. Opisanna kriptosistema kvadratiqnyh vyqetov obobwaets na klass kriptosistem, nazyvaemyh gomomorfnymi. Imenno, pust~ f : E ! H { gomomorfizm grupp, kotory vlets sekretnym klqom Ally. Bolee togo, imeets toqna posledovatel~nost~ gomomorfizmov grupp

f B !s E ! H ! f1g

M  E , transversal~noe (normal~no) podgruppe G = ker(f)  E , inymi slovami, f zadaet biektivnoe sootvetstvie medu M i H . Pri tom otkrytym klqom vlets pterka B , s, E , H , M . Predpolagaets, qto s vyqislimo s polii mnoestvo

nomial~no slonost~. Opisanna shema soglasuets s privedennymi vyxe pontimi i oboznaqenimi: G destvuet (posredstvom umnoeni sleva) na E , i mnoestvo ishodnyh (nezakodirovannyh) soobweni M transversal~no k tomu destvi, priqem G zadaets zdes~ nevno kak obraz G = s(B). Qtoby zakodirovat~ soobwenie m 2 M , Bor sluqano vybiraet b 2 B i peredaet po kanalu soobwenie s(b)m 2 E . Alla dekodiruet s(b)m, primen f , opiras~ na to, qto f(s(b)m) = f(m). Vove dekodirovat~ zatrudnitel~no, ne zna f . V opisanno vyxe kriptosisteme kvadratiqnyh vyqetom imeem H = Z2, B = E , s(b) = b2, i f vlets pimorfizmom kvadratiqnogo vyqeta. V [9, 33] byl postavlen vopros: dl kakih grupp H mogut byt~ postroeny gomomorfnye kriptosistemy (bolee obwo, mono li rassmatrivat~ gomomorfizmy kolec vmesto grupp)? Dl nekotoryh abelevyh grupp H gomomorfnye kriptosistemy byli postroeny v [4, 23{25, 27]. Dl nekotoryh didral~nyh grupp H gomomorfnye kriptosistemy predloeny v [28]. V [15] gomomorfnye kriptosistemy opisany dl proizvol~no razreximo gruppy H . Imeets mnogo rabot o kriptosistemah nad lliptiqeskimi krivymi (sm., naprimer, [17, 18]).

KRIPTOGRAFI S OTKRYTYM KLQOM

29

Obwe qerto vseh upomnutyh vyxe gomomorfnyh kriptosistem vlets to, qto dekodirovanie v nih opiraets na znanie sekretno pary qisel p, q. V nastowe zametke predlagaets drugo podhod k dekodirovani (i kodirovani), osnovanny na invariantah W : E ! F , gde E { vektornoe prostranstvo nad polem F . Inymi slovami, W postonno na orbitah destvi gruppy G. Alla moet dekodirovat~ soobwenie gm putem vyqisleni w(gm) = w(m) v predpoloenii, qto W prinimaet razliqnye znaqeni na ishodnyh (nezakodirovannyh) soobwenih iz M . Teori invariantov (sm., naprimer, [7, 30, 31]) razvita, glavnym obrazom, v situacii, kogda G : E ! F { linenoe predstavlenie, t.e. E { n-mernoe vektornoe prostranstvo, G  GL (E) { podgruppa matric nad polem F , invariant w 2 F[X1; : : : ; Xn] { mnogoqlen ot n peremennyh nad F . No, navernoe, bylo by polezno take izuqit~ i drugie destvi grupp i ih invarianty. Prinima vo vnimanie, qto invarianty w izvestny vno i mogut byt~ vyqisleny lix~ dl nebol~xogo qisla beskoneqnyh seri linenyh predstavleni G  GL(E) ([31]), my predlagaem \zaprtat~" G, rassmatriva ee soprenie a 1Ga  GL(E) dl matricy a 2 GL (E), kotora vlets sekretnym klqom Ally. Togda invariant e ! w(ae) sopreni a 1 Ga pozvolet Alle dekodirovat~ soobwenie a 1gam, gde a 1ga { lement gruppy a 1 Ga, sluqano vybranny Bore dl kodirovani soobweni m. Obyqno gruppa a 1Ga (sostavlwa otkryty klq vmeste s E i M  E ) zadaets semestvom matric iz GL(E), vlwihs ee obrazuwimi. Zadanie gruppy ee obrazuwimi { to dostatoqno saty sposob. V qastnosti, kada izvestna prosta gruppa imeet dve obrazuwih, krome togo, vska koneqna gruppa G zadaets ne bolee, qem log2 jGj obrazuwimi. Pri vyqislenih v gruppe G, zadanno semestvom obrazuwih, ne obzatel~no predpolagat~, qto G koneqna (to tak, v qastnosti, kogda pole F koneqno), poskol~ku dl kodirovani Bor sluqano vybiraet nekotoroe proizvedenie obrazuwih gruppy a 1Ga. Vsledstvie togo, tak e mono rassmatrivat~ semestvo obrazuwih, porodawih kaku-to podgruppu gruppy a 1 Ga. V posleduwih paragrafah my opixem klass kriptosistem s otkrytym klqom, osnovannyh na invariantah grupp, a take obsudim problemu ih nadenosti, no snaqala my zakonqim vve-

30

D. . GRIGOR^EV

denie obzorom ewe dvuh semestv kriptografiqeskih konstrukci, kotorye ispol~zut gruppy. Drugo zadaqe kriptografii, nardu s postroeniem kriptosistem s otkrytym klqom, vlets protokol soglaxeni o klqe, (sm., naprimer, [11, 13, 17]). Teper~ Alla i Bor hott dogovorit~s ob obwem klqe, obwas~ po otkrytomu kanalu. Rasprostranenny podhod k to zadaqe sostoit v tom, qto Alla i Bor nezavisimo vybirat sekretnye kommutiruwie operatory fA , fB : E ! E , sootvetstvenno, i krome togo, (publiqno) nekotoroe e 2 E . Dalee, Alla peredaet po kanalu fA (e), Bor peredaet fB (e), i ih obwim klqom vlets fA (fB (e)) = fB (fA (e)). V pervom iz protokolov soglaxeni Diffi{Hellmana (sm. [13, 17]) v kaqestve kommutiruwih operatorov vybiralis~ fA (e) = ea , fB (e) = eb (modp) dl celyh a, b. Takim obrazom, zadaqa Vovy po dekodirovani protokola Diffi{Hellmana svzana s vyqisleniem diskretnogo logarifma. Obwee mnenie sostoit v tom, qto to trudno, slonost~ diskretnogo logarifma izuqalas~ v [6, 22]. Ukazanny obwi podhod k zadaqe postroeni protokola soglaxeni o klqe rassmatrivals v sleduwe postanovke (sm. [3, 16, 26]). Pust~ E { gruppa s paro vzaimno (polementno) kommutiruwih podgrupp EA, EB  E . Togda v kaqestve fA Alla vybiraet soprenie e ! a 1 ea dl sluqanogo a 2 EA, Bor sootvetstvenno, fB (e) = b 1eb dl b 2 EB . V [16] rol~ E igraet gruppa kos, i trudnost~ dekodirovani protokola soglaxeni svzana s trudnost~ zadaqi soprennosti v gruppe kos. V [2, 8, 10, 32] predlagaets neskol~ko kriptosistem s otkrytym klqom, opirawihs na trudnost~ problemy ravenstva slov v podhodwih gruppah. Poslednee semestvo kriptosistem s otkrytym klqom, kotoroe my upomnem, osnovyvaets na rexetkah (predstavlwih sobo diskretnye abelevy podgruppy prostranstva Rn). Perva iz takih konstrukci predloena v [1]. Pust~ L  Rn { n-merna rexetka, obladawa tem svostvom, qto ona soderit (soprennu) (n 1)-mernu podrexetku L0 , q~ linena oboloqka ravna giperploskosti H , tak qto vypolneno sleduwee S svostvo. Giperploskosti Hi , parallel~nye H , takie, qto Hi  L, i sil~no otdeleny: imenno, rasstonie medu lbo paro sosednih giperploskoste Hi, Hi+1 bol~xe nekotorogo dostatoqno

KRIPTOGRAFI S OTKRYTYM KLQOM

31

bol~xogo d. Inymi slovami, suwestvuet bazis rexetki L, sostowi iz n 1 dostatoqno korotkogo vektora (ih mnoestvo oboznaqim qerez C ) iz L0 i dostatoqno dlinnogo vektora c, imewego bol~xu proekci, ortogonal~nu H . Togda kriptosistema s otkrytym klqom iz [1] rassmatrivaet kako-libo sluqany bazis C1 rexetki L v kaqestve otkrytogo klqa, a bazis C [ fcg { v kaqestve sekretnogo klqa Ally. Ishodny bit 0 Bor kodiruet posredstvom sluqanogo vektora iz L, a bit 1 { posredstvom sluqanogo vektora iz Rn. Dl dekodirovani vektora u Alla vyqislet veliqinu

` = u; c PH (c)




c

PH (c) 2 ;

gde PH oboznaqaet ortogonal~nu proekci na giperploskost~ H . Esli qislo ` celoe (to oznaqaet, qto u prinadleit odno iz giperploskoste Hi), togda Alla moet obvit~, qto ishod-

ny bit raven 0 (v protivnom sluqae,S1). Faktiqeski, takim sposobom Alla raspoznaet lementy iz Hi, a ne iz trebuemo i S rexetki L, potomu oxibka sluqaets, kogda u 2 Hi L. Qtoby i ispravit~ tu oxibku, Bor slegka xevelit u, pri tom kada toqka iz L okruaets xarikom podhodwego radiusa r tak, qtoS by pokryt~ Hi, no, s drugo storony, ne pokryt~ vse prostrani stvo Rn. Bolee togo, xeveleni sosednih giperploskoste Hi , Hi+1 dolny byt~ sil~no otdeleny, i kak raz po to priqine bylo naloeno trebovanie na dlinny vektor c. Nakonec, Alla S dekodiruet toqki u na rasstonii r ot obedineni Hi kak 0, i v protivnom sluqae { kak 1. Vse e, oxibka moet proizoti, S kogda u leit na rasstonii ne bolee r ot obedineni Hi , i no togda bolee verotno, qto v tom sluqae Bor zakodiroval 0 (a ne 1). Takim obrazom, predpolagaema trudnost~ dekodirovani Vovo opisanno kriptosistemy s otkrytym klqom osnovyvaets na trudnosti nahodeni dlinnogo vektora v rexetke, zadanno bazisom C1 (ili, kvivalentno, nahodeni korotkogo vektora v dvostvenno rexetke), v predpoloenii, qto dlinny vektor edinstvenen v nekotorom podhodwem strogom smysle. Druga kriptosistema s otkrytym klqom, ispol~zuwa xeveleni, byla postroena v [12]. Zdes~ ishodnoe soobwenie { toqka rexetki L  Rn, i ee kodirovanie poluqaets putem ee

32

D. . GRIGOR^EV

malogo xeveleni v Rn. Togda zadaqa dekodirovani (Vovo) kriptosistemy privodit k nahodeni dl danno vewestvenno toqki bliaxego k ne vektora rexetki L. Izvestno, qto ta zadaqa NP { trudna, tak e kak i priblienie k ne s toqnost~ do postonnogo mnoitel. Qtoby sdelat~ vozmonym dekodirovanie, Alla sperva vybiraet sluqano bazis c1; : : : ; cn rexetki L special~nogo vida (imenno tako, qto veliqina Y

 det(ci )

kci k

i ne slixkom velika, bazis s takim svostvom nazyvaets \poqti ortogonal~nym"), kotory igraet rol~ sekretnogo klqa. Zatem Alla menet (s pomow~ sluqanogo unimodulrnogo preobrazovani) bazis c1 ; : : : ; cn, poluqenny bazis sluit v kaqestve otkrytogo klqa. Glavnoe nabldenie sostoit v tom, qto znanie \poqti ortogonal~nogo" bazisa pozvolet Alle nati dl dannogo vektora bliaxi vektor v L v predpoloenii, qto xevelenie bylo dostatoqno malym. Itak, v oboih upomnutyh metodah, ispol~zuwih rexetki [1, 12], ishodnoe soobwenie \zaprtano" posredstvom malogo xeveleni, to otliqaets ot naxego podhoda \zaprtyvat~" soobwenie putem sdviga na nekotory lement danno gruppy.

2. Postroenie kriptosistem s otkrytym klqom, osnovannyh na invariantah grupp.

Pust~ G  GL n (F) { predstavlenie gruppy G, priqem mono sqitat~ bez ograniqeni obwnosti, qto pole F algebraiqeski zamknuto, odnako v vyqislenih kofficienty matric iz G mogut prinadleat~ nekotoromu podpol pol F . Naprimer, kofficienty mogut leat~ v koneqnom pole. Dopustim, qto izvesten nekotory (nepostonny) invariant w ([7, 30]) predstavleni G, t.e. mnogoqlen w 2 F[X1; : : : ; Xn] tako, qto dl vskogo lementa g 2 G i vskogo vektora v 2 F n imeem w(gv) = w(v). Krome togo, fiksiruem paru nenulevyh razliqnyh vektorov v0 , v1 2 F n. Obyqno predpolagaets, qto mono porodat~ lementy iz G. Dl postroeni (verotnostno) kriptosistemy s otkrytym klqom Alla sluqano vybiraet matricu a 2 GL(F) s tem svostvom, qto w(av0) 6= w(av1 ) (oqevidno, qto poqti vska matrica a obladaet tim svostvom).

33 1 Otkryty klq: v0 , v1 i semestvo lementov vida hi = a gi a 2 GL (F), gde gi { sluqano porodennye lementy gruppy G; Sekretny klq: a; Kodirovanie: bit 0 (ili, sootvetstvenno bit 1) Bor kodiruet vektorom u = hi1


hi` v0 2 F n (sootvetstvenno, u = hi1


hi` v1 2 F n dl sluqano vybrannyh i1 ; : : : ; i`. Dekodirovanie: po dannomu vektoru u 2 F n Alla vyqislet veliqinu w(au) i proveret, ravna li ona w(av0 ) (v tom sluqae ishodnoe soobwenie ravno v0 , poskol~ku w(av0 ) = w(ahi1


hi` v0 ) = w(au)) ili ona ravna w(av1) (v tom sluqae ishodnoe soobwenie ravno v1 ). 3. O nadenosti. KRIPTOGRAFI S OTKRYTYM KLQOM

Dl dekodirovani opisanno kriptosistemy s otkrytym klqom Vova moet popytat~s postroit~ invariant w0 podgruppy H sopreni a 1 Ga (zdes~ H oboznaqaet gruppu, porodennu obrazuwimi hi ). Mono sqitat~, qto gruppa G  GL (F) (razmera ksponencial~nogo ot n ili dae beskoneqnogo) izvestna, tak e kak i invariant w. Vova moet pytat~s iskat~ invariant w0 v vide w0(v) = w(bv) dl neizvestno matricy b 2 GL n(F). Pust~ d oboznaqaet stepen~ invarianta w (kak obyqno v teorii invariantov, mono bylo by ograniqit~s rassmotreniem odnorodnyh invariantov w). Podstavl w0 v zadannye obrazuwie a 1gi a gruppy H , inymi slovami, w(bv) = w(b(a 1 gia)v) dl kadogo i (sno, qto pododet lba taka matrica b), i priravniva kofficienty pri vseh monomah ot n koordinat vektora v, Vova poluqaet sistemu polinomial~nyh uravneni stepeni d ot kofficientov   matricy b. Sledovatel~no, ta sistema soderit

n+d 1 d

uravneni (dl

kadogo i) stepeni d ot n2 neizvestnyh, vlwihs kofficientami matricy b. Destvu drugim sposobom, Vova moet iskat~ invariant 

w0,

rassmatriva ego kak mnogoqlen stepeni

d

s

n+d 1 d

neizvestnymi kofficientami, udovletvorwimi uravnenim w0(hi v) = w0(v) dl kadogo i i dl vskogo vektora v 2 F n. to daet sistemu linenyh uravneni ot neizvestnyh kofficientov (sqita v parametriqeskim vektorom).

34

D. . GRIGOR^EV

V lbom sluqae, slonost~ kadogo izdvuh opisannyh sposo bov dekodirovani zavisit ot

n+d 1 d

, potomu dl obespe-

qeni nadenosti sleduet brat~ predstavlenie gruppy G, u kotorogo otsutstvut invarianty stepeni men~xe const
n. S drugo storony, invariant w dolen byt~ vyqislim so slonost~, polinomial~no ot n (nie my privedem neskol~ko takih primerov). Zadaqa nahodeni invarianta kaets trudno i v obwe situacii malo qto P izvestno, pomimo primeneni usrednxego g (v predpoloenii, qto gruppa G koneqna), operatora jGj 1 g 2G sr. [31]. Rassmotrim ewe dva podhoda k dekodirovani kriptosistem, opisannyh v predyduwem paragrafe. Pri pervom podhode Vova pytaets nati matricu a (ili lbu drugu matricu b 2 GL n(F) taku, qto bHb 1  G). sno, qto mono predpolagat~ bez ograniqeni obwnosti, qto gruppa H soprena s samo gruppo G (a ne s kako-to ee podgruppo), vybira v kaqestve gi obrazuwie gruppy G (sluqano vybrannoe dostatoqno bol~xoe semestvo gi porodaet G s bol~xo verotnost~). Problema proverki suwestvovani matricy b (i ee nahodeni, esli ona suwestvuet) tako, qto bHb 1 = G, nazyvaets problemo soprennosti matriqnyh grupp. K to probleme mono svesti problemy soprennosti grupp perestanovok, kak soobwil avtoru . Laks [21]. V svo oqered~, v [20] sformulirovana gipoteza o trudnosti problemy soprennosti grupp perestanovok. Krome togo, k probleme soprennosti grupp perestanovok svodits problema izomorfizma grafov [20]. Itak, pervy podhod k dekodirovani kriptosistem s otkrytym klqom, opisannyh v predyduwem paragrafe, privodit Vovu, v qastnosti, k probleme izomorfizma grafov. Pri vtorom podhode Vova pytaets nati matricu h 2 H taku, qto hu = v0 (ili, sootvetstvenno, hu = v1). ta problema nazyvaets problemo o perenose vektorov, i v [20] sformulirovana gipoteza o ee trudnosti v qastnom sluqae, kogda H { gruppa perestanovok. Analogiqno, k ne svodits problema izomorfizma grafov. Upomnem, qto qastny sluqa problemy o perenose vektorov, kogda (mnoestvo zakodirovannyh soobweni) F 4 rassmatriva-

KRIPTOGRAFI S OTKRYTYM KLQOM

35

ets kak prostranstvo 2  2 matric, i gruppa H = SL 2(Z)  SL 2 (Z) destvuet na F 4 po pravilu v ! h1vh2 , gde (h1 ; h2) 2 H , vlets NP -trudnym dl slonosti v srednem [5]. V to svzi zametim, qto dokazatel~stvo trudnosti dekodirovani kriptosistemy s otkrytym klqom otnositel~no bolee sil~nogo ponti slonosti v srednem bylo by bolee interesno, qem otnositel~no obyqno slonosti v hudxem sluqae (sr. [19]). Itak, oba podhoda k dekodirovani opisannyh vyxe kriptosistem s otkrytym klqom svzany s problemo izomorfizma grafov. No, koneqno, trudnost~ dokazatel~stva sved&eni problemy izomorfizma grafov k dekodirovani kriptosistem leit, v qastnosti, v neobhodimosti postroeni gruppy G i ee predstavleni, takih, qto problema izomorfizma grafov mogla by byt~ svedena k problemam soprennosti i perenosa vektorov dl G. Bylo by interesno vysnit~, svodits li destvitel~no problema izomorfizma grafov k dekodirovani opisannyh vyxe kriptosistem. Upomnem take, qto vygldwa vnexne pohoim obrazom zadaqa kvivalentnosti (soprennosti) predstavleni gruppovyh algebr F[G], F[H] (v otliqie ot soprennosti samih grupp), drugimi slovami, nahodenie matricy a 2 GL n (F) tako, qto a 1 F[H]a = F[G], moet byt~ ffektivno rexena nad algebraiqeski zamknutym polem F [29], osnovyvas~ na strukturnyh teoremah Xura i Vedderberna. Oqevidnoe zameqanie sostoit v tom, qto dl obespeqeni bol~xe nadenosti kriptosistem s otkrytym klqom bylo by razumno qasto ment~ sekretnye i (tem samym) otkrytye klqi a i a 1 gi a . Privedem teper~ neskol~ko prostyh primerov kriptosistem s otkrytym klqom, ispol~zuwih invarianty klassiqeskih grupp [7, 30].

Primer 1. ([30]) V kaqestve gruppy G voz~mem podgruppu grup-

py GL n , porodennu simmetriqesko gruppo Sn perestanovok standartnogo bazisa ei , 1 6 i 6 n, a take vsemi matricami t ` takimi, qto tei = ciei , gde cm i = 1, 1 6 i 6 n, (c1 ; : : : ; cn) = 1 dl nekotoryh `jm. Togda v kaqestve invarianta w mono vzt~ stepennu summu xm +


xm n . My soznatel~no rassmatrivaem rasxirenie simmetriqesko gruppy, qtoby izbeat~ naliqie invariantov malyh stepene (sm. diskussi v naqale togo pa-

36

D. . GRIGOR^EV

ragrafa).

Primer 2. Opredelim predstavlenie special~no lineno gruppy G = SL n (F) na simmetriqeskom kvadrate S 2 F n, drugimi

slovami, na simmetriqeskih matricah (ili kvadratiqnyh formah) formulo v ! mvm| , gde m 2 G i | oboznaqaet transponirovanie. Togda v kaqestve w mono vzt~ det(v).

Primer 3. Teper~ gruppa G = GL n (F) destvuet na prmo 2 summe F 2n = F  : : :  F n 2n kopi prostranstva F n po formule m(1 ; : : : ; 2n) = (m1 ; : : : ; m2n ). Rassmotrim dva razbieni I1 [ J1 = I2 [ J2 = f1; : : : ; 2ng na n-lementnye podmnoestva jI1j = jJ1 j = jI2j = jJ2j = n. Qerez detI1 oboznaqim opredelitel~ n  n minora, sostowego iz n vektorov pi dl i 2 I1 . Togda v kaqestve

w mono vzt~ racional~ny invariant detI1 detJ1 : detI2 detJ2

V opisanno v predyduwem paragrafe kriptosisteme s otkrytym klqom my rassmatrivali polinomial~nye invarianty w, no poqti doslovno mono bylo by rassmotret~ i racional~nye invarianty w 2 F(X1 ; : : : ; Xn), s to lix~ ogovorko, razumeet2 s, qto Alla dolna vybirat~ vektory v0 , v1 2 F 2n i matricu a 2 GL 2n2 (F) takim obrazom, qtoby znaqeni w(av0 ), w(av1 ) byli opredeleny. Mono ewe postroit~ podobnye primery, ispol~zuwie prmoe, tenzornoe, simmetriqeskoe, vnexnee proizvedeni predstavleni grupp. Sostonie del v nastowee vrem v kriptografii ne pozvolet dokazyvat~ nadenost~ kriptosistem s otkrytym klqom, to obyqno vopros very v trudnost~ nekotoro podhodwe vyqislitel~no zadaqi, a take opyta (potomu imeets mnogo state po kriptografii s otkrytym klqom, vklqa nastowu, ne soderawih teorem). Naprotiv, mono oidat~ \razoqarovyvawego" dekodirovani kakih-to qastnyh kriptosistem. to ne isklqeno ni dl kako iz opisannyh, v primerah vyxe, kriptosistem s otkrytym klqom (izbega pri tom rexeni problemy izomorfizma grafov, sm. zameqanie vyxe). S drugo storony, dekodirovanie moglo by privesti, vozmono, k interesnym algoritmam v teorii predstavleni grupp. Itak, mono smotret~

KRIPTOGRAFI S OTKRYTYM KLQOM

37

na privedennye primery (a take na konstrukci iz predyduwego paragrafa v celom) lix~ kak na predloenie issledovat~ kriptosistemy s otkrytym klqom, osnovannye na teorii invariantov. Blagodarnosti. Avtor hotel by poblagodarit~ Institut Vysxih Issledovani (Franci), vo vrem prebyvani v kotorom ta rabota byla zadumana, a take L. Levina i . Laksa za interesnye obsudeni.

Literatura

1. M. Ajtai, C. Dwork, A public-key cryptosystem with worst-case/average case equivalence. | Proceedings of the 29th Annual ACM Symposium on Theory of Computing (1997), pp. 284{293. 2. I. Anshel, M. Anshel, From the Post-Markov theorem through decision problems to public-key cryptography. | Amer. Math. Monthly, 100 (1993), 835{844. 3. I. Anshel, M. Anshel, D. Goldfeld, An algebraic method for public-key cryptography. | Math. Res. Lett., 6 (1999), 287{291. 4. J. Benaloh, Dense probabilistic encryption. | First Ann. Workshop on Selected Areas in Cryptology (1994), pp. 120{128. 5. A. Blass, Y. Gurevich, Matrix transformation is complete for the average case. | SIAM J. Comput., 24 (1995), 3{29. 6. D. Coppersmith, I. Shparlinski, On polynomial approximation of the discrete logarithm and the Die-Hellman mapping. | J. Cryptology, 13 (2000), 339{360. 7. J. Dieudonne, J. Carrell, Invariant theory, Old and New. Academic Press (1971). Perevod: . D~edonne, D. Krrel, Teori invariantov, Staroe i Novoe \Mir" (1975).

8. Do Long Van, A. Jeyanthi, R. Siromony, K. Subramanian, Public key cryptosystems based on word problems. | ICOMIDC Symp. Math. of Computations, Ho Chi Minh City, April (1988). 9. J. Feigenbaum, M. Merritt, Open questions, talk abstracts, and summary of discussions. | DIMACS series in discrete mathematics and theoretical computer science, 2 (1991), 1{45. 10. M. Garzon, Y. Zalcstein, The complexity of Grigorchuk groups with application to cryptography. | Theoret. Comput. Sci., 88 (1991), 83{98. 11. O. Goldreich, Modern cryptography, probabilistic proofs and pseudorandomness. Springer (1998). 12. O. Goldreich, S. Goldwasser, S. Halevi, Public-key cryptosystems from lattice reduction problems. | Lecture Notes in Comput. Sci., 1294 (1997), 112{131. 13. S. Goldwasser, M. Bellare, http://www-cse.ucsd.edu/users/mihir/papers/gb.html (2001), Lecture Notes on Cryptography. 14. S. Goldwasser, S. Micali, Probabilistic encryption. | J. Comput. System Sci., 28 (1984), 270{299. 15. D. . Grigor~ev, I. N. Ponomarenko, O neabelevyh gomomorfnyh kriptosistemah s otkrytym klqom. | Zap. nauqn. semin POMI, 293

(2002), 39{58.

38 D. . GRIGOR^EV 16. K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J. Kang, C. Park,, New public-key cryptosystem using braid groups. | Lecture Notes in Comput. Sci., 1880 (2000), 166{183. 17. N. Koblitz, Algebraic aspects of cryptography. | Algorithms and Computation in Mathematics, 3, Springer (1998). 18. K. Koyama, U. Maurer, T. Okamoto, S. Vanstone, New public-key schemes based on elliptic curves over the ring n. | Lecture Notes in Comput. Sci., 576 (1991), 252{266. 19. L. Levin, Average case complete problems. | SIAM J. Comput., 15 (1986), 285{286. 20. E. Luks, Permutation groups and polynomial-time computations. | DIMACS Series in Discr. Math. and Theor. Comput. Sci., 11 (1993), 139{175. 21. E. Luks, Personal communication. | (2002). 22. U. Maurer, S. Wolf, Lower bounds on generic algorithms in groups. | Lecture Notes in Comput. Sci., 1403 (1998), 72{84. 23. D. Naccache, J. Stern, A new public-key cryptosystem. | Lecture Notes in Comput. Sci., 1233 (1997), 27{36. 24. D. Naccache, J. Stern, A new public-key cryptosystem based on higher residues. | Proc. 5th ACM Conference on Computer and Communication Security 1998, pp. 59{66. 25. T. Okamoto, S. Uchiyama, A New Public-Key Cryptosystem as Secure as Factoring. | Lecture Notes in Comput. Sci., 1403 (1998), 308{317. 26. S.-H. Paeng, D. Kwon, K.-C. Ha, J. H. Kim, Improved public key cryptosystem using nite non-abelian groups. | Preprint NSRI, Korea. 27. P. Paillier, Public-Key Cryptosystem Based on Composite Degree Residuosity Classes. | Lecture Notes in Comput. Sci., 1592 (1999), 223{238. 28. D. Rappe, Algebraisch homomorphe Kryptosysteme. | Diplomarbeit,Universitat Dortmund (2000). 29. L. Ronyai, Computations in associative algebras. | Groups and Computation, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 11, AMS (1993), 221{243. 30. T. Springer, Invariant theory. | Lecture Notes in Mathematics, 585, Springer (1977). Perevod: T. Springer, Teori invariantov, \Mir", (1981). 31. B. Sturmfels, Algorithms in invariant theory. | Texts and Monographs in Symbolic Computation, Springer (1993). 32. N. Wagner, M. Magyarik, A public-key cryptosystem based on the word-problem. | Lect. Notes in Comput. Sci., 196 (1985), 19{36. 33. A. Yao, How to generate and exchange secrets. | Proceedings of the 27th annual IEEE Symposium on Foundations of Computer Sciences (1986), pp. 162{167.

Z

Grigoriev D. Public-key cryptography and invariant theory. Public-key cryptosystems are suggested based on invariants of groups. We give also an overview of known cryptosystems which involve groups. IRMAR, Universite de Rennes Beaulieu, 35042, Rennes, France http://maths.univ-rennes1.fr/dima

Postupilo 15 sentbr 2002 g.