Pytania otagowane jako zero-knowledge

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 …
1
Dlaczego Feige-Fiat-Shamir nie jest zerową wiedzą bez znaków?
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 mam nadzieję, że dobrze to zrobię). Zacznijmy od prostszego schematu: niech nnn będzie …
1
Interaktywny dowód dla HORN-SAT?
Czy istnieje sposób, w jaki przysłowie może przekonać weryfikatora, że ​​niektóre wyrażenia HORN-SAT są zadowalające? Oczywiście może się to wydawać głupie, ponieważ istnieją algorytmy czasu liniowego dla HORN-SAT. Z drugiej strony HORN-SAT jest P-zupełny, co oznacza, że ​​nie ma algorytmów przestrzeni logów, chyba że P = L. W związku z …
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.