Paillier — это CPA-безопасный шифр, поэтому все, что мы можем вывести из зашифрованных текстов, требует закрытого ключа. Таким образом, «я хочу найти…» требует, чтобы «у меня» был закрытый ключ, а затем «у меня есть зашифрованный массив» подразумевает, что «я» могу расшифровать каждый из зашифрованных текстов, что делает поставленный вопрос спорным.
Поэтому мы изменим постановку задачи на: у нас есть не более $к$ небольшое целое число $m_i\in[0,\ell)$ (в рассматриваемой задаче мы хотим $k\ge6$, и $\ell>20$); и мы хотим, чтобы общедоступный метод выражал эти $m_i$ зашифрован как $c_i$ используя криптосистему Пайе, и объединить $c_i$ в один $с$ как у нас в Пайе. Это делает продукт по модулю $n$ принадлежащий $c_i$, и, возможно, умножить по модулю $n$ зашифрованным текстом для $0$ чтобы еще больше замаскировать результат. Мы хотим, чтобы человек, владеющий закрытым ключом, мог определить из $с$ если $0$ присутствовал в исходном наборе данных $m_i$. Это меняет две важные вещи в исходной постановке задачи:
- Есть такое понятие объединения зашифрованных текстов $c_i$ в $с$, с $c_i$ недоступен для владельца закрытого ключа.
- У нас нет «зашифрованного массива». Мы хотим иметь его, но можем свободно определять, как он будет сделан, если он использует шифрование, использующее Пайе. Без такой свободы решения нет, потому что расшифровка Пайе позволит получить только $m=(\sum m_i)\bmod n$ и нет никакого способа узнать из этого, если $m_i$ был $0$.
Вот то, о чем мы не только узнаем, если $0$ присутствовал в $m_i$, мы также узнаем, сколько раз каждое целое число в $[0,\ell)$ присутствовал в исходном массиве.
Для этого кодируем $m_i$ в $m'_i=(k+1)^{m_i}$ перед применением шифрования Пайе. Пайе позволит нам комбинировать зашифрованные тексты $c_i$ тогда расшифруй комбинацию $с$ в $m'=(\sum m'_i)\bmod n$. От $м'$ мы можем вывести, сколько раз каждое целое число в $[0,\ell)$ присутствовал в $m_i$, так долго как $к(к+1)^{\ell-1}<n$, выражая $м'$ в базе $к+1$ и глядя на цифры/конечности. Я пропущу алгебру о том, как это сделать, и воспользуюсь примером в десятичном виде (таким образом $к=9$). $m_0=2$, $m_1=4$, $m_2=5$, $m_3=10$, $m_4=0$, $m_5=20$ кодирует в $m'_0=100$, $m'_1=10000$, $m'_2=100000$, $m'_3=10000000000$, $m'_4=1$, $m'_5=0$, $m'_6=1000000000000000000000$ в десятичной системе. мы получим $m'=1000000000010000110101$, из чего мы можем сказать, что было ровно по одному каждому из $0$, $2$, $4$, $5$, $10$, $20$ в исходном массиве $m_i$, посмотрев на положение ненулевых цифр и увидев, что они $1$. Если $20$ был изменен на $0$, результат будет $m'=10000110102$ и мы бы знали, что было два $m_i=0$, потому что крайняя правая цифра $2$.
Вопрос не говорит о том, что мы не хотят, чтобы владелец закрытого ключа мог определить из $с$. Возможно, мы хотим ограничить это определением, было ли $0$, с минимальной утечкой о том, сколько $0$ насколько это возможно.
Для этого мы можем закодировать каждый $m_i\ne0$ к $m'_i=0$, и каждый $m_i=0$ к некоторому целому числу $m'_i$ в $[1,\lэтаж n/k\rэтаж)$ выбираются случайным образом с распределением, сильно смещенным в сторону низких значений. Когда расшифровка комбинации равна нулю, известно, что нуля в коде не было. $m_i$, и ничего больше. В противном случае известно, что был ноль, и утекло мало информации о том, сколько. Распределение может быть оптимизировано для минимизации этой утечки, это остается читателю в качестве упражнения.
Можно усовершенствовать вещи так, чтобы один с закрытым ключом и $c_i$ могу найти $m_i$, но (как указано выше) один с закрытым ключом и $с$ может получить мало информации о $m_i$, кроме этого $0$. Я не буду детализировать, потому что этого нет в постановке задачи.
Как и многие вещи с гомоморфным шифрованием, это хорошие теоретические системы с небольшим количеством проблем, с которыми можно столкнуться в реальной жизни.
