무작위 추출기

흔히 간단히 "추출기"라고 불리는 무작위 추출기는 기능인데, 약하게 무작위 엔트로피 소스의 출력에 적용되며, 짧고 균일한 무작위 시드와 함께 소스와 독립적으로 나타나며 균일하게 분포하는 고도로 무작위 출력을 생성한다.^[1]약하게 무작위 선원의 예로는 방사능 붕괴나 열 소음이 있다. 가능한 선원에 대한 유일한 제한은 선원을 완전히 제어, 계산 또는 예측할 수 있는 방법이 없고 엔트로피 속도에 대한 하한을 설정할 수 있다는 것이다.주어진 선원의 경우, 무작위 추출기는 진정한 무작위 번호 생성기(TRNG)로 간주될 수 있지만, 어떤 유형의 약한 무작위 선원에서 진정한 무작위 출력을 생성하는 것으로 입증된 단일 추출기는 없다.

때때로 '바이어스'라는 용어는 약하게 무작위 소스의 균일성 이탈을 나타내기 위해 사용되기도 하며, 구 문헌에서는 일부 추출기를 이른바 '바이어스' 소스의 무작위성을 취하여 편향되지 않은 것으로 보이는 분포를 출력하기 때문에 ^[2]언바이어싱 알고리즘이라고 부른다.약하게 무작위 선원은 항상 추출기의 출력보다 길지만 효율적인 추출기는 이 길이의 비율을 가능한 한 낮추면서 동시에 시드 길이를 낮게 유지하는 것이다.직관적으로 이것은 가능한 한 많은 임의성이 원천으로부터 "추출"되었다는 것을 의미한다.

추출기는 유사 PRG(Philogorandom generator)와 일부 개념적 유사성을 가지고 있지만 두 개념은 동일하지 않다는 점에 유의하십시오.두 가지 모두 작고 균일하게 랜덤 시드를 입력하는 함수로서, 균일하게 랜덤하게 보이는 보다 긴 출력을 생성한다.일부 유사성 생성자는 실제로 추출기도 한다.(PRG가 하드코어 술어의 존재를 기초로 할 때, 약하게 무작위적인 출처를 그러한 술어의 진리표 집합으로 생각할 수 있고, 출력이 통계적으로 균일성에 가깝다는 것을 증명할 수 있다.)^[3]그러나 일반적인 PRG 정의는 약하게 무작위 선원을 사용해야 한다고 명시하지 않으며, 추출기의 경우 출력은 통계적으로 균형에 가까워야 하지만, PRG에서는 계산적으로 균일함과 다소 약한 개념인 균일성과 구별할 수 없는 경우에만 필요하다.

NIST 특별 간행물 800-90B(초안)는 SHA 해시 패밀리를 포함한 여러 추출기를 권장하며, 엔트로피 입력량이 이들로부터 출력되는 비트 수의 2배인 경우 그 출력은 본질적으로 완전 랜덤으로 간주할 수 있다고 명시하고 있다.^[4]

추출기의 공식 정의

The min-entropy of a distribution ${\displaystyle X}$ (denoted ${\displaystyle H_{\infty }(X)}$), is the largest real number ${\displaystyle k}$ such that ${\displaystyle \Pr[X=x]\leq 2^{-k}}$ for every ${\displaystyle x}$ in the range of ${\displaystyle X}$. In essence,$$이 $측정$은 X {\$displaystyle$ X}이$($가) 가장 가능성이 높은$$ 값을 취할 가능성을 $측정$하여 랜덤$$X {\$displaystyle$ X$}$이(가$$) 나타나는 방식에 대해 최악의 경우 한계를 부여한다.$U$ ${\$$\}\}\}\{{\displaystyle 0,}$ ${\displaystyle 1{}^{\ell }}$ ${\$ $\}\}\}\},$ H ${\displaystyle {\infty \mathrm{}}_{}}$(${\displaystyle {}_{}}$ ${\displaystyle {\ell }_{}}$)${\displaystyle }$= ${\displaystystyle$ H_${\infty }(U_${\ell $}=ell$ $\}).$

최소 엔트로피 k를 사용하는$$ n비트 분포 $X{\displaystyle }$ ${\displaystyle X}$의 경우 $X{\displaystyle }$ ${\displaystyle$ X$}$은$({\displaystyle }$n$$ ,${\displaystyle }$k${\displaystyle }$) ${\displaystyle(n,k)}$ 분포라고$$ 한다.

정의(추출기): (k, ε)-extractor

Let ${\displaystyle \text{Ext}}$:${\displaystyle }${ 0${\displaystyle ,}$ ${\displaystyle 1^{}}$ ${\displaystyle {}^{}}${ ${\displaystyle 0,}$ ${\displaystyle 1{}^{}}$} ${\displaystyle d^{}}$→${\displaystyle }${ ${\displaystyle 0,}$ ${\displaystyle 1{}^{}}$} ${\displaystyle m^{}}$ ${\$$Ext}}:\{0,1\}^{n}\times \{0,1\}^{d}\to \{0,1\}^{m}}$ be a function that takes as input a sample from an ${\displaystyle (n,k)}$ distribution ${\displaystyle X}$ and a d-bit seed from ${\displaystyle U_{d}}$, and outputs an m-bit string.${\$$Ext}}$은(는) (k, ε)-추출기로, 모든${\displaystyle }$(${\displaystyle n}$ ${\displaystyle ,}$ k${\displaystyle }$) ${\displaystyle(n,k)}$ 분포$$ $X{\displaystyle }$ ${\displaystyle X}$, ${\displaystyle \text{Ext}}$ ${\$의 출력 분포.$Ext}}}$은(는) ${\displaystyle {Um}_{}}${\$displaystyle U_{m}$에 근접해 있다$.$

위의 정의에서 ε-close는 통계적 거리를 가리킨다.

직관적으로 추출기는 약하게 무작위 n비트 입력과 짧고 균일한 무작위 시드를 취하여 균일하게 랜덤해 보이는 m비트 출력을 생성한다.목표는 낮은 $d{\displaystyle }$ ${\displaystyle$ d$}($즉, 가능한 한 균일한 무작위성을 적게 사용하기 위해)와 가능한$$ $높은{\displaystyle }$ m$${\$displaystyle m$}(즉, 가능한 한 많은 무작위 비트의 출력을 내보내는 것)을 갖는 것이다.

강추출기

씨앗을 추출기의 출력과 연결하면 추출기는 여전히 균일한 분포에 가까운 분포를 생성하는 경우에 강하다.

정의(강력 추출기):A${\displaystyle }$(${\displaystyle k}$ ,${\displaystyle ϵ}$) ${\displaystyle (k,\epsilon )}$ -strong$$ extractor는 함수임

${\displaystyle {\text{Ext}:{0,1\}^{n}\time \{0,1\}^{d}\오른쪽 화살표 \{0,1\}^{m}\,}$

예를 들어${\displaystyle }$(${\displaystyle n}$, k${\displaystyle }$) ${\displaystyle (n,k)}$ $분포$ X ${\displaystyle X}$에 대해 분포 $U{\displaystyle {}_{}}$ $d$ ${\displaystyle {}_{}}$ ${\displaystyle \text{Ext}}$( ${\displaystyle X}$, ${\displaystyle U_{}}$ ${\displaystyle {}_{}}$) ${\d}\circle {\text}$$Ext}}(X,U_$${d$$})($$U{\displaystyle {}_{}}$ ${\displaystyle d_{}}$ ${\$의 두 복사본은 동일한 랜덤 변수를 나타냄$$) $is{\displaystyle }$ ${\displaystyle \epsilon }$ - ${\displaystyle {Um}_{}}$+ ${\displaystyle d_{}}$ ${\$의 균일한 분포에 근접함$.$

명시적 추출기

확률론적 방법을 사용하면 (k, ε)-추출기가 존재한다는 것을 알 수 있다. 즉, 건설이 가능하다는 것을 알 수 있다.그러나 보통 추출기가 존재한다는 것을 보여주는 것만으로는 충분하지 않다.다음과 같이 명시적인 구문이 필요하다.

정의(익명 추출기):함수 k(n), ε(n), d(n), m(n) 패밀리 Ext = {Ext_n} 함수

${\displaystyle {\text{Ext}}_{n}:\{0,1\}^{n}\time \{0,1\}^{d(n)}^{0,1\}^{m(n)}}}}}}}\오른쪽 화살표 \{0,1\}}}}}}}}}$

