חתימה עיוורת

בקריפטוגרפיה ואבטחת מידע, חֲתִימָה עִוֶּרֶת (באנגלית: Blind Signature) היא צורת חתימה דיגיטלית שבה תוכן המסר החתום מוסתר מפני החותם בזמן החתימה עליו. החתימה העיוורת ניתנת לאימות באופן פומבי מול המסר הגלוי באותו אופן שבו מבוצע אימות חתימה דיגיטלית רגילה למרות שהחותם לא היה מודע לתוכן המסר בעת החתימה. חתימה עיוורת שימושית במגוון תחומים בהם דרושה אנונימיות כמו הצבעה ממוחשבת או מסחר במטבע דיגיטלי.

רעיון החתימה העיוורת הועלה לראשונה ב-1983 על ידי דויד צ'אום שנחשב לאחד מחלוצי המטבע הדיגיטלי. הוא הדגים לראשונה את החתימה העיוורת באמצעות אנלוגיה למעטפת הצבעה עם נייר פחם. המצביע מכניס פתק הצבעה שאליו מוצמד נייר פחם לתוך מעטפה עליה מודפסים פרטיו האישיים, הגורם המאשר בודק את פרטי המצביע המופיעים על גבי המעטפה וחותם עליה בחתימתו. חתימת הגורם המאשר עוברת לפתק ההצבעה באמצעות נייר הפחם. כעת המצביע יכול להוציא את פתק ההצבעה החתום ולשלוח אותו בדואר לקלפי במעטפה לא מזוהה. בכל שלב ניתן לבדוק את תקפות ההצבעה על ידי בדיקת החתימה שעל הפתק. למרות שהגורם שמודע לזהות בעל פתק ההצבעה אינו יודע למי הצביע כי הפתק הוסתר בתוך מעטפה אטומה.

סכמת הצבעה דיגיטלית בסיסית

באותה מידה יכולה חתימה עיוורת לשמש כלי עזר לתשלום מזומנים דיגיטליים ללא אפשרות מעקב. כלומר החתימה באופן זה מונעת מהבנק ליצור זיקה בין הכסף החתום לבין עסקה שנעשתה איתו מאוחר יותר, או בין גרסה מוסתרת של המטבע לבין גרסה גלויה שלו. דבר שיכול לעזור בשמירה על אנונימיות המשלם בדומה לשימוש במזומנים בשיטה המסורתית, תוך מניעה של בזבוז כפול.

אפשר להכין חתימה עיוורת באמצעות כל שיטת הצפנה אסימטרית הומומורפית חלקית כמו RSA, אל-גמאל, הצפנת פליאיי או אוקמוטו-אושיאמה. באופן פורמלי חתימה עיוורת היא פרוטוקול קריפטוגרפי בין שתי ישויות אליס ובוב. אליס מעוניינת להחתים את בוב על מסר כלשהו שהיא הכינה. בגמר הפרוטוקול אליס השיגה את חתימתו של בוב על המסר מבלי שיגלה דבר בנוגע למסר עליו חתם. וכן כל אחד מסוגל לוודא שאכן החתימה של בוב על המסר תקפה מבלי הצורך לדעת מיהו בעל המסר. במידה מסוימת יש קשר בין פרוטוקול זה לפרוטוקול הוכחה באפס ידיעה, שבו המוכיח מצליח לשכנע את המוודא בדבר אמיתות טענה מסוימת מבלי לחשוף בפניו את הטענה עצמה. למעשה דויד צ'אום, עמוס פיאט ומוני נאור פיתחו פרוטוקול למטבע דיגיטלי המסתמך על אפס ידיעה שמאפשר לאליס לשמור על האנונימיות שלה כל עוד היא אינה מרמה. העונש במקרה של הונאה הוא חשיפת זהותה.

מבוא

ערך מורחב – חתימה דיגיטלית

חתימה דיגיטלית היא תוצר של הצפנת מפתח ציבורי או הצפנה א-סימטרית שבה המערכת מפוצלת לשני חלקים נפרדים, שלב ההצפנה המקביל לשלב החתימה ושלב הפענוח המקביל לשלב אימות החתימה. כל אחד יכול לאמת חתימה המצורפת למסמך כלשהו באמצעות המפתח הציבורי של החותם אך רק החותם שמחזיק במפתח הפרטי יכול לחתום חתימה תקפה בשמו ובהגדרה אין אפשרות (או קשה מאוד) לנחש מהו מפתח החתימה הפרטי בידיעת מפתח האימות הציבורי. חתימה דיגיטלית כוללת פונקציית חתימה $S$ ופונקציית אימות $V$ כך שהתוצאה של $V(S(m))$ על המסר $m$ היא הוכחה לתקפותה. השיטה המפורסמת ביותר לחתימה דיגיטלית היא שיטת RSA המבוססת על העובדה שמצד אחד קל לבצע העלאה בחזקה ומצד שני קשה לפרק לגורמים מספרים שלמים. אליס בוחרת שני מספרים ראשוניים גדולים $p$ ו-$q$ ומחשבת את $n=pq$. כמו כן היא מגרילה מספר שלם $e$ שהוא זר ל-$\phi (n)$, מחשבת את המפתח הסודי $d$ כך שמתקיים $ed\equiv 1{\text{ (mod }}\phi (n))$. כאשר $\phi (n)$ הוא פונקציית אוילר של $n$ שהיא במקרה זה $(p-1)(q-1)$. את $e$ ואת $n$ היא מפרסמת לכל דורש ואילו את $d$ ואת $p$ ו-$q$ היא שומרת בסוד. כדי לחתום על המסר $m$ היא מחשבת את $s=m^{d}{\text{ (mod }}n)$ אותו היא שולחת לבוב יחד עם המסר $m$. כדי לאמת את החתימה בוב מחשב את $m'=s^{e}{\text{ (mod }}n)$ ורק אם מתקיים $m=m'$ הוא מקבל את החתימה. זה נכון בשל הזהות הבאה:

