Kryptosystém Bonnet-Go-Nissima

Kryptosystém Bonet-Go-Nishima je částečně homomorfní kryptosystém , který je modifikací kryptosystému Paye [1] a kryptosystému Okamoto-Uchiyama [2] . Vyvinutý v roce 2005 Danem Bonetem [3] s Yu Jin Go a Koby Nissim [4] [5] . Založeno na konečných grupách složeného řádu a bilineárních párování na eliptických křivkách; systém umožňuje vyhodnocení vícerozměrných kvadratických polynomů na šifrových textech (například disjunktivní normální forma druhého řádu (2 - DNF )).

Systém má aditivní homomorfismus (podporuje libovolné sčítání a jedno násobení (následované libovolným sčítáním) pro šifrovaná data).

Algoritmus používaný v kryptosystému BGN je založen na problému Burnside . [6] .

Operační algoritmus

Jako všechny homomorfní šifrovací systémy, CBGN zahrnuje následující procesy: Generování klíčů, šifrování a dešifrování.

Konstrukce využívá některé skupiny konečných složených řádů, které podporují bilineární mapování. Používá se následující zápis:

$\mathbb {G}$ a jsou dvě cyklické skupiny konečného řádu . $\mathbb {G} _{1}$ ${n}$
${G}$ - generátor . $\mathbb {G}$
${f}$ je bilineární mapování . Jinými slovy, pro všechny a my máme . Požadujeme také, aby : byl generátor ${\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}$

Říkáme, že je to bilineární skupina, pokud existuje skupina a bilineární zobrazení definované výše. [7] $\mathbb {G}$ $\mathbb {G} _{1}$

Generování klíčů

Generate_Key( ) : $\tau$

Vzhledem k parametru zabezpečení jako vstupu vypočítáme algoritmus pro získání n-tice . Algoritmus funguje takto: ${\displaystyle \tau \in \mathbb {Z} ^{+))$ $X(\tau )$ $({q}_{1},{q}_{2},\mathbb {G} ,\mathbb {G} _{1},{f})$
1. Vygenerujme dvě náhodná bitová čísla a a nastavme . $\tau$ ${q}_{1}$ ${\displaystyle {q}_{2))$ ${n}={q}_{1}{q}_{2}\in \mathbb {Z}$
2. Vytvořme bilineární skupinu pořadí , kde > 3 je dané číslo, které není dělitelné 3: $\mathbb {G}$ ${n}$ ${n}$
  1. Najděte nejmenší přirozené číslo takové, které je prvočíslo a . $\ell \in \mathbb {Z}$ ${p}=\ell {n}-1$ ${\displaystyle {p=3{\bmod {4))))$
  2. Uvažujme skupinu bodů na eliptické křivce definované přes . Protože křivka má body v . Proto má skupina bodů na křivce podgrupu řádu , kterou označíme . ${y^{2}=x^{3}+x}$ $\mathbb {F} _{p}$ ${\displaystyle {p=3{\bmod {4))))$ ${p}+1=\ell {n}$ $\mathbb {F} _{p}$ ${n}$ $\mathbb {G}$
  3. Nechť je podskupina uspořádaná . Upravený Weilův párovací algoritmus (Weylovo párování je bilineární, šikmo symetrické, nedegenerované zobrazení [8] [4] [9] [10] ) na křivce vytváří bilineární zobrazení splňující dané podmínky. $\mathbb {G} _{1}$ $\mathbb {F} _{{p}^{2}}^{*}$ ${n}$ ${\displaystyle {f}:\mathbb {G} \times \mathbb {\mathbb {G} } \rightarrow \mathbb {G} _{1))$
3. Na výstupu dostaneme . $({q}_{1},{q}_{2},\mathbb {G} ,\mathbb {G} _{1},{f})$
Nechte _ Zvolme dva náhodné generátory a definujme jako . Pak je to náhodný generátor pořadí podskupin . Veřejný klíč: . Soukromý klíč: . [11] [7] ${\displaystyle {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}}$

Šifrování

