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

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

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

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

Solution using the LessThan comparator from circomlib: ...
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))$, ...
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 ...
1 vote

### 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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
1 vote

### How to determine the layers of a circuit?

For many instances, the depth of the circuit is related directly to the arity of the logical gates from which is is built, or the arity of the subprotocols on which it depends. Considering the ...

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