בשנת 2019 הגישה תביעה בסך 300 אלף ש"ח נגד חברת "טוויטר", על שזו סירבה להסיר ציוץ פוגעני כלפיה.
יהדות עירק
צויקה
צויקה (ברומנית: Ţuica) הוא משקה אלכוהולי רומני מסורתי המופק מתסיסה כוהלית של שזיפים, שלמים או מרוסקים.
הצויקה מיוצרת על ידי התססה של שזיפים בתוך סיר גדול וזיקוק המשקה, עד לחוזק של בין 30% ל-40% אלכוהול.
למשקה כינויים שונים, כתלות באופן ייצורו:
הוכחה באפס ידיעה
במדעי המחשב ובקריפטוגרפיה, הוכחה באפס ידיעה או פרוטוקול אפס ידיעה, היא מערכת הוכחה אינטראקטיבית, שבה צד אחד (מוכיח או טוען) משכנע את הצד השני (מוודא) באמיתות טענה, בסבירות מכרעת (לא באופן מוחלט), מבלי לחשוף כל מידע בנוגע לטענה עצמה, שאי-אפשר היה להשיגו באמצעים אחרים (פרט לעצם נכונותה של הטענה). מעבר לחשיבות התאורטית, להוכחה באפס ידיעה השלכות מעשיות בקריפטוגרפיה – למשל, הטענה יכולה להיות מידע סודי (כמו סיסמה), וההוכחה במקרה זה היא הוכחת ידיעת הסיסמה, המאפשרת לצד אחד לזהות עצמו מול הצד השני (אימות), ללא צורך לחשוף את הסיסמה עצמה.
הוכחת אפס ידיעה חייבת לקיים את התכונות הבאות:
שתי התכונות הראשונות מאפיינות כל מערכת הוכחה אינטראקטיבית. מערכת כזו נקראת הוכחת ידיעה. התכונה השלישית מייחדת מערכת הוכחה באפס ידיעה. היא אינה הוכחה במובן המתמטי של המילה, משום שקיימת סבירות נמוכה במקרה של כשל נאותות, שמוכיח רמאי יהיה מסוגל לשכנע מוודא הגון בנכונות טענה שקרית. למעשה, זוהי הוכחה הסתברותית ולא דטרמיניסטית, אולם ניתן לצמצם את אפשרות השגיאה לכדי הסתברות שולית.
ישנן שלוש רמות של הוכחות אפס ידיעה: מושלמת, סטטיסטית ו-חישובית. הראשונה משמעה שלא עובר שום מידע למעט ידיעת אמיתות הטענה. השנייה משמעה שניתן לייצר בקלות תמלילים מדומים של הפרוטוקול, בהתפלגות שלה מרחק סטטיסטי קטן מזו של תמלילים אמיתיים. האחרונה אומרת כי צד-שלישי, המוגבל ליכולת חישוב פולינומית בזמן ובמקום, לא יוכל לזהות הבדל כלשהו בין תמליל של פרוטוקול אמיתי לבין תמליל מזויף. לכן, מעשית לא ניתן יהיה לחלץ כל מידע אודות טענתו של המוכיח. ההגדרה הראשונה היא החזקה ביותר; ההגדרה השנייה מעט חלשה יותר, וניתן להוכיח עליה טענות בקלות רבה יותר; תחת הגדרה זו ניתן להוכיח קיום של בעיות שלמות וקיום של פרוטוקולים קצרים מאוד. ההגדרה האחרונה, החלשה ביותר, היא על פי רוב זו הנדרשת לצרכים מעשיים.
היסטוריה.
רעיון אפס ידיעה נהגה לראשונה ב-1985 על ידי שפי גולדווסר (המכון הטכנולוגי של מסצ'וסטס, מכון ויצמן למדע), סילביו מיקאלי (המכון הטכנולוגי של מסצ'וסטס), וצ'ארלס ראקוף (אוניברסיטת טורונטו). הם תיארו במאמר "The knowledge complexity of interactive proof-systems" את הרעיון של הוכחת טענה מתמטית באופן אינטראקטיבי (interactive proof-system) ואת הרעיון שניתן לבצע הוכחה כזו ללא חשיפת מידע נוסף (Zero-knowledge proof). הם טבעו את המונח סיבוכיות ידיעה, והציעו מספר מדדים לכמות המידע העובר בהוכחה אינטראקטיבית. הם אף הביאו דוגמה מעשית ראשונה של הוכחת אפס ידיעה: שמספר שלם אינו שארית ריבועית מודולו formula_1, תוך חשיפת אפס מידע בנוגע למספר עצמו, בהתבסס על העובדה שלא קיים אלגוריתם יעיל לבדיקת שארית ריבועית, אם לא נתונים הגורמים הראשוניים של formula_1. על תרומתם זו זכו בפרס גדל.
עודד גולדרייך (מכון ויצמן), סילביו מיקאלי ואבי ויגדרזון (האוניברסיטה העברית בירושלים) הראו, שבהנחה שקיימת פונקציה חד-כיוונית, ניתן לבסס מערכת הוכחה אינטראקטיבית על בעיה NP-שלמה, כמו בעיית הצביעה בגרפים (ראה להלן). היות שכל בעיה במחלקת הסיבוכיות NP ניתנת לצמצום לבעיה זו, הרי שלכל בעיית NP קיימת הוכחת אפס ידיעה, תחת הנחה זו. באופן כללי, הראו גולדרייך וגולדווסר, שכל דבר שניתן להוכחה באופן אינטראקטיבי, ניתן להוכחה באמצעות הוכחת אפס ידיעה; ולמעשה, כל בעיית NP-שלמה ניתנת לשימוש כבסיס למערכת הוכחה באפס ידיעה, כמו גם בעיות קשות אחרות, כמו בעיית הפירוק לגורמים של מספר שלם.
דוגמאות.
צביעות גרף.
דוגמה אחת היא ההוכחה שגרף כלשהו הוא 3-צביע – כלומר, שניתן באמצעות שלושה צבעים לצבוע את כל קודקודיו בצורה כזו, שבה כל שני קודקודים שמחוברים בקשת יהיו צבועים בצבעים שונים. לדוגמה זו חשיבות, הן בשל האינטואיטיביות היחסית שלה, והן מכיוון שבעיית ה-3-צביעה של גרף היא בעיה NP שלמה, ולכן נובע מכך, שלכל בעיה ששייכת למחלקת הסיבוכיות NP קיימת הוכחה באפס ידיעה.
אופן ההוכחה הוא כדלהלן: בהינתן גרף שהוא 3-צביע, ה"סוד" של המוכיח הוא צביעה אפשרית של הגרף. מציאה של צביעה כזו באופן כללי היא בעיה קשה, ולכן ניתן להניח, שהמוודא אינו יכול לגלות צביעה שכזו בעצמו.
בכל סבב של הפרוטוקול המוכיח מגריל תמורה שונה על צבעי הגרף, ומשנה את הצביעה שלו בהתאם. ואז הוא "מכסה" את כל צומתי הגרף ושולח אותו למוודא. המוודא בוחר שני צמתים שמחוברים בקשת ושולח אותם למוכיח, והמוכיח חושף את שני הצמתים הללו (ואותם בלבד). המוודא בודק, שאכן שני הצמתים צבועים בצבע שונה; אם לא – ההוכחה נדחית. על תהליך זה חוזרים כמספר הפעמים הרצוי, עד שהמוודא משתכנע.
החלק הקשה בהוכחה הוא שלב ה"כיסוי". המוכיח צריך "להתחייב" מראש על הצביעה של הגרף כולו, ועם זאת, לא לחשוף דבר. קיימות סכימות התחייבות שמאפשרות לבצע זאת. הסיבה שפרוטוקול זה הוא בעל תכונת אפס ידיעה, נעוצה בכך שהמידע היחיד אותו מקבל המוודא בכל סבב הוא ששני הצמתים שבחר מהגרף אכן צבועים בצבע שונה, כפי שנדרש מהצביעה. אולם, כיוון שבכל סבב מוגרלת תמורה שונה על הצבעים, אין כל תועלת במידע מסבבים קודמים כדי לקבל מושג לגבי צביעת הגרף כולו. להמחשה, אם בסבב הראשון ביקש המוודא את צמתים A,B וראה שהם צבועים בכחול ואדום ובסבב השני ביקש את הצמתים A,C וראה שוב שהם צבועים בכחול ואדום, אין זה אומר ש-B ו-C צבועים בצביעה המקורית באותו הצבע.
עלי באבא והמערה המסתורית.
במאמר "איך להסביר לילדך את פרוטוקול אפס-ידיעה" המחישו המתמטיקאים לואי גילו וז'אן-ז'אק קוויזקווטר באופן ציורי את הרעיון של הוכחה באפס ידיעה, בעזרת הסיפור "עלי-באבא והמערה המסתורית". המערה (ראה תרשים) מכילה כניסה אחת, המתפצלת לשני מבואות, אחד לימין ואחד לשמאל, שבסופם מבוי סתום. הדרך היחידה לעבור מבוי סתום זה היא אמירת מילת קסם סודית, שגורמת לפתיחת דלת סתרים, המקשרת בין המעברים. מילת הקסם ידועה לראובן. השאלה היא: כיצד יוכל לשכנע את שמעון שהוא יודע את מילת-הקסם לפתיחת הדלת המסתורית, מבלי שייאלץ לחשוף אותה בפניו? שאלה זו מקבילה לשאלה "איך ניתן ליצור הוכחה באפס ידיעה". הפתרון הוא ששמעון ימתין בפתח המערה כאשר ראובן נכנס לתוכה, לאחר מכן יתייצב בהתפצלות המבואות ואז יכריז בקול "ימין" או "שמאל" באופן אקראי ועל ראובן לצאת מהמבוא המתאים בהתאם להכרזה. אם ראובן הצליח לצאת בדרך הנכונה, משמע שהוא יודע את מילת הקסם, כי הרי ראובן אינו יודע מראש מה תהיה הכרזתו של שמעון. לצורך המשל, נניח ששמעון אינו יכול ללוות את ראובן עד נקודת ההתפצלות כדי לוודא במו עיניו שהוא נכנס בדרך אחת ויוצא בשנייה, אלא עליו להמתין מחוץ למערה בזמן שראובן נכנס.
בניסוי בודד, סיכוייו של ראובן לרמות הם 50%. היות ששמעון לא ראה באיזה מבוא בחר ראובן, ייתכן מצב, שראובן אינו מכיר כל מילת קסם, אלא פשוט במקרה נכנס בדיוק בדרך בה התבקש לצאת. מאידך, אם שמעון הכריז "ימין" וראובן בחר בשמאל, הוא ייכשל אם הוא רמאי. חישוב פשוט מראה, שאם חוזרים על הניסוי מספר גדול של פעמים, סיכוייו של ראובן לרמות קטנים כל-כך, עד ששמעון יכול להיות משוכנע מעל לכל ספק סביר, שראובן דובר אמת והוא אכן יודע את מילת הקסם.
יתרה מזו, גם אם שמעון יסריט את כל המבחנים שעשה עם ראובן, הוא לא יוכל לשכנע אחרים באמיתות הטענה או אפילו בטענה שהוא עצמו מכיר את מילת הקסם. התבוננות בסרט בלבד אינה מניבה דבר, כיוון שתמיד קיים חשש שראובן ושמעון ביימו אותו (כגון, אם החליטו על סדר ההכרזות של שמעון מראש) או ששמעון השמיט מהסרט את המקרים בהם ראובן נכשל. זוהי תכונה יסודית של פרוטוקול אפס ידיעה – לא ניתן לעשות שימוש חוזר בהוכחה שניתנה בעבר, מאחר שהוכחת אפס ידיעה היא אינטראקטיבית במהותה; כלומר, כדי שישתכנע באמיתות הטענה, המוודא חייב לדעת, שהמבחן בוצע ביושר (דהיינו באופן אקראי, כגון הטלת מטבע) ואת זה הוא יכול לוודא רק אם הוא מבצע את הבדיקות בעצמו.
דוגמה נוספת היא המשחק "איפה אפי?", כאשר אחד מהשחקנים מספר לשאר שהוא מצא את אפי, אבל לא רוצה לגלות להם את מיקומו בתמונה. הפתרון הוא שהשחקן לוקח בריסטול גדול (יותר גדול מהספר), גוזר חור בגודל ראשו של אפי, ומניח את הבריסטול על הספר כך שראשו של אפי מציץ ממנו. לשאר המשתתפים אין יכולת לדעת איפה הספר ממוקם ביחס לבריסטול ולכן אין להם יכולת לקבל מידע בנוגע לפתרון, מעבר לכך שהמוכיח מצא את הדמות במשחק.
הוכחת אפס ידיעה בקריפטוגרפיה.