Théophile Brézot

Paola De Perthuis

David Pointcheval

Covercrypt: an Efficient Early-Abort KEM for Hidden Access Policies with Traceability from the DDH and LWE

Attribute-Based Encryption (ABE) is a very attractive primitive to limit access according to specific rights. While very powerful instantiations have been offered, under various computational assumptions, they rely on either classical or post-quantum problems, and are quite intricate to implement, generally resulting in poor efficiency; the construction we offer results in a powerful efficiency gap with respect to existing solutions. With the threat of quantum computers, post-quantum solutions are important, but not yet tested enough to rely on such problems only. We thus first study an hybrid approach to rely on the best of the two worlds: the scheme is secure if at least one of the two underlying assumptions is still valid (i.e. the DDH and LWE). Then, we address the ABE problem, with a practical solution delivering encrypted contents such that only authorized users can decrypt, without revealing the target sets, while also granting tracing capabilities. Our scheme is inspired by the Subset Cover framework where the users' rights are organized as subsets and a content is encrypted with respect to a subset covering of the target set. Quite conveniently, we offer black-box modularity: one can easily use any public-key encryption of their choice, such as Kyber, with their favorite library, to combine it with a simple ElGamal variant of key encapsulation mechanisms, providing strong security guarantees.

Introduction

Key Encapsulation Mechanisms (KEM) enable the transmission of symmetric keys at the beginning of an interaction while retaining trust that only the intended recipient will be able to get access to this encapsulated key. Once this trusted transmission has been established, users can privately communicate using this encapsulated secret key with the advantages of symmetric encryption, granting compact ciphertexts of similar size as corresponding cleartexts. Namely, they can be used to build Public-Key Encryption (PKE) schemes in the KEM-DEM (for Data Encapsulation Mechanism) paradigm [Sho01].

In organizations with complex structures, one will want to have more functionalities, namely being able to share a key among all users verifying a policy on a set of attributes, all at once. To this aim, KEMs constructed out of Attribute-Based Encryption (ABE) have been designed, in which keys can be encapsulated by being encrypted with these schemes for which all users verifying the specified attributes policy will be able to decrypt and thus decapsulate the key. These ABE primitives (stemming from [GPSW06]) are very powerful as they can cover any possible logical combination of the attributes, however this comes at an efficiency cost, and for practical use-cases, one will only need to encrypt for some of these existing combinations, for a limited number of attributes; this work is in this setting's scope, in which one can actually replace ABE constructions with encryption with respect to a union of attribute subsets. In these use-cases, it can also be relevant to get anonymity, meaning that a user should never know for which policy a ciphertext was produced, except if it is the policy they are using to successfully decrypt. In the case of ABE, this is called attribute hiding. This can also be used to get anonymous authentication (for instance in mobile network contexts) to service providers sending encapsulations without users needing to send out requests that would identify them.

Additionally, with current preoccupations with respect to the threat of quantum computers on classical cryptography, granting resistance to these for data that needs to be kept private on the long term is becoming a necessity. However, post-quantum cryptographic schemes are newer and only beginning to be used, one should try to keep current schemes' security properties. In fact, several security agencies are handing out guidelines for pre-and post-quantum security hybridization, meaning that cryptographic schemes should retain all their security properties even if one of the two pre-or post-quantum schemes is broken.

Another area of interest in this context in which users share some common keys, is the ability to still identify them uniquely, in case they choose to send some of there decapsulation capabilities to another party. Thus, if someone leaks some secret information they were supposed to keep to themselves, we would like to trace these so-called traitors, with traceability.

Related Work. This work combines many desirable properties for the use of KEMs in practical contexts, that other previous works had not, and since it covers only the practical contexts in which one would wish for ABE-based constructions, it compares favorably in efficiency with respect to such postquantum schemes built from ABE, in addition with providing traceability and post-and pre-quantum hybridization.

Anonymous Broadcast Encryption. Our simplified access structure with strong privacy has a similar flavor as previous works [LPQ12, FP12, LG18] on broadcast encryption with anonymity, with optimizations on the decryption time. However, they do not handle black-box post-quantum security nor traceability.

Post-Quantum Key-Policy ABE. Then, providing post-quantum resistance, the closest related works are Key-Policy ABEs (KP-ABE) based on LWE. Some theoretical works such as [Wee21] provide results with good asymptotic bounds, but are unsuited for use with practical parameters, and others, like [DDP + 17], provide implementable results, but even with their comparable lowest policy circuit depth, their encryption time is about a hundred times bigger than ours, their decryption time about ten times bigger, and their RLWE parameters lead to bigger ciphertext sizes than ours. Also, they do not provide anonymity nor traceability.

Hybridization for Pre and Post-Quantum Security. Our work, in the line of security agency and standardization organizations recommendations, enables the hybridization of both pre-and post-quantum schemes, so that its security holds if it does either one of the underlying schemes. The use of the postquantum scheme is totally black-box, enabling combinations with other semantically secure public-key encryption schemes. This is in the line of previous work to combine KEMs to get the best security out of the individual ones combined, such as [GHP18], and in [BBF + ], where the specific problem of combining pre-and post-quantum schemes against various types of classical or quantum adversaries was studied.

Our Contributions. Our final instantiation called Covercrypt provides an efficient KEM for hidden access policies with traceability, ensuring both pre-and post-quantum securities, along with a Rust implementation of the scheme 3 . Public-Key Encryption (PKE) allows the transmission of hidden information that only the intended recipient will be able to uncover. To make the scheme independent of the format of the cleartext message, the usual paradigm for encryption is the KEM-DEM [Sho01], where one first encapsulates a session key that only the recipient can recover, and then encrypts the payload under that key. The former step uses a Key Encapsulation Mechanism (KEM) and the latter a Data Encapsulation Mechanism (DEM), that is usually instantiated with an Authenticated Encryption, such as AES256-GCM 4 , providing both privacy and authenticity of plaintexts. We hereafter recall some formal definitions.

An Efficient KEM with Hidden Access Policies. Our scheme provides efficiency with respect to the stateof-the-art in KP-ABE schemes by restricting its scope to depth-one policy circuits. The attributes for which a key is encapsulated are kept hidden, providing anonymity. Also, we gain time on the decryption with an early-abort paradigm, in which one can quickly test whether a ciphertext was encrypted for one of their attributes, using a tag, and retaining the anonymity properties of the scheme. Our ciphertexts are of size 96 + #B × 1088 Bytes, where B is the list of attribute-subsets the key is encapsulated for. On the other hand, user's keys are of size (#A + 1) × 64 Bytes, where A is the list of attributes for the user. For #B ranging from 1 to 5, encapsulation takes from 350 to 950 microseconds, and decapsulation, from 230 to 480 microseconds, with an affine dependency in the user's attributes (see Section 7).

Traceability. As an optional feature, the pre-quantum ElGamal part of our scheme provides traceability under the Decisional Diffie-Hellman (DDH) assumption. It makes sense to consider traceability with pre-quantum security as this is a short-term security requirement, if users are currently misbehaving, whereas the post-quantum security preserves the privacy property, which is important on the long-term, as ciphertexts can be stored until their security is broken in the future. Our implementation covers the case were traitors do not collude; we also show how the scheme can be instantiated for arbitrarily tlarge collusions, but the tracing time then grows exponentially in t. A KEM can be used to broadcast symmetric encryption keys, but also for authentication, and in such an interactive context, implementing tracing requests is easily done in practice.

Notations. Henceforth, many security notions will be characterized by the computational indistinguishability between two distributions D 0 and D 1 . It will be measured by the advantage an adversary A can have in distinguishing them:

Adv(A) = Pr D1 [A(x) = 1] -Pr D0 [A(x) = 1] = 2 × Pr D b [A(x) = b] -1.
Then, we will denote Adv(τ ) the maximal advantage over all the adversaries with running-time bounded by τ . A first pair of distributions is used in the famous ElGamal encryption scheme, with Diffie-Hellman tuples in G = ⟨g⟩, a group of prime order p, spanned by a generator g, and denoted multiplicatively: Definition 1 (Decisional Diffie-Hellman Problem). The DDH assumption in a group G (DDH G ) of prime order p, with a generator g, states that the distributions D 0 and D 1 are computationally hard to distinguish, where

D 0 = {(g a , g b , g ab ), a, b $ ← Z p } D 1 = {(g a , g b , g c ), a, b, c $ ← Z p }
and we will denote Adv ddh G (A) the advantage of an adversary A. When studying the Kyber post-quantum encryption scheme, we will also need another algebraic structure, with indistinguishable distributions. We will denote R = Z[X]/(X n + 1) (resp. R q = Z q [X]/(X n + 1)) the ring of polynomials of degree at most n -1 with integer coefficients (resp. with coefficients in Z q , for a small prime q). We take n as power of 2, where X n + 1 is the n 2 -th cyclotomic polynomial. We denote B η the centered binomial distribution of parameter η. When a polynomial is sampled according to B η , it means each of its coefficient is sampled from that distribution. We will also use vectors e ∈ R k q and matrices A ∈ R m×k q in R q : Definition 2 (Decisional Module Learning-with-Error Problem). The DMLWE assumption in R q (DMLWE Rq,m,k,η ) states that the distributions D 0 and D 1 are computationally hard to distinguish, where

D 0 = {(A, b), A $ ← R m×k q , (s, e) $ ← B k η × B m η , b ← As + e} D 1 = {(A, b), A $ ← R m×k q , b $ ← B m η }
We will denote Adv dmlwe Rq,m,k,η (A) the advantage of an adversary A.

