I know that Boolean circuits and Arithmetic circuits are two different ways of representing a computation. But I want to know how to instantiate arithmetic circuits and it's computation in practice. For example, when we multiply two l bits numbers, we say that arithmetic circuits are efficient because it represent those two nums as two field elements, and only need 1 multiplication gate. But I don't understand: don't we have to represent those two nums in bits in machine code? And do we have to represent that multiplication gate in basic blocks such as and-gate/xor-gate...or is there a real circuit structure is multiplication gate? Sorry for such a dummy question, but this confuse me for quite a long time and I can't find the answer by myself. So could anyone give me some guide or some paper to this question? Great thanks.
3
-
$\begingroup$ Fields of characteristic 2 (i.e., of order $2^n$) are useful for easier security proofs (e.g., search for "tower field construction" and AES). Fields of odd characteristic are implemented for example in fully homomorphic encryption. $\endgroup$– j.p.Commented May 18, 2021 at 6:25
-
$\begingroup$ @j.p. I'm sorry, I did't get what you mean. First, is field of 2^n a high level representation of boolean circuit or considered as an arithmetic circuit? I think AES is usually implemented in boolean circuit right? Second, my question is really about practical representation, so do we still have to represent those arithmetic circuits into real boolean gates for computation in reality? If so, why we can get those efficiency improvement? $\endgroup$– rzxhCommented May 18, 2021 at 9:21
-
$\begingroup$ The field with $2^n$ elements is only used for the proofs, the HW-implementation is then in bits. $\endgroup$– j.p.Commented May 18, 2021 at 18:01
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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 gate.
The total number of gates and the depth of the AC are typical measures of complexity. Size and bit structure of inputs does not explicitly come into it, each operation is considered of some fixed complexity.
The goal is to find the minimum complexity circuit realizing a certain formula.
-
$\begingroup$ Thanks for your answer. But I still have a question, what's the meaning of this different representation? Even we can represent a computation in a simpler way, when doing those computation in reality, we still have to use those boolean circuits to transform the corresponding operation right? If so, why we can get efficiency improvement? $\endgroup$– rzxhCommented May 18, 2021 at 9:27
-
$\begingroup$ in addition to theoretical interest where AC models are used in proofs, the simple less complicated representation may indicate a weakness from a cryptanalytic point of view. an attacker may implement the function in a different way and obtain a speed advantage in brute force attacks. $\endgroup$– kodluCommented May 18, 2021 at 22:09