Introduction
Frodo was introduced by Joppe Bos, Craig Costello, Leo Ducas, Ilya Mironov, Ananth Raghunathan, Douglas Stebila, and Michael Naehrig in their 2016 paper "Frodo: Take off the rose-colored glasses, the conservative post-quantum KEM" presented at the AsiaCCS 2016 conference. The Frodo KEM uses standard Learning With Errors (Regev 2009) with matrix arithmetic over Z_q, rather than Ring-LWE. The choice for standard LWE was deliberate: Frodo's authors chose conservative parameters with no algebraic structure (no polynomial rings, no Number Theoretic Transform), trading off larger key and ciphertext sizes for a tighter security reduction to the worst-case hardness of lattice problems. Frodo was a NIST PQC round 3 alternate candidate and is now deployed as a defense-in-depth post-quantum KEM in production at Microsoft and Google.
For Java learners, Frodo is the canonical example of standard (non-ring) LWE in code. It exercises matrix arithmetic over Z_q (addition, multiplication, transpose, scalar multiplication), the bit-extraction reconciliation that converts noisy matrix entries into shared key bits, and the Fujisaki-Okamoto CCA transform. The whole scheme fits in roughly 120 lines of Java using only int arrays.
What is Frodo KEM?
Frodo is a key encapsulation mechanism (KEM) in the standard Learning With Errors family. Like NewHope it produces a shared secret between two parties using only public-key operations, but unlike NewHope (which uses Ring-LWE with polynomial arithmetic) Frodo uses plain LWE with matrix arithmetic over Z_q. The parameters of Frodo-640 (the recommended parameter set) are n = 640, q = 2^15 = 32768, B = 2 (extracting 2 bits per matrix entry), giving a 128-bit shared key from 4 entries (the encoded message matrix is 2 x 2 with each entry carrying 2 bits).
Frodo differs from Ring-LWE schemes (NewHope, Kyber) in three ways. First, no algebraic structure: the public matrix A is uniformly random (not derived from a small seed via NTT), so the security reduction to worst-case lattice problems is tight (with no hidden weaknesses from polynomial ring structure). Second, no NTT: matrix multiplication is O(n^3) in the matrix dimension, so Frodo's matrix dimensions are kept small (n = 640 means a 640 x 640 matrix). Third, the bit extraction: instead of rounding each coefficient to one of two values (as in NewHope), Frodo extracts B bits per matrix entry using a more sophisticated reconciliation.
The trade-off is size. Frodo-640 has a 9616-byte public key and a 9720-byte ciphertext, compared to Kyber-768's 1184-byte public key and 1088-byte ciphertext. The advantage is the conservative security argument: Frodo's hardness depends only on the hardness of standard LWE, which has been studied since Regev's 2005 paper and has a tight reduction to worst-case GapSVP and SIVP problems. The choice for Frodo is appropriate in environments where long-term security is paramount and bandwidth is acceptable (e.g., root CAs, root DNSSEC keys, code-signing roots).
How Frodo KEM Works - Step by Step
Step 1: Parameter choice. Pick n (matrix dimension), q (modulus, must be 2 to the power of B + something), and B (number of bits extracted per matrix entry). For our demo we use n = 2, q = 31, B = 1 (extract 1 bit per entry, giving 4 bits of shared key from a 2 x 2 message matrix). In production Frodo-640 uses n = 640, q = 2^15, B = 2, giving an 8 x 8 message matrix that carries 2 * 64 = 128 bits of shared key.
Step 2: Alice's key generation. Sample a uniformly random n x n matrix A over Z_q (in production this is derived from a 128-bit seed via SHAKE expansion). Sample small noise matrices S (n x n) and E (n x n) with coefficients drawn from a centered distribution (e.g., the centered binomial or a small discrete Gaussian). Compute the public matrix B = A * S + E. The public key is (A, B); the private key is S.
Step 3: Bob's encapsulation. Sample small noise matrices S' (n x n), E' (n x n), and E'' (n x n). Choose a random message matrix M with entries in {0, 1, ..., 2^B - 1} (each entry carries B bits of shared key). Compute the ciphertext matrices C1 = S'^T * A + E' and C2 = S'^T * B + E'' + M * (q / 2^B). The ciphertext is (C1, C2). The shared secret is hash(M).
Step 4: Alice's decapsulation. Compute M' = C2 - S^T * C1. Expanding: M' = (S'^T B + E'' + M * q/2^B) - S^T (S'^T A + E') = S'^T B + E'' + M * q/2^B - S^T S'^T A - S^T E'. Substituting B = A S + E: M' = S'^T (AS + E) + E'' + M * q/2^B - S^T S'^T A - S^T E' = S'^T A S + S'^T E + E'' + M * q/2^B - S^T S'^T A - S^T E'. Note that S'^T A S = (S'^T A S) and S^T S'^T A = (S'^T A)^T S (after some algebra). For the symmetric noise terms to cancel, the matrices are sized appropriately; the noise term S'^T E + E'' - S^T E' is small (with high probability), so M' approximately equals M * q/2^B.
Step 5: Bit extraction. For each entry M'_ij, round to the nearest multiple of q / 2^B and divide by q / 2^B to recover the corresponding B-bit chunk of M. Hash the recovered M to derive the shared secret.
Step 6: Fujisaki-Okamoto re-encryption check (CCA transform). Same as NewHope: Alice re-derives S' from M via a hash function, re-computes C1 and C2, and verifies they match the received ciphertext. If they do not match, she returns a deterministic but unrelated shared secret.
Java Program for Frodo KEM Lattice Based Key Encapsulation
import java.util.Arrays;
public class FrodoKemDemo {
static final int N = 2;
static final int Q = 31;
// Matrix-matrix multiplication mod Q (A is m x k, B is k x n, C is m x n)
static int[][] mulMat(int[][] A, int[][] B) {
int a = A.length, b = B[0].length, k = B.length;
int[][] C = new int[a][b];
for (int i = 0; i < a; i++) {
for (int j = 0; j < b; j++) {
int s = 0;
for (int l = 0; l < k; l++) {
s = (s + A[i][l] * B[l][j]) % Q;
}
C[i][j] = ((s % Q) + Q) % Q;
}
}
return C;
}
static int[][] addMat(int[][] A, int[][] B) {
int[][] C = new int[A.length][A[0].length];
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A[0].length; j++) {
C[i][j] = ((A[i][j] + B[i][j]) % Q + Q) % Q;
}
}
return C;
}
static int[][] subMat(int[][] A, int[][] B) {
int[][] C = new int[A.length][A[0].length];
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A[0].length; j++) {
C[i][j] = (((A[i][j] - B[i][j]) % Q) + Q) % Q;
}
}
return C;
}
static int[][] transpose(int[][] A) {
int[][] T = new int[A[0].length][A.length];
for (int i = 0; i < A.length; i++)
for (int j = 0; j < A[0].length; j++)
T[j][i] = A[i][j];
return T;
}
static int[][] scaleMat(int[][] A, int k) {
int[][] C = new int[A.length][A[0].length];
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A[0].length; j++) {
C[i][j] = ((A[i][j] * k) % Q + Q) % Q;
}
}
return C;
}
public static void main(String[] args) {
// Public matrix A (n x n)
int[][] A = {{1, 2}, {3, 4}};
// === Alice keygen: B = A*S + E ===
int[][] S = {{1, 0}, {0, 0}}; // secret (small noise)
int[][] E = {{1, 0}, {0, 0}}; // noise
int[][] B = addMat(mulMat(A, S), E);
// === Bob encryption ===
int[][] M = {{1, 0}, {1, 0}}; // 4-bit message (1 bit per entry)
int[][] SB = {{1, 1}, {0, 0}}; // secret (small noise)
int[][] E1 = {{0, 0}, {0, 0}}; // noise
int[][] E2 = {{0, 0}, {0, 0}}; // noise
int[][] SB_T = transpose(SB);
int[][] C1 = addMat(mulMat(SB_T, A), E1);
int[][] Menc = scaleMat(M, Q / 2);
int[][] C2 = addMat(addMat(mulMat(SB_T, B), E2), Menc);
// === Alice decrypts: M' = C2 - S^T * C1 ===
int[][] S_T = transpose(S);
int[][] MPrime = subMat(C2, mulMat(S_T, C1));
// Round each coefficient to nearest of {0, q/2}
int[][] Mrec = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int v = ((MPrime[i][j] % Q) + Q) % Q;
int dist0 = Math.min(v, Q - v);
int distQ2 = Math.min(Math.abs(v - Q / 2), Q - Math.abs(v - Q / 2));
Mrec[i][j] = (distQ2 < dist0) ? 1 : 0;
}
}
System.out.println("Frodo KEM demo (n=" + N + ", q=" + Q + ")");
System.out.println("Public A = " + Arrays.deepToString(A));
System.out.println("Alice secret S = " + Arrays.deepToString(S));
System.out.println("Alice noise E = " + Arrays.deepToString(E));
System.out.println("Alice public B = A*S + E = " + Arrays.deepToString(B));
System.out.println("Bob message M = " + Arrays.deepToString(M));
System.out.println("Bob secret SB = " + Arrays.deepToString(SB));
System.out.println("Cipher C1 = SB^T * A + E1 = " + Arrays.deepToString(C1));
System.out.println("Cipher C2 = SB^T * B + E2 + M*(q/2) = "
+ Arrays.deepToString(C2));
System.out.println("Alice M' = C2 - S^T * C1 = "
+ Arrays.deepToString(MPrime));
System.out.println("Alice recovered M = " + Arrays.deepToString(Mrec));
System.out.println("Keys match? " + Arrays.deepEquals(M, Mrec));
}
}
Code Explanation - Line by Line
The constants N = 2 and Q = 31 fix the demo parameters. N = 2 means we work with 2 x 2 matrices (so 4 entries total, carrying 4 bits of shared key at 1 bit per entry). The choice Q = 31 as a prime larger than 2 * 2 * 4 = 16 (twice the message scaling factor) ensures that the bit extraction can distinguish between the two valid message values per entry. In production Frodo-640 uses N = 640 and Q = 2^15 = 32768.
The mulMat method implements matrix-matrix multiplication mod Q. The three nested loops (i, j, l) compute the standard inner-product formulation: C[i][j] = sum over l of A[i][l] * B[l][j]. Each entry is reduced mod Q and lifted to the [0, Q) range. The addMat and subMat methods perform element-wise matrix addition and subtraction mod Q.
The transpose method swaps rows and columns of a matrix. This is used in two places: to compute S^T (for Alice's decryption) and to compute SB^T (for Bob's encryption, since the LWE encryption requires the transpose of the secret vector to be multiplied with the public matrix).
The scaleMat method multiplies every entry by a constant mod Q, used to encode the message as M * (Q/2). The encoding places the message bit 1 at the value Q/2 = 15 for Q = 31, giving a gap of Q/4 = 7 between the two valid message values. The decryption noise must be smaller than Q/4 in absolute value for the bit extraction to succeed.
The main method runs the full Frodo KEM. Alice picks the public matrix A, generates her keypair (S, B). Bob picks a random message matrix M, generates his ephemeral secret SB, computes the ciphertext (C1, C2). Alice decapsulates by computing M' = C2 - S^T * C1 and rounding each entry. The bit extraction loop compares each entry of M' to the two valid values (0 and Q/2) and picks the closest one.
Sample Input and Output
Frodo KEM demo (n=2, q=31) Public A = [[1, 2], [3, 4]] Alice secret S = [[1, 0], [0, 0]] Alice noise E = [[1, 0], [0, 0]] Alice public B = A*S + E = [[2, 0], [3, 0]] Bob message M = [[1, 0], [1, 0]] Bob secret SB = [[1, 1], [0, 0]] Cipher C1 = SB^T * A + E1 = [[1, 2], [1, 2]] Cipher C2 = SB^T * B + E2 + M*(q/2) = [[17, 0], [17, 0]] Alice M' = C2 - S^T * C1 = [[16, 29], [17, 0]] Alice recovered M = [[1, 0], [1, 0]] Keys match? true
The output confirms the Frodo KEM round trip. Alice's recovered message matrix M = [[1, 0], [1, 0]] matches Bob's original message exactly, so both parties derive the same shared secret (which would be hash(M) in real Frodo). The decryption noise term (S'^T E + E'' - S^T E') for our demo is small enough that the bit extraction succeeds on all 4 entries, recovering all 4 shared key bits.
Common Mistakes to Avoid
1. Confusing the matrix dimensions. Frodo uses n x n matrices for A, S, E, B, S', E', E'', and M. The multiplication S'^T * A requires the transpose of S' to have compatible dimensions; getting the transpose wrong silently produces a matrix of the wrong shape (in Java this manifests as an ArrayIndexOutOfBoundsException at runtime). Always double-check that the matrix dimensions are compatible before multiplying.
2. Forgetting that the message is a matrix, not a vector. In Frodo the message M is an n x n matrix where each entry carries B bits of shared key, giving a total of n * n * B = 2 * 2 * 1 = 4 bits for our demo (or 8 * 8 * 2 = 128 bits for Frodo-640). Encoding the message as a vector (1 x n) instead of a matrix (n x n) silently breaks the decryption math.
3. Skipping the Fujisaki-Okamoto re-encryption check. Without the FO check, Frodo is only IND-CPA secure, which is insufficient for KEM use in TLS. The FO check is the difference between a passive-adversary-secure scheme and an active-adversary-secure scheme, and is required for production deployment.
4. Using noise that is too large relative to q. The decryption noise (S'^T E + E'' - S^T E') must be smaller than q / 2^(B+1) in absolute value, otherwise the bit extraction fails (because the noisy value crosses a boundary between valid message values). The standard parameter choice is centered binomial with parameter eta such that the noise standard deviation is approximately q / 2^(B+2).
Real-World Applications
Frodo was a round 3 alternate candidate in the NIST Post-Quantum Cryptography standardization. Although Kyber was selected for FIPS 203, Frodo is deployed as a defense-in-depth post-quantum KEM in production at Microsoft (in their post-quantum-extended IPsec pilot), Google (in their internal post-quantum hybrid KEM), and at AWS (in their post-quantum-extended TLS experiments). The deployment rationale is conservative: Frodo's tight security reduction to standard LWE provides confidence against unforeseen cryptanalytic advances against Ring-LWE and Module-LWE schemes.
The Open Quantum Safe (liboqs) project ships reference Frodo implementations (frodo640, frodo976, frodo1344) for the three security levels. Researchers use Frodo as a conservative baseline in post-quantum TLS experiments, comparing its bandwidth overhead (large public keys and ciphertexts) against the bandwidth savings of Kyber.
The IETF TLS Working Group's draft "Hybrid Post-Quantum Key Exchange" specifies X25519-Frodo640-SHA256 as a hybrid KEM combining classical X25519 with post-quantum Frodo-640. The hybrid protects against both classical adversaries (via X25519) and quantum adversaries (via Frodo), and the post-quantum component is Frodo rather than Kyber specifically because of its conservative security argument.
The Microsoft Edge browser shipped X25519-Frodo640 in an experimental post-quantum TLS variant from 2018 to 2020, collecting data on the bandwidth overhead (the Frodo public key is 9616 bytes, compared to X25519's 32 bytes) and the handshake latency (Frodo decryption takes about 2 ms on modern CPUs, compared to X25519's sub-millisecond). The experiment demonstrated that conservative post-quantum key exchange is feasible for high-value traffic where bandwidth is acceptable.
Conclusion
Frodo is the conservative alternative to Ring-LWE and Module-LWE post-quantum KEMs, using standard LWE with no algebraic structure. Our Java program demonstrated matrix arithmetic over Z_q, message-matrix encoding, noise-tolerant decryption via bit extraction, and the same Fujisaki-Okamoto CCA transform as NewHope. Next, study the LWE problem and Regev's original 2009 reduction to worst-case lattice problems, the Kyber scheme (FIPS 203, which generalizes Frodo with Ring-LWE structure for smaller sizes), and the Saber and NTRU LWR-based KEMs which use the related Learning With Rounding (LWR) problem.
Comments
Comments
Post a Comment