Pseudorandom Generators (PRG). A long line of cryptographic works consider PRGs [HILL99, App12], as one of the theoretical foundations of modern cryptography. A PRG PRG : {0; 1} µ → {0; 1} ν is deterministic function which should have the property that uniformly distributed inputs on {0; 1} µ should have outputs through PRG indistinguishable from uniformly random samples of {0; 1} ν with respect to a PPT adversary. The bigger ν is with respect to µ, the more challenging constructing such a PRG becomes. We define a PRG's security as:

Definition 3 (IND-security of a PRG). Let PRG : {0; 1} µ → {0; 1} ν be a deterministic function.

Then PRG is an IND-secure PRG if the distributions D 0 and D 1 are computationally hard to distinguish, where

D 0 = {y, x $ ← {0; 1} µ , y ← PRG(x)} D 1 = {y, y $ ← {0; 1} ν }
We will denote Adv ind PRGµ,ν (A) the advantage of an adversary A.

Key Encapsulation Mechanism.

A Key Encapsulation Mechanism KEM is defined by three algorithms:

-KEM.KeyGen(1 κ ): the key generation algorithm outputs a pair of public and secret keys (pk, sk); -KEM.Enc(pk): the encapsulation algorithm generates a session key K and an encapsulation C of it, and outputs the pair (C, K); -KEM.Dec(sk, C): the decapsulation algorithm outputs the key K encapsulated in C.

Correctness. A correct KEM satisfies Adv cor KEM (κ) = 1 -Pr D [Ev] = negl(κ), for D = {(pk, sk) ← KEM.KeyGen(1 κ ), (C, K) ← KEM.Enc(pk) : (sk, C, K)} Ev = [KEM.Dec(sk, C) = K]
Session-Key Privacy. On the other hand, such a KEM is said to provide session-key privacy (denoted SK-IND) in the key space K, if the encapsulated key is indistinguishable from a random key in K. More formally, a KEM is SK-IND-secure if for any adversary A, Adv sk-ind KEM (A) = negl(κ), in distinguishing D 0 and D 1 , where

D b = (pk, sk) ← KEM.KeyGen(1 κ ), (C, K 0 ) ← KEM.Enc(pk), K 1 $ ← K : (pk, C, K b )
Public-Key Privacy. One can additionally expect anonymity of the receiver, also known as public-key privacy (denoted PK-IND), if the encapsulation does not leak any information about the public key, first defined in [BBDP01]. More formally, a KEM is PK-IND-secure if for any adversary A, Adv pk-ind KEM (A) = negl(κ), in distinguishing D 0 and D 1 , where

D b =    For i = 0, 1 : (pk i , sk i ) ← KEM.KeyGen(1 κ ), (C i , K i ) ← KEM.Enc(pk i ) : (pk 0 , pk 1 , C b )    ElGamal-based KEM.
In a group G of prime order p, with a generator g:

-EG.KeyGen(1 κ ): sample random sk = x $ ← Z p and set pk = h ← g x ; -EG.Enc(pk): sample a random r $ ← Z p and set C ← g r together with K ← h r ; -EG.Dec(sk, C): output K ← C x .
Under the DDH assumption in G, this KEM is both SK-IND and PK-IND with K = G. The formal security proofs for an extended version of this scheme will be given later, we thus postpone the analysis of this scheme.

Key Encapsulation Mechanism with Access Control. A KEM with Access Control allows multiple users to access the encapsulated key K from C, according to a rule R applied on Y in the user's key usk and X in the encapsulation C. It is defined by four algorithms:

-KEMAC.Setup(1 κ ) outputs the global public parameters PK and the master secret key MSK; -KEMAC.KeyGen(MSK, Y ) outputs the user's secret key usk according to Y ; -KEMAC.Enc(PK, X) generates a session key K and an encapsulation C of it according to X; -KEMAC.Dec(usk, C) outputs the key K encapsulated in C.

Correctness. A KEMAC is correct if Adv cor KEMAC (κ) = 1 -Pr D [Ev] = negl(κ), for D =        ∀(X, Y ) such that R(X, Y ) = 1, (PK, MSK) ← KEMAC.KeyGen(1 κ ), usk ← KEMAC.KeyGen(MSK, Y ), (C, K) ← KEMAC.Enc(PK, X) : (usk, C, K)        Ev = [KEMAC.Dec(usk, C) = K].
Session-Key Privacy. As for the basic KEM, one may expect some privacy properties. Session-key privacy is modeled by indistinguishability of ciphertexts, even if the adversary has received some decryption keys, as soon as associated Y i are incompatible with X (R(X, Y i ) = 0). Such a KEMAC is said to be SK-INDsecure in the key space K if for any adversary A, that can ask any key usk i , using oracle OKeyGen(Y i ) that stores Y i in the set Y and outputs KEMAC.KeyGen(MSK, Y i ), Adv sk-ind KEMAC (A) = negl(κ), for b $ ← {0; 1} and

D b =    (PK, MSK) ← KEMAC.Setup(1 κ ), (state, X) ← A OKeyGen(•) (PK), (C, K 0 ) ← KEMAC.Enc(PK, X), K 1 $ ← K : (state, C, K b )    BadXY = [∃Y i ∈ Y, R(X, Y i ) = 1] Adv pk-ind KEMAC (A) = 2 × Pr D b [A OKeyGen(•) (state, C, K b ) = b | ¬BadXY] -1.
We note the bad event BadXY (decided at the end of the game) should be avoided by the adversary, as it reduces its advantage: this indeed leads to a trivial guess, and this is considered as a non-legitimate attack.

Access-Control Privacy. In addition, one could want to hide the parameter X used in the encapsulation C even if the adversary A can ask any key usk i for

Y i such that R(X 0 , Y i ) = R(X 1 , Y i ) =
D b =    (PK, MSK) ← KEMAC.Setup(1 κ ), (state, X 0 , X 1 ) ← A OKeyGen(•) (PK), (C i , K i ) ← KEMAC.Enc(PK, X i ), for i = 0, 1 : (state, C b )    BadXY = [∃Y i ∈ Y, R(X 0 , Y i ) = 1 ∨ R(X 1 , Y i ) = 1] Adv ac-ind KEMAC (A) = 2 × Pr D b [A OKeyGen(•) (state, C b ) = b | ¬BadXY] -1,
where we again condition the advantage to legitimate attacks only.

Traceability. In any multi-user setting, to avoid abuse of the decryption keys, one may want to be able to trace a user (or their personal key) from the decryption mechanism, and more generally from any useful decoder, either given access to the key material in the device (white-box tracing) or just interacting with the device (black-box tracing). Without any keys, one expects session-key privacy, but as soon as one knows a key, one can distinguish the session-key. Then, we will call a useful pirate decoder P a good distinguisher against session-key privacy, that behaves differently with the real and a random key. But of course, this pirate decoder can be built from multiple user' keys, called traitors, and one would like to be able to trace at least one of them.

A weaker variant of traceability is just a confirmation of candidate traitors, and we will target this goal: if a pirate decoder P has been generated from a list T = {Y i } of traitors' keys, a confirmer algorithm C can output, from a valid guess G for T , at least one traitor in T . More formally, let us consider any adversary A that can ask for key generation through oracle OKeyGen(Y i ), that gets usk i ← KEMAC.KeyGen(MSK, Y i ), outputs nothing but appends the new user Y i in U, and then corrupt some users through the corruption oracle OCorrupt(Y i ), that outputs usk i and appends Y i in T , to build a useful pirate decoder P, then there is a correct confirmer algorithm C that outputs a traitor T , with negligible error : for b $ ← {0; 1} and

D =        (PK, MSK) ← KEMAC.Setup(1 κ ), P ← A OKeyGen(•),OCorrupt(•) (PK), X such that ∀Y i ∈ T , R(X, Y i ) = 1, (C, K 0 ) ← KEMAC.Enc(PK, X), K 1 $ ← K : (MSK, P, U, T , C, K 0 , K 1 )        ,
we denote:

-P as useful, if 2 × Pr D,b [P(C, K b ) = b] -1 is non-negligible; -C as correct, if Pr D [T ∈ T T ← C P(•,•) (MSK, T )] is overwhelming; -C as error-free if for any G ⊂ U, Pr D [T ̸ ∈ T T ← C P(•,•) (MSK, G) ∧ T ̸ = ⊥] is negligible.
More concretely, we say that the decoder P is useful if it can distinguish the real key from a random key with significant advantage. Then, from such a useful decoder, the confirmer C is correct if it outputs a traitor with overwhelming probability, when it starts from the correct set T of candidates. Eventually, it should be error-free: T does not output an honest user, but with negligible probability. The t-confirmation limits the number of corrupted users in T to t.

Hybrid KEM. While one can never exclude an attack against a cryptographic scheme, combining several independent approaches reduces the risks. This is the way one suggests to apply post-quantum schemes, in combination with classical schemes, in order to be sure to get the best security.

Hybrid KEM Construction. Let us first study the combination of two KEMs (KEM 1 and KEM 2 ), so that as soon as one of them achieves SK-IND security, the hybrid KEM achieves SK-IND security too.

We need both KEMs to generate keys in K, with a group structure and internal law denoted ⊕. One can also find it in appendix H, figure 2: -

