Bonnet-Go-Nissima kriptorendszer

A Bonet-Go-Nishima kriptorendszer egy részben homomorf kriptorendszer , amely a Paye kriptorendszer [1] és az Okamoto-Uchiyama kriptorendszer [2] módosítása . 2005-ben fejlesztette ki Dan Bonet [3] Yu Jin Go- val és Koby Nissim -mel [4] [5] . Összetett sorrendű véges csoportok és elliptikus görbék bilineáris párosításai alapján; a rendszer lehetővé teszi többváltozós másodfokú polinomok becslését rejtjelezett szövegeken ( például másodrendű diszjunktív normálforma (2-DNF )).

A rendszer additív homomorfizmussal rendelkezik (támogatja az önkényes összeadásokat és egy szorzást (amit tetszőleges összeadás követ) a titkosított adatokhoz).

A BGN titkosítási rendszerben használt algoritmus a Burnside problémán alapul . [6] .

Műveleti algoritmus

Mint minden homomorf titkosítási rendszer, a CBGN is a következő folyamatokat tartalmazza: Kulcsgenerálás, titkosítás és visszafejtés.

A konstrukció néhány véges összetett sorrendcsoportot használ, amelyek támogatják a bilineáris leképezést. A következő jelölést használják:

$\mathbb {G}$ és két véges rendű ciklikus csoport . $\mathbb {G} _{1}$ ${n}$
${g}$ - generátor . $\mathbb {G}$
${f}$ egy bilineáris leképezés . Más szóval, mindenkinek és nekünk . Azt is megköveteljük, hogy: egy generátor ${\displaystyle {f}:\mathbb {G} \times \mathbb {\mathbb {G} } \jobbra \mathbb {G} _{1))$ ${u},{v}\in \mathbb {G}$ ${a},{b}\in \mathbb {Z}$ ${f}({u}^{a},{v}^{b})={f}({u},{v})^{{a}{b))$ ${f}({g},{g})$ $\mathbb {G} _{1}$

Azt mondjuk, hogy bilineáris csoport, ha létezik egy csoport és egy fent meghatározott bilineáris leképezés. [7] $\mathbb {G}$ $\mathbb {G} _{1}$

Kulcsgenerálás

Generate_Key( ) : $\tau$

Ha a biztonsági paramétert bemenetként adjuk meg , kiszámítjuk az algoritmust , hogy egy tuple - t kapjunk . Az algoritmus így működik: ${\displaystyle \tau \in \mathbb {Z} ^{+))$ $X(\tau )$ $({q}_{1},{q}_{2},\mathbb {G} ,\mathbb {G} _{1},{f})$
1. Generáljunk két véletlenszerű bites számot és és állítsuk be . $\tau$ ${q}_{1}$ ${\displaystyle {q}_{2))$ ${n}={q}_{1}{q}_{2}\in \mathbb {Z}$
2. Hozzunk létre egy bilineáris sorrendű csoportot , ahol > 3 egy adott szám, amely nem osztható 3-mal: $\mathbb {G}$ ${n}$ ${n}$
  1. Keresse meg a legkisebb természetes számot , amely egy prímszám és . $\ell \in \mathbb {Z}$ ${p}=\ell {n}-1$ ${\displaystyle {p=3{\bmod {4))))$
  2. Tekintsünk egy pontcsoportot a felett meghatározott elliptikus görbén . Mivel a görbe pontokat tartalmaz . Ezért a görbe pontcsoportjának van egy rendű alcsoportja , amelyet -vel jelölünk . ${y^{2}=x^{3}+x}$ $\mathbb {F} _{p}$ ${\displaystyle {p=3{\bmod {4))))$ ${p}+1=\ell {n}$ $\mathbb {F} _{p}$ ${n}$ $\mathbb {G}$
  3. Legyen az alcsoport sorrendben . A módosított Weil párosítási algoritmus (a Weyl párosítás egy bilineáris, ferde szimmetrikus, nem degenerált leképezés [8] [4] [9] [10] ) egy görbén az adott feltételeket kielégítő bilineáris leképezést állít elő. $\mathbb {G} _{1}$ $\mathbb {F} _{{p}^{2}}^{*}$ ${n}$ ${\displaystyle {f}:\mathbb {G} \times \mathbb {\mathbb {G} } \jobbra \mathbb {G} _{1))$
