Bonnet-Go-Nissima kryptosystem

Bonet-Go-Nishima-kryptosystemet er et delvist homomorft kryptosystem , som er en modifikation af Paye-kryptosystemet [1] og Okamoto-Uchiyama-kryptosystemet [2] . Udviklet i 2005 af Dan Bonet [3] med Yu Jin Go og Koby Nissim [4] [5] . Baseret på endelige grupper af sammensat orden og bilineære parringer på elliptiske kurver; systemet tillader evaluering af multivariate kvadratiske polynomier på chiffertekster (for eksempel disjunktiv normalform af anden orden (2 -DNF )).

Systemet har en additiv homomorfi (understøtter vilkårlige additioner og én multiplikation (efterfulgt af vilkårlige tilføjelser) for krypterede data).

Algoritmen, der bruges i BGN-kryptosystemet, er baseret på Burnside-problemet . [6] .

Operationsalgoritme

Som alle homomorfe krypteringssystemer inkluderer CBGN følgende processer: Nøglegenerering, kryptering og dekryptering.

Konstruktionen bruger nogle endelige sammensatte ordensgrupper, der understøtter en bilineær kortlægning. Følgende notation bruges:

$\mathbb {G}$ og er to cykliske grupper af endelig orden . $\mathbb {G} _{1}$ ${n}$
${g}$ - generator . $\mathbb {G}$
${f}$ er en bilineær kortlægning . Med andre ord, for alle og vi har . Vi kræver også, at : er en generator ${\displaystyle {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}$

Vi siger, at det er en bilineær gruppe, hvis der findes en gruppe og en bilineær kortlægning defineret ovenfor. [7] $\mathbb {G}$ $\mathbb {G} _{1}$

Nøglegenerering

Generer_nøgle( ) : $\tau$

Givet sikkerhedsparameteren som input , beregner vi algoritmen for at få en tupel . Algoritmen fungerer således: ${\displaystyle \tau \in \mathbb {Z} ^{+))$ $X(\tau )$ $({q}_{1},{q}_{2},\mathbb {G},\mathbb {G} _{1},{f})$
1. Lad os generere to tilfældige bit-tal og og sætte . $\tau$ ${q}_{1}$ ${q}_{2}$ ${n}={q}_{1}{q}_{2}\in \mathbb {Z}$
2. Lad os oprette en bilineær rækkefølge , hvor > 3 er et givet tal, der ikke er deleligt med 3: $\mathbb {G}$ ${n}$ ${n}$
  1. Find det mindste naturlige tal som er et primtal og . $\ell \in \mathbb {Z}$ ${p}=\ell {n}-1$ ${\displaystyle {p=3{\bmod {4))))$
  2. Overvej en gruppe punkter på en elliptisk kurve defineret over . Da kurven har punkter i . Derfor har gruppen af punkter på kurven en undergruppe af orden , som vi betegner med . ${y^{2}=x^{3}+x}$ $\mathbb {F} _{p}$ ${\displaystyle {p=3{\bmod {4))))$ ${p}+1=\ell {n}$ $\mathbb {F} _{p}$ ${n}$ $\mathbb {G}$
  3. Lad undergruppen være i orden . Den modificerede Weil-parringsalgoritme (Weyl-parring er en bilineær, skæv-symmetrisk, ikke-degenereret kortlægning [8] [4] [9] [10] ) på en kurve producerer en bilineær kortlægning , der opfylder de givne betingelser $\mathbb {G} _{1}$ $\mathbb {F} _{{p}^{2}}^{*}$ ${n}$ ${\displaystyle {f}:\mathbb {G} \times \mathbb {\mathbb {G} } \rightarrow \mathbb {G} _{1))$
3. Ved udgangen får vi . $({q}_{1},{q}_{2},\mathbb {G},\mathbb {G} _{1},{f})$
Lad . Lad os vælge to tilfældige generatorer og definere som . Så er det en tilfældig undergruppegenerator af orden . Offentlig nøgle: . Privat nøgle :. [11] [7] ${\displaystyle {n}={q}_{1}\ gange {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}}$

Kryptering

Cipher( ): $OK,M$

Vi antager, at meddelelsesrummet består af heltal i mængden . For at kryptere en besked ved hjælp af den offentlige nøgle vælger vi en tilfældig parameter og beregner $\{0,T\}$ $M$ $Okay$ ${r}{\xleftarrow {R}}\{0,1,...,{n}-1\}$

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

Resultatet er chifferteksten. [11] [7]

Dekryptering

Afkod ( ): $SK,C$

For at dekryptere chifferteksten ved hjælp af den private nøgle , overvej følgende udtryk $SK=q_{1}$

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

Lad . For at gendanne er det nok at beregne den diskrete logaritme til basen . ${\hat {g}}={g}^{q_{1}}$ ${M}$ ${C}^{q_{1))$ ${\hat {g))$

Det skal bemærkes, at dekryptering i dette system tager polynomiel tid i størrelsen af meddelelsesrummet. [11] [7]

Eksempler

Et eksempel på, hvordan algoritmen fungerer

Først vælger vi to forskellige primtal

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

Beregn produktet

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

Dernæst konstruerer vi en gruppe elliptiske kurver med orden , som har et bilineært kort. Elliptisk kurveligning ${n}$

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

som er defineret over et felt for et eller andet primtal . I dette eksempel sætter vi $\mathbb {F} _{p}$ ${\displaystyle {p=3{\bmod {4))))$

${p=307}$ .

Derfor er kurven supersingular med # rationelle punkter, som indeholder en undergruppe af orden . I gruppen vælger vi to tilfældige generatorer ${(E(p))=p+1=308}$ $\mathbb {G}$ ${\displaystyle {{n}=77(=308/4)))$ $\mathbb {G}$

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

hvor disse to generatorer har orden og beregning ${n}$

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

hvor er orden . Vi beregner meddelelsens chiffertekst ${h}$ ${\displaystyle {q_{1}=7))$

${M}{=2}$ .

Lad os tage og beregne ${r=5}$

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

For at dekryptere, beregner vi først

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

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

Nu finder vi den diskrete logaritme, der sorterer gennem alle potenserne som følger ${\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 }$ .

Bemærk venligst at . Derfor er dekrypteringen af chifferteksten lig med , hvilket svarer til den oprindelige besked. [12] ${\displaystyle {\hat {g}}^{2}={C^{q_{1))))$ ${2}$

2-DNF-evaluering

Et delvist homomorft system gør det muligt at estimere 2- DNF .

Input: Alice har en 2-DNF-formel , og Bob har et sæt variabler . Begge sider af inputtet indeholder en sikkerhedsindstilling . $\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 gør følgende:
1. Den udfører Generate_Key( ) -algoritmen for at beregne den og sende den til Alice. $\tau$ ${O}{K},{SK}$ ${O}{K}$
2. Den beregner og sender Cipher( ) ${O}{K},{a_{j))$ for . ${j=1,...,n}$
Alice gør følgende:
1. Den udfører aritmetisering ved at erstatte " " med " ", " " med " " og " " med " ". Bemærk, at dette er et polynomium med grad 2. $\Phi (\phi )$ $\lor$ $+$ $\jord$ $\ gange$ ${\displaystyle {\bar {x_{j))))$ $(1-x_{j})$ $\Phi$
2. Alice beregner en kryptering for en tilfældigt valgt ved hjælp af krypteringssystemets homomorfe egenskaber. Resultatet sendes til Bob. ${r}\ gange \Phi ({a})$ ${r}$
Hvis Bob modtager krypteringen " ", udsender han " "; ellers udsender den " ". [13] $0$ $0$ $en$

Homomorfe egenskaber

Systemet er additivt homomorft. Lad være den offentlige nøgle. Lad være henholdsvis chifferteksterne af beskederne . Enhver kan skabe en ensartet fordelt kryptering ved at beregne produktet af et tilfældigt tal i området . $({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\))$

Endnu vigtigere er det, at enhver kan multiplicere to krypterede meddelelser én gang ved hjælp af den bilineære kortlægning. Lad os definere og . Så bestil og bestil . Derudover skriver vi for nogle (ukendte) parameter . Antag, at vi kender to chiffertekster , . For at konstruere krypteringen af produktet vælger vi et tilfældigt tal og sæt . Vi får , hvor fordeles jævnt i , efter behov. ${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}}\time {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}}t^{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}}$

