Pytania oznaczone «cr.crypto-security»

Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane...

Czy można przekształcić CNF w inny CNF Ψ ( C ), taki jak?CC\mathcal CΨ(C)Ψ(C)\Psi(\mathcal C) Funkcja może być obliczona w czasie wielomianowym z jakiegoś tajnego parametru losowego r .ΨΨ\Psirrr ma rozwiązanie wtedy i tylko wtedy, gdy C ma rozwiązanie.Ψ(C)Ψ(C)\Psi(\mathcal C)CC\mathcal C Każde...

O ile mi wiadomo, większość implementacji generowania liczb pseudolosowych w praktyce wykorzystuje metody, takie jak rejestry sprzężenia zwrotnego z przesunięciem liniowym (LSFR) lub te algorytmy „Mersenne Twister”. Chociaż zdają wiele (heurystycznych) testów statystycznych, nie ma teoretycznych...

Próbuję zrozumieć złożoność funkcji wyrażanych przez bramki progowe, co doprowadziło mnie do . W szczególności interesuje mnie to, co obecnie wiadomo na temat uczenia się w T C 0 , ponieważ nie jestem ekspertem w tej dziedzinie.TC0TC0\mathsf{TC}^0TC0TC0\mathsf{TC}^0 Do tej pory...

często mówi się, że używając algorytmu MD5 do podpisywania dowolnych informacji, wspólny sekret musi znajdować się na końcu.

Pytanie zadane mi przez Grega Kuperberga. Zastanawiam się, czy są jakieś prace, które definiują i badają złożoność klas języków dopuszczających różnego rodzaju dowody wiedzy . Klasy takie jak SZK i NISZK są niezwykle naturalne z punktu widzenia złożoności, nawet jeśli całkowicie zapomnieliśmy o...

Powszechnie używane algorytmy haszujące hasła działają dzisiaj tak: Zasol hasło i wprowadź je do KDF. Na przykład przy użyciu PBKDF2-HMAC-SHA1 proces mieszania hasła toDK = PBKDF2(HMAC, Password, Salt, ...) . Ponieważ HMAC jest 2-okrągłym skrótem z wyściełanymi klawiszami, a SHA1 szereg permutacji,...

Funkcja jest jednokierunkowa, jeśli f można obliczyć za pomocą algorytmu wielomianowego czasu, ale dla każdego losowego algorytmu wielomianowego czasu A ,f:{0,1}∗→{0,1}∗f:{0,1}∗→{0,1}∗f \colon \{0, 1\}^* \to \{0, 1\}^*fffAAA Pr[f(A(f(x)))=f(x)]<1/p(n)Pr[f(A(f(x)))=f(x)]<1/p(n)\Pr[f(A(f(x)))...

Czytam klasyczny utwór „Twardość kontra losowość” Nisana i Wigdersona. Niech B = { 0 , 1 }b={0,1}B=\{0,1\} , a ustalenie funkcją l : N → Nl:N.→N.l\colon \mathbb{N} \to \mathbb{N} . Określają one rodzinę funkcji G = { Gn: Bl ( n )→ B.n}sol={soln:bl(n)→bn}G = \{G_n : B^{l(n)} \to B^n\} być...

Załóżmy, że masz dwóch arbitralnie silnych uczestników, którzy sobie nie ufają. Mają dostęp do bitowego zaangażowania (np. Zapieczętowane koperty zawierające dane, które jeden gracz może przekazać drugiemu, ale których nie można otworzyć, dopóki pierwszy gracz nie da drugiemu klucza). Czy możesz to...

Blum, Micali i Feldman (BFM) przedstawiają nowy (kryptograficzny) model, w którym wszystkie strony (uczciwe lub przeciwne) mają dostęp do niektórych ciągów znaków. Zakłada się, że ciąg jest wybrany zgodnie z pewną dystrybucją (zwykle równomierną dystrybucją) przez zaufaną stronę. Nazywa się to...

Wiele kryptosystemów z kluczem publicznym ma pewnego rodzaju sprawdzalne zabezpieczenia. Na przykład kryptosystem Rabin jest tak samo trudny jak faktoring. Zastanawiam się, czy istnieje taki rodzaj możliwego do udowodnienia bezpieczeństwa dla kryptosystemów tajnych kluczy, takich jak AES. Jeśli...

Sprawdzam jakiś model kryptograficzny. Aby pokazać jego nieadekwatność, opracowałem wymyślony protokół oparty na izomorfizmie grafowym. Zakładanie istnienia algorytmów BPP zdolnych do generowania „trudnych wystąpień problemu z izomorfizmem grafów” jest „powszechne” (a jednak kontrowersyjne!)....

O ile wiem, prawie wszystkie implementacje QKD wykorzystują algorytm CASCADE Brassarda i Salvaila do korekcji błędów. Czy to naprawdę najbardziej znana metoda poprawiania błędów we wspólnej sekwencji losowych kubitów, czy może jest lepsza propozycja, aby zamiast tego stosować implementacje...

Rozważ mało pojedynczo połączoną listę w czysto funkcjonalnym otoczeniu. Jego pochwały śpiewano ze szczytów górskich i nadal będą śpiewane. Zajmę się tutaj jedną z wielu jego mocnych stron i pytaniem, w jaki sposób można ją rozszerzyć na szerszą klasę czysto funkcjonalnych sekwencji opartych na...

W artykule zatytułowanym „On Deniability in Common Reference String and Random Oracle Model” Rafael Pass pisze: Zauważamy, że udowadniając bezpieczeństwo zgodnie ze standardową definicją zerowej wiedzy w modelu RO [Random Oracle], symulator ma dwie zalety w stosunku do zwykłego symulatora...

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...

W rozdziale 10 HAC (10.4.2) widzimy dobrze znany protokół identyfikacyjny Feige-Fiat-Shamir oparty na dowodzie zerowej wiedzy przy użyciu (przypuszczalnej) trudności w wyodrębnieniu modulo pierwiastków kwadratowych z kompozytu, który jest trudny do uwzględnienia. Podam schemat własnymi słowami (i...

W małym algorytmie szyfrowania : Różne wielokrotności stałej magicznej służą do zapobiegania prostym atakom opartym na symetrii rund. Stała magiczna, 2654435769 lub 9E3779B9 16, jest wybrana jako , gdzie ϕ jest złotym współczynnikiem.232/ϕ232/ϕ2^{32}/ \phi Jakie właściwości ma , dzięki czemu...

Koncepcja tajnego schematu udostępniania jest często przypisywana Shamirowi (A. Shamir, How to share a secret , Comm. ACM, 22 (1979), str. 612-613.) I Blakey (GR Blakey, Zabezpieczanie kluczy kryptograficznych , w Proc. NCC, vol. 48, 1979, ss. 313–317.). Ogólny pomysł jest taki, że niektóre tajne...