PRG 지수 확장

Question

나는 의사 난수 생성기를 막 읽기 시작했고 PRG에 대한 다음 정의를 발견했습니다.

$G_n : \{0,1\}^n \rightarrow \{0,1\}^{l(n)}, \quad \text{ where $l (n)$ is a polynomial}$

이유가 있나요 $l(n)$다항식이어야합니까? 지수 함수라면 더 나은 보안 보장이 없을까요? 의사 난수 정의의 적도 확률 적 다항식 시간 적이기 때문입니다.

Answer 1

여기에는 두 가지 문제가 있습니다. 첫 번째는 지수 출력 길이를 가진 PRG는 출력을 쓰기 위해 지수 시간이 필요하기 때문에 더 이상 효율적인 (즉, 다항식 시간) 알고리즘이 될 수 없다는 것입니다.

두 번째 문제는 그러한 알고리즘이 안전하지 않다는 것입니다. PRG에 대한 구분자는 문자열을받습니다.$y\in \{0,1\}^{\ell(n)}$, 이는 PRG의 출력이거나 균일하게 임의의 문자열입니다. 효율적이어야합니다. 즉, 입력 길이 에서 시간 다항식으로 실행되어야합니다 . 입력 길이가 지수이면 다음과 같이 말하십시오.$\ell(n)=2^n$, 그런 다음 시간 다항식에서 실행할 수 있습니다. $2^n$. 가능한 모든 시드 값을 열거하기에 충분한 시간입니다.$s\in\{0,1\}^n$, 계산 $y':=G_n(s)$ 확인하고 $y' = y$. 균일하게 무작위이기 때문에$y$, 그러한 시드가 존재할 확률은 (정말로) 무시할 수 있으며, 이것은 사소한 구별 공격으로 이어집니다.