$s^{d}=(m^{e})^{d}=m^{ed}=m^{1+\phi (n)k}\equiv m{\text{ (mod }}n)$

כי לפי אוילר $m^{\phi (n)}\equiv 1{\text{ (mod }}n)$ עבור כל $m$ ולכן גם $m^{1+\phi (n)}\equiv m{\text{ (mod }}n)$. היות שאף אחד חוץ מאליס אינו יודע מהם $d$ או $\phi (n)$ כיוון שהם מעולם לא פורסמו ולא ניתן לחשב אותם מתוך $e$ ו-$n$ מבלי לדעת מהם הגורמים הראשוניים, זהו מאפיין יסודי של הצפנה אסימטרית, לכן בוב יכול לקבל את החתימה כאותנטית. כמובן שהשיטה המתוארת נועדה רק להדגים את הקונספט של חתימה דיגיטלית, אין לראות בה בשום אופן שיטה מעשית לחתימה דיגיטלית. בפועל מיישמים חתימה דיגיטלית באופן אחר לגמרי כדי למנוע התקפות קריפטוגרפיות ידועות. אפשר לבסס חתימה דיגיטלית על מערכות הצפנת מפתח ציבורי אחרות כמו חתימה דיגיטלית של רבין המבוססת על הצפנת רבין או DSA המבוססת על הצפנת אל-גמאל.

אפשר להרחיב כמעט כל פרוטוקול חתימה דיגיטלית לחתימה דיגיטלית עיוורת. הטכניקה הראשונה שפורסמה הייתה של דויד צ'אום, שהתאים את חתימת RSA ב-1992 פרסם אוקמוטו גרסת חתימה עיוורת המבוססת על חתימת שנור.

הצבעה דיגיטלית עם חתימה עיוורת

מאפיין רצוי בהצבעה דיגיטלית הוא שאימות זהות המצביע יהיה מופרד מאימות ההצבעה עצמה. חתימה דיגיטלית רגילה יוצרת זיקה בין המצביע לפתק ההצבעה ולכן אנונימיות המצביע נפגעת. מצד שני בהצבעה מקוונת גובר הסיכון להצבעה כפולה או התחזות והונאה. פרוטוקול הצבעה אנונימי מפריד בין תהליך אימות המצביע לבין תהליך אימות ההצבעה באופן כזה שהגורם המאשר את זהות המצביע אינו מסוגל לשייך או ליצור זיקה בינו לבין פתק ההצבעה שלו ומצד שני המצביע אינו יכול להצביע פעמיים או להתחזות למצביע אחר. באופן כללי פרוטוקול הצבעה עם חתימה עיוורת מכיל את המאפיינים הבאים. נניח שהמצביע הוא בוב והגורם הרשמי המאשר את ההצבעה היא אליס.

• בוב יוכל להוכיח לאליס את זהותו האמיתית והיא תוכל לבדוק בהתאם את זכאותו להצבעה.
• לא יהיה אפשרי לשכפל את החתימה של אליס.
• כל אחד יכול לוודא שהחתימה של אליס תקפה.
• בוב יכול להצביע באופן כזה שאליס לא תוכל לדעת מה הצביע.
• ההבדל היחידי בין פתק ההצבעה שבוב שלח לאליס לבין פתק ההצבעה שהוא הניח בקלפי הוא החתימה של אליס.

אם מתרגמים את המושגים הללו לשפה קריפטוגרפית אז שלוש הדרישות הראשונות מקבילות לתהליך אימות קריפטוגרפי עם חתימה דיגיטלית קונבנציונלית. חתימת אליס היא $S_{a}$ ופונקציית האימות הציבורית שלה היא $V_{a}$ כך שמתקיים $V_{a}(S_{a}(M))=M$. שתי הדרישות האחרונות אומרות שהבוחר בוב צריך להצפין את פתק ההצבעה שלו באמצעות פונקציית הצפנה כזו כך שפתק ההצבעה ניתן יהיה לאימות גם במצבו הגלוי (לאחר פענוח). לשם המחשה נניח שפתק ההצבעה של בוב מסומן באות $B$, פונקציית ההצפנה שלו היא $E_{b}$ ופונקציית הפענוח שלו היא $D_{b}$ אז צריך שיתקיים $D_{b}(S_{a}(E_{b}(B)))=S_{a}(B)$. אפקטיבית, פעולת הפענוח של בוב מסירה את ההצפנה שלו על הפתק מבלי לפגוע בתקפות החתימה. קיימות מספר פונקציות הצפנה שמקיימות את הדרישה האמורה, אפשר למשל להשתמש ב-RSA, אך יש להיזהר ממלכודות, בדרך כלל משתמשים בהצפנת פליאיי. תהליך ההצבעה יבוצע כדלהלן:

