Luddrig extraktor

Fuzzy-extraktorer är en metod som gör att biometriska data kan användas som indata till standardkrypteringstekniker för att förbättra datorsäkerheten. "Fuzzy", i detta sammanhang, syftar på det faktum att de fasta värden som krävs för kryptografi kommer att extraheras från värden nära men inte identiska med den ursprungliga nyckeln, utan att kompromissa med den säkerhet som krävs. En applikation är att kryptera och autentisera användarposter, med hjälp av användarens biometriska indata som nyckel.

Fuzzy-extraktorer är ett biometriskt verktyg som möjliggör användarautentisering, med hjälp av en biometrisk mall konstruerad från användarens biometriska data som nyckel, genom att extrahera en enhetlig och slumpmässig sträng $R$ från en indata $w$ , med en tolerans för buller. Om ingången ändras till $w'$ men fortfarande är nära $w$ , kommer samma sträng $R$ att byggas om. För att uppnå detta, under den initiala beräkningen av $R$ matar processen också ut en hjälpsträng $P$ som kommer att lagras för att återställa $R$ senare och kan göras offentlig utan att kompromissa med säkerheten av $R$ . Processens säkerhet säkerställs också när en motståndare modifierar $P$ . När den fasta strängen $R$ har beräknats, kan den användas till exempel för nyckelöverenskommelser mellan en användare och en server endast baserat på en biometrisk indata.

Historia

En föregångare till fuzzy extraktorer var det så kallade "Fuzzy Commitment", som designats av Juels och Wattenberg. Här frigörs den kryptografiska nyckeln med hjälp av biometriska data.

kom Juels och Sudan på fuzzy vault -scheman. Dessa är ordningsinvarianta för det luddiga åtagandeschemat och använder en Reed–Solomon felkorrigeringskod . Kodordet infogas som koefficienterna för ett polynom, och detta polynom utvärderas sedan med avseende på olika egenskaper hos biometriska data.

Både Fuzzy Commitment och Fuzzy Vaults var föregångare till Fuzzy Extractors.

Motivering

För att fuzzy extraherare ska generera starka nycklar från biometriska och andra brusiga data, kommer kryptografiska paradigm att tillämpas på denna biometriska data. Dessa paradigm:

(1) Begränsa antalet antaganden om innehållet i de biometriska uppgifterna (detta data kommer från en mängd olika källor, så för att undvika utnyttjande av en motståndare är det bäst att anta att inmatningen är oförutsägbar ) .

(2) Tillämpa vanliga kryptografiska tekniker på inmatningen. (Fuzzy extraherar konverterar biometriska data till hemliga, enhetligt slumpmässiga och tillförlitligt reproducerbara slumpmässiga strängar.)

Dessa tekniker kan också ha andra bredare applikationer för andra typer av bullriga indata, såsom approximativa data från mänskligt minne , bilder som används som lösenord och nycklar från kvantkanaler. Fuzzy-extraktorer har också applikationer för att bevisa omöjligheten av de starka föreställningarna om integritet med avseende på statistiska databaser.

Grundläggande definitioner

Förutsägbarhet

Förutsägbarhet indikerar sannolikheten att en motståndare kan gissa en hemlig nyckel. Matematiskt sett är förutsägbarheten för en slumpvariabel $A$$\max _{\mathrm {a} }P[A=a]$ .

Till exempel, givet ett par slumpvariabler $A$ och $B$ , om motståndaren känner till $b$ av $B$ , då förutsägbarheten för $A$ kommer att vara $\max _{\mathrm {a} }P[A=a|B=b]$ . Så en motståndare kan förutsäga $A$ med $E_{b\leftarrow B}[\max _{\mathrm {a} }P[A=a|B=b]]$ . Vi använder genomsnittet över $B$ eftersom det inte är under motståndarens kontroll, men eftersom att veta $b$ gör förutsägelsen av $A$ motstridig, tar vi det värsta fallet över $A$ .

Min-entropi

