Criptosistem Bonnet-Go-Nissima

Criptosistemul Bonet-Go-Nishima este un criptosistem parțial homomorf , care este o modificare a criptosistemului Paye [1] și a criptosistemului Okamoto-Uchiyama [2] . Dezvoltat în 2005 de Dan Bonet [3] cu Yu Jin Go și Koby Nissim [4] [5] . Bazat pe grupuri finite de ordin compus și perechi biliniare pe curbe eliptice; sistemul permite evaluarea polinoamelor pătratice multivariate pe texte cifrate (de exemplu, forma normală disjunctivă de ordinul doi (2- DNF )).

Sistemul are un homomorfism aditiv (suportă adunări arbitrare și o înmulțire (urmată de adunări arbitrare) pentru datele criptate).

Algoritmul utilizat în criptosistemul BGN se bazează pe problema Burnside . [6] .

Algoritm de operare

Ca toate sistemele de criptare homomorfă, CBGN include următoarele procese: generarea cheilor, criptarea și decriptarea.

Construcția folosește câteva grupuri finite de ordine compuse care suportă o mapare biliniară. Se folosește următoarea notație:

$\mathbb {G}$ și sunt două grupuri ciclice de ordin finit . $\mathbb {G} _{1}$ ${n}$
${g}$ - generator . $\mathbb {G}$
${f)$ este o mapare biliniară . Cu alte cuvinte, pentru toți și avem . De asemenea, solicităm ca : este un generator ${f}:\mathbb {G} \times \mathbb {\mathbb {G} } \rightarrow \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}$

Spunem că este un grup biliniar dacă există un grup și o mapare biliniară definite mai sus. [7] $\mathbb {G}$ $\mathbb {G} _{1}$

Generare cheie

Generare_Key( ) : $\tau$

Având în vedere parametrul de securitate ca intrare , calculăm algoritmul pentru a obține un tuplu . Algoritmul funcționează astfel: $\tau \in \mathbb {Z} ^{+)$ $X(\tau )$ $({q}_{1}, {q}_{2},\mathbb {G} ,\mathbb {G} _{1}, {f})$
1. Să generăm două numere aleatoare de biți și și setați . $\tau$ ${q}_{1}$ ${q}_{2)$ ${n}={q}_{1}{q}_{2}\in \mathbb {Z}$
2. Să creăm un grup biliniar de ordin , unde > 3 este un număr dat care nu este divizibil cu 3: $\mathbb {G}$ ${n}$ ${n}$
  1. Găsiți cel mai mic număr natural astfel încât să fie un număr prim și . $\ell \in \mathbb {Z}$ ${p}=\ell {n}-1$ ${p=3{\bmod {4)}}$
  2. Se consideră un grup de puncte pe o curbă eliptică definită peste . Deoarece curba are puncte în . Prin urmare, grupul de puncte de pe curbă are un subgrup de ordin , pe care îl notăm cu . ${y^{2}=x^{3}+x}$ $\mathbb {F} _{p}$ ${p=3{\bmod {4)}}$ ${p}+1=\ell {n}$ $\mathbb {F} _{p}$ ${n}$ $\mathbb {G}$
  3. Fie subgrupul de ordin . Algoritmul de împerechere Weil modificat (împerecherea Weyl este o mapare biliniară, simetrică, nedegenerată [8] [4] [9] [10] ) pe o curbă produce o mapare biliniară care satisface condițiile date $\mathbb {G} _{1}$ $\mathbb {F} _{{p}^{2}}^{*}$ ${n}$ ${f}:\mathbb {G} \times \mathbb {\mathbb {G} } \rightarrow \mathbb {G} _{1)$
3. La ieșire obținem . $({q}_{1}, {q}_{2},\mathbb {G} ,\mathbb {G} _{1}, {f})$
Lasă . Să alegem două generatoare aleatorii și să definim ca . Atunci este un generator de subgrup aleatoriu de ordine . Cheie publică: . Cheie privată: . [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}}$

Criptare

Cifrare( ): $OK,M$

Presupunem că spațiul mesajului este format din numere întregi din mulțime . Pentru a cripta un mesaj folosind cheia publică , alegem un parametru aleatoriu și calculăm $\{0,T\}$ $M$ $O.K$ ${r}{\xleftarrow {R}}\{0,1,...,{n}-1\}$

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

