مسألة حل الأعداد الصحيحة القصيرة

قدّم ميتشيانسيو الشبكات الدورية في عمله لتعميم مسألة الحقيبة المدمجة على الحلقات العشوائية. ^{[ 2 ]} الشبكة الدورية هي شبكة مغلقة تحت تأثير عامل الإزاحة الدورانية. تُعرَّف الشبكات الدورية رسميًا كما يلي:

التعريف: شبكة${\displaystyle {\mathfrak {L}}\subseteq \mathbb {Z} ^{n}}$تكون دورية إذا${\displaystyle \forall {\boldsymbol {x}}\in {\mathfrak {L}}:\operatorname {rot} ({\boldsymbol {x}})\in {\mathfrak {L}}}$.

أمثلة: ^{[ 3 ]}

1. ${\displaystyle \mathbb {Z} ^{n}}$هي نفسها شبكة دورية.
2. الشبكات المقابلة لأي مثالي في حلقة كثيرات الحدود الخارجة${\displaystyle R=\mathbb {Z} [x]/(x^{n}-1)}$دورية:

لنعتبر حلقة كثيرات الحدود الخارجة${\displaystyle R=\mathbb {Z} [x]/(x^{n}-1)}$ودع${\displaystyle p(x)}$ليكن كثير الحدود في${\displaystyle R}$، أي${\displaystyle p(x)=\sum _{i=0}^{n-1}a_{i}x^{i}}$أين${\displaystyle a_{i}\in \mathbb {Z} }$ل${\displaystyle i=0,\ldots ,n-1}$.

حدد معامل التضمين${\displaystyle \mathbb {Z} }$تماثل الوحدات النمطية${\displaystyle \rho }$مثل:

${\displaystyle {\begin{aligned}\quad \rho :R&\rightarrow \mathbb {Z} ^{n}\\[4pt]p(x)=\sum _{i=0}^{n-1}a_{i}x^{i}&\mapsto (a_{0},\ldots ,a_{n-1})\end{aligned}}}$

يترك${\displaystyle I\subset R}$أن يكون مثالياً. الشبكة المقابلة للمثالي${\displaystyle I\subset R}$، ويرمز إليه بـ${\displaystyle {\mathfrak {L}}_{I}}$، هي شبكة فرعية من${\displaystyle \mathbb {Z} ^{n}}$ويُعرَّف بأنه

${\displaystyle {\mathfrak {L}}_{I}:=\rho (I)=\left\{(a_{0},\ldots ,a_{n-1})\mid \sum _{i=0}^{n-1}a_{i}x^{i}\in I\right\}\subset \mathbb {Z} ^{n}.}$

نظرية:${\displaystyle {\mathfrak {L}}\subset \mathbb {Z} ^{n}}$تكون دورية إذا وفقط إذا${\displaystyle {\mathfrak {L}}}$يتوافق مع بعض المثالية${\displaystyle I}$في حلقة كثيرات الحدود الخارجة${\displaystyle R=\mathbb {Z} [x]/(x^{n}-1)}$.

دليل:${\displaystyle \Leftarrow )}$لدينا:

${\displaystyle {\mathfrak {L}}={\mathfrak {L}}_{I}:=\rho (I)=\left\{(a_{0},\ldots ,a_{n-1})\mid \sum _{i=0}^{n-1}a_{i}x^{i}\in I\right\}}$

يترك${\displaystyle (a_{0},\ldots ,a_{n-1})}$ليكن عنصرًا عشوائيًا في${\displaystyle {\mathfrak {L}}}$ثم حدد${\displaystyle p(x)=\sum _{i=0}^{n-1}a_{i}x^{i}\in I}$لكن منذ ذلك الحين${\displaystyle I}$هو مثال، لدينا${\displaystyle xp(x)\in I}$. ثم،${\displaystyle \rho (xp(x))\in {\mathfrak {L}}_{I}}$. لكن،${\displaystyle \rho (xp(x))=\operatorname {rot} (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}_{I}}$. لذلك،${\displaystyle {\mathfrak {L}}}$هو دوري.

${\displaystyle \Rightarrow )}$

يترك${\displaystyle {\mathfrak {L}}\subset \mathbb {Z} ^{n}}$لنفترض أنها شبكة دورية.${\displaystyle \forall (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}:\operatorname {rot} (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}}$.

عرّف مجموعة كثيرات الحدود${\displaystyle I:=\left\{\sum _{i=0}^{n-1}a_{i}x^{i}\mid (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}\right\}}$:

1. منذ${\displaystyle {\mathfrak {L}}}$شبكة، وبالتالي مجموعة فرعية جمعية من${\displaystyle \mathbb {Z} ^{n}}$،${\displaystyle I\subset R}$هي مجموعة فرعية جمعية من${\displaystyle R}$.
2. منذ${\displaystyle {\mathfrak {L}}}$دوري،${\displaystyle \forall p(x)\in I:xp(x)\in I}$.

لذلك،${\displaystyle I\subset R}$هو مثال يُحتذى به، وبالتالي،${\displaystyle {\mathfrak {L}}={\mathfrak {L}}_{I}}$.

المصدر: ^{[ 4 ]}

يترك${\displaystyle f(x)\in \mathbb {Z} [x]}$ليكن متعدد حدود أحادي من الدرجة${\displaystyle n}$بالنسبة للتطبيقات التشفيرية،${\displaystyle f(x)}$يُختار عادةً ليكون غير قابل للاختزال. المثالي الناتج عن${\displaystyle f(x)}$يكون:

${\displaystyle (f(x)):=f(x)\cdot \mathbb {Z} [x]=\{f(x)g(x):\forall g(x)\in \mathbb {Z} [x]\}.}$

حلقة كثيرات الحدود الخارجة${\displaystyle R=\mathbb {Z} [x]/(f(x))}$الأقسام${\displaystyle \mathbb {Z} [x]}$إلى فئات تكافؤ من كثيرات الحدود من الدرجة على الأكثر${\displaystyle n-1}$:

${\displaystyle R=\mathbb {Z} [x]/(f(x))=\left\{\sum _{i=0}^{n-1}a_{i}x^{i}:a_{i}\in \mathbb {Z} \right\}}$

حيث يتم اختزال الجمع والضرب بتردد صفري${\displaystyle f(x)}$.

ضع في اعتبارك معامل التضمين${\displaystyle \mathbb {Z} }$تماثل الوحدات النمطية${\displaystyle \rho }$ثم، كل مثال في${\displaystyle R}$يُعرّف شبكة فرعية من${\displaystyle \mathbb {Z} ^{n}}$تسمى الشبكة المثالية .

تعريف:${\displaystyle {\mathfrak {L}}_{I}}$، الشبكة المقابلة لمثالي${\displaystyle I}$يُطلق عليه اسم الشبكة المثالية. وبشكل أدق، لنفترض حلقة متعددة الحدود خارج القسمة${\displaystyle R=\mathbb {Z} [x]/(p(x))}$، أين${\displaystyle (p(x))}$هو المثال الذي تولده الدرجة${\displaystyle n}$متعدد الحدود${\displaystyle p(x)\in \mathbb {Z} [x]}$. ${\displaystyle {\mathfrak {L}}_{I}}$، هي شبكة فرعية من${\displaystyle \mathbb {Z} ^{n}}$ويُعرَّف على النحو التالي:

${\displaystyle {\mathfrak {L}}_{I}:=\rho (I)=\left\{(a_{0},\ldots ,a_{n-1})\mid \sum _{i=0}^{n-1}a_{i}x^{i}\in I\right\}\subset \mathbb {Z} ^{n}.}$

ملاحظة: ^{[ 5 ]}

1. اتضح أن${\displaystyle {\text{GapSVP}}_{\gamma }}$حتى بالنسبة للصغار${\displaystyle \gamma =\operatorname {poly(n)} }$عادةً ما يكون الأمر سهلاً على الشبكات المثالية. والسبب البديهي هو أن التناظرات الجبرية تجعل أقصر مسافة للمثال تقع ضمن نطاق ضيق يسهل حسابه.
2. من خلال استغلال التناظرات الجبرية المتوفرة في الشبكات المثالية، يمكن تحويل متجه قصير غير صفري إلى${\displaystyle n}$مستقلة خطيًا ولها أطوال متقاربة. لذلك، على الشبكات المثالية،${\displaystyle \mathrm {SVP} _{\gamma }}$و${\displaystyle \mathrm {SIVP} _{\gamma }}$^{[ 6 ]} وهي متكافئة مع خسارة طفيفة. علاوة على ذلك، حتى بالنسبة للخوارزميات الكمومية ،${\displaystyle \mathrm {SVP} _{\gamma }}$و${\displaystyle \mathrm {SIVP} _{\gamma }}$يُعتقد أنها صعبة للغاية في أسوأ السيناريوهات.

