Sztuczki kryptograficzne sprawiają, że trudny problem jest trochę łatwiejszy | Magazyn Quanta

Jaki jest najlepszy sposób rozwiązywania trudnych problemów? To pytanie leży w sercu poddziedziny informatyki zwanej teorią złożoności obliczeniowej. Trudno odpowiedzieć na to pytanie, ale odwróć je i będzie łatwiej. Najgorsze podejście prawie zawsze polega na próbach i błędach, które polegają na podłączaniu możliwych rozwiązań, dopóki nie zadziałają. Jednak w przypadku niektórych problemów wydaje się, że po prostu nie ma alternatyw – najgorsze podejście jest jednocześnie najlepsze.

Badacze od dawna zastanawiali się, czy rzeczywiście tak jest w ogóle, mówi Rahula Ilango, absolwent studiów teorii złożoności w Massachusetts Institute of Technology. „Można zapytać: «Czy istnieją problemy, w przypadku których zgadywanie i sprawdzanie jest po prostu optymalne?»”

Teoretycy złożoności badali wiele problemów obliczeniowych i nawet te trudne często dopuszczają jakąś sprytną procedurę lub algorytm, dzięki któremu znalezienie rozwiązania jest nieco łatwiejsze niż czysta metoda prób i błędów. Do nielicznych wyjątków należą tak zwane problemy kompresji, których celem jest znalezienie najkrótszego opisu zbioru danych.

Ale w listopadzie ubiegłego roku dwie grupy badaczy niezależnie odkryty inny algorytm rozwiązywania problemów z kompresją — taki, który jest nieco szybszy niż sprawdzanie wszystkich możliwych odpowiedzi. Nowe podejście polega na dostosowaniu algorytmu wynalezionego przez kryptografów 25 lat temu do atakowania innego problemu. Jest tylko jedno ograniczenie: musisz dostosować algorytm do rozmiaru zbioru danych.

„To naprawdę piękne i ważne wyniki” – stwierdziła Eryka Allendera, informatyk teoretyczny na Uniwersytecie Rutgers.

Definicja twardości

Nowe wyniki to najnowsze wyniki, które pozwalają zbadać kwestię badaną po raz pierwszy w Związku Radzieckim, na długo przed pojawieniem się teorii złożoności. „Zanim byłem w szkole podstawowej, formułowali to ludzie w Rosji” – powiedział Allender.

Specyficzny problem obliczeniowy badany przez sowieckich badaczy, zwany problemem minimalnego rozmiaru obwodu, jest podobny do tego, z którym nieustannie borykają się projektanci sprzętu komputerowego. Jeśli otrzymasz pełną specyfikację dotyczącą zachowania obwodu elektronicznego, czy możesz znaleźć najprostszy obwód, który wykona to zadanie? Nikt nie wiedział, jak rozwiązać ten problem bez „pereboru” – rosyjskiego słowa z grubsza odpowiadającego „wyczerpującym poszukiwaniu”.

Problem minimalnego rozmiaru obwodu jest przykładem problemu kompresji. Możesz opisać zachowanie obwodu za pomocą długiego ciągu bitów — 0 i 1 — a następnie zapytać, czy istnieje sposób na odtworzenie tego samego zachowania przy użyciu mniejszej liczby bitów. Sprawdzenie wszystkich możliwych układów obwodów zajęłoby czas, który rośnie wykładniczo wraz z liczbą bitów w ciągu.

Ten rodzaj wykładniczego wzrostu jest cechą charakterystyczną trudnego problemu obliczeniowego. Jednak nie wszystkie trudne problemy są równie trudne — niektóre mają algorytmy szybsze niż wyszukiwanie wyczerpujące, chociaż czas ich wykonywania wciąż rośnie wykładniczo. Mówiąc współcześnie, pytanie perebor brzmi, czy istnieją takie algorytmy do rozwiązywania problemów z kompresją.

W 1959 roku wybitny badacz Siergiej Jabłoński stwierdził, że udowodnił, że wyczerpujące poszukiwania naprawdę są jedynym sposobem rozwiązania problemu minimalnego rozmiaru obwodu. Ale jego dowód pozostawił pewne luki. Niektórzy badacze zauważyli wówczas te wady, ale Jabłoński był na tyle wpływowy, że zniechęcił większość innych do pracy nad kwestią pereboru.

W następnych dziesięcioleciach niewielu badaczy zajmowało się problemami kompresji, a kwestia pereboru była znana głównie jako przypis w prehistorii teorii złożoności. Szerokie zainteresowanie tą kwestią pojawiło się dopiero niedawno, gdy badacze odkryli ciekawe powiązanie między problemami z kompresją a podstawami kryptografii.

Ruch jednokierunkowy

Współczesna kryptografia wykorzystuje trudne problemy obliczeniowe w celu ochrony tajnych wiadomości. Jednak trudność obliczeniowa jest użyteczna tylko wtedy, gdy jest asymetryczna — jeśli trudno jest odszyfrować zakodowane wiadomości, ale przede wszystkim nie jest trudno je zakodować.

W każdym schemacie kryptograficznym źródłem tej asymetrii jest obiekt matematyczny zwany funkcją jednokierunkową, która przekształca wejściowe ciągi bitów w ciągi wyjściowe o tej samej długości. Biorąc pod uwagę dane wejściowe funkcji jednokierunkowej, łatwo jest obliczyć wynik, ale mając wynik, trudno jest odwrócić tę funkcję — to znaczy przeprowadzić jej inżynierię wsteczną i odzyskać dane wejściowe.

„Kryptografowie naprawdę chcieliby mieć bardzo, bardzo wydajnie obliczalne funkcje jednokierunkowe, które są naprawdę trudne do odwrócenia” – powiedział Allender. Wydaje się, że wiele funkcji matematycznych ma tę właściwość, a trudność odwracania tych funkcji wynika z pozornej trudności w rozwiązywaniu różnych problemów obliczeniowych.

Niestety, kryptografowie nie są pewni, czy którąkolwiek z tych funkcji naprawdę trudno jest odwrócić — w rzeczywistości jest możliwe, że prawdziwe funkcje jednokierunkowe nie istnieją. Ta niepewność utrzymuje się, ponieważ mają ją teoretycy złożoności walczył przez 50 lat udowodnić, że pozornie trudne problemy są naprawdę trudne. Jeśli tak nie jest i jeśli badacze odkryją superszybkie algorytmy rozwiązywania tych problemów, będzie to katastrofalne w skutkach dla kryptografii – podobnie jak nagłe skierowanie pędzących samochodów w obu kierunkach na ulicę jednokierunkową.

Chociaż wszechstronne zrozumienie trudności obliczeniowych pozostaje nieuchwytne, kryptografowie poczynili ostatnio ekscytujący postęp w kierunku ujednoliconej teorii funkcji jednokierunkowych. Jeden duży krok został zrobiony w 2020 roku, kiedy kryptolog z Uniwersytetu w Tel Awiwie Przełęcz Rafael i jego absolwent Yanyi Liu udowodnił, że funkcje jednokierunkowe są ściśle powiązane do specyficznego problemu kompresji zwanego problemem złożoności ograniczonej w czasie Kołmogorowa.

Jeśli ten jeden problem naprawdę jest trudny do rozwiązania dla większości danych wejściowych, wynik Passa i Liu daje przepis na skonstruowanie możliwej do udowodnienia trudnej funkcji jednokierunkowej — takiej, która gwarantuje bezpieczeństwo, nawet jeśli inne problemy obliczeniowe okażą się znacznie łatwiejsze niż oczekiwali badacze. Ale jeśli istnieje szybki algorytm rozwiązywania problemu złożoności ograniczonego w czasie Kołmogorowa, wówczas kryptografia jest skazana na porażkę, a każdą funkcję można łatwo odwrócić. Funkcja jednokierunkowa oparta na złożoności tego problemu jest najbezpieczniejszą możliwą funkcją — funkcją jednokierunkową, która rządzi wszystkimi.

Opieranie się na strukturach danych

Odkrycie Passa i Liu było najnowszym rozdziałem w długiej linii badań wykorzystujących teorię złożoności do lepszego zrozumienia podstaw kryptografii. Sugerowało to jednak także sposób na odwrócenie tej zależności: równoważność między problemem złożoności ograniczonej w czasie a inwersją funkcji oznacza, że ​​wgląd w każdy problem może ujawnić więcej na temat drugiego. Kryptografowie od dziesięcioleci badają algorytmy inwersji funkcji, aby lepiej zrozumieć słabe punkty ich metod szyfrowania. Badacze zaczęli się zastanawiać, czy algorytmy te mogłyby pomóc w odpowiedzi na odwieczne pytania z zakresu teorii złożoności.

Podobnie jak wiele problemów obliczeniowych, inwersję funkcji można rozwiązać poprzez poszukiwania wyczerpujące. Mając ciąg wyjściowy, po prostu podłącz każde możliwe wejście do funkcji, aż znajdziesz to, które da właściwą odpowiedź.

W 1980 roku kryptograf Martin Hellman zaczął badać, czy można zrobić coś lepiej — to samo pytanie radzieccy matematycy zadawali kilkadziesiąt lat wcześniej na temat problemów z kompresją. Piekielny człowiek odkryty że tak, jest to możliwe — pod warunkiem, że wcześniej zechcesz włożyć w to dodatkową pracę, używając obiektów matematycznych zwanych strukturami danych.

Struktura danych to zasadniczo tabela, w której przechowywane są informacje o funkcji, która ma zostać odwrócona, a jej skonstruowanie wymaga obliczenia wyników funkcji dla określonych strategicznie wybranych danych wejściowych. Wszystkie te obliczenia „mogą zająć bardzo dużo czasu” – stwierdził Ryan Williams, teoretyk złożoności w MIT. „Ale pomysł jest taki, że należy to zrobić raz, raz na zawsze”. Jeśli próbujesz odwrócić tę samą funkcję, biorąc pod uwagę wiele różnych wyników — powiedzmy, aby zdekodować wiele różnych wiadomości zaszyfrowanych w ten sam sposób — warto wykonać tę pracę z wyprzedzeniem.

Oczywiście przechowywanie tych dodatkowych informacji wymaga miejsca, więc zastosuj tę strategię do skrajności, a możesz otrzymać szybki program, który nie zmieści się na żadnym komputerze. Hellman zaprojektował sprytną strukturę danych, która umożliwiła jego algorytmowi odwracanie większości funkcji nieco szybciej niż wyszukiwanie wyczerpujące, bez zajmowania zbyt dużej ilości miejsca. Następnie w 2000 roku kryptografowie Amos Fiat i Moni Naor dużym Argumenty Hellmana do wszystkich funkcji.

Po przełomie Passa i Liu w 2020 r. te stare wyniki nagle nabrały nowego znaczenia. Algorytm Fiata-Naora może odwracać dowolne funkcje szybciej niż wyszukiwanie wyczerpujące. Czy może to również pomóc w przypadku problemów z kompresją?

Brak munduru

Pierwszymi badaczami, którzy podnieśli tę kwestię, byli teoretycy złożoności Rahula Santhanama Uniwersytetu Oksfordzkiego i jego absolwent Hanlina Rena. Zrobili to w Papier 2021 udowadniając, że problemy kompresji i inwersja funkcji były ze sobą powiązane jeszcze bardziej, niż sądzili badacze.

Pass i Liu udowodnili, że jeśli problem ograniczonej w czasie złożoności Kołmogorowa jest trudny, to inwersja funkcji również musi być trudna i odwrotnie. Jednak problemy mogą być trudne i nadal dopuszczać rozwiązania, które są nieco lepsze niż wyczerpujące poszukiwania. Santhanam i Ren wykazali, że istnieje ścisły związek pomiędzy tym, czy w przypadku jednego problemu wymagane są wyczerpujące poszukiwania, a tym, czy są one wymagane w przypadku drugiego.

Ich wynik miał różne implikacje dla dwóch szerokich klas algorytmów, które często badają badacze, zwanych algorytmami „jednolitymi” i „niejednorodnymi”. Jednolite algorytmy działają według tej samej procedury dla każdego wejścia — na przykład jednolity program do sortowania list liczb będzie działał w ten sam sposób niezależnie od tego, czy na liście będzie 20 wpisów, czy 20,000 XNUMX. Zamiast tego algorytmy niejednorodne wykorzystują różne procedury dla danych wejściowych o różnej długości.

Struktury danych wykorzystywane przez algorytm Fiata-Naora są zawsze dostosowane do konkretnej funkcji. Aby odwrócić funkcję szyfrującą 10-bitowy ciąg znaków, potrzebujesz struktury danych innej niż ta, której potrzebujesz do odwrócenia funkcji szyfrującej 20-bitowy ciąg znaków, nawet jeśli szyfrowanie odbywa się w podobny sposób. To sprawia, że ​​Fiat-Naor jest algorytmem niejednorodnym.

Wyniki Santhanama i Rena sugerują, że możliwe byłoby przekształcenie algorytmu Fiata-Naora w algorytm rozwiązywania problemów z kompresją. Jednak dostosowanie algorytmu z jednego problemu do drugiego nie było proste i nie zajęto się dalej tą kwestią.

Pass wpadł na ten sam pomysł rok później, po wysłuchaniu wykładu Fiata na temat klasycznego algorytmu podczas warsztatów poświęconych wkładowi Naora w kryptografię. „Od tamtej pory chodził mi po głowie pomysł wykorzystania inwersji funkcji” – powiedział. Później zaczął poważnie pracować nad tym problemem wraz z badaczem z Uniwersytetu w Tel Awiwie Noama Mazora.

W międzyczasie Ilango zainspirował się do zajęcia się tym problemem po dyskusjach z innymi badaczami, w tym z Santhanamem, podczas wizyty w Instytucie Teorii Informatyki Simonsa w Berkeley w Kalifornii. „To wyszło z jednej z tych bardzo nieoczekiwanych rozmów, podczas których po prostu rzucacie różnymi rzeczami” – powiedział Santhanam. Ilango później połączył siły z Williamsem i Shuichi Hirahara, teoretyk złożoności w Narodowym Instytucie Informatyki w Tokio.

Najtrudniejszą częścią było znalezienie sposobu osadzenia struktury danych będącej sercem algorytmu Fiata-Naora w niejednorodnym algorytmie rozwiązywania problemów z kompresją. Istnieje standardowa procedura wykonywania tego rodzaju osadzania, ale spowolniłaby ona algorytm i zniweczyła jego przewagę nad wyszukiwaniem wyczerpującym. Obydwa zespoły znalazły sprytniejsze sposoby na włączenie struktury danych Fiata-Naora i uzyskały algorytmy rozwiązywania problemów z kompresją, które działały na wszystkich danych wejściowych i pozostawały szybsze niż wyszukiwanie wyczerpujące.

Szczegóły obu algorytmów nieznacznie się różnią. Ten autorstwa Ilango i jego współautorów jest szybszy niż wyszukiwanie wyczerpujące, nawet jeśli ograniczysz wyszukiwanie do najprostszych możliwości i ma zastosowanie do wszystkich problemów z kompresją - ograniczonej w czasie złożoności Kołmogorowa, problemu minimalnego rozmiaru obwodu i wielu innych. Jednak podstawowa idea była taka sama dla obu algorytmów. Techniki stosowane w kryptografii sprawdziły się w tej nowej dziedzinie.

Zbieżność inwersji

Nowy dowód na niejednorodne algorytmy rodzi naturalne pytanie: co z algorytmami jednolitymi? Czy istnieje sposób na rozwiązanie problemów z kompresją szybciej niż wyczerpujące wyszukiwanie przy ich użyciu?

Niedawny ciąg wyników sugeruje, że każdy taki algorytm byłby równoważny jednolitemu algorytmowi odwracania dowolnych funkcji — jest to coś, czego kryptografowie bezskutecznie poszukiwali od dziesięcioleci. Z tego powodu wielu badaczy uważa taką możliwość za mało prawdopodobną.

„Byłbym bardzo zaskoczony” – powiedział Santhanam. „Wymagałoby to zupełnie nowego pomysłu”.

Ale Allender powiedział, że badacze nie powinni pomijać takiej możliwości. „Dla mnie dobra robocza hipoteza jest taka, że ​​jeśli istnieje niejednolity sposób wykonania czegoś, najprawdopodobniej istnieje jednolity” – powiedział.

Tak czy inaczej, praca ta sprawiła, że ​​teoretycy złożoności na nowo zainteresowali się starymi zagadnieniami kryptografii. Yuval Ishai, kryptolog z Technion w Hajfie w Izraelu, powiedział, że właśnie to jest najbardziej ekscytujące.

„Jestem naprawdę szczęśliwy, widząc tę ​​zbieżność interesów różnych społeczności” – powiedział. „Myślę, że to świetne rozwiązanie dla nauki”.