Således er en ensartet fordelt kryptering , men kun i gruppen , ikke i (så kun én multiplikation er tilladt). [elleve] ${C}$ ${m_{1}}\time {m_{2}}{\bmod {n}}$ $\mathbb {G} _{1}$ $\mathbb {G}$

Systemstabilitet

Stabiliteten af dette skema er baseret på Burnside-problemet : ved at kende et element af en sammensat ordensgruppe , er det umuligt at afgøre, om det tilhører en undergruppe af ordenen . ${n}={q}_{1}{q}_{2}$ ${q_{1}}$

Lad , og vær en tupel skabt af , hvor . Overvej følgende problem. Udskriv " " for et givet element , hvis rækkefølgen er lig med , ellers udskriv " ". Med andre ord, uden at kende faktoriseringen af ordensgruppen , skal man vide, om et element er i en undergruppe af gruppen . Dette problem kaldes Burnside-problemet [7] . ${\displaystyle \tau \in \mathbb {Z} ^{+))$ $({q}_{1},{q}_{2},\mathbb {G},\mathbb {G} _{1},{f})$ $x$ ${n}={q}_{1}{q}_{2}$ $({n},\mathbb {G} ,\mathbb {G} _{1},{f})$ ${x}\in \mathbb {G}$ $en$ ${x}$ ${q_{1}}$ $0$ ${n}$ ${x}$ $\mathbb {G}$