3. A kimeneten azt kapjuk, hogy . $({q}_{1},{q}_{2},\mathbb {G} ,\mathbb {G} _{1},{f})$
Hadd . Válasszunk ki két véletlen generátort , és definiáljuk úgy, mint . Ekkor ez egy véletlenszerű sorrendű alcsoportgenerátor . Nyilvános kulcs: . Privát kulcs: . [11] [7] ${n}={q}_{1}\times {q}_{2}$ ${g},{u}{\xleftarrow {R}}\mathbb {G}$ ${h}$ ${h}={u}^{q_{2))$ ${h}$ $\mathbb {G}$ ${q_{1}}$ ${O}{K}=({n},\mathbb {G},\mathbb {G_{1}},{f},{g},{h})$ ${S}{K}={q_{1}}$

Titkosítás

Rejtjel( ): $OK,M$

Feltételezzük, hogy az üzenettér a halmazban lévő egész számokból áll . Egy üzenet nyilvános kulccsal történő titkosításához kiválasztunk egy véletlenszerű paramétert , és kiszámítjuk $\{0,T\}$ $M$ $rendben$ ${r}{\xleftarrow {R}}\{0,1,...,{n}-1\}$

${C}={g}^{M}{h}^{r}\in \mathbb {G}$ .

Az eredmény a titkosított szöveg. [11] [7]

Dekódolás

Dekódolás( ): $SK,C$

A titkosított szöveg privát kulccsal történő visszafejtéséhez vegye figyelembe a következő kifejezést $SK=q_{1}$

${C}^{q_{1}}=({g}^{M}{h}^{r})^{q_{1}}=({g}^{q_{1}}) ^{M}$ .

Hadd . A visszaállításhoz elég kiszámítani a diszkrét logaritmust az alaphoz . ${\hat {g}}={g}^{q_{1}}$ ${M}$ ${C}^{q_{1))$ ${\hat {g))$

Meg kell jegyezni, hogy ebben a rendszerben a visszafejtés az üzenettér méretében polinomiális időt vesz igénybe. [11] [7]

Példák

Példa az algoritmus működésére

Először két különböző prímszámot választunk

${{q}_{1}=7}$ ${{q}_{2}=11}$ .

Számítsa ki a terméket

${\displaystyle {{n}={q}_{1}{q}_{2}=7\times 11=77))$ .

Ezt követően készítünk elliptikus görbék egy csoportját sorrendben , amelynek bilineáris leképezése van. Elliptikus görbe egyenlet ${n}$

${y^{2}=x^{3}+x}$

amely egy mező felett van definiálva valamilyen prímszámhoz . Ebben a példában beállítjuk $\mathbb {F} _{p}$ ${\displaystyle {p=3{\bmod {4))))$

${p=307}$ .

Ezért a görbe szuperszinguláris # racionális ponttal, amely a sorrend egy alcsoportját tartalmazza . A csoportban két véletlen generátort választunk ${(E(p))=p+1=308}$ $\mathbb {G}$ ${\displaystyle {{n}=77(=308/4)))$ $\mathbb {G}$

${g=[182 240]}$ , ${u=[28,262]}$

ahol ennek a két generátornak a sorrendje és a számítás ${n}$

${h=u^{q_{2}}=[28 262]^{11}=[99 120]}$

hol a rend . Kiszámoljuk az üzenet titkosított szövegét ${h}$ ${\displaystyle {q_{1}=7))$

${M}[=2}$ .

Vegyük és számoljuk ${r=5}$

${C={g}^{M}{h}^{r}=[182,240]^{2}\oplus [99,120]^{5}=[256,265]}$ .

A visszafejtéshez először kiszámítjuk

${\hat {g}}={g^{q_{1}}=[182,240]^{7}=[146,60]}$

és

${C}^{q_{1}}=({g}^{M}{h}^{r})^{q_{1}}=({g}^{q_{1}}) ^{M}={[256 265]^{7}=[299 44]}$ .

Most megtaláljuk a diszkrét logaritmust, a következőképpen rendezve az összes hatványt ${\hat {g}}={g}^{q_{1}}$

${\hat {g}}^{1}={[146,60]}$

${\hat {g}}^{2}={[299,44]}$

${\hat {g}}^{3}={[272 206]}$

${\hat {g}}^{4}={[191 151]}$

${\hat {g}}^{5}={[79 171]}$

${\hat {g}}^{6}={[79 136]}$

${\hat {g}}^{7}={[191 156]}$

${\hat {g}}^{8}={[272 101]}$

${\hat {g}}^{9}={[299 263]}$

