Score:3

การเข้ารหัสแบบ Lattice: ความลับจาก Gaussian distribution chi

ธง pl

ในการบรรยายโดย คริส พีเคิร์ต (ลิงค์ 40:20) เขาแสดงระบบเข้ารหัสลับที่มีประสิทธิภาพมากขึ้นซึ่งดึงความลับมาจากการกระจายข้อผิดพลาดแบบเกาส์เซียน $\chi$. ในการบรรยาย เขากล่าวว่า "บางแอปพลิเคชันที่ต้องการความลับจริง ๆ ที่มาจากการกระจายข้อผิดพลาด และพวกมันใช้งานไม่ได้จริง ๆ หากมาจากการกระจายแบบสม่ำเสมอ" และเขากล่าวเสริม "ด้วยเหตุผลแปลกๆ บางอย่าง นี่คือรูปแบบคือสิ่งที่ได้รับ คุณเพิ่มเติมในแง่ของการสร้างแอปพลิเคชันเช่น Full Homomorphic Encryption (FHE)"

  1. วันนี้เรารู้หรือไม่ว่าเหตุใดจึงเป็นเช่นนี้?
  2. การกระจายข้อผิดพลาดนำมาซึ่งประสิทธิภาพแบบใด?

แก้ไข: ปรับปรุงข้อมูล

Hilder Vitor Lima Pereira avatar
คุณแน่ใจหรือว่าเขากล่าวว่าแอปพลิเคชันใช้งานได้เฉพาะกับ Gaussian secret หรือข้อกำหนดคือความลับมีบรรทัดฐานเล็กน้อย? บางทีคุณควรตรวจสอบสิ่งนี้ เพราะแผนการ FHE บางอย่างทำงานได้ดีเมื่อความลับสั้น แต่ "สั้น" สามารถเป็นแบบ Gaussian, binary, ternary...
Karim avatar
pl flag
ขอโทษที่ตอบช้า ฉันพยายามหาที่ที่ฉันได้ยิน ดังนั้นจึงไม่ได้มาจาก Vadim Lyubashevsky แต่เป็น Chris Peikert ระหว่างโรงเรียนฤดูหนาว ฉันจะอัปเดตตามคำถามพร้อมลิงก์ไปยังการบรรยาย
Score:2
ธง in

การดำเนินการบางอย่างของ FHE เช่น “การสลับ/ลดโมดูลัส” จำเป็นต้องมี “ความลับเล็ก” LWE ในการทำงาน ในทำนองเดียวกัน ระบบเข้ารหัสบางอย่าง เช่น Lyubashevsky-Peikert-Regevâ10 และ Lindner-Peikertâ11 มีคีย์ที่เล็กกว่าและ/หรือ ciphertexts (และการทำงานที่เร็วขึ้นตามลำดับ) ด้วยการใช้ความลับที่มีขนาดเล็ก

ความลับที่เล็กกว่าให้ประสิทธิภาพที่ดีกว่าในระบบเหล่านี้ แต่เพื่อความปลอดภัยมีขีดจำกัดว่าเราสามารถทำได้เล็กแค่ไหน Applebaum-Cash-Peikert-Sahaiâ09 ได้รับการพิสูจน์แล้วว่าการดึงความลับ LWE จากการกระจายข้อผิดพลาด (ซึ่งให้ความลับที่ค่อนข้างเล็ก) มีความปลอดภัยไม่น้อยไปกว่าการใช้ความลับแบบสุ่มอย่างสม่ำเสมอ

Karim avatar
pl flag
ดังนั้น ถ้าผมเข้าใจถูกต้อง การดึงความลับจากการกระจายข้อผิดพลาด ฆ่านก 2 ตัวด้วยหินก้อนเดียว มันทำให้ความลับเล็ก ๆ น้อย ๆ โดยไม่สูญเสียความปลอดภัยโดยการทำให้ความลับเล็กเกินไป ถูกต้องหรือไม่?
Chris Peikert avatar
in flag
ใช่ นั่นเป็นฉบับย่อ
Hilder Vitor Lima Pereira avatar
[LWE ที่มีความลับไบนารีได้รับการพิสูจน์แล้วว่าปลอดภัย](https://theoryofcomputing.org/articles/v014a013/v014a013.pdf) คุณเพียงแค่ต้องเพิ่มมิติ $n$ อย่างไรก็ตาม ฉันคิดว่าไม่มีการลดกรณีที่เลวร้ายที่สุดถึงกรณีเฉลี่ยสำหรับ RLWE ที่มีความลับแบบไบนารีหรือไตรภาค แต่ผู้คนก็ใช้มันอยู่ดี เช่นใน HElib หรือ TFHE เนื่องจากยังคงเป็นไปได้ที่จะประเมินความปลอดภัยที่เป็นรูปธรรมสำหรับความลับดังกล่าว และ พวกมันสั้นกว่าเมื่อการกระจายเป็นแบบเกาส์เสียน...
Chris Peikert avatar
in flag
@HilderVitorLimaPereira ทั้งหมดนั้นเป็นความจริง อย่างไรก็ตาม การใช้ความลับแบบไบนารี/ไตรภาคนั้นตั้งอยู่บนพื้นฐานที่มั่นคงน้อยกว่า (ในแง่ของความปลอดภัย) มากกว่าการใช้การกระจายข้อผิดพลาด เนื่องจากมันอิงตามการเข้ารหัสที่รู้จักเท่านั้น ในขณะที่การใช้การกระจายข้อผิดพลาดมีการพิสูจน์ความแข็งอย่างแน่นหนาตามปัญหา LWE ดั้งเดิม ดังนั้นเราจึงมีการแลกเปลี่ยนทั่วไประหว่างสิ่งที่ดูเหมือนจะปลอดภัยกับสิ่งที่เราสามารถพิสูจน์ได้

โพสต์คำตอบ

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