เหตุใด RLWE จึงเบากว่า LWE และเหตุใดเราจึงเลือก $a_i$ เป็นการเรียงสับเปลี่ยนของ $a_1$ ใน RLWE แต่ไม่ใช่ LWE

ใน LWE เรามี

$$<a_1,s> + e + \mu_1\in \mathbb{Z}_q$$

สำหรับรหัสลับ $s\in \{0,1\}^n$ และ $a_1\in \mathbb{Z}_q^n$

นี่คือการเข้ารหัสของตัวเลข $\mu_1$. หากเราต้องการเข้ารหัส $n$ แตกต่าง $\mu_i$, พวกเราต้องการ $n$ แตกต่าง $a_i$. กับ $n$ ค่า $a_{11}, ..., a_{1n}$ เราสามารถเข้ารหัสหนึ่งเดียว $\mu_1$.

สำหรับ RLWE เรามี

$$a*s +e + m \in \mathbb{Z}_q[X]^n$$

สำหรับ $a\in \mathbb{Z}_q[X]^n, e\in \mathbb{Z}_q[X]^n, m \in \mathbb{Z}_q[X]^n$, และ $*$ คือโมดูโลการคูณพหุนาม $x^n+1$. นี่คือการเข้ารหัสของพหุนาม $m$ และทำให้การเข้ารหัสของ $n$ ตัวเลข $m_1,...,m_n$. กับ $n$ ค่า $a_1, ..., a_n$ เราสามารถเข้ารหัสได้ $n$ ตัวเลข

ฉันคิดว่านี่คือสิ่งที่คำตอบนี้หมายถึงการอธิบาย: https://crypto.stackexchange.com/a/47602. สำหรับการเข้ารหัส $n$ ค่าใน LWE เราต้องการขนาดคีย์หลายค่า $n^2$ เนื่องจาก $a$'s. สำหรับ RLWE เราต้องการเพียงแค่ $n$. อย่างไรก็ตาม สำหรับ RLWE ในหน้า 5 ของ PDF เขาเชื่อมโยงเขาบอกว่าถ้าเราต้องการเข้ารหัส $n$ เวกเตอร์ เราสามารถเลือก $a_1\in \mathbb{Z}_q[X]^n$ และอื่น ๆ $a_i$ เป็นหน้าที่ของ $a_1$ แบบนี้: $$\vec{a_i} = (a_i, ..., a_n, -a_1, ..., -a_{i-1}).$$ ก่อนอื่น เหตุใดจึงทำได้สำหรับ RLWE แต่ไม่ใช่ LWE สำหรับ LWE เรามีระบบสมการเชิงเส้นประเภทหนึ่ง:

$$a_{i1}s_1 + a_{i2}s_2 + ... + a_{in}s_n + e_i = bi \mbox{ mod q}$$

ซึ่งน่าจะแก้ไขได้ยาก หากเราทำให้มันเป็นเช่นนั้น $a_{i}$ เป็นการสับเปลี่ยนของ $a_1$ แล้วคิดว่าปัญหาจะไม่ใช่เรื่องยากอีกต่อไป ฉันถูกไหม? แต่ทำไม RLWE ถึงยังยากอยู่? เป็นเพราะใน RLWE เราไม่มีระบบสมการใช่หรือไม่ เรามี

$$a_i*s +e_i + m_i = b_i \mbox{ mod $x^n$ + 1}$$

อาจจะ $a_i$ เป็นการสับเปลี่ยนของ $a_1$ ฉันเดาว่าที่นี่ยังคงปล่อยให้ปัญหาหนัก

ประการแรก Regev อธิบายว่า RLWE สามารถดูได้ว่าเป็นอินสแตนซ์ "ที่มีโครงสร้าง" ของ LWE นี้เป็นเพราะ

