Ну и очередная задачка для пытливых умов.
Есть задача создать честную лотерею. Вот реально честную. У организатора нет задачи обмануть. Надо просто разыграть приз и получить 1000 рублей.
Т.е. 10 человек скидываются по 100 рублей и один из них получает приз. Как сделать так, что бы счастливчика и организатора никто не мог ни в чем заподозрить?

Еще раз. Лотерея должна быть честной и каждый участник мог это проконтролировать.

Для усложнения представим, что все это дело происходит в интернете.

GD Star Rating
loading...

41 Responses to Есть задача — создать честную лотерею

  1. Av:

    open source, независимая экспертиза, цифровые подписи, детальные логи.

  2. p77:

    Это да. И контроль честности md5.
    Чем может помочь open source и цифровые подписи?
    Кто будет независимым экспертом, который проверит детальные логи?

    Простой (логический, математический) способ нужен.

  3. Peels:

    Самое простое — довериться третьей стороне, которая сама все соберет, выберет победителя и даст результат. Если хочешь модняво и криптографично, то полезные ключевые слова тут: secure multiparty computation, secure coin–flipping и commitment scheme.

    Однако в таком случае критерий «честности» лотереи скорее всего нужно будет уточнить и усложнить. Например, я подозреваю что лотерею невозможно сделать «честной» если более половины участников сговорятся.

    Если ты, например, готов предположить что никто не сговаривается, что у всех есть возможность секьюрно ставить подписи и единственное что тебе надо гарантировать — это чтобы никто не смухлевал, то довольно простой результат можно получить, попросив каждого участника сгенерировать случайное число, зашифровать–подписать–послать. Собрать эти зашифрованные–подписанные числа, опубликовать на всеобщее обозрение, и выбрать номер победителя как сумма модуло 10.

  4. p77:

    3–я сторона — это уже человеческий фактор, а это возможность обмана.

    Мне видится что то с опубликованием произвольных чисел от каждого участника в открытый доступ. Тогда нам остается только указать «незапланированное» число, незапланированность которого каждый может проверить. Например — число статей в «Комсомольской правде Москва» за 15 февраля 2010 г.
    Кто ближе всех в этому числу — того и тапочки.

  5. Av:

    тогда уж проще можно. известно кол–во участников. каждый называет число и получает порядковый номер заявки. находим среднее арифметическое. побеждает участник, чей номер совпадает со средним арифметическим. для случаев, когда ничей номер не совпадает, придумать правила учета десятичных разрядов.

  6. Peels:

    Хотя тут не совсем прокатит. Нужно еще предполагать что никто не может вдруг «подменить» свой голос. Другая схема:

    1) Генерим пару секретный–публичный ключ для какой–либо гомоморфной криптосистемы, публичный ключ раздаем всем, секретный ключ превращаем в shared secret, такой что раскрыть его можно лишь когда соберутся все 10 вместе. Это можно сделать на доверенном компе, а может быть можно даже секьюрно организовать чисто математическими средствами.

    2) Каждый генерит случайное число, шифрует публичным ключем, публикует с подписью.

    3) Когда все 10 шифрованных чисел собраны, их складывают в шифрованном же виде ибо система гомоморфна. Полученную шифрованную сумму показывают каждому и собирают подпись что он ее видел. После этого все десятеро собирают обратно секретный ключ и раскрывают сумму. Победитель — это сумма по модулю 10.

    По идее здесь достаточно довериться вычислению в шаге 1 и предполагать что хотя бы один из 10 независимо от других генерит честное случайное число. Еще у последнего из тех, кто открывает shared secret есть возможность смухлевать (он увидит расшифровку первым и может не раскрывать свой ключ если он недоволен), но тогда все узнают что это он.

  7. Hanab:

    Розыгрыш проводится до раздачи номеров. Каждый получает запароленый архив, где выиграшный номер. А потом каждый выбирает себе номер. Когда номера все выбраны — озвучивается выигрышный номер и пароль на архив, для тех, кто сомневается.
    Так работают интернет–казино.

  8. Peels:

    В интернет–казино есть третья сторона, которой можно довериться. Иначе эта схема не очень хороша ибо если я сам генерю выигрышный номер, я сам же могу его и выбрать.

  9. p77:

    Как выбирается выигрышный номер? Веб–трансляция барабана с шариками?
    Если просто называется число, то с точки зрения участников организатор через подставного человека может выбрать себе выигрышное число.

  10. SLt:

    в качестве незапланированного числа можно использовать некую хэш–функцию, аргументами которой будут все 10 чисел.
    Главное тогда подобрать хэш функцию с равномерным распределением.

  11. Submulok:

    Тут на блоге как–то играли. 10 человек, у каждого цифра, скидываются. Потом ждут торгов на ММВБ, выигрышное число — четвертая цифра после запятой в курсе доллара на момент окончания торгов.

  12. SLt:

    есть вариант, что распределение четвертой цифры — неравномерное.

  13. p77:

    Да, это должно получится.
    Спаисбо.
    Пост закрыт?

  14. Peels:

    Ну если ты готов ждать до 15го февраля то да можно сразу в открытый доступ. А если ты хочешь результат «сразу» то это не прокатит (в том числе не прокатит с хеш функцией указанной снизу) ибо последний «публикующий» может подкрутить свой выбор так, чтобы он выиграл.

  15. Av:

    достаточно проанализировать статистику за год по частоте последних цифр

  16. p77:

    У последнего участника 100% шансы на выигрыш.

  17. p77:

    2, 3 цифра после запятой?

  18. Submulok:

    За год наверное мало будет. Но вот так, навскидку — не вижу причин какой–то цифре иметь больше шансов на выпадение.

  19. Av:

    во–первых, он не знает, что он последний. а во–вторых, числа хранятся в запароленых архивах и вскрываются после приема всех заявок.

  20. Submulok:

    Если хочется расширить — то лучше наверное другие цифры брать из других курсов. RUR/EUR, RUR/SEK… да мало ли валют. Вторую цифру после запятой уже как–то наверное прогнозировать можно, а вот последнюю — вряд ли.

  21. Peels:

    Хотя емае, все ж просто (я о случае, когда не надо ждать до 15 февраля).

    Каждый выбирает случайное число, считает на него комитмент (hash(n, rand())), публикует.
    После того, как все посмотрели на чужие комитменты, каждый раскрывает свое число. Победитель — сумма чисел модуло 10.

    Секьюрно при условии что хеш без коллизий и протокол обмена сообщениями честный (т.е. без подмен, тут можно какими–нить подписями заверить при необходимости).

  22. Peels:

    и да, это примерно то же самое, что уже упомянутый выше secure coin–flipping, только на десятерых.

  23. Av:

    зависит от количества участников

  24. Hanab:

    Согласен, здесь не сработает.
    В интернет казино ты играешь по сути один на один с крупье. Ты сначала получил запароленый выигрышный номер — потом сделал ставку. И выигрыш зависит только от твоей ставки.

  25. Peels:

    А, ну это все тот же классический secure coin flipping. Я вон внизу написал как его можно на десятерых делать.

  26. LeBig:

    1. * — участников. Каждый получает последовательный уникальный натуральный номер от 1 — до *.
    2. Каждый участник выбирает случайное число и считает какую нибудь, заранее известную, необратимую хеш–функцию.
    3. В назначенное время одновременно все публикуют свои хеши
    4. В назначенное время одновременно все публикуют свои случайные числа.
    5. Победитель — остаток суммы загаданных чисел от деления на *.

  27. Peels:

    Все так, но раз уж ты решил расписать детально по шагам, обрати внимание, что важна не необратимость хеша, а collision–resistance.

  28. LeBig:

    достаточно взять необратимую функцию, где наличие коллизий математически не доказано. Или нет известного мат аппарата позволяющего их генерировать.

  29. Peels:

    Ну необратимость функций тоже обычно «математически не доказана». И то, и другое — всего лишь предположения. И второе из них для данного протокола даже важнее чем первое (ибо если я найду пару чисел, которые дают один хеш, я могу начать мухлевать).

  30. LeBig:

    возможность мухлевать будет только у человека на четвёртом этапе, который будет открывать хеш последним. Если этот последний будет иметь пару чисел, то это увеличит его шанс выиграть в 2 раза. Но при достаточно большом *, это ему не сильно поможет.
    Если лотерея будет производится много раз тем же составом и ввести правило ротации «последнего», то у всех будет шанс смухлевать. Если действительно найдётся математик или программист, который найдёт или сбрутфорсит коллизию.

  31. Peels:

    Все так, только еще бывают коллизии, где * разных значений мапятся на один хэш. Ну и собственно протокол «опубликования» не так просто сделать убедительно секьюрным. Недостаточно же просто сказать «ребята, делаем вот так». Но этъятак, занудствую от нечегоделать.

  32. LeBig:

    ок. Дополнение. На третьем этапе каждый участник выкладывает не один, а Y хэшей. Полученных разными методами. И тогда возможность мухлежа катастрофически стремится к нулю.

  33. Peels:

    Не, с формальной точки зрения абсолютно не важно, будет ли твой комитмент коротким 64–битным md5 или же длиннющим многобитным из нескольких частей. Важно лишь то, чтобы он был убедительно необратимым и без коллизий.

    Кстати излишне длинный хэш — это тоже неоптимально, ибо тогда возрастают шансы его обратить.

  34. Kimos:

    а старый добрый вариант: собрать всех вместе, выдать бумажки, на которых они напишут имена, бумажки в шапку. чтобы исключить фактор судьи, вытаскивающего бумажки, можно простовысыпать их и выбрать «ближнюю к двери». не так мудрено, конечно, как запароленные архивы, торги на ММВБ и пр, но должно работать.

  35. LeBig:

    прочитай последнюю строчку условия задачи.

  36. Av:

    поле непаханое для наёбок

  37. Rumj:

    числа пишем прописью, например, «Сто пятнадцать» и шифруем открытым ключом.
    Рассылаем соперникам.
    После того как получили десять шифровок рассылаем подтверждение (подписанное) о получении всех шифровок.
    Когда получены 10 подтверждений рассылаем закрытый ключ.

  38. Peels:

    Да, сработает (это по сути та же схема что у ле коростеля и у меня выше). Но прописью писать не обязательно, а использовать ли хеш или шифрование для комитмента — без разницы, с хешем на практике проще.

  39. Rumj:

    ну пропись это чтобы коллизию было труднее подобрать. Одно дело когда обычное число изменить, а другое — вменяемый текст

  40. Peels:

    Когда шифруют (или же хешат) по любому не станут в качестве сообщения брать голую цифру или же ее текстовое представление, надо присыпать рандомными байтами. Иначе нередко (в частности с public–key crypto) перебором возможных сообщений можно по публичному ключу подобрать секретный.

Добавить комментарий