การสุ่มแบบสั้นใน ElGamal และ Paillier

ความปลอดภัยทางความหมายในการตั้งค่านั้นจะลดลงเป็นการรักษาความปลอดภัยทางความหมายสำหรับโครงร่างมาตรฐาน ก็ต่อเมื่อการแจกแจงแบบเอนโทรปีต่ำในกลุ่มย่อย

• ในกรณีของ ElGamal ข้อสันนิษฐานก็คือ $(g^r, h^r)$ สำหรับการสุ่มขนาดเล็ก $r$ แยกไม่ออกจากคู่ DH มาตรฐาน กล่าวคือ $(g^r, h^r)$ สำหรับเครื่องแบบ $r$. สิ่งนี้ได้รับการศึกษาโดย Kurosawa และ Koshiba ใน กระดาษ PKC 2004และพวกเขาแสดงให้เห็นว่าข้อสันนิษฐานนั้นถือได้ว่าปัญหาล็อกแบบแยกของเลขชี้กำลังสั้นในการคำนวณนั้นยาก สำหรับกลุ่มที่มีความเกี่ยวข้องในการเข้ารหัส การโจมตีที่ดีที่สุดในล็อกแบบแยกแบบเลขชี้กำลังแบบสั้นมักจะเป็นทั้งแลมบ์ดาของ Pollard หรือแบบเดียวกับสำหรับล็อกแบบแยกแบบไม่สั้น ดังนั้นหาก $r$ มีขนาดใหญ่พอ (อย่างน้อยสองเท่าของพารามิเตอร์ความปลอดภัย) ถือว่าใช้ได้ อย่างไรก็ตามสิ่งนี้ผูกพันกับ $r$ จะเหมือนกับขอบเขตบนเลขชี้กำลังแบบเต็ม อย่างไรก็ตาม หากคุณตั้งค่าพารามิเตอร์อย่างถูกต้อง ดังนั้นการทำเช่นนี้จึงไม่มีประโยชน์ในการตั้งค่าส่วนใหญ่

• ในกรณีของ Paillier ข้อสันนิษฐานก็คือ $r^n$ สำหรับขนาดเล็ก $r$ แยกไม่ออกจากการคำนวณจากการสุ่มในกลุ่มย่อยของคำสั่ง $\varphi(n)$ ของ $\mathbb{Z}/n^2\mathbb{Z}$. ฉันไม่ทราบถึงการโจมตีใดๆ ในปัญหานี้ และดูเหมือนว่าจะค่อนข้างเป็นไปได้หาก $r$ ไม่น้อยเกินไปแม้ว่าฉันจะไม่รู้ว่าสมมติฐานมาตรฐานใดที่เกี่ยวข้องมากกว่ากัน ไม่ว่าจะอย่างไรก็ตามความเร็วจากการใช้งานที่น้อยลง $r$ ในการคำนวณของ $r^n \bmod n^2$ ควรจะเล็กน้อย (อันที่จริง ไม่ควรเร่งความเร็วเลยถ้าคุณใช้เลขคณิตเร็ว) ดังนั้นฉันจึงไม่แน่ใจว่าจะเห็นประเด็นของตัวแปรนี้เช่นกัน