I am currently trying to get a grasp of homomorphic encryption and are working through the paper by Armknecht et al. (2015): https://eprint.iacr.org/2015/1192 which gives a nice overview and clear definitions.
The only thing I stumble across is the definition of the "depth of a Circuit".
The paper defines the set of Circuits C as
We begin with a space P = {0, 1}, which we call the plaintext space, and
a family F of functions from tuples of plaintexts to P. We can express such a
function as a Boolean circuit on its inputs. If we denote this circuit by C, we
use ordinary function notation C(m1, m2, . . . , mn) to denote the evaluation of
the circuit on the tuple (m1, m2, . . . , mn).
Later on it defines a levelled homomorphic scheme (Definition 8) as
A C–evaluation scheme
(Gen, Enc, Eval, Dec) is called a levelled homomorphic scheme if it takes an
auxiliary input α = d to Gen which specifies the maximum depth of circuits
that can be evaluated. Further requirements are correctness, compactness and
that the length of the evaluation output does not depend on d.
This introduces the notion of the Circuit depth.
My questions here are
- So does Circuit here mean an arbitrary combination of the elementary logical circuits (and, or, xor, not)?
- Is the circuit depth than considered the (minimal?) number of (elementary?) circuits combined in sequence?
or stated otherwise:
What are the exact definition of a Circuit, a Boolean Circuit and Circuit depths?
Thanks already in advance!
