Рейтинг:5

ZKP: Докажите, что >18, скрывая возраст

флаг cn
deb

Я относительно новичок в криптографии, но некоторое время программировал. Вот история, которая хорошо описывает проблему, которую я пытаюсь решить:

У Алисы есть цифровой паспорт, подписанный закрытым ключом ее правительства. Каждое свойство подписывается отдельно, и все равно можно было бы проверить, например, что ее имя «Алиса», не говоря о том, что ее фамилия «Смит».

Отсюда, зная, что она может доказать, что ее дата рождения 05/04/1975, может ли она доказать, что ей больше 18 лет, не раскрывая при этом дату своего рождения и не обращаясь за помощью к третьей стороне?

Я предполагаю, что она не может, но я надеюсь, ты меня удивишь!

Eugene Styer avatar
флаг dz
Связанный: https://crypto.stackexchange.com/questions/19265/finding-out-the-greater-number-under-zero-knowledge-conditions
флаг ar
Также связано: https://crypto.stackexchange.com/questions/58349/zero-knowledge-proof-using-hash-chains-is-there-a-flaw-in-the-algorithm
Vadym Fedyukovych avatar
флаг in
Если вы не возражаете против снарков при проверке и следите за Золушкой https://antoine.delignat-lavaud.fr/doc/oakland16.pdf, есть шанс скрыть все содержание сертификата при доказывании утверждений о нем.
Рейтинг:7
флаг ar

AFAICT, нет, она не может сделать это, используя только информацию о ее паспорте, как вы ее описываете*, и рассматривая алгоритм цифровой подписи как черный ящик.

Однако, если правительство предусмотрело этот вариант использования и добавило немного больше информации в ее паспорт, является способ сделать это, например. метод хэш-цепочки, описанный в эта более ранняя ветка вопросов и ответов (на основе статья 2013 г., опубликованная Angel & Walfish).

В частности, Алисе нужно:

  1. Криптографическая хеш-функция, устойчивая к прообразам $Ч$ стандартизированы правительством. Что-то вроде ША-256 было бы хорошо.

  2. Секретный токен, выпущенный правительством $s$, вычислительно неотличимый от вывода $Ч$. (Например, $s$ может быть сгенерирован путем выбора случайной строки $г$ по крайней мере с таким количеством битов энтропии, как выходная длина $Ч$ и сдача $s = H(r)$.)

  3. Заявление, подписанное правительством, по форме:

    Алиса** родилась 01.01.2050 или ранее (решётка = $H^a(s)$).

    куда $а$ возраст Алисы в днях на 01.01.2050 и $H^a$ обозначает $Ч$ повторяющийся $а$ раз, т.е. $H^0(s) = s$ и $H^{n+1}(s) = H(H^n(s))$

Теперь, чтобы доказать Бобу, что ей в настоящее время (2021-11-24) 18 лет или больше, Алиса должна предоставить подписанное выше заявление вместе с $ч = H^b(s)$, куда $b$ возраст Алисы в днях ровно 18 лет назад (т. е. 24 ноября 2003 г.).

Затем Боб может вычислить $ Н ^ с (ч) $, куда $с = 16840$ — количество дней между 24.11.2003 и 01.01.2003, и сравните его с хешем в подписанном Алисой заявлении. Если утверждение Алисы верно, они должны совпадать, так как $а = б + с$, и поэтому $H^c(h) = H^c(H^b(s)) = H^a(s)$.

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


