Obserwacja związana z kryptografią asymetryczną jest taka, że niektóre funkcje są (uważa się) za łatwe do wykonania w jednym kierunku, ale trudne do odwrócenia. Ponadto, jeśli istnieje jakaś informacja „zapadni”, która pozwala na szybkie obliczenie operacji odwrotnej, problem staje się kandydatem do schematu kryptografii klucza publicznego.
Klasyczne problemy z zapadniami, rozsławione przez RSA, obejmują problem faktoringu i problem z dyskretnym logiem. Mniej więcej w tym samym czasie, w którym opublikowano RSA, Rabin wynalazł kryptosystem klucza publicznego oparty na znalezieniu dyskretnych pierwiastków kwadratowych (później okazało się to co najmniej tak samo trudne jak faktoring).
Inni kandydaci pojawili się na przestrzeni lat. KNAPSACK (wkrótce po RSA), „Logarytmy” krzywej eliptycznej z określonymi parametrami oraz problemy z najkrótszą podstawą kraty są przykładami problemów, których problemy z zapadnią stosowane były w innych opublikowanych schematach. Łatwo też zauważyć, że takie problemy muszą znajdować się gdzieś w NP.
To wyczerpuje moją wiedzę na temat funkcji zapadni. Wydaje się również, że wyczerpuje również listę na Wikipedii .
Mam nadzieję, że uda nam się uzyskać listę wiki wiki języków, które dopuszczają zapadnie i odpowiednią literaturę. Lista będzie przydatna. Zmieniające się wymagania kryptografii zmieniają również to, które funkcje zapadni mogą być podstawą kryptosystemów. Eksplozja pamięci na komputerach umożliwia tworzenie schematów z dużymi rozmiarami klawiszy. Wiecznie wyłaniające się widmo obliczeń kwantowych unieważnia schematy, które można przełamać wyrocznią w poszukiwaniu ukrytych abelowych podgrup. W pełni homomorficzny kryptosystem Gentry działa tylko dlatego, że odkryliśmy funkcje zapadni, które szanują homomorfizmy.
Szczególnie interesują mnie problemy, które nie są NP-Complete.