Det er klart, at hvis vi kan tage hensyn til grupperækkefølgen i kryptosystemet, så kender vi den private nøgle , og som et resultat er systemet ødelagt. Også, hvis vi kan beregne de diskrete logaritmer i gruppen, så kan vi beregne og . De nødvendige betingelser for sikkerhed er således: kompleksiteten af factoring og kompleksiteten af at beregne diskrete logaritmer i . [fjorten] ${n}$ ${q_{1}}$ $\mathbb {G}$ ${q_{2}}$ ${q_{1}=n/q_{2}}$ ${n}$ $\mathbb {G}$

Noter

↑ Pascal Paillier. Offentlige nøglekryptosystemer baseret på sammensatte gradresiduositetsklasser // Fremskridt inden for kryptologi - EUROCRYPT '99 / Jacques Stern. — Springer Berlin Heidelberg, 1999. — S. 223–238 . — ISBN 9783540489108 . - doi : 10.1007/3-540-48910-x_16 . Arkiveret fra originalen den 26. juni 2019.
↑ Tatsuaki Okamoto, Shigenori Uchiyama. Et nyt offentligt nøglekryptosystem så sikkert som factoring // Fremskridt inden for kryptologi - EUROCRYPT'98 / Kaisa Nyberg. — Springer Berlin Heidelberg, 1998. — S. 308–318 . — ISBN 9783540697954 . - doi : 10.1007/bfb0054135 . Arkiveret fra originalen den 29. august 2018.
↑ Mihir Bellare, Juan A. Garay, Tal Rabin. Hurtig batchverifikation til modulær eksponentiering og digitale signaturer // Fremskridt inden for kryptologi - EUROCRYPT'98 / Kaisa Nyberg. — Springer Berlin Heidelberg, 1998. — S. 236–250 . — ISBN 9783540697954 . - doi : 10.1007/bfb0054130 . Arkiveret fra originalen den 7. juni 2018.
↑ 1 2 Dan Boneh, Matt Franklin. Identitetsbaseret kryptering fra Weil-parringen // Fremskridt i kryptologi - CRYPTO 2001 / Joe Kilian. — Springer Berlin Heidelberg, 2001. — S. 213–229 . — ISBN 9783540446477 . - doi : 10.1007/3-540-44647-8_13 . Arkiveret fra originalen den 22. februar 2020.
↑ Evaluering af 2-DNF-formler på chiffertekster . Hentet 20. februar 2021. Arkiveret fra originalen 8. august 2017. (ubestemt)
↑ Secure Computation II // Theory of cryptography : Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, 10.-12. februar 2005: procedurer . - Berlin: Springer, 2005. - S. 326. - 1 online ressource (xii, 619 sider) s. - ISBN 9783540305767 , 3540305769, 3540245731, 9783540245735.
↑ 1 2 3 4 5 Takuho Mitsunaga, Yoshifumi Manabe, Tatsuaki Okamoto. Effektive sikre auktionsprotokoller baseret på Boneh-Goh-Nissim-krypteringen . — 2010-11-22. - T. E96A . — S. 149–163 . - doi : 10.1007/978-3-642-16825-3_11 .
↑ O.N. Vasilenko. Om beregningen af Weyl- og Tate-parringer // Tr. ved diskr. Matem .. - M . : FIZMATLIT, 2007. - T. 10. - S. 18-46.
↑ Antoine Joux. En runde protokol for treparts Diffie-Hellman . — 30-12-2006. - T. 17 . — S. 385–393 . - doi : 10.1007/10722028_23 .
↑ Victor Miller. Weil-parringen og dens effektive beregning // 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, USA, 10.-12. februar 2005: procedurer . - Berlin: Springer, 2005. - S. 329. - 1 online ressource (xii, 619 sider) s. - ISBN 9783540305767 , 3540305769, 3540245731, 9783540245735.
↑ Yi, Xun (højskolelærer), . Homomorf kryptering og applikationer . — Cham. — 1 onlineressource (xii, 126 sider) s. - ISBN 978-3-319-12229-8 , 3-319-12229-0.
↑ Theory of cryptography: Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, 10.-12. februar 2005: procedurer . - Berlin: Springer, 2005. - S. 332. - 1 online ressource (xii, 619 sider) s. - ISBN 9783540305767 , 3540305769, 3540245731, 9783540245735.
↑ EUROCRYPT 2010 (2010: Riveria, Frankrig). Fremskridt inden for kryptologi - EUROCRYPT 2010: 29. årlige internationale konference om teori og anvendelser af kryptografiske teknikker, Franske Riviera, 30. maj-3. juni 2010: procedurer . - Springer, 2010. - ISBN 9783642131905 , 3642131905.

