Приложения доказательств с нулевым разглашением

Вопрос. Какие есть аппликации которые работают с использованием протокола с нулевым разглашением.

Ответ. Если под приложениями понимаются криптографические схемы, имеющие практическую реализацию, то, по-видимому, таковых нет. Можно было ожидать применения интерактивных доказательств с нулевым разглашением в качестве протоколов интерактивной аутентификации. Но, как известно, для нулевого разглашения необходимо минимум 4 раунда. Поэтому разработчики протоколов аутентификации вынуждены жертвовать обоснованием стойкости в пользу эффективности.

В математической криптографии доказательства с нулевым разглашением используются в качестве примитивных протоколов при построении более сложных криптографических протоколов. Такие примеры многочисленны. Некоторые из них:

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

Вопрос. Рассматриваются ли в математической криптографии вопросы, связанные с биометрией?

Ответ. Да, разумеется, такие исследования проводятся.

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

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

В работе [DORS] для решения этих проблем были предложены два новых, весьма любопытных криптографических примитива: стойкие скетчи (secure sketch) и пушистые экстракторы (нечеткие экстракторы — fuzzy extractors).

Биометрические данные $w$ полагаются элементами некоторого метрического пространства.

Стойкий скетч — пара эффективных вероятностных алгоритмов $(SS, Rec)$. Алгоритм $SS$ на входе $w$ выдает битовую строку $s$. Алгоритм $Rec$ получает на вход строку $s$ и элемент $w’$, который по метрике близок к $w$, и выдает $w$. Основное криптографическое требование к скетчу таково: знание строки $s$ не приводит к существенным потерям энтропии элемента $w$.

Пушистый экстрактор — пара эффективных вероятностных алгоритмов $(Gen, Rep)$. На входе $w$ алгоритм $Gen$ выдает пару строк $(R,P)$. Алгоритм $Rep$ получает на вход строку $P$ и элемент $w’$, который по метрике близок к $w$, и выдает $R$. Основное криптографическое требование гласит: строка $R$ имеет квазиравномерное распределение (даже при известной строке $P$).

В связи с этими двумя примитивами остается ещё множество нерешенных вопросов, но в литературе уже обсуждаются возможные приложения, в том числе и следующее, весьма неожиданное. Вам предоставляется возможность выбрать в качестве $w$, скажем, список любимых произведений искусства, создать с помощью пушистого экстрактора пару $(R,P)$, зашифровать на ключе $R$ номер своего телефона и опубликовать криптограмму вместе со строкой $P$. Вероятно, Вам позвонит родственная душа.

Литература

  • [DORS] Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, Adam Smith «Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data», SIAM J. Comput. 38(1): 97-139 (2008) / EUROCRYPT 2004 / IACR eprint archive 2003/235
Хэш функции: вопрос о терминах

Вопрос. Что такое free-start collision и semi-free-start collision?

Ответ. И тот и другой термин не являются устоявшимися. Разные авторы понимают под этими терминами разные объекты, причем существенно разные. Поэтому для точного ответа на этот вопрос требуется контекст.

Протоколы обмена секретами

Вопрос. Подскажите, пожалуйста, примеры протокола обмена секретами.

Ответ. Хороший, интересный вопрос, который оказался самым трудным за всю историю сайта, включая его (сайта) предыдущую версию.

Протоколы обмена секретами (exchange of secrets) — один из первых типов криптографических протоколов, с которых математическая криптография начиналась как наука. Но литература, посвященная данному типу протоколов крайне скудна, а основополагающие работы были опубликованы в начале 80-х и труднодоступны. Кроме того, поиск литературы по данной теме весьма непрост, поскольку многие авторы не различают два типа протоколов: протоколы обмена секретами и протоколы генерации секретных ключей (secret key exchange).

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

Мы подготовили по данной теме некоторый материал, который размещен в разделе Лекторий. Насколько его можно считать ответом на поставленный вопрос — судить Вам.

