| Internet-Draft | Kemeleon | October 2026 |
| Günther, et al. | Expires 26 April 2027 | [Page] |
This document specifies Kemeleon encoding algorithms for encoding ML-KEM encapsulation keys and ciphertexts as random bytestrings. Kemeleon encodings provide obfuscation of encapsulation keys and ciphertexts, relying on module LWE assumptions.¶
This note is to be removed before publishing as an RFC.¶
The latest revision of this draft can be found at https://ssveitch.github.io/draft-kemeleon/draft-irtf-cfrg-kemeleon.html. Status information for this document may be found at https://datatracker.ietf.org/doc/draft-irtf-cfrg-kemeleon/.¶
Source for this draft and an issue tracker can be found at https://github.com/ssveitch/draft-kemeleon.¶
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶
This Internet-Draft will expire on 26 April 2027.¶
Copyright (c) 2026 IETF Trust and the persons identified as the document authors. All rights reserved.¶
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document.¶
ML-KEM [FIPS203] is a post-quantum key-encapsulation mechanism (KEM) recently standardized by NIST, Many applications are transitioning from classical Diffie-Hellman (DH) based solutions to constructions based on ML-KEM. The use of Elligator and related Hash-to-Curve [RFC9380] algorithms are ubiquitous in DH-based protocols where DH shares are required to be encoded as, and look indistinguishable from, random bytestrings. For example, applications using Elligator include protocols used for censorship circumvention in Tor [OBFS4], password-authenticated key exchange (PAKE) protocols [CPACE] [OPAQUE], and private set intersection (PSI) [ECDH-PSI].¶
For the post-quantum transition, an analogous encoding for (ML-)KEM encapsulation keys and ciphertexts to random bytestrings is required. This document specifies such an encoding, Kemeleon, for ML-KEM encapsulation keys and ciphertexts. Kemeleon was introduced in [GSV24] for building an (post-quantum) "obfuscated" KEM whose encapsulation keys and ciphertexts are indistinguishable from random. This document specifies a version of the Kemeleon encoding that avoids any failure probability, as well as an alternate version that trades some failure probability for smaller encoding size.¶
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶
A KEM consists of three algorithms:¶
KeyGen() -> (ek, dk): A probabilistic key generation algorithm that, with no input, generates an encapsulation key ek and a decapsulation key dk.¶
Encaps(ek) -> (c, K): A probabilistic encapsulation algorithm that takes as input an encapsulation key ek, and outputs a ciphertext ct and shared secret K.¶
Decaps(dk, c) -> K: A decapsulation algorithm that takes as input a decapsulation key dk and ciphertext c, and outputs a shared secret K.¶
The following variables and functions are adopted from [FIPS203]:¶
q = 3329, n = 256¶
Compress_d : x -> round((2^d/q)*x) mod 2^d (Equation 4.7 [FIPS203])¶
Decompress_d : y -> round((q/2^d)*y) (Equation 4.8 [FIPS203])¶
ByteEncode_d: encode a vector of coefficients into a byte string using d bits per coefficient (Algorithm 5 [FIPS203])¶
ByteDecode_d: decode a byte string into a vector of coefficients using d bits per coefficient (Algorithm 6 [FIPS203])¶
k = 2 for ML-KEM-512, k = 3 for ML-KEM-768, k = 4 for ML-KEM-1024¶
remaining parameters d_u, d_v, etc. are defined by the respective ML-KEM parameter set (Table 2 [FIPS203]) -- this document writes du and dv in place of d_u, d_v in pseudocode¶
ML-KEM.KeyGen() (Section 7.1 [FIPS203]) produces an encapsulation key, ek and a decapsulation key, dk.
Encapsulation keys consist of byte-encoded vectors of coefficients in Z_q, where each coefficient is encoded in 12 bits, together with a 32-byte seed for generating the matrix A.
ML-KEM.Encaps(ek) (Section 7.2 [FIPS203]) produces ciphertexts consisting of byte-encoded compressed vectors of cofficients, where each coefficient in Z_q is compressed by a certain number of bits (depending on the ML-KEM parameter set).¶
The following terms and notation are used throughout this document:¶
At a high level, the constructions in this document instantiate the following functions:¶
EncodeEk(ek) -> eek is the (possibly randomized) encoding algorithm that on input an encapsulation key, outputs an obfuscated encapsulation key or an error.¶
DecodeEk(eek) -> ek is the deterministic decoding algorithm that on input an obfuscated encapsulation key, outputs an encapsulation key.¶
EncodeCtxt(c) -> ec is the (possibly randomized) encoding algorithm that on input a ciphertext, outputs an obfuscated ciphertext or an error.¶
DecodeCtxt(ec) -> c is the deterministic decoding algorithm that on input an obfuscated ciphertext, outputs a ciphertext.¶
The following function VectorEncode maps a vector of length n of coefficients modulo q to a large integer r such that r is byte-aligned and (statistically close to) uniformly distributed.
VectorEncode first accumulates the coefficients into a large integer r and then, applying the technique from [ELL2], adds m * q^n,
where m is chosen at random from [0,floor((2^3072-1-r)/(q^n))].
This results in an encoded output value byte-aligned to 384 bytes (the same size as the standard ML-KEM vector encoding)
whose statistical distance from uniform is at most 2^-76.
Users MAY set the statistical-distance parameter t to t = 76 + 8x for a positive integer x to obtain a smaller statistical distance.¶
VectorEncode(a):
r = 0
t = 76 # stat. distance from uniform and byte-aligned
b = 2996 # bit_length(q^n)
for i from 1 to n:
r += q^(i-1)*a[i]
m <--$ [0,...,floor( (2^(b+t)-1-r) / (q^(n)) )]
r = r + m*q^n
return r
¶
The following function VectorDecode inverts the above mapping.¶
VectorDecode(r):
r = r % q^n
for i from 1 to n:
a[i] = r % q
r = r // q
return a
¶
The following algorithm SamplePreimage samples an uncompressed pre-image of a coefficient c at random, where u is the decompressed value of c.
It must take as input values of u that are output from Decompress_d.
The mapping is based on the Compress_d, Decompress_d algorithms from (Section 4.2.1 [FIPS203]).¶
SamplePreimage(d,u,c):
if d == 10:
if Compress_d(u + 2) == c:
rand <--$ [-1,0,1,2]
else if Compress_d(u - 2) == c:
rand <--$ [-2,-1,0,1]
else:
rand <--$ [-1,0,1]
return (u + rand) % q
if d == 11:
if Compress_d(u + 1) == c:
rand <--$ [0,1]
else if Compress_d(u - 1) == c:
rand <--$ [-1,0]
else:
rand = 0
return (u + rand) % q
if d == 5:
if u == 0:
rand <--$ [-52,...,52]
else if u <= 1560:
rand <--$ [-51,...,52]
else:
rand <--$ [-52,...,51]
return (u + rand) % q
if d == 4:
if u == 0:
rand <--$ [-104,...,104]
else if u <= 1456:
rand <--$ [-103,...,104]
else:
rand <--$ [-104,...,103]
return (u + rand) % q
else:
return err
¶
The following algorithms encode ML-KEM encapsulation keys as random bytestrings.
rho is the public seed used to generate the public matrix A [FIPS203].
This is already a random 32-byte string, so it is returned alongside the encoded value of t.
t is a vector of k polynomials with n coefficients.
In an encapsulation key ek, the vector t is byte-encoded via ByteEncode_12 [FIPS203], meaning the polynomial coefficients must first be recovered by applying ByteDecode_12.
We treat each polynomial in the resulting t as a vector of n coefficient, for which we apply VectorEncode.
From this, we obtain k values that are then concatenated.¶
Kemeleon.EncodeEk(ek):
t = ByteDecode_12(ek[0:384*k])
rho = ek[384*k:384*k+32]
for i in range(k):
r_i = VectorEncode(t[i])
r = concat(r_0,...,r_(k-1))
return concat(r,rho)
¶
Kemeleon.DecodeEk(eek):
r_0,...,r_(k-1),rho = eek # rho and each r_i is fixed length
t = []
for i in range(k):
t_i = VectorDecode(r_i)
t.append(t_i)
return (ByteEncode_12(t), rho)
¶
ML-KEM ciphertexts consist of two components: c_1, a vector of k polynomials with n coefficients mod 2^du, and c_2, a polynomial with n coefficients mod 2^dv.
The coefficients of these polynomials are not uniformly distributed, as a result of the compression step in encapsulation.
The following encoding function decompresses and recovers a random preimage of this compression step in order to recover the uniform distribution of coefficients.
Then, the same vector encoding step used for encapsulation keys can be applied.
The two components c_1 and c_2 are byte-encoded in the ciphertext, via ByteEncode_du and ByteEncode_dv, respectively, meaning these must first be decoded using ByteDecode_du and ByteDecode_dv before the polynomial coefficients can be decompressed.¶
Kemeleon.EncodeCtxt(c):
c_1 = ByteDecode_du(c[0:32*du*k])
c_2 = ByteDecode_dv(c[32*du*k:32*(du*k+dv)])
u = Decompress_du(c_1)
for i from 1 to k*n:
u[i] = SamplePreimage(du,u[i],c_1[i])
v = Decompress_dv(c_2)
for i from 1 to n:
v[i] = SamplePreimage(dv,v[i],c_2[i])
for i in range(k):
r_i = VectorEncode(u[i])
r_k = VectorEncode(v)
r = concat(r_0,...,r_k)
return r
¶
Kemeleon.DecodeCtxt(r):
r_0,...,r_k = r # each r_i is fixed length
for i in range(k):
u[i] = VectorDecode(r_i)
v = VectorDecode(r_k)
c_1 = Compress_du(u)
c_2 = Compress_dv(v)
return (ByteEncode_du(c_1), ByteEncode_dv(c_2))
¶
| Algorithm / Parameter | Output size (bytes) | Success probability |
|---|---|---|
| Kemeleon - ML-KEM-512 | ek: 800, ctxt: 1152 | ek: 1.00, ctxt: 1.00 |
| Kemeleon - ML-KEM-768 | ek: 1184, ctxt: 1536 | ek: 1.00, ctxt: 1.00 |
| Kemeleon - ML-KEM-1024 | ek: 1568, ctxt: 1920 | ek: 1.00, ctxt: 1.00 |
This section contains additional considerations and comments related to using Kemeleon encodings in different applications.¶
In applications willing to incur some probability of failure in encoding, the following variant of the encoding algorithms that result in smaller output sizes for encapsulation keys and ciphertexts can be used.
The following algorithms make use of VectorEncodeR and VectorDecodeR, defined in Section 5.1.1.
The encoding algorithms for encapsulation keys should handle errors accordingly, returning an error if VectorEncodeR returns an error.¶
Kemeleon.EncodeEkR(ek): t = ByteDecode_12(ek[0:384*k]) rho = ek[384*k:384*k+32] r = VectorEncodeR(t,k) return concat(r,rho)¶
Kemeleon.DecodeEkR(eek): r,rho = eek # rho and each r_i is fixed length t = VectorDecodeR(r,k) return (ByteEncode_12(t), rho)¶
Both ciphertext components must first be decoded with ByteDecode_du and ByteDecode_dv.
For ciphertexts, the second ciphertext component need not be decompressed, and rejection sampling can be used to retain uniformity instead.¶
Kemeleon.EncodeCtxtR(c):
c_1 = ByteDecode_du(c[0:32*du*k])
u = Decompress_du(c_1)
for i from 1 to k*n:
u[i] = SamplePreimage(du,u[i],c_1[i])
r = VectorEncodeR(u,k)
if r == err:
return err
c_2 = c[32*du*k:32*(du*k+dv)]
a = ByteDecode_dv(c_2)
for i from 1 to n:
if a[i] == 0:
return err with prob. 1/ceil(q/(2^dv))
return concat(r,c_2)
¶
Kemeleon.DecodeCtxtR(ec): r,c_2 = ec # c_2 is fixed length u = VectorDecodeR(r,k) c_1 = Compress_du(u) return (ByteEncode_du(c_1),c_2)¶
This is a byte-aligned variant of the encoding as described in the original work [GSV24], and has the following properties.¶
| Algorithm / Parameter | Output size (bytes) | Success probability | Additional considerations |
|---|---|---|---|
| Kemeleon - ML-KEM-512 | ek: 781, ctxt: 877 | ek: 0.56, ctxt: 0.51 | Large int (750B) arithmetic |
| Kemeleon - ML-KEM-768 | ek: 1156, ctxt: 1252 | ek: 0.83, ctxt: 0.77 | Large int (1150B) arithmetic |
| Kemeleon - ML-KEM-1024 | ek: 1530, ctxt: 1658 | ek: 0.62, ctxt: 0.57 | Large int (1500B) arithmetic |
The following algorithms VectorEncodeR and VectorDecodeR are used for vector encoding.¶
Encoding in this case accumulates all k polynomials into one large integer r and rejects if the most significant bit msb(r) is 1.
The unused top bits of r (when represented in network byte order) are randomized to ensure a fully byte-aligned random output.
In this variant, it is no longer feasible to parallelize the encoding of the k polynomials; these must be treated as a single vector of k*n coefficients in order to achieve a reasonable rate of rejection.
Therefore, this approach also requires arithmetic over larger integers (up to bit_length(q^(4n)) = 11,982 bit integers for ML-KEM-1024).¶
VectorEncodeR(a,k):
r = 0
for i from 1 to k*n:
r += q^(i-1)*a[i]
if msb(r) == 1:
return err
b = bit_length(q^(k*n)) - 1 # bit length of r, after acceptance
# b=5990 if k=2, b=8986 if k=3, b=11981 if k=4
B = ceil(b/8) # byte-aligned size of r, in bytes
x = B*8 - b # number of unused bits
rand <--$ [0,...,2^x - 1]
r = r | (rand << b) # randomize unused bits
return r
¶
VectorDecodeR(r,k):
b = bit_length(q^(k*n)) - 1 # bit length of r
# b=5990 if k=2, b=8986 if k=3, b=11981 if k=4
r = r & (2^b - 1) # clear unused bits
for i from 1 to k*n:
a[i] = r % q
r = r // q
return a
¶
Applications merely interested in compressing encapsulation keys may use EncodeEkR and DecodeEkR without rejection and random padding in VectorEncodeR.
The resulting encoded encapsulation keys will NOT be uniformly random, but have smaller output size as in Table 2.¶
The randomness used in Kemeleon ciphertext encodings MAY be derived in a deterministic manner.
To do so, following a call to Encap which returns a shared secret K and a ciphertext c, the following steps can be taken:¶
Using a key derivation function (KDF), derive from the shared secret K a new shared secret K' and a seed for randomness rnd.¶
The seed rnd can be used to generate the randomness required when encoding the ciphertext c.¶
Use K' in place of K wherever applicable in the remainder of the protocol/system.¶
Upon any call to Decap, apply the same KDF to derive the new shared secret K', as required.¶
Deriving a new KEM shared secret for use in the remainder of a system is crucial in order to ensure key separation (i.e., the implementation MUST NOT use the original shared secret K to derive randomness and for other purposes).¶
The randomness used to encode an encapsulation key MAY be stored alongside the corresponding decapsulation key, if it is subsequently needed. See Section 6.2 for relevant discussion on keeping this randomness secret.¶
While the functionality of Kemeleon is similar to hash-to-curve [RFC9380] (mapping arbitrary byte strings to encapsulation keys/ciphertexts), the applications where hash-to-curve is used do not immediately follow in the KEM-based setting because having such an encapsulation key (without dk) or ciphertext (without dk or ek) does not appear to provide the same functionality, since it is not clear how to continue working with the element in the same way that can be done with an elliptic curve point.¶
In applications that only require Kemeleon-encoded values and where the underlying ML-KEM implementation can be modified, the ciphertext encoding algorithm (and ML-KEM encapsulation/decapsulation algorithms) MAY be adapted as follows for improved efficiency.
In particular, the compression and byte-encoding steps in the ML-KEM encapsulation algorithm can be omitted, and therefore, the byte-decoding and decompression steps in the Kemeleon algorithm can be omitted.
In the implementation of ML-KEM, the compression and byte-encoding steps (lines 22-23 of Algorithm 14 [FIPS203]) and corresponding byte-decoding and decompression steps (lines 3-4 of Algorithm 15 [FIPS203]) can be omitted from the encapsulation/decapsulation algorithms in ML-KEM.
In this case, the Kemeleon encoding algorithm for ciphertexts omits the ByteDecode, Decompress, and SamplePreimage steps and immediately applies VectorEncode:¶
Kemeleon.EncodeCtxt(c = (c_1,c_2)):
w = [c_1[0],...,c_1[k-1],c_2]
for i in range(k+1):
r_i = VectorEncode(w[i])
r = concat(r_0,...,r_k)
return r
¶
Decoding is adapted analogously.¶
Kemeleon.DecodeCtxt(ec):
r_0,...,r_k = ec # each r_i is fixed length
for i in range(k+1):
w[i] = VectorDecode(r_i)
c_1 = [w[0],...,w[k-1]]
c_2 = w[k]
return (c_1,c_2)
¶
The same applies to encapsulation keys, which are byte-encoded but not compressed: a modified KeyGen that exposes t directly lets EncodeEk skip ByteDecode_12 and DecodeEk skip ByteEncode_12.
However, ByteEncode_12 cannot be dropped entirely in KeyGen itself, as its output is used to compute H(ek) for the Fujisaki-Okamoto transform (Algorithms 16-18 [FIPS203]).¶
This section contains additional security considerations about the Kemeleon encodings described in this document.¶
In general, the obfuscation properties of the Kemeleon encodings depend on module LWE assumptions similar to those underlying the IND-CCA security of ML-KEM; see [GSV24] for the detailed security analysis of the original Kemeleon encoding. In particular, the notions of public/encapsulation key and ciphertext uniformity capture the indistinguishability of Kemeleon-encoded encapsulation keys and ciphertexts from random bitstrings, respectively. Both require the module LWE assumption to hold in order for Kemeleon to maintain its uniformity properties. Furthermore, distinguishing a pair of a Kemeleon-encoded encapsulation key and a Kemeleon-encoded ciphertext from uniformly random bitstrings also reduces to a module LWE assumption.¶
Both encapsulation key and ciphertext encodings in the Kemeleon encoding are randomized. The randomness (or seed used to generate randomness) used in Kemeleon encodings MUST be kept secret. In particular, public randomness enables distinguishing a Kemeleon-encoded value from a random bytestring: Decoding the value in question and re-encoding it with the public randomness will yield the original value if it was Kemeleon-encoded.¶
Beyond timing side-channel considerations for ML-KEM itself, care should be taken when using Kemeleon encodings. Algorithms required to perform large integer arithmetic may leak information via timing. Additionally, rejecting and re-generating encapsulation keys or ciphertexts may leak information about the use of Kemeleon encodings, as might the overhead of the encoding itself.¶
This document has no IANA actions.¶
Thanks to Michael Rosenberg, John Mattsson, Stanislaw Jarecki, and Afonso Arriaga for contributions to this document and helpful discussions.¶