Score:2

LWE และฟังก์ชั่นกรงเล็บประตูกลแบบขยายเพิ่มเติม

ธง sy

อนุญาต $q \geq 2$ เป็นจำนวนเต็มเฉพาะ พิจารณาสองฟังก์ชันที่กำหนดโดย:

$$f(b, x) = ขวาน + b \cdot u + e~~~(\text{mod}~q),$$ $$g(b, x) = ขวาน + b \cdot (As + e') + e~~~(\text{mod}~q),$$

ที่เรามี: \begin{จัด} ข &\in \{0, 1\}, \ x &\in \mathbb{Z}_{q}^{n}, \ s &\in \mathbb{Z}_{q}^{m}, \ &\in \mathbb{Z}_{q}^{n \times m}, \ e' &\in \mathbb{Z}_{q}^{m}, \ คุณ &\in \mathbb{Z}_{q}^{m}, \end{จัด}

$e$ สุ่มตัวอย่างจากการแจกแจง:

\begin{สมการ} D_{\mathbb{Z}_q, B^{'}}(x) = \frac{e^{\frac{- \pi ||x||^{2}}{B^{'2}}} }{\sum_{x \in \mathbb{Z}_q^{n}, ||x|| \leq B'} e^{\frac{- \pi ||x||^{2}}{B^{'2}}}}, \end{สมการ} ที่ไหน $$B' = \frac{q}{C_{T} \sqrt{mn \log q}},$$ $C_{T}$ เป็นค่าคงที่คงที่


ใน นี้ กระดาษ ฟังก์ชันที่กำหนดไว้ในสมการ 29 และมีการกล่าวถึงในกรณีที่เลวร้ายที่สุดกว่า $A$, $u$ และ $e'$สมมติว่า LWE ยากสำหรับอัลกอริธึมคลาสสิคของเวลาพหุนาม โดยแยกแยะระหว่าง $f$ และ $g$ ก็ยากเช่นกัน $A$ และให้ (พหุนามมาก) "ตัวอย่าง" (ตั้งแต่ $e$ เป็นการแจกแจงความน่าจะเป็น ผลลัพธ์ของ $f$ หรือ $g$ เป็นตัวอย่าง) จากอย่างใดอย่างหนึ่ง $f$ หรือ $g$.

การลด LWE ยังถือเป็นกรณีเฉลี่ย

กระดาษยังระบุด้วยว่าฟังก์ชันทั้งสองนี้เป็นตระกูลของ "ฟังก์ชันกรงเล็บประตูกับดักแบบขยาย (คำจำกัดความ 5, 6, 7)"

เพื่อเป็นการอ้างอิงถึงการพิสูจน์ข้อเท็จจริงข้างต้นเหล่านี้ กระดาษอ้างอิง นี้ กระดาษ (บทที่ 9.3) อย่างไรก็ตาม ในขณะที่พิสูจน์บทแทรก 9.3 เอกสารฉบับที่สองยังอ้างอิงเอกสารอื่นๆ เช่น นี้ หนึ่ง. หลักฐานไม่ชัดเจนสำหรับฉันในเอกสารใด ๆ


ฉันต้องการถามวิธีลดงานของการแยกแยะระหว่าง $f$ และ $g$ ถึง LWE ฉันยังต้องการถามเกี่ยวกับความสำคัญของฟังก์ชันที่ "ขยายกรงเล็บประตูกับดัก" ในการลดลงนั้น

จากความเข้าใจของฉันความแข็งของ LWE บอกว่าถ้าเราได้รับ $A$แยกแยะความแตกต่างระหว่างตัวอย่างสุ่มแบบสม่ำเสมอและตัวอย่างจาก $เป็น + e'$ เป็นเรื่องยาก ฉันไม่แน่ใจว่าเป็นอย่างไร $ข$ และ $x$ หรือพารามิเตอร์อื่น ๆ เป็นปัจจัยในข้อเท็จจริงนั้น นั่นคือจุดที่เราต้องการหลักฐานที่ปราศจากกรงเล็บแบบขยายประตูกับดักหรือไม่?

Score:2
ธง ng

ฉันคิดว่ามีจุดประสงค์ในการลดดังต่อไปนี้:

