Które języki zostały pomyślnie kryptograficznie trapdooredowane?

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.

Ważne jest, aby odróżnić funkcje zapadni od szyfrowania kluczem publicznym. Podczas gdy funkcje zapadni dają schematy szyfrowania kluczem publicznym, niektórzy z wymienionych kandydatów są znani tylko z szyfrowania kluczem publicznym i niekoniecznie dają ci funkcje zapadni. W rzeczywistości Gertner, Malkin i Reingold pokazują, że nie istnieje konstrukcja czarnej klapy funkcji zapadni z „predykatu zapadni” (którą można by traktować jako jednobitowy schemat szyfrowania klucza publicznego).

Klasycznymi przykładami funkcji zapadni są funkcje RSA i Rabin. Klasycznym przykładem predykty zapadniowej jest decyzja o kwadratycznym modulo residuosity kompozytu, ze względu na Goldwassera i Micali. Wspomniane konstrukcje z logami dyskretnymi i sieciami zapewniają bezpośrednie szyfrowanie klucza publicznego, bez przechodzenia przez funkcje zapadni.

Poniżej znajduje się (niepełna) lista konstrukcji schematów szyfrowania klucza publicznego, z których większość nie jest znana z funkcji zapadni.

• Kryptosystem klucza publicznego El Gamal (w tym warianty krzywej eliptycznej). Bezpieczeństwo opiera się na założeniu Decisional Diffie Hellman. Nie przechodzi przez funkcje zapadni (ale zobacz poniżej pozycję Peikert-Waters, aby poznać funkcję zapadni, której bezpieczeństwo opiera się na bezpieczeństwie semantycznym El Gamal).

  [Taher El Gamal: Kryptosystem klucza publicznego i schemat podpisu oparty na dyskretnych logarytmach. CRYPTO 1984: 10-18]

• Ajtai-Dwork, Regev. Bezpieczeństwo opiera się na unikalnym SVP w sieciach kratowych. Nie wiadomo, że implikuje funkcje zapadni.

  [Miklós Ajtai, Cynthia Dwork: Kryptosystem klucza publicznego o równoważności najgorszego / średniego przypadku. STOC 1997: 284-293]

  [Oded Regev: Nowe konstrukcje kryptograficzne oparte na sieci. STOC 2003: 407-416]

• Regev, Peikert. Bezpieczeństwo opiera się na trudności uczenia się z błędami (obejmuje to redukcję SVP). Nie wiadomo, że implikuje funkcje zapadni.

  [Oded Regev: w sieciach, uczenie się na błędach, losowe kody liniowe i kryptografia. STOC 2005: 84-93]

  [Chris Peikert: Kryptosystemy z kluczem publicznym od najgorszego najkrótszego problemu wektorowego: rozszerzone streszczenie. STOC 2009: 333–342]

• Peikert, Waters. Bezpieczeństwo opiera się na decyzyjnej Diffie Hellman i problemach z siecią. Wiadomo, że implikuje funkcje zapadni (poprzez stratne funkcje zapadni).

  [Chris Peikert, Brent Waters: Lossy funkcje zapadni i ich zastosowania. STOC 2008: 187-196]

• Lyubashevsky, Palacio, Segev. Bezpieczeństwo opiera się na sumach częściowych. Nie wiadomo, że implikuje funkcje zapadni.

  [Vadim Lyubashevsky, Adriana Palacio, Gil Segev: Prymitywy kryptograficzne z kluczem publicznym Zapewne tak bezpieczne, jak suma podzbiorów. TCC 2010: 382–400]

• Stehlé, Steinfeld, Tanaka, Xagawa i Lyubashevsky, Peikert, Regev. Bezpieczeństwo opiera się na twardości pierścienia LWE. Przewagą tych nad poprzednimi propozycjami jest ich mniejszy rozmiar klucza. Nie wiadomo, że implikuje funkcje zapadni.

  [Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, Keita Xagawa: Wydajne szyfrowanie klucza publicznego oparte na idealnych kratach. ASIACRYPT 2009: 617-635]

  [Vadim Lyubashevsky, Chris Peikert, Oded Regev: O idealnych kratach i uczeniu się z błędami nad pierścieniami. EUROCRYPT 2010: 1-23]