A circuit compiling device and circuit evaluation device

A compiling method for compiling a function into a binary circuit,

• wherein function computes at least one function output bit(s) from a plurality of function input bits,
• wherein the circuit comprises a plurality of circuit wires and at least one conjunction subcircuit(s),
• wherein the circuit wires comprise a plurality of input wires and at least one output wire(s),
• wherein the input wires correspond to the plurality of function input bits,
• wherein the at least one output wire(s) correspond to the at least one function output bit(s),
• wherein the at least one function output bit(s) comprise a first function output bit,
• wherein the comprises at least one conjunction subcircuit(s),
• wherein the at least one conjunction subcircuit(s) comprises a first conjunction subcircuit,
• wherein each of the at least one conjunction subcircuit(s) is arranged to compute a conjunction of at least two function input bits and at least one XOR subcircuit(s),
• wherein each of the at least one or more XOR subcircuit(s) are arranged to compute the function output bit, the compiling method comprising:
• representing each of the at least one function output bit(s) as a sum of interpolation terms,
• wherein each of interpolation terms is a product of zero or more function input bits,
• wherein the plurality of function input bits and the interpolation terms of the at least one function output bit(s) together form a plurality of interpolation terms;
• selecting a first interpolation term and a second interpolation term from the plurality of interpolation terms for each current interpolation term of the plurality of interpolation terms, when the current interpolation term is a product of multiple function input bits,
• wherein the current interpolation term is computed as a product of the first interpolation term and the second interpolation term,
• wherein the current interpolation term is arranged to signaling a selection error if no first interpolation term and second interpolation term can be selected;
• compiling the first conjunction subcircuit computing the current interpolation term for each current interpolation term of the plurality of interpolation terms, if the current interpolation term is a product of multiple function input bits, wherein the compiling the first conjunction subcircuit comprises providing a circuit wire corresponding to the current interpolation term as a conjunction of a first circuit wire corresponding to the first interpolation term and a second circuit wire corresponding to the second interpolation term;
• and
• compiling at least one XOR subcircuit(s) for each current interpolation term of the plurality of interpolation terms, if the current interpolation term is a product of multiple function input bits,
• wherein the first function output bit is computed by a current XOR subcircuit is represented as a sum of current interpolation terms,
• wherein the compiling of the current XOR subcircuit comprises providing an output wire of the at least one output wires(s) corresponding to the function output bit as a XOR of wires corresponding to the current interpolation terms.

A function evaluation device comprising:

• a memory circuit,
• wherein the memory circuit is configured to store a function and circuit,
• wherein the function is arranged to compute at least one function output bit(s) from a plurality of function input bits,
• wherein each function output bit is representable as a sum of interpolation terms,
• wherein each of the sum of interpolation term is a product of zero or more function input bits,
• wherein the plurality of function input bits and the interpolation terms forming a plurality of interpolation terms,
• wherein the circuit comprises:
• circuit wires,
• wherein the circuit wires comprise a plurality of input wires and at least one circuit output wire(s),
• wherein the plurality of input wires correspond to the plurality of function input bits,
• wherein the at least one output wire(s) correspond to the at least one function output bit(s) bits;
• at least one conjunction subcircuit(s),
• wherein the at least one conjunction subcircuit(s) comprises a first conjunction subcircuit,
• wherein each of the at least one or more conjunction subcircuit(s) is arranged to compute a conjunction of at least two function input bits,
• wherein the first conjunction subcircuit is arranged to provide a circuit wire corresponding to a current interpolation term as a conjunction of a first circuit wire,
• wherein the first circuit wire corresponds to a first interpolation term,
• wherein the second circuit wire corresponds to a second interpolation term;
• and
• at least one XOR subcircuit(s),
• wherein each of the at least one XOR subcircuit(s) is arranged to compute the first function output bit,
• wherein the first function output bit is computed by a current XOR subcircuit,
• wherein the first function output bit is represented as a sum of current interpolation terms,
• wherein the current XOR subcircuit provides an output wire of the at least one output wires(s) corresponding to the function output bit as a XOR of wires corresponding to the current interpolation terms;
• and
• a processor circuit,
• wherein the processor circuit is configured to obtain the plurality of input bits, wherein the processor circuit is configures to evaluate the function on the plurality of input bits by evaluating the circuit.

A function evaluation method for evaluating a function,

• wherein the function computes at least one function output bit(s) from a plurality of function input bits,
• wherein each function output bit of the at least one function output bit(s) is represented as a sum of interpolation terms,
• wherein each interpolation term of the sum of interpolation terms is a product of zero or more function input bits,
• wherein the plurality of function input bits and the interpolation terms of the at least one function output bit(s) together form a plurality of interpolation terms, the function evaluation method comprising:
• obtaining a circuit for the function, the circuit comprising:
• circuit wires,
• wherein the circuit wires comprise a plurality of input wires and at least one circuit output wire(s),
• wherein the plurality of input wires correspond to the plurality of function input bits,
• wherein the at least one output wire(s) correspond to the at least one function output bit(s);
• at least one conjunction subcircuit(s),
• wherein the at least one conjunction subcircuit(s) comprises a first conjunction subcircuit,
• wherein each of the at least one or more conjunction subcircuit(s) is arranged to compute a conjunction of at least two function input bits,
• wherein the first conjunction subcircuit is arranged to provide a circuit wire corresponding to a current interpolation term as a conjunction of a first circuit wire,
• wherein the first circuit wire corresponds to a first interpolation term,
• wherein the second circuit wire corresponds to a second interpolation term;
• and
• at least one XOR subcircuit(s),
• wherein each of the at least one XOR subcircuit(s) is arranged to compute the first function output bit,
• wherein the first function output bit is computed by a current XOR subcircuit,
• wherein the first function output bit is represented as a sum of current interpolation terms,
• wherein the current XOR subcircuit providing a output wire of the at least one output wires(s) corresponding to the function output bit as a XOR of wires corresponding to the current interpolation terms;
• obtaining the plurality of input bits;
• and
• evaluating the function on the plurality of input bits by evaluating the circuit.