Min-entropi indikerar den värsta entropin. Matematiskt sett definieras det som $H_{\infty }(A)=-\log(\max _{\mathrm {a } }P[A=a])$ .

En slumpvariabel med en min-entropi på minst $m$ kallas en $m$ -källa.

Statistiskt avstånd

Statistiskt avstånd är ett mått på särskiljbarhet. Matematiskt uttrycks det för två sannolikhetsfördelningar $A$ och $B$ som $SD[A,B]$ = ${\frac {1}{2}}\sum _{\mathrm {v} }|P[A=v]-P[B=v]|$ . I vilket system som helst, om $A$ ersätts med $B$ , kommer det att bete sig som det ursprungliga systemet med en sannolikhet på minst ${\displaystyle 1-SD$ .

Definition 1 (stark extraktor)

Ställer in $​​{\displaystyle M}$ som en stark slumpextraktor . Den randomiserade funktionen Ext: $M\rightarrow \{0,1\}^{l}$ , med slumpmässighet av längden $r$ , är a $(m,l,\epsilon )$ stark extraktor för alla $m$ -källor $W$ på ${\displaystyle M(\operatörsnamn {Ext} (W;I),I)\approx _{\epsilon }(U_{l},U_{r}),} där I$ = $displaystyle I=U_{r}}$ är oberoende av $W$ .

Utdata från extraheraren är en nyckel genererad från $w\leftarrow W$ med fröet $i\leftarrow I$ . Det beter sig oberoende av andra delar av systemet, med sannolikheten $1-\epsilon$ . Starka extraktorer kan som mest extrahera $l=m-2\log {\frac {1}{\epsilon }}+O(1)$ bitar från en godtycklig $m$ -källa.

Säker skiss

Säker skiss gör det möjligt att rekonstruera bullriga input; så att, om ingången är $w$ och skissen är $s$ , ges $s$ och ett värde $w'$ nära $w$ , $w$ kan återställas. Men skissen $s$ får inte avslöja information om ${\displaystyle w} ,$ för att hålla den säker.

Om $\mathbb {M}$ är ett metriskt utrymme, återställer en säker skiss punkten $w\in \mathbb {M}$ från valfri punkt $w'\ i \mathbb {M}$ nära $w$ , utan att avslöja själva ${\displaystyle w} .$

Definition 2 (säker skiss)

En $(m,{\tilde {m}},t)$ säker skiss är ett par effektiva randomiserade procedurer (SS – Sketch; Rec – Recover) så att:

(1) Skissproceduren SS tar som indata $w\in \mathbb {M}$ och returnerar en sträng $s\in {\{0,1\} ^{*}}$ .

Återställningsproceduren Rec tar som indata de två elementen $w'\in \mathbb {M}$ och $s\in {\{0,1\}^ {*}}$ .

(2) Korrekthet: Om $dis(w,w')\leq t$ så är $Rec(w',SS(w))=w$ .

(3) Säkerhet: För varje $m$ -källa över $M$ , är min-entropin för $W$ , givet $s$ , hög:

För alla $(W,E)$ , om ${\tilde {H}}_{\mathrm {\infty } }(W| E)\geq m$ , sedan ${\tilde {H}}_{\mathrm {\infty } }(W|SS(W) ),E)\geq {\tilde {m}}$ .

Luddrig extraktor

Fuzzy extraherare återställer inte den ursprungliga inmatningen utan genererar en sträng $R$ (som är nära enhetlig) från $w$ och tillåter dess efterföljande reproduktion (med hjälp av hjälpsträngen $P$ ) givet någon $w'$ nära $w$ . Starka extraktorer är ett specialfall av fuzzy extraherar när $t$ = 0 och $P=I$ .

Definition 3 (fuzzy extractor)

En $(m,l,t,\epsilon )$ fuzzy extraktor är ett par effektiva randomiserade procedurer (Gen – Generera och Rep – Reproducera) så att:

(1) Gen, givet $w\in \mathbb {M}$ , matar ut en extraherad sträng $R\in {\mathbb {\{} 0,1\ }^{l}}$ och en hjälpsträng $P\in {\mathbb {\{} 0,1\}^{*}}$ .

