הצגת המקור של הדף "הצפנה מבוססת סריג"

'''הצפנה מבוססת סריג''' (ב[[אנגלית]]: '''Lattice Based Cryptography''') כוללת [[פונקציה חד-כיוונית|פונקציות]] [[קריפטוגרפיה|קריפטוגרפיות]] (עם ביטחון מוכח) וקריפטואנליזה של פונקציות קריפטוגרפיות המבוססות על מבנה מתמטי שנקרא [[סריג (גאומטריה)|סריג]]. הצפנת [[מפתח ציבורי]] מבוססת סריג נשענת על הקושי שבפתרון [[בעיית הסריג]]. [[קריפטואנליזה]] של פונקציות אילו מבוססת על טכניקות [[רדוקציית סריג]].

הצפנת סריג עדיין בראשית דרכה ונעשית אטרקטיבית לאחרונה בשל החיפוש אחר מערכות הצפנה עמידות כנגד קריפטואנליזה [[הצפנה פוסט-קוונטית|פוסט-קוונטית]], כאשר מחשבים קוונטיים יהיו מעשיים. ב-1996 גילה Ajtai{{הערה|M. Ajtai and C. Dwork. A public-key cryptosystem with worst-case/average-case equivalence. In Proc. 29th ACM Symp. on Theory of Computing (STOC), pages 284-293. ACM, 1997.}}{{הערה|Ajtai, Mikls (1996). "Generating Hard Instances of Lattice Problems". Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. pp. 99–108}} תכונה חשובה של סריגים שמעניינת מהיבט קריפטוגרפי. מאז נעשים מאמצים לפתח מערכות הצפנה מבוססות סריג שתהיינה גם בטוחות לפי המבנה המקורי שהוצע וגם שתהיינה יעילות מבחינה מעשית כמו ממצאיו של Micciancio שחסרונן העיקרי שהן חסרות דלת מלכודת ולא ניתן להשתמש בהן עם מפתח הצפנה (הן שימושיות כפונקציה חד-כיוונית חסרת מפתח). ממצאים אחרים שיכולים להוביל לפיתוח מעשי של סכימות בטוחות מבוססות סריג הן של Micciancio ו-Vadhan שבהן אפשר לשתף סריג אחד על ידי משתמשים רבים והמפתח הציבורי של כל אחד יהיה מוכב מווקטור יחיד (המפתח הפרטי הוא הנקודה בסריג הקרובה ביותר לווקטור הציבורי) וכן [[הצפנת רגב]].

==היסטוריה ורקע==
[[קובץ:LatticeExample.png|שמאל|ממוזער|260px|דוגמה לסריג מעל <math>\mathbb{R}^2</math> ושני בסיסים, האדומים נקראים בסיסים "רעים" ואילו הכחולים נקראים בסיסים "טובים".]]
סריגים נחקרו על ידי מתמטיקאים במשך עשורים והם שימושיים במספר סוגיות כמו [[תכנון ליניארי]] ו[[פירוק לגורמים]]. העניין בסריגים עלה בשל מאפיין שימושי במיוחד לתחום הקריפטוגרפיה שהתגלה על ידי Ajtai ב-1996 קרי רדוקציה מהמקרה הגרוע למקרה הממוצע. הוא הוכיח שווריאציות מסוימות של [[בעיית התרמיל]] קשות לפתרון במקרה הממוצע לפחות כמו המקרה הגרוע של בעיות הסריג. עניין נוסף עלה בעקבות גילוי אלגוריתם [[LLL]] על ידי Lenstra, Lenstra ו-Lovasz ב-1982.

