Алгоритм для секретного призначення дарувальників Secret Santa


Привіт, Хабр! У цій статті я наведу простий алгоритм, що дозволяє групі з N чоловік таємно згенерувати кожному з учасників групи номер іншого учасника — обдаровуваного — для обміну подарунками на Новий рік у заході Таємний Санта (Secret Santa).
Насамперед, що таке Таємний Санта? Стаття у Вікіпедії розповідає це краще за мене, я лише коротко скажу, що це церемонія, яка прийшла до нас із Заходу, в якій група людей сговаривается подарувати на Новий рік один одному подарунки таким чином, що кожен з учасників дарує і отримує по одному подарунку, при цьому кожному не відомий його дарувальник, але відомий обдаровуваний (звідси "таємний Санта"). Вартість подарунків зазвичай обумовлюється заздалегідь, щоб усі подарунки були приблизно рівноцінні. При бажанні можна умовитися, що після того, як обмін подарунками відбудеться, дарувальники розкриються.
Свій "Таємний Санта" є і на Хабрахабре під назвою "Клуб Анонімних Дідів Морозів".
На жаль, для організації Таємного Санти просто згенерувати список пар дарувальник-обдаровуваний недостатньо. Дарування має відбуватися анонімно, і кожен учасник повинен знати тільки номер обдаровуваного і ні бітом більше інформації про інших учасників, тому, наприклад, не можна просто доручити одному з учасників згенерувати список і повідомити кожного залишився учаснику його обдаровуваного — той, хто створив список, буде знати все про всіх, в тому числі і свого дарувальника.
Як правило, учасники виходять з положення, вдаючись до допомоги "третьої сторони" — незацікавленого людини, не бере участь у церемонії, якого просять згенерувати номери обдаровуваних і таємно повідомити кожному учаснику єдиний номер. Такий "третьою стороною" може бути не тільки людина, але й спеціалізований сайт, до числа яких належить і вже згаданий "Клуб АДМ" Хабрахабра.
Якщо ж поставити умову децентралізованності (відсутності "третьої сторони"),
то "Таємний Санта" перетворюється на цікаву з точки зору криптографії завдання, досить добре вивчену і неодноразово вирішеної: ось приклад математичної моделі Таємного Санти, а от конкретний алгоритм розв'язання, де учасники для забезпечення приховування даних використовують асиметричне шифрування.
У даній статті я опишу ще один такий алгоритм. Його невелику перевагу перед іншими методами з області хардкорного криптографії в тому, що він дуже простий у виконанні: все, що треба робити учасникам, — це записувати набори натуральних чисел, а також викреслювати з них окремі елементи і вписувати нові.
Як і інші децентралізовані алгоритми для Таємного Санти, цей алгоритм не вимагає "третьої сторони" — учасникам достатньо тільки спілкуватися між собою. Все, що потрібно кожному учаснику, — це двічі отримати від учасника з попереднім номером набір натуральних чисел, змінити його певним чином і передати наступному. Після того, як обмін наборами завершиться, кожен учасник певним чином формує з наявних у нього наборів єдине натуральне число — номер обдаровуваного.
Відразу скажу, у такого підходу не дуже багато переваг порівняно з тим, щоб просто привернути "третю сторону", але пара плюсів все-таки є:
  • Це просто весело пограти на НГ в "Таємного Санту" з криптографією. Добре підійде компанії гиків.
  • Не потрібно шукати людину зі сторони, організовувати його спілкування з кожним з учасників.
  • Не потрібно реєструватися ні на якому сайті, потрібні тільки самі учасники і мінімум технічних засобів спілкування звичайним текстом. При фізичному зустрічі учасників не потрібно нічого, крім ручки і паперу. Для спілкування на відстані підійде що завгодно — електронна пошта, SMS, IRC...
