înregistrare Logare
Puncte:2
avatar Crypto

Extinderea dovezii OR la ​​mai mult de două afirmații

drapel cn
wattlab

Am citit despre protocoalele sigma, în special despre OR-Proof.

Multe exemple iau în considerare doar două afirmații și oferă o modalitate de a spune că una dintre afirmații este validă, dar nu care. De exemplu această întrebare dovada de cunoștințe zero a enunțurilor disjunctive (demonstrații SAU), sau protocolul 3 din acest articol Dovezi de cunoștințe zero cu protocoale Sigma, secțiunea 4 a acestei lucrări Pe Σ-protocoale iar acest 2.4 pe aceste diapozitive Σ-protocoale.

Aș dori să extind acest lucru la 1 din $N$ afirmații (în loc de 1 din 2 din toate exemplele pe care le-am găsit). Multe lucrări se referă Dovezi de cunoaștere parțială și simplificate Proiectarea protocoalelor de ascundere a martorilor. Am încercat să-l înțeleg complet pentru a implementa un 1 din $N$ sau-protocol dar fara noroc. Partajarea secretă este introdusă, după cum am înțeles, pentru a o face $t$ din $N$, introducând acțiuni, făcându-mi ceva mai complicat.

Pentru protocolul 1 din 2, o singură provocare este trimisă verificatorului făcută din însumarea provocării „corecte” și a unei provocări „aleatorie”. Aici cred că trebuie să aibă loc extinderea la provocări mai „aleatoare”.

Este posibil să extindeți protocolul la 1 din $N$ fără a folosi partea de partajare secretă?

90
0 + 0
Mark avatar
drapel ng
Mark
Nu sunt deloc familiarizat cu asta, dar nu este posibil să regrupez $P_1\lor P_2\lor \dots P_k$ ca $(P_1\lor \dots P_{\lfloor k/2\rceil})\lor(P_ {\lfloor k/2\rceil+1}\lor\dots\lor P_k)$, dovediți fiecare dintre „demonstrațiile la jumătate” și recurgeți?
0
Răspunde
Puncte:2
Geoffroy Couteau avatar Crypto
drapel cn
Geoffroy Couteau

Dacă vrei doar să te extinzi la $1$ din $N$, este suficientă o modificare foarte simplă a protocolului cu care ești familiarizat: o singură provocare $e$ este trimis celui care dovedește, iar cel care dovedește poate alege liber $N$ valorile $(e_1, \cdots, e_N)$ astfel încât $\sum_{i=1}^N e_i = e$. Concret, asta înseamnă că dacă $i$-a afirmație este cea pentru care dovatorul are un martor, o vor alege $(e_1, \cdots, e_{i-1}, e_{i+1}, \cdots, e_N)$ uniform la întâmplare în primul pas și la primirea provocării $e$ de la verificator, vor defini $e_i \gets e - \sum_{j\neq i} e_j$.

0 + 0
Vadym Fedyukovych avatar
drapel in
Vadym Fedyukovych
Cu alte cuvinte, dovediți o afirmație adevărată și simulați toate celelalte. Începeți prin a alege la întâmplare provocările $N-1$ pentru simulare și mai târziu calculați provocarea potrivită pentru demonstrare.
0
Răspunde
drapel cn
wattlab
Frumos, sună ușor de făcut. Plănuiesc să aplic euristica Fiat Shamir pentru a nu-l face interactiv, îl voi rezolva și îl voi posta aici. Mă întrebam, cu acest protocol 1-din-N, este garantat că una dintre afirmații este corectă? Sau ar putea un demonstrator să facă toate afirmațiile false și să susțină că „1 din N” este corect?
0
Răspunde
Geoffroy Couteau avatar
drapel cn
Geoffroy Couteau
Se garantează că cel puțin una dintre declarații este corectă și că cel care dovedește cunoaște martorul pentru cel puțin una dintre afirmațiile corecte. Nu este posibil să pretindem în mod fals că cel puțin una dintre afirmațiile N este corectă.
0
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.