ปัญหาของดิฟฟีเฮลแมน

ปัญหาของดิฟฟีเฮลแมน (อังกฤษ: Diffie–Hellman problem) เป็นปัญหาเชิงคณิตศาสตร์ที่ออกแบบโดยวิทฟิลด์ ดิฟฟี และมาร์ติน เฮลแมน ว่าด้วยวิทยาการเข้ารหัสลับแบบสมมาตร แรงจูงใจสำหรับปัญหานี้มาจากว่า การเข้ารหัสลับในหลายรูปแบบจะใช้ฟังก์ชันทางเดียว ซึ่งเป็นกระบวนการทางคณิตศาสตร์ที่สามารถประมวลผลได้อย่างรวดเร็วแค่ในทิศทางเดียว กล่าวคือระบบเหล่านี้จะสามารถเข้ารหัสข้อมูลอิเล็กทรอนิกส์ได้ง่าย แต่การถอดรหัสนั้นจะเป็นไปได้ยาก ปัญหาดังกล่าวมีดังต่อไปนี้

กำหนดให้ $G$ เป็นเซตของสมการพีชคณิต แล้วให้ $g\in G$ และ $x,y\in \mathbb {Z}$ แล้วถ้ารู้ค่าของ $g^{x}$ กับ $g^{y}$ จงหาค่าของ $g^{xy}$

ยกตัวอย่างเช่น ในการสลับกุญแจดิฟฟีเฮลแมน หากผู้ส่งมีกุญแจส่วนตัว $x$ ผู้รับมีกุญแจส่วนตัว $y$ และทั้งคู่มีกุญแจสาธารณะ $g^{x}$ กับ $g^{y}$ นักดักฟังจะสามารถเข้าถึงค่าของ $g^{x}$ กับ $g^{y}$ ได้เท่านั้น ผู้ส่งและผู้รับสามารถหาค่าของ $g^{xy}$ ได้ง่าย แต่นักดักฟังจะหาค่าได้ยากเนื่องจากในความเป็นจริงจะต้องใช้เวลานานมากในการหาค่า $x$ และ $y$ จากค่า $g^{x}$ และ $g^{y}$

ความซับซ้อนในการคำนวณ

ในวิทยาการเข้ารหัสลับ มีการคาดคะเนว่าการแก้ไขปัญหาของดิฟฟีเฮลแมนนั้นจะทำได้ยาก ซึ่งเรียกว่า สันนิษฐานของดิฟฟีเฮลแมน ปัญหาดังกล่าวได้ผ่านการพิจารณามาหลายทศวรรษแล้ว แต่ในปัจจุบันก็ยังไม่พบวิธีการแก้ปัญหานี้โดยไม่มีความซับซ้อน อย่างไรก็ตาม ในปี 2006 ได้มีการแผยแพร่วิธีการแก้ไขปัญหานี้โดยการคำนวณผ่านลอการิทึ่มแบบไม่ต่อเนื่อง กล่าวคือสามารถหาค่าของ $x$ เมื่อรู้ค่าของ $g$ และ $g^{x}$ ได้ แต่การคำนวณดังกล่าวก็ยังมีข้อถกเถียงว่ามีความซับซ้อนไม่แพ้ปัญหาของดิฟฟีเฮลแมน

แหล่งข้อมูลอื่น

• B. den Boer, Diffie–Hellman is as strong as discrete log for certain primes in Advances in Cryptology – CRYPTO 88, Lecture Notes in Computer Science 403, Springer, p. 530, 1988.
• U. M. Maurer and S. Wolf, Diffie–Hellman oracle in Advances in Cryptology – CRYPTO 96, (N. Koblitz, ed.), Lecture Notes in Computer Science 1070, Springer, pp. 268–282, 1996.
• D. Boneh and R. J. Lipton, Algorithms for black-box fields and their application to cryptotography in Advances in Cryptology – CRYPTO 96, (N. Koblitz, ed.), Lecture Notes in Computer Science 1070, Springer, pp. 283–297, 1996.
• A. Muzereau, N. P. Smart and F. Vercauteran, The equivalence between the DHP and DLP for ellipti curves used in practical applications, LMS J. Comput. Math., 7, pp. 50–72, 2004. See [www.lms.ac.uk].
• 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.