Šifra( ): $OK,M$

Předpokládáme, že prostor zpráv se skládá z celých čísel v množině . Pro zašifrování zprávy pomocí veřejného klíče zvolíme náhodný parametr a provedeme výpočet $\{0,T\}$ $M$ $OK$ ${r}{\xleftarrow {R}}\{0,1,...,{n}-1\}$

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

Výsledkem je šifrovaný text. [11] [7]

Dešifrování

Dekódovat ( ): $SK,C$

Chcete-li dešifrovat šifrovaný text pomocí soukromého klíče , zvažte následující výraz $SK=q_{1}$

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

Nechte _ K obnovení stačí vypočítat diskrétní logaritmus k základně . ${\hat {g}}={g}^{q_{1}}$ ${M}$ ${C}^{q_{1))$ ${\hat {g))$

Je třeba poznamenat, že dešifrování v tomto systému vyžaduje polynomiální čas ve velikosti prostoru zpráv. [11] [7]

Příklady

Příklad toho, jak algoritmus funguje

Nejprve zvolíme dvě různá prvočísla

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

Vypočítejte produkt

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

Dále sestrojíme skupinu eliptických křivek s řádem , která má bilineární zobrazení. Rovnice eliptické křivky ${n}$

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

který je definován přes pole pro nějaké prvočíslo . V tomto příkladu nastavujeme $\mathbb {F} _{p}$ ${\displaystyle {p=3{\bmod {4))))$

${p=307}$ .

Proto je křivka supersingulární s # racionálními body, která obsahuje podskupinu řádu . Ve skupině zvolíme dva náhodné generátory ${(E(p))=p+1=308}$ $\mathbb {G}$ ${\displaystyle {{n}=77(=308/4)))$ $\mathbb {G}$

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

kde tyto dva generátory mají řád a počítají ${n}$

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

kde je řád . Vypočítáme šifrový text zprávy ${h}$ ${\displaystyle {q_{1}=7))$

${M}{=2}$ .

Vezmeme a spočítáme ${r=5}$

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

Abychom dešifrovali, nejprve spočítáme

${\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]}$ .

Nyní najdeme diskrétní logaritmus, setříděním všech mocnin následovně ${\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 }$ .

Vezměte prosím na vědomí, že . Proto se dešifrování šifrovaného textu rovná , což odpovídá původní zprávě. [12] ${\displaystyle {\hat {g}}^{2}={C^{q_{1))))$ ${2}$

Hodnocení 2-DNF

Částečně homomorfní systém umožňuje odhadnout 2- DNF .

Vstup: Alice má vzorec 2-DNF a Bob má sadu proměnných . Obě strany vstupu obsahují nastavení zabezpečení . $\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 dělá následující:
1. Provede algoritmus Generate_Key( ) , aby jej vypočítal a odeslal Alici. $\tau$ ${O}{K},{SK}$ ${O}{K}$
2. Vypočítá a odešle Cipher( ) ${O}{K},{a_{j))$ pro . ${j=1,...,n}$
Alice dělá následující:
1. Provádí aritmetizaci nahrazením „ “ za „ “, „ “ za „ “ a „ “ za „ “. Všimněte si, že se jedná o polynom stupně 2. $\Phi (\phi )$ $\lor$ $+$ $\přistát$ $\krát$ ${\displaystyle {\bar {x_{j))))$ $(1-x_{j})$ $\Phi$
2. Alice vypočítá šifrování pro náhodně vybraného pomocí homomorfních vlastností šifrovacího systému. Výsledek je odeslán Bobovi. ${r}\times \Phi ({a})$ ${r}$
Pokud Bob obdrží šifrování " ", vypíše " "; jinak vypíše " ". [13] $0$ $0$ $jeden$

Homomorfní vlastnosti

Systém je aditivně homomorfní. Nechť je veřejný klíč. Nechť jsou šifrové texty zpráv, resp. Každý může vytvořit rovnoměrně rozložené šifrování výpočtem součinu náhodného čísla v rozsahu . $({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\))$

