חידת הצפנה

[עריסטו]

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

 

[יוביוב הירוק]

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

 

[עריסטו]

התכוונתי למשהו קצת יותר פשוט.

 

[הפרבולה1]

התכוונתי למשהו קצת יותר פשוט.

יש 10 אפשרויות לבחור 3 מנהלים מתוך החמישה. לכל אפשרות כזאת בוחרים 3 מספרים בין 0 ל999999 כך שסכומם מודולו מליון שווה לקוד של הכספת. קיבלנו 10 שלשות של מספרים.

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

כאשר חוברים 3 מנהלים יחד הם מזהים את השלישיה המתאימה מתוך ה10 וכל אחד חושף את המספר ששיך לאותה שלישיה, מסכמים מודלו מליון ומקבלים את הקוד לכספת.

נראה לי שזה מה שיוביוב התכוון, אז לא יודע אם זה פשוט כמו שהתכוונתה .

 

[עריסטו]

התכוונתי להסבר שונה מעט:
בוחרים 10 מספרים שסכומם מודולו מיליון הוא הקוד. לכל מספר נותנים גם אות מ-a עד j.
יש 10 אפשרויות לבחור 3 מנהלים מתוך 5. לכל שלשת מנהלים כזו נותנים אחד מ-10 המספרים ואת האות המתאימה (כלומר נותנים שלושה עותקים של המספר - אחד לכל חבר בשלשה). כך כל מנהל מקבל 6 מספרים, למשל המנהל הראשון יודע את ערכם של a,b,c,d,e,f.
כל זוג מנהלים לא יכול לפתוח את הכספת כי אין בידיו את המספר שנמצא אצל שלושת המנהלים האחרים. אבל כל שלשה יכולה לפתוח את הכספת, שהרי אין מספר שכל עותקיו נמצאים בידי שני המנהלים האחרים (כי מכל מספר חילקנו שלושה עותקים).