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

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

กำหนดให้  เป็นเซตของสมการพีชคณิต แล้วให้  และ  แล้วถ้ารู้ค่าของ  กับ  จงหาค่าของ 

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

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

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

 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].


หมวดหมู่:ปัญหาทางคณิตศาสตร์
หมวดหมู่:วิทยาการเข้ารหัสลับ