รูปแบบการเข้ารหัสแบบโฮโมมอร์ฟิคบางส่วนที่ปลอดภัย ทันสมัย ​​คืออะไร

ฉันกำลังอ่าน กระดาษแผ่นนี้ โดย Philippe Golle เกี่ยวกับการใช้คุณสมบัติโฮโมมอร์ฟิกของการเข้ารหัส ElGamal เพื่อเล่นเกมโป๊กเกอร์ทางจิต (เช่น โป๊กเกอร์ที่ปลอดภัยด้วยการเข้ารหัสโดยไม่มีตัวแทนจำหน่ายบุคคลที่สามที่เชื่อถือได้) ฉันตัดสินใจว่ามันจะเป็นโครงการที่ดีที่จะลองใช้เวอร์ชันพื้นฐานบางอย่าง แต่ฉันพบปัญหาอย่างรวดเร็ว

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

ฉันเดาว่าคำถามของฉันคือ ถ้า Golle เขียนบทความนี้ในปี 2022 เขาจะเสนออะไรแทน ElGamal สำหรับเกมโป๊กเกอร์ที่มีเดิมพันสูงพอ

ElGamal และ RSA «ถือว่าไม่ปลอดภัยโดยทั่วไป» ถ้า หนึ่งถือว่า คอมพิวเตอร์ควอนตัมที่เกี่ยวข้องกับการเข้ารหัสลับ. แต่สิ่งเหล่านี้ยังคงเป็นสมมุติฐานสูง ปัจจุบันโลก (อินเทอร์เน็ต ธนาคาร มือถือ..) ทำงานบนระบบเข้ารหัส ซึ่งในทางทฤษฎีแล้วมีความเสี่ยงต่อ CRQCs สมมุติเหล่านี้: RSA, ECDSA, EdDSA, ECIESâ¦

ระบบเข้ารหัสลับของ Paillier เป็นสิ่งที่ควรค่าแก่การพิจารณาเมื่อไม่คำนึงถึงสมมติฐาน CRQC มันเรียบง่าย¹ ให้การเข้ารหัสแบบโฮโมมอร์ฟิกเพิ่มเติมของจำนวนเต็ม (อาจมีลายเซ็น) โดยมีข้อจำกัดขนาดเล็กและชัดเจน² มีประสิทธิภาพภายในปัจจัยค่าคงที่เพียงเล็กน้อยของการถอดรหัส RSA (ดังนั้นจึงสามารถรับได้ในหลายๆ แอปพลิเคชัน) ปราศจากสิทธิบัตร สามารถลดทอนปัญหาทางคณิตศาสตร์ได้อย่างพิสูจน์ได้ เชื่อกันว่าเป็น super-polynomial สำหรับคอมพิวเตอร์คลาสสิก และถือว่าปลอดภัยพอๆ กับ RSA สำหรับขนาดไพรม์เดียวกัน

เหตุผลหลักที่ระบบเข้ารหัสลับของ Paillier ไม่ค่อยได้ใช้ในทางปฏิบัติก็คือ ฉันเชื่อว่าการเข้ารหัสแบบโฮโมมอร์ฟิคโดยทั่วไปนั้นไม่เป็นที่ต้องการสูง

เพิ่มเติม: การเข้ารหัส Paillier ไม่เสี่ยงต่อการโจมตีของ oracle หรือทางเลือกที่ไม่ดีของช่องว่าง เนื่องจาก (ตรงกันข้ามกับ RSA) ไม่จำเป็นต้องมีการเว้นช่องว่าง มีความเสี่ยงที่จะถูกโจมตีในการปรับใช้ RSA รวมถึงการใช้ประโยชน์จากตัวสร้างตัวเลขสุ่มที่ไม่ดีในการสร้างหรือใช้งานคีย์ ช่องทางด้านข้าง และการโจมตีข้อบกพร่อง ความคล้ายคลึงกันกับ RSA ถือเป็นข่าวดี เนื่องจาก RSA รู้จักมาตรการตอบโต้การโจมตีที่มีประสิทธิภาพและสามารถปรับเปลี่ยนให้เข้ากับ Paillier ได้

¹ โดยเฉพาะอย่างยิ่งกับข้อจำกัดทั่วไปของ $n$ ผลคูณของจำนวนเฉพาะสองตัวที่มีขนาดเท่ากัน และ $g=n+1$.

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

