חתימה דיגיטלית מבוססת פונקציית גיבוב
רקע > חתימה דיגיטלית מוכחת כבטוחה נגד התקפת מסר נבחר

רעיון דומה לעץ מרקל הוצע ב-1984 על ידי שפי גולדווסר, סילביו מיקלי ורונלד ריבסט במאמר חשוב המדגים מהיבט תאורטי מוכח כיצד אפשר להשתמש בזוג פונקציות חד-כיוונית עם דלת מלכודת הנקראות "Claw Free" לחתימה דיגיטלית. פונקציות שנקראות Claw-free הן שתי פונקציות  f_{0},f_{1} שבלתי אפשרי למצוא  X ו- Y כך שמתקיים  f_{0}(X)=f_{1}(Y) כמתואר בתרשים. הם הוכיחו שהשיטה שלהם בטוחה נגד "התקפת מסר-נבחר אדפטיבית" בהנחה שבעיית פירוק לגורמים היא בעיה קשה. אף על פי שהסכמה שלהם הודגמה עם פונקציית RSA הרי שאפשר לבנות חתימה כזו מכל פונקציה חד-כיוונית שעונה על התנאי האמור ולאו דווקא כזו המבוססת על פירוק לגורמים או לוגריתם בדיד.
התקפת מסר-נבחר אדפטיבית היא מודל ביטחון תאורטי החזק ביותר של פונקציית חתימה דיגיטלית. לפי מודל זה האויב או המתקיף רשאי לקבל מאורקל חתימות תקפות עבור מסרים כלשהם  m_{1},...,m_{k} לפי בחירתו ותפקידו לנסות לשבור את אלגוריתם החתימה על בסיס חתימות אילו וכן הוא רשאי לבקש חתימות נוספות גם לאחר שההתקפה החלה (מכאן הכינוי אדפטיבית). "שבירה" מחולקת לכמה רמות מהקל אל הכבד.
שבירה מוחלטת (total break). מציאת דרך לגלות את המפתח הפרטי (דלת המלכודת הסודית) של החותם ואז לזייף בקלות חתימה על כל מסמך ולטעון שנחתם על ידי החותם הלגיטימי.
זיוף כללי (universal forgery). מציאת דרך לעקוף את אלגוריתם החתימה כך שהתוקף מסוגל לדמות אותו ולזייף חתימות על מסמכים כלשהם מבלי לגלות את מפתח החתימה של החותם הלגיטימי.
זיוף סלקטיבי (selective forgery). מציאת דרך לזייף חתימה על מסמך ספציפי אחד או יותר שנבחרו על ידי המתקיף.
זיוף קיומי (existential forgery). זיוף חתימה על לפחות מסמך אחד כלשהו אפילו חסר משמעות ואפילו אם לתוקף אין שליטה על תוכנו.
ההגדרה האחרונה היא המחמירה ביותר ומבחינה תאורטית עדיף להגיע לסכמה שתהיה מוכחת כעמידה גם כנגד איום זה. הרעיון של אלגוריתם GMR הוא כדלהלן:
בהינתן שתי תמורות עם דלת מלכודת הנקראות Claw-free ופרמטר ביטחון  k יהיה קל לבחור באופן אקראי אלמנט מתחום הפונקציות, אך בהינתן תמורות כלשהן  f_{0},f_{1} יהיה קשה מבחינה חישובית למצוא  x,y כך שמתקיים  f_{0}(x)=f_{1}(y) ללא ידיעת דלת המלכודת. התכונה Claw-free משליכה גם על חד-כיווניות. למשל אם  n=pq כך ש- p\equiv 3{\text{ (mod }}8) ו- q\equiv 7{\text{ (mod }}8), אז הפונקציות  f_{0}^{n}(x)=x^{2}{\text{ (mod }}n) ו- f_{1}^{n}(x)=4x^{2}{\text{ (mod }}n) הן תמורות חד-כיווניות ומתאימות להגדרה Claw-free, כמו כן מתקיים  f_{i}^{-1}(f_{i}(x))=x ודלת המלכודת היא המספרים הראשוניים  p ו- q. אם נתון  Q רק מי שמחזיק במידע הסודי שהוא דלת המלכודת יכול לחשב את הערכים  R,L\in n כך שמתקיים  f_{R}^{-1}(Q)=L. תכונה זו נקראת "הוכחת אימות אטומית" של  L,R על ידי  Q כי רק מי שיכול להפוך את הפונקציה מסוגל לייצר את הערכים הללו מהערך  Q כך שהתנאי האמור יתקיים.
המפתחות הציבוריים לאימות החתימה על מסרים יהיו שני זוגות של תמורות חד-כיווניות  (g_{0},g_{1}),(f_{0},f_{1}). המפתחות הפרטיים המשמשים לחתימה הם דלתות המלכודת של הפונקציות הללו כך שהחותם יכול באמצעותן לחשב את הפונקציות ההופכיות שלהן בקלות. כעת אם נתון המסמך  M_{j} תחילה החותם מייצר ומאמת מספר אקראי  R_{j} ואיתו הוא מאמת את  M_{j}. את  R_{j} עצמו מאמתים בעזרת עץ אימות. מתחילים מ- R_{0} שהוא שורש העץ שנקרא מפתח ציבורי ומכל נקודת אימות  R_{j} או  L_{j} בהתאמה אפשר לאמת שני ערכים חדשים במקרה של צד ימין  (L_{2j+1},R_{2j+1}) ובמקרה של צד שמאל  (L_{2j},R_{2j}). בדרך זו נוצר עץ שגדל כלפי מטה ככל שנדרשות יותר חתימות כמתואר בתרשים. כל צומת מאמת את הצמתים הבנים. מכל צומת נתון קיים "מסלול אימות משורשר" לשורש  R_{0}. החתימה כוללת שני חלקים מלבד המסר עצמו.
הערכים  R_{j} ו- L_{j} המקיימים:
פונקציית אימות אטומית של המסר  M_{j} על ידי  R_{j}.
החתימה היא הערכים  (M_{j},A_{j},g_{m_{j}}^{-1}(R_{j})). ואימות החתימה מתבצע בשני שלבים, תחילה מאמתים את  R_{j} על ידי הפונקציות הציבוריות  f_{i} ואז מאמתים את המסמך על ידי הפונקציות  g_{i}. לפיכך הזמן הדרוש לחישוב חתימה הוא  O(k) ואורכה הכולל הוא  O(\log(j)\cdot k) כאשר  k הוא פרמטר ביטחון המייצג את אורך החתימה בסיביות. שים לב שגם אלגוריתם GMR נקרא תלוי זיכרון כיוון שכל חתימה תלויה בחתימות קודמות (כל  R_{j} תלוי באימות שלו על ידי ערכים קודמים)