Протоколы неинтерактивных доказательств

Вопрос. Существует ли протокол неинтерактивного доказательства?

Ответ. Видимо, речь идет о протоколах интерактивного доказательства.

Заметим, что здесь присутствует некая терминологическая несуразность: неинтерактивный протокол — частный случай интерактивного, выполняемый за один раунд (посылка одного сообщения от доказывающего проверяющему).

Неинтерактивные протоколы доказательства, очевидно, существуют. Просто из определений следует, что такие доказательства существуют для всех языков из классов NP и BPP.

Более интересен вопрос о неинтерактивных доказательствах с нулевым разглашением. Здесь имеется весьма сильный отрицательный результат. Орен [1] доказал, что если для данного языка существует двухраундовый протокол доказательства с нулевым разглашением, то этот язык принадлежит классу BPP.

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

Известны две расширенные модели, в которых можно определить понятие неинтерактивного доказательства с нулевым разглашением.

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

В модели с предобработкой (preprocessing), предложенной де Сантисом и др. [3], взаимодействие доказывающего и проверяющего делится на два этапа. На первом этапе (предобработка) участники выполняют специальный интерактивный протокол, результаты которого используются на втором этапе, который и представляет собой собственно неинтерактивное доказательство. Этот вариант доказательства становится нетривиальным, если, например, потребовать независимость этапа предобработки от доказываемого утверждения. Более того, установлено, что при некоторых предположениях существуют протоколы, позволяющие после однократного выполнения этапа предобработки выполнять полиномиальное (от параметра стойкости) количество неинтерактивных доказательств.

Исследование неинтерактивных доказательств во многом повторяло изучение общего случая: были определены понятия вычислительно, статистически и абсолютно нулевого разглашения, понятия доказательства знания и т.д. Cуществование неинтерактивных доказательств с нулевым разглашением для всего класса NP было изначально установлено в обеих моделях исходя из теоретико-числовых предположений. В дальнейшем эти результаты были усилены: оказалось, что достаточно общих криптографических предположений (о существовании односторонних перестановок).

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

Литература

  • [1] Yair Oren «On the cunning power of cheating verifiers: Some observations about zero knowledge proofs», FOCS 1987
  • [2] Manuel Blum, Paul Feldman, Silvio Micali «Non-interactive zero-knowledge and its applications», STOC 1988
  • [3] Alfredo De Santis, Silvio Micali, Giuseppe Persiano «Non-Interactive Zero-Knowledge Proof Systems», CRYPTO 1987
О спариваниях Вейля

Вопрос. Что такое спаривания Вейля? Как можно использовать спаривания на эллиптических кривых для того, чтобы быстрее решать вычислительную и распознавательную задачи Диффи–Хеллмана?

Ответ. Редакция благодарна автору за такой вопрос. Он соответствует тематике сайта, четко сформулирован и, главное, интересен с научной точки зрения. Но ответить на этот вопрос оказалось весьма непросто.

Начнем с задачи Диффи–Хеллмана. Вычислительный вариант этой задачи состоит в вычислении значения $g^{ab}$ по заданным $g^a$ и $g^b$. Здесь и далее предполагается, что вся необходимая информация о группе, в частности порождающий $g$, известна и не указывается во входных данных. Распознавательный вариант задачи Диффи–Хеллмана (DDH) формулируется так. Пусть значения $a$, $b$ и $r$ случайны. Требуется отличить распределения вероятностей $\{ (g^a, g^b, g^{ab})\}$ и $\{ (g^a, g^b, g^r)\}$. Предположение о вычислительной трудности этой задачи является на данный момент основным криптографическим предположением. На его основе доказано множество результатов о стойкости. Математически строгая формулировка этого предположения говорит о семействе групп с некоторыми свойствами эффективности, а основное требование формулируется на основе вычислительной неотличимости семейств распределений. Мы такое определение не приводим, его можно найти в справочнике.