Ext(x, y)를 다항 시간(입력 길이)으로 계산할 수 있는 경우 명시적(k, ε)-추출기로, 모든 n에 대해 Ext는_n a (k(n), ε(n)-추출기다.

확률론적 방법에 의해 시드 길이의 a(k, ε)-추출기가 존재함을 알 수 있다.

${\displaystyle d=\log {(n-k)}+2\log \left({\frac {1}{\barepsilon }\오른쪽)+O(1)}$

및 출력 길이

${\displaystyle m}$= k${\displaystyle }$+ d${\displaystyle }$- ${\displaystyle 2}$ ${\displaystyle \log }$ ${\displaystyle }$(${\displaystyle 1\frac{\mathrm{}}{}}$ ${\displaystyle -}$ ) -${\displaystyle O}$ (${\displaystyle 1}$ ) ${\displaystyle m=k+d-2\log \left ({\frac${1$}{\barepsilon }\right)-O($1$)\}.$^[5]

디스펜서스

성질이 약한 무작위 추출기의 변형은 분산 장치다.

암호학의 무작위 추출기

암호학의 가장 중요한 측면 중 하나는 임의의 키 생성이다.^[6]반비밀이거나 어느 정도 훼손될 수 있는 출처로부터 비밀키와 임의키를 생성해야 하는 경우가 많다.하나의 짧고 비밀스러운 임의의 키를 소스로 취함으로써 추출기를 사용하여 더 긴 의사 임의의 키를 생성할 수 있고, 그 다음 공개 키 암호화에 사용할 수 있다.좀 더 구체적으로 말하면, 강력한 추출기를 사용할 때 그 출력은 균일하게 무작위로 나타날 것이며, 심지어 소스의 일부를 보는 사람에게도 나타날 것이다(전부는 아니지만).예를 들어, 출처를 알 수 있지만 씨앗을 알 수 없는 경우(또는 그 반대의 경우)이 추출기의 특성은 원하는 추출기를 노출-재발성 기능(ERF)으로 사용하는 일반적으로 노출-재발성 암호학이라고 불리는 데 특히 유용하다.노출-초기 암호화는 암호화된 정보의 송신자가 암호 해독에 필요한 정보를 수신자에게 제공해야 하는 등 암호화 애플리케이션의 초기화 중에 자주 일어나는 데이터의 초기 교환을 비밀로 하기 어렵다는 사실을 고려한다.

다음 단락은 노출-복원 암호화에 유용한 두 종류의 ERF(k-ERF와 k-APRF) 사이에 중요한 관계를 정의하고 설정한다.

Definition (k-ERF): An adaptive k-ERF is a function ${\displaystyle f}$ where, for a random input ${\displaystyle r}$ , when a computationally unbounded adversary ${\displaystyle A}$ can adaptively read all of ${\displaystyle r}$ except for ${\displaystyle k}$ bits, ${\displaystyle Pr\{A^r(f(r))=1\}-Pr}$${\displaystyle \Pr\{$$A^{r}(f(r)=1\}-\Pr\{$$A^{r}(R)=1\} \leq \epsilon (n)}$ 일부 무시해도 되는 함수$$ $ϵ{\displaystyle (n}$ )$${\$displaystyle \epsilon (n)}($아래 정의).

목표는 출력이 고도로 랜덤하고 균일하게 분포된 적응형 ERF를 구성하는 것이다.그러나 거의 동일한 확률로 모든 출력이 발생하는 더 강력한 조건이 종종 필요하다.이를 위해 거의 완벽한 복원 기능(APRF)이 사용된다.APRF의 정의는 다음과 같다.

Definition (k-APRF): A ${\displaystyle k=k(n)}$ APRF is a function ${\displaystyle f}$ where, for any setting of ${\displaystyle n-k}$ bits of the input ${\displaystyle r}$ to any fixed values, the probability vector ${\displaystyle p}$ of the output ${\displaystyle f(r)}$ over the $k{\displaystyle }$ ${\displaystyle k}$ 나머지$$ 비트에 대한 무작위 선택은 모든 $i{\displaystyle }$ ${\displaystyle i}$및$$ 일부 무시해도 되는 함수 ible($n{\displaystyle )}$에 대해 p-<$2m ϵ(n)$ > $2m ϵ($${\displaystyle n}$)$$$\$$displaysty \epsilon (n$

캄프와 주커먼은^[7] $함수{\displaystyle }$ f$${\$displaystyle f$}이$$(가) k-APRF라면 $f{\displaystyle }${\$displaystyle$f}도$$ k-ERF라는 내용의 정리를 증명했다.좀 더 구체적으로 말하면, 충분히 작은 오차를 가지고 있고 망각의 비트 고정 선원을 입력으로 삼는 추출기도 APRF이며, 따라서 k-ERF이기도 하다.보다 구체적인 추출기는 이 보조정리기로 표현된다.

보조정리: 아무거나 ${\displaystyle 2^{-m}\엡실론(n)}$-형식기 ${\displaystyle f:\{0,1\}^{n}\오른쪽 화살표 \{0,1\}^{m}}}$ …을 위해서 ${\displaystyle(n,k)}$ 인식되지 않는 비트 전송 소스, 여기서 $\displaystyle \엡실론(n)}$ K-APRF도 무시할 수 있다.

이 보조정리기는 캄프와 주커맨에 의해 증명되었다.^[7]보조기구는 출력 균일으로부터의 거리를 조사함으로써 증명되는데${\displaystyle {,}^{}}$ $출력{\displaystyle {\mathrm{}}^{}}$ 균일으로부터의 거리는 ${\displaystyle {\mathrm{2m}}^{}}$ ${\displaystyle {}^{}(n}$ ${\displaystyle )}$ ${\$$displaystyle$ 2$^{-m}\엡실론(n)}$에서 분명히$$ APRF의 조건을 만족하는 최대${\displaystyle {}^{}}2m{\displaystyle {\mathrm{}}^{}{}^{}}$($n)$이다$.$

보조정리기는 다음과 같은 정리를 유도하며, 실제로 기술한 바와 같이 k-APRF 함수가 존재한다고 명시한다.

정리(존재):For any positive constant ${\displaystyle \gamma \leq {\frac {1}{2}}}$, there exists an explicit k-APRF ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}}$, computable in a linear number of arithmetic operations on ${\displaystyle m}$-bit strings, with ${\displaystyle m=\mathrm{\Omega }(n^{2\gamma })}$${\displaystyle m=\Oomega(n^{2\gamma })$ 및$$ $k{\displaystyle }$= ${\displaystyle {}^{}}$ 1 ${\displaystyle {\frac{2}{}}^{}}$+ ${\displaystyle {\gamma }^{}}$ ${\$}2$}}+\gamma$ $\}\}\}\}\}\}.$