(2) Korrekthet: Om $dis(w,w')\leq t$ och $(R, P)\leftarrow Gen(w)$ , sedan $Rep(w',P)=R$ .

(3) Säkerhet: För alla m-källor $W$ över ${\displaystyle M} är$ strängen $R$ nästan enhetlig, även givet $P$ . Så, när ${\displaystyle {\tilde {H}}_{\mathrm {\infty } }(W|E)\geq m},$ då $(R,P,E)\approx (U_{\mathrm {l} },P,E)$ .

Så Fuzzy-extraktorer matar ut nästan enhetliga slumpmässiga sekvenser av bitar som är en förutsättning för att använda kryptografiska applikationer (som hemliga nycklar). Eftersom utgångsbitarna är något olikformiga finns det en risk för minskad säkerhet; men avståndet från en enhetlig fördelning är inte mer än $\epsilon$ . Så länge detta avstånd är tillräckligt litet kommer säkerheten att förbli tillräcklig.

Säkra skisser och luddiga utdragare

Säkra skisser kan användas för att konstruera luddiga extraherar: till exempel tillämpa SS på $w$ för att få $s$ och stark extraherare Ext, med slumpmässighet $x$ , till $w$ , för att få $R$ . $(s,x)$ kan lagras som hjälpsträng $P$ . $R$ kan reproduceras med $w'$ och $P=(s,x)$ . $Rec(w',s)$ kan återställa $w$ och $Ext(w,x)$ kan återskapa $R$ .

Följande lemma formaliserar detta.

Lemma 1 (luddiga utdragare från skisser)

Antag att (SS,Rec) är en $(M,m,{\tilde {m}},t)$ säker skiss och låt Ext vara ett genomsnittsfall $(n,{\tilde {m}},l,\epsilon )$ stark extraktor. Då är följande (Gen, Rep) en $(M,m,l,t,\epsilon )$ fuzzy extractor:

(1) Gen $(w,r,x)$ : set ${ \displaystyle P=(SS(w;r),x),R=Ext(w;x),}$ och utgång $(R,P)$ .

(2) Rep $(w',(s,x))$ : återhämta $w=Rec(w' ,s)$ och utmatning $R=Ext(w;x)$ .

Bevis:

från definitionen av säker skiss (Definition 2), $H_{\infty }(W|SS(W))\geq {\tilde {m}}$ ;

och eftersom Ext är ett medelfall $(n,m,l,\epsilon )$ -stark extraktor;

$SD((Ext(W;X),SS(W),X),(U_{l},SS(W),X))=SD((R,P),(U_{l}, P))\leq \epsilon .$

Följd 1

     Om (SS,Rec) är en $(M,m,{\tilde {m}},t)$ säker skiss och Ext är en $(n,{\tilde {m}}-log({\frac {1}{\delta }}),l,\epsilon )$ stark extraktor, sedan ovanstående konstruktion (Gen, Rep) är en $(M,m,l,t,\epsilon +\delta )$ fuzzy extraktor.

Det citerade dokumentet innehåller många generiska kombinatoriska gränser på säkra skisser och luddiga extraktorer.

Grundläggande konstruktioner

På grund av deras feltoleranta egenskaper kan säkra skisser behandlas, analyseras och konstrueras som ett $(n,k,d)_{\mathcal {F}}$ allmänt fel- korrigeringskod eller $[n,k,d]_{\mathcal {F}}$ för linjära koder, där $n$ är längden på kodord, ${\ displaystyle k}$ är längden på meddelandet som ska kodas, $d$ är avståndet mellan kodord och ${\mathcal {F}}$ är alfabetet. Om ${\mathcal {F}}^{n}$ är universum av möjliga ord kan det vara möjligt att hitta en felkorrigerande kod $C\subset {\mathcal {F }}^{n}$ så att det finns ett unikt kodord $c\in C$ för varje $w\in {\mathcal {F}}^{n}$ med a Hammaravstånd på $dis_{Ham}(c,w)\leq (d-1)/2$ . Det första steget i att konstruera en säker skiss är att bestämma vilken typ av fel som sannolikt kommer att uppstå och sedan välja ett avstånd att mäta.

