Beslut Linjärt antagande

Decision Linear (DLIN) antagandet är ett beräkningshårdhetsantagande som används i elliptisk kurvkryptografi . I synnerhet är DLIN-antagandet användbart i inställningar där det beslutsmässiga Diffie–Hellman-antagandet inte håller (som ofta är fallet i parningsbaserad kryptografi ). Det linjära beslutsantagandet introducerades av Boneh , Boyen och Shacham.

Informellt anger DLIN-antagandet att givet $(u,\,v,\,h,\,u^{x},\,v^{y})$ , med $u,\,v,\,h$ slumpmässiga gruppelement och $x,\,y$ slumpmässiga exponenter är det svårt att särskilja ${ \displaystyle h^{x+y}}$ från ett oberoende slumpmässigt gruppelement $\eta$ .

Motivering

I symmetrisk parningsbaserad kryptografi är gruppen $G$ utrustad med en parning $e:G\times G\to T$ som är bilinjär . Denna karta ger en effektiv algoritm för att lösa det beslutsmässiga Diffie-Hellman- problemet. Givet input ${\displaystyle (g,\,g^{a},\,g^{b},\,h)} , är det$ lätt att kontrollera om ${\ displaystyle h}$ är lika med $g^{ab}$ . Detta följer genom att använda parningen: notera att

$e(g^{a},g^{b})=e(g,g)^{ab}=e(g,g^{ab}).$

Således, om $h=g^{ab}$ , då värdena $e(g^{a},g^{b})$ och $e(g,h)$ kommer att vara lika.

Eftersom detta kryptografiska antagande, väsentligt för att bygga ElGamal-kryptering och signaturer , inte håller i detta fall, behövs nya antaganden för att bygga kryptografi i symmetriska bilinjära grupper. DLIN-antagandet är en modifiering av antaganden av Diffie-Hellman-typ för att motverka ovanstående attack.

Formell definition

Låt $G$ vara en cyklisk grupp av prime order $p$ . Låt $u$ , $v$ och $h$ vara enhetliga slumpgeneratorer av $G$ . Låt $a,b$ vara enhetligt slumpmässiga element av $\{1,\,2,\,\dots ,\,p-1\}$ . Definiera en distribution

$D_{1}=(u,\,v,\,h,\,u^{a},\,v^{b},\,h^{a+b}).$

Låt $\eta$ vara ett annat enhetligt slumpmässigt element i $G$ . Definiera en annan distribution

$D_{2}=(u,\,v,\,h,\,u^{a},\,v^{b},\,\eta ).$

Decision Linear antagandet säger att $D_{1}$ och $D_{2}$ är beräkningsmässigt omöjliga att särskilja .

Ansökningar

Linjär kryptering

Boneh, Boyen och Shacham definierar ett krypteringsschema för offentlig nyckel i analogi med ElGamal-kryptering. I detta schema är en publik nyckel generatorerna $u,v,h$ . Den privata nyckeln är två exponenter så att $u^{x}=v^{y}=h$ . Kryptering kombinerar ett meddelande $m\in G$ med den publika nyckeln för att skapa en chiffertext

$c:=(c_{1},\,c_{2},\,c_ {3})=(u^{a},\,v^{b},\,m\cdot h^{a+b})$ .

För att dekryptera chiffertexten kan den privata nyckeln användas för att beräkna

$m':=c_{3}\cdot (c_{1}^{x}\cdot c_{2}^{y})^{-1}.$

För att kontrollera att detta krypteringsschema är korrekt , dvs $m'=m$ när båda parter följer protokollet, notera att

$m'=c_{3}\cdot (c_{1}^{x}\cdot c_{2}^{y})^{-1}=m\cdot h^{a+b}\cdot ((u^{a})^{x}\cdot (v^{b})^{y})^{-1}=m\cdot h^{a+b}\cdot ((u^{x })^{a}\cdot (v^{y})^{b})^{-1}.$

Att sedan använda det faktum att $u^{x}=v^{y}=h$ ger

$m'=m\cdot h^{a+b}\cdot (h^{a}\cdot h^{b})^{-1}=m\cdot (h^{a+b}\ cdot h^{-ab})=m.$

Vidare är detta schema IND-CPA säkert förutsatt att DLIN-antagandet gäller.

Korta gruppsignaturer

Boneh, Boyen och Shacham använder också DLIN i ett schema för gruppsignaturer . Signaturerna kallas "korta gruppsignaturer" eftersom de, med en standardsäkerhetsnivå, kan representeras i endast 250 byte .

Deras protokoll använder först linjär kryptering för att definiera en speciell typ av nollkunskapsbevis . Sedan Fiat–Shamir-heuristiken för att omvandla bevissystemet till en digital signatur . De bevisar att denna signatur uppfyller de ytterligare kraven på oförglömlighet, anonymitet och spårbarhet som krävs för en gruppsignatur.

Deras bevis bygger inte bara på DLIN-antagandet utan också på ett annat antagande som kallas q {\displaystyle q} -starka Diffie-Hellman-antagandet. Det är bevisat i den slumpmässiga orakelmodellen .

Andra applikationer

Sedan definitionen 2004 har beslutets linjära antagande sett en mängd andra tillämpningar. Dessa inkluderar konstruktionen av en pseudoslumpmässig funktion som generaliserar Naor-Reingold-konstruktionen , ett attributbaserat krypteringsschema och en speciell klass av icke-interaktiva nollkunskapsbevis .