Minimalny koszt komunikacji dla zerowych dowodów wiedzy o trzech kolorach

11

Dowód Goldreicha i in., Że trzy kolory mogą mieć zerowe dowody wiedzy, wykorzystuje bitowe zaangażowanie w całe zabarwienie wykresu w każdej rundzie [1]. Jeśli wykres ma wierzchołków i krawędzie, bezpieczne hash ma bitów i szukamy błędów prawdopodobieństwo , całkowity koszt komunikacji $n$ $e$ $b$ $p$

O (b mi n \log (1 / p))

$O(ben \log(1/p))$

ponad rund. Używając stopniowo ujawnianego drzewa Merkle, całkowitą komunikację można zredukować do kosztem zwiększenia liczby rund do . $O(1)$ $O(be \log n \log (1/p))$ $O(\log n)$

Czy można to zrobić lepiej, zarówno pod względem całkowitej komunikacji, jak i liczby rund?

http://www.wisdom.weizmann.ac.il/~oded/X/gmw1j.pdf

Edycja : Podziękowania dla Ricky'ego Demera za wskazanie brakującego czynnika . $e$

communication-complexity zero-knowledge

— Geoffrey Irving
źródło

3

Oto właściwy papier do moich celów:

Joe Kilian, „Uwaga na temat skutecznych dowodów i argumentów o zerowej wiedzy”. http://people.csail.mit.edu/vinodv/6892-Fall2013/efficientargs.pdf

Aby uzyskać najsilniejszy wynik, musimy zaakceptować zero argumentów wiedzy zamiast dowodów (dowcip związany z obliczeniami); to mnie interesuje, ale nie znałem terminologii.

Zakładając wystarczające założenia kryptograficzne, artykuł podaje zero argumentów wiedzy przy całkowitej komunikacji dla . $O(b \log^c n \log (1/p))$ $c = O(1)$

Wynik ten został zaostrzony do rund Ishai i wsp., „On Efficient Zero-Knowledge PCPs”, http://www.cs.virginia.edu/~mohammad/files/papers/13%20ZKPCPs.pdf . $O(1)$

— Geoffrey Irving
źródło

Myślę, że lepiej jest usunąć tę odpowiedź i zaktualizować oryginalną, aby była poprawną odpowiedzią.

— Kaveh

2

Aktualizacja : Ta odpowiedź jest nieaktualna w mojej innej odpowiedzi, z całkowicie polilogarytmicznymi granicami z odpowiednich odniesień.

Po namyśle nie trzeba stopniowo odsłaniać drzewa Merkle, więc niższa wersja komunikacyjna nie wymaga dodatkowych rund. Kroki komunikacji są

Przysłowie P losuje swoje zabarwienie, zamienia je w (solone) drzewo Merkle i wysyła korzeń do weryfikatora V.
V wybiera losową krawędź i wysyła ją do P. $e$
P wysyła ścieżki drzewa Merkle od katalogu głównego do każdego punktu końcowego od do V. $e$

Daje to komunikację przez rundy . $O(be \log n \log (1/p))$ $O(1)$

Aktualizacja: Oto szczegóły budowy drzewa Merkle. Dla uproszczenia, rozwinąć wykres mieć dokładnie wierzchołków dodając kilka odłączonych węzłów (nie są one skuteczne trzy zabarwienia lub zerową wiedzę). Przyjmij bezpieczną funkcję skrótu, przyjmującą dane o dowolnej wielkości i generujące bitowe dane wyjściowe. Dla każdego drzewa Merkle prover wybiera losowe bity , po jednym dla każdego liścia i nonleaf drzewa binarnego. Na liściach mieszamy kolor połączony z nonce, aby uzyskać wartość liścia. Na każdym nonleaf łączymy wartość dwójki potomnej z nonce nonceaf, aby uzyskać wartość nonleaf. $2^a$ $b$ $2^{a+1}-1$ $b$

W pierwszej rundzie prover wysyła tylko wartość root, która nie dostarcza informacji, ponieważ jest mieszana z nonce root. W trzeciej rundzie nie są przekazywane żadne informacje o żadnym nierozwiniętym węźle w drzewie binarnym, ponieważ taki węzeł został zaszyfrowany z nonce w tym węźle. Zakładam, że zarówno przysłowie, jak i weryfikator są ograniczone obliczeniowo i nie mogą złamać skrótu.

Edycja : Podziękowania dla Ricky'ego Demera za wskazanie brakującego czynnika . $e$

— Geoffrey Irving
źródło

Krok 1 dałby weryfikatorowi bardzo dokładny sposób przetestowania przypuszczeń dotyczących zabarwienia go, wykorzystując tylko 6-krotność pracy kroku 1 dla jednego przypuszczenia.

$\:$ Nie widzę też żadnego sposobu na użycie drzewa Merkle obliczonego przez prover bez przejścia od dowodu do argumentu .

$\;\;\;\;$

Jak solone drzewo Merkle może być użyte do odgadnięcia koloru?

— Geoffrey Irving

1

Wysłałem odpowiedź mówiącą, dlaczego myślę, że solony Merkle Tree nie działa.

$\:$ Zamiast tego powinieneś zamienić zobowiązania dotyczące losowości kolorów w drzewo Merkle.

$\:$ Zauważam również, że wydaje się, że brakuje Ci czynnika liczbowego w złożoności komunikacji.

$\hspace{.48 in}$

1

Cóż, można wziąć pod uwagę obietnicę, że zadanie jest albo prawidłowym 3-kolorowaniem, albo [przynajmniej

δ \cdot e

$\: \delta \cdot \hspace{-0.02 in}e\:$ krawędzie mają takie same wierzchołki].

