Рейтинг:0

Как доказать знание секрета и разрешить получателю его дедупликацию?

флаг ug

Рассмотрим следующий сценарий:

У нас есть два агента, А и Б.

Б должны доказать, что они знают секрет А, не раскрывая фактического секрета.

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

Думайте об этом, как о том, чтобы поделиться хэшем этого секрета, кроме: это очень маленький источник с низкой энтропией (около 1 миллиарда возможных значений). Это означает, что простой хэш будет уязвим для атаки по словарю.

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

Однако давайте теперь представим третьего агента, С. С отправляет одинаковые секреты на А. Б и С не могут делиться своими секретами друг с другом.

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

А, конечно, теперь нужно дедуплицировать не только секреты из Б, но и от С.

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

Может А, Б и С прийти к соглашению, где Б и С могут поделиться своими "доказательствами" с А, таким образом, что А можно их дедуплицировать, но никто не может раскрыть секреты друг друга?

Если да, то можно ли обобщить это на любое количество потребителей/производителей?

Будучи далеко не экспертом в криптографии (я действительно знаю только самые основы), я не уверен, что использую здесь правильные термины. Дайте мне знать, если я могу прояснить что-либо из этого. Кроме того, это не домашнее задание или что-то в этом роде — хотя оно было мотивировано конкретной проблемой, которую я недавно прочитал, это в основном просто любопытство. Грубое объяснение того, почему это невозможно (в случае, если это не так), для меня определенно было бы достаточно. То же самое для краткого описания известного алгоритма, хотя бы просто названия - при правильном направлении я могу провести исследование самостоятельно.

(Просто чтобы было ясно, если это уже не так: А, Б и С не доверяйте друг другу)

(Надуманный) пример

Алиса и Боб хотят продать марки коллекционеру. Думайте о марке как о строке из 7 символов, состоящей только из символов нижнего регистра, и коллекционер марок не может просто изготовить их самостоятельно.

Коллекционер марок купит любую марку, которой у него в данный момент нет. Однако он не купит марку сразу: он подождет, пока увидит, у скольких продавцов она есть, чтобы купить марку по самой низкой цене.

Таким образом, прежде чем отправить настоящую марку, Алиса (или Боб) должны отправить «предложение» коллекционеру, чтобы он мог проверить, есть ли у них уже марка или ее предложил кто-то другой. Они не могут отправить настоящую марку с таким предложением, иначе коллекционер просто получит ее бесплатно, что никому не доставляет удовольствия. Коллекционер должен знать, на какую марку сделана ставка, даже если он не знает фактическую строку из 7 символов, иначе он не сможет сравнить ставки.

knaccc avatar
флаг es
B и C должны будут довериться A, потому что A сможет раскрыть информацию B или C, если B и C поделятся какими-либо дубликатами друг с другом. Если B совместно использует одно значение за раз с A, B может быть проинформирован A, как только A заметит, что конкретное значение используется C. Возможно, если вы объясните конкретную проблему, вам будет легче полностью понять ограничения доверия.
Cássio Renan avatar
флаг ug
B или C вообще не могут доверять A или друг другу. Я не уверен, что (однажды) конкретная проблема добавит что-нибудь TBH. Как я уже сказал, это мотивировало вопрос, но на самом деле это не та проблема, которую я пытаюсь решить или о которой думаю.
knaccc avatar
флаг es
Вы говорите, что требование состоит в том, что A не сможет вступить в сговор с B, чтобы сообщить B, какое из ослепленных значений B имеет общее с C? Таким образом, для B не должно быть возможности отправлять ослепленные значения A одно за другим, чтобы A мог сообщить B, как только будет обнаружен дубликат? Вы также говорите, что дальнейшие «агенты» не должны иметь возможности участвовать без разрешения всех существующих агентов, чтобы предотвратить вариант такого сговора?
kelalaka avatar
флаг in
Вы ищете [конвергентное шифрование] (https://crypto.stackexchange.com/q/729/18298)?
Cássio Renan avatar
флаг ug
@knaccc нет, это не требование. Теоретически B и C даже не знают друг о друге (они общаются только с A и ни с кем другим).
Cássio Renan avatar
флаг ug
@kelalaka Из принятого ответа кажется, что одно из требований состоит в том, чтобы «файл», который нужно зашифровать, был достаточно длинным. Одним из ограничений этого вопроса является то, что секрет небольшой (в противном случае было бы достаточно хорошего хеша секрета, так как атаки по словарю больше не были бы проблемой)
Cássio Renan avatar
флаг ug
Из моего последнего комментария я предполагаю, что «доказательство» не является хорошим описанием. Поскольку мне все равно, отправит ли один «агент» «поддельный» хэш в A, поэтому меня действительно интересует не доказательство, а скорее некоторые форме, если уникальная идентификация/токен. Я постараюсь придумать лучший термин и улучшить вопрос.
Cássio Renan avatar
флаг ug
@knaccc Я добавил пример, думаю, он хорошо описывает ограничения. Дай мне знать, если это работает!
knaccc avatar
флаг es
Если неограниченное количество агентов может связываться с A без одобрения любого существующего агента, тогда A может участвовать в качестве агента и проверять все возможные комбинации, чтобы увидеть, не предложил ли какой-либо другой агент этот секрет. Поэтому вам потребуется механизм для ограничения количества предметов, которые агенты могут предложить А, где каждый агент обязуется и будет готов объявить свой слепой список только в то время, когда доказуемо ограниченное число других агентов предлагая доказуемо ограниченное количество предложений. Поскольку вы не указали фактический вариант использования, я понятия не имею, будет ли это приемлемым или нет.
Cássio Renan avatar
флаг ug
Нет, я думаю, что вы поставили очень хорошую точку здесь. Моя первоначальная мысль была: «Зачем А проверять это на себе? Теоретически они уже знают, что предлагали другие агенты, даже если они не знают секрета», но потом меня осенило: любая подобная договоренность должна позволить А просто грубая сила, как вы описываете, и в любом случае есть секреты.
Cássio Renan avatar
флаг ug
В примере с марками коллекционер может просто «продать» себе все возможные марки, а затем он будет знать каждую марку других продавцов, злоупотребляя механизмом дедупликации. Думаю, это мой ответ.
knaccc avatar
флаг es
Существует способ, с помощью которого А может проверить у каждого агента, есть ли у каждого агента что-то, чего еще нет у А. Это может быть сделано без раскрытия агентом того, какие секреты есть у A, и без раскрытия агентом каких-либо секретов, которые у него есть (кроме тех, которые уже есть у A). Агент может ограничить количество элементов, которые проверяет A, чтобы избежать перебора.К сожалению, это не позволяет A видеть, есть ли у нескольких агентов один и тот же секрет, которого нет у A.
Cássio Renan avatar
флаг ug
Нет, это не сработает в сценарии, о котором я думаю. Подумайте об «А» или о коллекционере марок, как если бы это был API, в который попали другие. Не может быть наоборот. В любом случае, после вашего последнего комментария я вполне уверен, что договоренность по своей природе просто не может обеспечить гарантию секретности «штампов» вместе с механизмом дедупликации. Большое спасибо, сэр!
Cássio Renan avatar
флаг ug
Или, другими словами, «сохранение штампов в секрете» и «возможность дедупликации штампов из разных источников» являются противоречивыми требованиями, когда количество возможных штампов достаточно мало для грубой силы.

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

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