이러한 기능 중 PRF는 무엇입니까?
그것을 가정 $F: \{0,1 \}^n \rightarrow \{0,1 \}^n$PRF입니다. 다음 기능이 PRF인지 확인하십시오.
$$ \begin{align} 1. \, F_1(k,x) &= F(k,x) \oplus x \\ 2. \, F_2(k,x) &= F\left(F(k,0^n), x\right) \\ 3. \, F_3(k,x) &= F\left(F(k,0^n), x\right)|| F(k,x) \end{align} $$
어디 $||$ 연결을 나타냅니다.
시도:
에 대한 $1.$ 표준 구분자는 다음과 같습니다. $x_1 \oplus x_2 == y_1 \oplus y_2$, 어디 $x_1, x_2$ 두 개의 입력이고 $y_1, y_2$각각 출력입니다. 그래서$F_1$ PRF가 아닙니다.
에 대한 $2.$ 나는 그것을 믿는다 $F(k,0^n) = k'$ 키 역할을하므로 $F_2(k',x) = F(k',x)$ 여전히 PRF 여야합니다.
에 대한 $3.$ 두 개의 의사 난수 출력을 함께 결합하여 산출하기 때문에 두 PRF의 연결은 여전히 PRF라고 말할 수 있습니다. $F_3$의 출력.
내 결과를 확인할 수 있습니까?
답변
안타깝게도 모든 세부 사항에 대해 설명 할 시간이 없지만 올바른 길로 안내하는 데 충분할 수 있습니다.
1. PRF입니다.
증명 아이디어 :
구별자가 있다고 가정합니다. $\mathcal{D}_{F_1}$ 구별 $F_1$무시할 수없는 확률을 가진 랜덤 함수에서. 그런 다음 구별자를 구성 할 수 있습니다.$\mathcal{D}_F$ 구별 $F$ 무시할 수없는 확률을 가진 랜덤 함수에서.
$\mathcal{D}_F$ 오라클에 대한 액세스 권한이 부여됨 $f(\cdot)$ 그 중 하나입니다 $F(k, \cdot)$ 또는 임의의 함수 $g(\cdot)$.
$\mathcal{D}_F$ 달리다 $\mathcal{D}_{F_1}$질문에 답할 수 있습니다. 언제$\mathcal{D}_{F_1}$ 요청 $x$, $\mathcal{D}_{F}$ 쿼리 $f$ 의 위에 $x$ 및 반환 $f(x) \oplus x$ ...에 $\mathcal{D}_{F_1}$. 이것은 시뮬레이션$\mathcal{D}_{F_1}$의 쿼리 : 언제 $f$ 이다 $F(k, \cdot)$ 우리는 돌아 간다 $F(k, x) \oplus x$, 정확히 $F_1(k, x)$.
언제 $\mathcal{D}_{F_1}$ 완료되면 출력을 복제합니다. $F_1$ (출력 = 1), $\mathcal{D}_F$동일하게 출력합니다. 임의의 함수 (출력 = 0)와 대화 중이라고하면$\mathcal{D}_F$ 동일하게 출력합니다.
이제 다음과 같은 이점이 있음을 증명해야합니다. $|\Pr[\mathcal{D}_F^{F(k, \cdot)}(1^n)=1] - \Pr[\mathcal{D}_F^{g(\cdot)}(1^n) = 1]|$ 의 $\mathcal{D}_F$ 무시할 수없는 것입니다. $\mathcal{D}_{F_1}$ 무시할 수 없습니다.
이 마지막 부분은 일반적으로 오류가 자동으로 발생할 수있는 어려운 부분이므로 단계를 건너 뛰거나 잘못된 가정을 할 때주의해야합니다.
2.
PRF입니다.
직관적으로 이것이 PRF인지 여부에 대한 질문은 적이 예측할 수 있는지 여부로 축소되는 것 같습니다. $F(k, 0^n)$. 그러나 무시할 수 없을 정도로 많은 사람들에게 이것이 가능한 기능$k$ PRF가 아닙니다.
삼.
PRF가 아닙니다.
우리는 구별자를 만들 수 있습니다 $\mathcal{D}$ 무시할 수없는 이점이 있습니다. $\mathcal{D}$ 에 대한 액세스 권한이 부여됨 $f(\cdot)$, 이는 $F_3(k, \cdot)$또는 임의의 함수. 나는 상반기를 나타냅니다$z$ 같이 $z_L$ 그리고 후반 $z$ 같이 $z_R$.
- $\mathcal{D}$ 쿼리 $y^0 = f(0)$
- $\mathcal{D}$ 계산 $y^1 = F(y^0_R, x)$ 무작위로 $x$.
- $\mathcal{D}$ 쿼리 $y^2 = f(x)$
- 만약 $y^1 = y^2_L$, $\mathcal{D}$ 출력 $f$ 이다 $F_3$.
- 그렇지 않으면, $\mathcal{D}$ 출력 $f$ 무작위 함수입니다.
$\mathcal{D}$ 무시할 수없는 이점이 있습니다. $f$ 이다 $F_3$, 다음 $y^1 = y^2_L$:
$y^1 = F(y^0_R, x) = F(f(0^n), x) = F(F(k, 0^n), x)$
$y^2_L = f(x)_L = F_3(k, x)_L = F(F(k, 0^n), x)$
이것이 유지 될 확률 $f$ 무작위 함수는 무시할 수 있습니다.
내가 도울 수 있기를 바랍니다!
@fgrieu가 2 번 질문에 관심이 있었기 때문에 저는 사이트 정책을 깨고 그 부분에 대해 완전한 답변을 드릴 것입니다. 비록 이것이 거의 확실히 숙제 임에도 불구하고 말입니다.
정리. 허락하다$F : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$PRF 여야합니다. 그때,$F_2 : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$, 로써 정의 된 $$F_2(k,x) := F(F(k,0^n),x)$$ 또한 PRF입니다.
공식적인 증거를 제공하기 전에 왜 이것이 사실이어야하는지 직관을 세워 보자. 내부 호출은$F$ 입력의 일부가 아니라 상수 (즉, $0^n$). 즉, 키를 수정하면$k$, 외부 호출에 사용되는 키 $F$모든 평가를 위해$F_2$ 고정 키 $k' := F(k,0^n)$. 이후$k$ 건설의 다른 곳에서는 사용되지 않습니다. $k'$ 기본 PRF의 보안에 의해 균일하게 임의의 키와 구별 할 수 없어야합니다. $k''$, 하는 한 $k$무작위로 균일하게 선택됩니다. 이것은 오라클이 평가하는 것보다$F_2(k,\cdot)$ 그리고 오라클 평가 $F(k,\cdot)$사실 구별 할 수 없어야합니다. 이후$F(k,\cdot)$ 균일하게 선택된 무작위 함수와 구별 할 수없는 것으로 이미 알려져 있습니다. $f(\cdot)$ 그리고 (점근 적 의미에서) 구별 할 수없는 것은 전 이적입니다. $F_2$ 또한 PRF 여야합니다.
이 직감을 공식화합시다.
증명. 허락하다$A$ 임의의 PPT 알고리즘이어야합니다. $$\Bigl|\Pr_k[A^{F_2(k,\cdot)}(1^n)=1] - \Pr_f[A^{f(\cdot)}(1^n)=1]\Bigr|=\epsilon(n).$$ 우리는 무시할 수있는 상한선을 찾고 있습니다. $\epsilon$. 이를 위해 우리는 일련의 주장을 증명할 것입니다.
주장 1. $\Bigl|\Pr\limits_k[A^{F(F(k,0^n),\cdot)}(1^n)=1] - \Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1]\Bigr| \leq \mathsf{negl}(n)$
다음의 적을 고려하십시오 $B$ PRF 보안에 대해 $F$. 입력시$1^n$ 오라클에 대한 액세스 권한이 부여되었습니다. $B$ 쿼리 $0^n$ 오라클에게 값을 돌려받습니다. $k'$. 그런 다음$A$ 입력시 $1^n$. 할때는 언제나$A$ 쿼리를 보냅니다. $x$ 오라클에 $B$ 컴퓨팅으로 응답 $y:=F(k',x)$. 결국,$A$ 조금 출력합니다 $b$ 어느 $B$ 또한 출력합니다.
쉽게 알 수 있습니다. $$\Pr_k[B^{F(k,\cdot)}(1^n)=1] = \Pr_k[A^{F(F(k,0^n),\cdot)}(1^n)=1]$$ 과 $$\Pr_f[B^{f(\cdot)}(1^n)=1] = \Pr_f[A^{F(f(0^n),\cdot)}(1^n)=1].$$ 또한 $F$ 안전한 PRF입니다. $$\Bigl|\Pr_k[B^{F(k,\cdot)}(1^n)=1]-\Pr_f[B^{f(\cdot)}(1^n)=1]\Bigr|\leq \mathsf{negl}(n)$$ 그리고 주장은 다음과 같습니다.
주장 2. $\Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1] = \Pr\limits_{k}[A^{F(k,\cdot)}(1^n)=1]$
이것이 사실인지 확인하기 위해 생각하는 것이 가장 쉽습니다. $f$쿼리 할 때 느리게 샘플링됩니다. 이후$f$ 에서만 호출됩니다. $0^n$, 샘플링 $f$ 단순히 샘플링하는 것과 같습니다. $f(0^n)$ 균일 한 임의의 값으로 한 번 $k\in \{0,1\}$, 이는 오른쪽과 동일합니다.
주장 3. $\Bigl|\Pr_{k}[A^{F(k,\cdot)}(1^n)=1] - \Pr_{f}[A^{f(\cdot)}(1^n)=1]\Bigr| \leq \mathsf{negl}(n)$
이 주장은 사실 다음과 같은 가정을 다시 진술 한 것입니다. $F$ PRF이므로 사소하게 따릅니다.
삼각형 부등식을 사용하여 다음과 같은 결론을 내릴 수 있습니다. \begin{align} \epsilon(n) =&\quad \Bigl|\Pr_k[A^{F_2(k,\cdot)}(1^n)=1] - \Pr_f[A^{f(\cdot)}(1^n)=1]\Bigr|\\ \leq&\quad\Bigl|\Pr\limits_k[A^{F(F(k,0^n),\cdot)}(1^n)=1] - \Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1]\Bigr|\\ &+ \Bigl|\Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1] - \Pr\limits_{k}[A^{F(k,\cdot)}(1^n)=1]\Bigr|\\ &+ \Bigl|\Pr_{k}[A^{F(k,\cdot)}(1^n)=1] - \Pr_{f}[A^{f(\cdot)}(1^n)=1]\Bigr|\\ &\leq 2\cdot\mathsf{negl}(n) \end{align} 그리고 정리 진술이 바로 뒤 따릅니다.$\tag*{$\광장$}$