Что такое безопасная, современная, частично гомоморфная схема шифрования?

я читал Эта бумага Филиппом Голлем об использовании гомоморфных свойств шифрования Эль-Гамаля для игры в ментальный покер (то есть криптографически безопасный покер без доверенного стороннего дилера). Я решил, что было бы неплохо попытаться реализовать какую-то базовую версию, но быстро столкнулся с некоторыми проблемами.

Похоже, что ElGamal (и, если на то пошло, RSA) в целом считаются небезопасными, и, по-видимому, преобладает совет избегать их. Таким образом, два больших варианта падения частичного гомоморфизма не учитываются в играх с достаточно высокими ставками. Кроме того, я не смог найти других стандартизированных криптосистем, обладающих этим свойством и работающих с дискретными значениями, а не с аппроксимациями (необходимыми для реализации алгоритма, изложенного в статье). Я упускаю что-то очевидное?

Я предполагаю, что мой вопрос: если бы Голле писал эту статью в 2022 году, что бы он предложил вместо Эль-Гамаля для игр в покер с достаточно высокими ставками?

ElGamal и RSA «считаются в целом небезопасными» ЕСЛИ предполагается Криптографически значимые квантовые компьютеры. Но они остаются весьма гипотетическими. Мир (интернет, банковское дело, мобильная связь...) в настоящее время работает на криптосистемах, которые, будучи асимметричными, теоретически уязвимы для этих гипотетических CRQC: RSA, ECDSA, EdDSA, ECIES…

Криптосистема Пайе заслуживает внимания, если игнорировать гипотезу CRQC. Это просто¹, обеспечивает аддитивное гомоморфное шифрование (возможно, со знаком) целых чисел с небольшим и четким ограничением², имеет эффективность в пределах небольшого постоянного коэффициента дешифрования RSA (таким образом, терпимо во многих приложениях), не имеет патентов, доказуемо сводится к математической задаче широко распространено мнение, что он является суперполиномиальным для классических компьютеров и считается таким же безопасным, как RSA, при том же простом размере.

Основная причина, по которой криптосистема Пайе мало используется на практике, заключается, как мне кажется, в том, что гомоморфное шифрование в целом не пользуется большим спросом.

Дополнение: шифрование Пайе не уязвимо для атаки оракула заполнения или неправильного выбора заполнения, поскольку (в отличие от RSA) оно не требует заполнения. Он уязвим для атак на реализацию примерно так же, как и RSA, включая использование некачественных генераторов случайных чисел при генерации или использовании ключа, побочных каналов и атак с ошибкой. Сходство с RSA — хорошая новость, поскольку для RSA известны эффективные меры противодействия атакам, которые в значительной степени могут быть адаптированы к Пайе.

¹ Особенно с общим ограничением $n$ произведение двух простых чисел одинакового размера, и $г=n+1$.

² Открытый текст, превышающий $n$ уменьшается по модулю $n$, с $n$ общедоступные параметры достаточно велики, и это не проблема для чего-либо, что можно сосчитать, включая любую значимую часть валюты, даже атомы. Контрастом будет аддитивно гомоморфный вариант Эль-Гамаля, который имеет строгие ограничения на целые числа, которые он может складывать.

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

1. аддитивный гомоморфизм,

2. "модульное сравнение открытого текста", например. проверка если $Enc(с)$ является шифрованием 0,

3. протокол распределенной генерации ключей.

было бы легче ответить на этот вопрос, если бы вы могли точно формализовать, какие операции/свойства вам нужны.

на основе решетки

При всем при этом наиболее распространенным типом частично гомоморфной схемы шифрования в настоящее время являются варианты шифрования R (LWE). Однако это удовлетворяет «зашумленному» варианту аддитивного гомоморфизма, а это означает, что можно оценить только некоторые априори ограниченный число аддитивных гомоморфизмов. Если нужны произвольные дополнения, то и это можно сделать, например схемы FHEW/TFHE для этого, пожалуй, хорошо подходят (обратите внимание, что это полностью гомоморфный схемы шифрования, хотя они особенно эффективны). Это правдоподобно/вероятно, в вашем случае это нормально.

Для двух других пунктов мне нужно было бы более внимательно прочитать/знать точные требования схемы. Мне кажется правдоподобным, что схемы шифрования на основе RLWE могли бы работать в вашей ситуации, но я не пытаюсь заполнять подробности, потому что...

Эль-Гамаль на базе:

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

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