KEM.KeyGen(1 κ ) calls (pk i , sk i ) ← KEM i .KeyGen(1 κ ), for i ∈ {1, 2} and outputs pk ← (pk 1 , pk 2 ) and sk ← (sk 1 , sk 2 ); -KEM.Enc(pk) parses pk as (pk 1 , pk 2 ), calls (C i , K i ) ← KEM i .Enc(pk i ) for i ∈ {1, 2}, and outputs (C = (C 1 , C 2 ), K = K 1 ⊕ K 2 ); -KEM.Dec(sk, C) parses sk as (sk 1 , sk 2 ) and C as (C 1 , C 2 ), then calls both K i ← KEM i .Dec(sk i , C i ),
and outputs

K = K 1 ⊕ K 2 .
Security Properties. As expected, we can prove that as soon as one of them achieves SK-IND security, the hybrid KEM achieves SK-IND security too. This also follows from [GHP18]'s first lemma. However, for PK-IND security of KEM, we need both the underlying schemes to be PK-IND secure. This second property is not as crucial as the first one: none of the other security properties we show for the schemes depend on it, and here the only property at stake is the anonymity of the receiver of the encapsulated keys, not the keys themselves. The proofs of theorems 4 and 5 can be found in appendices D.4 and D.5, respectively.

Theorem 4 (Session-Key Privacy). If at least one of the underlying KEM 1 and KEM 2 is SK-INDsecure, the hybrid KEM is SK-IND-secure:

Adv sk-ind KEM (τ ) ≤ min{Adv sk-ind KEM1 (τ ), Adv sk-ind KEM2 (τ )}.
Theorem 5 (Public-Key Privacy). If both underlying KEM 1 and KEM 2 are PK-IND-secure, the hybrid KEM is PK-IND-secure:

Adv pk-ind KEM (τ ) ≤ Adv pk-ind KEM1 (τ ) + Adv pk-ind KEM2 (τ ).
We will also use Public-Key Encryption (PKE), which is recalled in the Appendix A.

Authenticated Key Encapsulation Mechanism

With public-key privacy, one cannot know who is the actual receiver, and needs to check the decapsulated session key with an authenticated encryption scheme to know whether they were a recipient or not. The latter check can be time-consuming when applied on a large data content (or when there are multiple decryption keys to try). We can hope to have quick key confirmation, if the additional Authentication (AUTH) property is satisfied.

Authentication. A KEM provides authentication (denoted AUTH) if it satisfies Adv auth KEM (κ) = 1-Pr D [Ev] = negl(κ), for D = ∀i ∈ {0; 1}, (pk i , sk i ) ← KEM.KeyGen(1 κ ), (C, K) ← KEM.Enc(pk 0 ) : (sk 1 , C) Ev = [KEM.Dec(sk 1 , C) =⊥].
We stress this is a weak authentication definition, but strong enough for our further early-abort technique.

We indeed just want to exclude a ciphertext to be valid under two keys, at random. There is no malicious behavior.

We present a generic conversion to add the AUTH property to any KEM, while retaining previous properties (SK-IND and PK-IND). To this aim, we use a PRG. Key Encapsulation Mechanisms with Authentication. We present below (and in the Appendix H in Figure 1) a KEM ′ with authentication from a KEM that outputs κ-bit keys, with two security parameters: k, the length of the new encapsulated key, and ℓ, the length of the verification tag. We also use a PRG PRG : {0; 1} κ → {0; 1} k+ℓ . We require that in KEM.Enc's outputs (C, K), with K looking uniform in {0; 1} κ .

-KEM ′ .KeyGen(1 κ ) runs (pk, sk) ← KEM.KeyGen(1 κ ); -KEM ′ .Enc(pk) runs (c, s) ← KEM.Enc(pk) and gets U ∥V ← PRG(s). One then outputs C ← (c, V ) together with the encapsulated key K ← U ; -KEM ′ .Dec(sk, C = (c, V )) runs s ← KEM.Dec(sk, c), gets U ′ ∥V ′ ← PRG(s), and checks whether V = V ′ . In the positive case, one outputs K ′ ← U ′ , otherwise one outputs ⊥.

Correctness. If the KEM KEM is correct, then the derived KEM ′ with authentication is also correct, has the decapsulation of c outputs the same s as during encapsulation, and then PRG(s) gives the same key and tag.

Security Properties. We will now show the previous security notions still hold, and we really provide authentication. We can claim that the above KEM ′ retains the initial security properties of the KEM scheme, but as the proofs essentially rely of the PRG properties, we defer the proofs to the Appendix D.

; 1} κ → {0; 1} k+ℓ is an IND-secure PRG, then its derived KEM ′ using PRG is PK-IND-secure: Adv pk-ind KEM ′ (τ ) ≤ Adv pk-ind KEM (τ ) + 4 • Adv sk-ind KEM (τ ) + 4 • Adv ind PRG κ,k+ℓ (τ )
, for any running time τ . We develop the authentication property, with the proof in the Appendix B: Theorem 8 (Authentication). If the KEM KEM is SK-IND, outputs (C, K)'s of KEM.Enc have uniformly distributed K's in {0, 1} κ , and PRG : {0; 1} κ → {0; 1} k+ℓ is an IND-secure PRG, then the corresponding authenticated KEM KEM ′ using PRG provides authentication: Adv auth KEM ′ (κ) ≤ 2 -ℓ +Adv sk-ind KEM (τ )+ Adv ind PRG κ,k+ℓ (τ ′ ), for some small running times τ , τ ′ .

4 Subset-Cover KEMAC

The above notion of access control is quite general and includes both key-policy ABE and ciphertextpolicy ABE, where one can have policies P and attributes such that given a subset of attributes, this defines a list of Boolean B (according to the presence or not of the attribute), and P(B) is either true or false.

For efficiency considerations, we will focus on the subset-cover approach: during the Setup, one defines multiple sets S i ; when generating a user key usk j , a list A j of subsets if specified, which implicitly means user U j ∈ S i for all i ∈ A j ; at encapsulation time, a target set T is given by B, such that T = ∪ i∈B S i .

Intuitively, S i 's are subsets of the universe of users, and to specify the receivers, one encapsulates the key K for a covering of the target set T . A KEMAC, for a list Σ of sets S i , can then be defined from any KEM in K that is a group with internal law denoted ⊕. The most basic version of such a KEMAC is provided in appendix E. In this section, we directly describe a subset cover KEMAC with anonymity and early aborts, as these will be the properties used in our final construction.

Anonymous Subset-Cover KEMAC with Early Aborts. To avoid sending B together with the ciphertext, but still being able to quickly find the correct matching indices in the ciphertext and the user's key, one can use a KEM ′ with authentication:

-KEMAC.Setup(Σ), for each S i ∈ Σ, runs (pk i , sk i ) ← KEM ′ .KeyGen(1 κ ): PK ← (pk i ) i and MSK ← (sk i ) i ; -KEMAC.KeyGen(MSK, A j ) defines the user's secret key usk j ← (sk i ) i∈Aj ; -KEMAC.Enc(PK, B) generates a random session key K $ ← {0; 1} k , and, for all i ∈ B, runs (C i , K i ) ← KEM ′ .Enc(pk i ) and outputs C ← (C i , E i = K ⊕ K i ) i∈B together with the encapsulated key K; -KEMAC.Dec(usk, C), for all sk i in usk and all (C j , E j ) in C, runs K ′ i,j ← KEM ′ .Dec(sk i , C j ). It stops for the first valid K ′ i,j , outputs K ← K ′ i,j ⊕ E j . For this above scheme, we can claim both the SK-IND security and the AC-IND security, for selective key queries. But first, let us check the correctness, thats fails if a wrong key, among the S A S B possibilities, makes accepts: Theorem 9 (Correctness). If the underlying KEM ′ is AUTH-secure, the above subset-cover KEMAC is correct:

Adv cor KEMAC (κ) ≤ S A S B × Adv auth KEM ′ (κ)
, where S A and S B are the sizes of the user' sets of attributes and the number of subsets in the ciphertext, respectively. About SK-IND and AC-IND security, the proofs follow the classical hybrid technique, they are thus deferred to the Appendix D.3.

Theorem 10 (Session-Key Privacy). If the underlying KEM ′ is SK-IND-secure, the above subsetcover KEMAC is also SK-IND-secure, for selective key-queries:

Adv sk-ind KEMAC (τ ) ≤ 2q k × Adv sk-ind KEM ′ (τ )
, where q k is the number of key-queries. Theorem 11 (Access-Control Privacy). If the underlying KEM ′ is AC-IND-secure, the above subsetcover KEMAC is AC-IND-secure, for selective key-queries and constant-size sets B:

Adv ac-ind KEMAC (τ ) ≤ 2S B × Adv pk-ind KEM (τ )
, where S B is the constant-size of the sets B. We stress that B must have a constant size to achieve access-control privacy.

Traceable KEM

In a subset-cover-based KEMAC, a same decapsulation key sk i is given to multiple users, for a public key pk i . In case of abuse, one cannot trace the defrauder. We offer an ElGamal-based KEM with traceability, in the same vein as [BF99].

Traceable ElGamal-based TKEM. Let G be a group of prime order q, with a generator g, in which the Computational Diffie-Hellman problem is hard. We describe below a TKEM with n multiple decapsulation keys for a specific public key, allowing to deal with collusions of at most t users:

-TKEM.KeyGen(1 κ , n, t, g, G, q): returns a public key pk, n secret keys usk j :

• it samples random s, s k $ ← Z * q , for k = 1 . . . , t + 1 and sets h ← g s as well as h k ← g s k for each k;

• for users U j , for j = 1 . . . , n, one samples random (v j,k ) k $ ← Z t+1 q , such that k v j,k s k = s, for j = 1 . . . , n. Then, pk ← ((h k ) k , h), while each usk j ← (v j,k ) k .

