Teoretyczne informatyka cr.crypto-security

2

Macierz ma wymiar n × n ( n - 1 ) . Chcemy wypełnić A za pomocą liczb całkowitych od 1 do n włącznie.AAAn×n(n−1)n×n(n−1)n \times n(n-1)AAA111nnn Wymagania: Każda kolumna jest permutacją 1 , … , n .AAA1,…,n1,…,n1, \dots, n Żadna submatrix utworzona z dwóch rzędów nie może mieć identycznych kolumn.AAA …

11 co.combinatorics cr.crypto-security coding-theory

1

Stan badań nad atakami zderzeniowymi SHA-1

Bezpieczeństwo SHA-1 zostało omówione, ponieważ algorytm znajdowania kolizji został po raz pierwszy opublikowany w CRYPTO 2004, a następnie został ulepszony. Wikipedia wymienia kilka odniesień , jednak wydaje się, że najnowsze badania opublikowane (a później wycofane) na ten temat miały miejsce w 2009 r. (Cameron McDonald, Philip Hawkes i Josef Pieprzyk …

11 cr.crypto-security hash-function cryptographic-attack

2

symulacja w linii prostej

Czy jakieś ciało zna jakieś dobre odniesienie do znaczenia symulacji liniowej? Obecnie jestem głęboko w strukturze Universal Composability (UC) Canetti, ale nie mogę znaleźć żadnego dobrego odniesienia do znaczenia symulacji w linii prostej. Każda pomoc jest mile widziana.

11 cr.crypto-security

7

Jak informatyka teoretyczna odnosi się do bezpieczeństwa?

Kiedy myślę o oprogramowaniu, które nie jest bezpieczne, myślę, że jest ono „zbyt przydatne” i może zostać wykorzystane przez napastnika. W pewnym sensie zabezpieczenie oprogramowania to proces zmniejszania jego użyteczności. W informatyce teoretycznej nie pracujesz w prawdziwym świecie. Czy są jakieś obawy związane z bezpieczeństwem podczas pracy z czystą teorią? …

11 cr.crypto-security big-picture

1

Czy możemy skonstruować k-mądrą niezależną permutację na [n], używając tylko stałego czasu i przestrzeni?

Niech k>0k>0k>0 będzie stałą stałą. Biorąc pod uwagę liczbę całkowitą nnn , chcemy skonstruować permutację σ∈Snσ∈Sn\sigma \in S_n tak aby: Konstrukcja wykorzystuje stały czas i przestrzeń (tj. Wstępne przetwarzanie zajmuje stały czas i przestrzeń). Możemy użyć randomizacji. Biorąc pod uwagę i∈[n]i∈[n]i\in[n] , σ(i)σ(i)\sigma(i) można obliczyć w stałym czasie i przestrzeni. …

10 cc.complexity-theory ds.algorithms cr.crypto-security derandomization k-wise-independence

2

Funkcje jednokierunkowe a doskonale wiążące zobowiązania

Jeśli istnieją OWF, możliwe jest statystycznie wiążące zobowiązanie do bitu. [1] Czy wiadomo, że jeśli istnieją OWF, możliwe jest doskonale wiążące zaangażowanie bitów? Jeśli nie, to czy istnieje między nimi znana czarna skrzynka? [1] http://en.wikipedia.org/wiki/Pseudorandom_generator_theorem i http://en.wikipedia.org/wiki/Commitment_scheme#Bit-commitment_from_a_pseudo-random_generator

10 cr.crypto-security one-way-function

2

Czy kryptologowie odradzają rejestrom przesuwnym liniowe sprzężenie zwrotne?

Katz i Lindell wspominają w swojej książce, że LFSR są okropne jako podstawa dla generatorów pseudolosowych i zalecają, aby nie były już używane (cóż, zalecają również, aby ludzie używali szyfrów blokowych zamiast szyfrów strumieniowych). Widzę jednak na przykład, że jeden z szyfrów w portfolio estream ( ziarno , ukierunkowane na …

10 soft-question cr.crypto-security pseudorandom-generators

1

Zredukowanie podstawowych produktów faktoringowych do faktoringowych liczb całkowitych (w przeciętnym przypadku)

Moje pytanie dotyczy równoważności bezpieczeństwa różnych kandydujących funkcji jednokierunkowych, które można zbudować w oparciu o twardość faktoringu. Zakładając problem FAKTORING: [Biorąc pod uwagę dla losowych liczb pierwszych , znajdź , ]P , Q < 2 n P QN.= PQN=PQN = PQP., Q < 2nP,Q<2nP, Q < 2^nP.PPQQQ funkcja nie może …

10 reference-request cr.crypto-security nt.number-theory average-case-complexity one-way-function

2

Motywujące rozmowy na temat podstaw kryptografii

To pytanie jest w tym samym duchu, co inspirująca rozmowa dla uczniów ostatniej klasy liceum . Mój doktorat doradca poprosił mnie o przeprowadzenie inspirującej rozmowy dla nowego mgr inż. studenci Tematem są podstawy kryptografii , co najlepiej ilustruje książka Goldreicha . Rozmowa zajmie około godziny, a ja chcę zapoznać studentów …

10 reference-request soft-question cr.crypto-security teaching

1

Zależne poprawki w opartym na pomiarach uniwersalnym ślepym obliczeniu kwantowym

W Universal Blind Quantum Computation autorzy opisują protokół oparty na pomiarach, który pozwala prawie klasycznemu użytkownikowi wykonać dowolne obliczenia na serwerze kwantowym bez ujawniania prawie niczego na temat treści obliczeń. W opisie protokołu autorzy wspominają o „zestawach zależności” powiązanych z każdym kubitem, które mają być obliczone za pomocą metody opisanej …

10 quantum-computing cr.crypto-security

1

Skończona jednokierunkowa permutacja z nieskończoną domeną

Niech będzie permutacją. Zauważ, że chociaż działa w nieskończonej domenie, jego opis może być skończony. Przez opis rozumiem program, który opisuje funkcjonalność . (Jak w złożoności Kołmogorowa.) Zobacz wyjaśnienia poniżej. π ππ:{0,1}∗→{0,1}∗π:{0,1}∗→{0,1}∗\pi \colon \{0,1\}^* \to \{0,1\}^*ππ\piππ\pi Na przykład funkcja NOT jest jedną z takich permutacji: funkcja NOT (x) Niech y …

10 cc.complexity-theory co.combinatorics cr.crypto-security descriptive-complexity one-way-function

1

Światy, w stosunku do których nie istnieją „nietykalne generatory”

Niewrażliwe generatory są zdefiniowane następująco: Niech będzie relacją NP, a M będzie maszyną, która akceptuje L ( R ) . Nieformalnie program jest niewrażliwym generatorem, jeśli na wejściu 1 n wytwarza pary instancji-świadka ( x , w ) ∈ R , z | x | = n , zgodnie z …

10 cc.complexity-theory cr.crypto-security oracles relativization kolmogorov-complexity

1

Czy losowa wyrocznia może zmienić, które problemy TFNP są średnio trudne?

Zastanawiałem się nad następującym pytaniem w różnych momentach, odkąd widziałem to pytanie w kryptografii . Pytanie Pozwolić RRRbyć relacją TFNP . Czy losowa wyrocznia może pomóc P / poli w przełamaniu z nieistotnym prawdopodobieństwem? Bardziej formalnie, RRR \newcommand{\Pr}{\operatorname{Pr}} \newcommand{\E}{\operatorname{\mathbb{E}}} \newcommand{\O}{\mathcal{O}} \newcommand{\Good}{\mathsf{Good}} Robi dla wszystkich algorytmów P / poli , \ …

9 cr.crypto-security relativization advice-and-nonuniformity search-problem random-oracles

2

Dlaczego większość kryptografii zależy od dużych par liczb pierwszych, a nie innych problemów?

Większość obecnych metod kryptograficznych zależy od trudności faktorowania liczb, które są iloczynem dwóch dużych liczb pierwszych. Jak rozumiem, jest to trudne tylko tak długo, jak długo metoda zastosowana do wygenerowania dużych liczb pierwszych nie może być użyta jako skrót do faktoryzacji wynikowej liczby złożonej (a samo faktoring dużych liczb jest …

9 cr.crypto-security primes

2

Konsekwencje OWF dla złożoności

Powszechnie wiadomo, że istnienie funkcji jednokierunkowych jest konieczne i wystarczające dla dużej części kryptografii (podpisy cyfrowe, generatory pseudolosowe, szyfrowanie kluczem prywatnym itp.). Moje pytanie brzmi: jakie są teoretyczne konsekwencje istnienia funkcji jednokierunkowych? Na przykład sugerują to OWFN P ≠ PN.P.≠P.\mathsf{NP}\ne\mathsf{P}, B P P = PbP.P.=P.\mathsf{BPP}=\mathsf{P}, i C Z K = …

9 cc.complexity-theory reference-request complexity-classes cr.crypto-security one-way-function

Pytania otagowane jako cr.crypto-security