1. בוב מצפין את פתק ההצבעה שלו $E_{b}(B)$ ושולח אותו מאומת לאליס (הם משתמשים בפרוטוקול אימות בנפרד מפרוטוקול זה).
2. אליס מאמתת את זהותו של בוב וחותמת על פתק ההצבעה המוצפן $S_{a}(E_{b}(B))$ ומחזירה אותו לבוב.
3. בוב מפענח את המסר החתום שקיבל $D_{b}(S_{a}(E_{b}(B)))$ ומקבל את $S_{A}(B)$. כדי למנוע מרמאי מלהחליף את פתק ההצבעה שלו במהלך המשלוח הוא מוודא שמתקיים $V_{a}(S_{a}(B))=B$.
4. בוב שולח את פתק ההצבעה שלו $S_{a}(B)$ לקלפי באופן אנונימי.

היות שפונקציית האימות של אליס ציבורית כל אחד יכול לחשב את $V_{a}(S_{a}(B))$ ולוודא את אמינותו של פתק ההצבעה אך אף אחד לא יידע לשייך אותו לבוב כיוון שבוב שלח את הפתק באופן אנונימי. כדי למנוע הצבעה כפולה, חברי ועדת הקלפי צריכים לוודא שפתקי ההצבעה מכילים מרכיב אקראי שאליו מוצמדת ההצבעה כך שכל הצבעה עם $S_{a}(B)$ תהיה שונה. בדרך זו אפשר להבטיח ספירה אמינה של הקולות ולזהות כפילויות. התרשים מצד שמאל ממחיש מערכת הצבעה דיגיטלית טיפוסית.

מטבע דיגיטלי עם חתימה עיוורת

בניגוד לרכישה באמצעות כרטיס אשראי או המחאה בנקאית, המאפיין המרכזי בכסף מזומן הוא שכאשר הלקוח מושך מזומנים מהבנק, הבנק אינו יודע איפה הלקוח מתכוון לבזבז אותם וכן כאשר הלקוח מבצע רכישה, הסוחר אינו יודע מי הוא הקונה. כך הכסף החליף ידיים מבלי שניתן יהיה להתחקות אחר הרוכש. אפשר לדמות מאפיין זה של רכישה במזומן גם בכסף דיגיטלי. לצורך המחשה נניח שאליס מייצרת מטבע דיגיטלי $C$. היא מחשבת את פונקציית הגיבוב של המטבע $f(C)$ ואז מצפינה אותה באמצעות פונקציית ההצפנה שלה $E_{a}$ עם המפתח הסודי $a$. את התוצאה $E_{a}(\ f(C)\ )$ היא שולחת לבנק ומבקשת את אישורו. הבנק מזהה את הלקוחה באמצעי זיהוי רגילים ואז חותם על הגיבוב של המטבע באמצעות פונקציית החתימה שלו $S_{b}$, מחזיר לה את החתימה $S_{b}(\ E_{a}(\ f(C)\ )\ )$ ומנכה את הסכום המתאים מחשבונה. כעת אליס מסירה את ההצפנה שלה מהמטבע על ידי חישוב $D_{a}(\ S_{b}(\ f(C)\ )\ )$ ומתקבל $S_{b}(\ f(C)\ )$, כמו כן היא מוודא שמתקיים $V_{b}(\ S_{b}(\ f(C)\ )\ )=f(C)$ כדי למנוע רמאות מצד גורם שלישי. כעת כדי לבזבז את המטבע היא משלמת עבור סחורה כלשהי עם $C$ ועם $S_{b}(\ f(C)\ )$. הסוחר מוודא שהמטבע אותנטי ואושר על ידי הבנק על ידי בדיקה שמתקיים $V_{b}(\ S_{b}(\ f(C)\ )\ )=f(C)$ כנדרש. פונקציית הגיבוב נחוצה כאן כדי למנוע מאליס מלרמות את הסוחר, כי ללא פונקציית הגיבוב אליס יכולה לבחור ערך אקראי כלשהו $X$ ולמסור לו את ($X,V_{b}(X)$) כמטבע לגיטימי. כעת הסוחר שולח את המטבע $C$ ואת החתימה $S_{b}(\ f(C)\ )$ לבנק שמוודא שהמטבע תקף ואם כן הבנק מזכה את חשבונו של הסוחר בהתאם. כמו כן הבנק צריך לאחסן את $C$ במקום כלשהו כמטבע שבוזבז כך שאליס לא תבזבז אותו שוב.

אפשר להדגים מטבע דיגיטלי עם פונקציית ההצפנה RSA. המטבע $C$ בשווי דולר אחד יהיה מהצורה $C=(x,H(x)^{1/3}{\text{ (mod }}n))$ כאשר $n$ הוא מודולוס RSA של הבנק, $H$ היא פונקציית גיבוב ו-$x$ הוא ערך אקראי שנבחר על ידה. ביתר פירוט, פרוטוקול להנפקה ובזבוז של מטבע אחד מתנהל כדלהלן:

1. אליס מגרילה שני שלמים אקראיים $x$ ו-$r$ ושולחת לבנק את המטבע המוסתר $B=(r^{3}\cdot H(x)){\text{ (mod }}n)$.
2. הבנק מחזיר לה את השורש ממעלה שלישית של $B$ מודולו $n$ שהוא $(r\cdot H(x)^{1/3}){\text{ (mod }}n)$ ומנכה מחשבונה דולר אחד.
3. אליס מחלצת מתוך $B$ את החתימה על המטבע $C$ שהיא $H(x)^{1/3}{\text{ (mod }}n)$.
4. אליס מבזבזת את המטבע, היא שולחת לבוב את הזוג $(x,H(x)^{1/3}{\text{ (mod }}n))$.
5. בוב מתקשר לבנק מייד ומוודא שהמטבע לא בוזבז כבר. אם לא הוא בודק את חתימת הבנק ואת פונקציית הגיבוב.
6. אם הבדיקות הצליחו הוא מקבל את המטבע ומספק את הסחורה או השרות תמורתו לאליס.
7. הבנק מזכה את חשבונו של בוב בדולר אחד ורושם את המטבע כמי שכבר בוזבז, כדי למנוע בזבוז כפול.