Ještě důležitější je, že kdokoli může znásobit dvě zašifrované zprávy jednou pomocí bilineárního mapování. Pojďme definovat a . Pak objednávejte a objednávejte . Navíc pro nějaký (neznámý) parametr zapíšeme . Předpokládejme, že známe dva šifrové texty , . Pro konstrukci šifrování produktu zvolíme náhodné číslo a nastavíme . Dostaneme , kde je distribuováno rovnoměrně v , jak je požadováno. ${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}}$

Jedná se tedy o jednotně distribuované šifrování , ale pouze ve skupině , nikoli v (takže je povoleno pouze jedno násobení). [jedenáct] ${C}$ ${m_{1}}\times {m_{2}}{\bmod {n}}$ $\mathbb {G} _{1}$ $\mathbb {G}$

Stabilita systému

Stabilita tohoto schématu je založena na Burnside problému : při znalosti prvku složené řádové skupiny je nemožné určit, zda patří do podskupiny řádu . ${\displaystyle {n}={q}_{1}{q}_{2))$ ${q_{1}}$

Nechat , a být n-tice vytvořené , kde . Zvažte následující problém. Pro daný a prvek vytiskněte " " , pokud se pořadí rovná , jinak vytiskněte " " . Jinými slovy, aniž bychom znali faktorizaci skupiny pořadí , potřebujeme vědět, zda je prvek v podskupině skupiny . Tento problém se nazývá Burnside problém [7] . ${\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}$ $jeden$ ${X}$ ${q_{1}}$ $0$ ${n}$ ${X}$ $\mathbb {G}$

Je jasné, že pokud můžeme vzít v úvahu skupinové pořadí v kryptosystému, pak známe soukromý klíč a v důsledku toho je systém narušen. Také, pokud dokážeme vypočítat diskrétní logaritmy ve skupině , můžeme vypočítat a . Nezbytnými podmínkami pro bezpečnost jsou tedy: složitost faktoringu a složitost výpočtu diskrétních logaritmů v . [čtrnáct] ${n}$ ${q_{1}}$ $\mathbb {G}$ ${q_{2}}$ ${q_{1}=n/q_{2}}$ ${n}$ $\mathbb {G}$

Poznámky