Обратите внимание, что для удобства вычислений и для смягчения атак по времени Алисе может быть желательно предварительно вычислить и сохранить $H^{b'}(s)$ для различных значений $b'$ соответствует, скажем, ее возрасту в днях в начале каждого года. Таким образом, ей нужно будет выполнить не более 365 хэш-оценок на месте, чтобы вычислить $H^b(s)$ для любой $b$.

Чтобы уменьшить вычислительные потребности Боба, может быть желательно, чтобы правительство выдавало Алисе несколько подписанных заявлений формы, приведенной выше, но с разными датами и соответствующими значениями. $а$, чтобы Алиса могла отправить Бобу подписанное заявление, скажем, на 01.01.2004 вместо 01.01.2050. Опять же, несколько тысяч оценок SHA-256 в наши дни тоже не так уж и много, и Бобу не нужно беспокоиться об атаках по сторонним каналам.

Однако выдача нескольких подписанных операторов также помогает сохранить свойство нулевого разглашения при наличии ролловера. Например, давайте представим, что правительство изначально выбрало 01.01.2030 в качестве фиксированной даты для подписанных заявлений, но затем несколько лет назад решило перенести ее на 2050 год, поскольку они начали выдавать паспорта, действительные до 2030 года и позже. Это означало бы, что, как минимум, Боб мог узнать из даты в заявлении Алисы, был ли ее паспорт выдан до или после перехода, что могло бы коррелировать с другой информацией, включая ее возраст. Предоставляя Алисе подписанные заявления для обе 01.01.2030 и 01.01.2050 (и, возможно, другие применимые даты), этой утечки можно избежать, поскольку Алиса может просто выбрать оператор с более ранней подходящей датой для запроса Боба (но не, очевидно, ранее даты она хочет доказать, что она родилась не позднее).


Пс. Как отмечено в мой ответ на вопрос по ссылке выше, тот же протокол можно использовать, чтобы позволить Алисе подтвердить свой точный возраст. Для этого Алисе нужно знать не просто $s = H(r)$ но и оригинальный случайный токен $г$, который должен быть выбран правительством таким образом, чтобы он был нет действительный вывод $Ч$.

Тогда, если Алиса хочет доказать Бобу, что она родилась 04.05.1975 и не ранее, она может раскрыть эту дату вместе с $г$ и по крайней мере одно подписанное заявление формы выше. Затем Боб может рассчитать заявленный возраст Алисы в днях. $а$ на дату, указанную в ведомости, рассчитать $H^a(s) = H^{a+1}(r)$ и сравните его с хешем в подписанном заявлении.

Конечно, с этим вариантом протокола Бобу также необходимо проверить формат $s$ или же $г$ токен, отправленный Алисой (т. е. что это действительный вывод $Ч$ для заявлений «родился во время или раньше» и нет действительный вывод $Ч$ для заявлений «рожденных в этот день»).

Тем не менее, в вашем сценарии отдельная государственная подпись «Алиса родилась 04.05.1975» также послужит этой цели.


Сноски:

*) Ваше описание того, что «каждое свойство подписывается отдельно», на самом деле немного проблематично, если принимать его за чистую монету, поскольку то, что правительство подписывает отдельное свойство, такое как «имя: Алиса», означает, что любой, кто видел подпись Алисы имя может сделать копию подписи и использовать ее, чтобы заявить, что их имя также Алиса. Кроме того, например, если бы у Элис Эндрюс и Боба Баркера были паспорта с такими отдельно подписанными именами и фамилиями, они могли бы объединить их, чтобы создать поддельный паспорт для «Элис Баркер» или «Боб Эндрюс».

Несколько лучшим решением было бы сделать одно из свойств в паспорте уникальным идентификатором и включить этот идентификатор во все подписанные свойства. Таким образом, например, кто-то, кто видел подписанное заявление вида «ID: #123456789; имя: Алиса», теперь может подтвердить, что у Алисы, имеющей паспорт с ID #123456789, действительно есть имя «Алиса», но они не могут использовать подпись, чтобы требовать кого-либо чужой имя будет Алиса.

Конечно, у этой схемы все еще есть свои недостатки: например, Алиса может захотеть иметь возможность доказать Бобу, что ее зовут Алиса. без Боб может доказать этот факт кому-либо еще. Осуществление такой отрицательная аутентификация схема выходит за рамки этого ответа, хотя вы можете посмотреть, например. этот более ранний.

**) Здесь я использую «Алису» вместо уникального государственного удостоверения личности Алисы, как описано в предыдущей сноске выше.

fgrieu avatar
флаг ng
Фундаментальная проблема: если какая-то штуковина может проверить, что Алисе сейчас ≥18 лет, взаимодействуя с ее паспортом, и паспорт не помнит о более ранних таких попытках, ничто не мешает этой штуковине найти дату рождения Алисы с помощью дихотомии. Даже если штуковина этого не сделает, до тех пор, пока ее понятие «сейчас» не защищено (например, есть способ установить часы по желанию), ею можно злоупотребить, чтобы найти дату рождения Алисы. Мы могли бы захотеть, чтобы сам паспорт проверял метку времени на свежесть, используя вызов/ответ, и удостоверял, что Алиса в настоящее время не является несовершеннолетней (18 не должно регулироваться, по крайней мере, точно).
флаг ar
@fgrieu: Верно. Я неявно предполагал, что (по крайней мере, часть) информации в паспорте Алисы, например. зашифровано ключом, хранящимся за пределами самого паспорта, чтобы она могла выбирать, какие части раскрывать. В противном случае другие части вопроса (например, отдельное подписание полей паспорта) не имеют для меня особого смысла.
Maarten Bodewes avatar
флаг in
В IEC 18013-5 (мобильное водительское удостоверение / mDL) элементы данных объединяются случайным образом, а затем хэшируются. Затем рандомизированные хэши объединяются и подписываются в MSO (разумеется, без случайных). Таким образом, вы можете проверить MSO и элемент данных. Вы должны дать разрешение в приложении, чтобы ответить на любой запрос данных. Вам может быть интересно, что в этом стандарте реализованы варианты использования > 18 и > 21 (он допускает два запроса, что означает, что вы можете определить, что кому-то от 18 до 21).
deb avatar
флаг cn
deb
Это отличный ответ, большое спасибо, что нашли время.
deb avatar
флаг cn
deb
Разве это решение не предполагает, что Алиса говорит правду о своем возрасте в первую очередь при генерации `Hb(s)`? Мне кажется, я не правильно это понял.
флаг ar
@deb: Ключевое наблюдение заключается в том, что Алиса не может сгенерировать $H^b(s)$ для отрицательного $b$ (по крайней мере, без дополнительной информации), поскольку для этого им потребуется найти прообраз $H^{-1}( s)$ для хеш-функции. Предполагая, что $H$ является безопасной [криптографической хеш-функцией] (https://en.wikipedia.org/wiki/Cryptographic_hash_function), это невозможно, поскольку устойчивость к прообразу является одним из их основных предположений безопасности.Если бы Алиса нашла способ вычислить прообразы, скажем, для SHA-256, они взломали бы хэш и могли бы мгновенно стать знаменитыми, независимо от их возраста.
флаг ar
@deb: Что касается вашего более раннего вопроса об отрицаемой аутентификации в этом контексте, то на самом деле это очень хороший вопрос, и у меня нет на него ответа. Я думал, что это *должно* быть каким-то образом возможно, когда писал ответ, но теперь, когда я больше об этом думаю, я не понимаю, как это сделать. Но, может быть, есть какой-то хитрый трюк ZKP, который я упускаю. Я мог бы задать отдельный вопрос об этом, если вы этого не сделаете.
deb avatar
флаг cn
deb
@IlmariKaronen: О, я думаю, что теперь я понимаю ваш ответ немного лучше (я читал его больше раз, чем мог бы признать, и все же я не уверен, все ли я понял правильно!). Я не привык к такому уровню криптографии, поэтому я подумаю об этом больше, когда у меня будет лист бумаги для записи... Если мы говорим о вопросе, как я его помню, я удалил комментарий, потому что я мог бы найти ответ. Я, вероятно, создам Q&A на сайте, я поделюсь ссылкой здесь.
deb avatar
флаг cn
deb
Это вопрос, который я сделал.По сравнению с ответом, который вы дали здесь, решение было довольно простым; мы говорили об одной и той же проблеме? https://crypto.stackexchange.com/q/97803/88017
deb avatar
флаг cn
deb
Хорошо: Месяц спустя я здесь, наконец, понимаю ваш ответ. Я могу только оценить умность этого ответа, большое спасибо.
Рейтинг:2
флаг es

Использование эллиптической кривой: паспорт может содержать отметку времени unix в качестве обязательства Педерсена в форме $C = bG + tH$, куда $b$ - скалярный ослепляющий фактор, $t$ дата рождения владельца паспорта в виде временной метки unix (секунды с начала эпохи) и $G$ и $Ч$ хорошо известные базовые точки, выбранные таким образом, что их дискретный логарифм относительно друг друга неизвестен и непознаваем.

$С$ подписывается правительством. Паспорт сообщает владельцу паспорта отметку времени и фактор ослепления.

Чтобы доказать, что владелец паспорта старше 18 лет, мы сначала вычисляем $s$ в качестве последней возможной отметки времени, когда владелец паспорта мог родиться, и в настоящее время ему исполнилось 18 лет или старше.

Владелец паспорта должен продемонстрировать, что $s>=t$. Мы можем сделать это, доказав, что $C' = sH - C == (s-t)H - bG$ является приверженность положительному числу. Из-за модульной арифметической природы EC-алгебры это означает, что мы должны гарантировать, что обязательство относится к относительно небольшому числу, а не к огромному числу, которое возникло бы в результате $s-t$ быть «отрицательным».

Чтобы достичь этого, нам нужно нечто, называемое доказательством диапазона.

Доказательство диапазона докажет, что $С'$ может быть построена последовательностью из 43 битов (что позволит схеме работать следующие 200 лет). Каждый «бит» будет либо нулем, либо степенью двойки.

Во-первых, мы объявим 43 обязательства Педерсена. $C_i$ для значений $я$ от 0 до 42 включительно, где каждое обязательство будет иметь свой ослепляющий фактор $b_i$ и каждое обязательство будет либо равно нулю, либо $2^i$.

Теперь нам нужно доказать, что $С'$ является обязательством того же числа, что и $\sum_{i=0}^{42} C_i$. Это можно сделать, вычислив открытый ключ $C'' = C' - \sum_{i=0}^{42} C_i$. Поскольку число, переданное $С'$ будет равняться сумме чисел, зафиксированных 43 обязательствами, результат будет иметь вид $C'' == b'G$ куда $b' == -b - \sum_{i=0}^{42} b_i$. Поэтому предоставление подписи на $С''$ используя закрытый ключ $b'$ докажет, что не может быть ненулевого $Ч$ компонент $С''$, потому что подпись с использованием базовой точки $G$ невозможно, если только дискретный логарифм $Ч$ w.r.t. $G$ известно (и $Ч$ был специально выбран таким, что он непознаваем).

Наконец, нам нужно доказать, что каждая из компонент $C_i$ являются либо обязательствами по сведению к нулю, либо обязательствами по $2^i$. Мы делаем это, предоставляя кольцевую подпись для каждого обязательства для двух открытых ключей. $(C_i - 0H, C_i - 2^iH)$. Кольцевая подпись будет возможна только в том случае, если одна из этих двух возможностей создает точку EC без $Ч$ компонента, тем самым доказывая, что $C_i$ является обязательством либо нуля, либо $2^i$.

В общем, мы доказали, что $s>=t$ потому что мы доказали это $sH-C$ является приверженность положительному числу. Мы доказали, что это положительное число, доказав, что его можно построить в виде последовательности из 43 битов, где каждый бит равен либо нулю, либо определенной степени числа 2.

deb avatar
флаг cn
deb
Боюсь, я недостаточно знаю об эллиптических кривых / «Обязательствах Педерсена», чтобы полностью понять ваш ответ, но я действительно ценю ваши усилия. Что такое скалярный коэффициент привязки?
knaccc avatar
флаг es
@deb Это просто случайное число, которое скрывает значение обязательства Педерсена. Если бы обязательство было просто $tH$, вы могли бы перебрать множество значений метки времени, чтобы узнать дату рождения владельца. Ослепляющий фактор заставляет обязательство выглядеть совершенно случайным и предотвращает его грубое принуждение. Я описал, как суммы скрыты в криптовалютах, таких как Monero, где доказательства диапазона используются, чтобы гарантировать, что кто-то не попытается создать сумму в блокчейне с отрицательным значением.

Ответить или комментировать

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