5

Yes, and in fact, Schnorr's signature scheme was originally described as a non-interactive protocol. I think the confusion around interactivity comes from the fact that the same paper first described a interactive identification scheme, which can be viewed as a specialization of the signature scheme for empty messages. In both schemes, challenges can be ...


5

There is no generic conversion, but it is a standard property of dual-mode NIZKs. Here, the CRS comes in two indistinguishable modes, where one is structured, but the other is actually a truly random string. Typically, in group-based construction, the random CRS will be a tuple of random group elements, while the structured CRS will be a DDH tuple - both ...


4

Are there any zero knowledge protocols which do not rely on a group? It depends on your definition of "relying on a group". If you mean "doesn't rely on a group-based assumption like DDH, CDH or DLog or variants thereof", then yes. If you mean "doesn't use a group at some point" then no, because such a protocol would be unimplementable because the most ...


4

Theoretically speaking it's rather easy. You simply have the key owner (the prover) perform a proof that they have the private exponent for at least one of the public keys on the list. This is a standard OR-proof which composes multiple (Sigma) Zero-Knowledge proofs. As you're using standard elliptic curve crypto the public keys will be of the form $P_i=[...


4

A ZK-SNARK is a NIZK (more precisely, a non-interactive zero-knowledge argument of knowledge in the common reference string model) which is succinct, meaning that both the proof size and the verification time grow sublinearly with the witness size. Therefore, every ZK-SNARK is in particular a NIZK (but not all NIZKs are ZK-SNARKs). Pinocchio provide a ZK-...


3

Let us see an example of how cryptographic hash functions are used in Zero-Knowledge Proof Systems. Following code written in Zokrates DSL Toolbox is an example of computing a Hash using Zero-Knowledge Proof systems. The programming instructions are compiled first. Then we will proceed to the setup of the arithmetic circuit through the setup. Then we export ...


3

This is no longer a secure commitment. Note that there should not be any way to efficiently verify if a given commitment value $c$ is to a message $m$. However, once you derive the randomness in this way, an attacker could try to guess $m$ and verify if this guess is correct by checking if $g^m\cdot h^{H(m)} = c$. Thus, this is not a secure commitment scheme....


3

I am simplifying greatly, maybe someone else can provide a more formal answer. I see that homomorphic encryption works with only numeric data. There are many ways to encode strings into integers, you can encode a string into bytes and then translate these bytes to an integer. I have read that homomorphic has scalability issues as it creates a 100x ...


3

my question is why the verifier sends a challenge, would he be convinced if the prover just sends $t=r+x$ and the verifier tests if $g^t=g^w \cdot y$ ? That is, why doesn't the prover just send $t$ and $y$? Well, anyone can pick a random $t$ and compute $y = g^t \cdot (g^w)^{-1}$. Because $g^w$ is public, this can be computed by anyone, and so wouldn't ...


3

Since you reference my answer to a very similar question, I'm assuming you already read it, so you know what the difference between ZK and ZKPoK is at a technical level. To recall briefly, though: a standard ZK proves the existence of a witness, while ZKPoK proves that the prover actually knows the witness, which is formalized by saying that there exists an ...


3

If you're using the syntax $<a, b>$ to mean dot-product, then the assumption that you make: a binary vector is the only vector where $<a,a>=<a,1>$ is incorrect. It is correct in the ring $\mathbb{Z}$, however we're not in the integers, we're in a finite field. Counterexamples in finite fields are easy to find; for example, in $GF(11)$ (...


3

Here's a recent doctoral thesis with a decent literature review. https://discovery.ucl.ac.uk/id/eprint/10073525/


3

Special Honest Verifier Zero-Knowledge is a particular case of Honest Verifier Zero-Knowledge; that is, if a protocol satisfies SHVZK, it satisfies HVZK. SHVZK has been introduced to simplify discussions about $\Sigma$-protocols. In $\Sigma$-protocols, HVZK is typically proven as follows: fix an arbitrary challenge $e$, and show that it is possible to ...


3

They're just different things. A protocol may be challenge-response or not, and zero-knowledge or not; all four combinations are possible. Plain password authentication is not challenge-response and not zero-knowledge. The manual-lookup copy protection in old games is challenge-response and not zero-knowledge. Another example would be CAPTCHA. Non-...


3

A Polynomial Commitment is a cryptographic object that binds a party, typically the prover, to a single polynomial. This object could be an elliptic curve point, such as in KZG or Bulletproofs en element of a group of unknown order, such as in DARK the root of a Merkle tree of a Reed-Solomon codeword, such as in FRI. The point is that underlying this ...


3

For the discrete case, you can just use any zk-SNARK that generalizes over arithmetic circuits. There is no direct way to do a zero-knowledge proof over the reals. However, you can map linear operations over real numbers to operations in the field you are working in by first proving an upper bound on your inputs. Since the circuit is public the verifier can ...


3

The philosophy behind the extractor and knowledge is that if the prover can generate the proof, then it could itself run the extractor. Therefore, if it can prove, then it knows the witness. If the extractor runs in super polynomial time, then the prover itself cannot run the extractor. Note that if you took this to an extreme, then in exponential time it is ...


2

My goal is just to complete Mikero's answer, notably on that part: Also, I would be most grateful if you should show me example proofs in the UC framework. The shorter/easier the better, just so I can get my head around it. I just wrote a simple sketch of proof in this other answer. The goal is not to write a full formal proof in UC, but rather to give the ...


2

$ \newcommand{\NP}{\mathbf{NP}} \newcommand{\coNP}{\mathbf{coNP}} \newcommand{\TFNP}{\mathbf{TFNP}} \newcommand{\L}{L} \newcommand{\R}{\mathcal{R}} $ A zero-knowledge proof of knowledge is useful in scenarios where the notion of a plain zero-knowledge proof is vacuous. I think the accepted answer kind of misses this (crucial) point. For instance consider a ...


2

This problem was studied in [BCK], and interestingly they showed that constructing a Schnorr-like zero-knowledge proof system (ZKP) in a group of unknown order with non-trivial soundness error is not possible in the plain model (i.e., without CRS). Their result is much more general and talks about homomorphisms in groups of unknown order. However, if one ...


2

As shown recently$^1$ in [BBF], this can be carried out using universal accumulators [BdM]. Their construction is in the discrete-log setting in groups of unknown order (e.g., RSA group or class groups) and the size of both proofs of membership and non-membership is independent of the size of the set committed to. The security proof is in the generic group ...


2

(This answer assumes a proving system that supports general arithmetic constraints, e.g. R1CS, over a finite field $\mathbb{F}_p$. It can be adapted to other settings but that may be non-trivial.) Consider that a comparison $0 \leq n < c$ in $\mathbb{F}_p$ has negation $c \leq n < p$. So a constraint system for $b = (0 \leq n < c)$ can be ...


2

What is a zk-SNARK: a specific proof system, and if so: which one? a class of ZK proof systems, and if so: is this class specific enough to claim that proofs are "always 200 bytes"? zk-SNARK (short for zero-knowledge succinct non-interactive argument of knowledge) is a class of non-interactive zero-knowledge proof system which basically satisfies the ...


2

At first, every ZKPoK protocol is ZKP protocol. This is obvious: if you proved that you know a witness, therefore a witness exists, therefore the statement belongs to the language. The interesting question is whether a protocol exists which is ZKP but not ZKPoK. It holds for trivial languages, but you're justly not satisfied with this. My idea in a discrete ...


2

Assuming this, how would we use logic to find out if a given problem has a ZKP or if it does not? From a theoretical standpoint, this has a rather simple answer: If the language you are trying to prove lies in IP or PSPACE then there is an (efficient) ZKP for it. So, from a formal standpoint, a ZKP looks as follows: There's a prover and a verifier. The ...


2

You can find the security proofs for 5-round Fiat-Shamir: Ming-Shing Chen and Andreas Hülsing and Joost Rijneveld and Simona Samardjiska and Peter Schwabe: From 5-pass MQ-based identification to MQ-based signatures. Asiacrypt 2016. https://eprint.iacr.org/2016/708 Özgür Dagdelen, David Galindo, Pascal Véron, Sidi Mohamed El Yousfi Alaoui, and Pierre-Louis ...


2

final_exp_gadget<>() of libsnark could be a practical example to tune for DLP. The idea is, "final exponentiation" is a part of Ate pairing, that is verified as a part of check_e_equals_e_gadget<>(), which stands for Groth16 verification equation.


2

If I understand correctly, you're asking to prove that you have the result of running a secret input through a public process without revealing anything about this result. For this proof to be an interesting one, you would have to output some value and then prove how it relates to the values you're hiding. If you don't do that, then you're simply proving ...


2

Here is the simpler method I can think of: let's assume some PKI has been setup, so that there is a known public key $\mathsf{pk}_i$ for each receiver $R_i$. Then, the share sender can simply broadcast a list $c_i = \mathsf{Enc}_{\mathsf{pk}_i}(s_i)$ to everyone, where $\mathsf{Enc}$ is some encryption scheme and the $s_i$ form the secret shares of the ...


2

And I checked some related works, and most of them only considered the dictionary attack and forward security. Actually, a PAKE has two security goals: That someone cannot recover the password from a number of exchanges (with any greater advantage than being able to test $N$ potential passwords using $N$ active attacks). That someone will not be ...


Only top voted, non community-wiki answers of a minimum length are eligible