הרעיון של שיטת חלוקת הסוד של בלקלי מבוסס על נקודת ההצטלבות של שני קווים לא מקבילים במישור דו-ממדי במקרה של שני משתתפים, או נקודת ההשקה של שלושה או יותר מישורים לא מקבילים במרחב תלת-ממדי. כל חלק של הסוד הוא ערכי הנקודות המרכיבות מישור אחד והסוד הוא נקודת המפגש של כל המישורים. בהינתן נקודת המפגש של שני מישורים בלבד, אין די מידע כדי לגלות את הסוד (אם כי מעט מידע אכן מושג), אלא רק על ידי צירוף המידע של כל החלקים יחדיו מאפשר למצוא את נקודת המפגש, שהיא הסוד. לשיטת בלקלי מספר חסרונות, גם בשל העובדה שככל שידועים יותר מישורים כך מושג יותר מידע המצמצם את טווח ההסתברות של הסוד (לקו ההשקה של המישורים) וכן בשל העובדה שכל חלק מן הסוד גדול במידה ניכרת מהסוד עצמו.
בעיית חלוקת סוד כבעיה קומבינטורית.
ניתן להמחיש את הבעיה הכללית של חלוקת סוד בעזרת בעיה קומבינטורית ידועה: אחד-עשר מדענים עובדים על פרויקט סודי אותו הם מעוניינים לשמור בכספת. מטעמי בטיחות כל מדען צריך לקבל מנעול ומפתח משלו, אולם למען הנוחות הם מעוניינים שדי יהיה בנוכחות שישה מהם כדי לפתוח את הכספת. מהו מספר המנעולים הקטן ביותר הדרוש להם? ומהו מספר המפתחות הקטן ביותר שכל מדען יידרש לשאת על מנת לאפשר זאת? הפתרון המתמטי (לפי נוסחת הבינום) מראה שמספר המנעולים הדרוש הוא 462 וכל מדען צריך לשאת 252 מפתחות. בדרך זו מובטח שכל תת-קבוצה של שישה מדענים תוכל לפתוח את הכספת. כמובן שפתרון זה אינו מעשי לאור העובדה שמספר המפתחות והמנעולים יגדל באופן מעריכי ככל שמספר המדענים יגדל (למשל למספר כפול של מדענים יידרשו לא פחות מ-74,613 מנעולים וכל מדען יאלץ לשאת 20,349 מפתחות לפחות).
כמובן שלא ניתן לפתור בעיה זו על ידי חלוקה פשוטו כמשמעו של הסוד לכל המשתתפים. למשל אם הסוד הוא מפתח הצפנה בגודל 64 סיביות אותו מעוניינים שני משתתפים לחלוק ביניהם. אם כל משתמש יקבל מחצית מהמפתח, קרי 32 סיביות. הרי שניחוש המפתח השלם באמצעות כוח גס על ידי המשתתף האחר או על ידי יריב במקרה שאחד נחשף מצריך רק formula_17 ניסיונות. בכללות עבור formula_18 סיביות ו-formula_19 חלקים אפשר לנחש את הסוד ב-formula_20 ניסיונות.
תכונות.
סכמת חלוקת סוד תקרא מושלמת אם אף קבוצה לא מורשית של משתתפים לא תוכל להסיק כל מידע ביחס לסוד מהחלקים שניתנו לחבריה. כלומר בהינתן רק formula_7 חלקים או פחות, הסוד יכול להיות כל ערך בהסתברות שווה. סכימת הסף של עדי שמיר נקראת מושלמת בהקשר זה. יתירה מזו בניגוד לשיטות קריפטוגרפיות אחרות, שיטת שמיר אינה מסתמכת על השערות בלתי מוכחות כלשהן כגון בעיות מתמטיות פתוחות מתורת המספרים. בנוסף סכימת-הסף של עדי שמיר מקיימת את התכונות הבאות:
פנקס חד-פעמי.
קיימת שיטה פשוטה לחלוקת סוד עבור המקרה formula_22, כלומר כאשר יש צורך בכל החלקים על מנת לשחזר את הסוד. שיטה זו מושלמת מהיבט של תורת האינפורמציה והיא מבוססת על פנקס חד פעמי כדלהלן: הסוד מקודד כמחרוזת סיביות ועבור formula_19 משתתפים מייצרים formula_24 רצפים אקראיים formula_25 וכל משתתף formula_26 למעט האחרון יקבל אחד מהם בהתאם. כאשר המשתתף האחרון formula_27 יקבל את formula_28. כלומר חיבור מודולו 2 (XOR) של כל הערכים האקראיים עם הסוד. לא קשה להוכיח כי מאקראיות החלקים האחרים נובע שגם formula_29 אקראי ולכן אינו מכיל בפני עצמו כל מידע על הסוד. רק שיתוף פעולה של כל המשתתפים כלומר רק חיבור XOR של כל הערכים האקראיים יניב את תוצאה הרצויה; כלומר formula_30, פחות מכך התוצאה שתתקבל תהיה חסרת תועלת לחלוטין.
החסרון הוא כאמור בצורך בשיתוף פעולה של כולם, בדרך זו אין אפשרות לשחזר את הסוד על ידי מספר קטן יותר של משתתפים. עובדה היוצרת בעיה בהיעדר אחד המשתתפים (כגון במקרה של מחלה או מוות פתאומי) או כאשר אחד מהם אינו מעוניין לשתף פעולה.
מנגנון סכימת-סף (n,t) של עדי שמיר.
רעיון כללי.
המנגנון מבוסס על תכונה ידועה של פולינומים; בהינתן formula_5 נקודות במישור דו-ממדי formula_32 עם קואורדינטות formula_33 שונות, קיים פולינום אחד ויחיד formula_34 מסדר formula_7 המקיים formula_36, עבור כל שלם formula_37.
כדי לחלק את הסוד formula_1 ל-formula_2 משתתפים בוחרים פולינום אקראי מסדר formula_7 המוגדר: formula_41, קובעים את formula_42 (הסוד עצמו) ואז מחלקים לכל אחד את ערך הפולינום בנקודה formula_37 באופן זה: formula_44 בהתאם למספר המשתתפים (למעט formula_45). בהינתן כל תת-קבוצה formula_5 של נקודות (formula_47 עם מציין formula_37) ולא חשוב איזה מהם, ניתן לשחזר את הפולינום formula_34 ולכן לשחזר את הסוד formula_50. מאידך formula_7 ערכים כאלו אינם מספיקים. חישוב המקדמים formula_52 על ידי formula_5 הנקודות אפשרי על ידי אינטרפולצית לגראנג'. שמיר המחיש את הרעיון באמצעות חשבון מודולרי בשדות סופיים ולא בשדות ממשיים או שדה המספרים המרוכבים, הן בשל הנוחות שביישום ממוחשב של שדות אילו והן מטעמי בטיחות. קבוצת השלמים מודולו מספר ראשוני גדול מהווה שדה סופי, שבו אינטרפולציה היא פשוטה לביצוע, ואפשר להוכיח שהוא מספק רמת בטיחות גבוהה. קיימים אלגוריתמים לאינטרפולציה בשדות מסדר ראשוני בסיבוכיות של formula_54.
אלגוריתם.
מנגנון חלוקת סוד של עדי שמיר מאפשר לחלק סוד formula_55 בין formula_2 משתמשים באופן כזה שכל קבוצה של formula_19 משתמשים תוכל לצרף את חלקם יחד ולשחזר את הסוד. ניתן ליישם את המנגנון כך שהמשתמשים מסתייעים בצד שלישי שתפקידו לבחור את הסוד בעצמו ולחלקו בין המשתמשים בדרך בטוחה, כך שכל משתמש מכיר רק את חלקו בסוד.
חלוקת סוד בעזרת משפט השאריות הסיני.
אחד הרעיונות לשימוש ב-CRT ככלי לחלוקת סוד הוצע על ידי Asmuth-Bloom ב-1983. תחילה מכינים סדרה עולה של שלמים חיוביים זרים זה לזה formula_89 שמקיימת:
formula_90
ואז בהינתן סדרה פומבית כזו וסוד formula_91 המיועד לחלוקה בין formula_92 חברים, כאשר formula_93, האלגוריתם פועל כדלהלן:
ישנן שיטות יעילות לחישוב CRT. השיטה הישירה לפי גאוס מוצאת פתרון בסיבוכיות זמן של formula_106 פעולות בסיביות. בשיטה זו הפתרון הוא formula_107 כאשר formula_108 וכן formula_109 ו-formula_110. כלומר formula_103 הוא סכום הכפולות של החלקים הנוטלים חלק בשחזור הסוד והערכים formula_112 בהתאמה, המחושבים מודולו הכפולה של המודולים המקבילים להם. והערך formula_113 הוא הופכי כפלי מודולרי של formula_114 אותו אפשר לחשב על ידי אלגוריתם אוקלידס המורחב.
דוגמה במספרים קטנים.
דוגמה במספרים קטנים לסכימת סף (5,3). יהי הסוד formula_115 ונתונה הסדרה formula_116 עבור formula_117 משתתפים וכן formula_118 שימו לב שמתקיים התנאי formula_119. אם נבחר formula_120 תוצאת חישוב החלקים תהיה formula_121 כעת אם תת-קבוצה של formula_122 חברים, נניח: formula_123, formula_124 ו-formula_125 מעוניינים לשחזר את הסוד תחילה עליהם לפתור את מערכת הקונגרקואנציות:
קיים פתרון יחיד formula_129 והסוד הוא formula_130. שיתוף פעולה של פחות מ-formula_12 חברים לא יחשוף שום מידע לגבי הסוד.
שימושים נוספים בחלוקת סוד.
לחלוקת סוד תועלת רבה במקרים נוספים מעבר לשמירה על מפתחות הצפנה. להלן מספר דוגמאות:
תקשורת רדיו
מבצע נחשון
מבצע נחשון היה מבצע של ההגנה במלחמת העצמאות, שהחל בליל 6-5 באפריל 1948 והסתיים ב-15 באפריל. מטרתו הייתה לפרוץ את הדרך לירושלים, אשר הייתה מנותקת במידה זו או אחרת מאז פרוץ המלחמה, באמצעות יצירת ציר מאובטח, ועל ידי ארגון, העברת ואבטחת שיירות אספקה ותגבורת לעיר.
מבצע זה, אשר נערך בו זמנית עם קרבות משמר העמק, סימן את נקודת המפנה בשלב זה של המלחמה. מכאן ואילך, גילה היישוב יתרון ברור על ערביי ארץ ישראל, אשר נעזרו במתנדבים מן הארצות השונות. עם זאת, פתיחת הציר לירושלים הייתה זמנית, כיוון שהכוחות לאבטחת הדרך הופנו לגזרות אחרות עם סיום המבצע.
המבצע נקרא על שם נחשון בן עמינדב, שלפי המדרש היה הראשון מבני ישראל שנכנס לים סוף ביציאת מצרים, והפך לסמל של ראשוניות וחלוציות. בנוסף, המבצע נקרא על שם , שכינויו ב"הגנה" היה 'נחשון', שנהרג מספר ימים קודם לכן במרחב המבצע.
רקע.
כמעט כל הדרכים שמחוץ לערים היהודיות, עברו בקרבת, ולעיתים בתוך, יישובים ערביים, עד כדי טווח של נשק קל. היישוב היהודי, העירוני יותר והמתקדם יותר, היה תלוי יותר מן הערבי בתקינות התחבורה, ולכן השקיעו הכוחות הערבים מאמצים רבים בלחימה מסוג זה, שאף התאימה מאוד לאופי הכוחות שברשותם, עת רבים מהם לא היו מגויסים גיוס מלא. באזורים בהם שלטו הערבים באופן מוחלט על קטעים נרחבים מן הדרך, כמו הכבישים מירושלים לשפלה ולגוש עציון, הדרכים לנגב ועוד, הלחימה על הדרכים הייתה קשה ורבת קורבנות. הכישלון ליישם את תוכנית החלוקה הביא את נציג ארצות הברית באו"ם, וורן אוסטין, להעלות הצעה, ב-17 במרץ 1948, במועצת הביטחון, להקפיא את תוכנית החלוקה ולכונן בארץ ישראל משטר נאמנות של האו"ם.
עם זאת, עד סוף חודש מרץ, למרות הקרבנות, נשמר הקשר עם היישובים היהודיים. אולם באותו שלב החמיר המצב: מספר שיירות שיעדן יישובים מבודדים, כשיירת חולדה, שיירת נבי דניאל, ושיירת יחיעם, הושמדו כולן או חלקן (השלוש האמורות הותקפו בשבוע אחד בסוף מרץ, 'שבוע השיירות'), ובחלקן אף לא הגיעו ליעדן. המצב בירושלים החמיר, ואף עלה חשש לנפילתה.