בעיית תרמיל הגב קשורה בקשר הדוק עם סריגים. לאחר פרסום אלגוריתם LLL התברר שמערכת הצפנה מבוססת בעיית תרמיל הגב סובלת מבעיה מהותית. באופן כללי אם formula_1 כאשר formula_2 הוא פרמטר ביטחון (מפורט בהמשך) אז אלגוריתם לצמצום סריגים (Lattice reduction algorithm) מאפשר לגלות את הטקסט המקורי מתוך הטקסט המוצפן ללא ידיעת המפתח בזמן פולינומי. מאידך אם formula_3 אז המפתחות מגיעים לממדים עצומים בערך 176KB למפתח מה שהופך את המערכת לבלתי יעילה.
בעיית תרמיל הגב.
בעיית תרמיל הגב הנקראת גם בעיית הסכומים החלקיים - מהיבט קריפטוגרפי מוגדרת כדלהלן:
נתונה הסדרה formula_4 המכילה formula_2 איברים שלמים, כאשר formula_2 הוא פרמטר ביטחון (למשל formula_7):
ונתון שלם חיובי formula_9 הנקרא 'תרמיל גב'. הבעיה היא לגלות האם קיימת תת-קבוצה של איברים ב-formula_4 שסכומה הוא formula_9. במילים אחרות המטרה היא לגלות את הווקטור formula_12 המקיים:
דוגמה במספרים קטנים.
נניח ש-formula_14 ונתונה הסדרה:
אפשר לראות בניסוי וטעייה שהפתרון הוא תת-הסדרה formula_17 וקל לראות שזהו הפתרון היחיד במקרה זה. דרך אחרת להציג את הפתרון היא הווקטור formula_18 (כלומר הווקטור מכיל אחדים בכניסות המתאימות לאיברים הנכללים בסכום התרמיל ובכל היתר אפסים) במילים אחרות, אם ממספרים את כל האיברים בסדרה משמאל לימין formula_19 אז formula_20.
אפשר לפתור את הבעיה בכוח גס, פשוט על ידי ניסוי כל האפשרויות של הווקטור formula_21 עד למציאת הווקטור הנכון. סיבוכיות הפתרון היא מסדר גודל של formula_22, אולם אפשר לחתוך את סיבוכיות הפתרון בפקטור של שנים על ידי אלגוריתם ההתנגשות הבא.
אלגוריתם התנגשות לפתרון בעיית תרמיל הגב הכללית.
אם נתונה בעיית תרמיל-גב עם הפרמטרים formula_23 באורך formula_2 ושלם formula_9 אפשר לפעול כדלהלן:
מספר האלמנטים ב-formula_26 וב-formula_29 הוא לכל היותר formula_40 כל אחת ולכן זמן הריצה של האלגוריתם הוא formula_41 כאשר formula_42 הוא ערך קטן המייצג את התקורה הנוספת הנובעת מחישוב הרשימות ומיונן.
סדרה סוּפֶּר-עולה.
בעיקרון אם formula_2 גדול הפתרון המתואר אינו יעיל ולכן הבעיה הכללית מוגדרת קשה, אולם אינה מתאימה לקריפטוגרפיה כיוון שלא קיימת "דלת צונחת", אותו מידע סודי שהופך את פתרון הבעיה לקל מאוד למי שמחזיק בו ואילו עבור כל האחרים שאינם יודעים מהו הבעיה נותרת קשה. דרך אחת להכניס דלת צונחת היא להשתמש בבעיית תרמיל הגב עם תכונה מיוחדת שפתרונה קל. הרעיון של מרקל והלמן היה להשתמש בתרמיל גב המורכב מסדרה מונוטונית עולה שבה כל איבר גדול לפחות פי שניים מקודמו. בניסוח רשמי זוהי סדרה של formula_2 איברים שלמים formula_45 עם התכונה הבאה:
היא נקראת סופר-עולה (superincreasing) כיוון שעבור כל formula_48 מתקיים:
במקרה זה פתרון בעיית תרמיל הגב קל מאוד לפי האלגוריתם הבא: מבצעים רקורסיה שמתחילה באיבר האחרון (formula_51) כלפי מטה עד האיבר הראשון (formula_52) ובודקים עבור כל formula_53: אם formula_54 מציבים formula_55 ומחסרים formula_56 אחרת מציבים formula_57 וממשיכים עד ש-formula_58 (בהנחה שפתרון קיים).
לדוגמה הסדרה formula_59 היא סופר עולה, נניח שנתון השלם formula_60 מייצגים את formula_9 כסכום איברים בסדרה formula_62 כדלהלן: תחילה היות ש-formula_63 לכן formula_64 ומחליפים את formula_9 ב-formula_66. בשלב הבא היות ש-formula_67 מציבים formula_68. בשלב הבא רואים ש-formula_69 לכן formula_70 ו-formula_71. היות ש-formula_72 אנחנו יודעים ש-formula_73 ולבסוף formula_74 כי formula_75 ועוצרים כי formula_76. לסיכום, הפתרון הוא
הצפנת תרמיל גב של מרקל והלמן.
מרקל והלמן הציעו ב-1978 מערכת הצפנה המבוססת על בעיית תרמיל הגב עם סדרה סופר עולה שאותה מסתירים באמצעות שקילויות. כדי לייצר מפתח פרטי ומפתח ציבורי אליס בוחרת סדרה סופר עולה בעלת formula_2 איברים formula_45 כך שעבור כל formula_80 מתקיים formula_81 וכן בוחרת שני שלמים גדולים formula_4 ו-formula_83 המקיימים:
אליס מכינה סדרה formula_62 שאינה סופר עולה על ידי הכפלה ב-formula_4 כך:
הסדרה formula_62 היא המפתח הציבורי של אליס שהוסתר על ידי הכפל ב-formula_4 מודולו formula_83 ואילו המפתח הסודי כולל את הסדרה formula_95 והשלמים formula_4 ו-formula_83 בגלל החשבון המודולרי לא קל לנחש את formula_4 או formula_83 מתוך המפתח הציבורי. אם בוב רוצה להצפין את המסר formula_100 עבור אליס הוא משתמש במפתח הציבורי שלה ומחשב את
את הטקסט המוצפן formula_9 הוא שולח לאליס. לפענוח אליס פועלת כדלהלן, תחילה מחשבת את formula_103 דהיינו מכפילה את formula_9 בהופכי הכפלי של formula_4 מודולו formula_83 ואז משתמשת בסדרה הסופר עולה formula_95 כדי לפתור את בעיית תרמיל הגב עם formula_108. הסיבה שהפענוח נכון היא בשל הזהות הבאה:
היות ש-&lt;math&gt;S' מובטח לאליס שתקבל תוצאה מדויקת ולא רק שקילות כלשהי מודולו formula_83.
דוגמה במספרים קטנים.
נניח שאליס בחרה סדרה סופר-עולה סודית מהדוגמה הקודמת formula_111 וכן formula_112. כעת הסדרה המוסוות שלה formula_62 תהיה הכפלה של formula_95 ב-formula_4 כך שמתקבל:
שים לב שגם אם ממיינים את איברי M בסדר עולה הסדרה שהתקבלה רחוקה מלהיות סופר-עולה ולכן יהיה קשה לפתור את בעיית תרמיל הגב בסדרה זו לעומת הסדרה formula_95. כעת אם בוב מעוניין לשלוח לאליס את המסר formula_119, הוא מצפין אותו תחילה באמצעות הכפלה ב-formula_62 כך שמתקבל:
ושולח לאליס את formula_122. כאשר אליס מקבלת את הטקסט המוצפן formula_9 היא מכפילה אותו תחילה בהופכי של formula_124 מודולו formula_125 שהוא formula_126 ומתקבל:
כעת נותר לאליס להשתמש באלגוריתם המתואר לעיל כדי לפתור את בעיית תרמיל הגב בסדרה formula_95 עם הערך formula_129 וכך מחלצת את הטקסט המקורי formula_100.
ביטחון.
בעיית תרמיל הגב הכללית נחשבת ל-NP-קשה והיא מהווה מועמדת טובה לפונקציה חד-כיוונית. אולם לצורך קריפטוגרפי יש צורך גם בדלת צונחת שהיא המידע הנסתר המאפשר למקבל הלגיטימי לפתור את הבעיה בזמן פולינומי. הגרסה הראשונה של הצפנת תרמיל הגב שהסתמכה על סדרה סופר-עולה הכילה כמה חסרונות מהותיים שהעיקרית שבהן היא העובדה שתרמיל גב מכיל צפיפות נמוכה מדי מה שגורם לנקודת תורפה היות שבמקרה של תרמיל גב בעל תכונה זו קיימים אלגוריתמים יעילים לפתרון הבעיה. במרוצת הזמן הוצעו מספר רב של גרסאות משופרות שנועדו להתמודד עם הבעיות הללו בין היתר על ידי שימוש בתרמילי גב מרובים או הסתרה של תרמיל הגב באמצעות חשבון מודולרי ואלגברה בחוג הפולינומים.
ב-1985 פורסם בנפרד על ידי בריקל, לגריאס ואודליצקו אלגוריתם LO המסתמך על אלגוריתם צמצום סריגים (LLL) שמצליח לפתור את הבעיה כמעט תמיד בזמן פולינומי בתנאי שצפיפות תרמיל הגב נמוכה מ-0.6463. צפיפות תרמיל הגב formula_131 מוגדרת כדלהלן:
אלגוריתם CJLOSS משפר את החסם לגריאס-אודליצקו ל-formula_133. היות שהאלגוריתמים האמורים מסתמכים על צפיפות תרמיל הגב הם נקראים באופן כללי "התקפת צפיפות נמוכה". אולם הבעיה הכללית, דהיינו אם צפיפות תרמיל הגב גבוהה מהגבול האמור נותרה בעיה קשה. הרעיון של אלגוריתם LO הוא להמיר את הבעיה לבעיה אחרת מתורת הסריגים הנקראת בעיית מציאת הווקטור הקצר ביותר (SVP) שהיא בעיה קשה מאוד. אף על פי שלא קיים אלגוריתם פולינומי ל-SVP, מעשית אלגוריתם LLL של האחים לנסטרה ולובאז' מצליח לפתור את בעיית הווקטור הקצר בקירוב טוב, הרבה יותר ממה שמציע הגבול התאורטי. האמור הוא אם מתבצעת קריאה אחת לאורקל SVP. אולם במקרה של קריאות מרובות קיים שיפור שלו שנקרא אלגוריתם CJLOSS+ שמשפר את התוצאות האמורות מהיבט אסימפטוטי.
חוליו ג'ונס
קווינטוריס לופז "חוליו" ג'ונס (באנגלית: Quintorris Lopez "Julio" Jones; נולד ב-3 בפברואר 1989) הוא שחקן פוטבול אמריקאי המשחק בעמדת התופס בקבוצת טמפה ביי באקנירס מליגת ה-NFL.
ביוגרפיה.
ג'ונס נולד בפוליי שבאלבמה, הוא גדל עם אמו קווין מרווין ואחיו לאחר שאביו עזב את המשפחה כשהיה ג'ונס בן חמש. בתיכון הצטיין באתלטיקה וכדורסל ונחשב לאחד השחקנים הבולטים ביותר בארצות הברית בפוטבול. ב-2008 החל ללמוד באוניברסיטת אלבמה והשתלב בהרכב הפותח של קבוצת הפוטבול של האוניברסיטה. הוא זכה עם אלבמה באליפות המכללות ב-2009 לאחר עונה ללא הפסד ולאחר שלוש שנים החליט לוותר על שנתו האחרונה באוניברסיטה ולהעמיד עצמו לבחירה בדראפט ה-NFL.