يترك${\displaystyle A\in \mathbb {Z} _{q}^{n\times m}}$كن${\displaystyle n\times m}$مصفوفة ذات عناصر في${\displaystyle \mathbb {Z} _{q}}$والتي تتكون من${\displaystyle m}$متجهات عشوائية منتظمة${\displaystyle {\boldsymbol {a_{i}}}\in \mathbb {Z} _{q}^{n}}$:${\displaystyle A=[{\boldsymbol {a_{1}}}|\cdots |{\boldsymbol {a_{m}}}]}$أوجد متجهًا غير صفري${\displaystyle {\boldsymbol {x}}\in \mathbb {Z} ^{m}}$بحيث يكون ذلك لبعض المعايير${\displaystyle \|\cdot \|}$:

• ${\displaystyle 0<\|{\boldsymbol {x}}\|\leq \beta }$،
• ${\displaystyle f_{A}({\boldsymbol {x}}):=A{\boldsymbol {x}}={\boldsymbol {0}}\in \mathbb {Z} _{q}^{n}}$.

حل لمسألة SIS بدون القيد المطلوب على طول الحل (${\displaystyle \|{\boldsymbol {x}}\|\leq \beta }$يسهل حساب ) باستخدام تقنية الحذف الغاوسي . نحتاج أيضًا إلى${\displaystyle \beta <q}$، خلاف ذلك${\displaystyle {\boldsymbol {x}}=(q,0,\ldots ,0)\in \mathbb {Z} ^{m}}$إنه حل بسيط.

لضمان${\displaystyle f_{A}({\boldsymbol {x}})}$لدينا حل قصير وغير بسيط، ونحتاج إلى:

• ${\displaystyle \beta \geq {\sqrt {n\log q}}}$، و
• ${\displaystyle m\geq n\log q}$

نظرية: لأي${\displaystyle m=\operatorname {poly} (n)}$، أي ${\displaystyle \beta >0}$وأي حجم كبير بما فيه الكفاية${\displaystyle q\geq \beta n^{c}}$(لأي ثابت)${\displaystyle c>0}$حل${\displaystyle \operatorname {SIS} _{n,m,q,\beta }}$إن حل المسألة باحتمالية غير ضئيلة لا يقل صعوبة عن حل المسألة${\displaystyle \operatorname {GapSVP} _{\gamma }}$و${\displaystyle \operatorname {SIVP} _{\gamma }}$بالنسبة للبعض${\displaystyle \gamma =\beta \cdot O({\sqrt {n}})}$باحتمالية عالية في أسوأ السيناريوهات.

تُسمى مسألة SIS التي تُحل على حلقة مثالية أيضًا بمسألة Ring-SIS أو R-SIS. ^{[ 2 ] [ 9 ]} وتتناول هذه المسألة حلقة كثيرات الحدود الخارجة.${\displaystyle R_{q}=\mathbb {Z} _{q}[x]/(f(x))}$مع${\displaystyle f(x)=x^{n}-1}$لبعض الأعداد الصحيحة${\displaystyle n}$وببعض المعايير${\displaystyle \|\cdot \|}$ومن الحالات ذات الأهمية الخاصة تلك التي يوجد فيها عدد صحيح${\displaystyle k}$بحيث${\displaystyle n=2^{k}}$لأن هذا يقيد ناتج القسمة إلى كثيرات الحدود الدائرية. ^{[ 10 ]}

ثم نحدد المشكلة على النحو التالي:

يختار${\displaystyle m}$عناصر عشوائية منتظمة مستقلة${\displaystyle a_{i}\in R_{q}}$عرّف المتجه${\displaystyle {\vec {\boldsymbol {a}}}:=(a_{1},\ldots ,a_{m})\in R_{q}^{m}}$أوجد متجهًا غير صفري${\displaystyle {\vec {\boldsymbol {z}}}:=(z_{1},\ldots ,z_{m})\in R^{m}}$بحيث:

• ${\displaystyle 0<\|{\vec {\boldsymbol {z}}}\|\leq \beta }$،
• ${\displaystyle f_{\vec {\boldsymbol {a}}}({\vec {\boldsymbol {z}}}):={\vec {\boldsymbol {a}}}^{T}.{\vec {\boldsymbol {z}}}=\sum _{i=1}^{m}a_{i}.z_{i}=0\in R_{q}}$.