-TKEM.Enc(pk = ((h k ) k , h)): it samples a random r $ ← Z q , and sets

C = (C k ← h r k ) k , as well as K ← h r . -TKEM.Dec(usk j = (v j,k ) k , C = (C k ) k ): it outputs K ← k C v j,k k One notes: k C v j,k k = k h rv j,k k = k (g r ) s k v j,k = g r k s k v j,k = g sr = h r = K.
Security Properties. First, we will show that the above TKEM construction achieves both SK-IND and PK-IND security. But it also allows to confirm traitors, from a stateless pirate decoder P (in particular, this means that P never blocks itself after several invalid ciphertexts). The proofs of Theorems 12 and 13 can be found in appendices D.6 and D.7.

Theorem 12 (Session-Key Privacy). The above TKEM achieves SK-IND security under the DDH assumption in G: Adv sk-ind TKEM (τ ) ≤ Adv ddh G (τ ). Theorem 13 (Public-Key Privacy). The above TKEM achieves PK-IND security under the DDH assumption in G: Adv pk-ind TKEM (τ ) ≤ Adv ddh G (τ ). Theorem 14 (t-Confirmation). A collusion of at most t keys can be confirmed from a useful stateless pirate decoder P: starting from a correct guess for T , the traitors' keys used for building the pirate decoder P, by accessing the decoder, one can confirm a traitor in T , with negligible error.

Proof. To prove this theorem, we first give a description of the confirmer algorithm C, then we provide the indistinguishability analysis, and eventually prove C will give a correct answer. This proof can be found in the Appendix C.

Corrolary 1 In the particular case of t = 1, one can efficiently trace one traitor, from a useful stateless pirate decoder: by trying G = {J} sequentially for each J = 1, . . . , n, and evaluating p G , one should get either a significant advantage (for the traitor) or 0 (for honest keys).

We have already presented a traceable KEM that is secure against classical adversaries. If we combine it with another scheme expected secure against quantum adversaries, we can thereafter combine them into an hybrid-KEM, that inherits security properties from both schemes, with still traceability against classical adversaries. But we will actually exploit the properties of a Public-Key Encryption (PKE) scheme in order to improve efficiency of the combination. Given a PKE, that is both indistinguishable and anonymous, we can trivially get a KEM that is both SK-IND and PK-IND secure:

-KEM.KeyGen(1 κ ) gets (pk, sk) ← PKE.KeyGen(1 κ ), and outputs (pk, sk); -KEM.Enc(pk) gets K We identify R q with Z n q that contains the plaintext space K = {0; 1} n , and use two noise parameters η 1 ≥ η 2 , for the Gaussian distributions B η1 and B η2 : -Kyber.Dec(sk, C): compute w ← v -s T u and output K = ⌈ 2 q • w⌋. In the Appendix G, we recall the correctness, and the security proofs for indistinguishability and anonymity of this scheme, assuming η 1 ≥ η 2 (while in practice, we often have η 1 = η 2 ). Theorem 15 follows from [ABD + 21], and Theorem 16 is also in the scope of [MX22]:

-Kyber.KeyGen(1 κ ): sample random A $ ← R k×k
Theorem 15 (Indistinguishability of Kyber.). Kyber is IND-secure under the decisional Module-LWE assumption:

Adv ind Kyber (τ ) ≤ Adv dmlwe Rq,k,k,η1 (τ ) + Adv dmlwe Rq,k+1,k,η2 (τ ) ≤ 2 × Adv dmlwe Rq,k+1,k,η2 (τ ).

Theorem 16 (Anonymity of Kyber.). Kyber is PK-IND-secure under the decisional Module-LWE assumption:

Adv pk-ind Kyber (τ ) ≤ 2 × Adv dmlwe Rq,k,k,η1 (τ ) + Adv dmlwe Rq,k+1,k,η2 (τ ) ≤ 3 × Adv dmlwe Rq,k+1,k,η2 (τ ).

Hybrid KEM, from KEM and PKE. Using the ElGamal KEM that is both SK-IND and PK-INDsecure under the DDH assumption, together with the Kyber PKE that is both SK-IND and PK-IND-secure under the DMLWE assumption, the hybrid KEM is:

-SK-IND-secure, as soon as either the DDH or the DMLWE assumptions hold; -PK-IND-secure, under both the DDH and the DMLWE assumption.

according to Section 2. But with a PKE scheme, we can optimize a bit with:

-Hyb.KeyGen(1 κ ): generate both pairs of keys (pk 1 , sk 1 ) ← KEM.KeyGen(1 κ ) and (pk 2 , sk 2 ) ← PKE.KeyGen(1 κ ), then output pk ← (pk 1 , pk 2 ) and sk ← (sk 1 , sk 2 ); -Hyb.Enc(pk): parse pk as (pk 1 , pk 2 ), choose a random

K $ ← K, call (C 1 , K 1 ) ← KEM.Enc(pk 1 ) and C 2 ← PKE.Enc(pk 2 , K ⊕ K 1 ). Output (C = (C 1 , C 2 ), K); -Hyb.Dec(sk, C): parse sk as (sk 1 , sk 2 ) and C as (C 1 , C 2 ), then call both K 1 ← KEM.Dec(sk 1 , C 1 ), K 2 ← PKE.Dec(sk 2 , C 2 ), and output K = K 1 ⊕ K 2 .
Hybrid Traceable KEMAC. We can apply the above generic combination to build an anonymous subset-cover KEMAC with early abort, with the traceable ElGamal KEM and Kyber PKE to get a Key Encapsulation Mechanism with Access Control and Black-Box traceability (without collusions, so with t = 1 using notations from Section 5), where message-privacy hold as soon as at least the DDH or the DMLWE assumption holds, while the target-set privacy holds under both the DDH and DMLWE, and traceability works under the DDH assumption.

To have authentication properties, the ElGamal TKEM is slightly modified to fit theorems 6, 7 and 8's requirements, in which the element K output by the encapsulation algorithm should be uniform in {0; 1} κ . This modification can be done either in the Random Oracle Model (ROM) with a hash function modelled as a random oracle, and outputting a hash of the original key into {0; 1} κ , or, without the ROM, using a twist augmented technique from [CFGP06]. The KEMs derived with these two techniques are presented in appendix F, along with their security proofs. We describe here the one in the ROM. Proofs for SK-IND and PK-IND-securities follow immediately from the proofs that TKEM is SK-IND and PK-IND-secure.

Detailled Description. The straightforward construction of the hybrid traceable KEMAC with early abort is the simple instantiation of the KEMAC scheme from Section 4 from a KEM with authentication (from Section 3), itself based on our hybrid KEM from the previous subsection. A naïve instantiation would draw independent keys in the hybrid schemes and send their ⊕'s with the encapsulated key. But as K is chosen beforehand, the same K can be chosen for all the subsets. This optimized version is described with the following algorithms, where H is a hash function modeled as a random oracle with output length κ5 , PRG : {0; 1} κ → {0; 1} k+ℓ a PRG, where k is the length of the encapsulated key, ℓ the length of the verification tag, and Σ the set of subsets (S i ) i (or attributes). We instantiate it with the Kyber PKE, but it would work with any PKE that is both indistinguishable and anonymous. We call this KEMAC Covercrypt:

-Covercrypt.Setup(Σ, 1 κ ):

1. For a group G of prime order p, generated by g, one samples s, s 1 , s 2 $ ← Z p , then sets h = g s , and g 1 = g s1 , g 2 = g s2 (for tracing purposes). 2. Then, for tracing, we set tsk = (s, s 1 , s 2 , ID), where ID is the set of the users' identifiers uid, initialized as an empty set here, and tpk = (g, h, g 1 , g 2 ). 3. For each S i ∈ Σ, one samples a random scalar

x i $ ← Z p , a (pk i , sk i ) ← Kyber.KeyGen(1 κ ), then sets pk ′ i ← (h i = h xi , pk i )
, and sk ′ i ← (x i , sk i ). 4. Finally, the global public key is set to PK ← (tpk, {pk ′ i } i ), and the master secret key to MSK ← (tsk, {sk ′ i } i , UP), where UP is the set of user's secret keys, showing their permissions, but initialized as an empty set. One returns (MSK, PK).

-Covercrypt.KeyGen(MSK, U, A):

1. For a user U , with attributes A (a list of subsets, or equivalently their indices), one samples (α, β) ∈ Z 2 p such that αs 1 +βs 2 = s, and sets the corresponding user secret identifier uid ← (α, β). 2. The tracing secret key tsk is updated as tsk ′ by adding (U, uid) in ID. 3. Finally, the user's secret key is defined as usk ← (uid, {sk ′ j } j∈A ), and one outputs it along with MSK ′ , the master secret key MSK updated with usk added in UP, and tsk ′ instead of tsk.

-Covercrypt.Enc(PK, B):

1. For a target set that covers all the users with an attribute in B (or equivalently the indices of attributes, such that A ∩ B ̸ = ∅), one generates a random seed for the key to be encapsulated,

S $ ← {0; 1} κ , then draws r $ ← Z * p , sets c = (C 1 = g r 1 , C 2 = g r 2 )
, and, for each i ∈ B, with

pk ′ i = (h i = h xi , pk i ), sets K i = H(h r i
), and then sets E i ← Kyber.Enc(pk i , S ⊕ K i )6 . 2. One then computes K||V ← PRG(S), in order to grant the early aborts paradigm, and sets the encapsulation as: C ← (c, {E i } i∈B , V ), the encapsulated key as K, and outputs: and(c, E i , V ) in C, one decapsulates the underlying hybrid KEM to get the potential seed S used for the key:

(K, C). -Covercrypt.Dec(usk = (uid = (α, β), {sk j } j∈A ), C = (c, {E i } i∈B , V )): For i ∈ B, for each sk ′ j = (x j , sk j ) in usk
• first, K ′ i,j ← Kyber.Dec(sk j , E i ); • for ElGamal, from c = (C 1 , C 2 ), one computes K j ← H((C α 1 C β 2 ) xj ); • S i,j is then computed as S i,j ← K ′ i,j ⊕ K j .
In the early-abort check, one computes U ′ i,j ||V ′ i,j ← PRG(S i,j ), and checks whether V ′ i,j = V . In the positive case, one returns K ← U ′ i,j , for this first valid (i, j), as the session key. Else, if V ′ i,j ̸ = V , the ciphertext is rejected and the loop on the i, j indices goes on 7 . Security Analysis. Our Covercrypt scheme inherits its security properties from the underlying hybrid KEM scheme using both the Kyber PKE and the traceable ElGamal KEM, and as such, is SK-IND-secure as soon as either the DDH or the DMLWE assumptions hold, and PK-IND-secure under both the DDH and the DMLWE assumptions. Correctness also follows from the authentication property of the hybrid KEM, and thus under either the DDH or the DMLWE assumptions.

Traceability. The traceability is inherited from the underlying traceable ElGamal KEM scheme, with t = 1 in Section 5's notations; it relies on the DDH. To check whether a user U with uid = (α, β) using the key sk -which is shared among her and other users -is corrupted, one encapsulates a key that only this user can decapsulate with sk, because the ElGamal encapsulations are group elements with exponent a random linear combination of a vector which is orthogonal to (α, β), following the confirmer construction from Section 5. We stress that our construction with t = 1 does not allow collusions. But it can be extended to confirm larger t-big collusions of traitors.

Implementation

Parameters of Covercrypt. The parameters of Kyber are recalled in the Appendix G, Table 3, with the sizes (in Bytes) of the keys and ciphertexts, using the compression/decompression, as this does not impact our security results, and the Kyber PKE can be used as a black-box from any library.

We have done an implementation in Rust of Covercrypt (a pre-and post-quantum hybridized Anonymous Subset-Cover KEMAC with Early-Aborts), with optimization for a security of 128 bits 8 . We use Kyber-768 (and its pqd kyber library 9 ) and ElGamal on the Curve25519, as group that is of prime order p = 2 255 -19. The hash algorithm used to generate the Early-Abort tags (256 bits) and the keys (256 bits) generated by the KEM is SHAKE-256. Then we present the sizes of the keys and ciphertexts, according to the sizes of A and B, in Table 1. We compare these with the sizes obtained for a KEM based on a pre-quantum [GPSW06] ABE scheme 10 , way more efficient than post-quantum ones such as [DDP + 18] 11 . Acknowledgments. This work was supported in part by the France 2030 ANR Project ANR-22-PECY-003 SecureCompute.

8 https://github.com/Cosmian/cover_crypt 9 https://docs.rs/pqc_kyber/latest/pqc_kyber/ 10 Whose implementation can be found at: https://github.com/Cosmian/abe_gpsw. 11 In this comparison, to translate the attribute setting into a subset-cover one, we consider a context in which users hold |A| + 1 attributes, corresponding to |A| subsets in the subset-cover setting, the subsets being the intersection of one of these attributes with each of the other ones, and that encapsulations are made in the same way with respect to |B| + 1 attributes corresponding to |B| subsets, and for the decapsulation timings, we suppose there is always exactly one subset in the intersection of the ones the user has access to and the ones in the encapsulation.

Adv ind PKE (A) = 2 × Pr D b [A(pk, C, s) = b] -1.
where s is an internal state the adversary keeps between the two steps.

: (pk 0 , pk 1 , C, s)    Adv pk-ind PKE (A) = 2 × Pr D b [A(pk 0 , pk 1 , C, s) = b] -1.

B Proof of Theorem 8

We present a sequence of games, from the AUTH security game against KEM ′ .

Game G 0 : In the initial game, one runs (pk i , sk i ) ← KEM ′ .KeyGen(1 κ ), (c, s) ← KEM.Enc(pk 0 ) and K 0 ∥V ← PRG(s). One then runs s ′ ← KEM.Dec(sk 1 , c), followed by U ′ ∥V ′ ← PRG(s ′ ). We denote P 0 the probability V ′ = V . This is Adv auth KEM ′ (1 κ ). Game G 1 : In this game, we just replace s $ ← {0; 1} κ , that is drawn uniformly at random from the session-key space of KEM, {0; 1} κ . The difference between this game and the previous one is the SK-IND-game on the underlying KEM, against a trivial adversary A 0 . Hence, P 0 -P 1 ≤ Adv sk-ind KEM (τ ), τ the running time of the trivial adversary A 0 that runs two key generations, one encapsulation, two PRG evaluations, and one decapsulation. Game G 2 : In this game, one takes K 0 ∥V $ ← {0; 1} k+ℓ . This is indistinguishable from the previous game except with probability Adv ind PRG κ,k+ℓ (τ ′ ). Hence, P 1 -P 2 ≤ Adv ind PRG κ,k+ℓ (τ ′ ), where τ ′ is the running time of another trivial adversary A 1 that runs two key generations, one encapsulation, one PRG evaluations, and one decapsulation. In this game, as V is drawn uniformly at random from {0; 1} ℓ , the probability that it is equal to

V ′ ∈ {0; 1} ℓ is equal to 2 -ℓ : P 2 = 2 -ℓ .
Finally, from the above, one deducts that:

Adv auth KEM ′ (κ) ≤ 2 -ℓ + Adv sk-ind KEM (τ ) + Adv ind PRG κ,k+ℓ (τ ′ )

C Proof of Theorem 14

To prove this theorem, we first give a description of the confirmer algorithm C, then we provide the indistinguishability analysis, and eventually prove C will give a correct answer.

Description of the Confirmer C: The confirmer algorithm C can proceed as follows, for a candidate subset G: {usk j = (v j,k ) k } j∈G , for G of size at most t: it chooses (u k ) k orthogonal to the subvector-space spanned by {(v j,k ) k } j∈G , which means that: k u k v j,k = 0, ∀j ∈ G. This is possible as (v j,k ) k∈ [1,t+1],j∈G is of rank at most t in Z t+1 q . Then the kernel is of dimension at least 1. One generates a fake ciphertext C = (C k ) k , with C k ← h r k • g u k s ′ , for random r, s ′ $ ← Z q , and then K ← h r :

-Any key usk j in G will lead to:

k C v j,k k = k g (rs k +s ′ u k )•v j,k = g r k s k v j,k +s ′ k u k v j,k = g rs+s ′ ×0 = K;
and any key usk j outside G will lead to:

k C v j,k k = K × (g k u k v j,k ) s ′ ̸ = K.
we will show this allows to confirm at least one traitor from a candidat subset of traitors.

Indistinguishability Analysis. The above remark about the output key from a pirate decoder P assumes an honest behavior, whereas it can stop answering if it detects the fake ciphertext. We first need to show that, with the public key pk = ((h k ) k , h) and only {usk j = (v j,k ) k } j∈G , one cannot distinguish the fake ciphertext from a real ciphertext, generated as above: from a Diffie-Hellman tuple (A = g a , B = g r , C), one can derive, from random scalars s, s

′ k , u k $ ← Z q , such that k v j,k s ′ k = s and k v j,k u k = 0, for j = 1 . . . , n: h k ← A u k • g s ′ k = g au k +s ′ k h ← g s usk j = (v j,k ) k for j ∈ G
where we implicitly define

s k ← au k + s ′ k , that satisfy k v j,k s k = k v j,k (s ′ k + au k ) = k v j,k s ′ k + a k v j,k u k = s + 0 = s. Then, one defines C k ← C u k • B s ′ k and K ← B s . Let us note C = g r-c
, where c is either 0 (a Diffie-Hellman tuple) or random:

C k = A (r+c)u k • g rs ′ k = (A u k • g s ′ k ) r • A cu k = h r k • (A c ) u k .
One can remark that: when c = 0 (Diffie-Hellman tuple), C = (C k ) k is a normal ciphertext; when c = s ′ (random tuple), this is a fake ciphertext. Under the DDH assumption, they are thus indistinguishable for an adversary knowing the keys (usk i ) i∈G .

Confirmation of a Traitor. The above analysis shows that a pirate decoder P built from (usk i ) i∈G cannot distinguish the fake ciphertext from a real ciphertext. A useful pirate decoder should necessarily distinguish real key from random key. Then, several situations may appear, according to the actual set T of traitors' keys used to build the pirate decoder P by the adversary A:

-If T ⊆ G, a useful decoder P can distinguish keys; -If T ∩ G = ∅, P cannot distinguish keys, as it can get several candidates, independent from the real or random keys.

Let us now assume we started from G ⊇ T , then the advantage of P in distinguishing real and random keys, denoted p G , is non-negligible, from the usefulness of the decoder. The following steps would also work if one starts with G ∩ T ̸ = ∅, so that the advantage p G is significant. One then removes a user J from G to generate G ′ and new ciphertexts to evaluate p G ′ : if J ̸ ∈ T , usk J is not known to the adversary, and so there is no way to check whether k v J,k s ′ k = s and k v J,k u k = 0, even for a powerful adversary. So necessarily, p G ′ = p G .