Опис алгоритму
Для початку, невелику угоду про те, як представляти конкретний набір, сопоставляющий дарувальників і обдаровуваних, з математичної точки зору.
Призначення обдаровуваних в Таємному Санте — не що інше, як призначення кожного з учасників групи з N осіб номери від 1 до N, означає номер обдаровуваного (якщо вважати, що всі учасники пронумеровані від 1 до N). При цьому:
  • Нікому не повинен дістатися свій власний номер (тк не можна дарувати самому собі);
  • Не повинно бути номерів, нікому не дісталися (тк всі повинні бути обдаровані);
  • Номер кожного учасника дістається рівно одному дарувальнику (тк кожен повинен отримати рівне 1 подарунок).
  • Двом учасникам може випасти дарувати подарунки один одному в принципі, це абсолютно нормально, але іноді учасники можуть домовитися перекидати жереб в цьому випадку.
  • На номери можуть накладатися інші додаткові обмеження залежно від ситуації (наприклад, якщо в "Санте" беруть участь кілька сімей, вони можуть домовитися перекидати жереб, якщо комусь з учасників випало робити подарунок члену своєї сім'ї).
Звідси видно, що будь-список пар дарувальник-обдаровуваний для Secret Santa можна представити у вигляді послідовності з N чисел (на i-му місці записується номер того, кому дарує подарунок i-ий учасник), що представляє собою перестановку порядку N без нерухомих точок.
Перший етап алгоритму
Отже, кожному учаснику призначається номер від 1 до N, наприклад в алфавітному порядку імен. Ця інформація є відкритою і повідомляється всім учасникам.
Потім перший учасник випадковим чином створює великий набір (потрібно не менше 2N) натуральних чисел так, що ніякі 2 з них не збігаються. Цей набір спочатку не повідомляється нікому. Перший учасник записує ці числа для зручності в порядку зростання, вибирає собі будь-яке одне з них випадковим чином, видаляє вибране число з набору і передає залишився набір другому учаснику. В результаті у першого учасника виявляються записаними 2 речі: стартовий набір чисел і обраний ним число.
Наведемо приклад з 5 учасниками.
Перший учасник генерує початковий набір: 3, 46, 50, 89, 94, 95, 101, 500, 783, 5003, 5765, 7003
Вибрано: 783
Передається другому учаснику: 3, 46, 50, 89, 94, 95, 101, 500, 5003, 5765, 7003
Другий учасник точно так же вибирає собі з набору довільне число, видаляє його з набору і передає залишився набір наступному учаснику. Так само поступають 3-ій, 4-ий і 5-ий учасник. П'ятий, останній, учасник вибирає собі число, але нікому нічого поки не передає.
Продовжимо приклад:
Другий учасник отримує (повторимо ще раз): 3, 46, 50, 89, 94, 95, 101, 500, 5003, 5765, 7003
Другий учасник вибирає: 3
Третій учасник отримує: 46, 50, 89, 94, 95, 101, 500, 5003, 5765, 7003
Третій учасник вибирає: 94
Четвертий учасник отримує: 46, 50, 89, 95, 101, 500, 5003, 5765, 7003
Четвертий учасник вибирає: 5765
П'ятий учасник отримує: 46, 50, 89, 95, 101, 500, 5003, 7003
П'ятий учасник вибирає: 101
Залишок набору: 46, 50, 89, 95, 500, 5003, 7003
На цьому перший етап алгоритму закінчено. Коментар: в результаті у кожного з учасників є число, не відоме всім іншим (точніше, кожному учаснику відомий великий набір чисел, про який він знає, що наступні учасники обирали своє число з нього — але це не дає ніякої інформації, що дозволяє точно дізнатися чужі числа). Якщо ми тепер знайдемо спосіб якось повідомити весь набір вибраних чисел кожного з учасників, то завдання призначення дарувальників буде вирішена: кожному учаснику достатньо взяти за кінцевий результат порядковий номер обраного ним числа в цьому наборі вибраних номерів.
Припустимо, що ми вже знайшли спосіб повідомити кожного набір обраних номерів (взагалі ми це зробимо на 2-му етапі алгоритму) та учасники дізнались номери своїх обдаровуваних. Проблема в тому, що одному або більше учасникам можуть випасти їх власні номери, що робить весь підсумковий результат некоректним. Це великий мінус алгоритму, так як ймовірність потрапити в цю ситуацію досить висока, хоча вона і падає з ростом N. Виходів як мінімум 2:
  • Учасник, який отримав свій власний номер, запитує у всіх перекидання жеребу з початку. Цю процедуру потрібно повторювати, поки все не підтвердять, що їм дістався коректний номер.
  • Учасник, який отримав свій власний номер, запитує у всіх застосування до підсумковими результатами випадкової перестановки без нерухомих точок. Ця перестановка генерується відкрито і повідомляється всім учасникам. Кожен учасник повинен застосувати цю перестановку номер свого обдаровуваного. Цю процедуру потрібно повторювати, поки все не підтвердять, що їм дістався коректний номер. Цей спосіб підходить тільки при фізичному зустрічі, так як при дистанційному спілкуванні неможливо гарантувати випадковість перестановки (той, кому задано згенерувати перестановку, приміром, може безперешкодно згенерувати перестановку перекладом його номер обдаровуваного в будь-який інший номер обдаровуваного за його бажанням).
У прикладі з 5 учасниками от як будуть виглядати обрані номери:
1-ий учасник вибрав (повторимо ще раз): 783
2-ий учасник вибрав (повторимо ще раз): 3
3-ий учасник вибрав (повторимо ще раз): 94
4-ий учасник вибрав (повторимо ще раз): 5765
5-ий учасник вибрав (повторимо ще раз): 101
Список обраних номерів у порядку зростання (повторюся — припустимо, що ми знаємо, як таємно повідомити його всім учасникам): 3 94 101 783 5765
Разом, номери обдаровуваних:
1-ий учасник: вибрав 783, набір 3 94 101 783 5765 — номер обдаровуваного 4
2-ий учасник: вибрав 3, набір 3 94 101 783 5765 — номер обдаровуваного 1
3-ий учасник: вибрав 94, набір 3 94 101 783 5765 — номер обдаровуваного 2
4-ий учасник: вибрав 5765, набір 3 94 101 783 5765 — номер обдаровуваного 5
5-ий учасник: вибрав 101, набір 3 94 101 783 5765 — номер обдаровуваного 3
Перекидання не потрібно.
Другий етап алгоритму
Отже, як же повідомити всім набір "виділених" номерів? Це завдання другого етапу. Дізнатися цей набір може перший учасник, якщо останній учасник повідомить йому залишився в кінці набір (в прикладі це 46, 50, 89, 95, 500, 5003, 7003). Першому учаснику тоді досить виключити цей набір із стартового, і результат виключення буде потрібним набором обраних учасниками чисел. Зауважимо, що перший учасник при такій дії все ще не знає ніякої інформації, що дозволяє йому розкрити номери, що дісталися іншим учасникам.
На жаль, просто взяти і повідомити обчислений набір далі по ланцюжку можна — хоча б тому, що передостанній учасник цієї інформації миттєво визначить номер, обраний останнім учасником, а значить і впізнає його обдаровуваного.
Рішення у цієї проблеми наступне. Як вже сказано, останній учасник передає першому самий останній залишився набір. У першого учасника виявляються наступні дані:
Стартовий набір: 3, 46, 50, 89, 94, 95, 101, 500, 783, 5003, 5765, 7003
Вибрано число: 783
Останній залишок набору: 46, 50, 89, 95, 500, 5003, 7003
Перший учасник обчислює, як вже сказано вище, набір обраних усіма учасниками чисел: 3, 94, 101, 783, 5765 і дізнається, що випав йому номер обдаровуваного — 4.
Тепер, починаючи з цього моменту, кожен учасник, починаючи з першого, буде повідомляти следущему учаснику набір з N чисел. Кожен, отримав такий набір, повинен вважати його набором вибраних усіма учасниками номерів і відповідно обчислити номер свого обдаровуваного. Але на кожному кроці передаватися далі буде не оригінальний набір обраних номерів, а змінений, але дає той же результат обчислення номери обдаровуваного, що і оригінальний. При цьому змінений набір виключить будь-яку можливість дізнатися вибрані іншими числа.
Для складання такого зміненого набору учасник повинен взяти отриманий ним від попереднього учасника набір (у разі першого учасника — набір, обчислений як сказано вище) і замінити в ньому своє число (вибране на 1ом етапі) на будь-яке інше число дістався йому на 1-му етапі набору, з наступними обмеженнями:
  • Замінене число не повинне входити в тільки що отриманий від попереднього учасника набір;
  • Замінене число повинно мати той же порядковий номер у зміненому наборі, що і замінити число в оригінальному наборі.
У прикладі перший учасник підміняє в наборі 3, 94, 101, 783, 5765 вибране ним число — 783. Числа, які йому дозволено підставити замість 783, — це 500 і 5003. Припустимо, він вибрав підміну 783 на 5003 і передає другому учаснику набір 3, 94, 101, 5003, 5765.
Інші учасники роблять те ж саме. Доведемо приклад до кінця.
Другий учасник:
Набір на 1ом етапі— 3, 46, 50, 89, 94, 95, 101, 500, 5003, 5765, 7003
Вибране число — 3
Набір на 2-му етапі— 3, 94, 101, 5003, 5765
Можна підставити замість 3 — 46, 50, 89
Вибираємо підставити 50, передаємо далі набір 50, 94, 101, 5003, 5765
Третій учасник:
Набір на 1ом етапі— 46, 50, 89, 94, 95, 101, 500, 5003, 5765, 7003
Вибране число — 94
Набір на 2-му етапі— 50, 94, 101, 5003, 5765
Можна підставити замість 94 — 89, 95
Вибираємо підставити 89, передаємо далі набір 50, 89, 101, 5003, 5765
Четвертий учасник:
Набір на 1ом етапі— 46, 50, 89, 95, 101, 500, 5003, 5765, 7003
Вибране число — 5765
Набір на 2-му етапі— 50, 89, 101, 5003, 5765
Можна підставити замість 5765 — 7003
Вибираємо підставити 7003 (альтернатив особливо немає), передаємо далі набір 50, 89, 101, 5003, 7003
П'ятий учасник:
Набір на 1ом етапі— 46, 50, 89, 95, 101, 500, 5003, 7003
Вибране число — 101
Набір на 2-му етапі— 50, 89, 101, 5003, 7003
Обмін наборами закінчено, учасники можуть зайнятися обчисленням номери обдаровуваного.
Можна впевнитися, що ніхто з учасників при такому підході не може дізнатися нічого про чужих номерах.
Все, алгоритм завершений. Навскидку я бачу в ньому ще 2 нестачі, крім згаданих вище частих перекидів через шанс випадання учаснику свого власного номера:
  • Випадковість вибору учасником числа з набору ніяк не гарантується. Ніхто не заважає першому учаснику, наприклад, вибрати останнє число в наборі і тим самим практично забезпечити собі номер обдаровуваного, рівний N. Ця проблема усувається, якщо, як вже сказано, учасники домовляться в самому кінці алгоритму додатково застосувати до результатів відому всім випадкову перестановку без нерухомих точок, але її випадковість теж потрібно якось гарантувати.
  • Алгоритм не вміє створювати ніякі додаткові обмеження на номери обдаровуваних (наприклад, заборона будь-2 учасникам або певним 2 учасникам взаємно робити подарунок один одному).
дякую Всім, хто дочитав до кінця, і з наступаючим Новим роком :) Печеньку тому, хто знайде ще проблеми в алгоритмі або вирішить існуючі!
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.