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

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

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

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

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

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

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

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

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

וזה סופר פולינומי.^[2]

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

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

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

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

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

${\displaystyle |\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]|}$

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

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

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

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