- 26,710
- 46
- 8 Ноя 2022
Теоремы Гёделя, чтобы создать неразглашаемые доказательства. Вот как это работает.
В математике бывают утверждения, которые выглядят понятными, но доказать их очень трудно. Иногда доказательство, возможно, существует, но получилось бы таким длинным, что его нельзя записать и проверить на практике. Новая работа Рахула Иланго показывает, что эту трудность можно использовать в криптографии. Он связал теоремы Гёделя о неполноте с доказательствами с нулевым разглашением , где человек подтверждает, что знает решение задачи, но не показывает само решение.
Курт Гёдель в 1931 году показал предел любой достаточно сильной математической системы. Если теория строится на аксиомах, то внутри той же теории нельзя получить полную гарантию, что эти правила никогда не приведут к противоречию. Математики всё равно пользуются аксиомами, выводят теоремы и проверяют рассуждения, но абсолютную страховку из самой системы получить нельзя.
В криптографии похожая идея незнания работает иначе. В 1985 году Шафи Гольдвассер, Сильвио Микали и Чарльз Ракофф предложили доказательства с нулевым разглашением . Такой метод нужен, когда у человека есть секретная информация: например пароль, ключ доступа или решение сложной задачи. Он должен убедить проверяющего, что действительно владеет этой информацией, но не должен раскрывать её.
Классический пример - раскраска карты. Есть карта с множеством областей и три цвета. Нужно закрасить участки так, чтобы соседние области не совпадали по цвету. Найти такую схему бывает трудно, особенно если карта большая. Зато готовый вариант легко проверить: достаточно пройти по границам и посмотреть, отличаются ли цвета по обе стороны. В теории сложности такие задачи относят к классу NP : ответ тяжело найти, но легко проверить.
В этом примере секретом служит сама правильная раскраска. Если человек покажет всю карту, проверяющий сразу получит решение и сможет использовать его сам. Доказательство с нулевым разглашением устроено иначе. Человек закрывает все области и открывает только две, которые выбрал проверяющий по одной границе. Проверяющий видит, что цвета разные, но не видит всей схемы.
Затем цвета заново перемешиваются, и проверка повторяется на другом участке. После многих раундов становится крайне маловероятно, что человек просто угадывает ответы. Проверяющий убеждается, что правильная раскраска у него действительно есть. Но собрать полную карту по отдельным фрагментам не получается, потому что перед каждым раундом цветовая схема меняется.
Такой метод требует диалога. Проверяющий каждый раз выбирает новую границу, а владелец решения показывает только маленький фрагмент. Если вместо диалога просто передать готовый документ, проверяющий сможет прочитать всё и узнать лишнее. Если документ зашифровать, он не сможет убедиться, что внутри правильное решение.
В 1994 году Одед Гольдрайх и Яир Орен строго описали это ограничение. По их результату полностью неинтерактивная схема не может соответствовать классическому определению нулевого разглашения. Иными словами, обычная запись без вопросов и ответов не умеет одновременно убеждать проверяющего и скрывать всю лишнюю информацию.
Иланго предложил другой путь. Он не пытался сделать обычный текст таким же безопасным, как диалог. Вместо этого он изменил само условие, по которому схему считают безопасной. Для этого ему понадобилась область, которая называется сложностью доказательств. Она изучает не то, насколько трудно найти ответ на задачу, а насколько трудно доказать утверждение о задаче.
Например, можно спросить: сколько шагов нужно, чтобы найти правильную раскраску карты. Это обычный вопрос теории сложности. А можно спросить иначе: насколько длинным будет самое короткое доказательство того, что конкретную карту невозможно раскрасить тремя цветами. Это уже вопрос сложности доказательств.
Здесь есть важный промежуточный случай. Одни утверждения нельзя ни доказать, ни опровергнуть внутри выбранной системы - это область теорем Гёделя . Другие утверждения могут иметь доказательство в принципе, но оно настолько длинное, что никто не сможет записать его полностью. Для практической работы результат почти тот же: нужного рассуждения у нас нет.
Иланго решил использовать такую трудность как защитный механизм. Современная криптография чаще опирается на задачи, которые тяжело решить: например разложить большое число на множители или подобрать ключ. В новой работе источник защиты другой. Система опирается на то, что проверяющий не сможет доказать определённый факт о самой схеме.
В 2024 году Иланго выбрал конкретную цель - неинтерактивные доказательства с нулевым разглашением. Старый результат Гольдрайха и Орена запрещал их при классическом определении. Но этот запрет относится к одной строгой формулировке. Иланго предложил более мягкий критерий, который сохраняет главный практический смысл: проверяющий убеждается в знании секрета, но не получает способ восстановить его.
В классическом подходе важен симулятор. Так называют воображаемую программу, которая может заранее воспроизвести всё, что увидит проверяющий. Если такую картину можно получить без общения с владельцем секрета, значит, реальная проверка не раскрывает новых данных. В примере с картой проверяющий заранее знает формат успешного раунда: по выбранной границе откроются две области разных цветов. Он получает уверенность, но не получает всю раскраску.
Старый результат говорит, что у полностью неинтерактивной схемы такого симулятора быть не может. Иланго предложил смотреть на ситуацию иначе. Не обязательно показывать, что симулятор точно есть. Достаточно, чтобы проверяющий не мог доказать обратное - что симулятора точно нет. Если он не может это обосновать доступным способом, у него нет практического пути извлечь секрет.
Для интуиции можно представить замок с необычной гарантией. Производитель не говорит, что замок невозможно открыть без ключа. Он говорит другое: никто не сможет предъявить рабочее подтверждение, что замок уязвим. Если злоумышленник нашёл способ открыть замок, сам этот способ уже показывает проблему. Если показать такую слабость невозможно, то воспользоваться ею тоже не получится. Иланго переносит похожую идею на криптографическую схему.
Дальше в конструкцию входит логика Гёделя. Обычное утверждение «эту карту можно раскрасить тремя цветами» Иланго рассматривает с дополнительным условием: «если не существует эффективного способа найти противоречие в стандартных аксиомах математики». В нормальной математике это условие почти ничего не меняет, потому что исследователи обычно считают стандартные аксиомы непротиворечивыми.
Но само отсутствие противоречий нельзя быстро и удобно доказать изнутри той же системы. Возможно, формальное доказательство где-то существует, но оно слишком велико для реального использования. Поэтому проверяющий не может полностью исключить странный вариант, где аксиомы всё же противоречивы.
Зачем нужен такой странный вариант? В обычной математике старый запрет Гольдрайха и Орена работает, и неинтерактивная схема не получает классическое нулевое разглашение. А если представить систему с противоречивыми аксиомами, привычные правила проверки ломаются: корректные и ошибочные рассуждения уже нельзя нормально разделить. В таком формальном варианте запрет теряет силу.
Проверяющий почти наверняка работает в обычной непротиворечивой математике. Но он не может коротко и надёжно доказать, что другой вариант невозможен. Поэтому он не может доказать и отсутствие симулятора. На этом держится идея Иланго: схема не подходит под старое определение, но в практическом смысле всё равно не раскрывает секрет.
Для криптографов это неожиданный поворот. Иланго не отменяет результат 1994 года: при классическом определении запрет остаётся в силе. Он показывает, что можно выбрать другой критерий безопасности и получить полезную неинтерактивную схему. Проверяющий по-прежнему не получает решение задачи, даже если конструкция устроена иначе, чем классические протоколы.
Криптограф Амит Сахай из Калифорнийского университета в Лос-Анджелесе признался, что первая реакция на работу Иланго была почти недоверием: «Когда видишь это впервые, думаешь: подождите, что?» Реакция понятна: секретность здесь опирается не на шифр и не на диалог, а на невозможность доказать отсутствие определённого механизма. После проверки математическая логика сходится.
Работа важна не только из-за нового вида нулевого разглашения. Она показывает, что сложность доказательств может напрямую пригодиться криптографии. Раньше исследователи в этой области в основном изучали, какие утверждения трудно доказать , и сравнивали длину возможных рассуждений. Иланго показал, что эта трудность может стать основой для новых защитных схем.
Сейчас Иланго работает постдоком в Институте перспективных исследований в Принстоне. Его результат уже подтолкнул специалистов искать новые связи между математической логикой, теорией сложности и криптографией. Старые запреты в таких задачах не всегда закрывают направление окончательно. Иногда они показывают, что прежнее определение слишком узкое и рядом можно искать более точную формулировку.
В математике бывают утверждения, которые выглядят понятными, но доказать их очень трудно. Иногда доказательство, возможно, существует, но получилось бы таким длинным, что его нельзя записать и проверить на практике. Новая работа Рахула Иланго показывает, что эту трудность можно использовать в криптографии. Он связал теоремы Гёделя о неполноте с доказательствами с нулевым разглашением , где человек подтверждает, что знает решение задачи, но не показывает само решение.
Курт Гёдель в 1931 году показал предел любой достаточно сильной математической системы. Если теория строится на аксиомах, то внутри той же теории нельзя получить полную гарантию, что эти правила никогда не приведут к противоречию. Математики всё равно пользуются аксиомами, выводят теоремы и проверяют рассуждения, но абсолютную страховку из самой системы получить нельзя.
В криптографии похожая идея незнания работает иначе. В 1985 году Шафи Гольдвассер, Сильвио Микали и Чарльз Ракофф предложили доказательства с нулевым разглашением . Такой метод нужен, когда у человека есть секретная информация: например пароль, ключ доступа или решение сложной задачи. Он должен убедить проверяющего, что действительно владеет этой информацией, но не должен раскрывать её.
Классический пример - раскраска карты. Есть карта с множеством областей и три цвета. Нужно закрасить участки так, чтобы соседние области не совпадали по цвету. Найти такую схему бывает трудно, особенно если карта большая. Зато готовый вариант легко проверить: достаточно пройти по границам и посмотреть, отличаются ли цвета по обе стороны. В теории сложности такие задачи относят к классу NP : ответ тяжело найти, но легко проверить.
В этом примере секретом служит сама правильная раскраска. Если человек покажет всю карту, проверяющий сразу получит решение и сможет использовать его сам. Доказательство с нулевым разглашением устроено иначе. Человек закрывает все области и открывает только две, которые выбрал проверяющий по одной границе. Проверяющий видит, что цвета разные, но не видит всей схемы.
Затем цвета заново перемешиваются, и проверка повторяется на другом участке. После многих раундов становится крайне маловероятно, что человек просто угадывает ответы. Проверяющий убеждается, что правильная раскраска у него действительно есть. Но собрать полную карту по отдельным фрагментам не получается, потому что перед каждым раундом цветовая схема меняется.
Такой метод требует диалога. Проверяющий каждый раз выбирает новую границу, а владелец решения показывает только маленький фрагмент. Если вместо диалога просто передать готовый документ, проверяющий сможет прочитать всё и узнать лишнее. Если документ зашифровать, он не сможет убедиться, что внутри правильное решение.
В 1994 году Одед Гольдрайх и Яир Орен строго описали это ограничение. По их результату полностью неинтерактивная схема не может соответствовать классическому определению нулевого разглашения. Иными словами, обычная запись без вопросов и ответов не умеет одновременно убеждать проверяющего и скрывать всю лишнюю информацию.
Иланго предложил другой путь. Он не пытался сделать обычный текст таким же безопасным, как диалог. Вместо этого он изменил само условие, по которому схему считают безопасной. Для этого ему понадобилась область, которая называется сложностью доказательств. Она изучает не то, насколько трудно найти ответ на задачу, а насколько трудно доказать утверждение о задаче.
Например, можно спросить: сколько шагов нужно, чтобы найти правильную раскраску карты. Это обычный вопрос теории сложности. А можно спросить иначе: насколько длинным будет самое короткое доказательство того, что конкретную карту невозможно раскрасить тремя цветами. Это уже вопрос сложности доказательств.
Здесь есть важный промежуточный случай. Одни утверждения нельзя ни доказать, ни опровергнуть внутри выбранной системы - это область теорем Гёделя . Другие утверждения могут иметь доказательство в принципе, но оно настолько длинное, что никто не сможет записать его полностью. Для практической работы результат почти тот же: нужного рассуждения у нас нет.
Иланго решил использовать такую трудность как защитный механизм. Современная криптография чаще опирается на задачи, которые тяжело решить: например разложить большое число на множители или подобрать ключ. В новой работе источник защиты другой. Система опирается на то, что проверяющий не сможет доказать определённый факт о самой схеме.
В 2024 году Иланго выбрал конкретную цель - неинтерактивные доказательства с нулевым разглашением. Старый результат Гольдрайха и Орена запрещал их при классическом определении. Но этот запрет относится к одной строгой формулировке. Иланго предложил более мягкий критерий, который сохраняет главный практический смысл: проверяющий убеждается в знании секрета, но не получает способ восстановить его.
В классическом подходе важен симулятор. Так называют воображаемую программу, которая может заранее воспроизвести всё, что увидит проверяющий. Если такую картину можно получить без общения с владельцем секрета, значит, реальная проверка не раскрывает новых данных. В примере с картой проверяющий заранее знает формат успешного раунда: по выбранной границе откроются две области разных цветов. Он получает уверенность, но не получает всю раскраску.
Старый результат говорит, что у полностью неинтерактивной схемы такого симулятора быть не может. Иланго предложил смотреть на ситуацию иначе. Не обязательно показывать, что симулятор точно есть. Достаточно, чтобы проверяющий не мог доказать обратное - что симулятора точно нет. Если он не может это обосновать доступным способом, у него нет практического пути извлечь секрет.
Для интуиции можно представить замок с необычной гарантией. Производитель не говорит, что замок невозможно открыть без ключа. Он говорит другое: никто не сможет предъявить рабочее подтверждение, что замок уязвим. Если злоумышленник нашёл способ открыть замок, сам этот способ уже показывает проблему. Если показать такую слабость невозможно, то воспользоваться ею тоже не получится. Иланго переносит похожую идею на криптографическую схему.
Дальше в конструкцию входит логика Гёделя. Обычное утверждение «эту карту можно раскрасить тремя цветами» Иланго рассматривает с дополнительным условием: «если не существует эффективного способа найти противоречие в стандартных аксиомах математики». В нормальной математике это условие почти ничего не меняет, потому что исследователи обычно считают стандартные аксиомы непротиворечивыми.
Но само отсутствие противоречий нельзя быстро и удобно доказать изнутри той же системы. Возможно, формальное доказательство где-то существует, но оно слишком велико для реального использования. Поэтому проверяющий не может полностью исключить странный вариант, где аксиомы всё же противоречивы.
Зачем нужен такой странный вариант? В обычной математике старый запрет Гольдрайха и Орена работает, и неинтерактивная схема не получает классическое нулевое разглашение. А если представить систему с противоречивыми аксиомами, привычные правила проверки ломаются: корректные и ошибочные рассуждения уже нельзя нормально разделить. В таком формальном варианте запрет теряет силу.
Проверяющий почти наверняка работает в обычной непротиворечивой математике. Но он не может коротко и надёжно доказать, что другой вариант невозможен. Поэтому он не может доказать и отсутствие симулятора. На этом держится идея Иланго: схема не подходит под старое определение, но в практическом смысле всё равно не раскрывает секрет.
Для криптографов это неожиданный поворот. Иланго не отменяет результат 1994 года: при классическом определении запрет остаётся в силе. Он показывает, что можно выбрать другой критерий безопасности и получить полезную неинтерактивную схему. Проверяющий по-прежнему не получает решение задачи, даже если конструкция устроена иначе, чем классические протоколы.
Криптограф Амит Сахай из Калифорнийского университета в Лос-Анджелесе признался, что первая реакция на работу Иланго была почти недоверием: «Когда видишь это впервые, думаешь: подождите, что?» Реакция понятна: секретность здесь опирается не на шифр и не на диалог, а на невозможность доказать отсутствие определённого механизма. После проверки математическая логика сходится.
Работа важна не только из-за нового вида нулевого разглашения. Она показывает, что сложность доказательств может напрямую пригодиться криптографии. Раньше исследователи в этой области в основном изучали, какие утверждения трудно доказать , и сравнивали длину возможных рассуждений. Иланго показал, что эта трудность может стать основой для новых защитных схем.
Сейчас Иланго работает постдоком в Институте перспективных исследований в Принстоне. Его результат уже подтолкнул специалистов искать новые связи между математической логикой, теорией сложности и криптографией. Старые запреты в таких задачах не всегда закрывают направление окончательно. Иногда они показывают, что прежнее определение слишком узкое и рядом можно искать более точную формулировку.
- Источник новости
- www.securitylab.ru
