הוכחות אפס-ידע שהוסברו: חלק 1

הוכחות אפס-ידע שהוסברו חלק 2: הוכחות לא-אינטראקטיביות שאינן אינטראקטיביות

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

לעתים קרובות משתמשים בהאש, קידוד אסימטרי והצפנה סימטרית יחד כדי לאפשר תקשורת מאובטחת. במערכות קריפטוגרפיות פופולריות, כמו PGP, OTR ו- VPN, לרוב משתמשים באלגוריתמים שונים יחד, כולל:

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

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

הוכחות של אפס-ידע הן עדיין חדשות יחסית ומצאו רק מקרה נפוץ לשימוש לאחרונה ב- cryptocururrency.

הוכחות אינטראקטיביות עם אפס-ידע

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

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

למרות שזה טוב לפרטיות נוספת, זה יכול להגיע גם עם מאמץ נוסף ועלות רבה כשמנסים להוכיח משהו למספר אנשים.

איך עובדות הוכחות עם אפס

המצב:

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

הטענה:

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

ההוכחה:

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

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

אם תחזור על הניסוי, הפתגם (אם הם רק מנחשים) טועה עם סיכוי 75% מצטבר..

לאחר שחזרו על הבדיקה 10 פעמים, אם התוכנית נכונה בכל פעם, יש כבר סיכוי של 99.9% שהם לא שיערו, וסביר להניח שיש להם דרך להבדיל בין שתי המשקפיים. לאחר חזרה על המבחן n פעמים:

1 – 0.5 ^ n * 100%

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

מדוע הוכחות בעלות אפס עובדות

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

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