למשל פתרון בעיית SVP (הווקטור הקצר ביותר) עד קירוב פולינומי. בהנחה שלא קיים [[אלגוריתם]] פולינומי יעיל לחישוב SVP עד פקטור של <math>g=d^c</math> כאשר <math>d</math> הוא הממד של הסריג ו-<math>c</math> הוא קבוע בלתי תלוי, אפשר לבנות על בסיסה פונקציה חד-כיוונית קריפטוגרפית דומה לתרמיל (knapsack) שכמעט תמיד בטוח קשה אם המפתח נבחר באקראי. הצפנת סריג היא היחידה שקיימת הוכחה לגביה שהיא בטוחה כמו המקרה הגרוע אך זאת רק מנקודת ראות תאורטית, בעוד שמעשית החיסרון העיקרי של מערכת כזו הוא מפתח ההצפנה העצום.

בהשראת הרעיון של Ajtai פיתחו ב-1996 [[עודד גולדרייך]], [[שי הלוי]] ו[[שפי גולדווסר]] מערכת הצפנה מבוססת סריג (נקראת בקיצור [[GGH]]){{הערה|Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Public-key cryptosystems from lattice reduction problems. In CRYPTO ’97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, pages 112–131, London, UK, 1997. Springer-Verlag.}} עם יחס מקרה ממוצע/מקרה גרוע דומה, דהיינו פענוח אתגר אקראי נתון קשה לפחות כמקרה הגרוע של וריאציית SVP הנקראת uSVP (קיצור של unique SVP). הבעיה נעשית קלה ככל שפקטור הקירוב גדל, השאלה היא מהו הגורם <math>g</math> הקטן ביותר כך שאפשר יהיה לבנות פונקציה קריפטוגרפית הנחשבת קשה לפתרון לפחות כמו מציאת קירוב <math>g</math> לבעיית הסריג. Phong Nguyen{{הערה|Phong Q. Nguyen. Cryptanalysis of the Goldreich–Goldwasser–Halevi Cryptosystem from Crypto ’97. In CRYPTO ’99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, pages 288–304, London, UK, 1999. Springer-Verlag.}} פרסם והוכיח ב-1999 פגמים ב-GGH של גולדרייך, גולדווסר והלוי והציע דרכים לתיקון הבעיות שגילה. מסקנותיו הם שהאלגוריתם אינו יעיל מעשית. כדי שמערכת GGH תקרא בטוחה [[סדר גודל]] של מפתח ההצפנה צריך להיות ריבועי ביחס לפרמטר הביטחון <math>d</math>, מעשית זה יכול להגיע לאלפי סיביות. בימינו הממצאים הטובים ביותר הם פונקציית גיבוב חסינת התנגשויות של Micciancio המבוססת על אי-קירוב בטווח <math>g\approx d^{2.5}</math> וכן הצפנת רגב המבוססת על אי קירוב של בעיית uSVP בטווח <math>g\approx d^{1.5}</math>.

הבעיות שיש בהן עניין מנקודת ראות תאורטית הן בעיית הווקטור הקצר ביותר (בקיצור SVP) והכללה שלה שנקראת [[בעיית הווקטור הקרוב ביותר]] (CVP). מצד אחד הודות לאלגוריתם LLL ניתן לבצע קירוב יעיל בפתרון הבעיות האמורות עד כדי פקטור מעריכי מסדר גודל <math>2^{n\text{loglog}^2/\text{log }n}</math> כאשר <math>n</math> הוא ממד הסריג ועם אקראיות אפשר להגיע לסדר גודל של <math>2^{n\text{loglog}n/\text{log}n}</math>. מצד שני, עבור קבוע כלשהו <math>c>0</math> ידוע שלא קיים [[יעילות אלגוריתמית|אלגוריתם יעיל]] שיכול לבצע קירוב עד כדי <math>2^{c/\text{loglog}n}</math> אלא אם [[P=NP]]. הממצאים הללו אומתו אחר מחקרים שנעשו בתחום זה על ידי רבים.