דוגמה במספרים קטנים

יהיו $p=353,q=449$ ו-$n=pq=158497$. מפתח האימות הציבורי של חתימת הבנק יהיה $3$ ואילו מפתח החתימה הפרטי הוא $105131$. להכנת המטבע $C$

• אליס בוחרת את $x=330$ ואת $r=502$ מחשבת את $H(330)=37$ (במקרה זה הוגרל מספר כלשהו רק לצורך הדוגמה) ושולחת לבנק את $(25402\cdot 37)\equiv 147389{\text{ (mod }}158497)$.
• הבנק מחזיר את חתימתו $147389^{105131}\equiv 67047{\text{ (mod }}158497)$.
• אליס מפענחת את חתימת הבנק על ידי חילוק ב-$r$ (ליתר דיוק הכפלה בהופכי הכפלי שלו מודולו $n$) ומתקבלת החתימה $(67047\cdot 37572)\equiv 97063{\text{ (mod }}158497)$. המטבע של אליס הוא $x=330$ וחתימת הבנק על המטבע הגלוי היא $97063$.
• את הזוג $C=(330,97063)$ היא שולחת לסוחר בוב.
• הסוחר מצידו תחילה מוודא את תוקף המטבע על ידי בדיקת החתימה של הבנק (העלאה בחזקת 3) קל לראות שבמקרה זה מתקבל $97063^{3}\equiv 37{\text{ (mod }}158497)=H(x)$. כמו כן כדי למנוע רמאות מצד אליס הוא בודק שאכן מתקבל $H(330)=37$. אם שתי הבדיקות עלו בהצלחה הוא מספק את הסחורה או השרות לאליס ומפקיד את המטבע בבנק.

כאשר הבנק חתם על $H(x)=37$ הוא לא ראה אותו כיוון שהיה מוסתר בכפל ב-$r^{3}$ לכן כאשר הסוחר מפקיד את המטבע, הבנק לא יודע שהמטבע התקבל מאליס.

מטבע דיגיטלי עם הוכחה באפס ידיעה

ערך מורחב – הוכחה באפס ידיעה

בשיטה המתוארת לעיל נשמרת האנונימיות של אליס בזמן הרכישה וכן הבנק מסוגל למנוע בזבוז כפול אך החיסרון שלה הוא שהיא לא מענישה את הרמאי במקרה של ניסיון לבצע בזבוז כפול. הדרך היחידה למנוע מאליס מלנסות לבזבז את המטבע שוב היא שהסוחר יוודא מול הבנק את תקפות המטבע בזמן הרכישה און ליין, מצב שלא תמיד אפשרי. לכן הציעו דויד צ'אום, עמוס פיאט ומוני נאור רעיון להשתמש בהוכחה באפס ידיעה כדי לבנות פרוטוקול מטבע דיגיטלי שייחודו הוא בכך שעונשה של אליס במקרה של ניסיון לבצע בזבוז כפול הוא חשיפת זהותה. הפרוטוקול שלהם תאורטי ומסתמך על הרעיון של Cut-and-Choose, שבו שני משתתפים מבטיחים הוגנות על ידי אינטראקציה.

כמו בשיטה המתוארת לעיל הבנק בוחר תחילה מודולוס $n$ ופרמטר ביטחון $k$ שמגדיר את ההסתברות לתפוס מבזבז כפול. $k$ גדול פירושו שקשה יותר לרמות וההסתברות שהרמאי יתגלה מתקרבת ל-1 די מהר ככל ש-$k$ גדל. נניח שמספר החשבון של אליס הוא $u$ עם מונה כלשהו $v$, כך שהבנק ואליס יודעים מהם. נניח שנתונות שתי פונקציות חד-כיווניות חסינות התנגשויות $f$ ו-$g$ שמפיקות פלט באורך קבוע (אפשר להשתמש ב-SHA-2 למשל). המטבע של אליס יהיה אחד מ-$k$ הרביעיות $(a_{i},c_{i},d_{i},r_{i})$ של מספרים שלמים מודולו $n$ שהיא בוחרת באופן אקראי. רביעיות אלה נקראות "מועמדים". כדי להחתים את הבנק על המטבע היא מבצעת כדלהלן:

