Score:2

*-LWE เทียบเท่ากับ Diffie-Hellman $g^{x^2}$ ช่องโหว่

ธง vu

ใน Diffie-Hellman ปลอดภัยน้อยกว่าเมื่อ A และ B เลือกหมายเลขสุ่มเดียวกันหรือไม่ ความเป็นไปได้ของการแลกเปลี่ยนคีย์ Diffie-Hellman ทำให้เกิดคีย์เพียร์ที่เหมือนกันและช่องโหว่ของมันต่อการโจมตีแบบพาสซีฟถูกหยิบยกขึ้นมาอีกครั้ง - ซ้ำกัน

แต่มีสิ่งเทียบเท่าในตระกูล *-LWE ของการแลกเปลี่ยนคีย์แบบ lattice-based หรือไม่? คำถามของฉันคือ โดยไม่พิจารณาถึงการชุบแข็ง CCA เช่นการแปลง Fujisaki-Okamoto และรูปแบบการเข้ารหัสแบบ LPR ทำการแลกเปลี่ยนคีย์ธรรมดา *-LWE:

  • Q1: มีช่องโหว่เทียบเท่าหรือไม่

  • Q2: คุณสมบัติทางคณิตศาสตร์ของการแลกเปลี่ยนคีย์ *-LWE ใดที่ทำให้ช่องโหว่ดังกล่าวเป็นไปได้หรือเป็นไปไม่ได้

DannyNiu avatar
vu flag
ฉันรู้ว่าฉันทำผิดพลาดเกี่ยวกับความเป็นไปได้ของการโจมตี Squre-Diffie-Hellman ฉันขอให้คนที่คุ้นเคยกับหัวข้อนี้แก้ไขส่วนที่ไม่ถูกต้องตามข้อเท็จจริงในคำถามของฉัน
Score:4
ธง ng

ที่ให้ไว้ $(ก, ขวาน + จ)$ และ $(A, x^tA+e')$คุณสามารถทำได้ (อย่างน้อย) สิ่งที่น่าสนใจอย่างหนึ่งในการแก้ LWE กล่าวคือ คำนวณตัวอย่าง

$$(A+ A^t, Ax + e + (x^tA+e')^t) = (A+A^t, (A + A^t)x + e + {e'}^t)$ $

คุณจึงสามารถลด LWE ลงเป็นกรณีของ LWE โดยที่เมทริกซ์สุ่ม $A + A^t$ เป็น สมมาตร. ฉันไม่ชัดเจนจริงๆ ว่าสิ่งนี้ช่วยให้คุณเข้ารหัสได้ --- มันแนะนำโครงสร้างบางอย่างในปัญหา แต่

  1. ดูเหมือนว่ามีโครงสร้างน้อยกว่าสมมติฐาน เช่น RLWE/MLWE แนะนำ (เช่น an $n$ เมทริกซ์สมมาตรเชิงมิติถูกกำหนดโดย $O(n^2)$ พารามิเตอร์ ในขณะที่คุณดูตัวอย่าง RLWE เป็น "เมทริกซ์" ก็มี $O(n)$ พารามิเตอร์)
  2. ยังไม่ชัดเจนว่าโครงสร้างจะมีประโยชน์อย่างไร

ในประเด็นสุดท้ายนี้ ฉันหมายความว่าฉันไม่รู้เป็นส่วนใหญ่ สมมาตร รหัสเชิงเส้นแบบสุ่ม (หรือตาข่ายสุ่ม) ง่ายกว่าในการแก้ CVP หากสิ่งนี้เป็นจริง มันจะบ่งบอกถึงช่องโหว่ที่คุณสนใจทันที

Score:3
ธง cn

ก่อนอื่นฉันขอนิยามให้ชัดเจนยิ่งขึ้นว่า "เหมือนกัน $x$" จู่โจม.

การตีความครั้งแรก

อลิซและบ็อบรู้จักพวกเขา $x$ เหมือนกัน. มันไม่สมเหตุสมผลเลย เพราะในสถานการณ์นี้ พวกเขาแบ่งปันข้อมูลลับอยู่แล้ว (พวกเขาสามารถคำนวณรหัสสาธารณะทั่วไปได้อยู่แล้ว $ก^x$ โดยไม่มีการติดต่อใดๆ)

การตีความครั้งที่สอง

สมมุติว่าฝ่ายตรงข้ามบังคับได้ (เราไม่รู้วิธี) $x$ ให้เท่ากับ $y$ (แต่อลิสกับบ๊อบไม่รู้เรื่องนั้นแล้วสื่อสารกัน $ก^x$). จากนั้นเป้าหมายของฝ่ายตรงข้ามคือการคำนวณ $g^{x^2}$ โดยรู้ $ก^x$. ปัญหานี้เป็นที่รู้กันว่ายากในโมเดลทั่วไป (คุณสามารถหาตัวอย่างได้ นี้) และอาจเป็นเรื่องยากสำหรับกลุ่มที่ได้รับการคัดเลือกมาอย่างดี

การตีความที่สาม

อลิซและบ็อบเคารพระเบียบปฏิบัติ แต่โชคไม่ดีที่พวกเขาเลือกแบบเดียวกัน $x$มันน่าทึ่งเกินกว่าที่ฝ่ายตรงข้ามจะตรวจพบกรณีนี้ได้อย่างง่ายดาย แต่คอมพิวเตอร์ $g^{x^2}$ ยากเหมือนกรณีที่สอง

เกี่ยวกับ LWE

ฉันจะพิจารณา รุ่นนี้ ของการแลกเปลี่ยนคีย์ DH:

เกี่ยวกับการตีความครั้งแรก มันไม่สมเหตุสมผลสำหรับ DH

ข้อสังเกตที่สำคัญคือความจริงที่ว่าแม้แต่อลิซและบ็อบก็มีเหมือนกัน $x$, คีย์บางส่วนที่ส่งมาไม่เหมือนกัน (ตรงกันข้ามกับคีย์ใน DH) ประการแรกเพราะพวกเขาคำนวณ $x^\perp A$ และ $ขวาน$และเนื่องจากไม่มีเหตุผลใดที่พวกเขามีเสียงเหมือนกัน

ด้วยเหตุนี้ การตรวจจับความเท่าเทียมกันในกรณีที่สามจึงไม่ใช่เรื่องเล็กน้อย (อย่างน้อยก็ไม่ใช่เรื่องเล็กน้อยเหมือนในกรณี DH)

เกี่ยวกับข้อเท็จจริงในการคำนวณความลับ $x$ ในกรณีที่สอง ดูเหมือนยาก แต่เท่าที่ฉันรู้ ไม่มีผลลัพธ์เกี่ยวกับความแข็งของปัญหาเฉพาะนี้

เราสามารถกำหนดปัญหาทั้งสองใหม่ได้ กำหนดเมทริกซ์สี่เหลี่ยม $A$, มันยากที่จะ แยกแยะ $(ขวาน+ 2e, x^\perp A+ 2e')$ และ $(ขวาน+ 2e, y^\perp A+ 2e')$? และให้ $(ขวาน+ 2e, x^\perp A+ 2e')$ เป็นการยากที่จะเดาส่วนที่มีนัยสำคัญน้อยที่สุดของ $x^\perp ขวาน$.

ฉันอยากจะคิดว่าปัญหาทั้งสองเป็นเรื่องยาก แต่เท่าที่ฉันรู้ไม่สามารถลดปัญหาหนัก ๆ ที่ทราบได้

โพสต์คำตอบ

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