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 operation is much faster than AND operations. 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 [here]. The usage of LowMC [1] operations considerably improves the performance of the method. Dinur et al [2] proposed interporation attacks on LowMC and a fuller cryptoanalysis was undertaken by Liu et al in 2020 [3].
LowMC |
Method
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 overhea 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 \oplus C.D \oplus E.F \oplus 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 AND depth 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, 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 \oplus b.c, a \oplus b \oplus a.c, a \oplus b \oplus c \oplus a.b)\)
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 x 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;
The coding is:
#include#include #include #include #include #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; 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; return 0; }
A sample run:
Message: 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000110101 Key: 41 Ciphertext: 1110110110111000010101010101101110010000011001011011011011000000010110110110110000100101111101001101001000001111001000010101001111100011101000010111110110111010101011001000101100110101011000100111101111111011110001010101010110111001100010000111001010011110 Encryption followed by decryption of plaintext: 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000110101 LowMC matrices and constants =========================== Block size: 256 Key size: 80 Rounds: 12
The code is:
Reference
[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].