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

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

ככלל אלגוריתם הצפנה יהיה בעל ביטחון מוכח אם ההסתברות של שבירה אפילו חלקית שלו (כמו הפיכת פונקציה חד-כיוונית או הבחנה בין פלט מחולל פסאודו-אקראי לבין רצף אקראי אמיתי) תהיה בסבירות מאוד מאוד נמוכה ביחס לאורך המפתח. באופן כללי אם היריב מסוגל לפצח אלגוריתם הצפנה בהסתברות של $1/p(n)$ עבור פולינום חיובי כלשהו $p$ הרי שהאלגוריתם לא יקרא בטוח. מצד שני אם ההסתברות לשבירת האלגוריתם קטנה אסימפטוטית מ- $1/p(n)$ עבור כל פולינום $p$ אפשר להגיד שהאלגוריתם בטוח כי ההסתברות כל כך קטנה שהיא נחשבת לזניחה.

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

הפונקציה

f

תקרא זניחה אם עבור כל פולינום חיובי

p(\cdot )

(כלומר כל הערכים ש-

p

מקבל חיוביים) קיים שלם חיובי

N

כך שעבור כל השלמים

n>N

מתקיים

\textstyle |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)\leq n^{-c}$ . נשתמש בעובדה ש- $g_{1}(n),g_{2}(n)\leq n^{-(c+1)}$ . מאחר שהן זניחות, צרוף של שתי פונקציות זניחות שקטנות שוות ל- $n^{-(c+1)}$ חייבות להיות קטנות מ- $n^{-c}$ .

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

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

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

דוגמאות

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

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

לדוגמה, צופן AES נחשב בעל ביטחון אופטימלי במובן שיריב שרץ בזמן $t$ (שנמדד למשל במחזורי שעון) מסוגל לשבור את הצופן בזמן של לכל היותר $\epsilon =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}$ ו- $\epsilon =2^{-48}$ אז המפתח צריך להיות באורך 128 סיביות לפחות. בחירה כזו מספקת מרווח ביטחון מניח את הדעת לכל צורך מעשי לטווח הקרוב. כאשר מחשבים קוונטיים יהיו מעשיים יש כאלו שסבורים שיהיה צורך להכפיל את אורך המפתח.