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

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

กำหนดให้

$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].
• แม่แบบ:Cite journal