일방향 함수로부터의 의사 난수 생성

우리는 일방향 함수의 존재가 다음과 같은 의미에서 의사 난수 생성기의 존재를 위한 필요하고 충분한 조건임을 보여줍니다. ƒ을 쉽게 계산할 수 있는 함수라고 하고, x가 무작위로 선택될 때: (1) ƒ(x)로부터 ƒ(x1) = ƒ(x)가 성립하는 x1을 작은 회로로 복구하는 것이 어렵거나; (2) ƒ가 작은 퇴행성을 가지며, ƒ(x)로부터 빠른 알고리즘으로 x를 복구하는 것이 어렵습니다. 우리는 (1) 또는 (2)형 일방향 함수로부터 작은 회로 또는 빠른 알고리즘에 대해 안전한 의사 난수 생성기를 구성하는 방법을 보여줍니다. 이전 결과는 특별한 속성을 가진 일방향 함수로부터 의사 난수 생성기를 구성하는 방법을 보여줍니다 (Blum, Micali 82, Yao 82, Levin 85, Goldreich, Krawczyk, Luby 88).