Казалось, что для решения важной проблемы тщательная проверка всех возможных вариантов — наилучший подход. Теперь исследователи доказали, что есть лучший способ. Комментарий Сохранить статью Прочитать позже
Введение
Как лучше всего решать сложные задачи? Этот вопрос лежит в основе раздела компьютерной науки, называемого теорией сложности вычислений. На этот вопрос сложно ответить, но если взглянуть на него с другой стороны, он становится проще. Худший подход почти всегда — это метод проб и ошибок, когда приходится перебирать возможные решения до тех пор, пока одно из них не сработает. Но для некоторых задач, похоже, просто нет альтернатив — худший подход одновременно и лучший.
Исследователи давно задаются вопросом, действительно ли это так, говорит Рахул Иланго, аспирант, изучающий теорию сложности в Массачусетском технологическом институте. «Можно спросить: „Есть ли задачи, для которых метод догадок и проверок — это просто оптимальный подход?“»
Специалисты по теории сложности изучили множество вычислительных задач, и даже самые сложные из них часто допускают существование некой хитрой процедуры или алгоритма, который делает поиск решения немного проще, чем методом проб и ошибок. Среди немногих исключений — так называемые задачи сжатия, где целью является нахождение кратчайшего описания набора данных.
Но в ноябре прошлого года две группы исследователей независимо друг от друга открыли другой алгоритм для решения задач сжатия — тот, который работает чуть быстрее, чем проверка всех возможных ответов. Новый подход основан на адаптации алгоритма, разработанного криптографами 25 лет назад, для решения другой задачи. Есть только одно ограничение: алгоритм необходимо адаптировать к размеру вашего набора данных.
«Это действительно прекрасные и важные результаты», — сказал Эрик Аллендер, специалист по теоретической информатике из Ратгерского университета.
Определение твердости
Новые результаты — это новейшее исследование вопроса, который впервые изучался в Советском Союзе, задолго до появления теории сложности. «Ещё до того, как я пошёл в начальную школу, в России уже разрабатывали эту концепцию», — сказал Аллендер.
Конкретная вычислительная задача, которую изучали советские исследователи, называемая задачей минимального размера схемы, близка к той, с которой постоянно сталкиваются разработчики компьютерного оборудования. Если вам даны полные спецификации того, как должна вести себя электронная схема, сможете ли вы найти простейшую схему, которая её выполнит? Никто не знал, как решить эту задачу без «перебора» — русского слова, примерно соответствующего «перебору».
Задача о минимальном размере схемы — пример проблемы сжатия. Можно описать поведение схемы длинной строкой битов — нулей и единиц — а затем задаться вопросом, можно ли воспроизвести то же самое поведение, используя меньшее количество бит. Проверка всех возможных вариантов схемы займёт время, экспоненциально растущие с увеличением количества битов в строке.
Такой экспоненциальный рост — определяющая черта сложной вычислительной задачи. Но не все сложные задачи одинаково сложны — для некоторых существуют алгоритмы, которые быстрее полного перебора, хотя время их выполнения всё равно растёт экспоненциально. В современных терминах вопрос перебора заключается в том, существуют ли подобные алгоритмы для задач сжатия.
В 1959 году известный исследователь Сергей Яблонский заявил, что доказал, что полный перебор действительно является единственным способом решения задачи о минимальном размере схемы. Однако его доказательство оставляло некоторые пробелы. Некоторые исследователи заметили эти недостатки уже тогда, но Яблонский был достаточно влиятельным, чтобы отговорить большинство других исследователей от работы над проблемой перебора.
В последующие десятилетия мало кто из исследователей занимался проблемами сжатия, и вопрос перебора был известен в основном как сноска в предыстории теории сложности. Широкое внимание к нему пришло лишь недавно, после того как исследователи обнаружили любопытную связь между проблемами сжатия и основами криптографии.
Одностороннее движение
Современная криптография использует сложные вычислительные задачи для защиты секретных сообщений. Но вычислительная сложность полезна только в случае асимметричности — если расшифровать закодированные сообщения сложно, но закодировать их несложно.
В любой криптографической схеме источником этой асимметрии является математический объект, называемый односторонней функцией, которая преобразует входные битовые строки в выходные строки той же длины. По входным данным односторонней функции легко вычислить выходные данные, но по выходным данным сложно инвертировать функцию, то есть провести её обратную разработку и восстановить входные данные.
«Криптографы действительно хотели бы иметь очень, очень эффективно вычисляемые односторонние функции, которые было бы очень, очень трудно инвертировать», — сказал Аллендер. Многие математические функции, по-видимому, обладают этим свойством, и сложность их инвертирования проистекает из очевидной сложности решения различных вычислительных задач.
К сожалению, криптографы не знают наверняка, действительно ли какие-либо из этих функций трудно инвертировать — более того, вполне возможно, что настоящих односторонних функций не существует. Эта неопределённость сохраняется, поскольку теоретики сложности уже 50 лет пытаются доказать, что кажущиеся сложными задачи действительно сложны. Если это не так, и если исследователи откроют сверхбыстрые алгоритмы для их решения, это будет катастрофой для криптографии — подобно внезапному развороту на дороге с односторонним движением.
Несмотря на то, что полное понимание вычислительной сложности остаётся неясным, криптографы недавно добились впечатляющего прогресса на пути к созданию единой теории односторонних функций. Важный шаг был сделан в 2020 году, когда криптограф Тель-Авивского университета Рафаэль Пасс и его аспирант Яньи Лю доказали, что односторонние функции тесно связаны с конкретной задачей сжатия, называемой проблемой ограниченной по времени сложности Колмогорова.
Если эта задача действительно сложно решается для большинства входных данных, то результат Пасса и Лю даёт рецепт построения доказуемо сложной односторонней функции — гарантированно безопасной, даже если другие вычислительные задачи окажутся гораздо проще, чем ожидали исследователи. Но если существует быстрый алгоритм решения задачи Колмогорова с ограниченной по времени сложностью, то криптография обречена, и любая функция может быть легко обращена. Односторонняя функция, основанная на сложности этой задачи, является наиболее безопасной из возможных — односторонней функцией, способной управлять всеми.
Построение структур данных
Открытие Пасса и Лю стало последней главой в длинной череде исследований, использующих теорию сложности для лучшего понимания основ криптографии. Однако оно также предложило способ обратить эту взаимосвязь: эквивалентность задачи Колмогорова с ограниченной по времени сложностью и обращения функции подразумевает, что понимание одной из этих задач может дать больше информации о другой. Криптографы десятилетиями изучали алгоритмы обращения функций, чтобы лучше понять слабые места своих методов шифрования. Исследователи начали задаваться вопросом, могут ли эти алгоритмы помочь ответить на извечные вопросы теории сложности.
Как и многие вычислительные задачи, обращение функции можно решить методом полного перебора. Имея выходную строку, просто подставьте все возможные входные данные в функцию, пока не найдёте тот, который даст правильный ответ.
Рафаэль Пасс помог разработать более быстрый алгоритм решения задачи сжатия, адаптировав старый метод из криптографии.
В 1980 году криптограф Мартин Хеллман начал изучать, можно ли добиться чего-то лучшего — тот же вопрос, который советские математики задавали десятилетиями ранее, говоря о проблемах сжатия. Хеллман обнаружил, что да, это возможно — при условии готовности заранее выполнить дополнительную работу, используя математические объекты, называемые структурами данных.
Структура данных — это, по сути, таблица, хранящая информацию о функции, которую нужно инвертировать. Её построение требует вычисления выходных данных функции для определённых стратегически выбранных входных данных. Все эти вычисления «могут занять очень много времени», — сказал Райан Уильямс, специалист по теории сложности из Массачусетского технологического института. «Но идея заключается в том, что это делается один раз и навсегда». Если вы пытаетесь инвертировать одну и ту же функцию, имея множество различных выходных данных — например, для декодирования множества разных сообщений, зашифрованных одинаково, — заранее проделать эту работу может быть полезно.
Конечно, хранение этой дополнительной информации требует места, поэтому, доведя эту стратегию до крайности, можно получить быструю программу, которая не поместится ни на один компьютер. Хеллман разработал хитроумную структуру данных, которая позволила его алгоритму инвертировать большинство функций немного быстрее, чем полный перебор, не занимая при этом слишком много места. Затем, в 2000 году, криптографы Амос Фиат и Мони Наор распространили аргументы Хеллмана на все функции.
После прорыва Пасса и Лю в 2020 году эти старые результаты внезапно обрели новую актуальность. Алгоритм Фиата-Наора может инвертировать произвольные функции быстрее, чем полный перебор. Сможет ли он также работать и с задачами сжатия?
Вне формы
Первыми исследователями, поднявшими этот вопрос, были теоретик сложности Рахул Сантханам из Оксфордского университета и его аспирант Ханлин Рен. Они сделали это в статье 2021 года, доказав, что проблемы сжатия и инверсии функций переплетены ещё сильнее, чем предполагали исследователи.
Пасс и Лю доказали, что если задача Колмогорова с ограниченной по времени сложностью сложна, то и обращение функции должно быть сложным, и наоборот. Но задачи могут быть сложными и при этом допускать решения, немного превосходящие полный перебор. Сантанам и Рен показали, что существует тесная связь между необходимостью полного перебора для одной задачи и необходимостью полного перебора для другой.
Их результат имел различные последствия для двух широких классов алгоритмов, часто изучаемых исследователями, называемых «равномерными» и «неравномерными» алгоритмами. Равномерные алгоритмы используют одну и ту же процедуру для всех входных данных — например, единая программа для сортировки списков чисел будет работать одинаково, независимо от того, содержит ли список 20 записей или 20 000. Неравномерные алгоритмы, напротив, используют разные процедуры для входных данных разной длины.
Структуры данных, используемые алгоритмом Фиата-Наора, всегда адаптированы к конкретной функции. Для инвертирования функции, скремблирующей 10-битную строку, требуется структура данных, отличная от той, которая потребовалась бы для инвертирования функции, скремблирующей 20-битную строку, даже если скремблирование выполняется аналогичным образом. Это делает алгоритм Фиата-Наора неоднородным.
Результат Сантханама и Рена показал, что алгоритм Фиата-Наора, возможно, можно преобразовать в алгоритм для решения задач сжатия. Однако адаптация алгоритма с одной задачи на другую оказалась непростой задачей, и они не стали изучать этот вопрос дальше.
Райан Уильямс (слева), Рахул Иланго (в центре) и Шуичи Хирахара обнаружили один способ обойти исчерпывающий поиск проблем сжатия.
Пасс наткнулся на ту же идею год спустя, услышав доклад Фиата о классическом алгоритме на семинаре, посвящённом вкладу Наора в криптографию. «Эта идея использования инверсии функций крутилась у меня в голове с тех пор», — сказал он. Позже он начал серьёзно работать над этой проблемой вместе с исследователем из Тель-Авивского университета Ноамом Мазором.
Тем временем Иланго вдохновился на решение этой проблемы после обсуждений с другими исследователями, включая Сантанама, во время визита в Институт теории вычислений Саймонса в Беркли, штат Калифорния. «Это произошло в ходе одного из тех очень удачных разговоров, когда просто разбрасываешься информацией», — сказал Сантанам. Позже Иланго объединил усилия с Уильямсом и Шуичи Хирахарой, специалистом по теории сложности из Национального института информатики в Токио.
Сложнее всего было понять, как встроить структуру данных, лежащую в основе алгоритма Фиата-Наора, в неоднородный алгоритм для решения задач сжатия. Существует стандартная процедура для такого встраивания, но это замедлило бы алгоритм, сведя на нет его преимущество перед полным перебором. Две команды нашли более продуманные способы внедрения структуры данных Фиата-Наора и получили алгоритмы для задач сжатия, которые работали со всеми входными данными и оставались быстрее полного перебора.
Детали двух алгоритмов немного различаются. Алгоритм Иланго и его соавторов быстрее полного перебора, даже если ограничить поиск простейшими вариантами, и применим ко всем задачам сжатия — ограниченному по времени колмогоровскому перебору, задаче минимального размера схемы и многим другим. Но основная идея обоих алгоритмов одинакова. Методы криптографии доказали свою эффективность в этой новой области.
Инверсионная конвергенция
Новое доказательство для неоднородных алгоритмов поднимает естественный вопрос: а как насчёт однородных алгоритмов? Есть ли способ решать задачи сжатия быстрее, чем полный перебор с их помощью?
Недавняя серия результатов предполагает, что любой такой алгоритм будет эквивалентен единому алгоритму обращения произвольных функций — то, чего криптографы безуспешно пытаются добиться десятилетиями. По этой причине многие исследователи считают такую возможность маловероятной.
«Я был бы очень удивлён, — сказал Сантанам. — Для этого потребовалась бы совершенно новая идея».
Но Аллендер сказал, что исследователям не следует исключать такую возможность. «Для меня хорошая рабочая гипотеза заключается в том, что если существует нестандартный способ что-то сделать, то, скорее всего, существует и стандартный способ», — сказал он.
Так или иначе, эта работа пробудила в специалистах по теории сложности новый интерес к старым вопросам криптографии. Юваль Ишай, криптограф из Техниона в Хайфе, Израиль, сказал, что именно это делает её особенно интересной.
«Я очень рад видеть такое сближение интересов разных сообществ, — сказал он. — Я думаю, это очень полезно для науки».
Источник: www.quantamagazine.org
