6 votes
Accepted

Zero knowledge proofs that one has broken a crypto system

Sure! For example, you could prove in zero-knowledge that you know the prime factors of $n$, where $n$ is an online RSA challenge (i.e. something we know for sure you did not create yourself). Such a ...
Geoffroy Couteau's user avatar
5 votes
Accepted

What would be the degree (or range of the degree) of the polynomial used in real life zkSnarks as used in blockchains?

Circuit (polynomial) sizes in deployed zkSNARKs. Multiple projects apply zkSNARKSs (e.g., mainly Groth16 or Plonk) in production. The degree of the polynomial slightly depends on the applied poly-IOP ...
István András Seres's user avatar
5 votes
Accepted

How can a verifier benefit from being malicious or dishonest in a Zero Knowledge interactive proof?

For many concrete HVZK proof systems, we actually don't have an attack against zero-knowledge when the verifier is dishonest - but we don't have a security proof either! In particular, in many $\Sigma$...
Geoffroy Couteau's user avatar
5 votes

Division of two Elliptic curve points in KZG polynomial commitment scheme!

In this lecture, they use multiplicative notation for the pairing groups instead of additive notation. Thus, division is well-defined. Division is just the inverse of the group operation. The choice ...
Wilson's user avatar
  • 929
4 votes
Accepted

If SNARKs generally work in finite fields, how are non integer values handled - say fixed point decimal numbers?

If necessary, this can be done by sending all $n$ digits of the fraction (it has to be finite length to be represented digitally) and an encoding (in $\log_2(n+1)$ bits) of the position of the decimal ...
kodlu's user avatar
  • 21k
4 votes
Accepted

What security problem would cause if I reuse a NIZK proof?

A standard NIZK is publicly verifiable: not only can you reuse it, you could even publish it on your webpage, and let anyone download it and verify it. This does not harm soundness of ZK in any way. ...
Geoffroy Couteau's user avatar
4 votes

Verify HMAC tag without knowing the key

There are obviously constructions other than HMAC that work. Public key signing works obviously with Alice sending Bob her public key. HMAC has no algebraic structure to allow this to work. Zero ...
Richard Thiessen's user avatar
4 votes
Accepted

Assumptions on zero-knowledge proofs without trusted setup

Strongly unforgeable digital signatures exist from one-way function, so they are indeed a Minicrypt assumption, even though most efficient construction use public key cryptography. For succinct zero-...
Geoffroy Couteau's user avatar
4 votes
Accepted

Statistics-heavy crypto papers

I am afraid your search for Annals of Stats etc. level of purely statistical theoretical papers in cryptology may not yield too many examples. The field is very applied and the role of statistics is ...
kodlu's user avatar
  • 21k
4 votes

State of the art for Graph Isomorphism

Goldreich and Krawczyk proved the following theorem: Theorem 6.2: A language L has a three-round interactive proof which is black-box simulation zero-knowledge if and only if L ∈ BPP So unless GI is ...
Gareth Ma's user avatar
  • 340
3 votes
Accepted

What type of soundness/knowledge soundness does Schnorr's proof of knowledge of a DLOG have?

I answered the first part of the question here: Schnorr is a statistical proof of knowledge, with knowledge error $1/p$ (or $1/|C|$ if you pick the challenge from $C$). That is, one can always extract ...
Geoffroy Couteau's user avatar
3 votes
Accepted

In the Kate/KZG Polynomial Commitment Scheme, in which Polynomial Ring should the polynomial to be committed be?

An output of the setup algorithm in KZG is a description of a bilinear group which contains a description of three groups $\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T$ (sometimes $\mathbb{G}_T$ is ...
Wilson's user avatar
  • 929
3 votes

How to compare two field elements in Arithmetic Circuit?

You have misread my answer here. When converting a boolean circuit into an equivalent arithmetic circuit, you need to (1) Take your inputs over the field and convert them into bitstrings (e.g. through ...
Geoffroy Couteau's user avatar
3 votes
Accepted

What is the modern terminology for a digital signature scheme with a shadow?

In modern terminology, a digital signature scheme with a shadow is a (digital) signature scheme giving (total) message recovery. The shadow is the message representative. The paper linked in the ...
fgrieu's user avatar
  • 137k
3 votes
Accepted

PLONK Product Check Proof. Why is the 2nd condition required?

The correct checks are 1) $t(\omega^{k-1}) = 1$ and 2) $t(\omega\cdot x) - t(x)\cdot f(\omega \cdot x) = 0$ for all $x \in \Omega$ The prover is supplying values in a black box way. The second ...
kodlu's user avatar
  • 21k
3 votes
Accepted

PLONK Prod Check Proof - why does it have to be proven upto the last element of the set? It should be enough to prove it upto last but one element