Rezultatul este textul cifrat. [11] [7]

Decriptare

Decodificare( ): $SK,C$

Pentru a decripta textul cifrat folosind cheia privată , luați în considerare următoarea expresie $SK=q_{1}$

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

Lasă . Pentru a restabili , este suficient să calculați logaritmul discret la bază . ${\hat {g}}={g}^{q_{1}}$ ${M}$ ${C}^{q_{1))$ ${\pălărie {g)}$

Trebuie remarcat faptul că decriptarea în acest sistem necesită timp polinomial în dimensiunea spațiului de mesaje. [11] [7]

Exemple

Un exemplu despre cum funcționează algoritmul

Mai întâi alegem două numere prime diferite

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

Calculați produsul

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

În continuare, construim un grup de curbe eliptice cu ordinea , care are o hartă biliniară. Ecuația curbei eliptice ${n}$

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

care este definită peste un câmp pentru un număr prim . În acest exemplu, stabilim $\mathbb {F} _{p}$ ${p=3{\bmod {4)}}$

${p=307}$ .

Prin urmare, curba este suprasingulară cu # puncte raționale, care conține un subgrup de ordin . În grup, alegem două generatoare aleatorii ${(E(p))=p+1=308}$ $\mathbb {G}$ ${{n}=77(=308/4))$ $\mathbb {G}$

${g=[182.240]}$ , ${u=[28.262]}$

unde aceste două generatoare au ordine și calculează ${n}$

${h=u^{q_{2}}=[28.262]^{11}=[99.120]}$

unde este ordinea . Calculăm textul cifrat al mesajului ${h}$ ${\displaystyle {q_{1}=7))$

${M}{=2}$ .

Să luăm și să calculăm ${r=5}$

${C={g}^{M}{h}^{r}=[182.240]^{2}\oplus [99.120]^{5}=[256.265]}$ .

Pentru a decripta, mai întâi calculăm

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

și

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

Acum găsim logaritmul discret, sortând toate puterile după cum urmează ${\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 }$ .

Vă rugăm să rețineți că . Prin urmare, decriptarea textului cifrat este egală cu , care corespunde mesajului original. [12] ${\hat {g}}^{2}={C^{q_{1)}}$ ${2}$

Evaluare 2-DNF

Un sistem parțial homomorf permite estimarea 2 -DNF .

Intrare: Alice are o formulă 2-DNF și Bob are un set de variabile . Ambele părți ale intrării conțin o setare de securitate . $\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 face următoarele:
1. Acesta execută algoritmul Generate_Key( ) pentru a-l calcula și a-l trimite lui Alice. $\tau$ ${O}{K},{SK}$ ${O}{K}$
2. Acesta calculează și trimite Cipher( ) ${O}{K}, {a_{j)}$ pentru . ${j=1,...,n}$
Alice face următoarele:
1. Efectuează aritmetizarea prin înlocuirea „ ” cu „ ”, „ ” cu „ ”, și „ ” cu „ ”. Rețineți că acesta este un polinom de gradul 2. $\Phi (\phi)$ $\lor$ $+$ $\teren$ $\times$ ${\bar {x_{j)})$ $(1-x_{j})$ $\Phi$
2. Alice calculează o criptare pentru una aleasă aleatoriu folosind proprietățile homomorfe ale sistemului de criptare. Rezultatul este trimis lui Bob. ${r}\times \Phi ({a})$ ${r}$
Dacă Bob primește criptarea „ „, el scoate „ „; în caz contrar, scoate „ „. [13] $0$ $0$ $unu$

Proprietăți omomorfe

