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

חתימה דיגיטלית מבוססת פונקציית גיבוב היא שם כולל לשיטות חתימה דיגיטלית חד-פעמית אשר ביטחונן מסתמך אך ורק על פונקציית גיבוב קריפטוגרפית ולא על קושיין המשוער של בעיות מתורת המספרים או בעיות אחרות שאין לגביהן הוכחה מתמטית שהן קשות. פונקציות גיבוב קיימות ונחקרות מזה זמן רב ואף שברובן עשויות אד הוק הן עדיין נמצאות בשימוש מעשי נרחב, נחשבות לבטוחות ומעולם לא נפרצו (דוגמאות הן SHA-2, BLAKE, SHA-3 או Skein). בנוסף הדעה הרווחת לגבי מרביתן, אם כי זה לא הוכח, שהן פוסט-קוונטיות. כלומר גם בהינתן מתקיף המצויד במחשב קוונטי לא יוכל לפרוץ את האלגוריתם, כלומר לא ימצא התנגשות בזמן פולינומי. חתימה מבוססת גיבוב בדרך כלל מהירה ובטוחה מאוד והיא נחשבת כיום לתשובה האטרקטיבית ביותר נגד קריפטואנליזה קוונטית כאשר היא תהיה רלוונטית. 
חסרונות חתימה דיגיטלית מבוססת גיבוב הן; אורך החתימה גדול מהמקובל בתקנים המעשיים וכן היא חד-פעמית, מסיבה זו היא נקראת "תלוית זיכרון" (stateful), יש צורך לנהל מעקב גם על ידי החותם וגם על ידי המאמת באמצעות מונה כלשהו, כדי לדעת כיצד לחתום או איך לאשר את החתימה על מסמך נתון. זהו מצב בלתי אפשרי במקרה הגרוע או שאינו נוח למימוש מעשי במקרה הטוב. תאורטית ידוע שאפשר לבנות חתימה דיגיטלית מבוססת פונקציית גיבוב נטולת זיכרון (stateless). נושא המחקר העיקרי כיום הוא להפוך פונקציה כזו לאלגוריתם פרקטי, שניתן יהיה לחתום באופן מאסיבי על מסמכים רבים כמעט ללא הגבלה ועם חתימות באורך סביר. כך שניתן יהיה להציעה כחלופה מיידית לאלגוריתמים המקבילים בתקנים הבינלאומיים ללא שינויים מרחיקי לכת במערכת.

רקע

הרעיון להשתמש בפונקציית גיבוב (או בכל פונקציה חד-כיוונית) לצורך חתימה דיגיטלית עלה לראשונה על ידי לזלי למפורט שהמציא ב-1979 את חתימת למפורט. חתימת למפורט היא חד-פעמית במובן שכל זוג מפתחות; מפתח חתימה/מפתח אימות ניתנים לשימוש רק פעם אחת. כדי להדגים זאת, נניח שאליס מעוניינת להעביר לבוב מסר פשוט "כן" או "לא" ('0' או '1'), באופן כזה שהוא ידע בוודאות שההוראה הגיעה ממנה ולא ממתחזה. דרך אחת לפתור את הבעיה, תחילה אליס בוחרת פונקציה חד-כיוונית בלתי הפיכה מוסכמת (כלומר ידועה לכל), בוחרת  אקראי כלשהו ומשתמשת בה כדי לחשב את  ושומרת בסוד את . היא שולחת לבוב את  כהתחייבות וכן מסכמת איתו מראש שעבור המסר "כן" אליס תחשוף בפניו את הסוד  כהוכחה, אחרת המסר יהיה "לא". לאחר מכן נניח שאליס שלחה לבוב את . בוב בודק שמתקיים  ואם כן הרי שההוראה "כן" הגיעה מאליס ולא מאף אחד אחר, משום שבעצם ידיעת  אליס הוכיחה שהמסר הגיע ממנה. מעצם ההגדרה של הפונקציה יהיה קשה מאוד למי שאינו יודע מהו  לנחש ערך כזה המקיים . 
כאן  הוא המפתח הפרטי או "מפתח החתימה" ו- הוא המפתח הציבורי או "מפתח האימות". היות שבמהלך האימות אליס למעשה חשפה את המפתח הפרטי שלה, היא לא יכולה להשתמש בו שוב לחתימה על מסר אחר. לכן עבור כל סיבית '0' או '1' נוספת היא צריכה לחשב ולשלוח  חדש, כלומר החתימה מתנפחת לממדים ארוכים מאוד ביחס למסר. אפשר להרחיב את הרעיון החתימה החד-פעמית באופן כזה שאליס תחתום על מספר סיביות בו זמנית כפי שעושה חתימת למפורט, אם כי הבעיה נותרת בעינה, מפתחות החתימה והאימות עדיין ארוכים מאוד וכל חתימה מתאימה למספר מוגבל של סיביות. בוב צריך לוודא שאכן  שייך לאליס אבל זהו נושא נפרד.

עץ אימות נטול זיכרון

ב-2004 הציע עודד גולדרייך שני שיפורים משמעותיים לאלגוריתם האמור כדי להופכו לאלגוריתם נטול זיכרון. ראשית הוא הציע שכל צומת (שאינו עלה) בעץ יכיל חתימה חד-פעמית על ערך הגיבוב של המפתח הציבורי של הצמתים הבנים שלו. המפתח הסודי יהיה גרעין התחלתי אקראי אשר ישמש לבניית העץ כולו באמצעות מחולל פסאודו-אקראי. מעצם הגדרתו של מחולל כזה אם מתחילים מגרעין התחלתי קבוע, תמיד יתקבל רצף זהה, עובדה זו מסייעת בשיחזור כל עלה רק כאשר הוא נדרש ואין צורך לבנות את כל העץ בזיכרון. שנית הוא הציע במקום לנהל מעקב אחרי החתימות שהשתמשו בהם באמצעות מונה כלשהו, לבחור עלה באופן שערכו נגזר מהמסר, מייצגים את ערך הגיבוב של המסר כמספר כלשהו באורך  סיביות ואז המספר הזה משמש כאינדקס לבחירת העלה המתאים לחתימה. בשיטה זו חתימה אחת תכיל את כל המפתחות הציבוריים של כל החתימות החד-פעמיות של הצמתים במסלול מהעלה לשורש העץ, את כל המפתחות הציבוריים של הצמתים האחים לאורך המסלול וכן את החתימה החד-פעמית של המסר עצמו. 
החתימה כעת נטולת זיכרון כי אין צורך לשמור מונה כלשהו ואין סיכוי שתהיה התנגשות, כלומר עלה אחד שאיתו נחתמו שני מסמכים שונים. שיטה אחרת שהציע היא לבחור עלה באופן אקראי אם מרשים סבירות מאוד קלושה להתנגשות. במקרה כזה אין צורך בגיבוב המסר לפני החתימה כדי לבחור עלה מתאים.
לסיכום מפתח החתימה הפרטי באורך  סיביות, חישוב החתימה על המסמך דורש  מפתחות ו- חתימות. את מפתחות החתימה של כל הצמתים במסלול אין צורך לצרף לחתימה על המסמך כי אפשר לחשב אותם מהמפתחות הציבוריים. אך בכל זאת החסרון הוא שחתימה חד-פעמית אחת היא באורך  מפתחות הציבוריים. שילוב של שיטת גולדרייך עם חתימת וינטרניץ מגיע לאורך חתימה של 1 מגה בית במקרה שפרמטר הביטחון הוא . 
אלגוריתם SPHINCS-256 משלב כמעט את כל הטכניקות המתוארות בנוסף לכמה שיטות חדשות כדי להפוך חתימה חד-פעמית לחתימה דיגיטלית רב-פעמית נטולת זיכרון ויעילה, עם ביטחון ברמה של  ועם מפתחות באורך 1 קילו בית וחתימה באורך 41 קילו בית.

תקנים

NIST הכינו טיוטה לתקן חדש לחתימה דיגיטלית מבוססת גיבוב הנחשבת בטוחה נגד קריפטואנליזה קוונטית (כאשר הדבר יהיה רלוונטי), היא מהירה ויעילה המשלבת כמה רעיונות ביניהם  שהוא וריאציה של חתימת וינטרניץ, XMSS ו-. בהתבסס על הצעה של Mecgrew ו-Curcio.