랜덤 오라클

Random oracle
임의 질문에 대한 임의 응답은 인터넷 오라클을 참조하십시오.

암호학에서 랜덤 오라클은 출력 영역에서 균일하게 선택한 (진정한) 랜덤 응답으로 모든 고유 질의에 응답하는 오라클(이론적인 블랙박스)이다.쿼리가 반복되면 쿼리가 제출될 때마다 동일한 방식으로 응답한다.

다르게 표현하면, 랜덤 오라클은 무작위로 균일하게 선택된 수학 함수, 즉 출력 도메인에서 (고정) 무작위 응답에 각각의 가능한 쿼리를 매핑하는 함수다.

수학적인 추상화로서의 임의의 웅변은 미히르 벨라레와 필립 로가웨이(1993)가 1993년 출판한 엄격한 암호증명에 처음 사용되었다.[1]그것들은 일반적으로 암호해시함수에 대한 더 약한 가정을 사용하여 증명서를 수행할 수 없을 때 사용된다.모든 해시함수가 랜덤 오라클로 대체될 때 안전성이 입증된 시스템은 암호화의 표준 모델에서 보안이 아닌 랜덤 오라클 모델에서 보안이 되는 것으로 기술된다.

적용들

임의의 경구는 일반적으로 해시함수의 출력에 대해 강한 임의성 가정이 필요한 체계에서 암호 해시함수의 이상적인 대체물로 사용된다.그러한 증거는 종종 공격자가 Oracle로부터 불가능한 행동을 요구해야 한다는 것을 보여줌으로써 시스템이나 프로토콜이 안전하다는 것을 보여주거나, 그것을 깨기 위해서 어렵게 믿어진 어떤 수학적인 문제를 해결해야 한다는 것을 보여준다.그러나 랜덤 오라클 모델에서 그러한 특성을 증명할 뿐, 중요한 설계 결함이 없는지 확인한다.일반적으로 그러한 증거가 표준 모델에서 동일한 특성을 내포한다는 것은 사실이 아니다.그러나, 임의의 오라클 모델에서 증명하는 것은 공식적인 보안 증명서가 전혀 없는 것보다 더 낫다고 여겨진다.[2]

암호 해시함수의 모든 용도에 무작위 어래클이 필요한 것은 아니다: 표준 모델(충돌 저항성, 프리이미지 저항성, 두 번째 프리이미지 저항성 등)에 정의가 있는 하나 이상의 속성만 요구하는 체계는 표준 모델(예: Cramer–)에서 안전한 것으로 입증되는 경우가 많다.션프 암호 시스템).

계산 복잡성 이론에서는 오랫동안 무작위 경구들이 고려되어 왔으며,[3] 예를 들어 Optimal Asymmetric Encryption Pading, RSA-FDH, Probabilistic Signature Scheme과 같은 많은 체계들이 랜덤 오라클 모델에서 안전성이 입증되었다.1986년 아모스 피아트(Amos Fiat)와 아디 샤미르(Adi Shamir[4])는 서명 작성을 위한 프로토콜에서 상호작용을 제거하는 등 임의의 웅변을 주로 적용하였다.

1989년 러셀 임팔리아조와 스티븐 루디치는[5] 임의의 웅변, 즉 그들의 존재만으로는 비밀키 교환에 충분하지 않다는 한계를 보여주었다.

1993년, 미히르 벨라레와 필립 로가웨이가[1] 처음으로 암호구축에 그들의 사용을 옹호했다.그 정의에서 랜덤 오라클은 무한 길이의 비트 문자열을 생성하며, 원하는 길이까지 자를 수 있다.

보안 증명 내에서 임의의 신탁을 사용할 경우, 적이나 적수를 포함한 모든 플레이어가 이를 사용할 수 있도록 한다.단일 오라클은 각 쿼리의 시작 부분에 고정 비트 문자열을 미리 입력하여 여러 개의 경락으로 처리될 수 있다(예: "1 x" 또는 "0 x"로 포맷된 쿼리는 두 개의 개별 랜덤 경락에 대한 호출로 간주할 수 있으며, 마찬가지로 "00 x", "01 x", "10 x" 및 "11 x"는 네 개의 개별 경락으로 통화를 나타내는 데 사용될 수 있다).

