피히딩 가정
Phi-hiding assumption피히딩 가정 또는 φ히딩 가정은 φ(m)의 작은 인자를 찾기 어렵다는 가정이며, 여기서 m은 인자를 알 수 없는 숫자, φ은 오일러의 토털함수다.많은 현대 암호 시스템의 보안은 특정 문제의 인식된 어려움에서 비롯된다.P 대 NP 문제는 여전히 해결되지 않았기 때문에, 암호학자들은 계산적으로 난해한 문제가 존재한다고 확신할 수 없다.따라서 암호학자들은 어떤 문제가 어려운지에 대해 가정을 한다.일반적으로 m이 두 개의 큰 프리타임의 산물인 경우, ((m) 계산은 현재 계산상 불가능하며, 이 가정은 RSA Cryptosystem의 보안에 필요하다.φ-히딩 가정은 더1 강한 가정으로2, 즉 p와 p가 φ(m)를 정확하게 나누는 작은 소수인 경우, p와1 p가2 φ(m)를 1/2보다 크게 나눌 확률을 갖는 것을 구별할 수 있는 다항 시간 알고리즘이 없다.
이러한 가정은 1999년 다의류 통신을 통한 계산적 민간 정보 검색에서 처음으로 언급되었는데,[1] 여기서 그것은 개인 정보 검색 체계에서 사용되었다.
적용들
피히딩 가정은 몇 가지 암호 원료의 구성에서 응용 프로그램을 찾아냈다.건설의 일부는 다음과 같다.
- 다변량 통신을 이용한 전산상 개인 정보 검색 (1999)
- 의식 없는 제3자를 통한 효율적인 민간입찰 및 경매(1999)
- 일정한 통신 속도를 가진 단일 데이터베이스 개인 정보 검색(2005)
- 숨겨진 부드러운 하위 그룹을 사용한 암호 인증 키 교환(2005)
참조
- ^ Cachin, Christian; Micali, Silvio; Stadler, Markus (1999). Stern, Jacques (ed.). "Computationally Private Information Retrieval with Polylogarithmic Communication". Lecture Notes in Computer Science. Springer. 1592: 402–414. doi:10.1007/3-540-48910-X. ISBN 978-3-540-65889-4. S2CID 29690672.
