משתנה היברידי

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

מבוא

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

דוגמה

נניח שיש לנו יצרן פסאודו אקראי הממפה קלט מאורך n ביטים לאורך n+1 ביטים. נרצה להוכיח שקיים יצרן שממפה קלט מאורך n ביטים לאורך 2n ביטים. בסיס האינדוקציה - קיום יצרן בטוח מ-n ל-n+1

צעד האינדוקציה - אם קיים יצרן $G_{k}$ הממפה מ-k ל-k+1 (עבור k > n) אזי קיים יצרן הממפה מ-k ל-k+2

בנייה עבור קלט $s_{0}$ באורך n

1. נסמן: $\sigma _{i},s_{i}=G(s_{i-1})$, כאשר $|\sigma _{i}|=1$.
2. נחזור על התהליך למעלה k+2 פעמים, ונקבל $(\sigma _{1},...,\sigma _{k+2})$
3. נחזיר את הווקטור $(\sigma _{1},...,\sigma _{k+2})$

אם נבדוק נראה שאכן זו בנייה בטוחה. אך הבעיה שונה.

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

$t(G_{2n}(\cdot ))=2n*t(G_{2n-1}(\cdot ))=...\geq n^{n}*t(G_{n}(\cdot ))$

וזה סופר פולינומי.

הגדרה פורמלית

נרצה להראות שההתפלגויות $D^{1},D^{2}$ אינן מובחנות חישובית, כלומר

לכל יריב A, לכל פולינום $p(\cdot )$ ולכל n גדול דיו

$|\Pr[A(x\gets D^{1})=1]-\Pr[A(x\gets D^{2})=1]|<{\frac {1}{p(n)}}$

כאשר $x\gets D^{i}$ מסמל דגימה יוניפורמית מ-$D^{i}$, ו-n הוא פרמטר הביטחון.

נגדיר משתנה היברידי $D_{1}:=H_{0},H_{1},...,H_{t}:=D_{2}$ כאשר t פולינומי בפרמטר הביטחון n. מתקיים:

$|\Pr[A(x\gets D_{2})=1]-\Pr[A(x\gets D_{1})=1]|=|\sum _{i=1}^{n}\Pr[A(x\gets H_{i})=1]-\Pr[A(x\gets H_{i-1})=1]|$

ועל פי אי שוויון המשולש, הביטוי שלמעלה קטן או שווה ל-

$\sum _{i=1}^{n}|\Pr[A(x\gets H_{i})=1]-\Pr[A(x\gets H_{i-1})=1]|$

מאחר ש-t פולינומי ב-n, ועל פי עקרון שובך היונים, אם קיים מבחין A בין $D_{1},D_{2}$ עם יתרון לא זניח אז ניתן להבחין גם בין $H_{i}$ ל-$H_{i+1}$ מסוים. מכאן נובע שאם ניתן להוכיח עבור כל זוג היברידים שכנים שהם ניתנים להבחנה בהסתברות זניחה לכל היותר, אזי נובע מיד שלילת הטענה שלמעלה, כלומר זה גורר באופן מיידי שמתקיים ${D_{1}}\equiv ^{c}{D_{1}}$, כלומר ההתפלגויות ניתנות להבחנה עם יתרון זניח לכל היותר.

שימושים

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

דוגמה

פרק זה לוקה בחסר. אנא תרמו לוויקיפדיה והשלימו אותו.