$\;\;\;$ To zmniejsza złożoność komunikacji

O (((b \cdot n) / δ) \cdot \log (n))

$\: O\hspace{.02 in}(((b\hspace{-0.04 in}\cdot \hspace{-0.04 in}n)/\delta) \cdot \log(n))\;$ .

$\;\;\;$ (ciąg dalszy ...)

1

(... nieprzerwany)

$\;\;\;$ Następnie można zastosować maszynę PCP, aby zmniejszyć standardową relację trójkolorowania do tej relacji obietnicy.

$\;\;\;$ Doprowadzenie tego pomysłu do skrajności daje uniwersalne argumenty o zerowej wiedzy .

$\;\;\;\;\;\;\;\;$

1

Ostatnio wzrosła aktywność zwięzłych, nieinteraktywnych argumentów o zerowej wiedzy. Wiadomo na przykład, jak skonstruować argument NIZK dla Circuit-SAT, gdzie długość argumentu jest bardzo małą stałą liczbą elementów grupy (patrz Groth 2010, Lipmaa 2012, Gennaro, Gentry itp., Eurocrypt 2013 itp.). W oparciu o redukcję NP możesz następnie jasno skonstruować argument za 3-kolorowością przy tej samej komunikacji.

Oczywiście jest to inny model niż twoje pierwotne pytanie - na przykład w tych argumentach długość CRS ma rozmiar liniowy i w pewnym sensie można go traktować jako część komunikacji (choć można go ponownie wykorzystać w wiele różnych argumentów).

— cryptocat
źródło

0

(To nie pasuje do komentarza.)

Myślę, że teraz widzę, jak pokazać, że twoje solenie niekoniecznie zapewnia
rzetelną weryfikację zerowej wiedzy. $\:$ Niech będzie bezpiecznym hashem. $H_0$ $\:$ Jeśli wiemy,
że może już obsłużyć dane o dowolnej długości, to niech równe , w przeciwnym razie niech będzie wynikiem zastosowania konstrukcji Merkle – Damgard do . (Zauważ, że oznacza konkatenację.) $H_0$ $H_1$ $H_0$
$H_1$ $H_0$
$||$ $\:$ Niech jest takie, że do wszystkich łańcuchów 3-bitowe i , dla wszystkich $H_2$

$x$ $z$ -bit $\; ((3\hspace{-0.05 in}\cdot \hspace{-0.05 in}b)\hspace{-0.03 in}+\hspace{-0.02 in}6)$ $\;$ łańcuchy , dla łańcucha taki, że $y$
$m$ $\;\;\;\;\; m \:\: = \:\: x\:||\:111...[b\text{ of them}].\hspace{-0.04 in}.\hspace{-0.04 in}.111\:||\:y\:||\:z \;\;\;\;\;$ ,
jeden ma $\;\;\;\;\; H_2(m) \;\; = \;\; x\:||\:\:111...[b\text{ of them}].\hspace{-0.04 in}.\hspace{-0.04 in}.111\:||\:H_{\hspace{-0.02 in}1}(m)\:||\:z \;\;\;\;\;$ .

i

Dla wszystkich łańcuchów 3-bitowych , dla wszystkich soli $x$ $r\hspace{-0.02 in}$ , dla ciągu który wynika z solenia pomocą $m$ $x$ $r\hspace{-0.02 in}$ Jeżeli jest nie w postaci omówione powyżej, a następnie $m$
$\;\;\;\;\; H_2(m) \:\: = \:\: x\:||\:\:111...[b\text{ of them}].\hspace{-0.04 in}.\hspace{-0.04 in}.111\:||\:H_{\hspace{-0.02 in}1}(m)\:||\:x \;\;\;\;\;$ .

i

dla wszystkich łańcuchów które nie mają żadnej z tych dwóch form, $m$
$H_2(m) \:\: =$
$[b\hspace{-0.04 in}+\hspace{-0.05 in}3 \text{ bits whose values don't matter}]\:||\:H_{\hspace{-0.02 in}1}(m)\:||\:[3 \text{ bits whose values don't matter}]\;\;\;\;\;$ .

.

Ponieważ w każdym przypadku występuje w tym samym miejscu, każde zderzenie w jest również zderzeniem w . $H_1$ $H_2$ $H_1$ $\:$ Dzięki bezpieczeństwu Merkle-Damgarda każda kolizja w może być skutecznie przekształcona w kolizję w . $H_1$
$H_0$ $\:$ Zatem, jeśli jest odporny na kolizję, wówczas . Jeśli jednak liczba wierzchołków jest potęgą dwóch, to sprawdzając 3 bity na każdym końcu skrótu korzenia, można ustalić, czy początkowe i końcowe wierzchołki otrzymały ten sam kolor z prawdopodobieństwem błędu mniejszym niż . $H_0$ $H_2$

$1/(2^{(b-1)})$

Nie jestem pewien, czy podążam za twoją notacją, ale wygląda na to, że argumentujesz, że możesz wziąć mój szkic i uzupełnić szczegóły w oczywiście głupi sposób, tworząc w ten sposób niepewny system. Dodam czystszą bezpieczną wersję szczegółów do mojej odpowiedzi.

— Geoffrey Irving

H_{2}

$H_2$

$\:$ Wszystko inne było

$\hspace{1.71 in}$ co szczerze myślałem, że masz na myśli.

$\;\;\;\;$

Daj mi znać, czy szczegółowe informacje dodane do mojej odpowiedzi są jasne. Całkiem możliwe, że coś mi umknęło, a moja konstrukcja jest naprawdę zepsuta.

— Geoffrey Irving