↑ Pascal Paillier. Kryptosystémy s veřejným klíčem založené na složených třídách reziduózních stupňů // Pokroky v kryptologii - EUROCRYPT '99 / Jacques Stern. — Springer Berlin Heidelberg, 1999. — S. 223–238 . — ISBN 9783540489108 . - doi : 10.1007/3-540-48910-x_16 . Archivováno z originálu 26. června 2019.
↑ Tatsuaki Okamoto, Shigenori Uchiyama. Nový kryptosystém s veřejným klíčem stejně bezpečný jako faktoring // Pokroky v kryptologii - EUROCRYPT'98 / Kaisa Nyberg. — Springer Berlin Heidelberg, 1998. — S. 308–318 . — ISBN 9783540697954 . - doi : 10.1007/bfb0054135 . Archivováno z originálu 29. srpna 2018.
↑ Mihir Bellare, Juan A. Garay, Tal Rabin. Rychlé dávkové ověření pro modulární umocňování a digitální podpisy // Pokroky v kryptologii - EUROCRYPT'98 / Kaisa Nyberg. — Springer Berlin Heidelberg, 1998. — S. 236–250 . — ISBN 9783540697954 . - doi : 10.1007/bfb0054130 . Archivováno z originálu 7. června 2018.
↑ 1 2 Dan Boneh, Matt Franklin. Identity-Based Encryption from the Weil Pairing // Pokroky v kryptologii - CRYPTO 2001 / Joe Kilian. — Springer Berlin Heidelberg, 2001. — S. 213–229 . — ISBN 9783540446477 . - doi : 10.1007/3-540-44647-8_13 . Archivováno z originálu 22. února 2020.
↑ Vyhodnocení vzorců 2-DNF na šifrových textech . Získáno 20. února 2021. Archivováno z originálu 8. srpna 2017. (neurčitý)
↑ Secure Computation II // Theory of cryptography : Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, 10.-12. února 2005 : sborník . - Berlin: Springer, 2005. - S. 326. - 1 online zdroj (xii, 619 stran) Str. - ISBN 9783540305767 , 3540305769, 3540245731, 9783540245735.
↑ 1 2 3 4 5 Takuho Mitsunaga, Yoshifumi Manabe, Tatsuaki Okamoto. Efektivní zabezpečené aukční protokoly založené na šifrování Boneh-Goh-Nissim . — 22. 11. 2010. - T. E96A . — S. 149–163 . - doi : 10.1007/978-3-642-16825-3_11 .
↑ O.N. Vasilenko. O výpočtu Weylových a Tateových párů // Tr. podle discr. Matem .. - M . : FIZMATLIT, 2007. - T. 10. - S. 18-46.
↑ Antoine Joux. Jednokolový protokol pro tripartitu Diffie–Hellman . — 2006-12-30. - T. 17 . — S. 385–393 . - doi : 10.1007/10722028_23 .
↑ Victor Miller. Weilovo párování a jeho efektivní výpočet // J. Kryptologie. — 2004-09-01. - 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. února 2005: sborník . - Berlin: Springer, 2005. - S. 329. - 1 online zdroj (xii, 619 stran) s. - ISBN 9783540305767 , 3540305769, 3540245731, 9783540245735.
↑ Yi, Xun (vysokoškolský učitel), . Homomorfní šifrování a aplikace . — Cham. — 1 online zdroj (xii, 126 stran) str. - 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. února 2005 : sborník . - Berlin: Springer, 2005. - S. 332. - 1 online zdroj (xii, 619 stran) Str. - ISBN 9783540305767 , 3540305769, 3540245731, 9783540245735.
↑ EUROCRYPT 2010 (2010 : Riveria, Francie). Pokroky v kryptologii – EUROCRYPT 2010: 29. výroční mezinárodní konference o teorii a aplikacích kryptografických technik, Francouzská riviéra, 30. května – 3. června 2010: sborník příspěvků . - Springer, 2010. - ISBN 9783642131905 , 3642131905.

Literatura

S. M. Vladimirov, E. M. Gabidulin, A. I. Kolybelnikov, A. S. Kshevetsky. Kryptografické metody ochrany informací. - 2. vyd. - MIPT, 2016. - S. 225-257. — 266 s. - ISBN 978-5-7417-0615-2 .

Odkazy

S. I. Adian. Problém Burnside a související otázky // Uspekhi Mat. - 2010. - Září ( díl 65 , číslo 5 ).

Kryptosystémy s veřejným klíčem

Algoritmy

Faktorizace celých čísel	kryptosystém Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern zaplatit Rabin RSA Okamoto – Uchijama Schmidt-Samoa
Diskrétní logaritmus	BLS Cramer - Shoup protokol Diffie-Hellman DSA ECDH Křivka25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Výměna šifrovaných klíčů Schéma ElGamal podpisové schéma MQV Schnorrovo schéma SPEKE SRP STS
Kryptografie na mřížkách	NTRUEncrypt NTRUSsign Výměna klíčů založená na učení s chybami Trénink založený na podpisu s chybami v kruhu BLAHO Nová naděje
jiný	AE CEILIDH EPOC Rovnice skrytého pole IES Lamportův podpis McEliece Zádový kryptosystém Merkle-Hellman Zádový kryptosystém Naccache–Stern Tříkrokový protokol XTR

Teorie

Diskrétní logaritmus na eliptické křivce
Eliptická kryptografie
Kryptografie založená na hash
Nekomutativní kryptografie
Problém RSA
Jednosměrná funkce s tajným vstupem

Normy

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantová kryptografie

Témata

Elektronický podpis
OAEP
Otisk prstu
PKI
síť důvěry
Velikost klíče
Kryptografie založená na identitě
Postkvantová kryptografie
OpenPGP karta