On the other hand, we know that p ∅ = 0. So, one can sequentially remove users until a significant gap appears: this is necessarily for a user in T .

⊓ ⊔ Hence, we can claim Adv pk-ind KEM (A) ≤ Adv pk-ind KEM1 (τ ) + Adv pk-ind KEM2 (τ ). ⊓ ⊔

D.6 Proof of theorem 12

From a Diffie-Hellman tuple (A, B, C), one can derive, for random s k

$ ← Z q , for k = 1 . . . , t + 1 h k ← g s k h ← B C k ← A s k K ← C
where s, r are implicitly defined as A = g r and B = g s . If C is indeed the Diffie-Hellman value for (g, A, B), then K = C = g sr = h r , we are in the real case (b = 0). If C is a random value, we are in the random case (b = 1):

Adv sk-ind TKEM (A) ≤ Adv ddh G (τ ).

⊓ ⊔

D.7 Proof of theorem 13

From a Diffie-Hellman tuple (A, B, C), one can derive, for random scalars z

(0) k , z (1)
k , s

k , s

k , z (0) , z (1) , s (0) , s (1) $ ← Z q , for k = 1 . . . , t + 1

h (0) k ← A z (0) k • g s (0) k h (0) ← A z (0) • g s (0) h (1) k ← A z (1) k • g s (1) k h (1) ← A z (1) • g s (1) C k ← C z (b) k • B s (b) k
where r is implicitly defined as B = g r . If C is indeed the Diffie-Hellman value for (g, A, B), then

C k = A rz (b) k • g rs (b) k = (A z (b) k • g s (b) k ) r = (h (b) k ) r . If C is a random value C = A r+c , for a random c $ ← Z q : C k = A (r+c)z (b) k • g rs (b) k = (A z (b) k • g s (b) k ) r • A cz (b) k = (h (b) k ) r • A cz (b) k . As z (b)
k is perfectly hidden in the public key, C k follows a uniform distribution in G, independently of the public key, and thus of b:

Adv pk-ind TKEM (A) ≤ Adv ddh G (τ ). ⊓ ⊔ D.8 Proof of theorem 17
In the selective setting, the adversary asks, from the beginning, the keys it wants to get, before seeing the global public parameters PK.

Game G 0 : In the initial game, the adversary thus asks for the keys it wants: for several sets A j . One calls (pk i , sk i ) ← KEM.KeyGen(1 κ ), for each S i ∈ Σ, and provides PK together with all the asked keys sk i , for i ∈ A = ∪A j (all the asked sets). The adversary answers with a set B, but with the constraint that A ∩ B = ∅, and the challenger flips a random bit b $ ← {0; 1}, generates two random session keys K ′ 0 , K ′ 1 ← K, runs (C i , K i ) ← KEM.Enc(pk i ) for all i ∈ B, and outputs C ← (i, C i , E i = K ′ 0 ⊕ K i ) i∈B together with the challenged key K ′ b (that is either the really encapsulated key if b = 0 or a random key if b = 1). The adversary outputs its guess b ′ . We denote P 0 the probability of event b ′ = b, which is (1 + Adv sk-ind KEMAC (A))/2. Game G 1 : In this game, we replace all the K i 's by K i $ ← K in the generation of E i . To show this game is indistinguishable from the previous one, we define a sequence of hybrid games, for index I, such that for all i < I, one replaces K i by a random element in K. For I = 1, this is G 0 , whereas for I = q k + 1, where q k is the maximal number of keys, this is G 1 . And the gap between I and I + 1 is the SK-IND-game on the underlying KEM. Hence, P 0 -P 1 ≤ q k × Adv sk-ind KEM (τ ), where τ is the maximum running-time of adversary A. Game G 2 : In this game, we replace all the E i 's by E i $ ← K, which is perfectly indistinguishable from K ′ 0 ⊕ K i for a random K i , under the group-law property. Hence, P 1 = P 2 . In this final game, this is clear that P 2 = 1/2, as K ′ 0 and K ′ 1 do not appear anymore in C, and so K ′ b is just a random key.

Hence, Adv sk-ind KEMAC (A) ≤ 2q k × Adv sk-ind KEM (τ ).

⊓ ⊔ E Basic (Without Anonymity) Subset-Cover KEMAC

For efficiency considerations, we will focus on the subset-cover approach: during the Setup, one defines multiple sets S i ; when generating a user key usk j , a list A j of subsets if specified, which implicitly means user U j ∈ S i for all i ∈ A j ; at encapsulation time, a target set T is given by B, such that T = ∪ i∈B S i . Intuitively, S i 's are subsets of the universe of users, and to specify the receivers, one encapsulates the key K for a covering of the target set T . A KEMAC, for a list Σ of sets S i , can then be defined from any KEM in K that is a group with internal law denoted ⊕:

-KEMAC.Setup(Σ), for each S i ∈ Σ, runs (pk i , sk i ) ← KEM.KeyGen(1 κ ). Then PK ← (pk i ) i and MSK ← (sk i ) i ; -KEMAC.KeyGen(MSK, A j ) defines the user's secret key usk j ← (i, sk i ) i∈Aj ; -KEMAC.Enc(PK, B) generates a random session key K ← K, and runs (C i , K i ) ← KEM.Enc(pk i ) for all i ∈ B, and outputs C ← (i, C i , E i = K ⊕ K i ) i∈B together with the encapsulated key K; -KEMAC.Dec(usk j , C) looks for i ∈ usk j ∩ C, to run K ′ i ← KEM.Dec(sk i , C i ) and output K ← K ′ i ⊕ E i .

In terms of attributes, one can consider that each S i is associated to an attribute a i , and being in S i for a user U j means owning the attribute a i . At encapsulation time, B lists the attributes that allow to decrypt: as soon as a i is in B, any user U j owning a i can decrypt.

For the above scheme, we can claim the SK-IND security, but unfortunately not the AC-IND security. As attributes are known, the correctness of the KEM implies the correctness of the KEMAC.

Theorem 17 (Session-Key Privacy). If the underlying KEM is SK-IND-secure, the above basic subsetcover KEMAC is SK-IND-secure, for selective key-queries: Adv sk-ind KEMAC (τ ) ≤ 2q k × Adv sk-ind KEM (τ ), where q k is the number of key-queries.

As this proof uses a classical hybrid technique to replace each key by a random one, we defer the proof to the Appendix D.8. One notes that we need B to be provided in the ciphertext: indices i are given. We definitely exclude access-control privacy. In order to get anonymity, theses indices should not be given.

$

  ← K, C ← PKE.Enc(pk, K), and outputs (K, C); -KEM.Dec(sk, C) outputs PKE.Dec(sk, C). CRYSTALS-Kyber PKE We recall the algorithms of the CRYSTALS-Kyber [ABD + 21] public-key encryption whose both indistinguishability and anonymity rely on the hardness of Module-LWE [LS15].

  k η1 , then set pk ← (A, b = As + e) and sk ← s. -Kyber.Enc(pk, K): r $ ← B k η1 , and (e 1 , e 2 ) $ ← B k η2 ×B η2 , then set u = A T r+e 1 and v = b T r+e 2 +⌈ q 2 ⌋•K, and return C = (u, v).

  Anonymity. A PKE is anonymous, also known as public-key privacy (denoted PK-IND) if for two honestly generated pk 0 and pk 1 , when the adversary chooses a message m, it cannot distinguish an encryption of m under pk 0 from the encryption of m under pk 1 . More formally, a PKE is PK-IND-secure if for any adversary A, Adv pk-ind PKE (A) = negl(κ), for b i , sk i ) ← PKE.KeyGen(1 κ ), (m, s) ← A(pk 0 , pk 1 ), C ← PKE.Enc(pk b , m)

  0 for all i, using oracle OKeyGen(Y i ) that stores Y i in the set Y and outputs KEMAC.KeyGen(MSK, Y i ). A KEMAC is said to be AC-IND-secure if for any adversary A, that can ask any key usk i , using oracle OKeyGen(Y i ) that stores Y i in the set Y and outputs KEMAC.KeyGen(MSK, Y i ), Adv ac-ind KEMAC (A) = negl(κ), for b

$

← {0; 1} and

Table 1 .

 1 Sizes of keys and encapsulations (in Bytes) according the sizes of A and B.Benchmarks The benchmarks in table 2 are performed on an Intel Core Processor (Haswell, no TSX) CPU @3MHz. The table shows the time required to generate Covercrypt encapsulations and decapsulations for a 32-Byte symmetric key, with the same definitions for the sizes |A| and |B| as in table1. These performances are, as before, compared with the [GPSW06]-based KEM's.

	Size of A	1	2	3	4	5
	Covercrypt Secret Key usk	1250	2435	3620	4805	5990
	Coverc. Pre-Quant. S. K. (uid, {xi}i)	98	131	164	197	230
	User Secret Key with GPSW	340	504	668	832	996
	Size of B	1	2	3	4	5
	Covercrypt Encapsulation C	1171	2260	3349	4438	5527
	Covercrypt Pre-Quant. Encaps. (c, V )	115	148	181	214	247
	GPSW KEM Encapsulation	400	452	504	556	608