${\hat {g}}^{10}={[146 247]}$

${\hat {g}}^{11}={\infty }$ .

Kérjük, vegye figyelembe, hogy . Ezért a rejtjelezett szöveg visszafejtése megegyezik a -val , ami megfelel az eredeti üzenetnek. [12] ${\displaystyle {\hat {g}}^{2}={C^{q_{1))))$ ${2}$

2-DNF kiértékelés

Egy részlegesen homomorf rendszer lehetővé teszi a 2 -DNF becslését .

Bemenet: Alice-nek van egy 2-DNF-képlete , Bob-nak pedig egy sor változója van . A bemenet mindkét oldalán biztonsági beállítás található . $\phi (x_{1},...,x_{n})=\lor _{i=1}^{k}(l_{i,1}\land l_{i,2})$ ${a=a_{1},...,a_{n}\in \{0,1\}^{n))$ $\tau$

Bob a következőket teszi:
1. A Generate_Key( ) algoritmust végrehajtva kiszámítja és elküldi Alice-nek. $\tau$ ${O}{K},{SK}$ ${O}{K}$
2. Kiszámolja és elküldi a Cipher( ) ${O}{K},{a_{j))$ függvényt . ${j=1,...,n}$
Alice a következőket teszi:
1. Az aritmetizálást úgy hajtja végre, hogy a „ ” helyére cseréli a „ ” karaktert, a „ ” helyére a „ ” és a „ ” helyére „ ”. Vegye figyelembe, hogy ez egy 2. fokú polinom. $\Phi (\phi )$ $\lor$ $+$ $\föld$ $\szor$ ${\displaystyle {\bar {x_{j))))$ $(1-x_{j})$ $\Phi$
2. Alice kiszámítja a titkosítást egy véletlenszerűen kiválasztott titkosításhoz a titkosítási rendszer homomorf tulajdonságait felhasználva. Az eredményt elküldjük Bobnak. ${r}\times \Phi ({a})$ ${r}$
Ha Bob megkapja a " " titkosítást, a következőt adja ki: " "; ellenkező esetben " " kimenetet ad ki. [13] $0$ $0$ $egy$

Homomorf tulajdonságok

A rendszer additívan homomorf. Legyen a nyilvános kulcs. Legyen az üzenetek titkosított szövege, ill. Bárki létrehozhat egyenletes eloszlású titkosítást a tartományban lévő véletlenszám szorzatának kiszámításával . $({n},\mathbb {G} ,\mathbb {G_{1)) ,{f},{g},{h})$ ${C_{1}},{C_{2}}\in \mathbb {G} _{1}$ ${m_{1}},{m_{2}}\in \{0,1\}$ ${m_{1}}+{m_{2}}{\bmod {n}}$ ${C}={C_{1}}{C_{2}}{h}^{r}$ ${r}$ ${\displaystyle \{0,1,...,{n}-1\))$

Ennél is fontosabb, hogy a bilineáris leképezés segítségével bárki megsokszorozhat két titkosított üzenetet. Határozzuk meg és . Aztán rendelni , és rendelni . Ezen kívül néhány (ismeretlen) paraméter esetén a -t írjuk . Tegyük fel, hogy ismerünk két rejtjelezett szöveget , . A termék titkosításának elkészítéséhez kiválasztunk egy véletlen számot és beállítjuk . Azt kapjuk , ahol szükség szerint egyenletesen oszlik el . ${g_{1}}={f}({g},{g})$ ${h_{1}}={f}({g},{h})$ ${g_{1))$ ${n}$ ${h_{1))$ ${q_{1}}$ $\alpha \in \mathbb {Z}$ ${\displaystyle {h}={g}^{\alpha {q_{2))))$ ${C_{1}}={g}^{m_{1}}{h}^{r_{1}}\in \mathbb {G}$ ${C_{2}}={g}^{m_{2}}{h}^{r_{2}}\in \mathbb {G}$ ${m_{1}}\times {m_{2}}{\bmod {n}}$ ${r}\in \mathbb {Z_{n}}$ ${C}={f}({C_{1}},{C_{2}}){h_{1}^{r}}\in \mathbb {G} _{1}$ ${C=f(C_{1},C_{2})h_{1}^{r}=f(g^{m_{1}}h^{r_{1}},g^{m_ {2}}h^{r_{2}})h_{1}^{r}=g^{m_{1}m_{2}}h^{m_{1}r_{2}+r_{2} m_{1}+\alpha q_{2}r_{1}r_{2}+r}=g_{1}^{m_{1}m_{2}}h_{1}^{\tilde {r}} }\in \mathbb {G} _{1}$ ${{\tilde {r}}=m_{1}r_{2}+r_{2}m_{1}+\alpha q_{2}r_{1}r_{2}+r}$ $\mathbb {Z_{n}}$

