NTRUSign

NTRUSign , även känd som NTRU Signature Algorithm , är en krypteringsalgoritm med offentliga digitala signaturer baserad på GGH- signaturschemat .

Historik

Algoritmen presenterades först vid en:Asiacrypt-sessionen 2001 och publicerades i peer-reviewed form vid 2003 års RSA-konferens [1] . 2003 års utgåva inkluderade parameterrekommendationer för 80-bitars säkerhetsnivå. Nästa publikation 2005 reviderade rekommendationerna för 80-bitars säkerhetsnivå, och presenterade även parametrarna för de erforderliga säkerhetsnivåerna på 112, 128, 160, 192 och 256 bitar och beskrev algoritmer för att erhålla parameteruppsättningar för alla önskade säkerhetsnivåer. NTRU Cryptosystems, Inc. ansökte om patent för denna algoritm.[ när? ]

Funktioner

NTRUSign inkluderar att visa ett meddelande för en slumpmässig punkt i ett 2N-dimensionellt utrymme, där N är en av NTRUSign-parametrarna, och att lösa problemet med att hitta den närmaste vektorn i ett gitter , nära relaterat till NTRUEncrypt-gittret . Detta gitter har egenskapen att en viss 2N-dimensionell bas för gittret kan beskrivas med hjälp av 2 vektorer, som var och en består av N koefficienter och en bas som kan definieras av en separat N-dimensionell vektor. Detta gör att publika nycklar kan representeras i rymden snarare än , som är fallet med andra gitterbaserade signaturscheman. Operationerna tar tid, till skillnad från elliptisk kurvkryptografi och RSA. Därför är NTRUSign snabbare än dessa algoritmer vid låga säkerhetsnivåer och betydligt snabbare vid höga säkerhetsnivåer. $O(N)$ $O(N^{2})$ $O(N^{2})$ $O(N^{3})$

NTRUSign övervägs för standardisering av IEEE P1363-arbetsgruppen.

Beskrivning av algoritmen

Precis som i NTRUEncrypt görs i NTRUSign beräkningar i en ring , där multiplikationen " " är en cyklisk modulofaltning . Produkten av två polynom och är . $R=\mathbb {Z} _{q}[X]/(X^{N}-1)$ $*$ $q$ $f=[f_{0},f_{1},\ldots ,f_{N-1}]$ $g=[g_{0},g_{1},\ldots ,g_{N-1}]$ $f*g=\sum _{i+j\equiv k\mod N}f_{i}\cdot g_{j}\mod q$

NTRUSign kan baseras på standard- eller transponerade rutnät. Den största fördelen med det transponerade gittret är att koefficienterna för polynomet tillhör {-1,0,1}. Detta ökar multiplikationshastigheten.

Nyckelgenerering

Indata: heltal , sträng eller . $N,q,d_{f},d_{g},B>0$ $t=standard$ $transponera$
Generering av slutna gitterbaser och en öppen gitterbas $B$

Installera . Tills :

i=B

i>0

Välj godtyckligt , ∈ , samprima med respektive . $f$ $g$ $\mathbb {R}$ ${\displaystyle d_{f))$ ${\displaystyle d_{g))$
Hitta små sådana som . $F,G\in R$ $f*GF*g=q$
Om , ställ in och . $t=standard$ $f_{i}=f$ $f'_{i}=F$

Om , ställ in och .

t=transpose

f_{i}=f

f'_{i}=g

Beräkna . Installera .

h_{i}=f_{i}^{-1}*f'_{i}modq

i=i-1

Offentlig nyckel: inmatningsparametrar och . $h=ho=f_{0}^{-1}*f'_{0}\operatörsnamn {mod} q$
Privat nyckel: för . ${\displaystyle \left\{f_{i},f'_{i},h_{i}\right\))$ $i=0...B$

Signatur

Signaturen kräver en hashfunktion på dokumentets digitala utrymme . $H:{\mathcal {D}}\rightarrow R$ $\mathcal{D}$

Indata: digitalt dokument och privat nyckel för . $D\in {\mathcal {D}}$ ${\displaystyle \left\{f_{i},f'_{i},h_{i}\right\))$ $i=0...B$
Installera . $r=0$
Installera och . Representera som en sträng av bitar. Ställ in där anger sammanlänkning . Installera . $s=0$ $i=B$ $r$ $m_{o}=H(D||r)$ $||$ ${\displaystyle m=m_{o))$

${\displaystyle \left\{f_{i},f'_{i},h_{i}\right\))$ - bas $i$
Beräkna $x=\lfloor -{\frac {1}{q}}m_{i}*f'_{i}\rceil$
Beräkna $y=\lfloor {\frac {1}{q}}m_{i}*f_{i}\rceil$
$s_{i}=x*f+y*f'$
$m_{i}=si*(h_{i}-h_{i-1})\mod q$
Signatur: ${\displaystyle s=s+s_{i))$

Signaturverifiering

Verifiering kräver samma hashfunktion , "normaliserande relation" och polynomnorm . Normen för ett polynom definieras som , där (där den senare är den euklidiska normen). $H$ ${\mathcal {N}}\in \mathbb {R}$ $||.||$ $||t||$ $t$ ${\displaystyle \inf _{0\leq k<q}||t+kq||_{z))$ $||r||_{z}=\summa _{i=0}^{N-1}r_{i}^{2}-{\frac {1}{N))\summa _{ i=0}^{N}r_{i}$

Indata: Signerad data och publik nyckel . $(D,r,s)$ $h$
Representera r som en sträng av bitar. Installera . $m=H(D||r)$
Beräkna . $b=||(s,s*hm\operatörsnamn {mod} g))||$
Signaturen anses vara korrekt om . $b<{\mathcal {N}}$

Notera

Rekommenderade inställningar $(N,q,d_{f},d_{g},B,t,{\mathcal {N)))=(251,128,73,71,1,transponera,310)$

Anteckningar

↑ Jeffrey Hoffstein, Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman, William Whyte. NTRUSign: Digitala signaturer som använder NTRU-gittret . Arkiverad från originalet den 30 januari 2013.

Länkar

Public key kryptosystem

Algoritmer

Faktorisering av heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalare Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritm	BLS Cramer - Shoup Diffie-Hellman-protokollet DSA ECDH Kurva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypterad nyckelutbyte Schema för ElGamal signaturschema MQV Schnorr-schema SPEKE SRP STS
Kryptografi på galler	NTRUEncrypt NTRUSign Inlärningsbaserat nyckelutbyte med fel Signaturbaserad träning med fel i ringen SALIGHET Nytt hopp
Övrig	AE CEILIDH EPOC Dolda fältekvationer IES Lamports signatur McEliece Merkle-Hellman ryggsäckskryptosystem Naccache–Stern ryggsäckskryptosystem Trestegsprotokoll XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvantkryptering

Ämnen

Elektronisk signatur
OAEP
Fingeravtryck
PKI
nät av förtroende
Nyckelstorlek
Identitetsbaserad kryptografi
Postkvantkryptografi
OpenPGP-kort