Low Multiplicative Complexity — LowMC
Let’s take six numbers: 6, 3, 10, 5, 9 and 3. We want you to multiply pairs of numbers and then add them. For this most of us we would compute 18, 50 and 27, and then add these to get 95. The multiplication part had three operations and the add was just a single operation. If we do this for many pairs we can see the computation gets more timely for the multiplication, and the end part is perhaps still just a single addition.
When we implement cryptography we typically use two operations: AND and XOR. These can be seen as a multiplier and adder, respectively. Often from a silicon point-of-view, we prefer AND gates, as they take up less silicon. But when it comes to performance, the XOR (add) operations are often much faster and less of an overhead than AND (multiplication) operations. In many crypto systems we use GF(2) for operations, and where we have a 0 or a 1 and have no carry over from arithmetic operations. Often we define that XOR operations (⨁) are almost “free” as they can have a minimial overhead. For example we might have an operation of:
Z = A.B ⨁ C.D ⨁ E.F ⨁ G.H
In this case we have four multiplications, and one adding operation. Thus the multiplications will have a much greater significants in the time to compute the result than the add operation.
