유사난수 생성기

짧은 무작위 씨앗을 받아 훨씬 긴 문자열을 내되, 그 출력이 효율적인 어떤 검사로도 진짜 무작위 문자열과 구별되지 않게 하는 알고리즘이다(의사 난수 생성기라고도 한다). 일방향 함수가 존재하는 것과 암호학적 유사난수 생성기가 존재하는 것은 같은 말임이 증명되어 있다. 충분히 어려운 함수가 있으면 그것으로 유사난수 생성기를 만들어 무작위 알고리즘에서 무작위를 없앨 수 있다. 「어려움」을 「무작위성」으로 바꾸는 이 연결이 자연 증명 장벽의 밑바탕이기도 하다.