Score:2

Paillier เทียบกับ ElGamal ที่ยกขึ้นสำหรับการเพิ่มโฮโมมอร์ฟิคสำหรับการลงคะแนนทางอิเล็กทรอนิกส์

ธง ng

ฉันกำลังมองหาระบบ e-Voting ที่ไม่ระบุชื่อซึ่งจะกำหนดจำนวนบิตให้กับผู้สมัครแต่ละคนระหว่างการลงคะแนน เช่น 010000 สำหรับอลิซ 000100 สำหรับบ็อบ และ 000001 สำหรับชาร์ลี มันทำงานได้ดีกับ ElGamal ในสเกลที่เล็กลง แต่เมื่อฉันพยายามทำในสเกลที่ใหญ่ขึ้น (เพิ่มจำนวนมากขึ้น) มันหมดเวลา ในทางกลับกัน Paillier ดูเหมือนจะมีประสิทธิภาพมากกว่าในการเพิ่มจำนวนที่มากขึ้น

ฉันมีคำถามสองสามข้อเกี่ยวกับเรื่องนี้เนื่องจากฉันไม่ใช่ผู้เชี่ยวชาญด้านการเข้ารหัสลับ:

  • ElGamal มีปัญหากับการเพิ่มจำนวนที่มากขึ้นจริงๆ หรือเป็นเพราะข้อจำกัดในการใช้งาน มันจะสมเหตุสมผลเพราะมันใช้การยกกำลัง แต่ฉันต้องการยืนยัน
  • นอกจากนี้ เนื่องจาก Paillier อนุญาตทั้งการบวกและการคูณ จึงทำให้ "อ่อนตัว" และปลอดภัยน้อยกว่า ElGamal หรือไม่ ฉันไม่พบเมตริกใด ๆ ในการวิเคราะห์ความปลอดภัยเปรียบเทียบของพวกเขา แต่ฉันพบว่า ElGamal ควรจะมีประสิทธิภาพมากกว่า ดังนั้นคำถามเดิมของฉัน

อัปเดต: นี้ กระดาษบอกว่า: "ตัวอย่างเช่น เพื่อให้ได้ระดับความปลอดภัย 128 บิต ปกติจะใช้ 4096 บิต p และ 256 บิต q ใน ElGamal ในขณะที่ใน Paillier ขนาด n จะถูกเลือกให้เป็น 4096 บิต"

นั่นหมายความว่า Paillier อ่อนแอลงหรือไม่?

Score:1
ธง gb

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

ข้อแตกต่างที่สำคัญระหว่าง ElGamal และ ElGamal แบบเอกซ์โปเนนเชียลคือแทนที่จะเป็นข้อความ: $m$ คุณต้องเข้ารหัส $g^{m}$. ในการถอดรหัสนั่นหมายความว่าเราต้องแก้ปัญหาล็อกแยกเพื่อให้ได้มา $m$. สำหรับคนจำนวนน้อย นี่ไม่ใช่ปัญหาเลย (ดังนั้นจึงใช้งานได้ดีอย่างสมบูรณ์ในรูปแบบการลงคะแนน ซึ่งโดยทั่วไปแล้วจำนวนสะสมจะไม่มาก) แต่คุณพูดถูก เมื่อ $m$ ใหญ่ขึ้น สิ่งต่างๆ อาจยุ่งเหยิงและเชื่องช้า

เท่าที่ฉันรู้ คุณไม่มีข้อจำกัดนี้กับ Paillier

ความปลอดภัยของอัลกอริทึมเหล่านั้นมาจากสมมติฐานที่แตกต่างกัน ในขณะที่ El-Gamal พึ่งพา Diffie-Hellman (ตามลำดับ Decisional-Diffie-Hellman) Paillier ขึ้นอยู่กับ สมมติฐานความซ้ำซ้อนเชิงตัดสินใจ.

ฉันไม่ได้ตรวจสอบเอกสารที่เกี่ยวข้องเพื่อดูว่าพวกเขาเสนอหลักฐานความปลอดภัยใด แต่ฉันคิดว่าเมื่อคุณใช้งานอย่างเหมาะสมด้วยพารามิเตอร์ที่เหมาะสม ทั้งสองอย่างก็ใช้ได้กับระบบ e-voting โดยสิ้นเชิง

ng flag
ฉันได้แก้ไขคำถามเพื่อเพิ่มการวิจัย คุณคิดว่ามันสร้างความแตกต่างหรือไม่?
Reppiz avatar
gb flag
ความรู้ของฉันเกี่ยวกับรายละเอียดเฉพาะของอัลกอริทึมเหล่านั้นค่อนข้างจำกัด อย่างไรก็ตาม หากบทความระบุว่าพารามิเตอร์เหล่านี้ได้รับเลือกให้ได้รับความปลอดภัย 128 บิต ทั้งสองจะมีความปลอดภัย 128 บิตด้วยพารามิเตอร์ที่เกี่ยวข้อง ดังนั้น ความซับซ้อนของการโจมตีทั้งสองจะเท่ากับ $2^{128}$ (สำหรับพารามิเตอร์ที่กำหนด)
ng flag
ต้องใช้คีย์ที่ใหญ่กว่าสำหรับการรักษาความปลอดภัย 128 บิตหมายความว่าอย่างไร นั่นจะส่งผลให้เกิดไซเฟอร์เท็กซ์ที่ใหญ่ขึ้นหรือไม่?

โพสต์คำตอบ

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