סיבית קשה

בתורת הקריפטוגרפיה, סיבית קשה של פונקציה חד-כיוונית $\ f$, היא פונקציה $\ b(x)$ בעלת פלט של סיבית אחת (זוהי הסיבית ה"קשה") שקשה לנחשה גם כאשר הערך $\ f(x)$ ידוע.

הגדרה

תהי $f:\{0,1\}^{n}\to \{0,1\}^{n}$ פונקציה חד-כיוונית. הפונקציה $b:\{0,1\}^{n}\to \{0,1\}$ נקראת "סיבית קשה" של $\ f$ אם מתקיימים התנאים הבאים:

1. הפונקציה $\ b$ ניתנת לחישוב בזמן פולינומי.
2. לכל מכונת טיורינג הסתברותית $\ A$, ההסתברות לנחש את $\ b(x)$ בהינתן $\ f(x)$ זניחה,

$$\Pr _{x}\left[A\left(1^{n},f(x)\right)=b(x)\right]<{\frac {1}{2}}+\epsilon _{n}$$ (כאשר $\ n=|x|$, ו-$\ \epsilon _{n}$ היא פונקציה הקטנה מ-${\frac {1}{n^{c}}}$ לכל $\ c$, עבור $\ n$ גדול דיו. ההסתברות היא על מרחב כלל הקלטים האפשריים, והטלת המטבעות של A.)

שימושים

ביט-קשה של פונקציה חד-חד ערכית חד כיוונית, יכול לשמש עבור פרוטוקול התחייבות לביט, בו משתמש מתחייב לביט מסוים, מבלי לגלות מהו הביט. למשל, כאשר שני משתמשים (אליס ובוב), שאינם נמצאים זה ליד זה, רוצים להטיל מטבע יחדיו באופן אקראי, מבלי שאחד הצדדים יוכל לרמות. פתרון אפשרי הוא שאליס תתחייב לביט מסוים $\ b(x)$ על ידי שליחת הערך $\ f(x)$. כיוון שהביט הנ"ל הוא קשה בוב אינו יודע מהו הביט אליו אליס מחויבת. בוב ממשיך על ידי בחירת ביט אקראי $\ r$. כעת אליס מגלה את הערך $\ x$, ובוב בודק שאכן $\ f(x)$ הוא הערך שאליס שלחה בהתחייבות, ומחשב את הביט שאליו אליס מחויבת, $\ b(x)$.

הביט שהוגרל בשיטה זו הוא $b(x)\oplus r$. שני הצדדים אינם יכולים לרמות: בוב אינו יודע את הערך של $\ b(x)$, ולכן אינו יכול להטות את התוצאה על ידי בחירת $\ r$. אליס אינה יכולה לשנות את התחייבותה, מכיוון שהפונקציה חד-חד ערכית ולכן, לפי הגדרה, לא קיים $\ x'$ כך ש-$\ f(x')=f(x)$. מכאן נובע ששני הצדדים בחרו ביט מבלי לדעת מה האחר בחר, ולכן הביט הסופי הוא "הוגן".

שימוש נוסף עבור ביט-קשה הוא בניית מחולל פסבדו אקראי קריפטוגרפי. בהינתן גרעין $\ s$ מפעילים עליו שוב ושוב את הפרמוטציה החד-כיוונית, ועבור כל הפעלה מחשבים את הביט-הקשה. המחרוזת הנוצרת מהביטים הקשים מהווה פלט פסבדו אקראי במובן הקריפטוגרפי. באופן פורמלי, המחולל $\ G(s)$ ניתן לתיאור עלי-ידי $$G(s)\equiv b(f(s))b(f^{2}(s))\ldots b(f^{k}(s))$$ כאשר $k$ הוא פולינומי באורך הקלט $\ s$, ו-$\ f^{i}(s)$ משמעותו הפעלת הפרמוטציה $\ i$ פעמים, לדוגמה $\ f^{3}(s)=f(f(f(s)))$.

קיום

בשנת 1989, הוכיחו מדעני המחשב עודד גולדרייך ולאוניד לוין, שכל פונקציה חד-כיוונית ניתן לשנות לפונקציה חד-כיוונית בעלת סיבית קשה (חישובית). בהינתן פונקציה חד-כיוונית $\ f$, נגדיר את הפונקציה $\ f'(x,r)=f(x),r$ עבור $\ |f(x)|=|r|$. פונקציה זו היא חד-כיוונית והסיבית $\ b(x,r)=x\cdot r$ היא סיבית קשה של $\ f'$.

ההוכחה מתבססת על כך שאם קיים אלגוריתם לניחוש הסיבית הקשה, ניתן להשתמש בו על מנת להפוך את הפונקציה החד-כיוונית $\ f'$: בהינתן $\ f(x)$ האלגוריתם "מנחש" את ערך הביט-הקשה עבור כמות קטנה של ערכי $\ R$, (נאמר, $\ \log(n)$ קלטים כנ"ל). בעזרת ניחוש זה ניתן לבנות קבוצה גדולה של ערכי $\ R$ שהם בלתי-תלויים בזוגות. אם קיימת מכונה אשר מגלה את הביט הקשה בהסתברות בלתי-זניחה, ניתן להפעיל את המכונה על הקבוצה הגדולה של ה-$\ R$ים, ולהשוות אל הערכים שניחשנו. משיקולים הסתברותיים, ניתן יהיה לזהות מהו הניחוש הנכון של הביטים הקשים עבור הקבוצה ההתחלתית הקטנה, בהסתברות בלתי-זניחה. מכיוון שכל ערך $\ R$ הוא פונקציה ליניארית של סיביות $\ x$, מספיקה ידיעת $\ \log(n)$ ערכים בלתי-תלויים על מנת לחשב את כלל הסיביות של $\ x$.

לקריאה נוספת

• Oded Goldreich, Foundations of Cryptography vol 1: Basic Tools, Cambridge University Press, 2001.