디피-헬만 문제

Diffie–Hellman problem

디피-헬먼 문제(DHP)는 암호학의 맥락에서 휘트필드 디피와 마틴 헬먼이 처음 제안한 수학 문제다.이 문제의 동기는 많은 보안시스템이 단방향 함수를 사용하기 때문이다: 계산은 빠르지만 되돌리기는 어려운 수학 연산.예를 들어, 그들은 메시지 암호화를 가능케 하지만 암호화를 되돌리기는 어렵다.DHP의 해결이 쉬웠다면, 이러한 시스템들은 쉽게 깨질 것이다.

문제 설명

디피-헬먼 문제는 다음과 같이 비공식적으로 언급된다.

원소 g와x g와 g의y 값이 주어진다면 g의xy 값은 얼마인가?

형식적으로 g는 일부 그룹(일반적으로 유한장 또는 타원곡선 그룹의 승수 그룹)의 생성자로 x와 y는 임의로 정수로 선택된다.

예를 들어 디피-에서Hellman 키 교환, 도청자는 프로토콜의 일부로 교환된 g와x g를y 관찰하고, 양 당사자는 공유 키 g를xy 계산한다. DHP를 해결하기 위한 빠른 수단은 도청자가 Diffie-의 사생활을 침해할 수 있다.Hellman 키 교환 및 ElGamal 암호화를 포함한 많은 변형.

계산 복잡성

암호학에서는, 특정 집단의 경우, DHP가 딱딱하다고 가정하고, 이것을 흔히 디피-라고 부른다.지옥의 가정.이 문제는 몇 십 년 동안 정밀 조사를 거쳤으며 아직 "쉬운" 해결책은 발표되지 않았다.

2006년 현재 DHP를 해결하기 위해 알려진 가장 효율적인 수단은 이산 로그 문제(DLP)를 해결하는 것으로, 주어진 g와 g를x 찾는 것이다.실제로, (덴 보어, 마우어, 울프, 본, 립톤에 의해) 상당한 진전이 이루어졌는데, 많은 그룹들 이상에서 DHP는 거의 DLP만큼 어렵다는 것을 보여준다.(네체프와 슈프의) 일반 그룹을 제외하고는 DHP나 DLP 중 어느 한쪽이 어려운 문제라는 증거는 현재까지 없다.어느 한 가지 문제가 어렵다는 증거는 P ≠ NP를 암시한다.

기타 변형

디피족의 다양한 변종들-헬맨 문제가 고려되었다.가장 중요한 변형은 의사결정 디피-이다.헬만xy 문제(DDHP)는 g와 랜덤 그룹 요소를 구분하는 것으로 g, g, g가x 주어진다y.때로는 DHP를 계산적 디피-라고 부른다.DDHP와 보다 명확하게 구별하기 위한 헬만 문제(CDHP)최근 쌍을 이루는 그룹이 인기를 끌었고, 이러한 그룹에서는 DDHP가 쉽지만 DHP는 여전히 어렵다고 가정한다.덜 중요한 DHP 변형은 참조를 참조하십시오.

참조

  • B. 덴 보어, 디피-Hellman은 Changes in Cryptology – CRIPTO 88, 컴퓨터 사이언스 403, Springer, 페이지 530, 1988의 강의 노트에서 특정 프리타임에 대한 이산 로그만큼 강하다.
  • U.S. Maureer와 S.울프, 디피-Hellman oracle in Cryptology – CRIPTO 96, (N. Koblitz, ed.) 컴퓨터 과학 1070, 스프링어, 페이지 268–282, 1996.
  • Maurer, Ueli M.; Wolf, Stefan (2000). "The Diffie–Hellman Protocol". Designs, Codes and Cryptography. 19 (2/3): 147–171. doi:10.1023/A:1008302122286.
  • D. Boneh와 R. J. Lipton, 블랙박스 필드의 알고리즘 및 CRYPLO 96, (N. Koblitz, ed.) 컴퓨터 사이언스 1070, Springer, 페이지 283–297, 1996.
  • A. Muzerau, N. P. Smart, F.Vercauteran, 실제 적용에 사용되는 타원 곡선에 대한 DHP와 DLP 사이의 동등성, LMS J. Compute.수학, 7, 페이지 50–72, 2004.[www.lms.ac.uk]을 참조하십시오.
  • D. R. L. 브라운과 R. P. 갤런트, 정적 디피-Hellman 문제, IACR ePrint 2004/306.
  • V. I. Nechev, 이산 로그에 대한 결정 알고리즘의 복잡성, 수학 노트, 55(2), 페이지 165–172, 1994.
  • V. Shoup, Cryptology의 진전 로그 및 관련 문제에 대한 하한 - EUROCrypt 97, (W. Fumy, ed.) 컴퓨터 과학 1233, Springer, 페이지 256–266, 1997.
  • Bao, Feng; Deng, Robert H.; Zhu, Huafei (2003). "Variations of Diffie-Hellman Problem". ICICS 2003: Information and Communications Security. Lecture Notes in Computer Science. Vol. 2836. Springer. pp. 301–312. CiteSeerX 10.1.1.104.3007. doi:10.1007/978-3-540-39927-8_28. ISBN 978-3-540-20150-2.
  • Boneh, Dan (1998). "The Decision Diffie-Hellman problem". ANTS 1998: Algorithmic Number Theory. Lecture Notes in Computer Science. Vol. 1423. Springer. pp. 48–63. CiteSeerX 10.1.1.461.9971. doi:10.1007/bfb0054851. ISBN 978-3-540-64657-0.
  • Bresson, Emmanuel; Chevassut, Olivier; Pointcheval, David (2003). "The Group Diffie-Hellman Problems" (PDF). SAC 2002: Selected Areas in Cryptography. Lecture Notes in Computer Science. Vol. 2595. Springer. pp. 325–338. doi:10.1007/3-540-36492-7_21. ISBN 978-3-540-00622-0.
  • Biham, Eli; Boneh, Dan; Reingold, Omer (1999). "Breaking generalized Diffie–Hellman modulo a composite is no easier than factoring". Information Processing Letters. 70 (2): 83–87. CiteSeerX 10.1.1.39.110. doi:10.1016/S0020-0190(99)00047-2.
  • Steiner, Michael; Tsudik, Gene; Waidner, Michael (1996). "Diffie-Hellman key distribution extended to group communication". Proceedings of the 3rd ACM conference on Computer and communications security - CCS '96. ACM. pp. 31–37. CiteSeerX 10.1.1.35.9717. doi:10.1145/238168.238182. ISBN 978-0897918299.
  • Diffie, W.; Hellman, M. (1976). "New directions in cryptography". IEEE Transactions on Information Theory. 22 (6): 644–654. CiteSeerX 10.1.1.37.9720. doi:10.1109/tit.1976.1055638.