정의(불가결함수):이 정리의 증명에서 우리는 무시할 수 있는 함수의 정의가 필요하다.함수 $ϵ{\displaystyle }$(${\displaystyle n}$ )$${\$displaystyle \epsilon (n)}$은(는) ${\displaystyle ϵ}$(${\displaystyle }$)${\displaystyle }$= O${\displaystyle }$( ${\displaystyle \frac{{1n}^{}}{}}$ c${\displaystyle \frac{{}^{}}{}}$) ${\$ ($n)=$인 경우 무시할 수 있는 것으로 정의된다$$.모든 상수 $c{\displaystyle }$ ${\displaystyle c}$에 대한 $O\왼쪽({\frac {1}{n^{c}}\오른쪽$$).$

증명: 다음 $ϵ{\displaystyle }$ ${\displaystyle \epsilon }$ -extractor를$$ 고려하십시오.The function ${\displaystyle f}$ is an extractor for the set of ${\displaystyle (n,\delta n)}$ oblivious bit-fixing source: ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}}$. ${\displaystyle f}$ has ${\displaystyle m=\Omega (\delta ^{2}n)}$, $ϵ{\displaystyle }$= ${\displaystyle {\mathrm{}}^{}}$- ${\displaystyle c^{}}$ ${\$ c> ${\displaystyle c>1$

이 추출기가 $\Delta {\displaystyle }$Δ ${\displaystyle 1}$ {\$displaystyle$\delta $\leq 1$과(와) 함께 존재한다는 증거와 더불어 $m{\displaystyle }${\$displaystyle m}$의 길이에 대한 선형 계산 시간으로 계산할 수 있다는 사실은 제시 캄프와 데이비드 주커먼(p.1240)에 의해 논문에서 확인할 수 있다$$.

extract = 2${\displaystyle {}^{}}$-${\displaystyle c^{}}$ ${\displaystyle m^{}}$ ${\$이(가) 무시할 수 있는 함수인 만큼 이 추출기가 보조마 기준을 충족한다는 것은 사소한 사실이다.

$m{\displaystyle }$ ${\displaystyle m}$의 크기는 다음과$$ 같다.

${\displaystyle m=\Oomega(\delta ^{2}n)=\오메가(n)\geq \오메가(n^{2\gamma}}}}$

Since we know ${\displaystyle \delta \leq 1}$ then the lower bound on ${\displaystyle m}$ is dominated by ${\displaystyle n}$. In the last step we use the fact that ${\displaystyle \gamma \leq {\frac {1}{2}}}$ which means that the power of ${\displaystyle n}$ is at most ${\displaystyle 1}$$$. 그리고 $n{\displaystyle }$ ${\displaystyle n}$이(가) 양의 정수이기 때문에 n ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {\gamma }^{}}$ ${\$ n$^{2\gamma }}$은(는) 최대 $n{\displaystyle }$ ${\displaystyn}$입니다$.$

$k{\displaystyle }$ ${\displaystyle k}$ 값은 추출기의 정의를 사용하여 계산되며$$, 여기서 다음과 같이 알 수 있다.

${\displaystyle(n,k)=(n,\delta n)\Rightarrow k=\delta n}$

$m{\displaystyle }$ ${\displaystyle m}$의 값을 사용하여 다음$$ 작업을 수행하십시오.

${\displaystyle m=\cHB ^{2}n=n^{2\cHB }}}$

$이{\displaystyle }$ 값인 $m{\displaystyle }$ ${\displaystyle m}$을(를) $사용$하면 k {\$displaystyle$ k}이(가$)$ 하한인$$ 최악의 경우를 설명할 수 있다.이제 대수적 계산을 통해 다음과 같은 결과를 얻는다.

${\displaystyle \cHB ^{2}n=n^{2\cHB }}}$