ב-1996 הציע Jeffrey Hoffstein אלגוריתם הצפנה אסימטרי פרקטי שנקרא [[NTRU]] שיכול להגיע עם מפתח הצפנה קטן (בסדר גודל של כמה מאות סיביות) על ידי שימוש במחלקה מיוחדת של סריגים שמאפשרת ייצוג קומפקטי. האלגוריתם מבוסס על חוג פולינומי שנקרא [[קונבולוציה]] <math>R=\mathbb{Z}[X]/(X^N-1)</math> הפונקציה היא חישוב כפל וחיבור בפולינומיים מודולו <math>X^N-1</math>. הקשר לסריג הוא הקונבולוציה המודולרית, אפשר לראות שקיים [[הומומורפיזם]] בין הפולינומים בחוג R ומטריצה מעגלית בגודל <math>N\times N</math> עם מקדמים שלמים. הוכחת בטיחות האלגוריתם אינה לפי [[סיבוכיות]] המקרה הגרוע כמו במקרה של סריגים, ולמעשה קיימות מספר חולשות באלגוריתם שמאפשרות [[התקפת מוצפן-נבחר]] בגרסה המקורית.

==סריג==
סריגים ב[[תורת המספרים]] שנקראים גם "הגאומטריה של המספרים" ([[הרמן מינקובסקי]]), ניתנים להגדרה בכמה דרכים. בניסוח לא רשמי סריג הוא אוסף סדור של נקודות במרחב <math>n</math>-ממדי. בניסוח אחר, קבוצת כל הקומבינציות הליניאריות השלמות של וקטורים בלתי תלויים ליניארית מעל <math>\mathbb{R}^n</math>, כלומר אם <math>b_1,...,b_d</math> הם קבוצת וקטורים בלתי תלויים ליניארית אזי <math>\textstyle L=\{\sum_{i=1}^d n_i b_i | n_i\in \mathbb{Z}\}</math> ייקרא ''סריג'' והווקטורים <math>[b_1,...,b_d]</math> נקראים ''בסיס'' הסריג.

בניסוח פורמלי אם נתונים <math>x,y\in \mathbb{R}^n</math>, שני וקטורים <math>(x_1,...,x_n)</math> ו-<math>(y_1,...,y_n)</math> מעל המספרים הממשיים ויהי <math> \left\langle x,y\right\rangle</math> מכפלה אוקלידית של <math>x</math> עם <math>y</math> כך שמתקיים <math>\textstyle \left\langle x,y\right\rangle =\sum_{i=1}^n x_iy_i</math> וכן יהי <math>||x||</math> הנורמה האוקלידית של <math>x</math> כאשר <math>||x||=\left\langle x,x\right\rangle^{1/2}</math>. קבוצת הווקטורים <math>\{b_1,...,b_d\}</math> נקראת בלתי תלויה ליניארית מעל <math>\mathbb{R}</math> [[אם ורק אם]] תמיד מתקיים <math>\mu_1 b_1+\cdots +\mu_d b_d=0</math>. סריג היא תת-קבוצה <math>L\subseteq \mathbb{R}^n</math> כך שמתקיים <math>x-y\in L</math> כל עוד <math>(x,y)\in L^2</math> וכן קיים מספר ממשי <math>\rho>0</math> כך ש-<math>x\in L</math> ו-<math>||x||\le\rho</math> ו-<math>x=0</math>. לפי הגדרות אלו <math>\mathbb{Z}^n</math> הוא סריג כש-<math>\rho=1/2</math>. וכן כל תת-קבוצה של סריג היא סריג. בשל הדמיון למרחב הווקטורי תורת הסריגים מקבילה בכמה מובנים ל[[אלגברה ליניארית]]. בסיס הסריג אינו ייחודי, כלומר עבור סריג <math>L</math> מסדר <math>\ge 2</math> ישנם אין סוף בסיסים עם ממד זהה.

