Cryptography Stack Exchange
Cryptography Stack Exchange

Questions tagged [circuit]

In computational complexity theory, arithmetic circuits are the standard model for computing polynomials. Informally, an arithmetic circuit takes as inputs either variables or numbers and is allowed to either add or multiply two expressions it has already computed.

36 questions
14
votes
1 answer

Representing a function as FHE circuit

I am actually trying to study homomorphic encryption (on lattices) but I'm facing a problem. Every paper that I have read so far talk about writing the function to evaluate on ciphertexts as a circuit, either boolean or arithmetic according to our…
Binou
  • 398
  • 3
  • 14
7
votes
1 answer

Limitations of boolean and arithmetic circuits

Much of modern cryptography is based around working with boolean or arithmetic circuits. For example in Multi-Party Computation the 'famous' results allow for the secure computation of any function that can be represented as a boolean or arithmetic…
LDG
  • 83
  • 4
7
votes
3 answers

How to determine the layers of a circuit?

In many cryptographic applications like Multiparty Computation (MPC) or Fully Homomorphic Encryption (FHE), you consider a function $f$ described by a circuit over some algebraic structure, typically a field. Now, it's very typical that the…
Daniel
  • 3,862
  • 1
  • 17
  • 33
6
votes
1 answer

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?
WeCanBeFriends
  • 1,263
  • 10
  • 19
6
votes
1 answer

Arithmetic Circuits to R1CS. Do we consider addition gates or not?

Here is Ariel Gabizon's Blog for the process of converting Arithmetic Circuits into R1CS - https://electriccoin.co/blog/snark-explain5/ Here, he writes We assume multiplication gates have exactly two input wires, which we call the left wire and…
user93353
  • 2,197
  • 2
  • 21
  • 37
5
votes
1 answer

Can any one explain why circuit privacy is needed on homomorphic encryption?

I know some works have been done in the context of cirrcuit privacy on homomorphic encryption, where from an output ciphertext it does not allow someone to distinguish what function is computed. I wonder the need of this functionality. If we use a…
mallea
  • 1,505
  • 7
  • 20
4
votes
3 answers

An arithmetic circuit for the indicator function?

The indicator function (or characteristic function) is defined as $f_{t^*}:\mathbb{Z}_q\to \mathbb{Z}_q$ satisying that $f_{t^*}(t)=1$ if $t^*=t$ and $f_{t^*}(t)=0$, otherwise. (Here $t^*\in \mathbb{Z}_q$ is given to define the function.) I am…
Huy Le
  • 41
  • 3
4
votes
1 answer

How to construct a circuit in zkSNARK

I have a few questions about how to use zk-snark. Since the basic logic of using zk-snark is: using a circuit to represent a problem, generate an R1CS from the circuit, transform R1CS to QAP and then we can run zk-snark For the first part, is…
Mkotori
  • 65
  • 4
3
votes
1 answer

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 and $x$ cubed.
WeCanBeFriends
  • 1,263
  • 10
  • 19
3
votes
0 answers

Arithmetic Circuit to Square Arithmetic Program (SAP)

I'm trying to figure out how to convert a circuit into a Square Arithmetic Program (SAP). This is to eventually use it for zk-SNARKs such as Groth16. I do however understand how to convert arithmetic circuits into Quadratic Arithmetic Programs…
Dontmilkme
  • 31
  • 2
3
votes
1 answer

Reducing number of constraints in R1CS from an arithmetic circuit

The article Ligero++ (https://dl.acm.org/doi/pdf/10.1145/3372297.3417893) says "The number of constraints in R1CS maps to the number of multiplication gates in arithmetic circuits." But I understand the basic way to map an arithmetic circuit to R1CS…
lamba
  • 1,353
  • 7
  • 18
2
votes
2 answers

Why AND gate is * on Fully Homomorphic Encryption, BFV scheme?

According to Representing a function as FHE circuit, the AND gate for FHE encrypted data is just A*B, in the case that the plaintext has only 0 or 1 coefficients. Remember that on the BFV FHE scheme, it encrypts polynomials, and we can set the…
Guerlando OCs
  • 35
  • 7
2
votes
1 answer

How to generate a circuit for SHA-256?

In "A Boolean Circuit for SHA-256" by Steven Goldfeder, the author gives a Boolean circuit for SHA-256. I find this method very complicated. May I ask how to construct a Boolean circuit for a hash function? I mean, given an algorithm of a hash…
user77340
  • 777
  • 3
  • 12
2
votes
1 answer

Does the degree of this polynomial matter to achieve zero-knowledge? PlonK question

I was reading the paper PlonK and in the Round 1 of the claim to achieve zero-knowledge by adding random multiples (of degree one) of the polynomial $Z_H = x^n - 1$ to the secret polynomials. Here, $H$ is the set containing the $n$-th roots of unity…
Bean Guy
  • 593
  • 2
  • 7
2
votes
0 answers

Depth of $\operatorname{SHA-256}$ implementation by fan-in $2$ and fan-out $1$ Boolean circuits?

A fan-in $2$ and fan-out $1$ Boolean circuit is a circuit consisting of $\operatorname{AND}$, $\operatorname{OR}$ and $\operatorname{NOT}$ gates where number of inputs to $\operatorname{AND}$ and $\operatorname{NOT}$ are constrained to be $2$ and…
Turbo
  • 882
  • 4
  • 12
1
2 3