${\displaystyle \Rightarrow \delta ^{2}=n^{2\gamma -1}$

${\displaystyle \Rightarrow \delta =n^{\gamma -{\frac{1}{2}}:$

$k{\displaystyle }$ ${\displaystyle k}$ 값에 삽입되어$$

${\displaystyle k}$= ${\displaystyle \Delta }$ ${\displaystyle n}$= ${\displaystyle {}^{}}$ ${\displaystyle {\Delta }^{}}$n = ${\displaystyle {1\frac{\mathrm{}}{}}^{}}$ ${\displaystyle {2n}^{}}$ ${\displaystyle =}$ ${\displaystyle n^{}}$ ${\displaystyle {+}^{}}$ + ${\displaystyle {1\frac{\mathrm{}}{}}^{}}$ ${\displaystyle {\frac{2}{}}^{}}$ ${\$frac{1}{$1}:{2}}:n=$n^{n^{\$frac{1}{1$

이는 주어진 성질을 가진 명시적 k-APRF 추출기가 존재함을 증명한다.${\displaystyle \Box }$

예

폰 노이만 추출기

아마도 가장 초기의 예는 존 폰 노이만 때문일 것이다.입력 스트림에서 그의 추출기는 한 번에 두 조각씩(첫 번째와 두 번째, 그 다음 세 번째와 네 번째 등)을 가져갔다.두 비트가 일치하면 출력이 생성되지 않았다.비트가 다르면 첫 번째 비트의 값이 출력된다.Von Neumann 추출기는 입력 비트의 분포가 균일하지 않더라도 각 비트가 1이 될 확률은 같고 연속 비트 사이에 상관관계가 없는 한 균일한 출력을 생성하는 것을 보여줄 수 있다.^[8]

따라서 반드시 p가 1/2이 아닌 베르누이 시퀀스를 입력하여 $p{\displaystyle }$= 1${\displaystyle }$/ ${\displaystyle 2}$. ${\displaystyle p=1/2.}$ 보다 일반적으로$$ 교환 가능한 시퀀스에 적용된다. 01과 10이 동일한 가능성이 있다는 사실에만 의존한다. 독립 시험의 경우, 이러한 $시퀀스$는 p.${\displaystyle \cdot }$( ${\displaystyle 1}$- ${\displaystyle p}$)${\displaystyle }$=${\displaystyle }$( 1${\displaystyle }$- ${\displaystyle p}$) ${\displaystyle \cdot }$ ${\displaystyle p}$ ${\displaystyle p\cdot (1-p)=(1-p)\cdot p$ 교환 가능한 시퀀스의 경우 확률이 더 복잡할 수 있지만 둘 다 동일할 가능성이 있다.

카오스 기계

또 다른 접근방식은 입력 스트림에 적용되는 혼돈기계의 출력을 이용하는 것이다.이 접근법은 일반적으로 혼란스러운 시스템의 특성에 의존한다.입력 비트는 기계에 밀려서 여러 동력학 시스템에서 궤도와 궤도를 진화시킨다.따라서 입력의 작은 차이는 매우 다른 출력을 생성한다.이러한 기계는 입력 비트의 분포가 균일하지 않거나 심각한 결함이 있더라도 출력이 균일하므로 약한 엔트로피 소스를 사용할 수 있다.또한 이 계획은 출력 스트림의 복잡성, 품질 및 보안을 증가시킬 수 있도록 하며, 시간 비용, 필요한 메모리 및 비밀 키의 세 가지 매개변수를 지정하여 제어한다.

암호해시함수

암호 해시함수를 임의 추출기로 사용하는 것도 가능하다.그러나 모든 해싱 알고리즘이 이 목적에 적합한 것은 아니다.^{[citation needed]}

적용들

랜덤성 추출기는 암호화 어플리케이션에 널리 사용되며, 암호 해시함수를 높은 엔트로피에 적용하지만, 디스크 드라이브 타이밍 정보나 키보드 지연과 같은 불균일한 소스가 균일하게 무작위 결과를 산출한다.

난수성 추출기는 최근 양자암호화법 개발에 한 몫을 해왔는데, 광자는 난수성 추출기에 의해 안전한 난수 비트를 생성하기 위해 사용된다.[1]

랜덤성 추출은 계산 복잡성 이론의 일부 분야에서도 사용된다.

무작위 추출은 또한 데이터를 통계에 의해 원하는, 정규 분포를 따르는 단순한 랜덤 표본으로 변환하는 데 사용된다.

참고 항목

• 장식
• 하드웨어 난수 생성기
• 임의성 합병
• 퍼지 추출기

참조

• 독립 소스 및 애플리케이션을 위한 랜덤성 추출기, Anup Rao
• 추출기 명시적 시공의 최근 발전, 로넨 샬티엘
• CBC, Cascade 및 HMAC 모드, 예브게니 도디스 등을 이용한 무작위 추출 및 키 파생
• 키 파생 및 랜덤성 추출, 올리비에 쉐바수트 등.
• 비트-고정원 및 노출-복원 암호화를 위한 결정론적 추출기, 제시 캄프 및 데이비드 주커만
• 편향된 동전 던지기(및 고급 다단계 전략의 최적성), Michael Mitzenmacher