How is HQC substantially different from RLWE?
138 views
Skip to first unread message
Bobby McGee
Oct 1, 2025, 12:43:32 PM (5 days ago) Oct 1
to pqc-forum
How is HQC much different from RLWE?
Say we have 1-dimensional Kyber with public a, as+e, and HQC with public h, hx+y. Here a, h are uniform, while s, e, x, y are "small" (CBD or fixed low weight respectively), and arithmetic is in Z[x]/(q, x^n+1), Z[x]/(2, x^n-1) respectively. The distributions of the public keys are supposed to be computationally uniform and it should be difficult to find appropriate s, x satisfying the relations.
x^n+1 is chosen irreducible over Q (2-power cyclotomic) and q s.t. x^n+1 (mostly) factors over F_q for NTT optimization. On the other hand, (x^n-1)/(x-1) is irreducible over F_2 to prevent algebraic simplification, and the binary, cyclic structure is for convenience and optimization. Despite the differences in the ring structure, security seems to scale roughly with the size of the ring.
Encryption/decryption for both schemes follow the same "noisy Elgamal" setup, with slightly different error correction (modulation in the "q" direction and concatenated RS-RM codes respectively).
Obviously there are many analogies between code and lattice problems. To someone not familiar with the security reductions from "hard" problems (like myself), how would you justify standardizing both Kyber and HQC when they look so superficially similar? [Perhaps begging the question, why not BIKE?]
Maybe the answer is "go read [X], [Y], [Z] and learn what underlies the security and stop pestering pqc-forum," but is there a digestible or obvious reason HQC is substantially different from a RLWE scheme?
Say we have 1-dimensional Kyber with public a, as+e, and HQC with public h, hx+y. Here a, h are uniform, while s, e, x, y are "small" (CBD or fixed low weight respectively), and arithmetic is in Z[x]/(q, x^n+1), Z[x]/(2, x^n-1) respectively. The distributions of the public keys are supposed to be computationally uniform and it should be difficult to find appropriate s, x satisfying the relations.
x^n+1 is chosen irreducible over Q (2-power cyclotomic) and q s.t. x^n+1 (mostly) factors over F_q for NTT optimization. On the other hand, (x^n-1)/(x-1) is irreducible over F_2 to prevent algebraic simplification, and the binary, cyclic structure is for convenience and optimization. Despite the differences in the ring structure, security seems to scale roughly with the size of the ring.
Encryption/decryption for both schemes follow the same "noisy Elgamal" setup, with slightly different error correction (modulation in the "q" direction and concatenated RS-RM codes respectively).
Obviously there are many analogies between code and lattice problems. To someone not familiar with the security reductions from "hard" problems (like myself), how would you justify standardizing both Kyber and HQC when they look so superficially similar? [Perhaps begging the question, why not BIKE?]
Maybe the answer is "go read [X], [Y], [Z] and learn what underlies the security and stop pestering pqc-forum," but is there a digestible or obvious reason HQC is substantially different from a RLWE scheme?
Reply all
Reply to author
Forward
0 new messages