Konsekwencje faktoringu w P?

Faktoring nie jest znany jako NP-zupełny. To pytanie dotyczyło konsekwencji faktoringu jako NP-zupełnego. Co ciekawe, nikt nie pytał o konsekwencje faktoringu w P (być może dlatego, że takie pytanie jest banalne).

Więc moje pytania to:

Jakie byłyby teoretyczne konsekwencje faktoringu w P? Jak taki fakt wpłynie na ogólny obraz klas złożoności?
Jakie byłyby praktyczne konsekwencje faktoringu w P? Nie mów, że transakcje bankowe mogą być zagrożone, już znam tę banalną konsekwencję.

cc.complexity-theory cr.crypto-security conditional-results factoring Giorgio Camerani
źródło

Kilka dni temu zadałem podobne pytanie: „Jaka jest moc P przy wyroczni faktoryzacji liczb całkowitych?” cstheory.stackexchange.com/questions/4765/…

Marzio De Biasi

Również powiązane: Jakie są konsekwencje faktoringu jako NP-zupełne?

Kaveh

@Kaveh, pytanie już prowadzi do tego pytania.

Peter Taylor

Odpowiedzi:

Nie ma praktycznie żadnych teoretycznych konsekwencji złożoności faktoringu w P. Oznacza to, że nie ma dobrych uzasadnień dla faktoryzacji trudnych, poza tym, że do tej pory nikt nie był w stanie go złamać.

Faktoring w czasie wielomianowym umożliwiłby przejmowanie pierwiastków kwadratowych nad (a także o wiele bardziej ogólną klasę pierścieni) i dałby algorytmy czasu wielomianowego dla szeregu innych problemów teoretycznych, dla których wąskie gardło algorytm jest obecnie faktoring. $Z_n$

Jeśli chodzi o praktyczne konsekwencje, transakcje bankowe prawdopodobnie nie stanowią większego problemu - gdy tylko wiadomo było, że faktoring był w P, banki przełączyły się na inny system, prawdopodobnie powodując jedynie krótki okres opóźnień zaimplementowano. Dekodowanie przeszłych transakcji bankowych prawdopodobnie nie spowodowałoby poważnych problemów dla banków. Znacznie poważniejszym problemem jest to, że cała komunikacja, która wcześniej była chroniona przez RSA, byłaby teraz zagrożona odczytaniem.

Peter Shor
źródło

Trochę nie na temat, ale w as soon as it was known that factoring was in P, the banks would switch to some other systemwiększości jest to pobożne życzenie. W grudniu odkryłem, że firma, która nie robi nic oprócz przetwarzania danych karty kredytowej, używa wariantu Vigenère z kluczem krótszym niż niektóre serie znanego zwykłego tekstu. Co gorsza, dyrektor techniczny firmy nie uwierzyłby mi, że był niepewny, dopóki nie wysłałem mu kodu ataku. MD5, mimo że jest powszechnie uważany za zepsuty, jest nadal szeroko stosowany w bankowości.

Peter Taylor,

@PeterTaylor, gdy tylko wiadomo, że faktoring był w P, banki przestawiłyby się na inny system, który jest w dużej mierze życzeniem ”. Przy obecnej niskiej cenie pamięci Flash całkowicie możliwe jest stworzenie rozwiązania One Time Pad dla w bankowości użytkownicy od czasu do czasu przechodzą do bankomatu, aby pobierać dodatkowe losowe bajty. RSA jest po prostu tańszy i prostszy

Flávio Botelho

Posiadanie silnych szyfrów symetrycznych nie zastąpi szyfrów asymetrycznych, choć wystarcza do niektórych określonych zadań. Występuje problem braku możliwości korzystania z podpisów cyfrowych itp.

Joe Fitzsimons

W rzeczywistości możesz mieć podpisy cyfrowe z symetrycznymi szyframi! Jest to po prostu o wiele bardziej kłopotliwe i potrzebujesz znacznie większego zaufania do zaufanej strony trzeciej. Spójrz na rozdziały 11.6 i 11.7 Podręcznika kryptografii stosowanej.

Flávio Botelho

@Flavio: Ale niezaprzeczalność nie działa w ten sam sposób, prawda?

Joe Fitzsimons,

RSA jest jednym z najważniejszych schematów szyfrowania / podpisów, które psują się, jeśli FACTORING znajduje się w P. Jednak jest ich o wiele więcej. Kilka (ale nie wszystkie) z nich opiera się na założeniu, że rozróżnianie kwadratów i modułów innych niż kwadraty w liczbie złożonej jest trudne :

I wiele innych programów. Należy jednak pamiętać, że schematy oparte na twardości dyskretnego dziennika (powiedzmy, protokół Diffie-Helmann lub schemat szyfrowania / podpisu Elgamal ) będą nadal bezpieczne.

MS Dousti
źródło

Wydaje mi się bardzo prawdopodobne, że jeśli faktoring jest w P, to problem z logiem dyskretnym również. Z pewnością odwrotność jest prawdziwa.

Joe Fitzsimons,

@Joe: Mam takie same odczucia, ale czy jest jakiś dowód lub dowód matematyczny?

MS Dousti

a^{p q} \equiv a^{p + q - 1} (mod p q)

$a^{pq} \equiv a^{p+q-1}~(\mbox{mod } pq)$

c_{a} = \log_{N} (a^{N} mod N)

$c_a = \log_N(a^N \mbox{mod }N)$

p = x + y

$p = x + y$

q = x - y

$q = x - y$

x = \frac{c_{a} + 1}{2}

$x = \frac{c_a + 1}{2}$

y = \sqrt{x^{2} - N}

$y = \sqrt{x^2 - N}$

@Joe: Bardzo interesujące! Twój komentarz zmotywował mnie do

głębszego wniknięcia w ten temat i doszedł

Miejmy nadzieję, że kryptowaluty oparte na kratach pozostaną bezpieczne.

Antimony

$P$

Mohammad Al-Turkistany
źródło