===בעיית הווקטור הקצר ביותר===
Shortest Vector Problem היא בעיית הסריג המפורסמת ביותר. בהינתן סריג <math>\mathcal{L}</math> המיוצג על ידי בסיס <math>B</math>, בעיית SVP היא למצוא את הווקטור הקצר ביותר ב-<math>\mathcal{L}</math> שאינו אפס. הבעיה יכולה להיות ביחס לכל [[נורמה (אנליזה)|נורמה]] המסומנת ב-<math>N</math> אך ה[[נורמה (אלגברה)|נורמה האוקלידית]] הכי נפוצה. גרסה אחרת של הבעיה היא לחשב רק את אורכו המסומן ב-<math>\lambda(\mathcal{L})</math> של הווקטור הקצר ביותר מבלי בהכרח למצוא את הווקטור עצמו הבעיה מסומנת על ידי <math>\text{SVP}_\gamma</math>. כאשר <math>\gamma=2^{n/2}</math> הבעיה ניתנת לפתרון בזמן פולינומי אולם כאשר <math>\gamma=1</math> האלגוריתם הטוב ביותר הידוע לפתרון בעיה זו הוא בסיבוכיות של <math>2^{O(n)}</math>. 

בעיית SVP נחקרה על ידי מתמטיקאים עשרות שנים בשל הקרבה שלה לבעיות שונות בתורת המספרים והיא משוערת כבעיית NP-קשה. [[המשפט הראשון של מינקובסקי]] הוא משפט מפתח בתורת הסריגים שאומר שאורכו המקסימלי של כל וקטור הקצר ביותר שאינו אפס בכל סריג מממד <math>n</math> הוא <math>\gamma_n \text{det}(L)^{-1}</math> כאשר <math>\gamma_n</math> הוא קבוע אבסולוטי שתלוי רק בממד <math>n</math> ו-<math>\text{det}(L)</math> הוא ה[[דטרמיננטה]] של הסריג. הגבול העליון של מינקובסקי צמוד למדי אך ישנם סריגים שבהם קיים וקטור קצר הרבה יותר. מינקובסקי לא סיפק אלגוריתם שמוצא וקטור כזה. אלגוריתם שמוצא וקטור קצר ביותר בסריג דו-ממדי היה ידוע כבר לגאוס במאה ה-19 אולם למקרה הכללי לא היה פתרון (קירוב של פתרון) עד תחילת שנות השמונים של המאה הקודמת עם המצאת LLL. האלגוריתם LLL יכול לבצע קירוב עד פקטור של <math>g=O((2/\sqrt{3})^n)</math> כאשר <math>n</math> הוא ממד הסריג. אלגוריתם אחר עם פקטור קירוב טוב יותר שהוא תת-מעריכי בזמן פולינומי הוא של שנור שנקרא Block Korkine-Zolotarev. לא קיים אלגוריתם פולינומי יעיל המחשב את אורך הווקטור הקצר ביותר בסריג (שלא לדבר על מציאת וקטור כזה) והיא משוערת כבעיה NP-קשה בטווח קירוב פחות מפקטור של <math>\sqrt{2}</math>.

===בעיית GapCVP===
בעיית ההכרעה של CVP הנקראת GapCVP היא כדלקמן: נתון סריג <math>\mathcal{L}(B)</math> עם בסיס <math>B\in Z^{m\times n}</math> וקטור <math>t\in Z^m</math> ו-<math>r\in Q</math> הפלט צריך להיות 1 אם <math>\text{dist}(t,\mathcal{L}(B))\le r</math> או 0 אם <math>\text{dist}(t,\mathcal{L}(B))>r</math>.

בעיית ההכרעה <math>\text{CVP}_\gamma</math> היא בהינתן סריג דומה להחזיר 1 אם <math>\text{dist}(t,\mathcal{L}(B))\le r</math> או 0 אם <math>\text{dist}(t,\mathcal{L}(B))>\gamma\cdot r</math>.

בעיית GapCVP היא NP-שלמה ברדוקציה מבעיית התרמיל.

==ראו גם==
* [[GGH]]
* [[NTRU]]
* [[הצפנת תרמיל]]

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

{{קריפטוגרפיה}}

[[קטגוריה:הצפנה]]