Table 2 .

 2 Comparisons of Covercrypt and GPSW-based encapsulation/decapsulation times. For decapsulation, the GPSW-based KEM has a constant runtime of approximately 3880 µs. Indistinguishability. A PKE is indistinguishable (denoted IND) if for an honestly generated pk, when the adversary chooses two messages m 0 and m 1 , it cannot distinguish an encryption of m 0 from an encryption of m 1 , both under pk. More formally, a PKE is IND-secure if for any adversary A, Adv ind PKE (A) = negl(κ), for b

	Size of B	1	2	3	4	5
	Covercrypt	191	272	329	401	487
	GPSW KEM	4793 5431 6170 6607 7245
	Encapsulation time (in µs)
	|A| ↓ \ |B| →	1	2	3	4	5
	1	214	247	288	345	454
	2	311	386	466	543	562
	3	334	400	505	608	702
	4	471	613	781	908	1072
	5	467	646	831	1058 1212
	Covercrypt decapsulation time (in µs)

https://github.com/Cosmian/cover_crypt

https://docs.rs/aes-gcm/latest/aes_gcm/

Our base pre-quantum KEM is thus the ROM.UTKEM described in appendix F.

Note that this is the optimized version of a generic one where one would have drawn |B| extra session keys K ′ i , Ei would actually have been a Kyber encryption of these K ′ i 's instead of the S ⊕ Ki, and one would have had to send |B| extra Fi ← Ki ⊕ K ′ ⊕ S.

Again, this corresponds to our optimized version, taking advantage of the encrypting properties of Kyber. For a generic hybrid KEMAC, one would have output U ′ i,j ⊕ Fi when V ′ i,j = V (cf. previous footnote for the definition of Fi).

Appendix A Public-Key Encryption

A Public-Key Encryption (PKE) scheme is defined by 3 algorithms:

-PKE.KeyGen (1 κ ): the key generation algorithm outputs a pair of public and secret keys (pk, sk); -PKE.Enc(pk, m): the encryption algorithm encrypts the input message m under the public key pk and outputs the ciphertext C; -PKE.Dec(sk, C): the decryption algorithm outputs the message m encrypted in C.

We will use the classical notion of indistinguishability and of anonymity of such a PKE scheme, similarly to the same notions for KEMs:

D Other Deferred Proofs

D.1 Proof of theorem 6

We present a sequence of games, starting from the initial SK-IND security game against KEM ′ : Game G 0 : In the initial game, a challenger runs (pk, sk) ← KEM.KeyGen(1 κ ), (c, s) ← KEM.Enc(pk), and evaluates U ∥V ← PRG(s) to output (pk, C = (c, V ), K b ), where b $ ← {0; 1} is a random bit, K 0 = U , and K 1 $ ← {0; 1} k . From this output, the adversary returns her guess b ′ for b. We denote P 0 the probability of event b ′ = b happening, which is (1 + Adv sk-ind KEM ′ (A))/2. Game G 1 : In this game, s $ ← {0; 1} κ is this time drawn uniformly at random from the session-key space of KEM, {0; 1} κ , and one sets: U ∥V ← PRG(s). The difference is the SK-IND-game on the underlying KEM. Hence, P 0 -P 1 ≤ Adv sk-ind KEM (τ ), where τ is the maximum running-time of adversary A. Game G 2 : In this game, one takes U ∥V $ ← {0; 1} k+ℓ , which is indistinguishable unless from the previous game except with probability Adv ind PRG κ,k+ℓ (τ ), where τ is the maximum running time of adversary A. Hence, P 1 -P 2 ≤ Adv ind PRG κ,k+ℓ (τ ). In this final game, this is clear that P 2 = 1/2, as U and K are both randomly drawn in {0;

We present a sequence of games, starting from the initial PK-IND security game against KEM ′ :

Game G 0 : In this game, for every i in {0; 1}, a challenger runs (pk i , sk i ) ← KEM.KeyGen(1 κ ), (c i , s i ) ← KEM.Enc(pk i ), and gets

From the output, an adversary A outputs her guess b ′ for b. We denote P 0 the probability of the event b ′ = b happening, which is equal to (1 + Adv pk-ind KEM ′ (A))/2. Game G 1 : This game is as the previous one, except that now, one uses s i $ ← {0; 1} κ to evaluate U i ∥V i ← PRG(s i ), for every i in {0; 1}. The correct guess probability difference is the SK-IND-game on the underlying KEM, for both i's in {0; 1}. Hence, P 0 -P 1 ≤ 2 × Adv sk-ind KEM (τ ), where τ is the maximum running-time of adversary A. Game G 2 : This game is as the previous one, except that now, for each i ∈ {0; 1}, the challenger draws U i ∥V i $ ← {0; 1} k+ℓ . This is indistinguishable from the previous game under the security of PRG : {0; 1} κ → {0; 1} k+ℓ . Hence, P 1 -P 2 ≤ Adv ind PRG κ,k+ℓ (τ ), where τ is the maximal running time of the adversary A. Game G 3 : Now, one outputs (pk 0 , pk 1 , C b = (c b , V )), for a random b $ ← {0; 1} and a random V $ ← {0; 1} ℓ . This simulation is perfectly indistinguishable from the previous game: P 2 = P 3 . And this final game is exactly the PK-IND-game on the underlying KEM:

The proof is quite similar to above proof. In the selective setting, the adversary asks, from the beginning, the keys it wants to get, before seeing the global public parameters PK.

Game G 0 : In the initial game, the adversary thus asks for the keys it wants: for several sets A j . One calls (pk i , sk i ) ← KEM ′ .KeyGen(1 κ ), for each S i ∈ Σ, and provides PK together with all the asked keys sk i , for i ∈ A = ∪A j (all the asked sets). The adversary answers with two sets B 0 and B 1 , but with the constraints that

, and the challenger flips a random bit b $ ← {0; 1}, generates a random session key K ← K, runs (C i , K i ) ← KEM ′ .Enc(pk i ) for all i ∈ B 0 ∪B 1 , and outputs C ← (C i , E i = K ⊕ K i ) i∈B b together with the challenged key K. The adversary outputs its guess b ′ . We denote P 0 the probability of event b ′ = b, which is (1 + Adv ac-ind KEMAC (A))/2. Game G 1 : In this game, one always outputs C ← (C i , E i = K ⊕ K i ) i∈B0 . To show this game is indistinguishable from the previous one, we define a sequence of hybrid games, for index I, such that for the I first (C i , E i = K ⊕ K i ) in C are for indices in B 0 and the last are for indices in B b . For I = 0, this is G 0 , whereas for

And the gap between I and I + 1 is the PK-IND-game on the underlying KEM ′ . Hence, P 0 -P 1 ≤ |B 0 |×Adv pk-ind KEM ′ (τ ), where τ is the maximum running-time of adversary A. Furthermore, in this final game, this is clear that P 1 = 1/2, as the challenge C does not depend on b anymore.

, where S B is the constant-size of the sets B. ⊓ ⊔

D.4 Proof of theorem 4

We present the sequence of games, first exploiting the session-key privacy of KEM 1 .

Game G 0 : In the initial game, the adversary receives pk ← (pk 1 , pk 2 ), both keys having been generated by the respective key generation algorithms, together with

or a random key from K, according to the random bit b.

The adversary outputs its guess b ′ . We denote P 0 the probability of event b

, where t is the maximum running-time of adversary A. In this final game, this is clear that P 1 = 1/2, as K is truly random in K in both cases.

Hence, Adv sk-ind KEM (A) ≤ Adv sk-ind KEM1 (t). In the same way, one can prove

The proof is quite similar to the previous one, but with the security of both schemes:

Game G 0 : In the initial game, the adversary receives pk (0) ← (pk

2 ) and pk (1) ← (pk

2 ), with keys having been generated by the respective key generation algorithms, together with

i ), according to the random bit b. The adversary outputs its guess b ′ . We denote P 0 the probability of event b

, where t is the maximum running-time of adversary A. Game G 2 : In this game, we replace (

In this final game, this is clear that

Here is the derived ElGamal TKEM in the ROM: ROM.UTKEM.KeyGen(1 κ , n, t, g, G, q): This algorithm returns the outputs (pk, {usk j } j ) of TKEM.KeyGen

(1 κ , n, t, g, G, q); ROM.UTKEM.Enc(pk): this algorithm runs (C, K) ← TKEM.Enc(pk), and then with H : {0; 1} * → {0; 1} µ , a hash function modeled as a random oracle, it sets: K ′ ← H(K), and returns (C, K ′ ); ROM.UTKEM.Dec(usk j , C): this algorithm runs K ← TKEM.Dec(usk j , C), and then returns K ′ ← H(K).

Proof that ROM.UTKEM is SK-IND and PK-IND-secure follows immediately from the proofs that TKEM is SK-IND and PK-IND-secure, in the ROM.

F.2 ElGamal UTKEM without the ROM

The Uniform-Keys TKEM without the ROM, in its derived authenticated KEM scheme (as it is derived in a non black-box way), is described with the following algorithms, with PRG : {0; 1} κ → {0; 1} ℓ+k a PRG, and denoting E = ⟨g⟩ and Ẽ = ⟨g⟩ common twisted curves of respective prime orders p, p over the finite field F q such that q is on κ bits and |q -2 κ | ≤ 2 κ/2 , and absc the operation converting a curve element to the bitstring of its abscissa:

UTKEM ′ .KeyGen(1 κ , n, t): This algorithm runs (pk 0 , {usk 0,j } j ) ← TKEM.KeyGen(1 κ , n, t, g, E, q), (pk 1 , {usk 1,j } j ) ← TKEM.KeyGen(1 κ , n, t, g, Ẽ, q), and returns: (pk = (pk 0 , pk 1 ), {usk j = (usk 0,j , usk 1,j )} j ); UTKEM ′ .Enc(pk): this algorithm flips a coin b $ ← {0; 1}, runs: (c 0 , s 0 ) ← TKEM.Enc(pk 0 ), (c 1 , s 1 ) ← TKEM.Enc(pk 1 ), and: K∥V ← PRG(absc(s b )), and finally outputs: (C = (c 0 , c 1 , V ), K); UTKEM ′ .Dec(usk j , C): this algorithm runs s 0 ← TKEM.Dec(usk 0,j , c 0 ), s 1 ← TKEM.Dec(usk 1,j , c 1 ),

), and checks whether

