Low Multiplicative Complexity — LowMC
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.
Thus we see a new principle — LowMC — and which tries to minimise the number of multiplicative operations. This applies especially to areas of homomorphic encryption, MPC (Multiparty Computation) and in zero-knowledge proofs. An example usage is in the Picnic post-quantum cryptography method. The usage of LowMC operations considerably improves the performance of the method, and was proposed by Albrecht et al [here][1]:
Two key metrics we used to assess LowMC methods are:
- Multiplicative complexity (MC). This is the number of multiplications (AND gates) in a circuit.
- Multiplicative depth. With this, we aim for a low ANDdepth for homomorphic encryption methods.
LowMC is defined as a flexible block cipher based using an SPN (Substitution-Permutation Network) with a given block size (n), a key size (k), a number of S-box units (m), and the allowed data complexity of attacks (d). An S-box is a look-up table to map one data element to another (and which is reversed when decrypting), and a permutation maps shuffles the bit inputs in a given way (and then unshuffles for decryption).
We then determine the number of rounds required to define the security required. A sample run is [here]:
Blocksize=256, S-boxes=63, Complexity=128, Keysize=128
----------------------------------------------
Distinguisher Rounds
----------------------------------------------
Statistical with state guessing 5
Boomerang attack 6
Derivative + bit guessing 11
Derivative + interpolation 14
Impossible polytopic attack 7
----------------------------------------------
Secure rounds: 14
In this case for a blocksize of 256, 63 S-boxes, a complexity of 128 and a key size of 128, we need 14 secure rounds. Two defined instances are:
- Low MC-80. k=80 bits, block size = 256 bits, 49 S-boxes, data limit = 64, and 11 rounds.
- Low MC-128. k=128 bits, block size = 256 bits, 63 S-boxes, data limit = 128, and 12 rounds.
Overall we operate on a 256-bit state value (for a 256-bit block size). A single round of LowMC can be represented as [1]:
We can see we have a number of 3-bit S-boxes (m), an Affine layer (which permutates the bits) and a number of XOR gates with integrate with the key). Only 3m < n bits go into S-boxes (where m is the number of S-boxes), and where n − 3m bits will remain unchanged. The method uses a 3-bit S-box defined by:
S(a, b, c) = (a ⊕ bc, a ⊕ b ⊕ ac, a ⊕ b ⊕ c ⊕ ab)
If we use the code here we get:
A B C S1 S2 S3
0 0 0 0 0 0 (0x00)
0 0 1 0 0 1 (0x01)
0 1 0 0 1 1 (0x03)
0 1 1 1 1 0 (0x06)
1 0 0 1 1 1 (0x07)
1 0 1 1 0 0 (0x04)
1 1 0 1 0 1 (0x05)
1 1 1 0 1 0 (0x02)
The values for the S-box are then:
Sbox ={ 0x00, 0x01, 0x03, 0x06, 0x07, 0x04, 0x05, 0x02 };And for decryption, the inverse of the S-box is:
InvSbox = { 0x00, 0x01, 0x07, 0x02, 0x05, 0x06, 0x03, 0x04 };For example, when we are encrypting, we map 010b to 011b, and which maps back to 010b with the inverse S-Box. The Affine Layer involves multiplying the current state with a random matrix (LMatric(i)):
state = MultiplyWithGF2Matrix(LMatrix(i),state)
state = state + Constants(i)
In each round, LMatrix(i) is an n × n matrix and selected independently with random values. Constants(i) are also selected randomly. The process to encrypt is:
block c = message ^ roundkeys[0];
for (unsigned r = 1; r <= rounds; ++r) {c = Substitution(c); // S-Boxes
c = MultiplyWithGF2Matrix(LinMatrices[r - 1], c); // Multiply with matrix
c ^= roundconstants[r - 1];
c ^= roundkeys[r]; // Ex-or with round keys
}
return c;
And to decrypt, we perform the inverse:
block c = message;
for (unsigned r = rounds; r > 0; --r) {c ^= roundkeys[r];
c ^= roundconstants[r - 1];
c = MultiplyWithGF2Matrix(invLinMatrices[r - 1], c);
c = invSubstitution(c);
}
c ^= roundkeys[0];
return c;
An outline of the coding for the encryption and decryption process is [here]:
#include "LowMC.h"
/////////////////////////////
// LowMC functions //
/////////////////////////////
block LowMC::encrypt(const block message) {
block c = message ^ roundkeys[0];
for (unsigned r = 1; r <= rounds; ++r) {
c = Substitution(c);
c = MultiplyWithGF2Matrix(LinMatrices[r - 1], c);
c ^= roundconstants[r - 1];
c ^= roundkeys[r];
}
return c;
}
block LowMC::decrypt(const block message) {
block c = message;
for (unsigned r = rounds; r > 0; --r) {
c ^= roundkeys[r];
c ^= roundconstants[r - 1];
c = MultiplyWithGF2Matrix(invLinMatrices[r - 1], c);
c = invSubstitution(c);
}
c ^= roundkeys[0];
return c;
}
void LowMC::set_key(keyblock k) {
key = k;
keyschedule();
}
void LowMC::print_matrices() {
std::cout << "LowMC matrices and constants" << std::endl;
std::cout << "============================" << std::endl;
std::cout << "Block size: " << blocksize << std::endl;
std::cout << "Key size: " << keysize << std::endl;
std::cout << "Rounds: " << rounds << std::endl;
std::cout << std::endl;std::cout << "Linear layer matrices" << std::endl;
std::cout << "---------------------" << std::endl;
for (unsigned r = 1; r <= rounds; ++r) {
std::cout << "Linear layer " << r << ":" << std::endl;
for (auto row : LinMatrices[r - 1]) {
std::cout << "[";
for (unsigned i = 0; i < blocksize; ++i) {
std::cout << row[i];
if (i != blocksize - 1) {
std::cout << ", ";
}
}
std::cout << "]" << std::endl;
}
std::cout << std::endl;
}
std::cout << "Round constants" << std::endl;
std::cout << "---------------------" << std::endl;
for (unsigned r = 1; r <= rounds; ++r) {
std::cout << "Round constant " << r << ":" << std::endl;
std::cout << "[";
for (unsigned i = 0; i < blocksize; ++i) {
std::cout << roundconstants[r - 1][i];
if (i != blocksize - 1) {
std::cout << ", ";
}
}
std::cout << "]" << std::endl;
std::cout << std::endl;
}
std::cout << "Round key matrices" << std::endl;
std::cout << "---------------------" << std::endl;
for (unsigned r = 0; r <= rounds; ++r) {
std::cout << "Round key matrix " << r << ":" << std::endl;
for (auto row : KeyMatrices[r]) {
std::cout << "[";
for (unsigned i = 0; i < keysize; ++i) {
std::cout << row[i];
if (i != keysize - 1) {
std::cout << ", ";
}
}
std::cout << "]" << std::endl;
}
if (r != rounds) {
std::cout << std::endl;
}
}
}
/////////////////////////////
// LowMC private functions //
/////////////////////////////
block LowMC::Substitution(const block message) {
block temp = 0;
//Get the identity part of the message
temp ^= (message >> 3 * numofboxes);
//Get the rest through the Sboxes
for (unsigned i = 1; i <= numofboxes; ++i) {
temp <<= 3;
temp ^= Sbox[((message >> 3 * (numofboxes - i))
& block(0x7)).to_ulong()];
}
return temp;
}block LowMC::invSubstitution(const block message) {
block temp = 0;
//Get the identity part of the message
temp ^= (message >> 3 * numofboxes);
//Get the rest through the invSboxes
for (unsigned i = 1; i <= numofboxes; ++i) {
temp <<= 3;
temp ^= invSbox[((message >> 3 * (numofboxes - i))
& block(0x7)).to_ulong()];
}
return temp;
}
block LowMC::MultiplyWithGF2Matrix
(const std::vector matrix, const block message) {
block temp = 0;
for (unsigned i = 0; i < blocksize; ++i) {
temp[i] = (message & matrix[i]).count() % 2;
}
return temp;
}
block LowMC::MultiplyWithGF2Matrix_Key
(const std::vector matrix, const keyblock k) {
block temp = 0;
for (unsigned i = 0; i < blocksize; ++i) {
temp[i] = (k & matrix[i]).count() % 2;
}
return temp;
}
void LowMC::keyschedule() {
roundkeys.clear();
for (unsigned r = 0; r <= rounds; ++r) {
roundkeys.push_back(MultiplyWithGF2Matrix_Key(KeyMatrices[r], key));
}
return;
}
void LowMC::instantiate_LowMC() {
// Create LinMatrices and invLinMatrices
LinMatrices.clear();
invLinMatrices.clear();
for (unsigned r = 0; r < rounds; ++r) {
// Create matrix
std::vector mat;
// Fill matrix with random bits
do {
mat.clear();
for (unsigned i = 0; i < blocksize; ++i) {
mat.push_back(getrandblock());
}
// Repeat if matrix is not invertible
} while (rank_of_Matrix(mat) != blocksize);
LinMatrices.push_back(mat);
invLinMatrices.push_back(invert_Matrix(LinMatrices.back()));
}// Create roundconstants
roundconstants.clear();
for (unsigned r = 0; r < rounds; ++r) {
roundconstants.push_back(getrandblock());
}
// Create KeyMatrices
KeyMatrices.clear();
for (unsigned r = 0; r <= rounds; ++r) {
// Create matrix
std::vector mat;
// Fill matrix with random bits
do {
mat.clear();
for (unsigned i = 0; i < blocksize; ++i) {
mat.push_back(getrandkeyblock());
}
// Repeat if matrix is not of maximal rank
} while (rank_of_Matrix_Key(mat) < std::min(blocksize, keysize));
KeyMatrices.push_back(mat);
}
return;
}
/////////////////////////////
// Binary matrix functions //
/////////////////////////////
unsigned LowMC::rank_of_Matrix(const std::vector matrix) {
std::vector mat; //Copy of the matrix
for (auto u : matrix) {
mat.push_back(u);
}
unsigned size = mat[0].size();
//Transform to upper triangular matrix
unsigned row = 0;
for (unsigned col = 1; col <= size; ++col) {
if (!mat[row][size - col]) {
unsigned r = row;
while (r < mat.size() && !mat[r][size - col]) {
++r;
}
if (r >= mat.size()) {
continue;
}
else {
auto temp = mat[row];
mat[row] = mat[r];
mat[r] = temp;
}
}
for (unsigned i = row + 1; i < mat.size(); ++i) {
if (mat[i][size - col]) mat[i] ^= mat[row];
}
++row;
if (row == size) break;
}
return row;
}
unsigned LowMC::rank_of_Matrix_Key(const std::vector matrix) {
std::vector mat; //Copy of the matrix
for (auto u : matrix) {
mat.push_back(u);
}
unsigned size = mat[0].size();
//Transform to upper triangular matrix
unsigned row = 0;
for (unsigned col = 1; col <= size; ++col) {
if (!mat[row][size - col]) {
unsigned r = row;
while (r < mat.size() && !mat[r][size - col]) {
++r;
}
if (r >= mat.size()) {
continue;
}
else {
auto temp = mat[row];
mat[row] = mat[r];
mat[r] = temp;
}
}
for (unsigned i = row + 1; i < mat.size(); ++i) {
if (mat[i][size - col]) mat[i] ^= mat[row];
}
++row;
if (row == size) break;
}
return row;
}
std::vector LowMC::invert_Matrix(const std::vector matrix) {
std::vector mat; //Copy of the matrix
for (auto u : matrix) {
mat.push_back(u);
}
std::vector invmat(blocksize, 0); //To hold the inverted matrix
for (unsigned i = 0; i < blocksize; ++i) {
invmat[i][i] = 1;
}unsigned size = mat[0].size();
//Transform to upper triangular matrix
unsigned row = 0;
for (unsigned col = 0; col < size; ++col) {
if (!mat[row][col]) {
unsigned r = row + 1;
while (r < mat.size() && !mat[r][col]) {
++r;
}
if (r >= mat.size()) {
continue;
}
else {
auto temp = mat[row];
mat[row] = mat[r];
mat[r] = temp;
temp = invmat[row];
invmat[row] = invmat[r];
invmat[r] = temp;
}
}
for (unsigned i = row + 1; i < mat.size(); ++i) {
if (mat[i][col]) {
mat[i] ^= mat[row];
invmat[i] ^= invmat[row];
}
}
++row;
}
//Transform to identity matrix
for (unsigned col = size; col > 0; --col) {
for (unsigned r = 0; r < col - 1; ++r) {
if (mat[r][col - 1]) {
mat[r] ^= mat[col - 1];
invmat[r] ^= invmat[col - 1];
}
}
}
return invmat;
}
///////////////////////
// Pseudorandom bits //
///////////////////////
block LowMC::getrandblock() {
block tmp = 0;
for (unsigned i = 0; i < blocksize; ++i) tmp[i] = getrandbit();
return tmp;
}keyblock LowMC::getrandkeyblock() {
keyblock tmp = 0;
for (unsigned i = 0; i < keysize; ++i) tmp[i] = getrandbit();
return tmp;
}
// Uses the Grain LSFR as self-shrinking generator to create pseudorandom bits
// Is initialized with the all 1s state
// The first 160 bits are thrown away
bool LowMC::getrandbit() {
static std::bitset<80> state; //Keeps the 80 bit LSFR state
bool tmp = 0;
//If state has not been initialized yet
if (state.none()) {
state.set(); //Initialize with all bits set
//Throw the first 160 bits away
for (unsigned i = 0; i < 160; ++i) {
//Update the state
tmp = state[0] ^ state[13] ^ state[23]
^ state[38] ^ state[51] ^ state[62];
state >>= 1;
state[79] = tmp;
}
}
//choice records whether the first bit is 1 or 0.
//The second bit is produced if the first bit is 1.
bool choice = false;
do {
//Update the state
tmp = state[0] ^ state[13] ^ state[23]
^ state[38] ^ state[51] ^ state[62];
state >>= 1;
state[79] = tmp;
choice = tmp;
tmp = state[0] ^ state[13] ^ state[23]
^ state[38] ^ state[51] ^ state[62];
state >>= 1;
state[79] = tmp;
} while (!choice);
return tmp;
}
int main(int argc, char* argv[]) {int key = 1, msg = 1;
if (argc > 1) key = atoi(argv[1]);
if (argc > 2) msg = atoi(argv[2]);
LowMC cipher(key);
block m = (block)msg;
std::cout << "Message: " << m << std::endl;
std::cout << "Key: " << key << std::endl;
m = cipher.encrypt(m);
std::cout << "\nCiphertext:" << std::endl;
std::cout << m << std::endl;
m = cipher.decrypt(m);
std::cout << "\nEncryption followed by decryption of plaintext:" << std::endl;
std::cout << m << std::endl;
std::cout << char(m.to_ulong()) << std::endl;
return 0;
}
A sample run [here]:
Message: 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000110101
Key: 41
Ciphertext:
1110110110111000010101010101101110010000011001011011011011000000010110110110110000100101111101001101001000001111001000010101001111100011101000010111110110111010101011001000101100110101011000100111101111111011110001010101010110111001100010000111001010011110
Encryption followed by decryption of plaintext:
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000110101
The code is:
If you want to see an application of LowMC, have a look at Picnic:
Back] Picnic is one of the alternative finalists for the NIST standard for PQC (Post Quantum Cryptography) [1]. In the…asecuritysite.com
Dinur et al [2] proposed interporation attacks on LowMC and and a fuller cryptoanalysis was undertaken by Liu et al in 2020 [3].
References
[1] Albrecht, M. R., Rechberger, C., Schneider, T., Tiessen, T., & Zohner, M. (2015, April). Ciphers for MPC and FHE. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 430–454). Springer, Berlin, Heidelberg [here].
[2] Dinur, I., Liu, Y., Meier, W., & Wang, Q. (2015, November). Optimized interpolation attacks on LowMC. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 535–560). Springer, Berlin, Heidelberg [here].
[3] Liu, F., Isobe, T., & Meier, W. (2020). Cryptanalysis of Full LowMC and LowMC-M with Algebraic Techniques. IACR Cryptol. ePrint Arch, 1034, 2020 [here].