1. คุณสามารถอธิบายพหุนามในรูปของเวกเตอร์ได้ $\mathbb{Z}_q^n$,
2. คุณสามารถอธิบาย ส่วนที่เพิ่มเข้าไป ของพหุนามในรูปของ ส่วนที่เพิ่มเข้าไป ของเวกเตอร์ใน $\mathbb{Z}_q^n$, และ
3. คุณสามารถอธิบาย การคูณ ของพหุนาม $\bmod (x^n+1)$ ในแง่ของ "ผลคูณสเกลาร์ตลก" ของเวกเตอร์ใน $\mathbb{Z}_q^n$.

ขั้นตอนสุดท้ายเป็นเพียงขั้นตอนเดียวที่ไม่สำคัญ ฉันจะไม่สรุปทั้งหมดที่นี่ แต่สามารถแสดงให้เห็นว่า $i$ค่าสัมประสิทธิ์ของผลคูณพหุนาม $a(x)b(x)\bmod (q, x^n+1)$ เป็นรูปแบบ $\langle \vec b, \mathsf{negacyclic}^{\circ i}(\vec ก)\range$, ที่ไหน $\mathsf{negacyclic}^{\circ i}(\vec ก)$ คือ $i$แอพลิเคชัน -fold ของการดำเนินงานที่เลื่อนเป็นวงกลม $\vec ก$ (ไปทางซ้ายหรือขวา ฉันมักจะลืม) และคูณค่าสัมประสิทธิ์ด้วย $-1$ เมื่อพวกเขา "ล้อมรอบ" อย่างเป็นรูปธรรมก็คือ $i$- พับซ้ำของการดำเนินการ

$$(a_0,\dots,a_{n-1})\mapsto (-a_{n-1},a_0,\dots,a_{n-2}).$$

นี่คือการพูดหนึ่งสามารถ อย่างแน่นอน อธิบายอินสแตนซ์ RLWE $(ก(x), ก(x)s(x) + จ(x))$ โดยการเขียนสิ่งต่าง ๆ ใหม่ในรูปของเวกเตอร์จำนวนเต็ม โดยเฉพาะอย่างยิ่งถ้าคุณตั้งค่า $A$ ให้เป็นเมทริกซ์ต่อไปนี้ (โดยที่ $[ก,ข,ค]$ เป็นเมทริกซ์ที่มี คอลัมน์ $ก,ข,ค$)

$$A = [\mathsf{negacyclic}^{\circ 0}(\vec a),\mathsf{negacyclic}^{\circ 1}(\vec a),\dots, \mathsf{negacyclic}^{\ circ (n-1)}(\vec ก)],$$

จากนั้นอินสแตนซ์ RLWE ดังกล่าว อย่างแน่นอน สอดคล้องกับอินสแตนซ์ LWE $(ก, เป็น + จ)$. ดังที่ Regev กล่าวถึงสิ่งนี้ $A$ จะไม่สุ่มแบบสม่ำเสมออีกต่อไป $\mathbb{Z}_q^{n\times n}$อย่างที่มันเป็น โดยสิ้นเชิง ระบุโดย $O(n)$ องค์ประกอบ

ก่อนอื่น เหตุใดจึงทำได้สำหรับ RLWE แต่ไม่ใช่ LWE

เพื่อชี้แจงสิ่งที่กำลังดำเนินการคือ ดู RLWE เป็นรูปแบบโครงสร้างของ LWE. การแลกเปลี่ยนสมมติฐานบางอย่างของโครงสร้างใน $A$ เพื่อการประหยัดอย่างมีประสิทธิภาพ เนื่องจาก LWE เป็นเวอร์ชัน "ไม่มีโครงสร้าง" จึงไม่สามารถสันนิษฐานได้ว่ามีโครงสร้างในวัตถุ "ไม่มีโครงสร้าง"

หากเราทำให้มันเป็นเช่นนั้น $\vec a_i$ เป็นการสับเปลี่ยนของ $\vec a_1$ แล้วคิดว่าปัญหาจะไม่ใช่เรื่องยากอีกต่อไป

