חסרונות חתימה דיגיטלית מבוססת גיבוב הן; אורך החתימה גדול מהמקובל בתקנים המעשיים וכן היא חד-פעמית, מסיבה זו היא נקראת "תלוית זיכרון" (stateful), יש צורך לנהל מעקב גם על ידי החותם וגם על ידי המאמת באמצעות מונה כלשהו, כדי לדעת כיצד לחתום או איך לאשר את החתימה על מסמך נתון. זהו מצב בלתי אפשרי במקרה הגרוע או שאינו נוח למימוש מעשי במקרה הטוב. תאורטית ידוע שאפשר לבנות חתימה דיגיטלית מבוססת פונקציית גיבוב נטולת זיכרון (stateless). נושא המחקר העיקרי כיום הוא להפוך פונקציה כזו לאלגוריתם פרקטי, שניתן יהיה לחתום באופן מאסיבי על מסמכים רבים כמעט ללא הגבלה ועם חתימות באורך סביר. כך שניתן יהיה להציעה כחלופה מיידית לאלגוריתמים המקבילים בתקנים הבינלאומיים ללא שינויים מרחיקי לכת במערכת.
רקע.
הרעיון להשתמש בפונקציית גיבוב (או בכל פונקציה חד-כיוונית) לצורך חתימה דיגיטלית עלה לראשונה על ידי לזלי למפורט שהמציא ב-1979 את חתימת למפורט. חתימת למפורט היא חד-פעמית במובן שכל זוג מפתחות; מפתח חתימה/מפתח אימות ניתנים לשימוש רק פעם אחת. כדי להדגים זאת, נניח שאליס מעוניינת להעביר לבוב מסר פשוט "כן" או "לא" ('0' או '1'), באופן כזה שהוא ידע בוודאות שההוראה הגיעה ממנה ולא ממתחזה. דרך אחת לפתור את הבעיה, תחילה אליס בוחרת פונקציה חד-כיוונית בלתי הפיכה מוסכמת (כלומר ידועה לכל), בוחרת formula_1 אקראי כלשהו ומשתמשת בה כדי לחשב את formula_2 ושומרת בסוד את formula_1. היא שולחת לבוב את formula_4 כהתחייבות וכן מסכמת איתו מראש שעבור המסר "כן" אליס תחשוף בפניו את הסוד formula_1 כהוכחה, אחרת המסר יהיה "לא". לאחר מכן נניח שאליס שלחה לבוב את formula_1. בוב בודק שמתקיים formula_2 ואם כן הרי שההוראה "כן" הגיעה מאליס ולא מאף אחד אחר, משום שבעצם ידיעת formula_1 אליס הוכיחה שהמסר הגיע ממנה. מעצם ההגדרה של הפונקציה יהיה קשה מאוד למי שאינו יודע מהו formula_1 לנחש ערך כזה המקיים formula_2.
כאן formula_1 הוא המפתח הפרטי או "מפתח החתימה" ו-formula_4 הוא המפתח הציבורי או "מפתח האימות". היות שבמהלך האימות אליס למעשה חשפה את המפתח הפרטי שלה, היא לא יכולה להשתמש בו שוב לחתימה על מסר אחר. לכן עבור כל סיבית '0' או '1' נוספת היא צריכה לחשב ולשלוח formula_4 חדש, כלומר החתימה מתנפחת לממדים ארוכים מאוד ביחס למסר. אפשר להרחיב את הרעיון החתימה החד-פעמית באופן כזה שאליס תחתום על מספר סיביות בו זמנית כפי שעושה חתימת למפורט, אם כי הבעיה נותרת בעינה, מפתחות החתימה והאימות עדיין ארוכים מאוד וכל חתימה מתאימה למספר מוגבל של סיביות. בוב צריך לוודא שאכן formula_4 שייך לאליס אבל זהו נושא נפרד.
עץ מרקל.
רלף מרקל הראה שאפשר להקטין את המפתח האימות בדרך מקורית, במקום לשלוח עבור כל מסר formula_4 אחר, אפשר להשתמש בעץ גיבוב שהוא עץ בינארי מושלם בגובה formula_16 שבו כל צומת היא גיבוב של שני הצמתים הבנים מהעלים ועד לשורש העץ. מפתח האימות יהיה שורש העץ איתו יהיה אפשר לאמת עד formula_17 מסמכים המקבילים ל-formula_17 העלים, כל עלה הוא חתימה חד-פעמית של מסמך אחד. האימות נעשה על ידי בדיקת המסלול מהעלה ועד לשורש העץ. כל עלה מאומת על ידי חתימה חד-פעמית (OTS) שכוללת בתוכה גם מידע הנקרא "מסלול אימות" (authentication path) שהוא בעצם ערכם של עלים אחים לאורך המסלול מהעלה לשורש העץ על מנת לאפשר בניית מסלול אימות. בדרך זו אפשר להפוך חתימה חד-פעמית לחתימה "רב פעמית" חלקית, כי בעוד שנדרשים מפתחות חתימה שונים עבור כל המסמכים, הרי שנדרש מפתח אימות אחד בלבד.
עץ מרקל מהווה שיפור משמעותי אך למרות זאת אינו פרקטי מכמה סיבות:
כדי לפתור את הבעיות האמורות הוצעו מספר שיפורים. הראשון הוא חלוקת העץ לתת-עצים. למשל אם העץ מכיל יער של formula_22 שכבות של עצים המסודרים בערמה זה על גבי זה, כל אחד בגובה formula_23, במהלך החתימה על מסר נתון החותם משתמש רק בעץ אחד מתוכם. במקרה כזה המפתח הציבורי עבור formula_24 מסרים יקטן ל-formula_23 ערכים לכן החתימה מצטמצמת מ-formula_26 ל-formula_27. בנוסף אפשר לצמצם את החתימה על ידי ניצול העובדה שהיא סדרתית. כלומר שימוש באלגוריתם חכם לחיפוש בעץ שמאפשר צמצום החתימה מ-formula_26 ל-formula_29. שילוב שני הרעיונות יחד מאפשר לצמצם עוד את החתימה ל-formula_30.
עץ מרקל זכה לשיפורים רבים כמו FMTseq שהוא עץ חיפוש פרקטלי של נאור, שנהב ואבישי וול, אלגוריתם Bleichenbacher-Mauer המשתמש בגרפים או אלגוריתם עץ מרקל המורחב XMSS המשתמש בתת-עצים רבים וכן אלגוריתם SPHINCS. בשני האחרונים נוסף אלמנט מיסוך. כלומר כל ערך מחובר ב-XOR עם מסכה אקראית כלשהי לפני הפעלת פונקציית הגיבוב. המחיר הוא עליה קלה בסיבוכיות אבל הרווח הוא גדול, כי אלגוריתם מרקל המקורי דורש שאורך החתימות יהיה formula_31 סיביות כדי להגיע לרמת ביטחון של formula_32 סיביות בגלל התקפת יום הולדת. עם המסכה האקראית ניתן להגיע לביטחון של formula_33 סיביות עם פרמטר formula_34 שזהו שיפור בפקטור של חצי ביעילות האלגוריתם והפחתה דומה באורך החתימות.
חתימה דיגיטלית מוכחת כבטוחה נגד התקפת מסר נבחר.
רעיון דומה לעץ מרקל הוצע ב-1984 על ידי שפי גולדווסר, סילביו מיקלי ורונלד ריבסט במאמר חשוב המדגים מהיבט תאורטי מוכח כיצד אפשר להשתמש בזוג פונקציות חד-כיוונית עם דלת מלכודת הנקראות "Claw Free" לחתימה דיגיטלית. פונקציות שנקראות Claw-free הן שתי פונקציות formula_35 שבלתי אפשרי למצוא formula_36 ו-formula_37 כך שמתקיים formula_38 כמתואר בתרשים. הם הוכיחו שהשיטה שלהם בטוחה נגד "התקפת מסר-נבחר אדפטיבית" בהנחה שבעיית פירוק לגורמים היא בעיה קשה. אף על פי שהסכמה שלהם הודגמה עם פונקציית RSA הרי שאפשר לבנות חתימה כזו מכל פונקציה חד-כיוונית שעונה על התנאי האמור ולאו דווקא כזו המבוססת על פירוק לגורמים או לוגריתם בדיד.
התקפת מסר-נבחר אדפטיבית היא מודל ביטחון תאורטי החזק ביותר של פונקציית חתימה דיגיטלית. לפי מודל זה האויב או המתקיף רשאי לקבל מאורקל חתימות תקפות עבור מסרים כלשהם formula_39 לפי בחירתו ותפקידו לנסות לשבור את אלגוריתם החתימה על בסיס חתימות אילו וכן הוא רשאי לבקש חתימות נוספות גם לאחר שההתקפה החלה (מכאן הכינוי אדפטיבית). "שבירה" מחולקת לכמה רמות מהקל אל הכבד.
ההגדרה האחרונה היא המחמירה ביותר ומבחינה תאורטית עדיף להגיע לסכמה שתהיה מוכחת כעמידה גם כנגד איום זה. הרעיון של אלגוריתם GMR הוא כדלהלן:
בהינתן שתי תמורות עם דלת מלכודת הנקראות Claw-free ופרמטר ביטחון formula_40 יהיה קל לבחור באופן אקראי אלמנט מתחום הפונקציות, אך בהינתן תמורות כלשהן formula_35 יהיה קשה מבחינה חישובית למצוא formula_42 כך שמתקיים formula_43 ללא ידיעת דלת המלכודת. התכונה Claw-free משליכה גם על חד-כיווניות. למשל אם formula_44 כך ש-formula_45 ו-formula_46, אז הפונקציות formula_47 ו-formula_48 הן תמורות חד-כיווניות ומתאימות להגדרה Claw-free, כמו כן מתקיים formula_49 ודלת המלכודת היא המספרים הראשוניים formula_50 ו-formula_51. אם נתון formula_52 רק מי שמחזיק במידע הסודי שהוא דלת המלכודת יכול לחשב את הערכים formula_53 כך שמתקיים formula_54. תכונה זו נקראת "הוכחת אימות אטומית" של formula_55 על ידי formula_52 כי רק מי שיכול להפוך את הפונקציה מסוגל לייצר את הערכים הללו מהערך formula_52 כך שהתנאי האמור יתקיים.
המפתחות הציבוריים לאימות החתימה על מסרים יהיו שני זוגות של תמורות חד-כיווניות formula_58. המפתחות הפרטיים המשמשים לחתימה הם דלתות המלכודת של הפונקציות הללו כך שהחותם יכול באמצעותן לחשב את הפונקציות ההופכיות שלהן בקלות. כעת אם נתון המסמך formula_59 תחילה החותם מייצר ומאמת מספר אקראי formula_60 ואיתו הוא מאמת את formula_59. את formula_60 עצמו מאמתים בעזרת עץ אימות. מתחילים מ-formula_63 שהוא שורש העץ שנקרא מפתח ציבורי ומכל נקודת אימות formula_60 או formula_65 בהתאמה אפשר לאמת שני ערכים חדשים במקרה של צד ימין formula_66 ובמקרה של צד שמאל formula_67. בדרך זו נוצר עץ שגדל כלפי מטה ככל שנדרשות יותר חתימות כמתואר בתרשים. כל צומת מאמת את הצמתים הבנים. מכל צומת נתון קיים "מסלול אימות משורשר" לשורש formula_63. החתימה כוללת שני חלקים מלבד המסר עצמו.
החתימה היא הערכים formula_76. ואימות החתימה מתבצע בשני שלבים, תחילה מאמתים את formula_60 על ידי הפונקציות הציבוריות formula_78 ואז מאמתים את המסמך על ידי הפונקציות formula_79. לפיכך הזמן הדרוש לחישוב חתימה הוא formula_80 ואורכה הכולל הוא formula_81 כאשר formula_40 הוא פרמטר ביטחון המייצג את אורך החתימה בסיביות. שים לב שגם אלגוריתם GMR נקרא תלוי זיכרון כיוון שכל חתימה תלויה בחתימות קודמות (כל formula_60 תלוי באימות שלו על ידי ערכים קודמים)
עץ אימות נטול זיכרון.