Rött är kodförskjutningskonstruktionen, blått är syndromkonstruktionen och grönt representerar redigeringsavstånd och andra komplexa konstruktioner.

Hamming distans konstruktioner

När det inte finns någon risk för att data raderas och bara för att de skadas, är det bästa måttet att använda för felkorrigering Hamming-avståndet. Det finns två vanliga konstruktioner för att korrigera Hamming-fel, beroende på om koden är linjär eller inte. Båda konstruktionerna börjar med en felkorrigerande kod som har ett avstånd på $2t+1$ där ${t}$ är antalet tolererade fel.

Kodoffset konstruktion

När du använder en $(n,k,2t+1)_{\mathcal {F}}$ allmän kod, tilldela ett enhetligt slumpmässigt kodord $c \in C$ till varje $w$ , låt sedan $SS(w)=s=wc$ vilket är skiftet som behövs för att ändra $c$ till $w$ . För att fixa fel i $w'$ , subtrahera $s$ från $w'$ , korrigera sedan felen i det resulterande felaktiga kodordet för att få $c$ och slutligen lägg till $s$ till $c$ för att få $w$ . Detta betyder $Rec(w',s)=s+dec(w'-s)=w$ . Denna konstruktion kan uppnå bästa möjliga avvägning mellan feltolerans och entropiförlust när ${\mathcal {F}}\geq n$ och en Reed–Solomon-kod används, vilket resulterar i en entropiförlust på $2t\log({\mathcal {F}})$ . Det enda sättet att förbättra detta resultat skulle vara att hitta en kod bättre än Reed–Solomon.

Syndromkonstruktion

När du använder en $[n,k,2t+1]_{\mathcal {F}}$ linjär kod, låt $SS(w)=s$ är syndromet för $w$ . För att korrigera $w'$ , hitta en vektor $e$ så att $syn(e)=syn(w' )-s$ ; sedan $w=w'-e$ .

Ställ in skillnadskonstruktioner

När man arbetar med ett mycket stort alfabet eller mycket långa strängar som resulterar i ett mycket stort universum ${\displaystyle {\mathcal {U}}} ,$ kan det vara mer effektivt att behandla $w$ och $w '$ som uppsättningar och titta på uppsättningsskillnader för att korrigera fel. För att arbeta med en stor uppsättning $w$ är det användbart att titta på dess karakteristiska vektor ${\displaystyle x_{w}} ,$ som är en binär vektor med längden $n$ som har värdet på 1 när ett element $a\in {\mathcal {U}}$ och $a\in w$ , eller 0 när $a\notin w$ . Det bästa sättet att minska storleken på en säker skiss när $n$ är stor är att göra $k$ stor, eftersom storleken bestäms av $nk$ . En bra kod att basera denna konstruktion på är en $[n,nt\alpha ,2t+1]_{2}$ BCH-kod , där $n=2^{\alpha }-1$ och $t\ll n$ , så att $k\leq n-log{n \choose {t}}$ . Det är användbart att BCH-koder kan avkodas i sublinjär tid.

Stiftskisskonstruktion

Låt $SS(w)=s=syn(x_{w})$ . För att korrigera $w'$ , hitta först $SS(w')=s'=syn(x_{w}' )$ , hitta sedan en mängd v där $syn(x_{v})=s'-s$ , och beräkna slutligen den symmetriska skillnaden för att få $Rec(w',s)=w'\triangle v=w$ . Även om detta inte är den enda konstruktionen som kan användas för att ställa in skillnaden, är det den enklaste.

Redigera avståndskonstruktioner

När data kan skadas eller raderas är det bästa måttet att använda redigera avstånd . För att göra en konstruktion baserad på redigeringsavstånd är det enklaste sättet att börja med en konstruktion för inställd differens eller hammingsavstånd som ett mellanliggande korrigeringssteg, och sedan bygga redigeringsavståndskonstruktionen runt det.

