Який найкращий спосіб вирішити складні проблеми? Це питання в центрі підгалузі інформатики під назвою теорія обчислювальної складності. Важко відповісти на це запитання, але переверніть його, і стане легше. Найгірший підхід – це майже завжди метод проб і помилок, який передбачає підключення можливих рішень, поки одне не спрацює. Але для деяких проблем здається, що альтернатив просто немає — найгірший підхід є й найкращим.

Дослідники довго гадали, чи це колись справді так Рахул Іланго, аспірант, який вивчає теорію складності в Массачусетському технологічному інституті. «Ви можете запитати: «Чи є проблеми, для яких метод «вгадай і перевір» є оптимальним?»

Теоретики складності досліджували багато обчислювальних проблем, і навіть складні з них часто допускають якусь розумну процедуру або алгоритм, який робить пошук рішення дещо легшим, ніж чисті спроби та помилки. Серед небагатьох винятків є так звані проблеми стиснення, де метою є знайти найкоротший опис набору даних.

Але в листопаді минулого року дві групи дослідників самостійно відкритий ще один алгоритм для вирішення проблем стиснення — той, який дещо швидший, ніж перевірка всіх можливих відповідей. Новий підхід працює, адаптуючи алгоритм, винайдений криптографами 25 років тому, для атаки на іншу проблему. Є лише одне обмеження: вам потрібно адаптувати алгоритм до розміру вашого набору даних.

«Вони справді гарні та важливі результати», – сказав Ерік Аллендер, вчений-теоретик з Ратгерського університету.

Визначення твердості

Нові результати є останніми для дослідження питання, яке вперше вивчали в Радянському Союзі, задовго до появи теорії складності. «До того, як я був у початковій школі, люди в Росії це формулювали», — сказав Аллендер.

Конкретна обчислювальна проблема, яку досліджували ці радянські дослідники, називається проблемою мінімального розміру схеми, схожа на ту, з якою постійно стикаються розробники комп’ютерного обладнання. Якщо вам надано повні специфікації того, як має поводитися електронна схема, чи зможете ви знайти найпростішу схему, яка виконає цю роботу? Ніхто не знав, як вирішити цю проблему без «перебору» — російського слова, приблизно відповідного «вичерпному пошуку».

Проблема мінімального розміру схеми є прикладом проблеми стиснення. Ви можете описати поведінку схеми за допомогою довгого рядка бітів — 0 і 1 — і потім запитати, чи є спосіб відтворити ту саму поведінку, використовуючи меншу кількість бітів. Перевірка всіх можливих схем займе час, який експоненціально зростає зі збільшенням кількості бітів у рядку.

Цей тип експоненціального зростання є визначальною рисою складної обчислювальної задачі. Але не всі складні проблеми однаково складні — деякі мають алгоритми, швидші за вичерпний пошук, хоча час їх виконання все одно зростає експоненціально. Говорячи сучасними термінами, питання перебору полягає в тому, чи існують такі алгоритми для проблем стиснення.

У 1959 році видатний дослідник на ім'я Сергій Яблонський стверджував, що довів, що вичерпний пошук дійсно був єдиним способом вирішити проблему мінімального розміру схеми. Але його доказ залишив деякі лазівки. Деякі дослідники тоді помітили недоліки, але Яблонський був достатньо впливовим, щоб перешкодити більшості інших працювати над питанням перебору.

У наступні десятиліття мало дослідників вивчали проблеми стиснення, і питання перебору було відоме здебільшого як виноска в передісторії теорії складності. Широка увага до цього питання привернулася лише нещодавно, після того як дослідники виявили цікавий зв’язок між проблемами стиснення та основами криптографії.

Односторонній рух

Сучасна криптографія використовує складні обчислювальні проблеми для захисту секретних повідомлень. Але обчислювальна жорсткість корисна лише в тому випадку, якщо вона асиметрична — якщо важко розшифрувати закодовані повідомлення, але не важко закодувати повідомлення в першу чергу.

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

«Криптографи дійсно хотіли б мати дуже, дуже ефективно обчислювані односторонні функції, які дійсно, дуже важко інвертувати», — сказав Аллендер. Здається, багато математичних функцій мають цю властивість, і складність інвертування цих функцій виникає через очевидну складність вирішення різних обчислювальних задач.

На жаль, криптографи не знають напевно, чи справді будь-яку з цих функцій важко інвертувати — справді, цілком можливо, що справжніх односторонніх функцій не існує. Ця невизначеність зберігається, тому що теоретики складності це зробили боролися 50 років щоб довести, що, здавалося б, складні проблеми насправді є складними. Якщо це не так, і якщо дослідники відкриють надшвидкісні алгоритми вирішення цих проблем, це буде катастрофічно для криптографії — схоже на те, щоб раптово розганяти швидкісні автомобілі в обох напрямках на вулиці з одностороннім рухом.

Незважаючи на те, що всебічне розуміння обчислювальної складності залишається недосяжним, криптографи нещодавно досягли захоплюючого прогресу в напрямку єдиної теорії односторонніх функцій. Один великий крок був зроблений у 2020 році, коли криптограф Тель-Авівського університету Перевал Рафаеля та його аспірант Яньі Лю довів, що односторонні функції є тісно пов'язані до конкретної проблеми стиснення, яка називається обмеженою в часі проблемою складності Колмогорова.

Якщо цю проблему справді важко розв’язати для більшості вхідних даних, тоді результат Пасса та Лю дає рецепт, як побудувати доказово складну односторонню функцію — таку, яка гарантовано буде безпечною, навіть якщо інші обчислювальні проблеми виявляться набагато легшими. ніж очікували дослідники. Але якщо є швидкий алгоритм для вирішення обмеженої в часі проблеми складності Колмогорова, то криптографія приречена, і будь-яку функцію можна легко інвертувати. Односпрямована функція, заснована на складності цієї проблеми, є найбезпечнішою функцією з можливих — односпрямована функція керує ними всіма.

Побудова на структурах даних

Відкриття Пасса та Лю стало останньою главою в довгій лінії досліджень, які використовують теорію складності для кращого розуміння основ криптографії. Але він також запропонував спосіб інвертувати цей зв’язок: еквівалентність між обмеженою в часі проблемою складності Колмогорова та інверсією функції означає, що розуміння будь-якої проблеми може розкрити більше про іншу. Криптографи десятиліттями вивчали алгоритми інверсії функцій, щоб краще зрозуміти слабкі місця їхніх методів шифрування. Дослідники почали задаватися питанням, чи можуть ці алгоритми допомогти відповісти на давні питання в теорії складності.

Подібно до багатьох обчислювальних задач, інверсію функції можна розв’язати шляхом вичерпного пошуку. Маючи вихідний рядок, просто підключіть усі можливі вхідні дані до функції, доки не знайдете той, який дає правильну відповідь.

У 1980 році криптограф Мартін Геллман почав досліджувати, чи можна зробити щось краще — те саме питання, яке десятиліттями раніше ставили радянські математики щодо проблем стиснення. Хеллман відкритий це так, це можливо — за умови, що ви готові докласти додаткову роботу заздалегідь, використовуючи математичні об’єкти, які називаються структурами даних.

Структура даних — це, по суті, таблиця, яка зберігає інформацію про функцію, яку потрібно інвертувати, і її побудова вимагає обчислення виходів функції для певних стратегічно вибраних вхідних даних. Усі ці обчислення «можуть зайняти дуже багато часу». Райан Вільямс, теоретик складності в MIT. «Але ідея полягає в тому, що це робиться раз, раз і назавжди». Якщо ви намагаєтеся інвертувати ту саму функцію, маючи багато різних виходів — скажімо, щоб декодувати багато різних повідомлень, зашифрованих однаковим способом — це може бути корисним зробити цю роботу заздалегідь.

Звичайно, для зберігання цієї додаткової інформації потрібен простір, тому доведіть цю стратегію до крайності, і ви можете отримати швидку програму, яка не поміститься на жодному комп’ютері. Геллман розробив розумну структуру даних, яка дозволила його алгоритму інвертувати більшість функцій трохи швидше, ніж вичерпний пошук, не займаючи при цьому багато місця. Потім у 2000 році криптографи Амос Фіат і Моні Наор розширений Аргументи Хеллмана для всіх функцій.

Після прориву Пасса та Лю у 2020 році ці старі результати раптово стали актуальними. Алгоритм Фіата-Наора міг інвертувати довільні функції швидше, ніж вичерпний пошук. Чи може це також працювати для проблем зі стисненням?

Поза формою

Першими дослідниками, які поставили це питання, були теоретики складності Рахул Сантанам Оксфордського університету та його аспірант Ханлін Рен. Вони зробили це в Папір 2021 доводячи, що проблеми стиснення та інверсії функції переплетені ще більше, ніж уявляли дослідники.

Пасс і Лю довели, що якщо обмежена в часі проблема складності Колмогорова є важкою, то інверсія функції також має бути важкою, і навпаки. Але проблеми можуть бути важкими, і вони все одно допускають рішення, які трохи кращі, ніж вичерпний пошук. Сантанам і Рен показали, що існує тісний зв’язок між тим, чи потрібний вичерпний пошук для однієї проблеми та чи потрібен він для іншої.

Їх результат мав різні наслідки для двох широких класів алгоритмів, які часто вивчають дослідники, які називаються «уніфікованими» та «неуніфікованими» алгоритмами. Уніфіковані алгоритми виконують однакову процедуру для кожного введення — наприклад, уніфікована програма для сортування списків чисел працюватиме однаково незалежно від того, чи є в списку 20 записів, чи 20,000 XNUMX. Натомість неуніфіковані алгоритми використовують різні процедури для вхідних даних різної довжини.

Структури даних, які використовує алгоритм Fiat-Naor, завжди адаптовані до конкретної функції. Щоб інвертувати функцію, яка шифрує 10-бітний рядок, вам потрібна структура даних, відмінна від тієї, яка потрібна для інвертування функції, яка шифрує 20-бітовий рядок, навіть якщо скремблювання виконується подібним чином. Це робить Fiat-Naor неоднорідним алгоритмом.

Результат Сантанама та Рена припустив, що можливо перетворити алгоритм Фіата-Наора в алгоритм для вирішення проблем стиснення. Але адаптація алгоритму від однієї проблеми до іншої була не простою, і вони не розв’язували це питання далі.

Пасс наткнувся на ту саму ідею рік потому, почувши доповідь Фіата про класичний алгоритм на семінарі, присвяченому внеску Наора в криптографію. «Ця ідея використання інверсії функцій була в моєму розумі відтоді», — сказав він. Пізніше він почав серйозно працювати над цією проблемою разом із дослідником Тель-Авівського університету Ноам Мазор.

Тим часом Іланго був натхненний атакувати проблему після обговорень з іншими дослідниками, включаючи Сантанама, під час візиту до Інституту теорії обчислень Саймонса в Берклі, Каліфорнія. «Це виникло в результаті однієї з таких випадкових розмов, коли ви просто розкидаєтеся, — сказав Сантанам. Пізніше Іланго об'єднав зусилля з Вільямсом і Шуїчі Хірахара, теоретик складності в Національному інституті інформатики в Токіо.

Важкою частиною було з’ясувати, як вбудувати структуру даних, що лежить в основі алгоритму Фіата-Наора, у нерівномірний алгоритм для вирішення проблем стиснення. Існує стандартна процедура такого вбудовування, але це сповільнить роботу алгоритму, знищивши його перевагу над вичерпним пошуком. Дві команди знайшли розумніші способи об’єднати структуру даних Fiat-Naor і отримали алгоритми для вирішення проблем стиснення, які працювали на всіх вхідних даних і залишалися швидшими, ніж вичерпний пошук.

Деталі двох алгоритмів дещо відрізняються. Те, що належить Іланго та його співавторам, є швидшим, ніж вичерпний пошук, навіть якщо ви обмежите пошук найпростішими можливостями, і воно стосується всіх проблем стиснення — обмеженої в часі складності Колмогорова, проблеми мінімального розміру схеми та багатьох інших. Але основна ідея була однаковою для обох алгоритмів. Методи криптографії довели свою цінність у цій новій сфері.

Інверсійна конвергенція

Нове підтвердження нерівномірних алгоритмів викликає природне запитання: а як щодо однорідних алгоритмів? Чи є спосіб вирішити проблеми стиснення швидше, ніж вичерпний пошук із їх використанням?

Нещодавній ряд результатів свідчить про те, що будь-який такий алгоритм буде еквівалентним єдиному алгоритму для інвертування довільних функцій — те, чого криптографи безуспішно шукали десятиліттями. Через це багато дослідників вважають таку можливість малоймовірною.

«Я був би дуже здивований», — сказав Сантанам. «Це потребує абсолютно нової ідеї».

Але Аллендер сказав, що дослідники не повинні скидати з рахунків цю можливість. «Для мене хороша робоча гіпотеза полягає в тому, що якщо є неуніфікований спосіб зробити щось, то, швидше за все, є уніфікований спосіб», — сказав він.

У будь-якому випадку ця робота змусила теоретиків складності зацікавитися старими питаннями криптографії. Юваль Ішай, криптограф із Техніону в Хайфі, Ізраїль, сказав, що саме це робить його найбільш захоплюючим.

«Я дуже радий бачити таке зближення інтересів між різними спільнотами», – сказав він. «Я думаю, що це чудово для науки».