К сожалению, в данной области наблюдается путаница с терминологией. Иногда распознавательной задачей Диффи–Хеллмана называют задачу распознавания языка $L_{DH}=\{ (g^a,g^b,g^{ab})\}$. Здесь предполагается, что входами могут быть произвольные тройки $(g^a,g^b,g^r)$. Заметим, что в этих двух вариантах требования различны: алгоритм, распознающий язык $L_{DH}$, доставит решение задачи DDH. Обратное представляется сомнительным. Вопрос о связи двух указанных вариантов определения задачи DDH рассматривается в обзоре Боне.

Можно было бы сказать, что задача распознавания языка $L_{DH}$ не представляет никакого интереса для криптографии, если бы не одна особенность вычислительной задачи Диффи–Хеллмана. Предположим, что мы решаем эту задачу методом угадывания. Как, зная $g^a$ и $g^b$, проверить, что выбранный нами элемент группы равен $g^{ab}$? Никакие эффективные методы не известны. Задача распознавания языка $L_{DH}$ — это в точности проверка правильности решения задачи Диффи–Хеллмана.

Коллизии терминов — не новость для науки и, в частности, для математики. Но в нашем случае дела совсем плохи. На вопрос, какой из двух указанных вариантов будет правильно, с методической точки зрения, называть распознавательной задачей Диффи–Хеллмана, ответ простой: никакой.

Сам термин «распознавательная задача» заимствован из теории сложности вычислений. Там рассматриваются два типа вычислительных задач: задачи поиска (search) и задачи распознавания (decision). Согласно этой терминологии вычислительный вариант задачи Диффи–Хеллмана есть задача поиска. Ей соответствует множество распознавательных вариантов, например задача распознавания языка $\{ (g^a,g^b,c): g^{ab}>c\}$. Здесь $c$ — произвольный элемент группы. Смысл в том, что вычислительный вариант задачи должен эффективно сводиться к соответствующей распознавательной задаче (так называемая самосводимость).

Теперь о перспективах применения спариваний Вейля к задачам Диффи–Хеллмана.

Есть такая далеко не новая и почти очевидная идея. Предположим, что нам нужно решать задачу дискретного логарифмирования или вычислительный вариант задачи Диффи–Хеллмана в группе $G_1$, где всё сложно. Предположим также, что нам удалось найти группу $G_2$, в которой та же задача решается более эффективно. Можно попытаться найти хорошее отображение $F$ из $G_1$ в $G_2$, позволяющее построить сводимость исходной задачи к аналогичной, но уже в группе $G_2$.

Здесь возникает новая проблема: решение, найденное в группе $G_2$, необходимо «вернуть» в группу $G_1$. Отображение $F$ должно быть обратимым, а следовательно, слишком уж хорошим. Кроме того, при наличии такого $F$ неясно, что препятствует переводу эффективных алгоритмов из $G_2$ в $G_1$.

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

Исследования, посвященные применимости спариваний Вейля к задачам Диффи–Хеллмана, в целом можно считать развитием данной идеи.

Попытку ответить на заданный вопрос предпринял М. И. Анохин. После некоторых размышлений и сомнений редакция сочла целесообразным поместить этот текст в раздел Лекторий. Можно сказать, что в этом материале излагается подход к проблеме с позиции алгебраиста.

Редакция также обратилась за помощью к Михаилу Алексеевичу Черепневу, одному из ведущих специалистов именно в данной области. Подготовленный им материал о спариваниях Вейля можно найти здесь. Кроме того, Михаил Алексеевич разрешил выложить на сайте адрес своей электронной почты [показать адрес]. Посетители сайта могут задавать ему вопросы по данной тематике.

О задаче ВЫПОЛНИМОСТЬ

Вопрос. Недавно услышал следующую информацию относительно задачи ВЫПОЛНИМОСТЬ. Якобы разработан алгоритм, позволяющий свести исходную формулу 3-ВЫП к виду, в котором она представлена в виде двух структур, определенных на общих переменных. И для каждой из структур может быть найдено решение за полиномиальное время. То есть решение исходной задачи заключается в нахождении пересечения множеств выполняющих наборов обеих структур.