อนุญาต $D$ เป็นความแตกต่างสำหรับ $f, g$. สร้างความแตกต่าง $D'$ สำหรับ LWE ที่:

  1. ใช้เป็นอินสแตนซ์ LWE $(ก, ข')$
  2. สร้างออราเคิล $h_{A, b'}(b,x) = ขวาน + bb' + e\bmod q$
  3. จำลอง $D$ ด้วยการเข้าถึงของออราเคิล $h$และส่งกลับสิ่งที่ $D$ ทำ.

ดูเหมือนว่าค่อนข้างตรงไปตรงมาที่ศัตรูควรทำงาน เช่น:

  1. เมื่อไร $ข'$ เป็นแบบสุ่มอย่างสม่ำเสมอ $h_{A,b'}(b,x) = f(b,x)$
  2. เมื่อไร $b' = เป็น + e'$, $h_{A,b'}(b,x) = g(b,x)$

ข้อได้เปรียบที่คุณได้รับควรจบลงด้วยการเป็นอิสระจากอินสแตนซ์ LWE นั้น ๆ $(ก, ข')$ คุณใช้ในการลด ฉันคิดว่านี่คือจุดที่ "กรณีที่เลวร้ายที่สุดจบลง $A, u, e'$" มาจาก แต่ฉันไม่เคยได้ยินมาก่อน จึงไม่สามารถบอกได้อย่างแน่ชัดว่านี่คือสิ่งที่ผู้เขียนตั้งใจไว้

เป็นมูลค่าการกล่าวขวัญว่าฉันไม่เห็นที่ไหนที่คุณต้องการ $f, g$ เป็นฟังก์ชั่นที่ปราศจากกรงเล็บของประตูกล (หรืออะไรทำนองนี้) ฉันคิดว่าทั้งหมดที่เกิดขึ้นก็คือว่า $f, g$ แต่ละตัวอย่างมาจากการประมวลผลตัวอย่าง LWE หลังการประมวลผลอย่างมีประสิทธิภาพ (ตัวอย่างหนึ่งในโลกมาจากการแจกแจง LWE ซึ่งเป็นตัวอย่างแบบสุ่มอย่างสม่ำเสมอ) หากสิ่งนี้สามารถนำไปสู่การแยกแยะความแตกต่างได้ การโจมตี LWE จะเกิดขึ้นอย่างชัดเจน

BlackHat18 avatar
sy flag
เมื่อ $b' = As + e$, $h(b, x) = Ax + b(As + e) ​​+ e'$ แต่สำหรับสมการที่ 29 ของบทความนี้ (https://arxiv.org/pdf/2002.12814.pdf), $g(b, x) = Ax + b(As + e') + e$ สิ่งเหล่านี้เหมือนกันอย่างไร?
Mark avatar
ng flag
ฉันสลับ $e'\leftrightarrow e$ ซึ่งเป็นปัญหาด้านการพิมพ์ ถึงกระนั้น ประเด็นหลักก็คือหากการแจกแจง $D_0\about_c D_1$ สองครั้งใดๆ นั้นไม่สามารถแยกความแตกต่างทางการคำนวณ ดังนั้นต้องเป็น $h(D_0)\about_c h(D_1)$ สำหรับฟังก์ชัน $h$ ที่คำนวณได้อย่างมีประสิทธิภาพใดๆ ผลลัพธ์ตามมาด้วยการเลือก $h$ ที่ถูกต้อง
BlackHat18 avatar
sy flag
ฉันค่อนข้างสับสนเกี่ยวกับบางสิ่ง ให้ $(A, b')$ เป็นอินสแตนซ์ LWE อินพุต จากนั้น ในกรณีหนึ่ง $b'$ เป็นการสุ่มแบบสม่ำเสมอ แต่ในอีกกรณีหนึ่ง ไม่ใช่ $b' = As + e$ สำหรับข้อผิดพลาด Gaussian $e$ ใช่ไหม อย่างไรก็ตาม สำหรับกรณีที่สอง $b' = As + e'$ --- $e'$ ไม่ใช่ Gaussian error อีกต่อไป $e' \in \mathbb{Z}_{q}^{m}$
Mark avatar
ng flag
@ BlackHat18 นั่นไม่สำคัญ คุณพูดถูกว่าการสร้าง $f, g$ ใช้ได้กับ $e'$ ตามอำเภอใจ แต่เมื่อใช้ในการลดขนาดเป็น LWE คุณจะได้ $e'$ เป็น Gaussian

โพสต์คำตอบ

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