הצפנת סף

בקריפטוגרפיה, הצפנת סף (threshold cryptography) היא מערכת הצפנה המבוצעת בין שולחים או מקבלים מרובים התורמים במידה שווה למערכת, בניגוד למערכת הצפנה בין שולח יחיד למקבל יחיד. סכמת הצפנה תקרא הצפנת-סף <math>(t,n)</math> אם לצורך הצפנה או פענוח נדרשים לפחות <math>t</math> משתפי פעולה מתוך <math>n</math> מורשים כדי שההצפנה או פענוח יצליחו. כאשר <math>n</math> הוא מספר המורשים לשלוח או לקבל את המסר המוצפן ואילו <math>t</math> נקרא "מספר סף" הקובע את כמות המשתתפים המינימלית הנחוצה ואילו פחות ממספר זה ההצפנה או הפענוח יכשלו כי אין מספיק מידע להשלמתם. כמו כן ניתן להגדיר חתימה דיגיטלית עם סכמת סף, באופן שיידרשו לפחות <math>t</math> חותמים מתוך <math>n</math> מורשים כדי שהחתימה תהיה תקפה.

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

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

==מוטיבציה==
רוב סכמות ההצפנה המודרניות מוגדרות בין שולח ומקבל. אך ישנם מקרים שבהם נדרשים מספר משתתפים. הדוגמה הראשונה למערכת כזו הופיעה בתקן EES של NIST שנקרא שבב קליפר (clipper chip). במערכת זו צד שלישי מוסמך (במקרה זה ארגון ממשלתי כמו NSA) מקבל חלקים (shares) של מפתחות כל המשתמשים במערכת הצפנה מסוימת המיושמת בחומרה באופן כזה שבמידת הצורך רשויות החוק יכולים בצו שופט לקבל לידיהם את המפתח הזה ואיתו לפענח מידע ספציפי מבלי להדליף כל מידע אחר שאינו נחוץ במישרין. רבים מביעים התנגדות לשיטה זו בטענה שהיא פוגעת בפרטיות המשתמשים ואינה משיגה את יעדה. סכמת סף שימושית גם במקרים אחרים למשל; מסמכים הצריכים חתימה של מספר מורשים בארגון, מערכות קריטיות הדורשות אישור של מספר ממונים בעלי דרגה בכירה כדי להפעילן או תהליכים בהם נדרשת הכרעת רוב וכדומה. דוגמאות אחרות הן:
*פסאודו אקראיות עם סף. מספר פסאודו אקראי לצורך מערכת הצפנה נוצר במשותף על ידי מספר משתמשים, כך שכל אחד מהם תורם תרומה שווה להכנתו.
*אפס ידיעה עם סף. פרוטוקול אפס ידיעה שבו מספר סף של משתתפים מוכיחים יחד ידיעת סוד מסוים מבלי להדליף מאומה למשתתפים האחרים או לכל אדם אחר כל מידע נוסף מלבד עצם ההוכחה. 
*קוד אימות עם סף. זהו קוד אימות מסרים שבו נדרשים מספר סף של משתתפים כדי לייצר תג אימות למסמך מסוים.

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

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

==תיאור כללי==
קיימות שתי גישות עיקריות לבניית סכמת סף, האחת היא שימוש בתכונת הומומורפיזם של אלגוריתם ההצפנה. הרבה סכמות הצפנה עונות על הגדרה זו באופן חלקי, כמו RSA, אל-גמאל, הצפנת פאיי ועוד. לדוגמה אם נתונה הפונקציה <math>f_k(\text{input})</math> המקבלת מפתח <math>k</math> וקלט שבמקרה של הצפנה הוא טקסט-מוצפן המיועד לפענוח ובמקרה של חתימה דיגיטלית מסמך לחתימה. כעת אם נתונה פונקציית מעטפת המקיימת <math>g_{\text{input}}(k)=f_k(\text{input})</math> אזי היא תקרא הומומורפית אם מתקיים: 
:<math>g_{\text{input}}(k_1)\star g_{\text{input}}(k_2)=g_{\text{input}}(k_1+k_2)</math>. 
כאשר <math>k_1</math> ו-<math>k_2</math> הם אלמנטים של חבורה אבלית <math>K^+</math>. לדוגמה הצפנת אל-גמאל מקיימת את התנאי האמור. אפשר להפוך כל מערכת הצפנה להצפנה הומומורפית חלקית או מלאה וממנה לבנות סכמת סף. כשהמטרה היא שהמערכת תהיה בטוחה לפחות כמו הסכמה המקורית. 

הגישה השנייה היא חלוקת סוד כפלית כמו סכמת חלוקת סוד של עדי שמיר שמתאימה להרבה אלגוריתמים אסימטריים אך לא לכולם. בסכמת חלוקת סוד מפתח הצופן פשוט מחולק בין המשתתפים באופן כזה שרק שיתוף פעולה של לפחות <math>t</math> מהם מאפשר לשחזר את המפתח ואיתו לפענח את ההצפנה. כאשר נדרשים לשחזר את הסוד, כל משתתף מוסר את השתף שלו לדילר מרכזי שתפקידו "להכפיל" את כל החלקים או הכמות המינימלית שלהם כדי לשחזר את הסוד.

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

==הכללה==
גישה יותר כללית של סכמת סף נקראת "מבנה גישה" (Access Structure). נניח ש-<math>\mathcal{P}</math> הוא קבוצה של משתתפים מבנה גישה <math>\Gamma_{\mathcal{P}}</math> הוא תת-קבוצה של קבוצת החזקה <math>2^{\mathcal{P}}</math>. כאשר כל אלמנט של <math>\Gamma_{\mathcal{P}}</math> נקרא "רשאי" כלומר יש לו גישה לסוד המשותף. <math>\Gamma_{\mathcal{P}}</math> נקרא מונוטוני אם כאשר <math>\mathcal{A}\subseteq\mathcal{B}\subseteq\mathcal{P}, \mathcal{A}\in \Gamma_{\mathcal{P}}</math>, אז <math>\mathcal{B}\in \Gamma_{\mathcal{P}}</math>. מבנה יריב הוא המבנה המשלים המסומן <math>2^{\mathcal{P}} \setminus \Gamma_{\mathcal{P}}</math>.

==ראו גם==
*שידור מוצפן
*חלוקת סוד

==הערות שוליים==

קטגוריה:הצפנה