Kemeleon Encodings

4.1. Common Functions

The following function maps a vector of k*n coefficients modulo q to a large integer, rejecting if the most significant bit of the integer is 1.¶

VectorEncode(a):
   r = 0
   for i from 1 to k*n:
      r += q^(i-1)*a[i]
   if msb(r) == 1:
      return err
   else:
      return r

VectorDecode(r):
   for i from 1 to k*n:
      a[i] = r % q
      r = r // q
   return a

The following algorithm samples an uncompressed pre-image of a coefficient c at random, where u is the decompressed value of c. 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:
         rand <--$ [-1,0,1]
      return u + rand
   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
   if d == 5:
      if c == 0:
         rand <--$ [-52,...,52]
      else:
         rand <--$ [-51,...,52]
      return u + rand
   if d == 4:
      if c == 0:
         rand <--$ [-104,...,104]
      else:
         rand <--$ [-104,...,103]
      return u + rand
   else:
      return err

4.2. Encoding Public Keys

The following algorithms encode ML-KEM public 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, but in the following pseudocode t is treated as a vector of k*n coefficients.¶

Kemeleon.EncodePk(pk = (t, rho)):
   r = VectorEncode(t)
   if r == err:
      return err
   else:
      return concat(r,rho)

Kemeleon.DecodePk(epk):
   r,rho = epk # rho is fixed length
   t = VectorDecode(r)
   return (t, rho)

4.3. Encoding Ciphertexts

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 public keys is applied. For the second ciphertext component, rejection sampling is performed to retain uniformity, rather than decompressing.¶

Kemeleon.EncodeCtxt(c = (c_1,c_2)):
   u = Decompress_du(c_1)
   for i from 1 to k*n:
      u[i] = SamplePreimage(du,u[i],c_1[i])
   r = VectorEncode(u)
   if r == err:
      return err
   for i from 1 to n:
      if c_2[1] == 0:
         return err with prob. 1/ceil(q/(2^dv))
   return concat(r,c_2)

Kemeleon.DecodeCtxt(ec):
   r,c_2 = ec # c_2 is fixed length
   u = VectorDecode(r)
   c_1 = Compress_du(u)
   return (c_1,c_2)

4.4. Non-Rejection Sampling Variant

Applying a technique from [ELL2] (Section 3.4), the original Kemeleon construction can be adapted to avoid rejection sampling. This results in larger output sizes, but the encoding algorithm never fails. Applying the technique from [ELL2], where r is the encoded vector before rejection occurs in VectorEncode, we then choose m at random from [0,floor((2^(b+t)-r)/(q^(k*n)))], where b = log_2(q^(k*n)) and t is a security parameter, and return r + m*q^(k*n). This variant results in encoded values whose statistical distance from uniform is at most 2^-t. This results in an increased output size of t bits, where t is the security parameter. For example, with t=128, this increases the output size by 16 bytes.¶

For public key encodings, one can immediately replace VectorEncode and VectorDecode calls with calls to the following algorithms.¶

VectorEncodeNR(a):
   r = 0
   t = sec_param # e.g. t = 128, 256, ...
   b = log_2(q^(k*n))
   for i from 1 to k*n:
      r += q^(i-1)*a[i]
   m <--$ [0,...,floor((2^(b+t)-r)/(q^(k*n)))]
   return r + m*q^(k*n)

VectorDecodeNR(a):
   a = a % q^(k*n)
   for i from 1 to k*n:
      a[i] = r % q
      r = r // q
   return a

Notably, the random value m need not be transmitted alongside the encoded values.¶

For ciphertext encodings, one must also avoid rejection sampling based on coefficients of the second component of the ciphertext. Therefore, the new ciphertext encoding must decompress and VectorEncodeNR the second component of the ciphertext. This more significantly increases the size of the encoded ciphertext.¶

Kemeleon.EncodeCtxtNR(c = (c_1,c_2)):
   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])
   w = [u,v] # treat u,v as a singular vector of (k+1)*n coefficients
   r = VectorEncodeNR(w) # this call should use k+1 rather than k when accumulating to a large integer
   return r