ในขณะที่เรากำลังเขียนอินสแตนซ์ RLWE ของเราใหม่ในภาษาอื่น เวอร์ชัน "LWE ที่มีโครงสร้าง" นั้นยากหากเวอร์ชัน RLWE นั้นยาก ดังนั้น RLWE จึงถูกมองว่าเป็นปัญหา (สำหรับการเรียงสับเปลี่ยนที่เหมาะสม) นิ่ง แข็ง.

โปรดทราบว่าการเรียงสับเปลี่ยนไม่ได้ผลทั้งหมด สิ่งนี้กลายเป็นเรื่องทางเทคนิคอย่างรวดเร็ว แต่ $\mathbb{Z}_q[x]/(x^n-1)$ ได้รับการพิจารณาเบื้องต้น (โดย Micciancio สำหรับตัวแปร Ring ของปัญหา SIS). พหุนามนี้ไม่สามารถลดทอนได้ (มีรากที่ $x = 1$). จากนั้นจะมีโฮโมมอร์ฟิซึ่ม (สอดคล้องกับการประเมินพหุนามที่ 1) ที่แมป $a(x) \in\mathbb{Z}_q[x]/(x^n-1)\to \mathbb{Z}_q$ซึ่งนำไปสู่การโจมตี อย่างไรก็ตาม สิ่งนี้มีความเกี่ยวข้องเนื่องจากการคูณบน $\mathbb{Z}_q[x]/(x^n-1)$ สอดคล้องกับ เป็นวงจร การสับเปลี่ยนของ $\vec ก$ (แทนที่จะเป็น เนกาไซคลิก ที่อธิบายไว้ข้างต้น)

ทั้งหมดนี้หมายความว่าชุดของอินสแตนซ์ RLWE ทั้งหมดสามารถดูเป็นชุดย่อยของชุดของอินสแตนซ์ LWE ทั้งหมดได้ จากมุมมองนี้ RLWE จะไม่ยากไปกว่า LWE --- อัลกอริทึมใด ๆ ที่ทำลาย LWE จะทำลาย RLWE อย่างเท่าเทียมกัน บางคนอาจสงสัยว่า "ชุดย่อย RLWE" นั้นง่ายกว่าเพียงใด --- มีปัญหาโครงตาข่ายที่ทราบกันดีซึ่งสิ่งต่างๆ ได้รับ มาก ง่ายขึ้นเมื่อคุณถือว่าโครงสร้าง (ฉันเชื่อว่า SIVP เป็นตัวอย่างหลัก) สำหรับปัญหา RLWE มีตัวอย่างเพิ่มเติมที่ ถ้ากำหนดพารามิเตอร์ผิด สิ่งต่างๆ ง่ายขึ้น เช่น เมื่อคุณใช้ $x^n-1$ พหุนามลดไม่ได้ นอกจากนี้ยังมีการโจมตีควอนตัมที่ไม่สำคัญกับตัวแปรที่ใกล้เคียงของปัญหา SVP สำหรับอินสแตนซ์ RLWE (ฉันเชื่อว่ามันเป็นปัญหาตัวสร้างหลักการสั้น ๆ )

ไม่มีนัยใด ๆ ข้างต้น (สำหรับพหุนามเช่น $x^{2^k}+1$ซึ่งใช้กันทั่วไป) โจมตี RLWE ได้ดีกว่าที่มีอยู่สำหรับ LWE มีผู้เขียนบางคน (คือเบิร์นสไตน์) ที่เชื่อว่าโครงสร้างพิเศษช่วยได้ [1] แต่ยังไม่มีการแสดงอย่างเป็นรูปธรรม

