אפשר להכין חתימה עיוורת באמצעות כל שיטת הצפנה אסימטרית הומומורפית חלקית כמו RSA, אל-גמאל, הצפנת פליאיי או אוקמוטו-אושיאמה. באופן פורמלי חתימה עיוורת היא פרוטוקול קריפטוגרפי בין שתי ישויות אליס ובוב. אליס מעוניינת להחתים את בוב על מסר כלשהו שהיא הכינה. בגמר הפרוטוקול אליס השיגה את חתימתו של בוב על המסר מבלי שיגלה דבר בנוגע למסר עליו חתם. וכן כל אחד מסוגל לוודא שאכן החתימה של בוב על המסר תקפה מבלי הצורך לדעת מיהו בעל המסר. במידה מסוימת יש קשר בין פרוטוקול זה לפרוטוקול הוכחה באפס ידיעה, שבו המוכיח מצליח לשכנע את המוודא בדבר אמיתות טענה מסוימת מבלי לחשוף בפניו את הטענה עצמה. למעשה דויד צ'אום, עמוס פיאט ומוני נאור פיתחו פרוטוקול למטבע דיגיטלי המסתמך על אפס ידיעה שמאפשר לאליס לשמור על האנונימיות שלה כל עוד היא אינה מרמה. העונש במקרה של הונאה הוא חשיפת זהותה.
מבוא.
חתימה דיגיטלית היא תוצר של הצפנת מפתח ציבורי או הצפנה א-סימטרית שבה המערכת מפוצלת לשני חלקים נפרדים, שלב ההצפנה המקביל לשלב החתימה ושלב הפענוח המקביל לשלב אימות החתימה. כל אחד יכול לאמת חתימה המצורפת למסמך כלשהו באמצעות המפתח הציבורי של החותם אך רק החותם שמחזיק במפתח הפרטי יכול לחתום חתימה תקפה בשמו ובהגדרה אין אפשרות (או קשה מאוד) לנחש מהו מפתח החתימה הפרטי בידיעת מפתח האימות הציבורי. חתימה דיגיטלית כוללת פונקציית חתימה formula_1 ופונקציית אימות formula_2 כך שהתוצאה של formula_3 על המסר formula_4 היא הוכחה לתקפותה. השיטה המפורסמת ביותר לחתימה דיגיטלית היא שיטת RSA המבוססת על העובדה שמצד אחד קל לבצע העלאה בחזקה ומצד שני קשה לפרק לגורמים מספרים שלמים. אליס בוחרת שני מספרים ראשוניים גדולים formula_5 ו-formula_6 ומחשבת את formula_7. כמו כן היא מגרילה מספר שלם formula_8 שהוא זר ל-formula_9, מחשבת את המפתח הסודי formula_10 כך שמתקיים formula_11. כאשר formula_9 הוא פונקציית אוילר של formula_13 שהיא במקרה זה formula_14. את formula_8 ואת formula_13 היא מפרסמת לכל דורש ואילו את formula_10 ואת formula_5 ו-formula_6 היא שומרת בסוד. כדי לחתום על המסר formula_4 היא מחשבת את formula_21 אותו היא שולחת לבוב יחד עם המסר formula_4. כדי לאמת את החתימה בוב מחשב את formula_23 ורק אם מתקיים formula_24 הוא מקבל את החתימה. זה נכון בשל הזהות הבאה:
כי לפי אויילר formula_26 עבור כל formula_4 ולכן גם formula_28. היות שאף אחד חוץ מאליס אינו יודע מהם formula_10 או formula_9 כיוון שהם מעולם לא פורסמו ולא ניתן לחשב אותם מתוך formula_8 ו-formula_13 מבלי לדעת מהם הגורמים הראשוניים, זהו מאפיין יסודי של הצפנה אסימטרית, לכן בוב יכול לקבל את החתימה כאותנטית. כמובן שהשיטה המתוארת נועדה רק להדגים את הקונספט של חתימה דיגיטלית, אין לראות בה בשום אופן שיטה מעשית לחתימה דיגיטלית. בפועל מיישמים חתימה דיגיטלית באופן אחר לגמרי כדי למנוע התקפות קריפטוגרפיות ידועות. אפשר לבסס חתימה דיגיטלית על מערכות הצפנת מפתח ציבורי אחרות כמו חתימה דיגיטלית של רבין המבוססת על הצפנת רבין או DSA המבוססת על הצפנת אל-גמאל.
אפשר להרחיב כמעט כל פרוטוקול חתימה דיגיטלית לחתימה דיגיטלית עיוורת. הטכניקה הראשונה שפורסמה הייתה של דויד צ'אום, שהתאים את חתימת RSA ב-1992 פרסם אוקמוטו גרסת חתימה עיוורת המבוססת על חתימת שנור.
הצבעה דיגיטלית עם חתימה עיוורת.
מאפיין רצוי בהצבעה דיגיטלית הוא שאימות זהות המצביע יהיה מופרד מאימות ההצבעה עצמה. חתימה דיגיטלית רגילה יוצרת זיקה בין המצביע לפתק ההצבעה ולכן אנונימיות המצביע נפגעת. מצד שני בהצבעה מקוונת גובר הסיכון להצבעה כפולה או התחזות והונאה. פרוטוקול הצבעה אנונימי מפריד בין תהליך אימות המצביע לבין תהליך אימות ההצבעה באופן כזה שהגורם המאשר את זהות המצביע אינו מסוגל לשייך או ליצור זיקה בינו לבין פתק ההצבעה שלו ומצד שני המצביע אינו יכול להצביע פעמיים או להתחזות למצביע אחר. באופן כללי פרוטוקול הצבעה עם חתימה עיוורת מכיל את המאפיינים הבאים. נניח שהמצביע הוא בוב והגורם הרשמי המאשר את ההצבעה היא אליס.
אם מתרגמים את המושגים הללו לשפה קריפטוגרפית אז שלוש הדרישות הראשונות מקבילות לתהליך אימות קריפטוגרפי עם חתימה דיגיטלית קונבנציונלית. חתימת אליס היא formula_33 ופונקציית האימות הציבורית שלה היא formula_34 כך שמתקיים formula_35. שתי הדרישות האחרונות אומרות שהבוחר בוב צריך להצפין את פתק ההצבעה שלו באמצעות פונקציית הצפנה כזו כך שפתק ההצבעה ניתן יהיה לאימות גם במצבו הגלוי (לאחר פענוח). לשם המחשה נניח שפתק ההצבעה של בוב מסומן באות formula_36, פונקציית ההצפנה שלו היא formula_37 ופונקציית הפענוח שלו היא formula_38 אז צריך שיתקיים formula_39. אפקטיבית, פעולת הפענוח של בוב מסירה את ההצפנה שלו על הפתק מבלי לפגוע בתקפות החתימה. קיימות מספר פונקציות הצפנה שמקיימות את הדרישה האמורה, אפשר למשל להשתמש ב-RSA אך יש להזהר ממלכודות, בדרך כלל משתמשים בהצפנת פליאיי. תהליך ההצבעה יבוצע כדלהן:
היות שפונקציית האימות של אליס ציבורית כל אחד יכול לחשב את formula_46 ולוודא את אמינותו של פתק ההצבעה אך אף אחד לא יידע לשייך אותו לבוב כיוון שבוב שלח את הפתק באופן אנונימי. כדי למנוע הצבעה כפולה, חברי ועדת הקלפי צריכים לוודא שפתקי ההצבעה מכילים מרכיב אקראי שאליו מוצמדת ההצבעה כך שכל הצבעה עם formula_45 תהיה שונה. בדרך זו אפשר להבטיח ספירה אמינה של הקולות ולזהות כפילויות. התרשים מצד שמאל ממחיש מערכת הצבעה דיגיטלית טיפוסית.
מטבע דיגיטלי עם חתימה עיוורת.
בניגוד לרכישה באמצעות כרטיס אשראי או המחאה בנקאית, המאפיין המרכזי בכסף מזומן הוא שכאשר הלקוח מושך מזומנים מהבנק, הבנק אינו יודע איפה הלקוח מתכוון לבזבז אותם וכן כאשר הלקוח מבצע רכישה, הסוחר אינו יודע מי הוא הקונה. כך הכסף החליף ידיים מבלי שניתן יהיה להתחקות אחר הרוכש. אפשר לדמות מאפיין זה של רכישה במזומן גם בכסף דיגיטלי. לצורך המחשה נניח שאליס מייצרת מטבע דיגיטלי formula_48. היא מחשבת את פונקציית הגיבוב של המטבע formula_49 ואז מצפינה אותה באמצעות פונקציית ההצפנה שלה formula_50 עם המפתח הסודי formula_51. את התוצאה formula_52 היא שולחת לבנק ומבקשת את אישורו. הבנק מזהה את הלקוחה באמצעי זיהוי רגילים ואז חותם על הגיבוב של המטבע באמצעות פונקציית החתימה שלו formula_53, מחזיר לה את החתימה formula_54 ומנכה את הסכום המתאים מחשבונה. כעת אליס מסירה את ההצפנה שלה מהמטבע על ידי חישוב formula_55 ומתקבל formula_56, כמו כן היא מוודא שמתקיים formula_57 כדי למנוע רמאות מצד גורם שלישי. כעת כדי לבזבז את המטבע היא משלמת עבור סחורה כלשהי עם formula_48 ועם formula_56. הסוחר מוודא שהמטבע אותנטי ואושר על ידי הבנק על ידי בדיקה שמתקיים formula_57 כנדרש. פונקציית הגיבוב נחוצה כאן כדי למנוע מאליס מלרמות את הסוחר, כי ללא פונקציית הגיבוב אליס יכולה לבחור ערך אקראי כלשהו formula_61 ולמסור לו את (formula_62) כמטבע לגיטימי. כעת הסוחר שולח את המטבע formula_48 ואת החתימה formula_56 לבנק שמוודא שהמטבע תקף ואם כן הבנק מזכה את חשבונו של הסוחר בהתאם. כמו כן הבנק צריך לאחסן את formula_48 במקום כלשהו כמטבע שבוזבז כך שאליס לא תבזבז אותו שוב.
אפשר להדגים מטבע דיגיטלי עם פונקציית ההצפנה RSA. המטבע formula_48 בשווי דולר אחד יהיה מהצורה formula_67 כאשר formula_13 הוא מודולוס RSA של הבנק, formula_69 היא פונקציית גיבוב ו-formula_70 הוא ערך אקראי שנבחר על ידה. ביתר פירוט, פרוטוקול להנפקה ובזבוז של מטבע אחד מתנהל כלדהלן:
דוגמה במספרים קטנים.
יהיו formula_81 ו-formula_82. מפתח האימות הציבורי של חתימת הבנק יהיה formula_83 ואילו מפתח החתימה הפרטי הוא formula_84. להכנת המטבע formula_48
כאשר הבנק חתם על formula_99 הוא לא ראה אותו כיוון שהיה מוסתר בכפל ב-formula_100 לכן כאשר הסוחר מפקיד את המטבע, הבנק לא יודע שהמטבע התקבל מאליס.
מטבע דיגיטלי עם הוכחה באפס ידיעה.
בשיטה המתוארת לעיל נשמרת האנונימיות של אליס בזמן הרכישה וכן הבנק מסוגל למנוע בזבוז כפול אך החסרון שלה הוא שהיא לא מענישה את הרמאי במקרה של ניסיון לבצע בזבוז כפול. הדרך היחידה למנוע מאליס מלנסות לבזבז את המטבע שוב היא שהסוחר יוודא מול הבנק את תקפות המטבע בזמן הרכישה און ליין, מצב שלא תמיד אפשרי. לכן הציעו דויד צ'אום, עמוס פיאט ומוני נאור רעיון להשתמש בהוכחה באפס ידיעה כדי לבנות פרוטוקול מטבע דיגיטלי שייחודו הוא בכך שעונשה של אליס במקרה של ניסיון לבצע בזבוז כפול הוא חשיפת זהותה. הפרוטוקול שלהם תאורטי ומסתמך על הרעיון של Cut-and-Choose, שבו שני משתתפים מבטיחים הוגנות על ידי אינטראקציה.
כמו בשיטה המתוארת לעיל הבנק בוחר תחילה מודולוס formula_13 ופרמטר ביטחון formula_102 שמגדיר את ההסתברות לתפוס מבזבז כפול. formula_102 גדול פירושו שקשה יותר לרמות וההסתברות שהרמאי יתגלה מתקרבת ל-1 די מהר ככל ש-formula_102 גדל. נניח שמספר החשבון של אליס הוא formula_105 עם מונה כלשהו formula_106, כך שהבנק ואליס יודעים מהם. נניח שנתונות שתי פונקציות חד-כיווניות חסינות התנגשויות formula_107 ו-formula_108 שמפיקות פלט באורך קבוע (אפשר להשתמש ב-SHA-2 למשל). המטבע של אליס יהיה אחד מ-formula_102 הרביעיות formula_110 של מספרים שלמים מודולו formula_13 שהיא בוחרת באופן אקראי. רביעיות אלה נקראות "מועמדים". כדי להחתים את הבנק על המטבע היא מבצעת כדלהלן: