ก่อนอื่นฉันขอนิยามให้ชัดเจนยิ่งขึ้นว่า "เหมือนกัน $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 ขวาน$.
ฉันอยากจะคิดว่าปัญหาทั้งสองเป็นเรื่องยาก แต่เท่าที่ฉันรู้ไม่สามารถลดปัญหาหนัก ๆ ที่ทราบได้