1. היא מסתירה את $k$ המועמדים באמצעות פונקציית ההצפנה שלה: $B_{i}=E_{r_{i}}(\ f(x_{i},y_{i})\ )$ כאשר $x_{i}=g(a_{i},c_{i})$ וכן $y_{i}=g(\ a_{i}\oplus (u\ \|\ (v+i)\ ),d_{i})$ ושולחת אותם לבנק. הסימן $\oplus$ מייצג XOR והסימן $\|$ מייצג שרשור מחרוזות.
2. הבנק בוחר קבוצת אתגר אקראית $R$ באורך $k/2$ מועמדים מתוך הרשימה שקיבל ושולח אותה לאליס. אליס חושפת בפני הבנק את $(a_{i},c_{i},d_{i},r_{i})$ עבור כל $i\in R$. הבנק בודק עבור כל רביעייה שמתקבל $B_{i}$ כיוון שהוא יודע מהם $u$ ו-$v$. לכן אם אליס מנסה לרמותו הסיכויים שהוא יגלה את הרמאות מאוד גבוהים.
3. לאחר שנחה שדעתו של הבנק והוא משוכנע שאליס אינה רמאית הוא חותם על המטבע הממוסך $S_{b}(\Pi _{i\not \in R}B_{i})$ ומנכה את הסכום המתאים מחשבונה. הרעיון כאן הוא שהבנק צריך להחסיר מהחתימה את כל הערכים שאליס חשפה בשלב ההוכחה, כי הם אינם יכולים יותר לשמש כמטבע לגיטימי. הסימן $\Pi$ היא פעולה כלשהי שהתכונה שלה היא שהיא נשמרת גם לאחר תהליך הפענוח של אליס. במאמר המקורי הפעולה הייתה כפל בגלל שסכמת החתימה הייתה חישוב שורש ממעלה שלישית וההצפנה של אליס הייתה כפל ב-$r_{i}^{3}$. כעת מפעילה אליס את פונקציית הפענוח שלה כדי לחשוף את הערך $C=S_{b}(\Pi _{i\not \in R}f(x_{i},y_{i}))$, בודקת שהתוצאה נכונה על ידי הפעלת פונקציית האימות $V_{b}$ ומקדמת את המונה $v=v+k$.

עבור $\epsilon$ קבוע כלשהו, אם פחות מ-$(1-\epsilon )$ מתוך $k$ המועמדים המוסתרים $B_{i}$ אינו במבנה הנכון $(\ E_{r_{i}}(f(g(a_{i},c_{i}),g(a_{i}\oplus (u\|(v+i)),d_{i})))\ )$ (יש לזכור שהבנק יודע מהו $u\|(v+i)$), אז אליס תיתפס כמי שניסתה לרמות בהסתברות של $1-\exp(-c\epsilon k)$.

כעת בידי אליס מטבע דיגיטלי אותו היא יכולה לבזבז כדלהלן:

1. היא שולחת את $C$ לסוחר.
2. הסוחר שולח לאליס מחרוזת אתגר אקראית בינארית באורך $k/2$ סיביות. אם הסיבית ה-$i$ היא 1 אליס צריכה לשלוח לבוב את $a_{i},c_{i},y_{i}$ ואם הסיבית ה-$i$ היא 0 היא אמורה לשלוח את $x_{i},a_{i}\oplus (u\ \|\ (v+i))$ ואת $d_{i}$. הסוחר בודק שהערכים שקיבל תואמים את הערך של $C$. היות שההנחה היא שהפונקציות $f$ ו-$g$ בלתי הפיכות והחתימה של הבנק נחשבת אמינה, אם אליס מרמה בשלב זה היא תיתפס בהסתברות גבוהה.
3. הסוחר שולח תעתיק של השיחה שלו עם אליס לבנק שמזכה אותו בסכום המתאים ושומר את תעתיק השיחה בקובץ לצורך תיעוד.

האנונימיות של אליס באינטראקציה שלה עם הסוחר נשמרת. המידע המזהה היחידי שהיא מסרה הוא מספר החשבון שלה כשהוא ממוסך עם ערך אקראי $a_{i}$ לכן הסוחר אינו יכול לעשות בו כל שימוש. הערכים $c_{i},d_{i}$ נחוצים כך שגם אם יתגלה שהחד-כיווניות של הפונקציה $g$ חלשה מהצפוי ומישהו הצליח לפצח אותה הוא יישאר עם מספר עצום של זוגות אפשריים $(a_{i},c_{i})$ וכן $(a_{i}\oplus (u\ \|\ (v+i)),d_{i})$ שהפונקציה $g$ ממפה לערכים $x_{i},y_{i}$. כך שגם אם הסוחר מצליח להפוך את $g$ הוא לא יצליח לחלץ מידע מועיל לגבי זהות אליס. אם אליס תנסה לבזבז את המטבע $C$ שוב, יקרה דבר מעניין, הבנק ישווה את תעתיק השיחה מהרכישה החדשה עם התעתיק השמור מהרכישה הקודמת ובגלל שהאתגר אקראי יש סבירות גבוהה שיכול להיות אינדקס $i$ כלשהו כך שסיבית האתגר ה-$i$ הייתה 1 בעותק הראשון ו-0 בעותק השני כי שניהם אקראיים. לכן לא רק שהבנק יודע כעת שנעשה ניסיון לבזבוז כפול, אם הוא יבצע XOR של שני תעתיקי השיחות שבידו הוא יקבל את $u\ \|\ (v+i)$, שבעצם חושף את מספר חשבונה של אליס ואת זהותה.