Litteratur

S. M. Vladimirov, E. M. Gabidulin, A. I. Kolybelnikov, A. S. Kshevetsky. Kryptografiske metoder til informationsbeskyttelse. - 2. udg. - MIPT, 2016. - S. 225-257. — 266 s. - ISBN 978-5-7417-0615-2 .

Links

S. I. Adian. Burnside-problemet og relaterede spørgsmål // Uspekhi Mat. - 2010. - September ( bind 65 , hæfte 5 ).

Offentlig nøgle kryptosystemer

Algoritmer

Faktorisering af heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalingsmodtager Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritme	BLS Cramer - Shoup Diffie-Hellman protokol DSA ECDH Kurve25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypteret nøgleudveksling Ordning af ElGamal underskriftsordning MQV Schnorr ordning SPEKE SRP STS
Kryptografi på gitter	NTRUEncrypt NTRUSign Læringsbaseret nøgleudveksling med fejl Signaturbaseret træning med fejl i ringen LYKKELIGHED Nyt håb
Andet	AE CEILIDH EPOC Skjulte feltligninger IES Lamports underskrift McEliece Merkle-Hellman rygsæk kryptosystem Naccache-Stern rygsæk kryptosystem Tre trins protokol XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantekryptering

Emner

Elektronisk signatur
OAEP
Fingeraftryk
PKI
web af tillid
Nøglestørrelse
Identitetsbaseret kryptografi
Postkvantekryptografi
OpenPGP-kort