At $x=\omega^{k-1}$ the 2nd equation is $$t(\omega^k) = t(\omega^{k-1}) \cdot f(\omega^k)$$ which, knowing that $\omega^k = 1$ and assuming 1) is satisfied, i.e. $t(\omega^{k-1})=1$, it converts to $$...
Bean Guy's user avatar
  • 722
3 votes
Accepted

Is the permuation check range in the PLONK Paper incorrect?

The argument in the paper is correct. Verifying (a) confirms that $Z(g)=1$, verifying $$Z(a)f'(a)=g'(a)Z(a\mathbf g)$$ for $a=\mathbf g,\mathbf g^2,\mathbf g^3\ldots \mathbf g^{n-1}$ then inductively ...
Daniel S's user avatar
  • 21.2k
3 votes
Accepted

Securely derive multiple EC keys from master EC key and prove it

Alice doesn't have to do anything. A' = (a+r)*G = a*G + r*G = A + r1*G Bob can compute these keys himself. That's usually how key diversification works. If he wants ...
Richard Thiessen's user avatar
3 votes
Accepted

What does preprocessed polynomial mean in the context of PLONK?

Pre-processing means part of the one-time initial set up computation of the system prior to the generation of any proofs. This set-up phase is allowed to use considerably more resources. If we look to ...
Daniel S's user avatar
  • 21.2k
3 votes
Accepted

PLONK: Why is the quotient polynomial multiplied by different powers of a challenge?

The quotient challenge is necessary for soundness. In particular, if the prover wants to show that there exists quotients $q_1=f_1/z_H$, $q_2=f_2/z_H$, and $q_3=f_3/z_H$. To do so, it can instead send ...
Wilson's user avatar
  • 929
3 votes

How to prove the correct decryption of several (ElGamal) ciphertexts in a batch?

Batch verification is straightforward in this case. Given $n$ signatures $(u_i,v_i,vk_i)$ for $1\le i\le n$, the same $x$ and $z$ value can be used to verify all $n$ signatures, by multiplying ...
Daniel S's user avatar
  • 21.2k
3 votes
Accepted

Zero-knowledge card shuffle

Mental poker is a fairly well studied problem in cryptography. There are existing libraries that implement it: a zero knowledge library for Mental Poker (and all card games) Good alternate ...
Richard Thiessen's user avatar
3 votes

Proving addition of secret values in a small field

Write the finite field as $\mathbb{F} = \mathbb{F}_q$, where $q = p^k$ is a prime power. Since $\mathbb{F}_q \cong \mathbb{F}_p^k$, we can interpret $x, y, z$ as vectors over $\mathbb{F}_p$ where ...
Gareth Ma's user avatar
  • 340
2 votes
Accepted

Zero knowledge validation to check if private element is in a set hidden on a central server

Sounds like a scheme where $\phi$-hiding would work well. A scheme for a single secret element Write a publicly-known hash-to-prime function that maps guesses to primes of around, say, 128-bits (e.g. ...
Daniel S's user avatar
  • 21.2k
2 votes

How to calculate soundness error of a sigma protocol?

For a $\Sigma$ protocol with a challenge space $\mathcal C$, the soundness error is $1/c$ where $c = |\mathcal C|$. Alternatively, the error is $2^{-t}$ for a $t$-bit challenge. The proof that I still ...
Marc Ilunga's user avatar
  • 2,623
2 votes
Accepted

How to calculate soundness error of a sigma protocol?

As far as I know, a general answer depends on protocol under analysis (as Schnorr) being a Proof of Knowledge (PoK) and not necessarily being a Sigma Protocol. PRELIMINARIES A Knowledge Extractor (KE)...
baro77's user avatar
  • 680
2 votes
Accepted

How to implement CRS model in the real world?

You are correct: CRS can be realized by a set of trusted parties. To my knowledge, the closest reference to a practical solution to a CRS is the one that Zerocash uses, and that we can read from: ...
Crypto Learner's user avatar
2 votes

Is it possible to prove that an encrypted message was encrypted with some public key without divulging the plaintext or secret key?

Yes, it is perfectly possible to prove that a ciphertext $C$ is of the form $\mathsf{Enc}_{\mathsf{pk}}(m;r)$, where $m$ is an arbitrary plaintext, $r$ an arbitrary random coin (both secret), and $\...
Geoffroy Couteau's user avatar
2 votes

How to construct a circuit in zkSNARK

To answer your first question, the feature of problem is usually from NP Class where you compute in Non-deterministic Polynomial(NP) time, but verifying the computation should take less than or equal ...
Verified Anon's user avatar
2 votes

Proof of membership on a merkle tree

Unfortunately, an in depth answer for me would be too long and is actually the scope of the Zerocash paper itself, which I recommend you re-read thoroughly. A high-level answer: Instead of providing ...
Alin Tomescu's user avatar
  • 1,003

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