Известно ли что-либо про это? Также с удовольствием бы послушал обзор про современное состояние в данной области.

Ответ. Редакция не смогла ответить на этот вопрос. Не ясна формулировка. Что такое структура? Что такое решение структуры? При различных интерпретациях этих терминов получается широкий спектр утверждений, от тривиальных до сенсационных ($\mathrm{P}=\mathrm{NP}$).

Что касается второй части вопроса… Мы бы тоже почитали хороший обзор по задаче ВЫПОЛНИМОСТЬ. Дело в том, что последняя — бесспорно самая популярная из вычислительных задач. Проводится ежегодная международная конференция, издается журнал, поддерживается некоторое количество сайтов, из которых, вероятно, наиболее известным является SAT-LIVE! И это только специализированные источники информации, посвященные задаче ВЫПОЛНИМОСТЬ. Кроме того, ежегодно проводятся соревнования среди программ (SAT-solvers), решающих эту задачу. А “краткий” обзор состояния исследований задачи ВЫПОЛНИМОСТЬ представляет собой почти 1000-страничную монографию. Справедливости ради, следует отметить, что тематика этой книги на самом деле несколько шире (SAT, 3-SAT, k-SAT, CSP…).

Возможно ли автоматизированное распознавание правильности решения криптограмм?

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

К примеру: есть зашифрованная не известным способом строка , ее декодируют по какому способу, и смотрят на получившийся результат человек сразу поймет адекватный ли результат, а существует ли система или алгоритм что бы компьютер (как и человек) сам «понял» что результат получился адекватным!?

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

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

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

Это частный случай общефилософской проблемы, активно обсуждавшейся полвека назад: может ли вычислительная машина мыслить?

Результатом всех эмоциональных дискуссий стала одна-единственная, но замечательная научная идея — так называемый тест Тьюринга. Имеется экспериментатор, который может задавать любые вопросы подопытному. При этом экспериментатор не знает, с кем общается — с человеком или машиной. Если никакой эксперимент не отличит этих двух подопытных, то машина умеет мыслить.

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

Так что на поставленный вопрос ответ таков: науке не известно.

Есть еще одна родственная и весьма серьезная проблема. Криптоаналитик приносит руководству некоторое сообщение и утверждает, что извлек его из перехваченной криптограммы. Насколько можно доверять этой информации? Эта проблема обсуждается в параграфе «Правильность решения криптограммы» основополагающей работы К. Шеннона «Теория связи в секретных системах» (C. Shannon. Communication theory of secrecy systems. Bell System Techn. J., 1949, v. 28, no. 4, p. 656–715. Русский перевод: К. Шеннон. Работы по теории информации и кибернетике. М., ИЛ, 1963, с. 333–402).

Относятся ли магические квадраты к современной криптографии?

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

Ответ. Магические квадраты в современных криптографических исследованиях практически не встречаются. Они не упоминаются ни в монографиях по криптографии, ни в трудах ведущих конференций и семинаров по криптографии (Crypto, Eurocrypt, FSE, TCC и др.).

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

Построение эффективных алгоритмов синтеза магических квадратов, видимо, имеет смысл. Магические квадраты являются интересным комбинаторным объектом. Математика не ограничивается математической криптографией.

Информация по криптографическим хэш-функциям

Вопрос. Есть ли у вас информация по алгоритмам криптографического хеширования (к примеру, SHA-1 или ГОСТ Р 34.11-94), а если нет, то думаю, не плохо было бы добавить, ведь это неотъемлемая часть криптографии.

Что такое субэкспоненциальная сложность?

Вопрос. Что такое субэкспоненциальная сложность? Какие алгоритмы имеют субэкспоненциальную сложность?

С чего начать изучать криптографию?

Вопрос. Хочется начать изучать криптографию, подскажите, с чего начать?

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна