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

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

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

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

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

פונקציית זניחות מקיימת תכונת סגירות מסוימת. עבור שתי פונקציות זניחות  ו- מתקיים  זניחה גם היא. וכן עבור כל פולינום  הפונקציה  נקראת גם כן זניחה.

הוכחה:

הרעיון: להראות שלפונקציה  כלשהי  . נשתמש בעובדה
ש-. מאחר שהן זניחות, צירוף של שתי פונקציות זניחות שקטנות שוות ל- חייבות להיות קטנות מ-.

אנחנו צריכים להראות של- כלשהו, אנחנו יכולים למצוא  ככה ש- נבחר. מכיוון שגם  וגם  זניחות, יש  שבהם  וגם . נבחר , ואז עבור כלשהו, יש לנו בגלל  מה שמראה שגם  ומכיוון שכך  זניחה

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

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

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

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

לדוגמה, צופן AES נחשב בעל ביטחון אופטימלי במובן שיריב שרץ בזמן  (שנמדד למשל במחזורי שעון) מסוגל לשבור את הצופן בזמן של לכל היותר . בטכנולוגיה הנוכחית חישובים בסדר גודל של  נחשבים בקושי ברי ביצוע. אם למשל המחשב פועל במהירות של 1GHz שאז מתבצעים בערך  מחזורים בשנייה, המשמעות היא של- מחזורי שעון דרושים  שניות, או בערך 35 שנה. אם משתמשים במחשבי על מרובים באופן מקבילי אפשר לצמצם את זמן החישוב לכדי שנתיים. היות שאורך המפתח ב-AES הוא לפחות 128 סיביות, מתקבלת תוספת ביטחון בפקטור של  שזה מספר בן עשרים ספרות עשרוניות בקרוב. כדי לקבל מושג כמה גדול המספר הזה, לפי הערכות של פיזיקאים מספר השניות שחלפו מאז המפץ הגדול הוא בערך .

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

הערות שוליים

הצפנה