Sistemul este homomorf aditiv. Să fie cheia publică. Fie textele cifrate ale mesajelor, respectiv. Oricine poate crea o criptare distribuită uniform calculând produsul unui număr aleatoriu din interval . $({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}$ $\{0,1,...,{n}-1\)$

Mai important, oricine poate multiplica două mesaje criptate o dată folosind o hartă biliniară. Să definim și . Apoi comandă și comandă . În plus, pentru un parametru (necunoscut) , scriem . Să presupunem că cunoaștem două texte cifrate , . Pentru a construi criptarea produsului , alegem un număr aleatoriu și setăm . Obținem , unde este distribuit uniform în , după cum este necesar. ${g_{1}}={f}({g}, {g})$ ${h_{1}}={f}({g}, {h})$ ${g_{1)}$ ${n}$ ${h_{1)}$ ${q_{1}}$ $\alpha \in \mathbb {Z}$ ${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}} }\în \mathbb {G} _{1}$ ${{\tilde {r}}=m_{1}r_{2}+r_{2}m_{1}+\alpha q_{2}r_{1}r_{2}+r}$ $\mathbb {Z_{n}}$

Astfel, este o criptare distribuită uniform , dar numai în grup , nu în (deci este permisă o singură multiplicare). [unsprezece] ${C}$ ${m_{1}}\times {m_{2}}{\bmod {n}}$ $\mathbb {G} _{1}$ $\mathbb {G}$

Stabilitatea sistemului

Stabilitatea acestei scheme se bazează pe problema Burnside : cunoscând un element dintr-un grup de ordine compus , este imposibil să se determine dacă acesta aparține unui subgrup al ordinului . ${\displaystyle {n}={q}_{1}{q}_{2))$ ${q_{1}}$

Fie , și un tuplu creat de , unde . Luați în considerare următoarea problemă. Pentru un anumit și element , tipăriți „ „ dacă comanda este , în caz contrar tipăriți „ ”. Cu alte cuvinte, fără a cunoaște factorizarea grupului de ordine , trebuie să știm dacă un element se află într-un subgrup al grupului . Această problemă se numește problema Burnside [7] . $\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}$ $unu$ ${X}$ ${q_{1}}$ $0$ ${n}$ ${X}$ $\mathbb {G}$

Este clar că dacă putem lua în considerare ordinea grupului în criptosistem, atunci cunoaștem cheia privată și, ca urmare, sistemul este stricat. De asemenea, dacă putem calcula logaritmii discreti din grup, atunci putem calcula și . Astfel, condițiile necesare pentru securitate sunt: complexitatea factoringului și complexitatea calculării logaritmilor discreti în . [paisprezece] ${n}$ ${q_{1}}$ $\mathbb {G}$ ${q_{2}}$ ${q_{1}=n/q_{2}}$ ${n}$ $\mathbb {G}$

Note