Így egy egyenletes eloszlású titkosítás van , de csak a csoportban , nem pedig (tehát csak egy szorzás megengedett). [tizenegy] ${C}$ ${m_{1}}\times {m_{2}}{\bmod {n}}$ $\mathbb {G} _{1}$ $\mathbb {G}$

Rendszerstabilitás

Ennek a sémának a stabilitása a Burnside-problémán alapul : egy összetett rendcsoport elemének ismeretében nem lehet megállapítani, hogy az a rend valamelyik alcsoportjába tartozik-e . ${\displaystyle {n}={q}_{1}{q}_{2))$ ${q_{1}}$

Legyen , és egy sor, amelyet a , ahol . Vegye figyelembe a következő problémát. Adott és elem esetén nyomtassa ki a " " parancsot , ha a sorrend megegyezik a következővel , ellenkező esetben nyomtatja ki " " . Más szóval, anélkül, hogy ismernénk a sorrendi csoport faktorizálását, tudnia kell, hogy egy elem a csoport alcsoportjában van-e . Ezt a problémát Burnside problémának [7] nevezik . ${\displaystyle \tau \in \mathbb {Z} ^{+))$ $({q}_{1},{q}_{2},\mathbb {G} ,\mathbb {G} _{1},{f})$ $x$ ${\displaystyle {n}={q}_{1}{q}_{2))$ $({n},\mathbb {G} ,\mathbb {G} _{1}, {f})$ ${x}\in \mathbb {G}$ $egy$ ${x}$ ${q_{1}}$ $0$ ${n}$ ${x}$ $\mathbb {G}$

Nyilvánvaló, hogy ha figyelembe tudjuk venni a kriptorendszerben a csoportsorrendet, akkor ismerjük a privát kulcsot , és ennek eredményeként a rendszer tönkremegy. Továbbá, ha ki tudjuk számítani a csoport diszkrét logaritmusait, akkor kiszámíthatjuk és . A biztonsághoz tehát a szükséges feltételek a következők: a faktoring bonyolultsága és a diszkrét logaritmusok számításának bonyolultsága -ben . [tizennégy] ${n}$ ${q_{1}}$ $\mathbb {G}$ ${q_{2}}$ ${q_{1}=n/q_{2}}$ ${n}$ $\mathbb {G}$

Jegyzetek

