Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [zero-knowledge-proofs]

Zero-knowledge proofs are an interactive method for one party to prove to another that a statement is true, without revealing anything other than the veracity of the statement.

1
vote
0answers
27 views

Given a ciphertext $c$ and a public string, how do we check whether $c$ encrypts something that is roughly equal to the string without decryption?

Let $𝑓$ be an encryption function, then we have $c = f(m)$ for some bit string $𝑚$. Here, we also have pattern matching function $𝑔(𝑚,𝑚′)$ which returns true whether $𝑚$ matches roughly with $𝑚′...
3
votes
0answers
37 views

Homomorphic encryption and zero-knowledge proof in one cryptosystem?

Does a cryptosystem exist that simultaneously has the properties of homomorphic encryption and zero-knowledge proof?
1
vote
1answer
24 views

Monero Ring CT sj calculation

For a university project, I am currently implementing the RingCT Ring signatures as used in Monero (before the introduction of Bulletproofs) as laid out in this paper. To close the ring we calculate ...
1
vote
0answers
51 views

ZKP: Proving knowledge of a variable length hash preimage

I am currently trying to implement a proof of knowledge of the preimage to a public hash image using different zkp system implementations. There are a lot of examples that do exactly this (see this ...
3
votes
0answers
43 views

Schnorr protocol is witness-hiding?

Regular 3-steps Schnorr protocol is a proof of knowledge system for discrete logarithm. It's honest-verifier zero-knowledge, but not full zero-knowledge. My question is, is it witness-hiding? (I guess ...
0
votes
0answers
25 views

The security of Zero knowledge proof performance

I recently learned to study the security of zero knowledge proof. As you can see on the wiki (link), it seems to be the most popular example of the Ali Baba cave. I have a question about the security ...
0
votes
0answers
41 views

How can users be authenticated without revealing their identity on a massive scale? [on hold]

I want to create a system where a user can be authenticated without revealing who they are. I assume I have a list of public keys for all users (E.g. government issued). Ring signature could be used ...
2
votes
0answers
31 views

What is the relation between honest verifier zero-knowledge and non-interactive zero-knowledge?

I'm not clear about the relation between the following definitions: zero-knowledge protocols; honest verifier zero-knowledge; non-interactive zero-knowledge. To my best understanding, zero-knowledge ...
2
votes
1answer
50 views

How does the Signature Scheme in Picnic Works

I am trying to understand how signature scheme proposed to NIST, Picnic, works. The propossal uses ZKboo and ZKboo++ as their basis. I can see how the ZKPoK works, where the witness x is some key ...
2
votes
1answer
67 views

Pedersen commitments in bulletproofs

In Bulletproofs range proof, Pedersen commitments look like $C=aG+bH$ If I need to proof several values' range proof and keep G as constant, do I need to change H everytime? I have found it doesn't ...
1
vote
0answers
24 views

Zero Knowledge Proof of Association

Assuming there are a group of individuals with static ecdsa keypairs, of which the public keys are in a shared database that all of them have access to, how can each participant publish an ephemeral ...
-1
votes
0answers
21 views

Expensive operation to preserve correctness in MPC protocol

If I want to ensure correctness property in a Multi-party computation (MPC) protocol with the dishonest majority then do I need to include expensive operations (such as zero-knowledge proofs) in my ...
3
votes
1answer
39 views

Are multi move proof protocols still “sigma protocols”?

Conventionally, sigma protocols are defined as being a three-move protocol (1. commit, 2. challenge, 3. response). Reading papers like "Bulletproofs" (Bunz, Bootle, Boneh et al., 2018), it feels like ...
1
vote
1answer
86 views

Simulator in Zero Knowledge Proofs

I'm reading about Zero-Knowledge-Proofs, in particular the argument of building a Simulator in order to prove the zero-knowledge property. As expected, there's something that doesn't click yet. Since ...
4
votes
1answer
109 views

Could Diffie-Hellman protocol serve as a zero-knowledge proof of knowledge of discrete logarithm?

The Schnorr identification protocol is widely recognized as the simplest ZKPoK of the discrete logarithm (more clearly, Honest-Verifier ZKPoK). However, I can't figure out why this simple protocol, ...
3
votes
0answers
69 views

Doubt in computing $g^\frac{1}{\delta+x}$ where $x \in \mathbb{Z}$

I was going through Zero Knowledge Set Membership and came across the following: Given $x \in \mathbb{Z}$ and $g$ is the generator of a multiplicative group $\mathbb{G}$ how do we compute $g^\frac{1}{...
0
votes
0answers
21 views

Simulator in the ideal world computes the proof for parties for $F_{NIZK}$

In the definition of $F_{NIZK}$ in [GOS06b], on receiving prove from a party, the functionality forwards the statement to the ideal world adversary $S$. This ideal world adversary then creates a ...
1
vote
1answer
113 views

Simulation based proofs, what am I missing?

In the example given by in the top answer of Simulation based proofs: Simple examples claims that this is insecure the semi-honest, and I need assistance in where I am failing to reason why that this ...
0
votes
1answer
52 views

Searching for a dining cryptographers problem variant

When I frist read about the famous dining cryptographers problem, in a book years ago I remember the author made a twist on it, demonstrating the generalization of the problem. Basically the dining ...
1
vote
1answer
66 views

Proof of correctness of an ElGamal encryption given a specific public key

Suppose Alice sends an ElGamal encryption of a value $v$ to Bob (using either the normal or exponential version of ElGamal). E.g. assuming publicly-known $pk_{BOB} = h$ and a generator $g$, Alice ...
2
votes
1answer
56 views

Share secret non-interactively in a verifiable way

In an application, I need to share a secret (random number) with a Group of known receivers over a public channel (a Blockchain) but each receiver needs to be able to check that the others received ...
3
votes
1answer
51 views

Bulletproofs range proof of value provided from trusted third party

I'm really interested in range proofs, and bulletproof seems to be the most effective range proof. I saw an example of usage of bulletproofs range proof: You can generate a proof that your age is ...
2
votes
1answer
99 views

What is difference between Zero Knowledge proof and Zero Knowledge Proof of Knowledge?

In a zero knowledge proof, a prover interactively proves to a verifier that an NP statement is true. If the language is an NP complete language and if the prover runs in poly time, the only way a ...
10
votes
1answer
261 views

Contradiction to the Sequential Self-Composability of Black-Box Zero-Knowledge?

In short: it is well-known that black-box zero-knowledge protocols are sequentially self-composable. However, Goldreich and Krawczyk [GK90] present a protocol which is proven to be zero-knowledge (in ...
1
vote
2answers
80 views

ZKP: Asymmetric encryption with confidential message and known hash

I'm searching for a ZKP package that supports asymmetric encryption so I can implement the following scenario: Carol encrypts message $m$ with Alice's public key and sends the ciphertext to Alice. ...
3
votes
1answer
91 views

Zero-knowledge proof with only a ciphertext

Suppose there is a plaintext p, which is encrypted with a symmetric cipher using a key k, resulting in a ciphertext c. Bob knows both c and k, but Alice knows only c. Is there any protocol by which ...
5
votes
0answers
54 views

What's the difference among Vector Commitment, Zero-knowledge Set, Zero-knowledge Accumulator, and Zero-knowledge Elementary Database?

Vector commitment allows to commit to an ordered sequence of $q$ value ($m_1,\cdots,m_q$) in such a way that one can later open the commitment at specific positions(e.g., prove that $m_i$ is the $i$-...
3
votes
1answer
74 views

Is Quadratic Arithmetic Program NP-complete?

I'm reading this paper: Quadratic Span Programs and Succinct NIZKs without PCP Is QAP NP-complete? as same as QSP?
3
votes
1answer
61 views

Zero-knowledge proof for Paillier parameters

For RSA one can give a non-interactive zero-knowledge proof that RSA with parameters $(e,N)$ form a permutation and a proof of knowledge of the associated RSA secret key. For example, such a proof can ...
1
vote
1answer
62 views

Upper bound for the length of non-interactive zero-knowledge proofs of knowledge

In a hybrid protocol $\pi$ for which I want to proof uc-security in the absence of corrupted parties, there is an ideal functionality $\mathcal{F}_{SMT}$ for secure message transfer that leaks the ...
0
votes
0answers
22 views

Zero knowledge token for communicating files one has

Is there a method for individuals to publish a token which indicates having a file in their local set of files without revealing exactly what they have? For these purposes we will consider a file to ...
0
votes
0answers
39 views

Honest Verifier Zero-Knowledge Game for Sigma Protocols

I am looking for how an adversary to special HVZK would work. In Boneh and Shoup's book (BonehShoup) they have Attack Game 20.4 for special cHVZK. Here, the adversary produces a pair (x,y) (witness ...
3
votes
1answer
67 views

What are the major advantages of SPHF for PAKE?

I am working on Password Authenticated Key Exchange (PAKE). I noted some PAKE schemes were built upon the smooth projective hash function (SPHF). I am confused why SPHF can be used to design PAKE? I ...
1
vote
1answer
71 views

Linear combination IOP for SNARK registers

The STARK paper says Our ZK-STARK uses a separate Reed-Solomon codeword for each register, leading to w many codewords, each of lower degree ...
1
vote
2answers
61 views

Zero Knowledge for Low Entropy Witness

For any PPT prover ($p$) and verifier ($v$), imagine I have a low entropy witness, say smaller than $2^8$. Now, let us say I have a dlog statement in the form of $y = g^w$. Theory says I could use a ...
0
votes
1answer
41 views

Extractor for Oblivious Transfer Protocol

In a paper that I have been reading (https://cs.nyu.edu/~ganesh/zk.pdf), in one of the proofs, this has been said: The simulator works as follows: It uses the OT simulator to extract the prover’s ...
1
vote
1answer
118 views

What is a rank-1 constraint system?

Why not rank-2 constraint system or rank-3 constraint system? How do rank-1 constraint systems link to circuits?
2
votes
0answers
20 views

Strategies for fast integrity attestation over multi party computation for large messages

I am looking for ways to efficiently perform integrity attestation over large messages using multi party computation. While, hashing (SHA1, 256...) is one alternative but it's painfully slow and grows ...
2
votes
0answers
59 views

Is this an error in the Pinocchio Protocol paper

I am going through the Pinocchio protocol paper and I need 2 clarifications in the section Protocol 1 (Verifiable Computation from strong QAP). The part that explains the Verify process, which ...
2
votes
1answer
122 views

Disjunctive zero knowledge proof of equality of committed values

I have read on ZK proof of equality of committed values, that is for $g^xh^y$ and $g^{x'}h^{y'}$, prove in ZK that $x = x'$ (can also be generalized if generators are different using sigma-protocols). ...
0
votes
0answers
52 views

Simple proof of knowledge

It seems to me that signing the hash of the public key with ECDSA should be a sufficient non-interactive proof of knowledge. In my use case, I only need the guarantee that "someone even had ...
1
vote
1answer
165 views

What is purpose of a simulator and extractor in zero knowledge proof protocols?

I am new to zero knowledge proofs. I read the paper Efficient Protocols for Set Membership and Range Proofs by Jan Camenisch, Rafik Chaabouni and Abhi Shelat. The author proposed a zero knowledge ...
2
votes
1answer
70 views

In constraint systems for ZK proofs, why are multiplications counted but are additions not?

For example, If I wanted to prove that: $$x^2 + x^3 = 45$$ This cost of this would be calculated by counting the number of multiplications that need to be done, and not the addition of $x$ squared ...
2
votes
1answer
47 views

Subtracting one pederssen commitment from another

I am building a range proof to prove that a secret number x lies between a specific range a prover commits to a values a<x<b prover generates a pedersen ...
2
votes
0answers
47 views

The theory of transformation of arithmetic expressions into boolean circuits in zkboo

I've read the sources of ZKBoo where they transformed arithmetic operations of the SHA hash functions into a bunch of boolean ones. Where does this transformation arise from? How do you construct such ...
0
votes
0answers
56 views

Can we build a zero knowledge mapping using public-key encryption?

I'm trying to understand if this design is possible. I want to build a mapping that is zero-knowledge, between a (pubkey, proposalId) => bytes form, without ...
1
vote
1answer
63 views

Proof of ignorance to prevent “double-spend”?

Suppose I have some knowledge that I want to transfer securely from Alice's computer to Bob's computer, and prove that future breaches to Alice's computer will not reveal that information to someone ...
2
votes
1answer
70 views

Witness-Extended Emulation

I am reading up on Sonic: Zero Knowledge SNARKS from Linear - Sized Universal And Updateable Structured Reference Strings. An excerpt: For soundness, we do not use the standard definition of ...
1
vote
1answer
82 views

ZK due to rewinds, why we need poly number of rewinds?

I've been looking into rewinding techniques for proving ZK and got a bit confused. This answer is good, but I still have questions about challenge size and the number of rewinds. Consider an ...
1
vote
0answers
49 views

Rewinding Argument and Forking lemma

In Dan Boneh's crypto book, there is a section describing the "Rewinding Lemma", however I cannot find it explained in other sources on the internet. How does this differ from the forking lemma?