# Tag Info

0

After lots of additional googling I have found some answers: These lecture notes, slides 12 through 23; in particular slide 22, which presents a ZK proof of knowledge of five moves; This paper by Ronald Cramer, Ivan Damgård and Philip MacKenzie, that presents a ZK proof (p. 365) of four moves. Denoting the order of the group by p, both of these have ...

0

To prove "the same" relation, just use the same response of $\Sigma$-protocol for each $s_i$ in relations for $Y$, $Z$ and $s_i \in \{0,1\}$. This technique was suggested by Chaum, Evertse, de Graaf in Eurocrypt'87 paper. To prove OR relation, one would split the challenge, prove the valid part and simulate the false one. See Cramer, Damgaard, Schoenmakers ...

2

There are two answers. One, go non-interactive with the Fiat-Shamir transform. This requires the Random Oracle Model (ROM) to analyse, but the ROM is standard enough in cryptography and ROM proofs have been used in practice for long enough that this shouldn't worry you. It gets you full ZK, curiously enough for the exact same reason that plain Schnorr is ...

1

Soundness usually means "you can't prove a false statement". There are different ways to formalise this but usually the probability of an efficient algorithm coming up with a false statement and a proof that verifies is negligible in some parameter (such as the length of the statement). Soundness can be defined for any proof scheme, including ones that are ...

2

The common reference string in NIZK does not have to be uniformly distributed. It is to be sampled from whatever distribution the NIZK protocol specifies. However, the common random string in NIZK does have to be uniformly distributed, and the setup strings in NIZK also have to be uniformly distributed.

2

I believe a zero knowledge proof that $-1$ is a quadratric nonresidue would accomplish that. If we know that $n$ has two prime factors, and that $n \equiv 1 \pmod{4}$, then $n$ is either a product of two primes both $1 \bmod 4$, or two primes both $3 \bmod 4$. If it were the former, then $-1$ is a QR modulo $p$, and $-1$ is a QR modulo $q$, and hence $-1$ ...

Top 50 recent answers are included