Score:2

บันทึกแยกโดยทั่วไปยากในกลุ่ม Paillier หรือไม่

ธง gt

https://en.wikipedia.org/wiki/Paillier_cryptosystem

ระบบเข้ารหัสลับของ Paillier ใช้ประโยชน์จากความจริงที่ว่าสามารถคำนวณลอการิทึมแบบไม่ต่อเนื่องบางตัวได้อย่างง่ายดาย

ถ้าฉันต้องเลือก $g \in \mathbb{Z}_{n^2}^*$ ที่ไหน $n$ แบ่งลำดับของ $g$จากนั้นบันทึกแยกนั้นง่าย (w.r.t base $g$) ถ้าฉันเข้าใจถูกต้อง

แต่ถ้าให้ผมสุ่มเลือกค่าใดค่าหนึ่ง $r \in \mathbb{Z}_{n^2}^*$ ที่ไหน $n$ ไม่แบ่งลำดับของ $r$เราจะสามารถพูดอะไรเกี่ยวกับความยากของบันทึกแยกได้หรือไม่

Score:0
ธง ru

ฉันจะถือว่า Paillier ทั่วไปตั้งค่านั้น $n=pq$ กับ $p$ และ $คิว$ จำนวนเฉพาะ $(p-1)\ไม่\!| คิว$ และในทางกลับกัน.

การกู้คืนลอการิทึมแบบไม่ต่อเนื่อง $x$ ขององค์ประกอบทั่วไป $a$ ในส่วนที่เกี่ยวกับเครื่องกำเนิดไฟฟ้านั้นเทียบเท่ากับการกู้คืนค่าสามค่า: $$x\equiv\cases{x_\lambda\pmod{\lambda(n)}\ x_p\pmod p\ x_q\pmod q}.$$

ถ้าใครรู้ค่าของ $p$ และ $คิว$ แล้ว $x_p$ และ $x_q$ สามารถกู้คืนได้ง่ายโดยใช้ Fermat quotients หรือ $p$รุ่น -adic ของอนุกรมลอการิทึมเทย์เลอร์ วิธีที่ดีที่สุดในการกู้คืน $x_\แลมบ์ดา$ ขึ้นอยู่กับตะแกรงฟิลด์ตัวเลขและสำหรับขนาดเข้ารหัส* $p$ และ $คิว$นี้ควรจะเป็นไปไม่ได้ ถ้าใครเลือกเครื่องกำเนิดไฟฟ้าในลักษณะที่ลำดับของเครื่องกำเนิดไฟฟ้าแบ่งออก $n$นี่หมายความว่า $x_\แลมบ์ดา$ สามารถละเว้นได้และลอการิทึมที่ไม่ต่อเนื่องเกี่ยวกับตัวสร้างนี้สามารถคำนวณได้โดยง่ายโดยใครก็ตามที่รู้ $p$ และ $คิว$.

ในกรณีแรกของคุณที่ $n$ แบ่งลำดับของ $g$นี้เท่านั้นที่บอกเราว่า $x_p$ และ $x_q$ ไม่สามารถเพิกเฉยได้ มันไม่รับประกันว่า $x_\แลมบ์ดา$ สามารถเพิกเฉยได้และด้วยเหตุนี้ปัญหาของเราจึงยังคงยากอยู่

ในกรณีที่สองของคุณที่ $n$ ไม่แบ่งลำดับของ $r$ สิ่งนี้บอกเราว่าเช่นกัน $x_p$ สามารถละเว้นหรือ $x_q$ สามารถละเว้นได้ (อาจละเว้นได้ทั้งสองอย่าง) มันไม่รับประกันว่า $x_\แลมบ์ดา$ สามารถเพิกเฉยได้และปัญหาของเราอาจยังคงแก้ไขได้ยาก

โดยทั่วไป:

  • ถ้า $p$ ไม่แบ่งลำดับการกำเนิดแล้ว $x_p$ สามารถละเว้นได้
  • ถ้า $คิว$ ไม่แบ่งลำดับการกำเนิดแล้ว $x_q$ สามารถละเว้นได้
  • ถ้า $\แลมบ์ดา(n)$ ไม่แบ่งลำดับการกำเนิดแล้ว $x_\แลมบ์ดา$ สามารถละเว้นได้

โปรดทราบว่าหากเราทราบขอบเขตของขนาดของ $x$จากนั้นอาจไม่จำเป็นต้องกู้คืนองค์ประกอบทั้งสาม เช่น. ถ้าเรารู้ว่า $x<pq$ แล้วการกู้คืนของ $x_p$ และ $x_q$ ช่วยให้เราสามารถกู้คืนได้อย่างไม่ซ้ำใคร $x$ จากทฤษฎีบทเศษเหลือของจีน

*- โปรดทราบว่า $p$ และ $คิว$ ต้องมีโมดูลาลีขนาดใหญ่กว่าที่จะถูกโจมตีด้วยตะแกรงช่องตัวเลขแทนที่จะเป็นเพียงแค่ $n$ เป็นโมดูลัสที่ใหญ่กว่าที่สามารถโจมตีด้วยตะแกรงช่องหมายเลขได้

โพสต์คำตอบ

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