มีสองสิ่งที่ชัดเจนที่จะกล่าวถึง อย่างแรก มีข้อแม้ว่าฉันแค่อ่านบทความที่คุณลิงก์สั้นๆ เท่านั้น ฉันเห็นส่วนที่ 3 ระบุว่ารูปแบบการเข้ารหัสที่ใช้ต้องการคุณสมบัติ 3 อย่าง ได้แก่

1. โฮโมมอร์ฟิซึ่มเสริม,

2. "การเปรียบเทียบข้อความธรรมดาแบบแยกส่วน" เช่น ตรวจสอบว่า $Enc(ค)$ เป็นการเข้ารหัส 0

3. โปรโตคอลการสร้างคีย์แบบกระจาย

มันจะง่ายกว่าที่จะตอบคำถามนี้หากคุณสามารถกำหนดการดำเนินการ/คุณสมบัติที่คุณต้องการให้เป็นทางการได้อย่างแม่นยำ

ตามตาข่าย

จากทั้งหมดที่กล่าวมา รูปแบบการเข้ารหัสแบบ partially homomorphic ที่พบมากที่สุดในขณะนี้คือรูปแบบการเข้ารหัสแบบ R(LWE) สิ่งนี้ตอบสนองความแปรปรวนของโฮโมมอร์ฟิซึ่มแบบเติมแต่งที่ "มีเสียงดัง" ซึ่งหมายความว่าเราสามารถประเมินได้เพียงบางส่วนเท่านั้น ขอบเขตเบื้องต้น จำนวนโฮโมมอร์ฟิซึ่มแบบเติมแต่ง หากคุณต้องการเพิ่มเติมโดยพลการ ก็สามารถทำได้เช่นกัน ตัวอย่างเช่น แบบแผน FHEW/TFHE อาจเหมาะสมสำหรับสิ่งนี้ (โปรดทราบว่าสิ่งเหล่านี้คือ โฮโมมอร์ฟิคอย่างเต็มที่ รูปแบบการเข้ารหัสแม้ว่าจะมีประสิทธิภาพเป็นพิเศษก็ตาม) เป็นไปได้/น่าจะใช้ได้ในกรณีของคุณ

สำหรับอีกสองประเด็น ฉันจำเป็นต้องอ่าน/ทราบข้อกำหนดที่ชัดเจนของโครงร่างอย่างระมัดระวังมากขึ้น ดูเหมือนว่าจะเป็นไปได้สำหรับฉันว่ารูปแบบการเข้ารหัสที่ใช้ RLWE สามารถใช้ได้กับสถานการณ์ของคุณ แต่ฉันไม่รำคาญที่จะกรอกรายละเอียดเพราะ...

อิงจากเอล-กามาล:

ในขณะที่คุณพูดถูกว่า El-Gamal "คลาสสิค" (พูดตาม Diffie Hellman ที่มีขอบเขตจำกัด) นั้นค่อนข้างล้าสมัย แต่คุณ สามารถ ใช้ El-Gamal ตามกลุ่มเส้นโค้งวงรี นี่คือ "สมัยใหม่" (แม้ว่าจะยังอ่อนเมื่อเทียบกับคอมพิวเตอร์ควอนตัม หากคุณกังวล) และน่าจะง่ายกว่าสำหรับวัตถุประสงค์ของคุณมากกว่าการหารายละเอียดของวิธีการใช้โครงร่างแบบตาข่าย โปรดทราบว่าสำหรับ การเข้ารหัสทั่วไป มีเหตุผลเล็กน้อยที่จะใช้ตัวแปรเส้นโค้งวงรีของ El Gamal (ดูรายละเอียดที่นี่) แต่เนื่องจากคุณต้องการใช้โฮโมมอร์ฟิซึ่มแบบเติมแต่งโดยเฉพาะ การใช้ El Gamal จึงสมเหตุสมผล

หากคุณไม่เห็นด้วยกับการใช้ Elliptic Curve El Gamal ด้วยเหตุผลบางประการ ตัวเลือกหลักที่เหลืออยู่คือโครงร่างแบบตาข่าย การดำเนินการนี้จะต้องใช้ความพยายามมากขึ้นในการหารายละเอียด ซึ่งจะช่วยให้ผู้คนในเว็บไซต์นี้ช่วยเหลือคุณได้ง่ายขึ้น หากคุณสามารถระบุได้อย่างแม่นยำว่าคุณมีข้อกำหนดใดสำหรับโครงร่างการเข้ารหัสพื้นฐาน