제한 사항

Church-Turing 논문에 따르면, 유한 알고리즘에 의해 계산될 수 있는 어떤 기능도 진정한 무작위 신탁을 구현할 수 없다(정의상으로는 가능한 입력이 무한히 많으며, 그 출력은 모두 서로 독립적이며 어떤 설명에 의해서 개별적으로 지정될 필요가 있기 때문에 무한한 설명을 필요로 한다).

실제로 랜덤 오라클 모델에서는 안전성이 입증되지만 실제 기능이 랜덤 오라클로 대체될 경우 사소한 불안정한 특정 인공 서명 및 암호화 방식이 알려져 있다.[6][7]그럼에도 불구하고, 더 이상 자연적인 프로토콜의 경우, 임의의 오라클 모델에서의 보안 증명은 프로토콜의 실제적인 보안에 대한 매우 강력한 증거를 제공한다.[8]

일반적으로, 프로토콜이 안전하다고 입증된 경우, 프로토콜에 대한 공격은 입증된 것을 벗어나거나, 증명에서 가정들 중 하나를 깨트려야 한다. 예를 들어, 증명서가 정수 인자화의 경도에 의존하는 경우, 이러한 가정을 깨기 위해서는 빠른 정수 인자화 알고리즘을 발견해야 한다.대신 랜덤 오라클 가정을 파기하기 위해서는 실제 해시함수의 알 수 없고 바람직하지 않은 특성을 발견해야 한다. 이러한 특성이 가능성이 낮다고 여겨지는 양호한 해시함수의 경우, 고려된 프로토콜이 안전한 것으로 간주될 수 있다.

랜덤 오라클 가설

비록 Baker–Gill–Solovay theorem[9]이 신탁이 존재한이 1939)경찰청, 베넷과 Gill,[10]에 의해 일련의 작업은 무작위의 신탁 B({0,1}n에서{0,1}에 함수가 각 입력 요소 매핑 됩니다의 0또는 1과 확률 1/2, 독자적으로 매핑의 다른 모든 입력), PB⊊ 일본 프로 야구 프로 보여 줬다.bability 1.유사한 분리, 뿐만 아니랐다는 사실이 확률 0또는 1(는 콜모고로프의zero–one 법칙의 결과로써)과의 무작위 신탁의 분리된 등급, 랜덤 오라클의 가설의 창조하기, 만일 그들은(확률 1로)은 무작위. 자세한 내용은 acc에 동등하다고 할 두"허용"복잡도 종류 C1및 C2평등하고 있다.e복잡도 등급의 ptability는 BG81[10]).확률 1의 랜덤 오라클 A에 대해 IPA ⊊ PSPACE에도A 불구하고 허용 가능한 두 가지 복잡성 등급 IP와 PSPACE가 동일한[11] 것으로 나타났기 때문에 이 가설은 나중에 거짓으로 밝혀졌다.[12]

이상 암호

이상적인 암호는 이상화된 블록 암호의 모델링에 사용되는 임의 순열 오라클이다.무작위 순열은 각 암호문 블록을 하나의 일반 텍스트 블록으로 해독하고 그 반대의 경우도 마찬가지여서 일대일 서신 왕래가 있다.일부 암호증명은 "전진" 순열뿐만 아니라 "역진" 순열도 모든 플레이어가 사용할 수 있게 한다.

최근의 연구들은 이상적인 암호는 10라운드[13] 혹은 8라운드[14] 페이젤 네트워크를 이용하여 임의의 신탁으로부터 만들어질 수 있다는 것을 보여주었다.

이상적인 순열

이상적인 순열은 때때로 암호법에 사용되는 이상화된 물체로, 출력이 무작위 순열과 구별되지 않는 순열의 행동을 모델링한다.이상적인 순열 모델에서, 이상적인 순열과 그 역순에 추가적인 오라클 액세스가 주어진다.이상적인 순열 모델은 이상 암호 모델의 경우처럼 순열 계열이 아니라 단일 순열에만 접근하는 이상 암호 모델의 특별한 사례로 볼 수 있다.

양자 액세스 가능 임의의 경구

포스트 퀀텀 암호학은 고전적인 암호 체계에 대한 양자 공격을 연구한다.랜덤 오라클은 해시함수의 추상화인 만큼 양자 공격자가 양자 중첩에서 랜덤 오라클에 접근할 수 있다고 보는 것이 타당하다.[15]많은 고전적인 보안 증명들은 양자 랜덤 오라클 모델에서 분해되어 수정될 필요가 있다.

참고 항목

참조

  1. ^ a b Bellare, Mihir; Rogaway, Phillip (1993). "Random Oracles are Practical: A Paradigm for Designing Efficient Protocols". ACM Conference on Computer and Communications Security: 62–73.
  2. ^ Katz, Jonathan; Lindell, Yehuda (2015). Introduction to Modern Cryptography (2 ed.). Boca Raton: Chapman & Hall/CRC. pp. 174–175, 179–181. ISBN 978-1-4665-7027-6.
  3. ^ Bennett, Charles H.; Gill, John (1981), "Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1", SIAM Journal on Computing, 10 (1): 96–113, doi:10.1137/0210008, ISSN 1095-7111
  4. ^ Fiat, Amos; Shamir, Adi (1986). "How to Prove Yourself: Practical Solutions to Identification and Signature Problems". CRYPTO. pp. 186–194.
  5. ^ Impagliazzo, Russell; Rudich, Steven (1989). "Limits on the Provable Consequences of One-Way Permutations". STOC: 44–61.
  6. ^ Ran Canetti, Oed Goldreich and Shai Halevi, The Random Oracle Methodology Reagained, STOC 1998, 페이지 209–218(PS 및 PDF)
  7. ^ 크레이그 젠트리, 줄피카 람잔."이븐만수어 암호에서 임의 순열 오라클 제거"2004.
  8. ^ Koblitz, Neal; Menezes, Alfred J. (2015). "The Random Oracle Model: A Twenty-Year Retrospective" (PDF). Another Look. Retrieved 6 March 2015.
  9. ^ Baker, Theodore; Gill, John; Solovay, Robert (1975). "Relativizations of the P =? NP Question". SIAM J. Comput. SIAM. 4 (4): 431–442. doi:10.1137/0204037.
  10. ^ a b Bennett, Charles; Gill, John (1981). "Relative to a Random Oracle A, P != NP != co-NP with Probability 1". SIAM J. Comput. SIAM. 10 (1): 96–113. doi:10.1137/0210008.
  11. ^ Shamir, Adi (October 1992). "IP = PSPACE". Journal of the ACM. 39 (4): 869–877. doi:10.1145/146585.146609. S2CID 315182.
  12. ^ Chang, Richard; Oded Goldreich, Benny Chor; Hartmanis, Juris; Hastad, Johan; Ranjan, Desh; Rohatgi, Pankaj (August 1994). "The Random Oracle Hypothesis is False". Journal of Computer and System Sciences. 49 (1): 24–39. doi:10.1016/S0022-0000(05)80084-4. ISSN 0022-0000.
  13. ^ Dachman-Soled, Dana; Katz, Jonathan; Thiruvengadam, Aishwarya (2016). "10-Round Feistel is Indifferentiable from an Ideal Cipher". EUROCRYPT 2016. Springer. pp. 649–678. doi:10.1007/978-3-662-49896-5_23.
  14. ^ Dai, Yuanxi; Steinberger, John (2016). "Indifferentiability of 8-Round Feistel Networks". CRYPTO 2016. Springer.
  15. ^ Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry (2011). Random oracles in a quantum world. Springer. pp. 41–69. arXiv:1008.0931. doi:10.1007/978-3-642-25385-0_3.{{cite conference}}: CS1 maint : 복수이름 : 작성자 목록(링크)