[1] เขาเชื่อว่ามีบางสิ่งที่เหมาะสมกว่าที่เกี่ยวข้องกับขนาดของกลุ่ม Galois ของพหุนามที่เลือก $ฉ(x)$ ใช้ใน RLWE พหุนาม $x^{2^k}+1$ มีกลุ่ม Galois ขนาดเล็กขนาด $O(\deg f)$. ขนาดของกลุ่ม galois สูงสุดคือ $O((\deg f)!)$, ใหญ่กว่ามาก. กลุ่ม galois ขนาดใหญ่เกิดขึ้นสำหรับพหุนามสุ่ม w.h.p. ดังนั้นจึง "มีโครงสร้างน้อยกว่า" มีการโจมตีที่ไม่รู้จักโดยใช้กลุ่ม Galois ขนาดเล็กของ $x^{2^k}+1$.

"เราเลือกได้ $a_i \in \mathbb{Z}_q[X]^n$" => ฉันคิดว่ามันควรจะเป็นแค่ $\mathbb{Z}_q^n$.

สิ่งที่คุณต้องเข้าใจในย่อหน้านี้คือความจริงที่ว่าการเข้ารหัส

$\mu_0, \จุด, \mu_{n-1}$ เห็นเป็นพหุนาม $\mu = \sum \mu_i X^i$ ด้วย RLWE และพหุนาม $\sum a_i X^i$เทียบเท่ากับการเข้ารหัสแต่ละพิกัด $\mu_j$ ด้วย LWE และเวกเตอร์ $\vec{a_j}=(a_{j}, a_{j+1}, \dots, a_{n-1}, -a_{1}, \dots, -a_{j-1})$.

ทำไมมันถึงเป็นความจริง? เพราะถ้าเราดูค่าสัมประสิทธิ์ของ $X^j$ ใน $a*s +e + \mu \in \mathbb{Z}_q[X]^n$เราได้รับอย่างแน่นอน

$<a_j,s> + e_j + \mu_j$ (กับ $e_j$ ค่าสัมประสิทธิ์ของ $X^j$ สำหรับพหุนาม $e$).

เกี่ยวกับความแข็งของสมมติฐาน: RLWE เป็นสมมติฐานที่แตกต่าง (และง่ายกว่า) มากกว่า LWE มีการศึกษาความปลอดภัยของมันอย่างอิสระ เกี่ยวกับสมมติฐานที่คุณเสนอ แต่ฉันแค่ตั้งข้อสังเกต:

• คุณไม่ได้บันทึก RLWE (เนื่องจากไฟล์ $-$).

• สำหรับการเรียงสับเปลี่ยนบางอย่าง ปัญหาจะง่ายขึ้นมาก:

ตัวอย่างเช่น ถ้า $\sigma = (1,2)(3,4)\dots(n-1, n).$ (ด้วยสัญกรณ์ของคุณมันคือ $i_j = i_j + 1$ ถ้า $i_j$ เป็นเรื่องแปลกและ $i_j -1$ ถ้าไม่ใช่).

จากนั้นเราก็มี $c_1= <a,s> + e_1 + \mu_1$, และ $c_2 = \sum^{n/2}_{j=1} (a_{2j}s_{2j-1} + a_{2j-1}s_{2j}) + e_2 + \mu_2.$

แล้ว $c_1 + c_2 = \sum^{n/2}_{j=1} (a_{2j}s_{2j-1} + a_{2j-1}s_{2j} + a_{2j}s_{2j} + a_{2j-1}s_{2j-1}) + e_1+ e_2 + \mu_1+ \mu_2.$

$=\sum^{n/2}_{j=1} (a_{2j} + a_{2j-1})(s_{2j-1} + s_{2j-1}) + e_1+ e_2 + (\ mu_1+ \mu_2).$

จากนั้นเราได้ลดขนาดของปัจจัย $2$.

ฉันจะถูกล่อลวงให้สรุปและพูดด้วยการเรียงลำดับ $k$คุณสามารถลดมิติของตัวประกอบได้ $k$ (ก็อาจจะไม่ปลอดภัย).