암호·평균 복잡도서지만 확인
A hard-core predicate for all one-way functionsOded Goldreich, Leonid A. Levin · 1989STOC 1989 (Proceedings of the 21st Annual ACM Symposium on Theory of Computing), 25–32쪽제목이 말하듯 어떤 일방향 함수에서든 「맞히기 어려운 한 비트」를 뽑아낼 수 있음을 보인 논문이다. 일방향 함수 하나만 있으면 유사난수 생성기를 만들 수 있다는 결과(hill-1999)로 가는 디딤돌이다. 일방향 함수의 존재는 P ≠ NP 보다 강한 가정이며, 그 가정에서 무엇이 나오는지 따라가려는 글이 인용한다.
확인:Crossref 의 DOI 등록 기록으로 제목·저자(머리글자 표기)·학회·쪽을 확인했다(본문은 열지 못함).