# Tag Info

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
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
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
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
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
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 ...

### 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

### 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 ...

### 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
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
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

### 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
Accepted

### How to generate constraint on right shift bitwise operator in Circom

Solution using the LessThan comparator from circomlib: ...
• 1,583

### 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
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
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 ...
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