↑ Pascal Paillier. Nyilvános kulcsú kriptorendszerek összetett fokozatú maradványsági osztályokon alapulva // Advances in Cryptology - EUROCRYPT '99 / Jacques Stern. - Springer Berlin Heidelberg, 1999. - P. 223-238 . — ISBN 9783540489108 . - doi : 10.1007/3-540-48910-x_16 . Archiválva az eredetiből 2019. június 26-án.
↑ Tatsuaki Okamoto, Shigenori Uchiyama. Egy új, nyilvános kulcsú kriptorendszer, ami olyan biztonságos, mint a faktoring // Advances in Cryptology - EUROCRYPT'98 / Kaisa Nyberg. - Springer Berlin Heidelberg, 1998. - P. 308-318 . — ISBN 9783540697954 . - doi : 10.1007/bfb0054135 . Az eredetiből archiválva : 2018. augusztus 29.
↑ Mihir Bellare, Juan A. Garay, Tal Rabin. Gyors kötegellenőrzés moduláris hatványozáshoz és digitális aláírásokhoz // Advances in Cryptology - EUROCRYPT'98 / Kaisa Nyberg. - Springer Berlin Heidelberg, 1998. - P. 236-250 . — ISBN 9783540697954 . - doi : 10.1007/bfb0054130 . Archiválva az eredetiből 2018. június 7-én.
↑ 1 2 Dan Boneh, Matt Franklin. Identitás alapú titkosítás a Weil párosításból // A kriptológia fejlődése – CRYPTO 2001 / Joe Kilian. - Springer Berlin Heidelberg, 2001. - P. 213-229 . — ISBN 9783540446477 . - doi : 10.1007/3-540-44647-8_13 . Archiválva az eredetiből: 2020. február 22.
↑ 2-DNF képletek kiértékelése titkosított szövegeken . Letöltve: 2021. február 20. Az eredetiből archiválva : 2017. augusztus 8.. (határozatlan)
↑ Secure Computation II // A kriptográfia elmélete : Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, 2005. február 10-12. : közlemények . - Berlin: Springer, 2005. - P. 326. - 1 online forrás (xii, 619 oldal) p. - ISBN 9783540305767 , 3540305769, 3540245731, 9783540245735.
↑ 1 2 3 4 5 Takuho Mitsunaga, Yoshifumi Manabe, Tatsuaki Okamoto. Hatékony biztonságos aukciós protokollok a Boneh-Goh-Nissim titkosításon alapulnak . — 2010-11-22. - T. E96A . – S. 149–163 . - doi : 10.1007/978-3-642-16825-3_11 .
↑ O.N. Vaszilenko. A Weyl és Tate párosítások kiszámításáról // Tr. a diszkr. Matem .. - M . : FIZMATLIT, 2007. - T. 10. - S. 18-46.
↑ Antoine Joux. Egyfordulós jegyzőkönyv a háromoldalú Diffie–Hellman számára . — 2006-12-30. - T. 17 . – S. 385–393 . - doi : 10.1007/10722028_23 .
↑ Victor Miller. A Weil-párosítás és annak hatékony számítása // J. Cryptology. — 2004-09-01. - T. 17 . – S. 235–261 . - doi : 10.1007/s00145-004-0315-8 .
↑ 1 2 3 4 Secure Computation II // A kriptográfia elmélete : Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, 2005. február 10-12. : közlemények . - Berlin: Springer, 2005. - P. 329. - 1 online forrás (xii, 619 oldal) p. - ISBN 9783540305767 , 3540305769, 3540245731, 9783540245735.
↑ Yi, Xun (főiskolai tanár), . Homomorf titkosítás és alkalmazások . – Cham. — 1 online forrás (xii, 126 oldal) p. - ISBN 978-3-319-12229-8 , 3-319-12229-0.
↑ A kriptográfia elmélete : Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, 2005. február 10-12.: kiadvány . - Berlin: Springer, 2005. - P. 332. - 1 online forrás (xii, 619 oldal) p. - ISBN 9783540305767 , 3540305769, 3540245731, 9783540245735.
↑ EUROCRYPT 2010 (2010: Riveria, Franciaország). Fejlődés a kriptológiában – EUROCRYPT 2010: 29. éves nemzetközi konferencia a kriptográfiai technikák elméletéről és alkalmazásairól, Francia Riviéra, 2010. május 30-június 3.: előadások . - Springer, 2010. - ISBN 9783642131905 , 3642131905.

Irodalom

S. M. Vladimirov, E. M. Gabidulin, A. I. Kolybelnikov, A. S. Kshevetsky. Az információvédelem kriptográfiai módszerei. - 2. kiadás - MIPT, 2016. - S. 225-257. — 266 p. - ISBN 978-5-7417-0615-2 .

Linkek

S. I. Adian. A Burnside probléma és a kapcsolódó kérdések // Uspekhi Mat. - 2010. - szeptember ( 65. évf. , 5. szám ).

Nyilvános kulcsú kriptorendszerek

Algoritmusok

Egész számok faktorizálása	Benalo kriptorendszer Bluma – Goldwasser Cayley Purser Damgorda – Eureka GMR Goldwasser – Micali Nakasha – Stern paye Rabin RSA Okamoto – Uchiyama Schmidt-Szamoa
Diszkrét logaritmus	BLS Cramer – Shoup Diffie-Hellman protokoll DSA ECDH Görbe 25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Titkosított kulcscsere ElGamal séma aláírási séma MQV Schnorr-séma SPEKE SRP STS
Kriptográfia rácsokon	NTRUEncrypt NTRUSign Tanulás alapú kulcscsere hibákkal Aláírás alapú edzés hibákkal a ringben BOLDOGSÁG Új remény
Egyéb	AE CEILIDH EPOC Rejtett mező egyenletek IES Lamport aláírása McEliece Merkle-Hellman háti kriptorendszer Naccache–Stern háti kriptorendszer Három lépéses protokoll XTR

Elmélet

Szabványok

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Posztkvantum kriptográfia

Témák

Elektronikus aláírás
OAEP
Ujjlenyomat
PKI
a bizalom hálója
Kulcsméret
Identitás alapú kriptográfia
Posztkvantum kriptográfia
OpenPGP kártya