פונקציה זניחה

במתמטיקה ובקריפטוגרפיה פונקציה זניחה (Negligible function) היא פונקציה שהערכים שהיא מחזירה קטנים מאוד - זניחים - ביחס לערכים שהיא מקבלת. פורמלית, פונקציה $f:\mathbb{\mathbb{N}}\to \mathbb{\mathbb{N}}$ נחשבת לזניחה אם לכל פולינום $p$, הפונקציה קטנה יותר מהר מהפונקציה $1/p$. בקריפטוגרפיה, המטרה היא שכל יריב מוגבל חישובית יוכל להצליח לשבור את ההצפנה (כלומר, לגלות את הטקסט המקורי שהוצפן) בהסתברות זניחה לכל היותר, כלומר, עבור טקסט מוצפן באורך $n$, היריב יוכל להצליח לגלות את הטקסט הסודי המקורי בסיכוי לכל היותר $negl(n)$, כאשר $negl$ היא פונקציה זניחה. ככלל סכמה קריפטוגרפית תחשב בטוחה אם ההסתברות של שבירה אפילו חלקית שלו (כמו הפיכת פונקציה חד-כיוונית או הבחנה בין פלט מחולל פסאודו-אקראי לבין רצף אקראי אמיתי) חסומה על-ידי פונקציה זניחה של אורך הקלט.

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

הפונקציה $f$ תקרא זניחה אם עבור כל פולינום חיובי $p(\cdot )$ (כלומר כל הערכים ש-$p$ מקבל חיוביים) קיים שלם חיובי $N$ כך שעבור כל השלמים $n>N$ מתקיים $|f(n)|<\frac{1}{p(n)}$.

דרך אחרת לנסח זאת: עבור כל קבוע $c$ קיים שלם חיובי $N$ כך שעבור כל $n>N$ מתקיים $f(n)<n^{-c}$.

פונקציית זניחות מקיימת תכונת סגירות מסוימת. עבור שתי פונקציות זניחות ${\text{negl}}_1$ ו-${\text{negl}}_2$ מתקיים ${\text{negl}}_3(n)={\text{negl}}_1(n)+{\text{negl}}_2(n)$ זניחה גם היא. וכן עבור כל פולינום $p$ הפונקציה ${\text{negl}}_4(n)=p(n)\cdot {\text{negl}}_1(n)$ נקראת גם כן זניחה.

הוכחה:

הרעיון: להראות שלפונקציה $f$ כלשהי $f(n)\le n^{-c}$ . נשתמש בעובדה ש-$g_1(n),g_2(n)\le n^{-(c+1)}$. מאחר שהן זניחות, צירוף של שתי פונקציות זניחות שקטנות שוות ל-$n^{-(c+1)}$ חייבות להיות קטנות מ-$n^{-c}$.

אנחנו צריכים להראות של-$c\in \mathbb{\mathbb{N}}$ כלשהו, אנחנו יכולים למצוא $n_0$ ככה ש-$\mathrm{\forall }n\ge n_0,f(n)\le n^{-c}$ נבחר$c\in \mathbb{\mathbb{N}}$. מכיוון שגם $c+1\in \mathbb{\mathbb{N}}$ וגם $g_1(n),g_2(n)$ זניחות, יש $n_{g_1},n_{g_2}$ שבהם $\mathrm{\forall }n\ge n_{g_1},g_1(n)\le n^{-(c+1)}$ וגם $\mathrm{\forall }n\ge n_{g_2},g_2(n)\le n^{-(c+1)}$. נבחר $n_0=\max (n_{g_1},n_{g_2},2)$, ואז עבור $n\ge n_0$כלשהו, יש לנו $f(n)=g_1(n)+g_2(n)\le n^{-(c+1)}+n^{-(c+1)}=2n^{-(c+1)}\le n*n^{-(c+1)}$בגלל $n\ge n_0\ge 2$ מה שמראה שגם $f(n)\le n^{-c}$ ומכיוון שכך $f(n)$ זניחה

מזה נובע שאם אירוע מסוים מתרחש בהסתברות זניחה בניסוי אחד אז היא תוותר זניחה גם אם חוזרים על הניסוי מספר פולינומי של פעמים. לדוגמה הסיכויים שלאחר הטלת $n$ מטבעות יתקבל בכולם "עץ" מאוד נמוכים. משמעות הדבר היא שגם אם נחזור על הניסוי של הטלת $n$ מטבעות (במספר פולינומי של פעמים) ההסתברות שזה יקרה תישאר זניחה.

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

דוגמאות

הפונקציות $2^{-n}$ או $2^{-\sqrt{n}}$ נקראות זניחות אף על פי שהן מתכנסות לאפס בקצב שונה. לעומת זאת $n^{-3}$ אינה זניחה. אם קובעים רף של $10^{-6}$ אז עבור $n\ge 20$ מתקבל $2^{-n}<10^{-6}$. כמו כן אפשר לראות שעבור כל $n>65,536$ מתקיים $2^{-\sqrt{n}}<n^{-\log n}$ מזה נובע שעבור $n$ גדול הסתברות של $2^{-\log n}$ יותר זניחה.

בהערכת פונקציית זניחות יש חשיבות רבה לגודלו של פרמטר הביטחון $n$ שבדרך כלל מייצג את אורך המפתח/אורך הבלוק בסיביות. אם $n$ נמוך למשל $n\le 40$ אז אף על פי שהפונקציה $2^{40}\cdot 2^{-n}$ נחשבת לכאורה לזניחה ביחס ל-$n$, אבל מאחר ש-$n$ קטן, יכול להיות מצב שיריב שרץ במשך זמן של $n^3$ דקות יכול לשבור את אלגוריתם ההצפנה בכוח גס בהסתברות של כמעט 1. כי במקרה ש-$n=40$ זמן ריצה של $40^3$ דקות יוצא בסך הכול שישה שבועות. לעומת זאת אם $n=500$ יריב שרץ בזמן של מאתיים שנה יצליח לשבור את האלגוריתם בהסתברות של $2^{-500}$ בקירוב, זמן כל כך לא מעשי שהוא נחשב לזניח.

לדוגמה, צופן AES נחשב בעל ביטחון אופטימלי במובן שיריב שרץ בזמן $t$ (שנמדד למשל במחזורי שעון) מסוגל לשבור את הצופן בזמן של לכל היותר $ϵ=t/2^n$. בטכנולוגיה הנוכחית חישובים בסדר גודל של $2^{60}$ נחשבים בקושי ברי ביצוע. אם למשל המחשב פועל במהירות של 1GHz שאז מתבצעים בערך $10^9$ מחזורים בשנייה, המשמעות היא של-$2^{60}$ מחזורי שעון דרושים $2^{60}/10^9$ שניות, או בערך 35 שנה. אם משתמשים במחשבי על מרובים באופן מקבילי אפשר לצמצם את זמן החישוב לכדי שנתיים. היות שאורך המפתח ב-AES הוא לפחות 128 סיביות, מתקבלת תוספת ביטחון בפקטור של $2^{68}$ שזה מספר בן עשרים ספרות עשרוניות בקרוב. כדי לקבל מושג כמה גדול המספר הזה, לפי הערכות של פיזיקאים מספר השניות שחלפו מאז המפץ הגדול הוא בערך $2^{58}$.

אירוע שמתרחש אחת למאה שנים, יקרה בהסתברות של $2^{-30}$ בקירוב. כל אירוע שההסתברות שיקרה בכל רגע היא $2^{-60}$, יקרה בהסתברות נמוכה יותר בפקטור של $2^{-30}$ כלומר הוא צפוי לקרות אחת למאה מיליארד שנים. המסקנה היא שאם $t=2^{80}$ ו-$ϵ=2^{-48}$ אז המפתח צריך להיות באורך 128 סיביות לפחות. בחירה כזו מספקת מרווח ביטחון מניח את הדעת לכל צורך מעשי לטווח הקרוב. כאשר מחשבים קוונטיים יהיו מעשיים יש כאלו שסבורים שיהיה צורך להכפיל את אורך המפתח.

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

פונקציה זניחה39070555Q1766279