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