↑ Pascal Paillier. Criptosisteme cu cheie publică bazate pe clase de reziduozitate de grad compus // Progrese în criptologie - EUROCRYPT '99 / Jacques Stern. — Springer Berlin Heidelberg, 1999. — P. 223–238 . — ISBN 9783540489108 . - doi : 10.1007/3-540-48910-x_16 . Arhivat din original pe 26 iunie 2019.
↑ Tatsuaki Okamoto, Shigenori Uchiyama. Un nou criptosistem cu cheie publică la fel de sigur ca factoring // Progrese în criptologie - EUROCRYPT'98 / Kaisa Nyberg. — Springer Berlin Heidelberg, 1998. — P. 308–318 . — ISBN 9783540697954 . - doi : 10.1007/bfb0054135 . Arhivat din original pe 29 august 2018.
↑ Mihir Bellare, Juan A. Garay, Tal Rabin. Verificare rapidă a lotului pentru exponențierea modulară și semnăturile digitale // Advances in Cryptology - EUROCRYPT'98 / Kaisa Nyberg. — Springer Berlin Heidelberg, 1998. — P. 236–250 . — ISBN 9783540697954 . - doi : 10.1007/bfb0054130 . Arhivat din original pe 7 iunie 2018.
↑ 1 2 Dan Boneh, Matt Franklin. Criptare bazată pe identitate din perechea Weil // Progrese în criptologie - CRYPTO 2001 / Joe Kilian. — Springer Berlin Heidelberg, 2001. — P. 213–229 . — ISBN 9783540446477 . - doi : 10.1007/3-540-44647-8_13 . Arhivat din original pe 22 februarie 2020.
↑ Evaluarea formulelor 2-DNF pe texte cifrate . Preluat la 20 februarie 2021. Arhivat din original la 8 august 2017. (nedefinit)
↑ Secure Computation II // Theory of cryptography : Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, SUA, 10-12 februarie 2005 : proceduri . - Berlin: Springer, 2005. - P. 326. - 1 resursă online (xii, 619 pagini) p. - ISBN 9783540305767 , 3540305769, 3540245731, 9783540245735.
↑ 1 2 3 4 5 Takuho Mitsunaga, Yoshifumi Manabe, Tatsuaki Okamoto. Protocoale eficiente de licitație sigure bazate pe criptarea Boneh-Goh-Nissim . — 22.11.2010. - T. E96A . — S. 149–163 . - doi : 10.1007/978-3-642-16825-3_11 .
↑ O.N. Vasilenko. Despre calculul perechilor Weyl și Tate // Tr. de discr. Matem .. - M . : FIZMATLIT, 2007. - T. 10. - S. 18-46.
↑ Antoine Joux. Un protocol cu o singură rundă pentru Diffie–Hellman tripartit . — 30-12-2006. - T. 17 . — S. 385–393 . - doi : 10.1007/10722028_23 .
↑ Victor Miller. Împerecherea Weil și calculul său eficient // J. Cryptology. — 01-09-2004. - T. 17 . — S. 235–261 . - doi : 10.1007/s00145-004-0315-8 .
↑ 1 2 3 4 Secure Computation II // Theory of cryptography : Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, SUA, 10-12 februarie 2005 : proceduri . - Berlin: Springer, 2005. - P. 329. - 1 resursă online (xii, 619 pagini) p. - ISBN 9783540305767 , 3540305769, 3540245731, 9783540245735.
↑ Yi, Xun (Profesor de facultate), . Criptare homomorfă și aplicații . — Cham. — 1 resursă online (xii, 126 pagini) p. - ISBN 978-3-319-12229-8 , 3-319-12229-0.
↑ Theory of cryptography: Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, SUA, 10-12 februarie 2005: proceduri . - Berlin: Springer, 2005. - P. 332. - 1 resursă online (xii, 619 pagini) p. - ISBN 9783540305767 , 3540305769, 3540245731, 9783540245735.
↑ EUROCRYPT 2010 (2010 : Riveria, Franța). Progrese în criptologie--EUROCRYPT 2010 : a 29-a Conferință Internațională Anuală privind Teoria și Aplicațiile Tehnicilor Criptografice, Riviera Franceză, 30 mai-3 iunie 2010 : lucrări . - Springer, 2010. - ISBN 9783642131905 , 3642131905.

Literatură

S. M. Vladimirov, E. M. Gabidulin, A. I. Kolybelnikov, A. S. Kshevetsky. Metode criptografice de protecție a informațiilor. - Ed. a II-a. - MIPT, 2016. - S. 225-257. — 266 p. - ISBN 978-5-7417-0615-2 .

Link -uri

S. I. Adian. Problema Burnside și întrebările conexe // Uspekhi Mat. - 2010. - Septembrie ( vol. 65 , numărul 5 ).

Criptosisteme cu cheie publică

Algoritmi

Factorizarea numerelor întregi	Criptosistemul Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Pupa paye Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Logaritm discret	BLS Cramer - Shoup Protocolul Diffie-Hellman DSA ECDH Curba25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Schimb de chei criptate Schema lui ElGamal schema de semnătură MQV Schema Schnorr VORBIȚI SRP STS
Criptografia pe zăbrele	NTRUEncrypt NTRUSign Schimb de chei bazat pe învățare cu erori Antrenament bazat pe semnătură cu erori în ring FERICIRE Speranța nouă
Alte	AE CEILIDH EPOC Ecuații de câmp ascunse IES Semnătura lui Lampport McEliece Criptosistem de rucsac Merkle-Hellman Criptosistem de rucsac Naccache–Stern Protocol în trei etape XTR

Teorie

Logaritm discret pe o curbă eliptică
Criptografia eliptică
Criptografia bazată pe hash
Criptografia necomutativă
Problema RSA
Funcție unidirecțională cu intrare secretă

Standarde

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Criptografie post cuantică

Subiecte

Semnatura electronica
OAEP
Amprenta
PKI
rețea de încredere
Dimensiunea cheii
Criptografia bazată pe identitate
Criptografia post-cuantică
Card OpenPGP