הבעיה בשיטה זו היא שבעוד שהבנק מסוגל לגלות אם אליס ניסתה להונות אותו, הוא עצמו יכול להמציא תעתיק שיחה בדוי כדי להפליל אותה, לכן מעצם טענה זו הבנק לא יוכל לשכנע אף אחד אחר שאליס אכן רמאית (זוהי תכונה מהותית בהוכחה באפס ידיעה). אפשר לתקן את הבעיה על ידי הוספת חתימה דיגיטלית של אליס כדי להגן עליה מפני רמאות מצד הבנק. כאשר אליס בוחרת את המועמדים היא מגרילה $k$ זוגות נוספים של ערכים $(p_{i},q_{i})$ משרשרת אותם ביחד $g(p_{1},q_{1})\ \|\ \cdots \ \|\ g(p_{k},q_{k})$, חותמת על התוצאה ושולחת הכול לבנק. בנוסף כאשר היא מחשבת את$f(x_{i},y_{i})$ היא מחליפה את $u$ בביטוי $u\ \|\ p_{i}\ \|\ q_{i}$. ואז אם הבנק יכול לספק $k/2+1$ זוגות נכונים $(p_{i},q_{i})$ בידו ההוכחה שאליס ניסתה לרמות. אך התועלת כאן היא שהבנק אינו יכול לשנות את הערכים $g(p_{i},q_{i})$ בגלל החתימה של אליס עליהם. גם אם נניח שהבנק מסוגל לפצח את $g$ כל מה שאליס צריכה לעשות זה לחשוף את הזוג המתאים $(p_{i},q_{i})$ שברשותה כדי להוכיח שנעשה ניסיון לרמותה.

אפשר להרחיב את השיטה להמחאה בנקאית דיגיטלית שאינה ניתנת למעקב או התחקות אחר הרוכש. אליס יכולה לבקש מהבנק "פנקס" המחאות שבכל אחד מהם היא יכולה לבזבז עד הסכום הנקוב בו והבנק ינכה מחשבונה בהתאם את הסכום שבזבזה, אך הבנק לא יידע היכן היא השתמשה בהמחאה או באיזה סכום. השיטה המתוארת עובדת מבחינה תאורטית אך אינה פרקטית בגלל המחיר הכבד שהצדדים צריכים לשלם מבחינה חישובית כדי להגיע לתוצאה המיוחלת. בשיטות חדשות מנסים להגיע לרמת ביטחון דומה ללא הצורך בתקורה הגבוהה של פרוטוקול Cut-and-Choose.

חתימה עיוורת מבוססת DSA

חתימה דיגיטלית DSA וכן חתימה דיגיטלית של שנור מבוססים על הצפנת אל-גמאל שהיא מערכת מפתח ציבורי המבוססת על בעיית הלוגריתם הבדיד. פונקציית החתימה של שנור בגרסה הלא עיוורת פשוטה יותר מ-DSA והיא פועלת באופן כללי כדלהלן: בהינתן המפתח הציבורי $(p,q,g,y)$ כאשר $(p,q,g)$ הם פרמטרים ציבוריים המשותפים לכל המשתמשים. $p$ ו-$q$ הם מספרים ראשוניים מתארים תת-חבורה $\mathbb {Z} _{q}^{*}$ של $\mathbb {Z} _{p}^{*}$ מסדר $q$ עם היוצר $g$ כאשר $q|(p-1)$. המפתח הציבורי הוא $y=g^{-x}{\text{ mod }}p$ ואילו המפתח הפרטי הוא $x$. אם $H$ היא פונקציית גיבוב מוסכמת המפיקה פלט בטווח $[1,q-1]$, אז תהליך החתימה על המסר $m$ מתבצע כך. החותם מגריל שלם אקראי $k$ בטווח $[1,q-1]$ ומחשב את $(r,e,s)$ כדלהלן:

$r=g^{k}{\text{ mod }}p$

$e=H(m\ \|\ r){\text{ mod }}q$

$s=(k+xe){\text{ mod }}q$

הסמל "$\|$" מייצג שרשור. לאימות החתימה באמצעות המפתח הציבורי של החותם בודקים שמתקיים:

$r\equiv (g^{s}\cdot y^{e}){\text{ mod }}p$ או $e=H(m,(g^{s}\cdot y^{e}){\text{ mod }}p)$.

כדי להפוך את החתימה המתוארת לחתימה עיוורת (נניח אליס מעוניינת להחתים את הבנק על המטבע $C$), מבצעים את הפרוטוקול של אוקמוטו המבוסס על שנור כדלהלן:

1. הבנק בוחר את $k$ כמו קודם ומייצר את $r=g^{k}{\text{ mod }}p$ ושולח את $r$ לאליס.
2. אליס מגרילה שלמים אקראיים $a$ ו-$b$ בטווח $[1,q-1]$ ומחשבת את $(r',e',e)$ כדלהלן:
   1. $r'=(r\cdot g^{-a}\cdot y^{-b}){\text{ mod }}p$
   2. $e'=H(C\ \|\ r'){\text{ mod }}q$
   3. $e=(e'+b){\text{ mod }}q$
   4. את הערכים הללו שולחת אליס לבנק.
3. הבנק מחשב את $s=(k+ex){\text{ mod }}q$ ושולח לאליס את $s$.
4. אליס מחשבת את $s'=(s-a){\text{ mod }}q$ והזוג $(e',s')$ הם חתימה תקפה על $C$. כי מתקיים: $e'=H(m,(g^{s'}\cdot y^{e'}){\text{ mod }}p)$

ביטחון

חתימת שנור היא שילוב של פרוטוקול אימות של שנור יחד עם רעיון של עמוס פיאט ועדי שמיר. פונקציית הגיבוב לצורך חתימת שנור לא חייבת להיות חסינת התנגשויות, מחקרים מראים שבניגוד ל-DSA אפשר להסתפק בחתימת שנור בפונקציית גיבוב חלשה כמו SHA-1 וכן אפשר להסתפק בערך גיבוב קצר יותר בכעשרים וחמש אחוז.

הביטחון של חתימת שנור ניתן להוכחה במסגרת מודל אורקל אקראי תחת ההשערה שבעיית הלוגריתם הבדיד קשה. ב-2012 בוצע מחקר באשר לביטחון המדויק של חתימת שנור והטענה היא שלפי למת הפיצול קיים איבוד זמן בפקטור של $O(q_{h})$ כאשר $q_{h}$ הוא מספר השאילתות לאורקל האקראי. במילים אחרות אם קיים זייפן שיכול לזייף חתימת שנור בהסתברות $\epsilon _{F}$ אז אפשר יהיה לחשב את הלוגריתם הבדיד בהסתברות קבועה על ידי חזרה לאחור $O(q_{h}/\epsilon _{F})$ פעמים, תחת הנחות נוספות אפשר להגיע לרדוקציה של $q_{h}^{2/3}$ לכל היותר בשיעור ההצלחה-זמן.

דוגמה במספרים קטנים

• נתון $q=179,p=359,g=164$ וכן המפתח הפרטי של אליס הוא $x=81$ והמפתח הציבורי הוא $y=245$.
• הבנק בוחר שלם אקראי $k=45$ ושולח לאליס את האתגר $r=164^{45}\equiv 120{\text{ (mod }}359)$.
• אליס בוחרת את $a=64,b=120$ ונניח שהמטבע הוא הערך $c=12345678$. היא מחשבת את $120\cdot 164^{-64}\cdot 245^{-120}\equiv 158{\text{ (mod }}359)$. נניח לצורך הפשטות שתוצאת הגיבוב היא $H(c\ \|\ 158)=54{\text{ (mod }}179)$.
• הבנק מחזיר לאליס את $s=(45+174\cdot 81){\text{ mod }}179=177$ כך שמתקיים $120\equiv (174^{177}\cdot 245^{174}){\text{ (mod }}359)$
• אליס מחלצת את חתימת הבנק על המטבע כך: תחילה $s'=177-64=113$ ואז הצמד $(113,54)$ הוא חתימה תקפה על $c$ כי מתקיים $H(c\ \|\ ((164^{113}\cdot 245^{54})=64{\text{ mod }}359))=54$

שיטות חדשות

קיימות מספר שיטות חתימה עיוורת חדשות יעילות ובטוחות יותר, בהן אפשר לציין את Camenisch-Lysyanskaya שייחודה בכך שניתן לחלץ חתימה על קבוצה של מסרים בבת אחת, ולהוכיח תקפות על כל אחד מהם בנפרד. הרעיון שימושי גם למטבע דיגיטלי תוך שמירה על אנונימיות המשתמש. כמו כן קיימת שיטת חתימה עיוורת המסתמכת על תחום חדש בקריפטוגרפיה הקרוי מיפוי ביליניארי. בנוסף קיימת מחלקה של חתימה עיוורת שכאמור מענישה את הלקוח שמנסה לבזבז פעמיים בחשיפת זהותו. שיטה אחת כזו היא חתימה עיוורת של סטפן ברנדס שהוטמעה בטכנולוגיית אימות חדשה מבית מיקרוסופט הנקראת U-Prove. הרעיון של ברנד בעצם לוקח את החיסרון הידוע של חתימת DSA שבה אסור להשתמש במפתח הארעי יותר מפעם אחת לחתימה על שני מסמכים שונים והופך אותו ליתרון, בזה שהוא משתמש בו כדי לחשוף את זהות המשתמש במקרה של בזבוז כפול.

פרוטוקול מטבע דיגיטלי עם חתימה עיוורת של ברנדס

פרוטוקול הכנה

הבנק ${\mathcal {B}}$ בוחר באקראי שלושה יוצרים $(g,g_{1},g_{2})$ של החבורה $G_{q}$ מסדר $q$ ראשוני, שלם אקראי $x\in \mathbb {Z} _{q}^{*}$ וכן שתי פונקציות גיבוב $H,H_{0}$ כאשר $H$ משמשת ליצירה ואימות חתימת הבנק ואילו $H_{0}$ משמשת לצורך האתגר בפרוטוקול התשלום. הערכים הציבוריים המשותפים לכל הלקוחות הם $G_{q}$ וכן הראשוניים $p$ ו-$q$ כאשר $G_{q}$ היא תת-קבוצה של $\mathbb {Z} _{p}^{*}$ וכן היוצרים ופונקציות הגיבוב. המפתח הסודי של הבנק הוא $x$. כרגיל ההנחה היא שהבנק מנהל מסד נתונים המכיל פרטים מזהים של כל הלקוחות וכל הסוחרים ובנפרד מסד נתונים המכיל מעקב אחרי כל המשיכות וההפקדות. מטבע דיגיטלי יכיל זוג הערכים $(A,B)\in G_{q}\times G_{q}$ שבהמשך יוסבר איך מחשבים אותם והחתימה של הבנק עליהם ${\text{sign}}(A,B)=(z,a,b,r)$ כך שמתקיים

$g^{r}=h^{H(A,B,z,a,b)}a$, וכן $A^{r}=z^{H(A,B,z,a,b)}b$.

ההוכחה שהמטבע שייך ללקוח היא אם הוא יכול להוכיח שידוע לו הייצוג הלוגריתמי של $A$ ו-$B$ ביחס ליוצרים $g_{1}$ ו-$g_{2}$. בתהליך פתיחת חשבון הלקוח מזהה עצמו מול הבנק באמצעי זיהוי רגילים, מייצר ערך אקראי $u_{1}$ ומחשב את $I=g_{1}^{u_{1}}$ אם $g_{1}^{u_{1}}\cdot g_{2}\neq 1$ הוא משדר את $I$ לבנק ושומר בסוד את $u_{1}$. הבנק מחשב ומחזיר ללקוח את $z=(I\cdot g_{2})^{x}$.

פרוטוקול משיכה

המשיכה מתבצעת בשלושה מהלכים, לאחר שהלקוח זיהה עצמו מול הבנק בדרכים רגילות:

1. הבנק מגריל ערך אקראי $w$ ושולח ללקוח את $a=g^{w}$ ואת $b=(I\cdot g_{2})^{w}$.
2. הלקוח מייצר מטבע; בוחר שלושה ערכים אקראיים $(s,x_{1},x_{2})$ ומחשב את $A=(I\cdot g_{2})^{s}$, את $B=g_{1}^{x_{1}}g_{2}^{x_{2}}$ וכן $z'=z^{s}$. כמו כן בוחר שני ערכים אקראיים נוספים $u,v$ ומחשב את $a'=a^{u}g^{v}$ וכן $b'=b^{su}A^{v}$ ואז מחשב את האתגר $c'=H(A,B,z'a',b')$ ושולח לבנק את $c=c'/u$ מודולו $q$.
3. הבנק מחזיר ללקוח תגובה המכילה את $r=cx+w$ מודולו $q$ ומחייב את חשבון הלקוח בהתאם.

הלקוח ${\mathcal {U}}$ מקבל את חתימת הבנק רק אם מתקיים $g^{r}=h^{c}a$ וכן $(I\cdot g_{2})^{r}=z^{c}b$. אם כן הוא מחשב את $r'=ru+v$ מודולו $q$. בפרוטוקול זה מספר המטבעות לעולם לא יעבור את מספר המשיכות לכן הלקוח לא יכול לייצר לעצמו מטבעות במיוחד לאור העובדה שכדי להצליח בכך הוא חייב לדעת את הייצוג של המטבע ביחס ליוצרים שזו בעיה קשה הנגזרת מבעיית הלוגריתם הבדיד. וההוכחה דומה להוכחה של פרוטוקול האימות של שנור. תכונה מעניינת נוספת היא שהפרוטוקול נחשב לחתימה עיוורת חלקית כי הלקוח יכול להסתיר את המעטפת החיצונית של המטבע אבל לא את המבנה הפנימי שלו.

פרוטוקול בזבוז

כאשר ${\mathcal {U}}$ רוצה לבזבז את המטבע אצל ${\mathcal {S}}$ הוא מבצע כדלהלן:

1. שולח לסוחר את המטבע $\langle (A,B),{\text{sign}}(A,B)\rangle$.
2. הסוחר מחשב את $d=H_{0}(A\ \|\ B\ \|\ ID)$ כאשר $ID$ מכיל פרטים מזהים של הסוחר כמו גם תאריך העסקה.
3. הלקוח מחשב ושולח ל-${\mathcal {S}}$ את המענה $r_{1}=d(u_{1}s)+x_{1}$ ואת $r_{2}=ds+x_{2}$ (מודולו $q$).

הסוחר מקבל את המטבע כלגיטימי רק אם שני הדברים הבאים מתקיימים: החתימה של הבנק תקפה וכן שמתקיים $g_{1}^{r_{1}}g_{2}^{r_{2}}=A^{d}B$. אם הלקוח יודע את פרטי הסוחר מראש אפשר לצמצם את פרוטוקול התשלום למהלך אחד שכן הוא יכול לחשב את $d$ לבדו. ברור שנכונות $d$ חשובה לסוחר ולא ללקוח כי תקפותו תקבע אם הבנק יכבד את העסקה ויזכה את הסוחר בהתאם.

פרוטוקול הפקדה

הסוחר יכול לאחר מכן לשלוח לבנק את תעתיק העסקה הכולל את $A,B,{\text{sign}}(A,B),(r_{1},r_{2})$ וכן התאריך הכלול בה. הבנק לא יכבד את העסקה אם $A=1$, אחרת הוא מחשב את $d$ בעזרת זהותו של הסוחר הרשומה במסד הנתונים של הבנק ותעתיק העסקה. ומוודא שמתקיים $g_{1}^{r_{1}}g_{2}^{r_{2}}=A^{d}B$ וכן שהחתימה שלו על המטבע תקפה ואם הבדיקות עלו בהצלחה הוא מפקיד את המטבע בחשבונו של הסוחר. אם המטבע כבר רשומה במאגרי הבנק משמע אחד מהשניים או ש-${\mathcal {S}}$ מנסה להפקיד את אותה מטבע פעמיים או שנעשה ניסיון לבזבוז כפול מצד ${\mathcal {U}}$. קל לזהות את המקרה שהסוחר מנסה להפקיד את אותה מטבע פעמיים כי תעתיק העסקה זהה לחלוטין. במקרה שתעתיק העסקה שונה הבנק יכול לחשוף את זהות ${\mathcal {U}}$ כי בידיו כעת $(d,r_{1},r_{2})$ מהעסקה החדשה וכן $(d',r_{1}',r_{2}')$ מעסקה קודמת. הוא יכול לחשב את $g_{1}^{(r_{1}-r_{1}')/(r_{2}-r_{2}')}$. התוצאה היא למעשה מספר החשבון של הלקוח שניסה לבזבז את המטבע פעמיים והוא מהווה הוכחה לכך.