Andra avståndsmåttkonstruktioner

Det finns många andra typer av fel och avstånd som kan användas för att modellera andra situationer. De flesta av dessa andra möjliga konstruktioner bygger på enklare konstruktioner, såsom konstruktioner med redigeringsavstånd.

Förbättra feltoleransen genom avslappnade föreställningar om korrekthet

Det kan visas att feltoleransen för en säker skiss kan förbättras genom att tillämpa en probabilistisk metod för felkorrigering med stor sannolikhet att lyckas. Detta tillåter potentiella kodord att överskrida Plotkin bound , som har en gräns på $n/4$ felkorrigeringar, och att närma sig Shannons bound , vilket tillåter nästan $n/2$ korrigeringar . För att uppnå denna förbättrade felkorrigering måste en mindre restriktiv felfördelningsmodell användas.

Slumpmässiga fel

För denna mest restriktiva modell, använd en BSC $_{p}$ för att skapa en $w'$ med en sannolikhet $p$ vid varje position i $w'$ att den mottagna biten är fel. Denna modell kan visa att entropiförlust är begränsad till ${\displaystyle nH(p)-o(n)} ,$ där $H$ är den binära entropifunktionen .Om min- entropi $m\geq n(H({\frac {1}{2}}-\gamma ))+\varepsilon$ sedan ${\displaystyle n({\frac {1}{2}}-\gamma )}-$ fel kan tolereras, för vissa konstanter $\gamma >0$ .

Ingångsberoende fel

För denna modell har fel inte en känd distribution och kan komma från en motståndare, de enda begränsningarna är $dis_{\text{err}}\leq t$ och att ett korrupt ord endast beror på på ingången $w$ och inte på den säkra skissen. Det kan visas för denna felmodell att det aldrig kommer att finnas fler än $t$ fel, eftersom denna modell kan redogöra för alla komplexa brusprocesser, vilket innebär att Shannons gräns kan nås; För att göra detta läggs en slumpmässig permutation till den säkra skissen som kommer att minska entropiförlusten.

Beräkningsmässigt begränsade fel

Denna modell skiljer sig från den ingångsberoende modellen genom att ha fel som beror på både ingången $w$ och den säkra skissen, och en motståndare är begränsad till polynomtidsalgoritmer för att introducera fel. Eftersom algoritmer som kan köras i bättre-än-polynomisk tid för närvarande inte är genomförbara i den verkliga världen, skulle ett positivt resultat med denna felmodell garantera att eventuella fel kan åtgärdas. Detta är den minst restriktiva modellen, där det enda kända sättet att närma sig Shannons gräns är att använda listavkodningsbara koder, även om detta kanske inte alltid är användbart i praktiken, eftersom att returnera en lista, istället för ett enda kodord, kanske inte alltid är godtagbar.

Integritetsgarantier

I allmänhet försöker ett säkert system att läcka så lite information som möjligt till en motståndare . När det gäller biometri, om information om den biometriska avläsningen läcker, kan motståndaren få veta personlig information om en användare. Till exempel märker en motståndare att det finns ett visst mönster i hjälpsträngarna som antyder användarens etnicitet. Vi kan betrakta denna ytterligare information som en funktion $f(W)$ . Om en motståndare skulle lära sig en hjälpsträng, måste det säkerställas att han från dessa uppgifter inte kan sluta sig till några uppgifter om den person från vilken den biometriska avläsningen togs.

Korrelation mellan hjälpsträng och biometrisk inmatning

Helst skulle hjälpsträngen $P$ inte avslöja någon information om den biometriska inmatningen $w$ . Detta är endast möjligt när varje efterföljande biometrisk avläsning $w'$ är identisk med originalet $w$ . I det här fallet finns det faktiskt inget behov av hjälpsträngen; så det är lätt att generera en sträng som inte på något sätt är korrelerad till $w$ .

Eftersom det är önskvärt att acceptera biometrisk inmatning $w'$ liknande $w$ , måste hjälpsträngen $P$ på något sätt vara korrelerad. Ju mer olika $w$ och $w'$ tillåts vara, desto mer korrelation blir det mellan $P$ och $w$ ; ju mer korrelerade de är, desto mer information $P$ om $w$ . Vi kan betrakta denna information som en funktion $f(W)$ . Den bästa möjliga lösningen är att se till att en motståndare inte kan lära sig något användbart från hjälpsträngen.

Gen( W ) som en probabilistisk karta

En probabilistisk karta $Y()$ döljer resultaten av funktioner med en liten mängd läckage $\epsilon$ . Läckaget är skillnaden i sannolikhet som två motståndare har att gissa någon funktion, när man kan den probabilistiska kartan och man inte gör det. Formellt:

$|\Pr[A_{1}(Y(W))=f(W)]-\Pr[A_{2}()=f(W)]|\leq \epsilon$

Om funktionen $\operatorname {Gen} (W)$ är en probabilistisk karta, så även om en motståndare känner till både hjälpsträngen $P$ och den hemliga strängen $R$ , de är bara försumbart mer sannolikt att komma på något om ämnet som om de inte visste någonting. Strängen $R$ är tänkt att hållas hemlig; så även om det läcker (vilket borde vara mycket osannolikt)m kan motståndaren fortfarande inte komma på något användbart om ämnet, så länge $\epsilon$ är liten. Vi kan betrakta $f(W)$ som vilken korrelation som helst mellan den biometriska inmatningen och någon fysisk egenskap hos personen. Inställningen $Y=\operatörsnamn {Gen} (W)=R,P$ i ovanstående ekvation ändras till:

$|\Pr[A_{1}(R,P)=f(W)]-\Pr[A_{2}()=f(W)]|\leq \epsilon$

Detta betyder att om en motståndare $A_{1}$ har $(R,P)$ och en andra motståndare $A_{2}$ inte vet någonting, är deras bästa gissningar på $f(W)$ är bara $\epsilon$ från varandra.

Enhetliga fuzzy extraktorer

Uniform fuzzy extractorer är ett specialfall av fuzzy extractors, där utsignalen $(R,P)$ av $Gen(W)$ skiljer sig försumbart från strängar plockade från den enhetliga fördelningen, dvs $(R,P)\approx _{\epsilon }(U_{\ell },U_{|P|})$ .

Enhetliga säkra skisser

Eftersom säkra skisser innebär luddiga extraktorer, möjliggör konstruktionen av en enhetlig säker skiss en enkel konstruktion av en enhetlig fuzzy extractor. I en enhetlig säker skiss är skissproceduren $SS(w)$ en slumpextraktor $Ext(w;i)$ , där $w$ är den biometriska inmatningen och $i$ är det slumpmässiga fröet . Eftersom slumpextraktorer matar ut en sträng som verkar vara från en enhetlig fördelning, döljer de all information om deras inmatning.

Ansökningar

Extraktionsskisser kan användas för att konstruera $(m,t,\epsilon )$ -fuzzy perfekt enkelriktade hashfunktioner. När den används som en hashfunktion är ingången $w$ det objekt du vill hasha. P $P,R$ som $Gen(w)$ ut är hashvärdet. Om man ville verifiera att a $w'$ inom $t$ från originalet $w$ , skulle de verifiera att $Rep(w',P)=R$ . Sådana luddiga perfekt envägs-hash-funktioner är speciella hash-funktioner där de accepterar vilken inmatning som helst med högst $t$ -fel, jämfört med traditionella hash-funktioner som bara accepterar när inmatningen matchar originalet exakt. Traditionella kryptografiska hashfunktioner försöker garantera att det är beräkningsmässigt omöjligt att hitta två olika indata som hash till samma värde. Luddiga perfekt enkelriktade hashfunktioner gör ett analogt påstående. De gör det beräkningsmässigt omöjligt att hitta två ingångar som är mer än $t$ Hamming avstånd från varandra och hash till samma värde.

Skydd mot aktiva attacker

