Pytania otagowane jako cr.crypto-security

Teoretyczne aspekty kryptografii i bezpieczeństwa informacji.

2
Dlaczego modułowe potęgowanie Montgomery nie jest rozważane do stosowania w faktorowaniu kwantowym?
Powszechnie wiadomo, że potęgowanie modułowe (główna część operacji RSA) jest drogie obliczeniowo i, o ile rozumiem, preferowaną metodą jest potęgowanie modułowe Montgomery'ego . Modułowe potęgowanie jest również wyraźnie widoczne w algorytmie faktoringu kwantowego i tam również jest drogie. Więc: dlaczego modułowe potęgowanie Montgomery'ego najwyraźniej nie występuje w obecnych szczegółowych podprogramach …
1
Czy istnieje lepsza niż liniowa dolna granica dla faktoringu i dziennika dyskretnego?
Czy istnieją odniesienia, które zawierają szczegółowe informacje na temat dolnych granic obwodu dla konkretnych trudnych problemów pojawiających się w kryptografii, takich jak faktoring liczb całkowitych, problem logarytmu dyskretnego z liczbami pierwszymi / złożonymi i jego wariant nad grupą punktów krzywych eliptycznych (i ich wielowymiarowych odmian abelowych) i ogólne ukryty problem …
1
Czy kryptografia ma nieodłączny koszt termodynamiczny?
Obliczenia odwracalne to model obliczeniowy, który pozwala jedynie na operacje odwracalne termodynamicznie. Zgodnie z zasadą Landauera, która stwierdza, że ​​usunięcie części informacji uwalnia ciepło dżuli, wyklucza to funkcje przejścia, które nie są jeden do jednego (np. Operatory logiczne AND i OR). Powszechnie wiadomo, że obliczenia kwantowe są z natury odwracalne, …
5
Czy można sprawdzić, czy liczba obliczalna jest wymierna czy całkowita?
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 z faktem, że nie można sprawdzić, czy dwie …
18 computability  computing-over-reals  lambda-calculus  graph-theory  co.combinatorics  cc.complexity-theory  reference-request  graph-theory  proofs  np-complete  cc.complexity-theory  machine-learning  boolean-functions  combinatory-logic  boolean-formulas  reference-request  approximation-algorithms  optimization  cc.complexity-theory  co.combinatorics  permutations  cc.complexity-theory  cc.complexity-theory  ai.artificial-intel  p-vs-np  relativization  co.combinatorics  permutations  ds.algorithms  algebra  automata-theory  dfa  lo.logic  temporal-logic  linear-temporal-logic  circuit-complexity  lower-bounds  permanent  arithmetic-circuits  determinant  dc.parallel-comp  asymptotics  ds.algorithms  graph-theory  planar-graphs  physics  max-flow  max-flow-min-cut  fl.formal-languages  automata-theory  finite-model-theory  dfa  language-design  soft-question  machine-learning  linear-algebra  db.databases  arithmetic-circuits  ds.algorithms  machine-learning  ds.data-structures  tree  soft-question  security  project-topic  approximation-algorithms  linear-programming  primal-dual  reference-request  graph-theory  graph-algorithms  cr.crypto-security  quantum-computing  gr.group-theory  graph-theory  time-complexity  lower-bounds  matrices  sorting  asymptotics  approximation-algorithms  linear-algebra  matrices  max-cut  graph-theory  graph-algorithms  time-complexity  circuit-complexity  regular-language  graph-algorithms  approximation-algorithms  set-cover  clique  graph-theory  graph-algorithms  approximation-algorithms  clustering  partition-problem  time-complexity  turing-machines  term-rewriting-systems  cc.complexity-theory  time-complexity  nondeterminism 
1
Bitcoin i zapobieganie podwójnym wydatkom w zdecentralizowanych walutach cyfrowych
Ostatnie podejście do tworzenia zdecentralizowanej waluty internetowej, zwanej Bitcoin , wzbudza pewne zainteresowanie. Celem jest posiadanie sposobu na przelewanie waluty bez centralnego organu i bez podwójnych wydatków lub fałszowania. Ich podejście polega na tym, że wszystkie węzły w sieci próbują zweryfikować transakcję, wykonując obliczenia typu proof-of-work, a następnie transakcje o …
2
Czy w praktyce wykorzystywane są teoretycznie generatory pseudolosowe?
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 gwarancji, że wyglądają pseudolosowo, powiedzmy, na wszystkie skutecznie obliczalne testy statystyczne. Jednak metody te …
1
Mieszanie hasła przy użyciu NP pełne problemy
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, przesunięć, rotacji i operacji bitowych, zasadniczo cały proces …
1
Klasy złożoności dla dowodów wiedzy
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 zerowej wiedzy i po prostu zdefiniowaliśmy je …
2
O statusie zdolności uczenia się w
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 odkryłem: Wszystkie można wyciągnąć w quasipolynomial czasie w jednorodnym rozkładzie …
5
Czy „Funkcje jednokierunkowe” mają jakieś aplikacje poza kryptografią?
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)]&lt;1/p(n)Pr[f(A(f(x)))=f(x)]&lt;1/p(n)\Pr[f(A(f(x))) = f(x)] < 1/p(n) dla każdego wielomianu i wystarczająco dużego n , przy założeniu, że x jest wybrany równomiernie z { 0 …
2
Czy zaangażowanie bitowe daje nieświadomy transfer w modelu bezpieczeństwa opartym na teorii informacji?
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 wykorzystać do zbudowania nieświadomego protokołu przesyłania. Czy to …
1
Gdzie jest usterka w metodzie Bluma-Feldmana-Micali
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 ciągiem odniesienia , a model jest trafnie nazwany modelem …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.