15
votes
Accepted
Representing a function as FHE circuit
The circuit term in the evaluation of functions with FHE is a coming from Electronics. In the notion of FHE circuit, we have almost the same problem; build a circuit of a function $f$ with available ...
- 49.3k
7
votes
Accepted
What is a rank-1 constraint system?
The "rank-1" specifically refers to the rank of the matrix which is produced.
As for the link to circuits, in zk-SNARKS at least, an arithmetic circuit is converted into a R1CS. Each constraint ...
- 186
3
votes
Accepted
Can any one explain why circuit privacy is needed on homomorphic encryption?
When we say circuit privacy, we actually mean that the distribution over the result of the computation is the same (statistically close) to the distribution over an encryption of the result. This is ...
- 28.1k
3
votes
Accepted
How to construct a circuit in zkSNARK
is there any specific definition or feature for the problem, and could all problems, which can be verified, be converted into circuits and use zk-snark to generate proofs?
Problem should be in NP ...
- 365
2
votes
Accepted
How to determine the layers of a circuit?
Given a circuit for f, how can we optimize to get a "shallower" circuit for the same f? Are there any tools/algorithms available for this purpose?
Researchers have already identified this is a ...
- 124
2
votes
Accepted
Fixed variable in Groth16
Your thinking is correct!
In the GGPR13 paper (see Definition 11 in section 7.1 ) quadratic arithmetic programs were introduced for proving arithmetic circuit satisfiability. The key idea was that ...
2
votes
In constraint systems for ZK proofs, why are multiplications counted but are additions not?
Your question seems to assume this is true for any constraint proof system. I'm quite confident that this property is on a case-by-case basis. Bulletproofs, for example, have this property: proof size ...
- 2,430
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 ...
2
votes
Homomorphic encryption methods that could support logical XOR, AND?
Partial and Fully Homomorphic Encryption
When a homomorphic encryption scheme supports a single operation on the encrypted data like
RSA has a modular multiplicative operation
Elgamal has a modular ...
- 49.3k
2
votes
Accepted
How to generate a circuit for SHA-256?
given an algorithm of a hash function, how to transform it into a circuit?
Most importantly we first want to better state the problem
What hash function?
Do we want a circuit for the full hash ...
- 144k
2
votes
Accepted
Does the degree of this polynomial matter to achieve zero-knowledge? PlonK question
the degree of the blinding polynomial that you're multiplying with the vanishing polynonial $Z_H$ has to be sampled from $F_d[X]$ with $d$ greater or equal to the number of evaluations in the protocol ...
- 1,565
2
votes
How to do division in secure multi-party computation (mpc)?
Path 1: there is a protocol which lets you perform division. Suppose you're given $[x]$ and you want to compute $[x^{-1}]$:
Take a random element $[r]$
$[y] \gets [r] * [x]$
Open $[y]$ and obtain $y$
...
- 1,375
2
votes
Accepted
How to generate constraint on right shift bitwise operator in Circom
Solution using the LessThan comparator from circomlib:
...
- 1,583
2
votes
How to generate a SNARK arithmetic circuit for SHA256?
What format of arithmetic circuits are you looking for? If you are needing some insight, this github repo contains python code for generating a SHA256 arithmetic circuit that is used for benchmarking ...
- 467
2
votes
Accepted
Can a 3-coloring for a graph be represented as a circuit?
The beauty of QAP is that it is NP-Complete. Thus, the 3-coloring problem reduces to QAP. In fact, any problem in NP can be represented using QAP constraints.
More practically, all that is required is ...
- 939
2
votes
Accepted
Arithmetic Circuits to R1CS. Do we consider addition gates or not?
I've answered a similar question on this here
As you've correctly observed, Buterin's example is simplified and does not account for the optimisations that are possible with R1CS. If you want to ...
- 467
1
vote
R1CS and zkSNARK
All computations in the proof are done in the finite field.
The advantage of using Finite fields is that it keeps the operations closed - i.e.
the output of an operation will also be in the same field ...
- 2,262
1
vote
Accepted
Conditional Boolean circuits
Say I want to sort three numbers from a given input. How can I convert this function to a boolean circuit?
For this particular question, there are simple answers.
The traditional way to sort number ...
- 13.8k
1
vote
Accepted
Reducing number of constraints in R1CS from an arithmetic circuit
@lamba is already aware of this, but I thought I'd add a response for future reference as there is not a lot of resources on this.
R1CS is a language which asks for an input $v$ such that
$$Av\circ Bv ...
- 467
1
vote
Why AND gate is * on Fully Homomorphic Encryption, BFV scheme?
First, note that BFV is traditionally phrased in terms of arithmetic circuits, not boolean ones.
For example, the initial paper has a message space of the form $R_t := \mathbb{Z}_t[x] / (\Phi_n(x))$, ...
- 13.8k
1
vote
What is arithmetic circuits indeed?
The whole point is that in the Aritmetic Circuit (AC) model we take a field and use field operations (+,*) as building blocks.
Each field operation is represented as a single output multiple input ...
- 23.1k
1
vote
Accepted
Homomorphic encryption methods that could support logical XOR, AND?
XOR and AND are "just" addition and multiplication $\bmod 2$. Your application needs a fully homomorphic encryption scheme defined over $\mathbb{F}_2$, of which the schemes FHEW/TFHE (which ...
- 13.8k
1
vote
An arithmetic circuit for the indicator function?
Any degree $d$ polynomial (over a field) has at most $d$ roots (unless it is identically zero). As the indicator function has $q-1$ roots, one gets that it must have degre $\geq q-1$.
There are ...
- 13.8k
1
vote
Accepted
zkSnark Circuit
Large circuits are definitely a bottleneck for proof systems. Splitting them into sub-circuits (often reffered to as "gadgets") is mainly a programming construct: gadgets are the equivalent ...
- 2,430
1
vote
Examples of multi output bit balanced Boolean functions
As in the other answer a vectorial boolean function with $m$ coordinates $f : \{0,1\}^n\to\{0,1\}^m$ are viewed as $m$ boolean functions $f_i : \{0,1\}^n\to\{0,1\}$.
However, it is not enough to ...
- 23.1k
1
vote
Limitations of boolean and arithmetic circuits
The question should be which functions can we build a small circuit to solve. Any function mapping a fixed number of bits to a fixed output can be represented as a boolean circuit. But it may be very ...
- 11.9k
1
vote
Why RSA2048 sign of Intel accelerate card is fast?
Specialized hardware is the answer. This machine uses asynchronous computation, very likely using parallel Montgomery multipliers and a local register of 4096 bits (4096 seems to be the largest key ...
- 94k
1
vote
How would I convert an arithmetic circuit into a system of bilinear equations?
I don't know if this is exactly what you mean, but you can always consider each one of the wire values in the circuit as variables, and then create an equation per gate which represents the relation ...
- 4,022
1
vote
What is a rank-1 constraint system?
I may be necro-answering a bit, but the terminology seems to be inherited from a general case of quadratic equation (which is a natural generalization of a linear equation). In quadratic equation you ...
- 111
1
vote
How to determine the layers of a circuit?
For question 2, I suspect this might be equivalent to a topological sorting algorithm, modified to keep track of the "depth" (i.e. the layer index) of the gates. It can be done in $O(n + m)$ time, ...
- 665
Only top scored, non community-wiki answers of a minimum length are eligible