Kemeleon.DecodeCtxtNR(ec):
   w = VectorDecodeNR(r)
   u,v = w # u, v are fixed length
   c_1 = Compress_du(u)
   c_2 = Compress_dv(v)
   return (c_1,c_2)

4.5. Faster Arithmetic Variant

[OPEN ISSUE: Is the faster variant of interest? If so, the following can be extended with a complete description.]¶

Observing that q = 3329 = 13*2^8+1, a variant of Kemeleon with faster integer arithmetic can be specified. First, the encoding rejects any polynomial with a coefficient equal to q-1 = 3328. This ensures that all arithmetic can be computed with values modulo q-1 = 13*2^8. Then, note that rather than accumulating values to a large integer mod q^(k*n), it is only required to accumulate values to an integer mod 13^(k*n), while keeping track of the 8 lower order bits of each coefficient. The output size of the encoding does not change, but this results in an increased rejection rate.¶

In particular, Table 1 gives success probabilities for public key and ciphertext encodings:¶

4.6. Deterministic Encoding

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 KEM key K and a ciphertext c, the following steps can be taken:¶

• Using a key derivation function (KDF), derive from the key K a new key 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 key K', as required.¶

Deriving a new KEM key for use in the remainder of a system is crucial in order to ensure key separation (i.e., not using the original key K to derive randomness and for other purposes).¶

The randomness used to encode a public key MAY be stored alongside the corresponding secret key, if it is subsequently needed. See Section 5.1 for relevant discussion on keeping this randomness secret.¶

4.7. Summary of Encodings

5.1. Randomness Sampling

Both public key and ciphertext encodings in the original 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.¶

5.2. Timing Side-Channels

Beyond timing side-channel considerations for ML-KEM itself, care should be taken when using Kemeleon encodings, in particular those with a non-zero failure probability. Rejecting and re-generating public keys or ciphertexts may leak information about the use of Kemeleon encodings, as might the overhead of the encoding itself.¶

7.1. Normative References

[ELL2]

Tibouchi, M., "Elligator Squared: Uniform Points on Elliptic Curves of Prime Order as Uniform Random Strings", 2014, <https://eprint.iacr.org/2014/043>.

[FIPS203]

"Module-lattice-based key-encapsulation mechanism standard", National Institute of Standards and Technology (U.S.), DOI 10.6028/nist.fips.203, August 2024, <https://doi.org/10.6028/nist.fips.203>.

[GSV24]

Günther, F., Stebila, D., and S. Veitch, "Obfuscated Key Exchange", 2024, <https://eprint.iacr.org/2024/1086>.

[RFC2119]

Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/rfc/rfc2119>.

[RFC8174]

Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfc-editor.org/rfc/rfc8174>.

[RFC9380]

Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R. S., and C. A. Wood, "Hashing to Elliptic Curves", RFC 9380, DOI 10.17487/RFC9380, August 2023, <https://www.rfc-editor.org/rfc/rfc9380>.

7.2. Informative References

[CPACE]

Abdalla, M., Haase, B., and J. Hesse, "CPace, a balanced composable PAKE", Work in Progress, Internet-Draft, draft-irtf-cfrg-cpace-13, 14 October 2024, <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-cpace-13>.

[ECDH-PSI]

wangyuchen, Chang, Lu, Y., Hong, C., and J. Peng, "PSI based on ECDH", Work in Progress, Internet-Draft, draft-ecdh-psi-00, 21 October 2024, <https://datatracker.ietf.org/doc/html/draft-ecdh-psi-00>.

[OBFS4]

"obfs4 (The obfourscator)", n.d., <https://gitlab.torproject.org/tpo/anti-censorship/pluggable-transports/lyrebird/-/blob/HEAD/doc/obfs4-spec.txt>.

[OPAQUE]

Bourdrez, D., Krawczyk, H., Lewi, K., and C. A. Wood, "The OPAQUE Augmented PAKE Protocol", Work in Progress, Internet-Draft, draft-irtf-cfrg-opaque-18, 21 November 2024, <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-opaque-18>.