אוהבת שירה.

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

לשחקן ראשון יש X בוחר אקראית A
לשחקן שני יש Y בוחר אקראית B
לשחקן שלישי יש Z בוחר אקראית C

שחקן ראשון מחשב X|A מעביר לשחקן שני.
שחקן שני מוסיף B ומעביר לשחקן שלישי. שחקן שלישי יודע X|A|B
שחקן שלישי מוסיף C ומחזיר לשחקן ראשון. שחקן ראשון יודע X|A|B|C. מכיוון ששחקן ראשון יודע X|A הרי שהוא יודע B|C
ועכשיו:
שחקן שני מעביר לשחקן ראשון Y|B
שחקן שלישי מעביר לשחקן ראשון Z|C

מה יודע שחקן ראשון?
יודע X|A|Y|B|Z|C
יודע B|C ויודע A
ולכן X|A|Y|B|Z|C|A|B|C=X|Y|Z
שזו בדיוק התשובה שחיפשנו ואותה אפשר לפרסם.

מה אני מקבלת?
:-))

poetry lover - את מקבלת את כל אהבתי, כמובן.
התשובה חכמה אך יש בה פגם.
אצטט אותך:
שחקן ראשון מחשב X|A מעביר לשחקן שני.
שחקן שני מוסיף B ומעביר לשחקן שלישי. שחקן שלישי יודע X|A|B
אם שחקן א' ושחקן ג' יעשו קואליציה, הם יוכלו ללמוד את הערך של שחקן ב'.
לכן האלגוריתם שלך אינו חסין קואליציות (אך הוא חסין כנגד "סקרן" בודד.

ולמרות זאת, אני אוהבת את החשיבה שלך.

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

קובלט - טוב, את תצטרכי לוותר לי הפעם על פיתוח מלא של הרעיון, אבל זה הולך ככה:
אנחנו מניחים שיש חמישה שחקנים, עד שלושה מהם משתפים פעולה (אם יש ארבעה רמאים, כמו בדוגמא הקודמת, אכלנו אותה...).
המשחק דומה, רק שהפעם השחקן השני בוחר 3 מספרים אקראיים: A, B ו - C.
השחקן השלישי מקבל X|A
השחקן הרביעי מקבל X|B
השחקן החמישי מקבל X|C
והשחקן הראשון מקבל X|A|B|C
אין לי את הזמן שנדרש לפתח את זה עד הסוף... אבל הרעיון הוא שהשחקנים הרמאים צריכים קואליציה של כולם על מנת לפצח את המספר.

אהבה זה נפלא אבל אי אפשר לאכול את זה. גלידה?

poetry lover - את בהחלט בכוון, יקירה.
אם יש N משתתפים, כל אחד צריך להטיל N-1 מטבעות (או להגריל ביטים רנדומיים).
עיבוד סופי יהיה לך קל לעשות. יש לזכור כי הפעולה ההופכית לXOR היא XOR עצמה שכן
a*b*b=a
אמרתי לך שאני מתה על הראש שלך?
אם לא, אז הנה: מתה עלייך.

האדון - יותר מתמיד
התשובה ידועה לך
כל היתר שעשוע.......
XOR אומר
A*B=AB
AB*A=B
AB*B=A

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