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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

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

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

הגדרה פורמלית[עריכת קוד מקור | עריכה]

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

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

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

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

דוגמאות[עריכת קוד מקור | עריכה]

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

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

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

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

הערות שוליים[עריכת קוד מקור | עריכה]