تذكر أنه لضمان وجود حل لمشكلة SIS، فإننا نحتاج إلى${\displaystyle m\approx n\log q}$ومع ذلك، توفر لنا مشكلة Ring-SIS مزيدًا من الإيجاز والفعالية: لضمان وجود حل لمشكلة Ring-SIS، نحتاج إلى${\displaystyle m\approx \log q}$.

التعريف: المصفوفة السالبة الدائرية لـ${\displaystyle b}$يُعرَّف على النحو التالي:

${\displaystyle {\text{for}}\quad b=\sum _{i=0}^{n-1}b_{i}x^{i}\in R,\quad \operatorname {rot} (b):={\begin{bmatrix}b_{0}&-b_{n-1}&\ldots &-b_{1}\\[0.3em]b_{1}&b_{0}&\ldots &-b_{2}\\[0.3em]\vdots &\vdots &\ddots &\vdots \\[0.3em]b_{n-1}&b_{n-2}&\ldots &b_{0}\end{bmatrix}}}$

عندما تكون حلقة كثيرات الحدود الخارجة${\displaystyle R=\mathbb {Z} [x]/(x^{n}+1)}$ل${\displaystyle n=2^{k}}$الضرب الحلقي${\displaystyle a_{i}.p_{i}}$يمكن حسابها بكفاءة عن طريق تشكيل${\displaystyle \operatorname {rot} (a_{i})}$، المصفوفة السالبة الدائرية لـ${\displaystyle a_{i}}$ثم الضرب${\displaystyle \operatorname {rot} (a_{i})}$مع${\displaystyle \rho (p_{i}(x))\in Z^{n}}$، متجه معامل التضمين لـ${\displaystyle p_{i}}$(أو بديلًا عن ذلك مع${\displaystyle \sigma (p_{i}(x))\in Z^{n}}$، متجه المعاملات الأساسية.

علاوة على ذلك، فإن مسألة R-SIS هي حالة خاصة من مسألة SIS حيث المصفوفة${\displaystyle A}$في مشكلة SIS، يقتصر الأمر على الكتل السالبة الدورانية:${\displaystyle A=[\operatorname {rot} (a_{1})|\cdots |\operatorname {rot} (a_{m})]}$[ ^{10 ]​}

تُسمى مسألة SIS التي تُحل على شبكة وحدات أيضًا مسألة Module-SIS أو M-SIS. ومثل R-SIS، تأخذ هذه المسألة في الاعتبار حلقة كثيرات الحدود الخارجة.${\displaystyle R=\mathbb {Z} [x]/(f(x))}$و${\displaystyle R_{q}=\mathbb {Z} _{q}[x]/(f(x))}$ل${\displaystyle f(x)=x^{n}-1}$مع اهتمام خاص بالحالات التي${\displaystyle n}$إذا كان 2 قوة للعدد 2، فلنفرض${\displaystyle M}$كن وحدة من الرتبة${\displaystyle d}$بحيث${\displaystyle M\subseteq R^{d}}$ودع${\displaystyle \|\cdot \|}$كن معيارًا اعتباطيًا على${\displaystyle R_{q}^{m}}$.

ثم نحدد المشكلة على النحو التالي:

يختار${\displaystyle m}$عناصر عشوائية منتظمة مستقلة${\displaystyle a_{i}\in R_{q}^{d}}$عرّف المتجه${\displaystyle {\vec {\boldsymbol {a}}}:=(a_{1},\ldots ,a_{m})\in R_{q}^{d\times m}}$أوجد متجهًا غير صفري${\displaystyle {\vec {\boldsymbol {z}}}:=(z_{1},\ldots ,z_{m})\in R^{m}}$بحيث:

• ${\displaystyle 0<\|{\vec {\boldsymbol {z}}}\|\leq \beta }$،
• ${\displaystyle f_{\vec {\boldsymbol {a}}}({\vec {\boldsymbol {z}}}):={\vec {\boldsymbol {a}}}^{T}.{\vec {\boldsymbol {z}}}=\sum _{i=1}^{m}a_{i}.z_{i}=0\in R_{q}^{d}}$.

على الرغم من أن M-SIS هو شكل أقل اختصارًا من R-SIS، إلا أن مشكلة M-SIS تُعتبر، من الناحية التقاربية، على الأقل بنفس صعوبة R-SIS، وبالتالي تُعطي حدًا أدق لفرضية صعوبة SIS. وهذا يجعل افتراض صعوبة M-SIS فرضية أساسية أكثر أمانًا، ولكنها أقل كفاءة عند مقارنتها بـ R-SIS. ^{[ 10 ]}