סיבית קשה

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

הגדרה[עריכת קוד מקור | עריכה]

תהי f: n\to 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 ] < \frac12 + \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, הוכיחו מדעני המחשב עודד גולדרייך ולאוניד לוין, שכל פונקציה חד-כיוונית ניתן לשנות לפונקציה חד-כיונית בעלת סיבית קשה (חישובית)‏[1]. בהינתן פונקציה חד-כיונית \ 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.

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ O. Goldreich, L. Levin, "A hard-core predicate for all one-way functions", In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing (STOC), 1989 (pdf)