En aktiv attack kan vara en där en motståndare kan modifiera hjälpsträngen $P$ . Om en motståndare kan ändra $P$ till en annan sträng som också är acceptabel för reproduceringsfunktionen $Rep(W,P)$ , orsakar det $Rep(W,P)$ för att mata ut en felaktig hemlig sträng ${\tilde {R}}$ . Robusta fuzzy extraktorer löser detta problem genom att tillåta reproduceringsfunktionen att misslyckas, om en modifierad hjälpsträng tillhandahålls som indata.

Robusta luddiga utdragare

En metod för att konstruera robusta fuzzy-extraktorer är att använda hashfunktioner . Denna konstruktion kräver två hashfunktioner $H_{1}$ och $H_{2}$ . Funktionen G $Gen(W)$ producerar hjälpsträngen $P$ genom att lägga till utdata från en säker skiss $\displaystyle s=SS(w) }$ till hashen för både läsningen $w$ och säker sketch $s$ . Den genererar den hemliga strängen $R$ genom att tillämpa den andra hashfunktionen på $w$ och $s$ . Formellt:

$Gen( w):s=SS(w),retur:P=(s,H_{1}(w,s)),R=H_{2}(w,s)$

Reproduceringsfunktionen $Rep(W,P)$ använder sig också av hashfunktionerna $H_{1}$ och $H_{2}$ . Förutom att verifiera att den biometriska inmatningen är tillräckligt lik den som återställs med $Rec(W,S)$ , verifierar den också att hashen i den andra delen av ${ \displaystyle P}$ härleddes faktiskt från $w$ och $s$ . Om båda dessa villkor är uppfyllda returnerar den $R$ , som i sig är den andra hashfunktionen som tillämpas på $w$ och $s$ . Formellt:

$Rep(w',{\tilde {P}}):$ Få ${\tilde {s}}$ och ${ \tilde {h}}$ från ${\displaystyle {\tilde {P}};{\tilde {w}}=Rec(w',{\tilde {s}}).} Om Δ ( w$ ~ $Delta ({\tilde {w}},w')\leq t}$ och ${\tilde {h}}=H_{1}({\tilde {w }},{\tilde {s}})$ sedan $return:H_{2}({\tilde {w}},{\tilde {s}})$ else $return:fail$

Om $P$ har manipulerats kommer det att vara uppenbart, eftersom $Rep$ kommer att misslyckas vid utmatning med mycket hög sannolikhet. För att få algoritmen att acceptera ett annat $P$ måste en motståndare hitta en ${\tilde {w}}$ så att $H_{1}(w,s)=H_{1}({\tilde {w}},{\tilde {s}})$ . Eftersom hashfunktion tros vara envägsfunktioner är det beräkningsmässigt omöjligt att hitta en sådan ${\tilde {w}}$ . Att se $P$ skulle ge en motståndare ingen användbar information. Eftersom hashfunktion återigen är envägsfunktioner är det beräkningsmässigt omöjligt för en motståndare att vända hashfunktionen och ta reda på $w$ . En del av $P$ är den säkra skissen, men per definition avslöjar skissen försumbar information om dess input. Att se $R$ (även om den aldrig borde se den) skulle på samma sätt ge en motståndare ingen användbar information, eftersom en motståndare inte skulle kunna vända hashfunktionen och se den biometriska inmatningen.

Vidare läsning

• "Fuzzy Extractors: En kort undersökning av resultat från 2004 till 2006" .
• Álvarez, F. Hernández; et al. (2007). "Biometric Fuzzy Extractor Scheme for Iris Templates" (PDF) . Spanska nationella forskningsrådet (CSIC) . Hämtad 25 mars 2022 .
• Juels, Ari; et al. (2002). "A Fuzzy Vault Scheme" (PDF) . MIT datavetenskap och artificiell intelligens Laboratory (CSAIL) . Hämtad 25 mars 2022 .

externa länkar

• "Minisketch: Ett optimerat C++-bibliotek för BCH-baserad (Pin Sketch) set-avstämning" . github.com . 31 maj 2021.