Else, if none of these two conditions are met, the algorithm returns ⊥.

One remarks that in UTKEM ′ , correctness is not perfect, but ensured except with probability 2 Game G 0 : In the initial game, setting: (pk = (pk 0 , pk 1 ), sk = {usk j = (usk 0,j , usk 1,j )} j ) ← UTKEM ′ .

KeyGen(1 κ , n, t), the adversary is given pk; K 1 is drawn uniformly at random from {0; 1} k , as well as b from {0; 1}, and (C = (c 0 , c 1 , V ), K 0 ) ← UTKEM ′ .Enc(pk), and the adversary is provided with C and K b . The adversary outputs her guess b ′ for b. We denote P 0 the probability of event b ′ = b, which is (1

Game G 1 : this game is identical to the previous one, except that now in the UTKEM ′ .Enc(pk) operation, the s 0 generated with c 0 is replaced with a random element of E, and the s 1 generated with c 1 is replaced with a random element of Ẽ. The adversary then looses twice her advantage in the SK-IND security game of the underlying TKEM, and: P 0 -P 1 ≤ 2 • Adv sk-ind TKEM (t). Game G 2 : this game is identical to the previous one except that now, the absc(s a ) (with a ∈ {0; 1}) used as an input to PRG to generate V is replaced with a random bit in {0; 1} κ . According to [CFGP06]'s corollary 11, since q is on κ bits and |q -2 κ | ≤ 2 κ/2 , then the adversary looses an advantage bounded by (1 + √ 2) • 2 -κ/2 , and:

. Game G 3 : this game is the same as the previous one except that now, K 0 ∥V is replaced by K 0 ∥V $ ← {0; 1} k . The adversary then looses her advantage in the PRG IND-security game: P 2 -P 3 ≤ Adv ind PRG (t). In this final game, this is clear that P 3 = 1/2, as K b and V are then uniformly random.

PK-IND-security of UTKEM ′ We present a sequence of games, starting from the initial PK-IND-security game against UTKEM ′ :

Game G 0 : In the initial game, setting:

(pk 0 = (pk 0,0 , pk 0,1 ), sk 0 = {usk 0,j } j = ({usk 0,0,j } j , {usk 0,1,j } j )) ← UTKEM ′ .KeyGen(1 κ , n, t);

and:

and drawing b $ ← {0; 1}, the adversary is provided with pk 0 , pk 1 , and C b . The adversary outputs her guess b ′ for b. We denote P 0 the probability of the event b ′ = b, which is (1 + Adv pk-ind UTKEM ′ (A))/2. Game G 1 : this game is identical to the previous one, except that now, in the UTKEM ′ .Enc(pk b ) operation to generate C b , the s b,0 and s b,1 generated with c b,0 and c b,1 are replaced by respective group elements of E and Ẽ. The adversary then looses twice her advantage in the SK-IND game of the underlying TKEM: P 0 -P 1 ≤ 2 • Adv sk-ind TKEM (t). Game G 2 : this game is identical to the previous one except that now, denoting absc(s b,a ) the input to PRG used to generate V b , absc(s b,a ) is replaced with a uniformly random element of {0; 1} κ . According to [CFGP06]'s corollary 11, since q is on κ bits and |q -2 κ | ≤ 2 κ/2 , then the adversary looses an advantage bounded by (1 + √ 2) • 2 -κ/2 , and:

. Game G 3 : this game is the same as the previous one, except that now, K b ∥V b is replaced by uniformly random K b ∥V b $ ← {0; 1} k+ℓ . The adversary then looses her advantage in the PRG IND-security game: P 2 -P 3 ≤ Adv ind PRG (t). Game G 4 : this game is identical to the previous one except that now one replaces: (c b,0 , c b,1 ) in the adversary's input by (c 1-b,0 , c 1-b,1 ). This game is perfectly indistinguishable from the previous one: P 3 = P 4 , and the adversary's advantage in it is bounded by twice her advantage in the TKEM PK-IND security game, so:

AUTH-security of UTKEM ′ We present a sequence of games, starting from the initial AUTH-security game against UTKEM ′ :

Game G 0 : In the initial game, setting:

(pk 0 = (pk 0,0 , pk 0,1 ), sk 0 = {usk 0,j } j = ({usk 0,0,j } j , {usk 0,1,j } j )) ← UTKEM ′ .KeyGen(1 κ , n, t);

Game G 1 : this game is identical to the previous one except that now in the UTKEM ′ .Enc(pk 0 ) operation providing C, the s 0 and s 1 are respectively replaced by uniformly random elements of E and Ẽ. The difference between this game and the previous one is twice the SK-IND security game of TKEM, against a trivial adversary A 0 , so: P 0 -P 1 ≤ 2 • Adv sk-ind TKEM (τ ), where τ is the running time of A 0 computing two key generations, one encapsulation, and one decapsulation of UTKEM ′ . Game G 2 : this game is identical to the previous one, except that now, the absc(s b ) used as input to PRG to generate V is replaced by a uniformly random element of {0; 1} κ . According to [CFGP06]'s corollary 11, since q is on κ bits and |q -

. Game G 3 : this game is identical to the previous one, except that now one replaces the original K∥V in the UTKEM ′ .Enc(pk 0 ) operation by K∥V $ ← {0; 1} k+ℓ . This is indistinguishable from the previous game except with probability Adv ind PRG (τ ′ ), where τ ′ is the running time of another trivial adversary A 1 , running two key generations, one encapsulation and one decapsulation of UTKEM ′ , so: P 2 -P 3 ≤ Adv ind PRG (τ ′ ). In this game, the probability that in the UTKEM ′ .Dec(sk 1 , C) operation, the V ′ 0 drawn from c 0 is equal to V is of 2 -ℓ , and the probability that the V ′ 1 drawn from c 1 is equal to V is of 2 -ℓ too, so the probability that V ′ 0 = V or V ′ 1 = V , and so that something different from ⊥ is returned is bounded by 2 1-ℓ , so:

We can first show that decryption indeed gives back K. To this aim, one can note that we have

with z = e T r + s T e 1 + e 2 . Then,

As K ∈ {0; 1} n , if ∥z∥ ∞ < q/4, then ⌈ 2 q • w⌋ = K. And since e, r, s are drawn according to B η1 , and e 1 , e 2 according to B η2 , with appropriate n, k, q, η 1 , η 2 , ∥z∥ ∞ < q/4, with overwhelming probability [ABD + 21], even with the additional compression function, that introduces an additional noise. And we omit it in the current description, as it is for efficiency purpose but does not impact the security notions we are interested in.

G.2 Indistinguishability of Kyber

We proceed with a sequence of games, so that the final game does not leak any information about the bit b used by the challenger when encrypting K b among K 0 and K 1 chosen by the adversary.

Game G 0 : The initial game is the security experiment, where a public key pk = (A, b) is generated, as well as a ciphertext C of K b . Game G 1 : We change the way the challenger generates the public key pk, with randomly chosen b $ ← R q . The distance of the distributions of the outputs of the adversary is then bounded by Adv dmlwe Rq,k,k,η1 (τ ). But still, the ciphertext is built as

We change now the simulation of the ciphertext, with (w, z)

The distance of the distributions of the outputs of the adversary is then bounded by Adv dmlwe Rq,k+1,k,η2 (τ ), as r $ ← B k η1 and (e 1 , e 2 ) $ ← B k η2 × B η2 = B k+1 η2 , and η 1 ≥ η 2 . Game G 3 : We eventually replace C by a random sampling in R k q × R q , which is perfectly indistinguishable. And then, the ciphertext is perfectly independent from K b . We will show that the ciphertexts are statistically close to uniform in the ciphertext space, i.e. in R k q ×R q , whatever the public key.

H Some Figures

Game G 0 : The initial game is the security experiment, where two public keys pk 0 = (A 0 , b 0 ) and pk 1 = (A 1 , b 1 ) are generated and a ciphertext C is generated according to pk b , an a message K chosen by the adversary.

Game G 1 : We change the way the challenger generates the public keys pk 0 and pk 1 , with randomly chosen b 0 , b 1 $ ← R q . The distance of the distributions of the outputs of the adversary is then bounded by 2 × Adv dmlwe Rq,k,k,η1 (τ ). But still, the ciphertext is built as

Game G 2 : We change now the simulation of the ciphertext, with (w, z)

, and

The distance of the distributions of the outputs of the adversary is then bounded by Adv dmlwe Rq,k+1,k,η2 (τ ), as r $ ← B k η1 and (e 1 , e 2 ) $ ← B k η2 × B η2 = B k+1 η2 , and η 1 ≥ η 2 . Game G 3 : We eventually replace C by a random sampling in R k q × R q , which is perfectly indistinguishable. And then, the ciphertext is perfectly independent from the used public key.

H.2 Parameters

In Table 3, we recall the parameters of Kyber, where δ is the security level (one can see δ = 2 -κ ), and (d u , d v ) are some parameters for the compression function, with the sizes (in Bytes) of the keys and ciphertexts, using the compression/decompression.