퍼지 추출기

이 글에는 여러 가지 문제가 있다. 이 문제를 개선하거나 대화 페이지에서 토의하십시오. (이러한 템플릿 메시지를 제거하는 방법 및 시기 알아보기) 이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다. 기술 세부 정보를 삭제하지 않고 비전문가가 이해할 수 있도록 개선하십시오. (2014년 1월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기) 이 글은 일반적인 참고문헌 목록을 포함하고 있지만, 그에 상응하는 인라인 인용구가 충분하지 않기 때문에 대체로 검증되지 않은 상태로 남아 있다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2018년 1월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기) 이 글은 문법, 스타일, 응집력, 어조 또는 철자를 위해 복사를 필요로 할 수 있다. 편집하여 도움을 받을 수 있다. (2021년 8월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

퍼지 추출기는 생체인식 데이터를 보안용 표준암호 기법의 입력으로 사용할 수 있도록 하는 방법이다. 이런 맥락에서 '퓨지'는 암호화에 필요한 고정값을 필요한 보안을 훼손하지 않고 원래 키와 비슷하지만 동일하지는 않은 값에서 추출한다는 사실을 말한다. 한 응용 프로그램은 사용자의 생체 인식 입력을 키로 사용하여 사용자 레코드를 암호화하고 인증하는 것이다.

퍼지 추출기는 사용자의 생체 데이터로 구성된 생체 인식 템플릿을 키로 사용하여 사용자 인증을 허용하는 생체 인식 도구다. 노이즈에 대한 허용오차가 있는$$ 입력 $w{\displaystyle }$ ${\displaystyle w}$에서 균일하고 $랜덤한{\displaystyle }$ 문자열 R$${\$displaystyle$ R$}$을(를) 추출한다. 입력이 $w{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$으)로 변경되지만$$ $여전히{\displaystyle }$ w ${\displaystyle w}$에 가까우면 동일한 문자열 $R{\displaystyle }$ ${\displaystyle R}$이(가) 다시 생성된다$.$ $이$를 위해 R ${\$$displaystyle R}$을(를) 초기 계산하는 동안 프로세스는 $나중$에 R$${\$displaystyle R$}을$$(를) 복구하기 위해 저장될 도우미 $문자열{\displaystyle }$ P ${\displaystyle P}$도 출력하며, R {\$displaystyle$ R}의 보안을$훼손$하지 않고 공개될 수 있다$.$ 프로세스의 보안도 보장된다. 상대가 $P{\displaystyle }$ ${\displaystyle P}$을(를) 수정하는 경우$.$ 고정 $문자열{\displaystyle }$ R$${\$displaystyle$R}을(^[1][2]를) 계산한$$ 후에는 생체 인식 입력만으로 사용자와 서버 간의 키 합의에 사용할 수 있다.

역사

퍼지 추출기의 선구자 중 하나는 쥬얼스와 왓텐버그가 설계한 소위 "퍼지 커밋"이었다.^[2] 여기서 암호키는 생체인식 데이터를 이용하여 불용된다.

후에, 줄스와 수단은 퍼지 금고 계획을 고안했다. 이것은 퍼지 약속 체계에 불변하는 주문이며 Reed-Solomon 코드를 사용한다. 코드어는 다항식의 계수로 삽입되며, 이 다항식은 생체 데이터의 다양한 속성과 관련하여 평가된다.

퍼지 약속과 퍼지 볼트 모두 퍼지 추출기에 대한 선행자였다.

동기

퍼지 추출기가 생체 인식 및 기타 잡음이 많은 데이터에서 강력한 키를 생성하기 위해 암호화 패러다임이 이 생체 인식 데이터에 적용된다. 이는 다음을 허용해야 함을 의미한다.

(1) 생체 인식 데이터의 내용에 대한 가정 수를 제한한다(이 데이터는 다양한 출처로부터 제공되므로, 적에 의한 착취를 피하기 위해서는 입력이 예측 불가능하다고 가정하는 것이 가장 좋다).

(2) 입력에 통상적인 암호기술을 적용한다. (Fuzzy 추출기는 생체측정 데이터를 비밀스럽고 균일하게 무작위적이며 신뢰성 있게 재현 가능한 무작위 문자열로 변환한다.

이러한 기법들은 또한 인간의 기억에서 나오는 근사 데이터, 암호로 사용되는 이미지, 양자 채널에서 나오는 키와 같은 다른 유형의 잡음 입력에 대해 더 광범위한 응용 프로그램을 가질 수 있다.^[2] 신시아 드워크(ICALP 2006)의 차등 프라이버시 문서에 따르면 퍼지 추출기는 통계 데이터베이스에 대한 강력한 프라이버시 개념의 불가능성의 증명에도 응용 프로그램을 가지고 있다.

기본 정의

예측 가능성

예측가능성은 상대가 비밀키를 추측할 수 있는 확률을 나타낸다. 수학적으로 말하면 랜덤 변수 $A{\displaystyle }$ ${\displaystyle A}$의 예측 가능성은 ${\displaystyle \underset{}{최대}}$ ${\displaystyle \underset{}{P\mathrm{}}}$[ ${\displaystyle A}$= ${\displaystyle ]}$ ${\displaystyle \max _{\mathrm {a}{}P[A=a]}}$이다$.$

For example, given a pair of random variable ${\displaystyle A}$ and ${\displaystyle B}$, if the adversary knows ${\displaystyle b}$ of ${\displaystyle B}$, then the predictability of ${\displaystyle A}$ will be ${\displaystyle \max _{\mathrm {a} }P[A=a B=b]}$. So, an adversary can predict ${\displaystyle A}$ with ${\displaystyle E_{b\leftarrow B}[\max _{\mathrm {a} }P[A=a B=b]]}$. We use the average over ${\displaystyle B}$ as it is not under adversary control, but since knowing ${\displaystyle b}$ makes the prediction of ${\displaystyle A}$$반대론자$$,$ $우리$는 A에 대해 최악의 경우를 본다$.$

민엔트로피

최소 엔트로피는 최악의 엔트로피를 나타낸다. 수학적으로 ${\displaystyle \mathrm{말하면}}$ $H{\displaystyle {}_{\mathrm{}}}$∞ (${\displaystyle {}_{}}$A${\displaystyle }$)${\displaystyle }$=${\displaystyle }$- ${\displaystyle \log }$⁡${\displaystyle }$(${\displaystyle \underset{}{최대\mathrm{}}}$ ${\displaystyle \underset{}{P}}$[ ${\displaystyle A}$ =${\displaystyle a])}$ ${\displaystyle H_{\infit }}=-\log(\max _{\mathrm$ {a$} }P[A=a])}$ 로 정의된다.$$

$최소{\displaystyle }$ ${\$$displaystyle$ m$}$의 min-entropy를 가진 임의 변수를 m {\$displaystyle$ m$}$ -source라고$$ 한다$$.

통계 거리

통계적 거리는 구별성의 척도다. Mathematically speaking, it is expressed for two probability distributions ${\displaystyle A}$ and ${\displaystyle B}$ as ${\displaystyle SD[A,B]}$ = ${\displaystyle {\frac {1}{2}}\sum _{\mathrm {v} } P[A=v]-P[B=v] }$. In any system, if ${\displa$$ystyle$ $A}$은(는) $B{\displaystyle }$ ${\displaystyle B}$로 대체되며$$, 적어도 1$$-${\displaystyle S}$ ${\displaystyle D}$[ $B$의 확률로 $원래{\displaystyle \mathrm{}}$ 시스템처럼 동작한다$.$

정의 1(강력 추출기)

$M{\displaystyle }$ ${\displaystyle M}$을(를) 강력한 임의 추출기로 설정$$. The randomized function Ext: ${\displaystyle M\rightarrow \{0,1\}^{l}}$ with randomness of length ${\displaystyle r}$ is a ${\displaystyle (m,l,\epsilon )}$ strong extractor if for all ${\displaystyle m}$-sources ${\displaystyle W}$ on ${\displaystyle M(\mathrm{Ext}(W;I),I){\approx }_{ϵ}(U_{}}$${\displaystyle l_{}}$, ${\displaystyle {}_{}}$ ${\displaystyle r_{}}$)${\displaystyle }$, ${\$$displaystyle$ $M(\$displaystyle M(\$operatorname {Ext}(W;I),I)\관련된 _{\epsilon$}($U_{l},U_{r}),$ $여기$서${\displaystyle }$I = $r$${\$$displaystystyle$ I$=U_{r}$은 W$}$와 독립적이다$.$

The output of the extractor is a key generated from ${\displaystyle w\leftarrow W}$ with the seed ${\displaystyle i\leftarrow I}$. It behaves independently of other parts of the system with the probability of ${\displaystyle 1-\epsilon }$. Strong extractors can extract at most ${\displaystyle l=m-2\log \frac{1}{ϵ}+O}$${\displaystyle (}$ ${\displaystyle 1}$) 임의 $m{\displaystyle }$ ${\$$displaystyle l=m-2\log {\frac$ {1$}{\\epsilon }+O(1$) 임의 m {\$displaystyle$ m$}$ -source에서$$ 나온 비트는${\$displaystyle m} -source.

보안 스케치

보안 스케치를 사용하면 노이즈가 많은 입력을 재구성할 수 있으므로 입력이 w ${\displaystyle$ $w$$}$이고 스케치가 s ${\$$displaystyle s}$인 경우$,$ $s{\displaystyle }$$$${\$displaystyle w$}$에 가까운$$$$ $값{\displaystyle {}^{}}$$display$ {\$displaystyle$ w}을$($를$)$ $복구$할 수 있다. 그러나 스케치 $s{\displaystyle }$ ${\displaystyle s}$은$($는) 보안을 유지하기 위해 $w{\displaystyle }$ ${\displaystyle w}$에 대한 정보를 노출해서는 안 된다$$.

$M{\displaystyle \mathbb{}}$ ${\$가) 거리 함수를 디스하는 메트릭 공간인$$ 경우 Secure 스케치는 $w{\displaystyle }$ {\$displaystyle w\$${\displaystyle in\mathbb{}}$ $\mathb {M}$이$($가) w ${\displaystyle w$을(를) 표시하지 않고$$ 모든 닫힌 $문자열$에서${\displaystyle 문자열}$을 복구한다.

정의 2(보안 스케치)

$({\displaystyle m}$, ${\displaystyle m\stackrel{}{}}$~ ,${\displaystyle t}$) ${\displaystyle(m,{\tilde{m},t)}$ 보안$$ 스케치는 다음과 같은 효율적인 무작위 절차(Scotch noted SS, Recover noted Rec)의 한 쌍이다.

(1) ${\displaystyle w\mathbb{}}$M ${\$ {M$} }$ 입력에 적용된 스케치 절차 SS는 $문자열{\displaystyle }$ s ${\displaystyle \in }${ ${\displaystyle 0{}^{}}$ ${\displaystyle 1}$ ${\displaystyle {\ast }^{}}$ ${\$을(를) 반환한다$.$

복구 절차 Rec은 ${\displaystyle {\prime }^{}}$ ${\displaystyle \in }$ {\$displaystyle$ w$'\in \mathb {M}}$ 및 $s$ ${\displaystyle \in }${$1$ ${\$의 두 요소를 입력으로 사용한다$.$

(2) 정확성: ${\displaystyle d}$ ${\displaystyle i}$ ${\displaystyle s}$( ${\displaystyle w}$, ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$) ${\displaystyle \le }$ t ${\displaystyle dis(w,w')\leq t}$인 경우 $R{\displaystyle }$ ${\displaystyle e}$ ${\displaystyle c(w,,}$ ${\displaystyle S}$ (${\displaystyle }$w )${\displaystyle }$= ${\displaystyle w}${\$displaystyle Rec(w'),SS(w)=w$

(3) 보안: $M{\displaystyle }$ ${\displaystyle M}$을(를) 통한 $m{\displaystyle }$ ${\displaystyle M}$ - source의$$ $경우{\displaystyle }$ ${\displaystyle$ s$}$에 지정된$$ $W{\displaystyle }$ ${\displaystyle W}$의 최소 엔트로피가 높음$$$:$

for any ${\displaystyle (W,E)}$, if ${\displaystyle {\tilde {H}}_{\mathrm {\infty } }(W E)\geq m}$, then ${\displaystyle {\tilde {H}}_{\mathrm {\infty } }(W SS(W),E)\geq {\tilde {m}}}$.

퍼지 추출기

퍼지 추출기는 원래 입력을 복구하지 않지만 $w{\displaystyle }$ ${\displaystyle w}$에서 $문자열{\displaystyle }$ R ${\displaystyle R}($ 균일성에 가까운)을 생성하고$$ w ${\displaystyle w}$에 가까운$$ $w{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$을$($도움말 문자열 $P{\displaystyle }$ $사용).$ 강력한 $추출기$ $t{\displaystyle }$ ${\displaystyle t}$ $$= 0 및 $P{\displaystyle }$= ${\displaystyle I}$ ${\displaystyle P=I}$일 때 퍼지 추출기의 특별한 경우$.$

정의 3(퍼지 추출기)

(${\displaystyle m}$, ${\displaystyle l}$, ${\displaystyle t}$ , t ,${\displaystyle ϵ}$) ${\displaystyle (m,l,t,\epsilon )}$ 퍼지$$ 추출기는 다음과 같은 효율적인 임의 추출 절차의 한 쌍이다.

(1) Gen, given ${\displaystyle w\in \mathbb {M} }$, outputs an extracted string ${\displaystyle R\in {\mathbb {\{} 0,1\}^{l}}}$ and a helper string ${\displaystyle P\in {\mathbb {\{} 0,1\}^{*}}}$.

(2) 정확성: If ${\displaystyle dis(w,w')\leq t}$ and ${\displaystyle (R,P)\leftarrow Gen(w)}$, then ${\displaystyle Rep(w',P)=R}$.

(3) 보안: For all m-sources ${\displaystyle W}$ over ${\displaystyle M}$, the string ${\displaystyle R}$ is nearly uniform even given ${\displaystyle P}$, So ${\displaystyle {\tilde {H}}_{\mathrm {\infty } }(W E)\geq m}$, then ${\displaystyle$$(R,P,E)\reasoning (U_{\mathrm {l} },P,E$

그래서 퍼지 추출기는 암호 응용 프로그램을 (비밀 키로) 사용하기 위한 필수 조건인 거의 동일한 무작위 비트 시퀀스를 출력한다. 출력 비트가 약간 균일하지 않기 때문에 보안이 저하될 위험이 있지만 균일한 분포로부터의 거리는 $ϵ{\displaystyle }$ ${\displaystyle \epsilon }$에 지나지 않으며$$, 이 거리가 충분히 작으면 보안이 적절하게 유지될 것이다.

안전한 스케치 및 퍼지 추출기

안전한 스케치는 퍼지 추출기를 만드는 데 사용될 수 있다. $s{\displaystyle }$ ${\displaystyle s}$을(를) 얻기 위해$$ $w{\displaystyle }$ {\displaystyle w}에 SS를 적용하고 r ${\displaystyle R}$을(를${\displaystyle )}$ 얻기 위해$$ $w{\displaystyle }$ ${\displaystyle w}$에 강한 추출기 Ext를 적용하는 것과 마찬가지로$,$ $r{\displaystyle }$$${\$displaystystyle R$$}$을($s, s)$로 저장할$$ 수 있다$.$$}$ can be reproduced by ${\displaystyle w'}$ and ${\displaystyle P=(s,x)}$. ${\displaystyle Rec(w',s)}$ can recover ${\displaystyle w}$ and ${\displaystyle Ext(w,x)}$ can reproduce ${\displaystyle R}$. The following lemma formalizes this.

보조정리 1 (스케치에서 퍼지 추출기)

가정(SS,Rec)은${\displaystyle }$(${\displaystyle M,}$ ${\displaystyle m,}$ m${\displaystyle \stackrel{}{,}}$ ${\displaystyle m}$ ~${\displaystyle }$, t${\displaystyle }$) ${\displaystyle(M,m,{\tilde {{m},t)}$ 보안$$ 스케치이며 Ext를 평균 케이스$n$ ${\displaystyle m\stackrel{}{}}$~${\displaystyle }$, ${\displaystyle l,}$ $){\tilde},$l$, 엡실론 )$로 한다. Then the following (Gen, Rep) is an ${\displaystyle (M,m,l,t,\epsilon )}$ fuzzy extractor: (1) Gen ${\displaystyle (w,r,x)}$: set ${\displaystyle P=(SS(w;r),x),R=Ext(w;x),}$ and output ${\displaystyle (R,P)}$. (2) Rep ${\displaystyle (w^{\prime }}$${\displaystyle {}^{},}$( ${\displaystyle s}$, ${\displaystyle x}$)${\displaystyle (w'$ ,($s,x$ $복구{\displaystyle }$ w${\displaystyle }$= R ${\displaystyle e}$ ${\displaystyle c}$(${\displaystyle w}$ ${\displaystyle {\prime }^{}}$, s${\displaystyle }$) ${\displaystyle w=Rec(w',s)}$ 및 $출력$ R${\displaystyle }$= E ${\displaystyle x}$ t${\displaystyle }$(${\displaystyle w}$; ${\displaystyle x}$) ${\displaysty R=Extext(w;x$

Proof: From the definition of secure sketch (Definition 2), ${\displaystyle H_{\infty }(W SS(W))\geq {\tilde {m}}}$. And since Ext is an average-case ${\displaystyle (n,m,l,\epsilon )}$-strong extractor. ${\displaystyle SD((Ext(W;X),SS(W),X),(U_{l},SS(W),X))=SD((R,P),(U_{l},P))\leq \epsilon .}$

코롤러리 1

If (SS,Rec) is an ${\displaystyle (M,m,{\tilde {m}},t)}$ secure sketch and Ext is an ${\displaystyle (n,{\tilde {m}}-log({\frac {1}{\delta }}),l,\epsilon )}$ strong extractor, then the above construction (Gen,Rep) is a ${\displaystyle$$(M,m,l,t,\epsilon +\delta )}$ 퍼지$$ 추출기

참조 문서는 보안 스케치와 퍼지 추출기에 대한 많은 일반 결합 한계를 포함한다.^[2]

기본 구성

Due to their error tolerant properties, secure sketches can be treated, analyzed, and constructed like a ${\displaystyle (n,k,d)_{\mathcal {F}}}$ general error correcting code or ${\displaystyle [n,k,d]_{\mathcal {F}}}$ for linear codes, where ${\displaystyle n}$ is the length of codewords, $k{\displaystyle }$ ${\displaystyle k}$은(는) 코드화할 메시지의 길이, d ${\displaystyle d}$은(는) 코드 워드 사이의 거리, $F{\displaystyle \mathcal{}}$ ${\$은(는) 알파벳이다. If ${\displaystyle {\mathcal {F}}^{n}}$ is the universe of possible words then it may be possible to find an error correcting code ${\displaystyle C\subset {\mathcal {F}}^{n}}$ such that there exists a unique codeword ${\displaystyle c\in C}$ for every ${\displaystyle w\in {$$\mathcal{F}^{n}$ 해밍 거리가 d $i{\displaystyle }$ ${\displaystyle s}$ ${\displaystyle {}_{}}$ ${\displaystyle a_{}}$ ${\displaystyle m_{}c,}$ ${\displaystyle w}$) ${\displaystyle ((d\mathrm{}}$-${\displaystyle 1}$ ) / 2 ${\displaystyle dis_{Ham}(c,w)\leq(d-1)/2}$인 \mathcal{F}^{n}. 보안 스케치 구성을 위한 첫 번째 단계는 발생할 수 있는 오류 유형을 결정한 후 측정할 거리를 선택하는 것이다$.$

해밍 거리 구조

데이터가 삭제될 위험이 없고 데이터만 손상될 경우 오류 보정에 사용할 수 있는 최선의 측정값은 해밍 거리입니다. 해밍 오류는 코드가 선형인지 아닌지에 따라 두 가지 일반적인 구조로 수정된다. 두 구성 모두 거리가 ${\displaystyle \mathrm{2t}}$+ ${\displaystyle 1}$ ${\displaystyle 2t+1}$인 코드 수정 오류로 시작하며, $여기$서 t ${\$은(는) 허용되는 오류 수입니다.

코드 오프셋 구성

When using a ${\displaystyle (n,k,2t+1)_{\mathcal {F}}}$ general code, assign a uniformly random codeword ${\displaystyle c\in C}$ to each ${\displaystyle w}$, then let ${\displaystyle SS(w)=s=w-c}$ which is the shift needed to change ${\displaystyle c}$ into ${\displaystyle w}$ ${\displaystyle w}.$w${\displaystyle {}^{}}w{\displaystyle {}^{}}$ {\$displaystyle w'}$의 오류를 수정하려면 $w{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$에서 s ${\$$displaystyle$ s$}$을(를) 뺀 다음$$ $잘못된$ 코드 $워드$의 $오류$를 수정하여$$ c ${\displaystystyle$ $c$$}$에 마지막으로 s${\$$w$를 $가져오십시오$.$tyle w}$. This means ${\displaystyle Rec(w',s)=s+dec(w'-s)=w}$. This construction can achieve the best possible tradeoff between error tolerance and entropy loss when ${\displaystyle {\mathcal {F}}\geq n}$ and a Reed–Solomon code is used resulting in an entropy loss of ${\displaystyle 2}$${\displaystyle t}$ ${\displaystyle \log }$ ${\displaystyle }$(${\displaystyle F}$) ${\displaystyle 2t\log({\mathcal {F})}$. 더 나은 방법은 리드-솔로몬보다 더 나은 암호를 찾는 것뿐일 것이다.

신드롬 건설

When using a ${\displaystyle [n,k,2t+1]_{\mathcal {F}}}$ linear code let the ${\displaystyle SS(w)=s}$ be the syndrome of ${\displaystyle w}$. To correct ${\displaystyle w'}$ find a vector ${\displaystyle e}$ such that ${\displ$$aystyle syn(e)=$$syn{\displaystyle }$$(w$ $w$${\displaystyle }$= ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$- ${\displaystyle e}$ ${\displaystyle w=w'-e$ .

차이 구성 설정

매우 큰 알파벳 문자나 매우 긴 문자열로 작업하여 매우 큰 우주 $U{\displaystyle \mathcal{}}$ ${\$을(를) 생성할 때 $w{\displaystyle }$ ${\displaystyle w}$ 및 w${\displaystyle {}^{}}w$ ${\$ w$'}$을(를) 세트로 처리하고 설정된$$ 차이를 살펴 오류를 수정하는 것이 더 효율적일 수 있다$.$ ${\displaystyle 큰\mathcal{}}$ $집합{\displaystyle }$w {\$displaystyle w}$과(와$)$ 함께 작업하려면${\displaystyle }$vector U {\$displaystyle$ a\$in$${\$$mathcal {U}$일${\displaystyle }$때 값이 1인$$ 길이 $n{\displaystyle }$ ${\displaystyle n}$의 2진 벡터인 특성 벡터$$$x{\displaystyle {}_{}}$ ${\displaystyle w_{}}$ ${\displaystystyle a\in w$ 또는 0을 살펴보는 것이 유용하다. ${\displaystyle \notin }$ $[\displaystyle a\notin$ w$\}.$ The best way to decrease the size of a secure sketch when ${\displaystyle n}$ is large is make ${\displaystyle k}$ large since the size is determined by ${\displaystyle n-k}$. A good code to base this construction on is a ${\displaystyle [n,n-t\alpha ,2t+1]_{2}}$ BCH code where $$${\displaystyle n}$$$${\displaystyle }$= ${\displaystyle {2\alpha }^{}}$- ${\displaystyle 1}$ ${\displaystyle n=2^{\alpha$ }-$1,$ t$$${\displaystyle \mathrm{tn}}$ ${\displaystyle$ t$\ll$ n$}, k$$$ ${\displaystyle n}$ - ${\displaystyle lo}$ g (${\displaystyle n\genfrac{}{}{0ex}{}{t}{}}$ ) $displaystyleq n-log${n$\t},$ BCH 코드가 하위 선형으로 디코딩될 수 있는 것도 유용하다$.$

핀 스케치 구조

${\displaystyle \mathrm{Let}}$ $S{\displaystyle }$( ${\displaystyle w}$)${\displaystyle }$= s${\displaystyle }$= ${\displaystyle s}$ ${\displaystyle y}$ n${\displaystyle }$( ${\displaystyle {}_{}}$ ${\displaystyle w_{}}$) ${\displaystyle SS(w)=s=syn(x_{w})}$. To correct ${\displaystyle w'}$ first find ${\displaystyle SS(w')=s'=syn(x_{w}')}$, then find a set v where ${\displaystyle syn(x_{v})=s'-s}$, finally compute the symmetric difference to get ${\displaystyle Re$$c(w',s)=w'\triangle v=w$ 차이를 설정하는 데 사용할 수 있는 구조는 이것만이 아니지만 가장 쉬운 구조다.

거리 구성 편집

데이터가 손상되거나 삭제될 수 있는 경우 가장 좋은 측정은 거리 편집이다. 편집 거리를 기준으로 시공하려면 중간 보정 단계로서 설정 차이 또는 해밍 거리에 대한 시공부터 시작한 다음 그 주위에 편집 거리 시공부터 하는 것이 가장 쉽다.

기타 거리 측정 구성

다른 상황을 모형화하는 데 사용될 수 있는 많은 유형의 오류와 거리가 있다. 이러한 다른 가능한 구성의 대부분은 거리 구성 편집과 같은 단순한 구성에 기초한다.

완화된 정확성 개념을 통해 오류 허용 오차 개선

오류 수정에 확률론적 방법을 적용하고 높은 확률로 오류 수정만 요청하면 보안 스케치의 오류 허용오차를 개선할 수 있음을 알 수 있다. 이렇게 하면 플롯킨 바운드를 초과할 수 있으며, 이 바운드는 $n{\displaystyle }$/ ${\displaystyle 4\mathrm{}}$ ${\displaystyle n/4}$ 오류를$$ 수정하고 섀넌의 바운드에 근접하여 거의 ${\displaystyle n\mathrm{}}$/ 2 ${\displaystyn/2} 수정$ 작업을$$ 허용한다. 이렇게 강화된 오류 보정을 달성하려면 보다 제한적인 오류 분포 모델을 사용해야 한다.

무작위 오류

이 가장 제한적인 모델의 경우 ${\displaystyle {}_{}}$ p ${\$를 사용하여$$ 비트가 수신된$$ w${\displaystyle {}^{}}$′ ${\$의 각 위치에서 확률$$ $p{\displaystyle }$ ${\displaystyle p}$이(가) 잘못되었다는$$ $w{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ w$'}$을 생성한다. This model can show that entropy loss is limited to ${\displaystyle nH(p)-o(n)}$, where ${\displaystyle H}$ is the binary entropy function, and if min-entropy ${\displaystyle m\geq n(H({\frac {1}{2}}-\gamma ))+\varepsilon }$ then ${\displaystyle n({\fra$$c {1}{2}}-\message )}$개의$$ 오류는 일부 상수 > ${\displaystyle \$ \ >$0}$에 대해 허용할 수 있다

입력 종속 오류

이 모델 오류는 알려진 분포를 가지고 있지 않고 상대 모델에서 발생할 수 있으므로, $유일$한 제약조건은 d ${\displaystyle i}$ ${\displaystyle {}_{}{\text{err}}_{}}$ err $($오류 err) {\$displaystyle dis_{\text{err}\leq$ t$}$이며, 손상된 단어는 보안 스케치가$$아닌 $입력$ w {\$displaystystyle$w}에만 의존한다는 것이다. 이 오류 모델에 대해 이 모델은 모든 복잡한 소음 프로세스를 설명할 수 있기 때문에, 즉 섀넌의 한계치에 도달할 수 있기 때문에, 이를 위해 무작위 순열화가 엔트로피 손실을 줄이는 보안 스케치에 선행되기 때문에 $t{\displaystyle }$ ${\디스플레이$ 스타일 $t}$ 이상의 오차는$$ 결코 없을 것임을 보여줄 수 있다.

계산적으로 한정된 오류

이는 입력 $w{\displaystyle }$ ${\displaystyle w}$과(와) 보안 스케치 모두에 의존하는 오류를 갖는 입력 종속 모델과 다르며, 적수는 오류를 도입하기 위한 다항 시간 알고리즘으로 제한된다. 다항식 시간보다 더 잘 실행할 수 있는 알고리즘은 현재 현실 세계에서 실현 가능하지 않기 때문에, 이 오류 모델을 사용한 긍정적인 결과는 어떤 오류도 고칠 수 있음을 보장할 것이다. 단일 암호문 대신 목록을 반환하는 것이 항상 허용되는 것은 아닐 수 있으므로 실제로는 항상 유용하지는 않을 수 있지만 섀넌의 바인딩에 접근하는 유일한 방법은 목록 해독 가능한 코드를 사용하는 것이다.

프라이버시 보장

일반적으로 보안 시스템은 가능한 한 적은 정보를 적에게 유출하려고 시도한다. 생체 측정의 경우 생체 측정 판독에 대한 정보가 유출되면 상대방은 사용자에 대한 개인 정보를 학습할 수 있을 것이다. 예를 들어, 상대방은 도우미 문자열에 사용자의 민족성을 암시하는 일정한 패턴이 있음을 알아차린다. $만약{\displaystyle }$ 적수가 도우미 문자열을 배운다면$,$ 이 $데이터$로부터 생체 측정 판독을 받은 사람에 대한 어떤 데이터도 유추할 수 없다는 것을 확실히 ${\displaystyle \mathrm{해야}}$ 한다${\displaystyle .}$

도우미 문자열과 생체 인식 입력 간의 상관 관계

이상적인 경우 도우미 문자열 $P{\displaystyle }$ ${\displaystyle$ $P$$}$은(는$)$ $생체{\displaystyle }$ 인식 입력에 대한 정보를 표시하지 않는다$$$displaystyle$ w$}).$ 이는 $이후$의 모든 생체 인식 판독값이 원본 w ${\displaystyle w}$과(와$$) 같을 때만 가능하다$.$ 이 경우 도우미 문자열은 실제로 필요하지 않다., 따라서 $w{\displaystyle }$ ${\displaystyle w}$과(와) 전혀 상관되지 않는 문자열을 생성하는 것은 쉽다$.$

$w{\displaystyle }$${\displaystyle {}^{}}$${\displaystyle w}$과(와) 유사한$$ $생체{\displaystyle {}^{}}$ 인식 입력 ${\$ w$'}$을(를) 받아들이는 것이 $바람직하므로$ 도우미 문자열 $P{\displaystyle }$ ${\displaystyle$ P$}$은(는) 어떻게든 상관되어야 한다$$. $w{\displaystyle }$ ${\displaystyle w}$과 $w{\displaystyle {}^{}}$$\$ {\$displaystyle$w$'}$이(가$$) 서로 $더{\displaystyle }$ 다를수록$P$ {\$displaystyle$ $P{\displaystyle }$}과$($와) 더 많은 상관관계가 있을 $것$이고$,$ P {\$displaystyle$ P$}$이($가)$ w {\$displaystystyle$ w}에 대해 더$$ 많은 정보를 공개하는 것을 고려할 수 있다$.$ 함수 $f{\displaystyle (W}$ ) ${\displaystyle f(W)}$이 되기 위한 정보$.$ 가장 좋은 해결책은 상대가 도우미 문자열에서 유용한 것을 배울 수 없도록 하는 것이다.

확률적 지도로서의 Gen(W)

확률론적 지도 $Y{\displaystyle }$(${\displaystyle }$) ${\displaystyle$ Y$()}$은(는$)$ 소량의 $누출$이 있는 함수의 결과를 $숨긴다${\$displaystyle$ \epsilon$\}.$ 누설은 확률론적 지도를 알고 있고 한 명이 추측하지 못할 때 두 적수가 어떤 함수를 추측할 확률의 차이다. 공식:

$[\displaystyle \Pr]A_{1}(Y(W)=f(W)]-\Pr[A_{2}()=f(W)] \leq \엡실론 }$

${\displaystyle \mathrm{Gen}}$ ${\displaystyle }$( ${\displaystyle W}$) ${\displaystyle \operatorname {Gen}(W)$ 기능이 확률론적 지도라면$$, 상대가 도우미 $문자열{\displaystyle }$ P ${\displaystyle P}$과 비밀 $문자열{\displaystyle }$ R ${\displaysty R}$을 모두 알고 있더라도 그들은 아무것도$$ 모르는 것처럼 주제에 대해 뭔가를 알아낼 가능성이 무시해도 될 뿐이다. 문자열 $R{\displaystyle }$ ${\displaystyle R}$은(는) 비밀로 하기로 되어$$ 있기 때문에 (매우 가능성이 희박하지 않을 것) $유출$되더라도 {$${\$displaystyle \epsilon }}$이(가$$) 작다면 상대방은 여전히 주제에 대해 유용한 것을 알아낼 수 없다. $우리$는 f${\displaystyle }$( ${\displaystyle W}$) ${\displaystyle f(W)}$을(를) 생물학적 입력과 그 사람의 신체적 특성 사이의 어떤 상관관계라고 생각할$$ 수 있다. $위{\displaystyle }$ 방정식에서$$ Y${\displaystyle }$= ${\displaystyle \mathrm{Gen}}$ ${\displaystyle }$( W${\displaystyle }$)${\displaystyle }$= ${\displaystyle R}$, ${\displaystyle P}$ ${\displaystyle Y=\operatorname {Gen}(W)=R,P}$을(를) 설정하면 다음과 같이 변경된다.

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

이는 한 적수 A $1{\displaystyle {}_{}}$ ${\$ ${\displaystyle \mathrm{A\_}}$${1}$에 (R ,${\displaystyle }$P${\displaystyle }$) ${\디스플레이스타일(R,P)}$이$({\displaystyle }$가) 있고$$ 두 번째 $적수{\displaystyle {}_{}}$ A ${\displaystyle {2\mathrm{}}_{}}$ ${\$ $아무것$도 모르면$$ f${\displaystyle }$(${\displaystyle W}$) ${\디스플레이스타일 f(W)}$에서 그들의 최선의 추측은 $ϵ{\displaystyle }$ ${\디스플레이스타일 \epsilon}$밖에 차이가 나지 않는다는$$ 것을 의미한다.

균일한 퍼지 추출기

Uniform fuzzy extractors are a special case of fuzzy extractors, where the output ${\displaystyle (R,P)}$ of ${\displaystyle Gen(W)}$ are negligibly different from strings picked from the uniform distribution, i.e. ${\displaystyle (R,P)\approx _{\epsilon }(U_{\el$$l{{P }}}}$

균일한 보안 스케치

보안 스케치는 퍼지 추출기를 의미하므로, 균일한 보안 스케치를 구성하면 균일한 퍼지 추출기를 쉽게 구성할 수 있다. 동일한 보안 스케치에서 스케치 $절차{\displaystyle }$ ${\displaystyle S}$( ${\displaystyle w}$) ${\displaystyle SS(w)}$은 랜덤성 $추출기{\displaystyle }$ E x ${\displaystyle t}$( ${\displaystyle w}$; ${\displaystyle i}$) ${\displaystyle Ext(w;i)}$입니다$.$ 여기서 $w{\displaystyle }$ ${\displaystyle w}$은 생체인식 입력이고 i ${\displaystystyle$ i$}$은 랜덤 시드입니다. 랜덤성 추출기는 균일한 분포에서 나온 것으로 보이는 문자열을 출력하기 때문에 입력에 대한 모든 정보를 숨긴다.

적용들

추출기 스케치는${\displaystyle }$(${\displaystyle m}$ , t , ${\displaystyle ϵ}$) ${\displaystyle (m,t,\epsilon )}$ -fuzzy$$ 완벽히 단방향 해시함수를 구성하는 데 사용될 수 있다. 해시 함수로 사용할 경우 입력 $w{\displaystyle }$ ${\displaystyle$ w$}$은(는) 해시할 개체임$$. $G{\displaystyle }$ ${\displaystyle e}$ ${\displaystyle n}$( w${\displaystyle }$) ${\displaystyle Gen(w)}$ 출력하는$$$$ $P{\displaystyle }$, R ${\displaystyle P,R}$은 해시 값이다. If one wanted to verify that a ${\displaystyle w'}$ within ${\displaystyle t}$ from the original ${\displaystyle w}$, they would verify that ${\displaystyle Rep(w',P)=R}$. ${\displaystyle (m,t,\epsilon )}$-fuzzy perfectly one-way hash functions are special hash functions 입력이 원본과 정확히 일치할 때만 수용하는 기존 해시함수와 비교하여 대부분의 $t{\displaystyle }$ ${\displaystyle t}$ 오류가$$ 있는 입력을 허용한다. 기존의 암호해시함수는 동일한 값으로 해시하는 두 개의 다른 입력을 찾는 것이 계산상 불가능하다는 것을 보증하려고 시도한다. 퍼지 완벽하게 단방향 해시함수는 유사한 주장을 한다. 그들은 계산적으로 실현 불가능한 두 개의 입력을 찾도록 하는데, 두 입력이 $t{\displaystyle }$ {\$displaystyle t}$ Hamming$$ 거리 이상 떨어져 동일한 값으로 해시된다$.$

활성 공격으로부터 보호

An active attack could be one where the adversary can modify the helper string ${\displaystyle P}$. If the adversary is able to change ${\displaystyle P}$ to another string that is also acceptable to the reproduce function ${\displaystyle Rep(W,P)}$, it causes ${\displaystyle Rep(W,P)}$ to 잘못된 비밀 문자열 $R{\displaystyle \stackrel{}{}}$~ ${\$ 수정된 도우미 문자열이 입력으로 제공되는 경우 재생산 기능이 실패하도록 하여 강력한 퍼지 추출기가 이 문제를 해결한다.

강력한 퍼지 추출기

강력한 퍼지 추출기를 구성하는 한 가지 방법은 해시함수를 사용하는 것이다. 이$$ 시공에는 2개의 해시함수 $H{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$1}와 H$$2 {\$displaystyle H_{2$}}개가 필요하다$.$ $G{\displaystyle }$ ${\displaystyle e}$ ${\displaystyle n}$( W${\displaystyle }$) ${\displaystyle Gen(W)}$ 함수는$$ 보안 $스케치{\displaystyle }$ s${\displaystyle }$= ${\displaystyle S}$( ${\displaystyle w}$) ${\$$displaystyle s(w$$)$의 출력을 판독$$w {\$displaystyle{\displaystyle }$ w$}$와 $보안$ 스케치$$ s {\$displaystyle$ s}의 해시에 추가하여$$$$ 도우미 $문자열{\displaystyle }$ P$$$\{\backslash$$displaystystystyle{\displaystyle }$ P}을 생성한다.$\displaystyle R}$ by applying the second hash function to ${\displaystyle w}$ and ${\displaystyle s}$. Formally: ${\displaystyle Gen(w):s=SS(w),return:$$P=(s,H_{1}(w,s),$$R=H_{2}(w,s)}$

The reproduce function ${\displaystyle Rep(W,P)}$ also makes use of the hash functions ${\displaystyle H_{1}}$ and ${\displaystyle H_{2}}$. In addition to verifying the biometric input is similar enough to the one recovered using the ${\displaystyle Rec(W,S)}$ function, it also $P{\displaystyle }$ ${\displaystyle P}$의 두 번째 부분에 있는 해시가 $실제로{\displaystyle }$ w$${\$displaystyle w}$ 및 $s{\displaystyle }${\$displaystyle$s}에서$$ 파생되었는지$$ 검증한다$.$ 이 두 조건이 모두 충족되면 $R{\displaystyle }$ ${\displaystyle R}$을 반환하며, 이는$$ $w{\displaystyle }$ ${\displaystyle$ $w$$}$ 및$$ $s{\displaystyle }$ ${\daystyle$ s$}$에 적용된 두 번째 해시함수이다$.$ Form s. Formally:

${\displaystyle Rep(w',{\tilde {P}}):}$ Get ${\displaystyle {\tilde {s}}}$ and ${\displaystyle {\tilde {h}}}$ from ${\displaystyle {\tilde {P}};{\tilde {w}}=Rec(w',{\tilde {s}}).$$\Delta {\displaystyle \mathrm{}(w\stackrel{}{}}$~ ,${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ )${\displaystyle )}$ ${\displaystyle t}$ ${\displaystyle \Delta({\tilde{w},w')\$$leq{\displaystyle \stackrel{}{}}$ $t}$ 및$$ h${\displaystyle \stackrel{}{}}$~${\displaystyle }$= H ${\displaystyle {1\mathrm{}}_{}w\stackrel{}{}}$~ ,${\displaystyle s\stackrel{}{}}$~${\displaystyle }$) ${\displaystyle {\tilde{h}}=$인 경우$$$H_{1}({\tilde{w},{\tilde {s}})}$ 다음에$$ $r{\displaystyle }$ ${\displaystyle e}$ ${\displaystyle e}$ t ${\displaystyle u}$ r ${\displaystyle n}$: H ${\displaystyle {2\mathrm{}}_{}w\stackrel{}{}}$~${\displaystyle }$,${\displaystyle \stackrel{}{}s\stackrel{}{}}$ ~${\displaystyle }$) ${\displaystyle return:$$H_{2}({\tilde{w},{\tilde {s}})$ 다른 $r$ e ${\displaystyle t}$ ${\displaystyle u}$ ${\displaystyle r}$ n${\displaystyle }$: ${\displaystyle f}$ ${\displaystyle a}$ ${\displaystyle l}$ ${\displaystyle return:fail}$

$P{\displaystyle }$ ${\displaystyle P}$을(를) 임의로 변경했다면$$ R ${\displaystyle e}$ p ${\displaystyle Rep}$이(가) 출력되지 않고 매우 높은 확률로 발생하기$$ 때문에 명백할 수 있다. 알고리즘이 다른 $P{\displaystyle }$ ${\displaystyle P}$을(를) 수용하도록 하려면 상대방은$$ H ${\displaystyle {1\mathrm{}}_{}w}$, ${\displaystyle s}$ ${\displaystyle )}$= ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}w\stackrel{}{}}$~ ,${\displaystyle s\stackrel{}{}}$~${\displaystyle }$) ${\displaystyle H_{1}(w,s)=$와 같은$$ $w{\displaystyle \stackrel{}{}}$~ ${\$을 찾아야 한다.$H_{1}({\tilde{w}},{\tilde{s$ 해시함수는 단방향 함수로 간주되기 때문에 이러한 $w{\displaystyle \stackrel{}{}}$~ ${\$을(를) 찾는 것이 계산상 불가능하다$.$ $P{\displaystyle }$ ${\displaysty P}$를 보면 상대에게 유용한 정보가 없을 것이다$$. 다시 말하지만 해시함수는 일방 함수가므로 상대방은 해시함수를 $역행$하여 w$${\$displaystyle w}$을(를) 알아내는 것이 계산상 불가능하다$.$ $P{\displaystyle }$ ${\displaystyle P}$의 일부가 보안 스케치지만$$, 정의상 스케치는 그 입력에 대해 무시할 수 없는 정보를 드러낸다. 이와 $유사$하게 R ${\displaystyle$ R$}$을(를) 보면($$그것은 절대 보면 안 되겠지만) 상대는 해시함수를 되돌릴 수 없고 생체인식 입력을 볼 수 없기 때문에 상대에게 유용한 정보를 제공하지 못할 것이다.

참조

• "Fuzzy Extractors: A Brief Survey of Results from 2004 to 2006".
• "Biometric Fuzzy Extractor Scheme for Iris Templates" (PDF). {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)
• "A Fuzzy Vault Scheme" (PDF). {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)

외부 링크

• "Minisketch: An optimized C++ library for BCH-based (Pin Sketch) set reconciliation". github.com. 31 May 2021.