남은 해시 보조정리

남은 해시 보조정리기는 러셀 임팔리아초, 레오니드 레빈, 마이클 루비가 처음 진술한 암호학의 보조정리체다.^[1]

여러분이 $n개$ 의 균일한 무작위 비트를 가진 비밀키 $X$ 를 가지고 있다고 상상해보십시오. 그리고 당신은 이 비밀키를 사용하여 메시지를 암호화하기를 원한다.불행히도, 당신은 열쇠를 좀 부주의하게 다루었고, 적수가 그 $키$ 의 $몇몇$ t < n 비트의 값을 배울 수 있었다는 것을 알고 있지만, 당신은 $어떤$ t 비트의 값을 알 수 없다.아직도 열쇠를 사용할 수 있니, 아니면 버리고 새 열쇠를 선택해야 하니?남은 해시 보조정리기는 $우리$ 가 약 n - t $비트$ 의 키를 만들 수 있다는 것을 말해주는데, 그 너머로 상대방은 거의 아는 바가 없다.상대방은 $n$ - $t비트$ 를 제외한 모든 것을 알고 있기 때문에, 이것은 거의 최적이다.

좀 더 정확히 말하면, 남은 해시 보조정리기는 거의 균일하게 분포된 $임의변수$ $H_{\infty }(X)$ 에서 H $H_{\infty }(X)$ ( $H_{\infty }(X)$ ) $H_{\infty }(X)$ {\ $displaystyle H_{\infit }(X)}($ $X$ )}(X의 최소 엔트로피) 비트에 대한 길이 점증약을 추출할 수 있다는 것을 알려준다.즉, $X$ 에 대해 어느 정도 부분적인 지식을 갖고 있는 적수는 추출된 가치에 대해 거의 아무런 지식이 없을 것이다.그렇기 때문에 이를 프라이버시 증폭이라고도 한다(Qumantum key distribution 기사의 프라이버시 증폭 섹션 참조).

랜덤성 추출기는 동일한 결과를 얻지만 (보통) 랜덤성을 적게 사용한다.

Let $X$ be a random variable over ${\mathcal {X}}$ and let $m>0$ . Let ${\textstyle h\colon {\mathcal {S}}\times {\mathcal {X}}\rightarrow \{0,\,1\}^{m}}$ be a 2-universal hash function.만약

{\textstyle m\leq H_{\inflit }(X)-2\log \left({\frac {1}{\barepsilon }}\오른쪽)}

${\mathcal {S}}$ ${\$ 을 ${\mathcal {S}}$ (를) 통한 $S$ 유니폼에 $대해$ X와 독립적으로 다음을 수행하십시오.

\\textstyle \delta \left[(h(S,X),S),(U,S)\right]\leq \varepsilon .}

여기서 $U$ 는 $\{0,1\}^{m}$ { $\{0,1\}^{m}$ , $\{0,1\}^{m}$ $\{0,1\}^{m}$ $\{0,1\}^{m}$ ${\$ 에 걸쳐 균일하며 $\{0,1\}^{m}$ $S$ 와는 독립적이다.^[2]

${\textstyle H_{\infty }(X)=-\log \max _{x}\Pr[X=x]}$ ${\textstyle H_{\infty }(X)=-\log \max _{x}\Pr[X=x]}$ ( ${\textstyle H_{\infty }(X)=-\log \max _{x}\Pr[X=x]}$ ) ${\textstyle H_{\infty }(X)=-\log \max _{x}\Pr[X=x]}$ = ${\textstyle H_{\infty }(X)=-\log \max _{x}\Pr[X=x]}$ - ${\textstyle H_{\infty }(X)=-\log \max _{x}\Pr[X=x]}$ ${\textstyle H_{\infty }(X)=-\log \max _{x}\Pr[X=x]}$ ${\textstyle H_{\infty }(X)=-\log \max _{x}\Pr[X=x]}$ x ${\textstyle H_{\infty }(X)=-\log \max _{x}\Pr[X=x]}$ [ ${\textstyle H_{\infty }(X)=-\log \max _{x}\Pr[X=x]}$ = ${\textstyle H_{\infty }(X)=-\log \max _{x}\Pr[X=x]}$ ${\textstyle H_{\infty }(X)=-\log \max _{x}\Pr[X=x]}$ ${\textstyle H_{\infit }}=-\log \max _{x}\Pr[X=x]}}}}$ 는 ${\textstyle H_{\infty }(X)=-\log \max _{x}\Pr[X=x]}$ X의 최소 엔트로피로서 X가 가지는 랜덤성의 양을 측정한다.최소 엔트로피는 항상 섀넌 엔트로피보다 작거나 같다.최대 ${\textstyle \max _{x}\Pr[X=x]}$ ${\textstyle \max _{x}\Pr[X=x]}$ [ ${\textstyle \max _{x}\Pr[X=x]}$ X = ${\textstyle \max _{x}\Pr[X=x]}$ ${\textstyle \max _{x}\Pr[X=x$ ]}은 $($ 는 ${\textstyle \max _{x}\Pr[X=x]}$ ) X를 정확하게 추정할 확률이라는 점에 유의하십시오. (가장 좋은 추측은 가장 가능성이 높은 값을 추측하는 것이다.)따라서 min-entropy는 $X$ 를 추측하는 것이 얼마나 어려운지를 측정한다.

$]$ $Y=v]\오른쪽 \leq 1}$ 은 ${\textstyle 0\leq \delta (X,Y)={\frac {1}{2}}\sum _{v}\left|\Pr[X=v]-\Pr[Y=v]\right|\leq 1}$ $X$ 와 Y 사이의 $통계적$ 거리다.

참고 항목

참조

^ Impagliazzo, Russell; Levin, Leonid A.; Luby, Michael (1989), "Pseudo-random Generation from one-way functions", in Johnson, David S. (ed.), Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA, {ACM}, pp. 12–24, doi:10.1145/73007.73009
^ Rubinfeld, Ronnit; Drucker, Andy (April 30, 2008), "Lecture 22: The Leftover Hash Lemma and Explicit Extractions" (PDF), Lecture notes for MIT course 6.842, Randomness and Computation, MIT, retrieved 2019-02-19

[1] Impagliazzo, Russell; Levin, Leonid A.; Luby, Michael (1989), "Pseudo-random Generation from one-way functions", in Johnson, David S. (ed.), Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA, {ACM}, pp. 12–24, doi:10.1145/73007.73009

[2] Rubinfeld, Ronnit; Drucker, Andy (April 30, 2008), "Lecture 22: The Leftover Hash Lemma and Explicit Extractions" (PDF), Lecture notes for MIT course 6.842, Randomness and Computation, MIT, retrieved 2019-02-19

[1]

[2]

Search

남은 해시 보조정리

네임스페이스

더

참고 항목

참조