# Updatable Encryption from Group Actions

Antonin Leroux, Maxime Roméas

► To cite this version:

Antonin Leroux, Maxime Roméas. Updatable Encryption from Group Actions. PQCrypto 2024 - 15th International Conference on Post-Quantum Cryptography, Jun 2024, Oxford, United Kingdom. hal-04389878

HAL Id: hal-04389878

https://hal.science/hal-04389878v1

Submitted on 12 Jan 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Updatable Encryption from Group Actions

Antonin Leroux¹ and Maxime Roméas²

¹ DGA-MI, Bruz, France antonin.leroux@polytechnique.org

² ANSSI, Paris, France maxime.romeas@ssi.gouv.fr

**Abstract.** Updatable Encryption (UE) allows to rotate the encryption key in the outsourced storage setting while minimizing the bandwidth used. The server can update ciphertexts to the new key using a token provided by the client. UE schemes should provide strong confidentiality guarantees against an adversary that can corrupt keys and tokens. This paper studies the problem of building UE in the group action framework. We introduce a new notion of Mappable Effective Group Action (MEGA) and show that we can build CCA secure UE from a MEGA by generalizing the SHINE construction of Boyd et al. at Crypto 2020. Unfortunately, we do not know how to instantiate this new construction in the post-quantum setting. Doing so would solve the open problem of building a CCA secure post-quantum UE scheme.

Isogeny-based group actions are the most studied post-quantum group actions. Unfortunately, the resulting group actions are not mappable. We show that we can still build UE from isogenies by introducing a new algebraic structure called Effective Triple Orbital Group Action (ETOGA). We prove that UE can be built from an ETOGA and show how to instantiate this abstract structure from isogeny-based group actions. This new construction solves two open problems in ciphertext-independent post-quantum UE. First, this is the first post-quantum UE scheme that supports an unbounded number of updates. Second, our isogeny-based UE scheme is the first post-quantum UE scheme not based on lattices. The security of this new scheme holds under an extended version of the weak pseudorandomness of the standard isogeny group action.

**Keywords:** Updatable Encryption, Group Actions, Isogenies, Post-Quantum Cryptography

## 1 Introduction

Updatable Encryption (UE), introduced by Boneh et al. in 2013 [7], is a very useful primitive for storing encrypted data<fnref n="3" /> on a cloud server. To fight against risks of seeing the secret key compromised, the client can always download its data, decrypt it, encrypt it under a new key and upload it back on the server. However, this solution uses too much bandwidth to be considered practical. Dealing with key rotation while minimizing bandwidth usage is the goal of UE. This

<footnote n="3">³ UE is a variant of symmetric encryption</footnote>
work focuses on the ciphertext-independent variant of UE, where the client generates a single value, called a token, when rotating its key. This token can then be used by the server to update all of the client’s ciphertexts under the latest key. Unlike symmetric encryption, UE schemes aim at preserving the confidentiality of the data in a setting where secret keys and update tokens can leak. The huge real-life applications of UE explains the recent renewed interest on the subject [24,23,9,22,28].

*Related Work.* Security notions for UE have evolved a lot since the original proposal of [7]. Lehmann and Tackmann [24] proposed two CPA security notions where the adversary can adaptively corrupt keys and tokens. Their IND-ENC notion requires fresh encryptions to be indistinguishable and their IND-UPD notion asks the same for updated ciphertexts. Klooß et al. [23] augmented the previous notions with CCA security and integrity protection. Boyd et al. [9] introduced the IND-UE notion which is stronger than previous ones and requires fresh encryptions to be indistinguishable from updated ciphertexts. They also show that a CPA UE scheme with ciphertext integrity (CTXT) is CCA.

As for UE constructions in the classical setting, RISE of [24], is an updatable variant of ElGamal where the public key is used in the token. [23] introduced two generic constructions based on encrypt-and-MAC (secure under DDH) and on the Naor-Yung transform (secure under SXDH). Boyd et al. [9] proposed the permutation-based SHINE schemes, that achieve their stronger detIND-UE-CCA security notion in the ideal cipher model (under DDH).

In the post-quantum setting, Jiang [22] presented the first post-quantum UE scheme LWEUE (secure under LWE). In [28], Nishimaki introduced RtR, another LWE-based UE scheme, which is the first ciphertext-independent UE scheme that prevents the adversary from obtaining the new key from the knowledge of the update token and the old key. Nishimaki showed that UE schemes with this property have stronger security than those without. Unlike RtR, the UE schemes introduced in this work do not have this property. These two LWE-based UE schemes use homomorphic operations to re-randomize updated ciphertexts which has two main drawbacks. On one hand, ciphertext noise grows with each key update, which means that these schemes only support a bounded number of updates. On the other hand, using the homomorphic property and the knowledge of the update token, an adversary can craft ciphertexts of related messages which means that these schemes are not CCA secure (only randIND-UE-CPA).

We try to overcome these issues by using group actions to build UE. The first efficient post-quantum group action was introduced by Castryck et al. using isogenies [11]. Their construction is called CSIDH and it uses the group action of the class group of the quadratic order $\mathbb{Z}[\sqrt{-p}]$ on the supersingular curves defined over $\mathbb{F}_p$. Other proposals following the same idea but for different families of quadratic orders have been introduced such as SCALLOP [17] presented at PKC 2023. The resulting group actions are believed to be post-quantum one-way, i.e., hard to invert, and this has motivated to study the protocols that can be built generically upon a cryptographic group action. This is what is done for instance in the work of Alamati et al. [2]. Since, then, other proposals of post-
quantum group action have been introduced such as the work of Tang et al. [35]
or of Ji et al. [21], both based on multivariate problems. To our knowledge, there
does not exists any UE scheme in the group action framework, even if we will
show that the SHINE construction fits into that framework.

Eaton et al. [18] have introduced an isogeny-based “updatable encryption” scheme on the CSIDH group action. However, their construction does not achieve at all the same primitive. Their construction target public key encryption schemes and the updates are only applied to keys and not ciphertexts. Their construction shares some similarities with ours as they use elements of the class group as secret keys and the update mechanism is made of a group action computation.

*Overview of the contributions.* We present two new generic constructions of UE from abstract algebraic frameworks. The first construction is called GAINE for Group-Action Ideal-cipher Nonce-based Encryption. GAINE generalizes the SHINE [9] construction and builds UE from a weak pseudorandom group action as defined in [2]. In fact, SHINE is a concrete instantiation of GAINE for the group action of $Z_q^*$ on any cyclic group $H$ of order $q$ by exponentiation. The hardness of the DDH problem over this group implies that the resulting group action is weak pseudorandom. For SHINE, and GAINE, to work, we need one other thing: that the set $H$ is mappable, i.e., that there exists an invertible and efficient map $\pi$ going from the space of messages to the set of the group action. The authors of SHINE showed how to build this map when $H$ is the group of points of an elliptic curve. The idea is to use this map to translate messages as elements of the group $H$ before encrypting them with exponentiation, using secret keys as exponents. In that setting, the token is simply an exponent and the update is just another exponentiation. Overall, SHINE is quite simple and we show that it adapts very naturally to the setting of cryptographic group actions. If the group action is abelian and transitive, a straightforward generalization of SHINE's security proof shows that we can instantiate GAINE with a group action that satisfies the analog of the classical DDH assumption for group actions. Moreover, we show that it is still possible to instantiate GAINE with a nonabelian group action. Only this time, we need the group action to be weak pseudorandom, i.e., an adversary cannot distinguish between many samples that or either of the form $(s_i, g \star s_i)$, where $g$ is a random group element and the elements $s_i$ are random set elements, or samples of the form $(s_i, t_i)$ where $s_i$ and $t_i$ are random set elements. Moreover, we show that we can apply the transform used in SHINE to make our GAINE UE scheme CCA. Unfortunately, we do not know how to instantiate GAINE in the post-quantum setting. Indeed, there are currently two cryptographic group actions that are mappable and believed to be post-quantum. The first one was introduced by Tang et al. [35] and uses alternating trilinear forms, while the second one from Ji et al. [21] is based on tensors. These two group actions are not abelian and they are conjectured to be weak pseudorandom but only over a very small number of samples. However, when working with nonabelian group actions, our security proof for GAINE needs one sample per ciphertext. Thus, we are not currently able to give a practical post-quantum instantiation for GAINE.
Finding one would solve the problem left open by Jiang [22] at Asiacrypt2020 to build a CCA post-quantum UE scheme.

Isogeny-based cryptography provides another source of post-quantum weak pseudorandom group actions. However, it is notoriously hard to sample elements in the set of the known group actions based on isogenies (see [8]), and it is the case for CSIDH [11] and SCALLOP [17], the two most promising group actions based on isogenies. Thus, we cannot really hope to instantiate GAINE from isogenies. However, these group actions remain credible post-quantum candidates since they are not affected by the recent attacks against SIDH [12,31,25].

This is why we show how to build UE from the CSIDH and SCALLOP group actions. We circumvent the mappable requirement by using an idea of Moriya et al. for their SIGAMAL encryption scheme [26]. Intuitively, their idea is to see messages as scalars that are mapped to points of an elliptic curve using the scalar multiplication but this time in a group where discrete logarithm is easy so that we can decrypt efficiently. The points obtained in this manner are encrypted using isogenies. We obtain an analog of the standard isogeny group action by considering a set made of elements constituted by a curve and a point (and not just a curve). We will require that this extended group action is weak pseudorandom, which is a much less standard assumption than the pseudorandomness of the usual isogeny group action. Nonetheless, this problem have been studied in the context of SIGAMAL and it is still believed to be hard. In particular the recent paper [10] explored to no-effect an avenue of attacks based on self-pairings. We refine the idea of Moriya et al. to get a scheme that is updatable.

The way we circumvent the issue that CSIDH is not mappable could be of independent interest as there are several examples of protocols where this proves to be a big obstacle [1,4].

We extracted an abstract framework of this idea to identify the algebraic structure required by our new UE scheme. This gave us what we call a TOGA for Triple Orbital Group Action. As the name suggests, there are three group actions involved in this scheme, each with a specific role, and we require the three different operations to interact in a very specific way that we summarized in Fig. 8. We introduce TOGA-UE, a generic UE protocol based on a TOGA family. Unfortunately, deriving a CCA encryption scheme from TOGA-UE seems hard and we leave that to future work.

Finally, we show how to build a TOGA from the isogeny group actions CSIDH and SCALLOP. This gives an instantiation of post-quantum UE based on another family of assumptions. In particular, it is the first post-quantum UE scheme that does not suffer any limitations regarding the number of updates, contrary to the solutions based on lattices. The known instantiation of these group actions reach a fixed level of security due to the sub-exponential complexity of some of the algorithms. We leave the problem of overcoming this obstacle to future work.

*Acknowledgements.* The authors are very thankful to Jonas Lehmann and Sabrina Kunzweiler for pointing out a mistake in an earlier version of the paper.
*Outline of the paper.* In Section 2 we introduce the necessary notions and backgrounds. Section 3 is dedicated to our first construction GAINE of UE from a MEGA. Our second UE scheme TOGA-UE is introduced in Section 4, where we present our new algebraic structure of TOGA before showing how to build UE from it. Finally, in Section 5, we show how to instantiate TOGA-UE.

# 2 Preliminaries

*Notations.* For a finite set $S$, we use $s \stackrel{\$}{\leftarrow} S$ to sample uniformly from $S$. For a probability distribution $\mathcal{D}$ on a finite set $S$, we use $s \leftarrow \mathcal{D}$ to sample from $\mathcal{D}$. We use $\mathcal{S}(S)$ to denote the set of permutations of a finite set $S$. For an algorithm $\mathcal{A}$ and an oracle $\mathcal{O}$, $\mathcal{A}$ having access to $\mathcal{O}$ is denoted by $\mathcal{A}^{\mathcal{O}}$.

## 2.1 Cryptographic group actions

In this section, we give a few reminders about group actions and how they can be endowed with hardness properties for cryptographic use. We use the framework of cryptographic group actions of Alamati et al. [2].

**Definition 1 (Group Action).** Let $G$ be a group for a law written multiplicatively and let $S$ be a set. A group action of $G$ on $S$ is an operation $\star : G \times S \rightarrow S$ such that

1. If $1_G$ is the identity element of $G$, then for any $s \in S$, we have $1_G \star s = s$.

2. For any $g, h \in G$ and any $s \in S$, we have $(gh) \star s = g \star (h \star s)$.

We may use the notation $(G, S, \star)$ to denote a group action. We stress that the group actions used in this work do not need to be abelian. A group action $(G, S, \star)$ partitions the set $S$ into a disjoint union of *orbits* where the orbit of $s \in S$ is the set $\text{Orb}(s) := \{g \star s \mid g \in G\} \subseteq S$.

*Properties of group actions.* Our group actions $(G, S, \star)$ can be:

1. Transitive: A group action is *transitive* if it has a single orbit, i.e., if for any $(s_1, s_2) \in S$, there exists $g \in G$ such that $g \star s_1 = s_2$. We can always obtain a transitive group action from any group action. Indeed, take $s \in S$, one can easily verify that $(G, \text{Orb}(s), \star)$ is a transitive group action.

2. Free: A group action is *free* if for all $g \in G$, $g = 1_G$ if and only if there exists $s \in S$ such that $g \star s = s$.

Since we need to define computational assumptions related to group actions, we need a notion of efficiency. We say that a group action $(G, S, \star)$ is *effective* (EGA) if $G$ and $S$ can be efficiently represented, the operations and sampling in $G$ as well as $\star$ are efficient. A formal definition is given in Appendix A.

**Definition 2 (Group Action Family).** We say that $\mathcal{G}\mathcal{A}$ is a group action family if, for a security parameter $\lambda$, $\mathcal{G}\mathcal{A}(\lambda)$ consists of a group action $(G, S, \star)$ where $|G|, |S| = \text{poly}(\lambda)$.
In the following, let $\mathcal{G}A$ be a group action family. We define weak pseudo-random group actions:

**Definition 3 (Weak Pseudorandom Group Action [2]).** Let $(G, S, \star)$ be $\mathcal{G}A(\lambda)$ for some security parameter $\lambda$. Let $D_G$ and $D_S$ be distributions on $G$ and $S$ respectively. For $g \in G$, let $\pi_g : S \to S$ be the permutation defined by $\pi_g : s \mapsto g \star s$. For a permutation $f \in \mathfrak{S}(S)$, we use $f^\$$ to denote the randomized oracle that, when queried, samples $s \leftarrow D_S$ and outputs $(s, f(s))$. We say that $(G, S, \star)$ is $(D_G, D_S)$-weakly pseudorandom if, for all PPT adversaries $\mathcal{A}$, we have:

$$ \mathbf{Adv}_{\mathcal{G}A, \mathcal{A}}^{\text{wk-PR}}(\lambda) := \left| \Pr[\mathbf{Exp}_{\mathcal{G}A, \mathcal{A}}^{\text{wk-PR-0}}(\lambda) = 1] - \Pr[\mathbf{Exp}_{\mathcal{G}A, \mathcal{A}}^{\text{wk-PR-1}}(\lambda) = 1] \right| \le \text{negl}(\lambda) $$

where $\mathbf{Exp}_{\mathcal{G}A, \mathcal{A}}^{\text{wk-PR-b}}(\lambda)$ is the experiment described in figure 1.

Informally, a group action $(G, S, \star)$ is $(D_G, D_S)$-weakly pseudorandom if there is no PPT adversary that can distinguish tuples of the form $(s_i, g \star s_i)$ from $(s_i, u_i)$ where $g \leftarrow D_G$ and each $s_i, u_i \leftarrow D_S$. If both distributions are uniform, we omit them and we say that the group action is weakly pseudorandom.

$\mathbf{Exp}_{\mathcal{G}A, \mathcal{A}}^{\text{wk-PR-b}}(\lambda)$:

1. $(G, S, \star) \leftarrow \mathcal{G}A(\lambda)$

2. if $b=0$

3. $g \leftarrow D_G$

4. $\mathcal{O}$.Sample $\leftarrow \pi_g^\$$

5. else $(b=1)$

6. $\pi \stackrel{\$}{\leftarrow} \mathfrak{S}(S)$

7. $\mathcal{O}$.Sample $\leftarrow \pi^\$$

8. $b' \leftarrow \mathcal{A}^{\mathcal{O}.Sample}(1^\lambda, (G, S, \star))$

9. if $b'=b$

10. return 1

11. else

12. return 0

**Fig. 1.** Weak pseudorandom group action experiment. Recall that $D_G$ and $D_S$ are distributions on $G$ and $S$ respectively. For a permutation $f \in \mathfrak{S}(S)$, we use $f^\$$ to denote the randomized oracle that samples $s \leftarrow D_S$ and outputs $(s, f(s))$.

## 2.2 Updatable Encryption

In this section, we describe the syntax and security definitions of UE, we follow the presentations of [28,9,24,22]. An UE scheme operates in epochs, where an epoch is an index incremented with each key update. Let $n+1$ be the maximum number of epochs (this is only for proof purposes).
**Definition 4.** An updatable encryption scheme UE for message space $\mathcal{M}$ consists of a tuple of PPT algorithms (UE.setup, UE.KeyGen, UE.TokenGen, UE.Enc, UE.Dec, UE.Upd) where:

* UE.setup(1^λ) → pp: The setup algorithm takes as input the security parameter and outputs a public parameter pp.

* UE.KeyGen(pp) → k_e: The key generation algorithm takes as input the public parameter pp and outputs an epoch key k_e.

* UE.Enc(k, m) → c: The encryption algorithm takes as input an epoch key k and a message m and outputs a ciphertext c.

* UE.Dec(k, c) → m: The encryption algorithm takes as input an epoch key k and a ciphertext c and outputs a message m or ⊥.

* UE.TokenGen(k_e, k_{e+1}) → Δ_{e+1}: The token generation algorithm takes as input two keys of consecutive epochs e and e + 1 and outputs a token Δ_{e+1}.

* UE.Upd(Δ_{e+1}, c_e) → c_{e+1}: The update algorithm takes as input a token Δ_{e+1} and a ciphertext c_e and outputs a ciphertext c_{e+1}.

**Definition 5 (Correctness).** For any $m \in \mathcal{M}$, for $0 \le e_1 \le e_2 \le n+1$, it holds that $\Pr[UE.Dec(k_{e_2}, c_{e_2}) \ne m] \le \text{negl}(\lambda)$, where pp $\leftarrow$ UE.setup(1^λ), $k_{e_1}, \dots, k_{e_2} \leftarrow$ UE.KeyGen(pp), $c_{e_1} \leftarrow$ UE.Enc($k_{e_1}, m$), and $\Delta_{i+1} \leftarrow$ UE.TokenGen($k_i, k_{i+1}$), $c_{i+1} \leftarrow$ UE.Upd($\Delta_{i+1}, c_i$) for $i \in [e_1, e_2 - 1]$.

*Security definitions.* In all of our UE schemes, the Upd algorithm is deterministic. Thus, we only consider security definitions in the deterministic update setting.

**Definition 6 (detIND-UE-atk [9]).** Let UE = (UE.setup, UE.KeyGen, UE.TokenGen, UE.Enc, UE.Dec, UE.Upd) be an updatable encryption scheme. The detIND-UE-atk advantage, for atk $\in$ {CPA, CCA} of an adversary A against UE is given by

$$ \mathbf{Adv}_{\text{UE},\mathcal{A}}^{\text{detIND-UE-atk}}(\lambda) := \left| \Pr[\mathbf{Exp}_{\text{UE},\mathcal{A}}^{\text{detIND-UE-atk-0}} = 1] - \Pr[\mathbf{Exp}_{\text{UE},\mathcal{A}}^{\text{detIND-UE-atk-1}} = 1] \right| $$

where the confidentiality experiment $\mathbf{Exp}_{\text{UE},\mathcal{A}}^{\text{detIND-UE-atk-b}}$ is given in fig. 2.

*Leakage sets.* We follow the bookkeeping technique [24,9] to maintain the epoch leakage sets.

* C: List of epochs in which the adversary learned an updated version of the challenge ciphertext (from O.Chall or O.UpdC̃).

* K: List of epochs in which the adversary corrupted the encryption key.

* T: List of epochs in which the adversary corrupted the update token.

The adversary can also learn the values of ciphertexts and their updates.

* L: List of non-challenge ciphertexts (from O.Enc or O.Upd) with entries of the form (c, C, e), where c is a counter incremented with each O.Enc query.

* L̃: List of updated versions of challenge ciphertext (created by O.Next and returned by O.UpdC̃), with entries of the form (C̃, e).
$$ \mathbf{Exp}_{\text{UE}, \mathcal{A}}^{\text{detIND-UE-atk-b}}(\lambda) $$

1. do UESetup(1^λ)

2. ors ← O({Enc, Upd, Next, Corr}

3. if atk = CCA

4. ors ← ors ∪ {O.Dec}

5. (M, C) ← A^{ors}(1^λ)

6. phase ← 1, e ← e

7. $\tilde{C}_e \leftarrow O.Chall(M, \bar{C})$

8. $b' \leftarrow A^{\text{ors, Upd}\tilde{C}}(\tilde{C}_e)$

9. if $\mathcal{K}^* \cap C^* \neq \emptyset$ or $\mathcal{I}^* \cap C^* \neq \emptyset$

10. twf ← 1

11. if twf = 1

12. $b' \leftarrow \$\{0, 1\}$

13. return b'

<figure><img src="image_2.png" /><figcaption>**Fig. 3.** Oracles in security games for UE with deterministic updates. Computing the leakage sets is discussed in sec. 2.2</figcaption></figure>
*Trivial wins via keys and ciphertexts.* We consider the extended epoch leakage sets $C^*$, $K^*$ and $T^*$ inferred from $C$, $K$ and $T$. These extended sets are used to identify trivial wins, i.e., if $C^* \cap K^* \neq \emptyset$, then there exists an epoch in which the adversary knows the epoch key and a valid update of the challenge ciphertext. The challenger computes these sets once the adversary has finished running. We give their precise descriptions in Appendix B.

*Trivial wins via direct updates.* Define $\mathcal{I}$ as the set of epochs in which the adversary learned an updated version of the ciphertext given as challenge input $(\tilde{C})$. Furthermore, define $\mathcal{I}^*$ to be the extended set in which the adversary has inferred information via token corruption. Since, in our case, the algorithm Upd is deterministic, an updated ciphertext is uniquely determined by a token and a ciphertext. Thus, the adversary trivially wins if $\mathcal{I}^* \cap C^* \neq \emptyset$. Indeed, there exists an epoch in which the adversary knows the updated ciphertext of the challenge input $\tilde{C}$ and a valid challenge-equal ciphertext. Comparing them allows the adversary to win the game.

In [9], $\mathcal{I}$ is computed by finding an entry in $\mathcal{L}$ that contains the challenge input $\tilde{C}$. Then, note the query identifier $c$ for that entry and scan $\mathcal{L}$ for other entries with this identifier $\mathcal{I} := \{e \in \{0, \dots, n\} \mid (c, \cdot, e) \in \mathcal{L}\}$. We show how to extend $\mathcal{I}$ into $\mathcal{I}^*$ in Appendix B.

## 2.3 Elliptic curves and isogenies

Let $K$ be a field. An elliptic curve over $K$ is a smooth projective curve of genus 1 with a distinguished base point defined over $K$. For our purpose, it is enough to consider elliptic curves as curves defined by an equation of the form $E: y^2 = x^3 + ax + b$. The set of points $E(K)$ is made of the solutions $(x, y)$ to the equation of the curve. A good generic reference on elliptic curves is the book from Silverman [34]. The set of points is a group for a law that we write $\oplus$. The scalar multiplication $[n]: E(K) \to E(K)$ is the operation $\oplus$ iterated $n$ times. We write $E[n]$ for the kernel of the morphism $[n]$.

An isogeny $\varphi: E_1 \to E_2$ is a non-constant morphism sending the identity of $E_1$ to that of $E_2$. The degree of an isogeny is its degree as a rational map. When the degree $\deg(\varphi) = d$ is coprime to $p$, the isogeny is necessarily separable. An isogeny induces a homomorphism of groups $E_1(K) \to E_2(K)$ and, if separable, the kernel of $\varphi$ is a group of order $d$. Such an isogeny is entirely described by its kernel, meaning that there is a one-to-one correspondence between separable isogenies (up to an isomorphism of the target curve) and finite subgroups of $E(\overline{K})$. An isogeny can be computed from its kernel $G$ using Vélu's formula [36], in this case we write $\varphi: E \to E/G$. The degree of $\varphi \circ \psi$ is equal to $\deg(\varphi)\deg(\psi)$. For any isogeny $\varphi: E_1 \to E_2$, there exists a unique dual isogeny $\tilde{\varphi}: E_2 \to E_1$, satisfying $\varphi \circ \tilde{\varphi} = [\deg(\varphi)]$, the multiplication-by-deg($\varphi$) map on $E_2$. Similarly $\tilde{\varphi} \circ \varphi$ is the multiplication-by-deg($\varphi$) map on $E_1$. An endomorphism of $E$ is an isogeny $\theta: E \to E$. The set of endomorphisms is a ring with addition and composition that we write $\mathrm{End}(E)$.

Let us take $K$, a finite field of characteristic $p$. Over $K$, a curve is said to be *supersingular* when $\mathrm{End}(E)$ is a maximal order inside the quaternion algebra
ramified at $p$ and $\infty$. The Frobenius morphism is defined as $\pi : (x, y) \to (x^p, y^p)$, it sends any curve $E : y^2 = x^3 + ax + b$ to $E^{(p)} : y^2 = x^3 + a^p x + b^p$. $\pi$ is the only isogeny of degree $p$ between any two supersingular curves.

# 3 UE from group action

We generalize the SHINE scheme of Boyd et al. [9] using the framework of cryptographic group actions of Alamati et al. [2].

## 3.1 Generalizing SHINE to group actions

First, we introduce the novel mappable EGA (MEGA) definition.

**Definition 7 (Mappable EGA).** Let $(G, S, \star)$ be an EGA. We say that $(G, S, \star)$ is a mappable EGA if there exists an efficient bijection $\pi : \{0, 1\}^N \to S$.

Let $\mathcal{G}A$ be a MEGA family and let $(G, S, \star)$ be $\mathcal{G}A(\lambda)$: a MEGA with bijection $\pi : \{0, 1\}^{m+v} \to S$, for integers $m$ and $v$. Let $\mathcal{M} := \{0, 1\}^m$ be the message space and $\mathcal{N} := \{0, 1\}^v$ be the nonce space.

We present our generalization of the SHINE scheme [9] to group actions, which we call GAINE for Group Action Ideal-cipher Nonce-based Encryption, in figure 4. We use group elements as keys and set elements as messages. Encryption, decryption and updates boil down to a group action computation. Ciphertexts are randomized by adding a random nonce as input to $\pi$. The group action used in the original proposal of Boyd et al. [9] is the action of the group $\mathbb{Z}_q^*$ on $S$ by exponentiation, where $S$ is a cyclic group of prime order $q$ in which the discrete logarithm problem is hard. The correctness of GAINE is proven in Appendix C, even for non-abelian group actions.

## 3.2 Security - GAINE is detIND-UE-CPA secure

In Theorem 1, we show that GAINE is detIND-UE-CPA in the ideal cipher model, if the group action is a weakly pseudorandom MEGA. The ideal cipher model, introduced by Shannon [33] and shown to be equivalent to the random oracle model by Coron et al. [14], gives all parties access to a permutation chosen randomly from all possible key permutations of appropriate length. The GAINE scheme acts on the outputs of the permutation with the epoch key to encrypt, so our reduction can “program” the transformation from permutation outputs to set elements.

**Theorem 1 (GAINE is detIND-UE-CPA).** Let GAINE be the UE scheme described in figure 4 for a MEGA family $\mathcal{G}A$. For any ideal cipher model adversary $\mathcal{A}$, there exists a reduction $\mathcal{B}$ such that

$$ \mathbf{Adv}_{\text{GAINE},\mathcal{A}}^{\text{detIND-UE-CPA}}(\lambda) \leq \mathcal{O}(1)(n+1)^3 \cdot \mathbf{Adv}_{\mathcal{G}A,\mathcal{B}}^{\text{wk-PR}}(\lambda) $$

We give a full proof of Theorem 1 in Appendix E. We show how to make GAINE CCA-secure in Appendix F.
<figure><img src="image_3.png" /><figcaption>Fig. 4. GAINE: our generalization of the SHINE scheme using group actions.</figcaption></figure>

## 3.3 Post-quantum instantiations of GAINE

Potential candidates for instantiating GAINE include the non-abelian group actions of the general linear group on the set of alternating trilinear forms introduced by Tang et al. [35] and on the set of $k$-tensors, for $k \ge 3$, by Ji et al. [21]. These two actions act on a finite vector space $V \simeq \mathbb{F}^n$ where $\mathbb{F}$ is a finite field and $n$ an integer. This implies that these two actions are mappable. Unfortunately, these two actions are also linear, meaning that the map $f_g : s \mapsto g \star s$ is a linear transformation of $V$. Given enough samples of the form $(s_i, g \star s_i)$ for a fixed $g$, one can compute $g \star s$ for any $s \in V$. This means that this action is not weak pseudorandom if the adversary gains access to too many samples of the weak pseudorandom experiment of Fig. 1. Since our security proof for GAINE uses one such sample per ciphertext, we can only use these two group actions to instantiate GAINE when there are few ciphertexts, which is unpractical.

## 4 UE from Triple Orbital Group Action

Below, we present a new abstract algebraic structure that we call Triple Orbital Group Action (TOGA). The formulation of this framework is in fact motivated by the fact that we cannot instantiate GAINE with the most-studied post-quantum group action based on isogenies because it is notoriously hard [8] to hash into the set of supersingular elliptic curves.

Let us start with a quick overview. A TOGA is made of three group actions, each with a distinct role. The main group action, that we write $(A, S, \star_A)$, is our starting point. The main ingredient to get a TOGA from the simple group action $\star_A$ is a congruence relation $\sim_A$. This relation allows us to derive a second group action $(A/\sim_A, S/\sim_S, \star_G)$, called the induced group action, of the quotient
group on the quotient set (see Definition 8 for $\sim_S$). Of course, this induced group action is not mappable as we would not need a TOGA to build UE in this case. This time, we consider plaintexts as group elements of a third group action $(H, S, \star_H)$. For decryption to be possible, we assume that this action is efficiently invertible. We want $\star_H$ to commute with $\star_A$ but also that the orbits of $\star_H$ are exactly the classes of equivalences of $S/\sim_S$, which is what we call to be orbital. For a visualization of the interaction between the three group actions of a TOGA, see Fig. 8 in appendix. The algebraic structure TOGA is explained in Section 4.1, while the computational model is given in Section 4.2. In Section 4.3, we show how to build UE from a TOGA.

## 4.1 The algebraic structure

Let us assume that we have a group action $(A, S, \star_A)$ for an abelian multiplicative group $A$ and a set $S$. We write $1_A$ for the neutral element of $A$. If there exists a congruence relation $\sim_A$ on $A$ (we recall that a congruence on a set with an intern law is an equivalence relation compatible with the law, i.e., such that if $a_1 \sim_A a_2$ and $b_1 \sim_A b_2$ we have $a_1 b_1 \sim_A a_2 b_2$), then we get that $G = A/\sim_A$ is an abelian group for the law naturally derived from the multiplication in $A$.

**Definition 8.** Let $A$ be an abelian group and let $\sim_A$ be a congruence relation on $A$. Let $S$ be a set and let $\star_A$ be a group action of $A$ on $S$. The relation $\sim_S$ induced by $\sim_A$ and $\star_A$ is

$$s_1 \sim_S s_2 \iff \exists a_1, a_2 \in A \text{ with } a_1 \sim_A a_2 \text{ such that } a_1 \star_A s_1 = a_2 \star_A s_2$$

**Proposition 1.** Keeping the notations of Definition 8, we have that $\sim_S$ is an equivalence relation and $\star_A$ induces a group action $\star_G$ of $G := A/\sim_A$ on $T := S/\sim_S$.

*Proof.* The relation $\sim_S$ is clearly reflexive and symmetric. For transitivity let us take $s_1, s_2, s_3 \in S$ with $s_1 \sim_S s_2$ and $s_2 \sim_S s_3$, we have $a_1 \star_A s_1 = a_2 \star_A s_2$ and $b_2 \star_A s_2 = b_3 \star_A s_3$, thus $a_1 b_2 \star_A s_1 = a_2 b_3 \star_A s_3$ and $a_1 b_2 \sim_A a_2 b_3$ since $\sim_A$ is a congruence. Let us write $G = A/\sim_A$ and $T = S/\sim_S$. First, we need to verify that the operation $\star_A$ is well-defined on the quotients. To see that, we need to verify that $a_1 \star_A s_1 \sim_S a_2 \star_A s_2$ when $a_1 \sim_A a_2$ and $s_1 \sim_S s_2$. This is true because we have $b_1 \sim_A b_2$ such that $b_1 \star_A s_1 = b_2 \star_A s_2$, and so $(a_2 b_1) \star_A (a_1 \star_A s_1) = (a_1 b_2) \star_A (a_2 \star_A s_2)$ with $a_2 b_1 \sim_A a_1 b_2$ because $\sim_A$ is a congruence. Then, we need to show that $\star_A : G \times T \to T$ verifies the usual group action properties from Definition 1. First, let us take $a \sim_A 1_A$. We must have $a \star_A s \sim_S s$ for any $s \in S$, which is clearly the case. Then, for any $a_1, a_2 \in A$, $s \in S$, we have the equality $(a_1 a_2) \star_A s = a_1 \star_A (a_2 \star_A s)$ and this equality remains true when considering the quotients $G, T$.

**Definition 9.** Given $A, S, \star_A, \sim_A$ as in Proposition 1, the group action $\star_G$ of $A/\sim_A$ on $S/\sim_S$ is called the group action induced by $A, \star_A, \sim_A$ (or induced by $A$ when it is clear from the context) and $(A, S, \star_A)$ is called the main group action.
We obtain a third group action (hence the name of triple group action) by looking at the classes of equivalence of $S$. We want to consider these classes as the orbits of a third group action $\star_H : H \times S \to S$ for another abelian group $H$. By that we mean that, for any $s \in S$ and $h \in H$, we have $s \sim_S h \star_H s$ and that, for all $s' \sim_S s$, there exists $h \in H$ with $s' = h \star_H s$. Additionally, we need the group action $(H, S, \star_H)$ to be free because we will need to invert $\star_H$. When these constraints are respected we qualify the group action $(H, S, \star_H)$ to be orbital.

Finally, we want that $\star_A$ and $\star_H$ commute and that for any $a_1, a_2 \in A$ such that $a_1 a_2 \sim_A 1_A$, there exists a unique element $h(a_1, a_2) \in H$ such that $(a_1 a_2) \star_A s = h(a_1, a_2) \star_H s$ for any $s \in S$. With Proposition 2, we give a useful reformulation that will prove useful for the correctness of our scheme.

**Proposition 2.** For any $a, b \in A$ with $a \sim_A b$, we have $a \star_A s = (h(a, c)h(b, c)^{-1}) \star_H (b \star_A s)$ for any $c \in A$ with $ac \sim_A 1_A$ and $s \in S$.

*Proof.* We have $h(a, c) \star_H (b \star_A s) = (ac) \star_A (b \star_A s) = (abc) \star_A s = (bc) \star_A (a \star_A s) = h(b, c) \star_H (a \star_A s)$.

**Definition 10 (TOGA).** When $A, H, S, \star_A, \sim_A, \star_H$ satisfy all the above properties we say that we have a Triple Orbital Group Action (TOGA).

*Remark 1.* Note that $A$ being a group is not really necessary for the UE scheme that we will introduce below. In fact, we only need that $A$ is a monoid and that the quotient $A/\sim_A$ is a group. We only assumed that $A$ is a group for simplicity.

## 4.2 Computational model

As for group actions, we define an ETOGA as an Effective TOGA:

**Definition 11 (ETOGA).** A TOGA $A, H, S, \star_A, \sim_A, \star_H$ is effective if:

1. The group action $(H, S, \star_H)$ is an Effective and Easy Group Action (EEGA):

(a) The group action $(H, S, \star_H)$ is a free EGA.

(b) There is a PPT inversion algorithm $\text{Invert}_H : S^2 \to \{\perp\} \cup H$ taking two elements $s_1, s_2$ and that outputs either $\perp$ when $s_1 \not\sim_S s_2$ or the element $h \in H$ such that $s_1 = h \star_H s_2$.

2. There exists a finite subset $A' \subset A$ such that:

(a) The class of equivalence of $A'$ form a generating set of $G$, i.e., $G = A'/\sim_A$.

(b) There is a PPT algorithm to compute $a' \star_A s$ for any $s \in S$ and $a' \in A'$.

(c) There exists a PPT algorithm $\text{Reduce}_A : A \to A'$ that takes an element $a \in A$ and outputs $a' \sim_A a$.

(d) There exists a PPT algorithm to sample from $A'$ in a distribution statistically close to the uniform distribution, we write $a' \stackrel{\$}{\leftarrow} A'$ for elements sampled in that manner.

(e) The distribution $D_G$ that samples $a' \stackrel{\$}{\leftarrow} A'$ and returns the class of $\text{Reduce}_A(a')$ in $G$ is statistically close to the uniform distribution.
3. There exists a deterministic PPT algorithm Reduce$_S$ to compute a canonical representative for equivalence classes in $S/\sim_S$.

**Remark 2.** Note that the Reduce$_A$ algorithm may or may not be deterministic. For efficiency, it is interesting to try to select the element $a'$ in the class of $a$ that minimizes the computation cost of $a' \star_A s$ for any $s \in S$.

Note that when $a_1a_2 \sim 1_A$, we have $h(a_1, a_2) = \text{Invert}_H((a_1a_2) \star_A s, s)$ for any $s \in S$. Thus, we can define a PPT algorithm to compute $h(a_1, a_2)$ from $\text{Invert}_H$. We abuse notations and write $h$ for this algorithm.

Since the function Reduce$_S$ is deterministic, we can abuse notations and assimilate $T = S/\sim_S$ and Reduce$_S(S)$ by identifying the elements of $T$ to their canonical representative in $S$ through Reduce$_S$. Using this, we sometimes apply the action $\star_A$ on the elements of $T$ (it suffices to compose $\star_A$ with Reduce$_S$ to obtain the canonical representative afterward).

## 4.3 The updatable encryption scheme

Let TOGA be an ETOGA family and let $(A, H, S, \star_A, \sim_A, \star_H)$ be TOGA$(1^\lambda)$ for some $\lambda$. We fix a starting element $s_0 \in S$, and we also assume the existence of an invertible map $\psi: M \to H$ where $M$ is the space of the messages. We will use the function $\psi$ to send the messages in the group $H$ before encrypting them with $\star_H$. Then, decryption will rely on $\text{Invert}_H$. This operation is efficient by definition of an ETOGA. This principle basically solves the problem of needing our group action $\star_A$ to be mappable. The rest of our scheme follows the framework of GAINE with keys being elements of $A \times H$ and updates being obtained by applying $\star_A$ and $\star_H$. The security relies on the fact that the main group action $(A, S, \star_A)$ is weakly pseudorandom. Our UE scheme TOGA-UE is given in Fig. 5.

**Proposition 3 (Correctness of updates).** Let $k_e, k_{e+1} = (a_e, h_e), (a_{e+1}, h_{e+1})$ be two keys and $C_e = h_e \star_H (a_e \star_A s)$ for some $s \in S$. If $\Delta_{e+1} = \text{TokenGen}(k_e, k_{e+1})$, then $\text{Upd}(\Delta_{e+1}, C_e) = h_{e+1} \star_H (a_{e+1} \star_A s)$.

*Proof.* We reuse the notation of TokenGen, we have for $c_e = \text{Reduce}_A(a_e^{-1}a_{e+1})$. Since $c_e \sim_A a_{e+1}a_e^{-1}$, we have that $c_e \star_A (a_e \star_A s') = (h(c_e, c_e^{-1})h(a_{e+1}a_e^{-1}, c_e^{-1})^{-1}) \star_H ((a_{e+1}a_e^{-1}a_e) \star_A s')$ by Proposition 2. The proof is completed by the fact that $(a_{e+1}a_e^{-1}a_e) \star_A s' = a_{e+1} \star_A s'$ and $h(c_e, c_e^{-1}) = 1_H$.

**Proposition 4 (Correctness).** The TOGA-UE scheme is correct.

Proposition 4 follows from Proposition 3.

*Proof.* Let $\mathbf{e}_1 \le \mathbf{e}_2 \le n+1$ be two epochs and let us consider a ciphertext $c_{\mathbf{e}_2}$ updated through the successive tokens $\Delta_{i+1}$ for $i \in [\mathbf{e}_1, \mathbf{e}_2 - 1]$ from an initial ciphertext $c_{\mathbf{e}_1}$ that is the encryption of a message $m$ under the key $k_{\mathbf{e}_1}$ as in Definition 5. Each key $k_i$ can be decomposed as $a_i, h_i \in A \times H$. By definition of $c_{\mathbf{e}_1} = \text{Enc}(k_{\mathbf{e}_1}, m)$, we have $c_{\mathbf{e}_1} = (h_{\mathbf{e}_1} \psi(m)) \star_H a_{\mathbf{e}_1} \star_A \text{Reduce}_S(s_1)$ for some $s_1 \in S$. By applying Proposition 3 on $s = \psi(m) \star_H \text{Reduce}_S(s_1)$, we have that
<figure><img src="image_4.png" /><figcaption>Fig. 5. TOGA-UE: UE from ETOGA.</figcaption></figure>

$c_{e_2} = h_{e_2} \psi(m) \star_A a_{e_2} \star_A \text{Reduce}_S(s_1)$ since $\star_A$ and $\star_H$ commute. Then, let us take any $b_{e_2} \in A'$ such that $a_{e_2} b_{e_2} \sim_A 1_A$. By definition of $h$ we know that $(b_{e_2} a_{e_2}) \star_A x = h(b_{e_2}, a_{e_2}) \star_H x$ for any $x \in S$. Thus, $s' = (h_{e_2} h(b_{e_2}, a_{e_2}))^{-1} \star_H b_{e_2} \star_A c_{e_2} = \psi(M) \star_H \text{Reduce}_S(s_1)$. Then, since the orbits of $\star_H$ are exactly the equivalence classes of $S$, we have $s' \sim_S s_1$ and so $\text{Reduce}_S(s') = \text{Reduce}_S(s_1)$. Thus, when we compute $\text{Invert}_H(s', \text{Reduce}_S(s'))$ we obtain $\psi(m)$ and the message is recovered by applying $\psi^{-1}$.

## 4.4 Security - TOGA-UE is detIND-UE-CPA secure

Let $A, H, S, \star_A, \sim_A, \star_H$ be an ETOGA, fix $s_0 \in S$ and let $(A, S, \star_A)$ be the main group action of $A$ on $S$. In Theorem 2, we show that our UE scheme TOGA-UE (described in Fig. 5) is detIND-UE-CPA secure if the group action $(A, S, \star_A)$ is $(D_A, D_S)$-weakly pseudorandom where $D_S$ is the distribution that samples $a \leftarrow A'$ and returns $s := \text{Reduce}_S(a \star_A s_0)$ and $D_A$ is the distribution that samples $a \leftarrow A'$ and returns $\text{Reduce}_A(a)$.

**Theorem 2 (TOGA-UE is detIND-UE-CPA).** Let TOGA-UE be the UE scheme described in figure 5 for an ETOGA family $\mathcal{TOGA}$. We define a group action family $\mathcal{GA}$, where $\mathcal{GA}(1^\lambda)$ is $(A, S, \star_A)$, the main group action of $\mathcal{TOGA}(1^\lambda)$ (as in Definition 9). For any adversary $\mathcal{A}$, there exists a reduction $\mathcal{B}$ such that

$$ \mathbf{Adv}_{\text{TOGA-UE}, \mathcal{A}}^{\text{detIND-UE-CPA}}(\lambda) \le \mathcal{O}(1)(n+1)^3 \cdot \mathbf{Adv}_{\mathcal{G}, \mathcal{B}}^{\text{wk-PR}}(\lambda) $$
*Proof.* The proof uses the same hybrid argument as the one of Theorem 1, thus we only point out the differences between both proofs. Contrary to the proof of Theorem 1, we do not need to use the ideal cipher model. Indeed, in TOGA-UE, randomization of ciphertexts is not done through the permutation $\psi$. Thus, we do not need to "program" $\psi$ to get consistent randomness throughout our reduction. Our reduction $\mathcal{B}$ is given in Fig. 6. It uses the following notations. Given a ciphertext $C_e$ and a token $\Delta_e$, we can downgrade $C_e$ to epoch $e-1$ like so:

1. $(c, h) \leftarrow \Delta_e$

2. $b \leftarrow \text{Reduce}_A(c^{-1})$

3. $h' \leftarrow h(b, c)$

4. $C_{e-1} \leftarrow (hh')^{-1} \star_H (b \star_A C_e)$

5. **return** $C_{e-1}$

For readability, we will use the (abuse of) notation $\Delta_e^{-1} \star C_e$ to denote this downgrade. Similarly, if $\Delta_e = (c, h)$, we will use the notation $\Delta_e \star C_{e-1}$ to denote the update $h \star_H (c \star_A C_{e-1})$.

The reduction $\mathcal{B}$ starts by receiving a group action $(A, S, \star_A)$ and an oracle $\mathcal{O}.Sample$ that returns either tuples of the form $(s_i, a \star_A s_i)$ or $(s_i, t_i)$ where $a \leftarrow D_A$ and $s_i, t_i \leftarrow D_S$. We use the same hybrid argument over insulated regions as in Theorem 1. $\mathcal{B}$ will use the tuples of $\mathcal{O}.Sample$ to perfectly simulate the detIND-UE-CPA experiment for TOGA-UE when those tuples are of the form $(s_i, a \star_A s_i)$. Thus, if we know an efficient adversary $\mathcal{A}$ against the detIND-UE-CPA security of TOGA-UE, using the hybrid argument of Theorem 1, $\mathcal{B}$ can use $\mathcal{A}$ to break the weak pseudorandomness of $(A, S, \star_A)$.

In TOGA-UE, a ciphertext is of the form $C_e := h_e \star_H (a_e \star_A r)$ with $k_e := (a_e, h_e)$, where $a_e \leftarrow D_A$, $h_e \stackrel{\$}{\leftarrow} H$ and $r \leftarrow D_S$ is the randomness used during the first encryption. Reduction $\mathcal{B}$ will try to embed the $\mathcal{O}.Sample$ tuples in the $i$-th insulated region $[fwl_i, fwr_i]$. If $(r, s) \leftarrow \mathcal{O}.Sample()$, $\mathcal{B}$ uses $r$ as randomness for new ciphertexts. When updating ciphertext $C_{fwl_i-1} := h_{fwl_i-1} \star_H (a_{fwl_i-1} \star_A r)$ to epoch $fwl_i$, $\mathcal{B}$ sets $C_{fwl_i} := h_{fwl_i} \star_H s$ where $h_{fwl_i}$ is simulated by $\mathcal{B}$. If $(r, s)$ is of the form $(r, a \star_A r)$, $\mathcal{B}$ has embedded $a$ into $k_{fwl_i} := (a, h_{fwl_i})$ and the randomness of the ciphertext stays consistent because of Proposition 3. Else, if $(r, s)$ is a tuple of random elements of $S$, the ciphertexts inside the $i$-th insulated region are all random (there is no consistent key or randomness linking them).

Recall that a token $\Delta_{e+1} := (c_e, hh_{e+1}h_e^{-1})$ where $h_e, h_{e+1}$ are part of the epoch keys $k_e$ and $k_{e+1}$ and $c_e, h$ are computed by Upd using those keys. When both keys are unknown (like in the $i$-th insulated region), $c_e$ is uniformly distributed in $G$ by Definition 11 item 2e. Recall that $h \in H$ is useful for the correction of updates (see Proposition 3) and that it is not independent of $c_e$. However, $h_e$ and $h_{e+1}$ are sampled uniformly in $H$ and are not used in the computations of $c_e$ and $h$. Since $h_e$ and $h_{e+1}$ are unknown to the adversary in the $i$-th insulated region, $hh_{e+1}h_e^{-1}$ is uniformly distributed in $H$ and reduction $\mathcal{B}$ can perfectly simulate tokens inside the $i$-th insulated region.
Reduction $\mathcal{B}$ playing

$\mathbf{Exp}_{\mathcal{G}, \mathcal{A}, \mathcal{B}}^{\text{wk-PR-b}^*}(\lambda)$

1. receive $(A, S, \star_A)$ and $\mathcal{O}.\text{Sample}$

2. do Setup$(1^\lambda)$

3. $\bar{M}, \bar{C} \leftarrow \mathcal{A}^{\text{ors}}(\lambda)$

4. phase $\leftarrow 1$

5. $\tilde{C}_e \leftarrow \mathcal{O}.\text{Chall}(\bar{M}, \bar{C})$

6. $b' \leftarrow \mathcal{A}^{\text{ors}, \mathcal{O}.\text{Upd}\tilde{\mathcal{C}}}(\tilde{C}_e)$

7. twf $\leftarrow 1$ if

8. $\mathcal{C}^* \cap \mathcal{K}^* \neq \emptyset$ or

9. $\mathcal{I}^* \cap \mathcal{C}^* \neq \emptyset$

10. if ABORT occurred or twf = 1

11. $b' \stackrel{\$}{\leftarrow} \{0, 1\}$

12. return $b'$

13. if $(i, \text{fwl}_i, \text{fwr}_i) \notin \mathcal{F}W$

14. $b' \stackrel{\$}{\leftarrow} \{0, 1\}$

15. return $b'$

16. if $b' = b$

17. return 0

18. else

19. return 1

Setup$(1^\lambda)$

1. $b \stackrel{\$}{\leftarrow} \{0, 1\}$

2. pp $\leftarrow$ TOGA-UESetup$(1^\lambda)$

3. $k_0 \leftarrow$ TOGA-UE.KeyGen(pp)

4. $\Delta_0 \leftarrow \bot$

5. e, c, phase, twf $\leftarrow 0$

6. $\mathcal{L}, \tilde{\mathcal{L}}, \mathcal{C}, \mathcal{K}, \mathcal{T} \leftarrow \emptyset$

7. $\text{fwl}_i, \text{fwr}_i \stackrel{\$}{\leftarrow} \{0, \dots, n\}$

8. for $j \in \{0, \dots, \text{fwl}_i - 1\} \cup \{\text{fwr}_i + 1, \dots, n\}$ do

9. $a_j \leftarrow \mathcal{D}_A, h_j \stackrel{\$}{\leftarrow}$ H; $k_j \leftarrow (a_j, h_j)$

10. $\Delta_j \leftarrow$ TOGA-UE. TokenGen$(k_j, k_{j+1})^{\bowtie}$

11. for $j \in \{\text{fwl}_i + 1, \dots, \text{fwr}_i\}$ do

12. $c_j \leftarrow \mathcal{D}_A, h_j \stackrel{\$}{\leftarrow}$ H; $\Delta_j \leftarrow (c_j, h_j)$

13. $h_{\text{fwl}_i} \stackrel{\$}{\leftarrow} H$

$\mathcal{O}.\text{Enc}(M)$

1. $c \leftarrow c + 1$

2. $(\text{inf}_1, \text{inf}_2) \leftarrow \mathcal{O}.\text{Sample}()$

3. if $e \in \{0, \text{fwl}_i - 1\} \cup \{\text{fwr}_i + 1, \dots, n\}$

4. $(a_e, h_e) \leftarrow k_e$

5. $C_e \leftarrow (\psi(M)h_e) \star_H \{a_e \star_A \text{inf}_1\}$

6. else

7. $C_{\text{fwl}_i} \leftarrow (\psi(M)h_{\text{fwl}_i}) \star_H \text{inf}_2$

8. for $j \in \{\text{fwl}_i + 1, \dots, e\}$ do

9. $C_j \leftarrow \Delta_j \star C_{j-1}$

10. $\text{inf} \leftarrow (\text{inf}_1, \text{inf}_2, M)$

11. $\mathcal{L} \leftarrow \mathcal{L} \cup \{(c, C_e, e; \text{inf})\}$

12. return $C_e$

$\mathcal{O}.\text{Next}$

1. $e \leftarrow e + 1$

$\mathcal{O}.\text{Upd}(C_{e-1})$

1. if $(c, C_{e-1}, e-1; \text{inf}) \notin \mathcal{L}$

2. return $\bot$

3. if $e \in \{1, \dots, \text{fwl}_i - 1\} \cup \{\text{fwr}_i + 1, \dots, n\}$

4. $(\text{inf}_1, \text{inf}_2, M) \leftarrow \text{inf}$

5. $(a_e, h_e) \leftarrow k_e$

6. $C_e \leftarrow (\psi(M)h_e) \star_H \{a_e \star_A \text{inf}_1\}$

7. else

8. $(\text{inf}_1, \text{inf}_2, M) \leftarrow \text{inf}$

9. $C_{\text{fwl}_i} \leftarrow (\psi(M)h_{\text{fwl}_i}) \star_H \text{inf}_2$

10. for $j \in \{\text{fwl}_i + 1, \dots, e\}$ do

11. $C_j \leftarrow \Delta_j \star C_{j-1}$

12. $\mathcal{L} \leftarrow \mathcal{L} \cup \{(c, C_e, e; \text{inf})\}$

13. return $C_e$

$\mathcal{O}.\text{Corr}(\text{inp}, \hat{e})$

1. do

Check inp, $\hat{e}$; e; $\text{fwl}_i$, $\text{fwr}_i$)

2. if $\text{inp} = \text{key}$

3. $\mathcal{K} \leftarrow \mathcal{K} \cup \{\hat{e}\}$

4. return $k_e$

5. if $\text{inp} = \text{token}$

6. $\mathcal{T} \leftarrow \mathcal{T} \cup \{\hat{e}\}$

7. return $\Delta_{\hat{e}}$

$\mathcal{O}.\text{Chall}(\bar{M}, \bar{C})$

1. if $(c, \bar{C}, \bar{e} - 1; \text{inf}) \notin \mathcal{L}$

2. return ABORT

3. if $b = 0$

4. $(s, t) \leftarrow \mathcal{O}.\text{Sample}()$

5. $r \leftarrow s$

6. $\tilde{C}_{\text{fwl}_i} \leftarrow (\psi(\bar{M})h_{\text{fwl}_i}) \star_H t$

7. else

8. $(\text{inf}_1, \text{inf}_2, M) \leftarrow \text{inf}$

9. $r \leftarrow \mathcal{D}_S$

10. $\tilde{C}_{\text{fwl}_i} \leftarrow (\psi(M)h_{\text{fwl}_i}) \star_H \text{inf}_2$

11. for $j \in \{0, \dots, \text{fwl}_i - 1\}$ do

$\tilde{C}_j \leftarrow (\prod_{k=j}^1 \Delta_k)(\prod_{k=1}^{\tilde{e}-1} \Delta_k^{-1}) \star \tilde{C} \text{ //left}$

13. for $j \in \{\text{fwl}_i + 1, \dots, \text{fwr}_i\}$ do

14. $\tilde{C}_j \leftarrow \Delta_j \star \tilde{C}_{j-1}$

15. for $j \in \{\text{fwr}_i + 1, \dots, n\}$ do

16. $(a_j, h_j) \leftarrow k_j$

17. $\tilde{C}_j \leftarrow (\psi(\bar{M})h_j) \star_H (a_j \star_A r)$ //right

18. $\tilde{\mathcal{L}} \leftarrow \cup_{j=0}^n \{(\tilde{C}_j, j)\}$

19. return $\tilde{C}_e$

$\mathcal{O}.\text{Upd}\tilde{\mathcal{C}}$

1. $C \leftarrow C \cup \{e\}$

2. find $(\tilde{C}_e, e) \in \tilde{\mathcal{L}}$

3. return $\tilde{C}_e$

**Fig. 6.** Our reduction $\mathcal{B}$ for proof of th. 2 in hybrid $i$. inf encodes fixed programming information: it marks two set elements $(\text{inf}_1, \text{inf}_2)$ sampled with $\mathcal{O}.\text{Sample}$ and a plaintext $M$. $\text{inf}_1$ is the randomness used during encryption, $\text{inf}_2$ is used to compute the ciphertext value in epoch $\text{fwl}_i$ and $M$ is the plaintext. $\text{ors}$ refers to the set $\{\mathcal{O}.\text{Enc}, \mathcal{O}.\text{Next}, \mathcal{O}.\text{Upd}, \mathcal{O}.\text{Corr}\}$. $\bowtie$ indicates that $\Delta_0$ and $\Delta_{\text{fwr}_i+1}$ are skipped in the computation.
Because of the correctness of updates in **TOGA-UE** (see Proposition 3) and of the observations above, when *O*.Sample returns tuples of the form $(s_i, a \star_A s_i)$, the reduction *B* perfectly simulates the environment of the adversary *A* and we get a similar result as the one of Theorem 1.

On the CCA security of TOGA-UE. Unlike GAINE, making TOGA-UE CCA se-
cure appears to be hard. Indeed, our construction has a pretty clear malleability
property: let $M, M'$ be two distinct messages, under the $\psi$ map we get two ele-
ments $h := \psi(M), h' := \psi(M')$. Then, for any encryption $c$ of the message $M$,
we compute $h'h^{-1}_{\star H} c$ to obtain a valid encryption of $M'$. We leave the problem
of making TOGA-UE CCA secure open for future work.

5 Instantiation from isogenies

The GAINE construction introduced in Section 3 requires a MEGA, i.e., that the underlying group action is mappable (which we showed was implying the group action to be hashable). Isogeny-based cryptography is one of the main provider of post-quantum cryptographic group action so it is natural to ask if we can instantiate GAINE from them. Unfortunately, it is notoriously hard to hash into the set of supersingular curves [8] and this implies that building a MEGA from isogenies is probably very hard. This fact is what motivated the introduction of our new TOGA framework to build UE. In fact, our UE scheme is inspired by the SIGAMAL encryption scheme from Moriya, Onuki and Takagi [26]. Instead of encrypting messages as curves (wich would require to hash into the set of supersingular curves), we propose to encrypt messages as scalars similarly to what is done in SIGAMAL. In that sense, the instantiation of our UE scheme with isogenies can be considered as an updatable version of SIGAMAL. More precisely, our main group action $\star_A$ will be the one of fractional ideals of quadratic orders on orientations of supersingular curves. Under the usual equivalence relation on ideals, the group action $\star_G$ induced by this group action is the standard group action of the class group on oriented supersingular curves used in isogeny-based cryptography [11,13,16]. To obtain the richer structure of TOGA as in Definition 10, we consider orientations on curves with a level $N$-structure, i.e., curves that are enriched with a point of order $N$. In that setting, the group $H$ is simply $\mathbb{Z}/N\mathbb{Z}^*$ and the action $\star_H$ is the scalar multiplication on the points of order $N$. For everything to be well-defined and behave as expected by our computational model, we must take $N$ as a smooth number split in the quadratic order.

5.1 A TOGA from isogenies.

We fix a prime $p$ and consider the supersingular elliptic curves in characteristic
$p$. In practice, they can always be defined over $\mathbb{F}_{p^2}$. We take a quadratic order
$\mathcal{D}$ of discriminant $\Delta$ and write $\mathcal{R}$ for the quadratic imaginary field $\mathcal{Q} \otimes \mathcal{D}$.
**Definition 12.** For any elliptic curve $E$, a $\mathfrak{R}$-orientation is a ring homomorphism $\iota : \mathfrak{R} \hookrightarrow \text{End}(E) \otimes \mathbb{Q}$. A $\mathfrak{R}$-orientation induces an $\mathfrak{D}$-orientation if $\iota(\mathfrak{D}) = \text{End}(E) \cap \iota(\mathfrak{R})$. In that case, the couple $(E, \iota)$ is called an $\mathfrak{D}$-oriented curve and $E$ is an $\mathfrak{D}$-orientable curve.

In what follows, we consider the elements of $S(p)/\pi$ rather than $S(p)$ because the Frobenius $\pi$ creates two orientations (one in $E$ and one in $E^{(p)}$) from each optimal embedding of $\mathfrak{D}$ in a quaternion maximal order of $B_{p,\infty}$. Note that this is not the convention taken in [29,37] where orientations are not considered up to Galois conjugacy.

**Definition 13.** $S_{\mathfrak{D}}(p)$ is the set of $\mathfrak{D}$-oriented curves $E, \iota$ up to isomorphisms and Galois conjugacy.

More concretely, we obtain an orientation $E, \iota$ by an endomorphism $\theta \in \text{End}(E)$ such that $\iota(\mathfrak{D}) = \mathbb{Z}[\theta]$. Note that $S_{\mathfrak{D}}(p)$ may be empty for some quadratic orders $\mathfrak{D}$ but it is also non-empty for an infinite number of order $\mathfrak{D}$ given any prime $p$.

*The group action of fractional ideals.* When we consider fractional $\mathfrak{D}$-ideal, we get an abelian group (for the multiplication operation). This group acts on the elements of $S_{\mathfrak{D}}(p)$ by an operation that we write $\star_A$. This action is computed concretely using isogenies. Given an integral ideal $\mathfrak{a}$ and $E, \iota \in S_{\mathfrak{D}}(p)$, we define the kernel of $\mathfrak{a}$ as $E[\mathfrak{a}] := \{P \in E[n(\mathfrak{a})] \mid \iota(\alpha)(P) = 0, \forall \alpha \in \mathfrak{a}\}$. The isogeny $\varphi_{\mathfrak{a}}^E : E \to E_{\mathfrak{a}}$ is simply the isogeny of kernel $E[\mathfrak{a}]$. Thus, we have $E_{\mathfrak{a}} = E/E[\mathfrak{a}]$ and $\iota_{\mathfrak{a}}(x) = \frac{1}{n(\mathfrak{a})}\varphi_{\mathfrak{a}}^E \circ \iota(x) \circ \hat{\varphi}_{\mathfrak{a}}^E$.

Fractional ideals can always be expressed as the multiplication of an integral ideal and a scalar in $\mathbb{Q}$. Thus, we will decompose the action of fractional ideals by applying first the action of the integral part as defined above, then by doing a scalar multiplication. We will explain how we propose to do this exactly a bit later when we introduce the set $S$.

Since our goal, in the end, is to get an ETOGA as defined in Section 4.2, we define the concrete group $A$ that we will use as a subgroup of the group of $\mathfrak{D}$-ideals. This restriction is motivated by efficiency of the computation of $\star_A$. Indeed, the cost of computing an isogeny of degree $D$ is in $O(\sqrt{D'})$ where $D'$ is the biggest factor of $D$ (see [5]). Thus, it is pointless to consider ideals that are multiples of prime ideals of big prime norm. This is why we fix an effective factor base of the $\mathfrak{D}$-ideals as a collection of ideals $\mathfrak{l}_1, \dots, \mathfrak{l}_n$ where each $\mathfrak{l}_i$ is an ideal of norm $\ell_i$ for a small prime $\ell_i$ that is split in $\mathfrak{D}$ (here, small is to be considered with respect to some complexity parameter $\lambda$). Note that any such ideal $\mathfrak{l}_i$ has a dual ideal, usually denoted by $\overline{\mathfrak{l}_i}$, such that $\mathfrak{D}\ell_i = \mathfrak{l}_i\overline{\mathfrak{l}_i}$. Then, we can define the inverse of $\mathfrak{l}_i$ as $\mathfrak{l}_i^{-1} := \overline{\mathfrak{l}_i}/\ell_i$. Thus, $\mathfrak{l}_i^e$ is defined for any $e \in \mathbb{Z}$. With these definitions, we set our group $A$ as $\langle \mathfrak{l}_1, \dots, \mathfrak{l}_n \rangle_{\mathbb{Z}} := \{\prod_{i=1}^n \mathfrak{l}_i^{e_i} \ell_i^{f_i} \mid (e_1, \dots, e_n) \in \mathbb{Z}^n, (f_1, \dots, f_n) \in \mathbb{Z}^n\}$, the subgroup generated by our collection of prime ideals and their inverse. The implicit bijection between $A$ and $\mathbb{Z}^{2n}$ given in our definition provides a way of representing the elements of $A$.
The standard cryptographic group action used in isogeny-based cryptography is obtained from our main group action of ideals by considering the equivalence relation ~A defined as a ~A b iff there exist non zero-elements a, b ∈ D with (a)a = (b)b. It can be verified that ~A is a congruence relation and so A/ ~A is an abelian group. If n is big enough A contains all equivalence classes of D-ideals. In that case, the group A/ ~A is called the class group of D and written Cl(D). By definition of S_D(p) (up to isomorphisms and Galois conjugacy), equivalent ideals act identically on the elements of S_D(p). Thus, the group action induced by ★_A on S_D(p) as in Definition 9 is the usual isogeny-based group action. Since we clearly have ℓa ~A a for any ℓ ∈ Q* and a ∈ A, we see that any ideal class of A/ ~A admits a representative of the form ∏_{i=1}^n l_i^{e_i} where (e_1, ..., e_n) ∈ Z^n. Thus, we can use elements of Z^n to represent the elements of G. More concretely, Φ : (e_1, ..., e_n) ↦→ ∏_{i=1}^n l_i^{e_i} yields an isomorphism between A/ ~A and Z^n/L where L is the lattice generated by the e ∈ Z^n such that Φ(e) ~A 1_A. The lattice L is usually called the lattice of relations of Cl(D) for the factor basis l_1, ..., l_n.

The orbital group action. We now introduce our third group action (written ★_H in Definition 10). To get this orbital group action, our idea is to use the group of points of the orientable elliptic curves. Let us take N a split integer in D coprime with all the l_i for 1 ≤ i ≤ n. We can consider elements of the form E, l, P where P ∈ E[N] has order N. The group of fractional ideals of norm coprime with N acts on this set in the following manner: let us consider the fractional ideal (a/b)a where a is an integral ideal, we have the action (a/b)a ★ (E, l, P) = E_a, l_a, [ac]φ_a^E(P) where c = b⁻¹ mod N. However, in this setting, it seems hard to get a group action ★_H as we desire. Indeed, equivalent ideals will send E, l, P on E_1, l_1, P_1 and E_2, l_2, P_2 where we have E_1, l_1 = E_2, l_2 but we cannot tell anything about the points P_1, P_2 apart from the fact that they are two points of order N. Fortunately, if we restrict the set of points of order N we consider, the situation becomes a lot simpler. For that, if we have D = Z[θ], it suffices to consider one eigenvalue of θ, i.e., one value ν such that ker(l(θ) − ν) ∩ E[N] is a cyclic subgroup of order N. Since N is split, we know there exists one such eigenvalue ν and if P ∈ ker(l(θ) − ν) ∩ E[N], we get that φ^E(a)(P) ∈ ker(l_a(θ) − ν) ∩ E_a[N]. Let us take

$$S = \{(E, l, P) \mid (E, l) \in S_D(p) \text{ and } \langle P \rangle = E[N] \cap \ker(l(\theta) - \nu)\} \quad (1)$$

With that choice of S, the image under the group action of two equivalent fractional ideals a_1, a_2 on E, l, P ∈ S will give E_1, l_1, P_1 and E_2, l_2, P_2 with P_1 and P_2 in the same subgroup, i.e., there exists μ ∈ H = Z/NZ* such that P_1 = μP_2. Moreover, it is easily verified that the scalar μ depends only on two ideals a_1, a_2 (and not on E, l and P) as it corresponds to the action of the endomorphism corresponding to a_1a_2 on the eigen-space of ν. This scalar μ is what we call h(a_1, a_2) in our definition of a TOGA.

In that setting, for any scalar h ∈ H, we define h ★_H (E, l, P) as (E, l, [h]P) and it can be verified that (A, H, S, ★_A, ~A, ★_H) is a TOGA.
## 5.2 Making the isogeny TOGA effective

To instantiate our protocol, we not only need a TOGA but an ETOGA as in Section 4.2. Below, we address the efficiency requirements. We try to stay generic in our approach and a more detailed example can be found in Section 5.3.

In fact, we are going to see that our proposed solution from isogeny is not exactly an ETOGA, but we can assume every operations to be practical assuming some (possibly-heavy) precomputation. In what follows, we discuss these limitations to understand what are the main obstacles.

The elements of $S$ and the canonical representation of equivalence classes. We need to verify that the set $S$ satisfies several properties. First, it needs to be finite which is our case (the cardinal is equal to $\varphi(N)h(\mathcal{D})$ where $\varphi$ is Euler's totient function). Regarding the existence of an origin $s_0$, it suffices to fix an element $s_0 \in S$ as the origin. There may be different ways of finding one, depending on the concrete $\mathcal{D}$ and $p$, but a generic algorithm to compute one was described in [16] (in the context of generating backdoor curves for the Séta encryption scheme). Regarding the unique representation of the elements of $S$, it suffices to use a canonical representation of a class of isomorphic curves (using the $j$-invariant for instance). Once the curve $E$ is fixed, we can deterministically derive a representation of the orientation $\iota$ and of any point $P$. The naive way of representing the point $P$ would be by giving its coordinates $x, y$ but we propose to use another way that is more compact in most cases. The idea is that given a basis $P_1, P_2$ of $E[N]$, any points $P \in E[N]$ is equal to $[a]P_1 + [b]P_2$ for some $a, b \in \mathbb{Z}/N\mathbb{Z}$. If the basis $P_1, P_2$ can be computed deterministically from $E$, the coefficients $a, b$ are enough to recover the point $P$ from the knowledge of $E$. This representation has size $2\log(N)$ which is usually a lot better than what we can expect with the naive method (that can be in $O(N\log(p))$ in the worst case). A deterministic algorithm to compute a basis of $E[N]$ from $N$ can be easily derived from a deterministic algorithm Point($E, N, i$) that takes an elliptic curve $E$ and two integers $i, N$ and outputs a point $P(i)$ of order $N$ in $E$ (the role of $i$ is simply to index the points). There are numerous examples of such algorithms in the literature (see [38,27,3,15,30] for instance) so we do not describe one in detail. This algorithm will be useful for Reduce$_S$ as well.

Membership testing for a given element $E, \iota, P$ in $S$ consists in: verifying that $E$ is supersingular, that $\iota$ is a correct orientation and that $P$ is in $\ker(\iota(\theta) - \nu)$ and has order $N$. The first check can always be performed in polynomial time if $p$ is in $\text{poly}(\lambda)$, because supersingular curves have a known order. The second check will really depend on the choice of $\mathcal{D}$ so it cannot be described generically but the idea is that we need to be able to verify the norm and trace of $\iota(\theta)$. For the third check, we simply need to be able to perform efficient operations on the $N$-torsion, so we need $E[N]$ to be defined over a field extension of degree polynomial in $p$. For the examples of CSIDH and SCALLOP given in Section 5.3 all these operations are efficient.

The last ingredient we need for $S$ is the Reduce$_S$ algorithm. Its goal is to determine a unique representative of the classes of $S$ for the equivalence relation $\sim_S$. We recall that these classes correspond to the orbits of the group action of
H. Thus, what we need concretely is an efficient way to compute a canonical
point $P_E$ of order $N$ in $E[N] \cap \ker(\iota(\theta) - \nu)$ from $E, \iota$. We will use the Point
algorithm for that. Let us write $\nu'$, the second eigenvalues of $\iota(\theta)$.
$\text{Reduce}_S(E, \iota, \cdot)$:

1. Compute $U = E[N] \cap \ker(\iota(\theta) - \nu)$ and $V = E[N] \cap \ker(\iota(\theta) - \nu')$.

2. Let $i=0$, Repeat the following:

(a) $P = \text{Point}(E, N, i)$.

(b) Compute the unique decomposition $P = P_U + P_V$ where $P_U \in U$ and $P_V \in V$.

(c) $i = i + 1$.

3. Until $P_V$ has order $N$.

4. Return $E, \iota, P_V$.

The unique decomposition $P = P_U + P_V$ can be computed efficiently because
the discrete logarithm problem is easy in $E[N]$.

Making $(H, S, \star_H)$ into an EEGA. First, note that it is easily verified that the
group $H = \mathbb{Z}/N\mathbb{Z}^*$ is meeting all the requirements in terms of membership and
equality testing, sampling and operations. Finally, the group action $\star_H$ being
the scalar multiplication, it is clear that it can be performed in polynomial time
when all the other operations can be done in PPT. For $(H, S, \star_H)$ to be an
EEGA, we need to be able to invert efficiently $\star_H$. It is easily seen that $\text{Invert}_H$
is simply a DLP in a cyclic subgroup of $E[N]$. For this operation to be efficient
with the Pohlig-Hellman algorithm, we need $N$ to be smooth (with smoothness
bound polynomial in $\lambda$). Fortunately, this condition is rather agreeable with the
other constraint regarding the field of definition of $E[N]$. Indeed, for any prime
$p$, we know that $E[N]$ has a field of definition whose degree is polynomial (in
the powersmoothness bound of $N$) for any $p$. In practice, we can even choose the
prime $p$ to ensure that $E[N]$ is defined over $\mathbb{F}_p$ or $\mathbb{F}_{p^2}$. This allows us to consider
smooth values of $N$ as well (for instance a power of 2).

The subset $A'$. The main requirement for $A'$ is efficiency of $\star_A$. The complexity
of this computation mainly depends on $n(\mathbf{a})$ (because $\star_A$ consists in the com-
putation of an isogeny of degree $n(\mathbf{a})$). More concretely, the computation of an
isogeny of degree $\prod_{i=1}^n \ell_i^{e_i}$ is in $O(n \max_{1 \le i \le n} e_i \max_{1 \le i \le n} \sqrt{\ell_i})$. Thus, we need
that $n, \max_{1 \le i \le n} \ell_i$ and $\max_{1 \le i \le n} e_i$ are all polynomial in $\lambda$. We have already
assumed that it was the case for $n$ and the $\ell_i$, so we only need to put a bound
$m$ on the exponent. Unfortunately, having an asymptotic polynomial bound on
$m$ will not be possible due to the Reduce$_A$ algorithm that we will detail be-
low. However, the value of $m$ will remain reasonably small in practice as was
demonstrated for CSIDH in [6] and SCALLOP [17]. This motivates to set $A'$ as
$\{\prod_{i=1}^n \ell_i^{e_i} \mid \mathbf{e} = (e_1, \dots, e_n) \in \mathbb{Z}^n \text{ and } \|\mathbf{e}\|_{\infty} \le m\}$ for some value $m$. Under the
map $\Phi$ that we introduced in Section 5.1, we can sample elements of $A'$ as image
under $\Phi$ of random vectors in the ball $B_\infty(m) = \{\mathbf{e} \in \mathbb{Z}^n \mid \|\mathbf{e}\|_{\infty} \le m\}$ inside $\mathbb{Z}^n$
and it is clear that we can sample uniform vectors in that set. In the definition
of an ETOGA, we also need that $A'$ covers all equivalence classes of $A / \sim_A$ and
that sampling in $A'$ gives classes that are statistically distributed uniformly in
G. We see that the cardinal of $A'$ is $(2m + 1)^n$. Thus, even when $\#A/ \sim_A$ is exponential in $\lambda$, we can take small values of $m, n$ such that $A'$ is big enough to hope that all equivalence classes are covered and that sampling in $A'$ provide a good distribution in $\text{Cl}(\mathcal{D})$. In practice, this is what we observe for the example given in Section 5.3.

Regarding the Reduce$_A$ function, we use $\mathcal{F}$ again. Let us take an element $\mathfrak{a} \in A$. We know that this corresponds to an element of $\mathbb{Z}^{2n}$. Once again, since scalars are in the class of $1_A$, we can simply ignore them and consider the equivalent ideal of the form $\prod_{i=1}^n \ell_i^{e_i}$ that corresponds to the vector $(e_1, \dots, e_n) \in \mathbb{Z}^n$ under the map $\mathcal{F}$. The ideal that we look for is $\mathcal{F}(\mathfrak{e}')$ where $\mathfrak{e}' \in \mathcal{B}_\infty(m)$ and $\mathfrak{e}' \in \mathcal{L}$. If $m$ is big enough, a correct solution $\mathfrak{e}'$ is given by solving a Closest Vector Problem (CVP). Hence, we define a parameter $\gamma \ge 1$ and look for a solution of the $\gamma$-CVP. Of course, the parameter $\gamma$ and $m$ need to be compatible in the sense that we want the solutions of our $\gamma$-CVP to be contained in $\mathcal{B}_\infty(m)$.

More concretely, the Reduce$_A$ algorithms consists in the following steps given an ideal $\mathfrak{a}$ as input: divide $\mathfrak{a}$ by its scalar factor to get another ideal $\mathfrak{a}'$, compute $\mathfrak{e} = \mathcal{F}^{-1}(\mathfrak{a}')$, compute $\mathfrak{e}'$ a solution for the $\gamma$-CVP for $\mathfrak{e}$ and $\mathcal{L}$, output $\mathcal{F}(\mathfrak{e}')$. The complexity of Reduce$_A$ mainly depends on the complexity of solving the $\gamma$-CVP problem. The best known algorithm are sub-exponential in the dimension of the lattice $\mathcal{L}$ (here it is $n$) but the cost can be greatly reduced if the lattice $\mathcal{L}$ comes with a small basis of $\mathcal{L}$ (see [19]). This shifts the computational cost to the precomputation of a nice basis of $\mathcal{L}$. The cost of this precomputation is why we cannot have $m$ polynomial in $\lambda$. Indeed, having a polynomial $m$ would require to make a precomputation of exponential complexity (which would be greater than the complexity of attacks) to compute a good basis of the lattice $\mathcal{L}$. Thus, asymptotically, it is only possible to have $m$ sub-exponential in $\lambda$ so that the basis reduction remains feasible. However, in the practical examples of the literature, the dimension of the lattice remains small enough that it is possible to obtain a reasonable value of $m$ (see [6,17] and our discussion in Section 5.3). The choice of $\gamma$ might also offer interesting tradeoffs between the cost of $\star_A$ and the cost of Reduce$_A$.

## 5.3 Concrete instantiation for isogeny TOGA and TOGA-UE

There are currently two candidates to instantiate our ETOGA from isogenies. The most standard one is the CSIDH group action [11], but there is also the recent SCALLOP construction [17]. Below we will briefly explain the limitations and advantages of these two schemes. Then, we will discuss their security.

In CSIDH, the quadratic order $\mathcal{D}$ is $\mathbb{Z}[\sqrt{-p}]$. This particular choice allows us to compute the group action quite efficiently when the prime $p$ is chosen carefully. Indeed, the orientation of $\mathcal{D}$ is induced by the Frobenius endomorphism which is always very easy to compute. A very nice side effect is that all the curves considered are defined over $\mathbb{F}_p$ (and not $\mathbb{F}_{p^2}$ as is the case for all the other supersingular curves). The common example in the literature is the CSIDH-512 prime given in [11] for which the computation of the group action is particularly efficient for ideals of norm $\prod_{i=1}^n \ell_i^{e_i}$ with $\{\ell_i\}_{1\le i\le n}$ the set of the 74 small
primes that divide $p+1$. All the necessary precomputations related to this prime were performed in [6]. The authors of [6] implemented the full group action and obtained reasonable performances. However, the problem with CSIDH is that there is no control over the structure of the class group $Cl(\mathfrak{D})$. Computing this structure is the bottleneck of the precomputation, and it seems currently infeasible to scale the precomputations made in [6] to higher level of security. This is a big obstacle given the lack of consensus in the community regarding the exact security level of CSIDH-512 (see the security paragraph below).

The recent SCALLOP construction [17] was introduced to overcome some of the limitations of CSIDH. In particular, the authors of SCALLOP propose to use $\mathfrak{D} = \mathbb{Z}[f\sqrt{-1}]$ for a well-chosen prime number $f$. In that case, the exact structure of the class group $Cl(\mathfrak{D})$ is given freely by a mathematical theorem. This, in turn, gives some freedom to choose the value of $f$ in a way that greatly simplifies the rest of the required precomputations. However, the concrete orientation is not realized by a simple endomorphism like the Frobenius, and so the group action in itself is generally much slower than the one of CSIDH for the same level of security. Nonetheless, SCALLOP appears more promising than CSIDH to reach a high level of security. The authors managed to perform the necessary precomputation for a level of security equivalent to CSIDH-1024 (essentially doubling the level of security of CSIDH-512) without any extensive computational resources. However, the performances they obtained are not very practical (one group action takes several minutes to compute).

***The security.*** First, we want to stress that establishing the exact level of security reached by a specific instance of CSIDH and SCALLOP in the post-quantum setting is out of the scope of this paper so we do not claim any particular security level.

The standard group action used in isogeny-based cryptography corresponds to the induced one $\star_G$ in our ETOGA. In the case of CSIDH, it is a quite standard assumption that this group action is weak-PR. Given how recent the scheme is, the weak pseudorandomness of $\star_G$ in SCALLOP has been a lot less studied, but there is currently no reason to believe that it might not hold. However, our scheme requires that the main group action $\star_A$ is also weak pseudorandom. In the case of CSIDH, this was studied in the context of SIGAMAL [26]. The same cannot be said for $\star_A$ in SCALLOP, even though, once again, there are currently no reason to believe that it might be easier than its CSIDH counterpart.

As of yet, both constructions are not affected by the recent attacks against SIDH [12,25,31]. This has already been stated several times in the literature for the main group action of CSIDH, and the analysis of SCALLOP in [17] also concludes that the scheme remains safe for now. Similarly, the recent attacks against SIDH do not appear to affect the weak pseudorandomness of $\star_A$. Indeed, the fact that the image of a point under the secret isogeny is revealed does not seem problematic when the degree is unknown (and there does not seem to be a way to use the point to obtain some information on the degree either). In particular, we see that some of the attacks developed in [20] do not apply in our case because the image of only one point is given and so the Weil pairing
(which is self-trivial) does not help in recovering information on the degree. The
lack of existence of such a self-pairing in the case that interests us was recently
demonstrated in [10]. Nonetheless, further analysis of these problems is required
in order to gain confidence in their hardness and to estimate concretely the size
of the parameters required to get the weak pseudorandomness of $\star_A$.

In conclusion, even though CSIDH and SCALLOP are not perfect candidates,
they are currently the best solution we have. We hope that our construction will
motivate further research in that topic and that our ETOGA construction can
help building more advanced protocols from isogenies.

References

1. Michel Abdalla, Thorsten Eisenhofer, Eike Kiltz, Sabrina Kunzweiler, and Doreen Riepel, *Password-authenticated key exchange from group actions*, Advances in Cryptology–CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part II, Springer, 2022, pp. 699–728.

2. Navid Alamati, Luca De Feo, Hart Montgomery, and Sikhar Patranabis, *Cryptographic group actions and applications*, Advances in Cryptology – ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part II (Berlin, Heidelberg), Springer-Verlag, 2020, p. 411–439.

3. Reza Azarderakhsh, David Jao, Kassem Kalach, Brian Koziel, and Christopher Leonardi, *Key compression for isogeny-based cryptosystems*, Proceedings of the 3rd ACM International Workshop on ASIA Public-Key Cryptography, ACM, 2016.

4. Andrea Basso, *A post-quantum round-optimal oblivious prf from isogenies*, Cryptology ePrint Archive (2023).

5. Daniel J. Bernstein, Luca De Feo, Antonin Leroux, and Benjamin Smith, *Faster computation of isogenies of large prime degree*, ANTS (2020).

6. Ward Beullens, Thorsten Kleinjung, and Frederik Vercauteren, *Csi-fish: Efficient isogeny based signatures through class group computations*, International Conference on the Theory and Application of Cryptology and Information Security, Springer, 2019, pp. 227–247.

7. Dan Boneh, Kevin Lewi, Hart Montgomery, and Ananth Raghunathan, *Key homomorphic prfs and their applications*, Advances in Cryptology – CRYPTO 2013 (Berlin, Heidelberg) (Ran Canetti and Juan A. Garay, eds.), Springer Berlin Heidelberg, 2013, pp. 410–428.

8. Jeremy Booher, Ross Bowden, Javad Doliskani, Tako Boris Fouotsa, Steven D Galbraith, Sabrina Kunzweiler, Simon-Philipp Merz, Christophe Petit, Benjamin Smith, Katherine E Stange, et al., *Failing to hash into supersingular isogeny graphs*, arXiv preprint arXiv:2205.00135 (2022).

9. Colin Boyd, Gareth T. Davies, Kristian Gjøsteen, and Yao Jiang, *Fast and secure updatable encryption*, Advances in Cryptology – CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part I, Springer-Verlag, 2020, p. 464–493.

10. Wouter Castryck, Marc Houben, Simon-Philipp Merz, Marzio Mula, Sam van Buuren, and Frederik Vercauteren, *Weak instances of class group action based cryptography via self-pairings*, Cryptology ePrint Archive (2023).
11. Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, and Joost Renes, *Csidh: an efficient post-quantum commutative group action*, International Conference on the Theory and Application of Cryptology and Information Security, Springer, 2018, pp. 395-427.

12. Wouter Castryck, Jana Sotáková, and Frederik Vercauteren, *Breaking the decisional diffie-hellman problem for class group actions using genus theory*, Annual International Cryptology Conference, Springer, 2020, pp. 92-120.

13. Leonardo Colò and David Kohel, *Orienting supersingular isogeny graphs*, Number-Theoretic Methods in Cryptology 2019 (2019).

14. Jean-Sébastien Coron, Jacques Patarin, and Yannick Seurin, *The random oracle model and the ideal cipher model are equivalent*, Advances in Cryptology – CRYPTO 2008 (Berlin, Heidelberg) (David Wagner, ed.), Springer Berlin Heidelberg, 2008, pp. 1-20.

15. C. Costello, D. Jao, P. Longa, M. Naehrig, J. Renes, and D. Urbanik, *Efficient compression of SIDH public keys*, pp. 679-706, Springer International Publishing, 2017.

16. Luca De Feo, Cyprien Delpech de Saint Guilhem, Tako Boris Fouotsa, Péter Kutas, Antonin Leroux, Christophe Petit, Javier Silva, and Benjamin Wesolowski, *Séta: Supersingular encryption from torsion attacks*, International Conference on the Theory and Application of Cryptology and Information Security, Springer, 2021, pp. 249-278.

17. Luca De Feo, Tako Boris Fouotsa, Péter Kutas, Antonin Leroux, Simon-Philipp Merz, Lorenz Panny, and Benjamin Wesolowski, *SCALLOP: scaling the CSI-FiSh*, PKC (2023).

18. Edward Eaton, David Jao, Chelsea Komlo, and Youcef Mokrani, *Towards post-quantum updatable public-key encryption via supersingular isogenies*, Cryptology ePrint Archive (2020).

19. Thomas Espitau and Paul Kirchner, *The nearest-colattice algorithm: Time-approximation tradeoff for approx-cvp*, Open Book Series 4 (2020), no. 1, 251-266.

20. Tako Boris Fouotsa, Tomoki Moriya, and Christophe Petit, *M-SIDH and MD-SIDH: countering SIDH attacks by masking information*, EUROCRYPT (2023).

21. Zhengfeng Ji, Youming Qiao, Fang Song, and Aaram Yun, *General linear group action on tensors: A candidate for post-quantum cryptography*, Theory of Cryptography (Cham) (Dennis Hofheinz and Alon Rosen, eds.), Springer International Publishing, 2019, pp. 251-281.

22. Yao Jiang, *The direction of updatable encryption does not matter much*, Advances in Cryptology – ASIACRYPT 2020 (Cham) (Shiho Moriai and Huaxiong Wang, eds.), Springer International Publishing, 2020, pp. 529-558.

23. Michael Klooß, Anja Lehmann, and Andy Rupp, (*r*)cca secure updatable encryption with integrity protection, Advances in Cryptology – EUROCRYPT 2019 (Cham) (Y. Ishai and V. Rijmen, eds.), Springer International Publishing, 2019, pp. 68–99.

24. Anja Lehmann and Björn Tackmann, *Updatable encryption with post-compromise security*, Advances in Cryptology – EUROCRYPT 2018 (Cham) (J. B. Nielsen and V. Rijmen, eds.), Springer International Publishing, 2018, pp. 685–716.

25. Luciano Maino, Chloe Martindale, Lorenz Panny, Giacomo Pope, and Benjamin Wesolowski, *A direct key recovery attack on sidh*, EUROCRYPT, 2023.

26. T. Moriya, H. Onuki, and T. Takagi, *Sigamal: a supersingular isogeny-based pke and its application to a prf*, International Conference on the Theory and Application of Cryptology and Information Security, Springer, 2020, pp. 551-580.
27. Michael Naehrig and Joost Renes, *Dual isogenies and their application to public-key compression for isogeny-based cryptography*, Advances in Cryptology – ASI-ACRYPT 2019 (Cham) (Steven D. Galbraith and Shiho Moriai, eds.), Springer International Publishing, 2019, pp. 243–272.

28. Ryo Nishimaki, *The direction of updatable encryption does matter*, Public-Key Cryptography – PKC 2022: 25th IACR International Conference on Practice and Theory of Public-Key Cryptography, Virtual Event, March 8–11, 2022, Proceedings, Part II (Berlin, Heidelberg), Springer-Verlag, 2022, p. 194–224.

29. Hiroshi Onuki, *On oriented supersingular elliptic curves*, Finite Fields and Their Applications **69** (2021), 101777.

30. Geovandro C. C. F. Pereira, Javad Doliskani, and David Jao, *x-only point addition formula and faster torsion basis generation in compressed sike*, Cryptology ePrint Archive, Report 2020/431, 2020.

31. Damien Robert, *Breaking SIDH in polynomial time*, EUROCRYPT (2023).

32. Phillip Rogaway, Mihir Bellare, John Black, and Ted Krovetz, *Ocb: A block-cipher mode of operation for efficient authenticated encryption*, Proceedings of the 8th ACM Conference on Computer and Communications Security (New York, NY, USA), CCS '01, Association for Computing Machinery, 2001, p. 196–205.

33. C. E. Shannon, *Communication theory of secrecy systems*, The Bell System Technical Journal **28** (1949), no. 4, 656–715.

34. P. W. Shor, *Algorithms for quantum computation: discrete logarithms and factoring*, Proceedings 35th Annual Symposium on Foundations of Computer Science, Nov 1994, pp. 124–134.

35. Gang Tang, Dung Hoang Duong, Antoine Joux, Thomas Plantard, Youming Qiao, and Willy Susilo, *Practical post-quantum signature schemes from isomorphism problems of trilinear forms*, Cryptology ePrint Archive, Report 2022/267, 2022.

36. J. Vélu, *Isogénies entre courbes elliptiques*, Comptes-Rendus de l'Académie des Sciences, Série I **273** (1971), 238–241.

37. B. Wesolowski, *Orientations and the supersingular endomorphism ring problem*, EUROCRYPT, 2022.

38. Gustavo H. M. Zanon, Marcos A. Simplicio, Geovandro C. C. F. Pereira, Javad Doliskani, and Paulo S. L. M. Barreto, *Faster isogeny-based compressed key agreement*, Post-Quantum Cryptography (Tanja Lange and Rainer Steinwandt, eds.), Springer International Publishing, 2018, pp. 248–268.
# Appendices

## Appendix A Definitions for group actions

**Definition 1 (Effective Group Action [2]).** $(G, S, \star)$ is an effective group action (EGA), with respect to a parameter $\lambda$, if the following properties are satisfied:

1. The group $G$ is finite and there exist PPT algorithms for:

(a) Membership testing, i.e., to decide if a given bit string represents a valid element in $G$.

(b) Equality testing, i.e., to decide if two bit strings represent the same group element in $G$.

(c) Sampling, i.e., to sample an element $g$ from a distribution $D_G$ on $G$.

(d) Operation, i.e., to compute $gh$ for any $g, h \in G$.

(e) Inversion, i.e., to compute $g^{-1}$ for any $g \in G$.

2. The set $S$ is finite and there exist efficient PPT algorithms for:

(a) Membership testing.

(b) Unique representation, i.e., given any arbitrary set element $s \in S$, compute a string $\hat{s}$ that canonically represents $s$.

3. There exists a distinguished element $s_0 \in S$, called the origin, such that its bit-string representation is known.

4. There exists an efficient algorithm that given (some bit-string representations of) any $g \in G$ and any $s \in S$, outputs $g \star s$.

We can strengthen the definition on an EGA by replacing the existence of the origin $s_0$ by the following Hashing to the set axiom.

**Definition 2 (Hashable EGA [2]).** Let $(G, S, \star)$ be an OW-EGA. We say that $(G, S, \star)$ is a hashable OW-EGA if there exists an efficient sampler $H : \{0, 1\}^N \to S$ (where $N$ depends on the security parameter), such that for all PPT adversaries $\mathcal{A}$, we have $\Pr[\mathcal{A}(i, j) \star H(i) = H(j)] \le \text{negl}(\lambda)$ for $i, j \stackrel{\$}{\leftarrow} \{0, 1\}^N$.

We define one-way group actions:

**Definition 3 (One-Way Group Action [2]).** Let $(G, S, \star)$ be $\mathcal{G}\mathcal{A}(\lambda)$ for some security parameter $\lambda$. Let $\mathcal{D}_G$ and $\mathcal{D}_S$ be distributions on $G$ and $S$ respectively. For $s \in S$, let $f_s: G \to S$ be the function defined by $f_s: g \mapsto g \star s$. We say that $(G, S, \star)$ is $(\mathcal{D}_G, \mathcal{D}_S)$-one-way if, for all PPT adversaries $\mathcal{A}$, we have:

$$ \Pr[f_s(\mathcal{A}(s, f_s(g))) = f_s(g)] \le \text{negl}(\lambda) $$

where $s \leftarrow \mathcal{D}_S$ and $g \leftarrow \mathcal{D}_G$.
Informally, a group action $(G, S, \star)$ is $(\mathcal{D}_G, \mathcal{D}_S)$-one-way if, given a pair of set elements $(s, g \star s)$ where $s \leftarrow \mathcal{D}_S$ and $g \leftarrow \mathcal{D}_G$, there is no PPT adversary that can recover $g$. If $\mathcal{D}_S$ and $\mathcal{D}_G$ are uniform distributions, then we simply speak of an OW group action.

We show that our OW-MEGA is also a hashable OW-EGA.

**Proposition 1.** Let $(G, S, \star)$ be an OW-MEGA with bijection $\pi$. Then, $(G, S, \star)$ is also a hashable OW-EGA with sampler $H := \pi$.

*Proof.* Keeping the notations of the proposition, let $\mathcal{A}$ be an adversary that breaks the *Hashing to the set* axiom of the sampler $\pi$ of $(G, S, \star)$ with probability $\epsilon$. We build the following adversary $\mathcal{B}$ against the one-way property of $(G, S, \star)$.

1. $\mathcal{B}$ receives $(s, f_s(g)) = (s, g \star s)$ such that $s \stackrel{\$}{\leftarrow} S$ and $g \stackrel{\$}{\leftarrow} G$.

2. $\mathcal{B}$ calls $\mathcal{A}$ on input $(\pi^{-1}(s), \pi^{-1}(g \star s))$ and let $h \in G$ be the value returned by $\mathcal{A}$.

3. $\mathcal{B}$ outputs $h$.

By definition of $\mathcal{A}$, $\mathcal{A}$ returns $h$ such that $h \star \pi(\pi^{-1}(s)) = \pi(\pi^{-1}(g \star s))$ with probability $\epsilon$. This means that, with probability $\epsilon$, $\mathcal{B}$ outputs $h$ such that $h \star s = f_s(g)$ which is exactly breaking the one-way property of $(G, S, \star)$.

# Appendix B Computing leakage sets

Using [24], extended epoch leakage sets $\mathcal{C}^*$, $\mathcal{K}^*$ and $\mathcal{T}^*$ are computed as follows:

$$ 
\begin{align*}
\mathcal{C}^* &\leftarrow \{e \in \{0, \dots, n\} \mid \text{CorrK}(e) = \text{true}\} \\
\text{true} &\leftarrow \text{CorrK}(e) \Leftrightarrow (e \in \mathcal{K}) \lor (\text{CorrK}(e-1) \land e \in \mathcal{T}) \lor (\text{CorrK}(e+1) \land e+1 \in \mathcal{T}) \\
\mathcal{T}^* &\leftarrow \{e \in \{0, \dots, n\} \mid (e \in \mathcal{T}) \lor (e \in \mathcal{K}^* \land e-1 \in \mathcal{K}^*)\} \\
\mathcal{C}^* &\leftarrow \{e \in \{0, \dots, n\} \mid \text{ChallEq}(e) = \text{true}\} \\
\text{true} &\leftarrow \text{ChallEq}(e) \Leftrightarrow (e = \tilde{e}) \lor (e \in \mathcal{C}) \lor (\text{ChallEq}(e-1) \land e \in \mathcal{T}^*) \lor \\
&\phantom{\leftarrow} (\text{ChallEq}(e+1) \land e+1 \in \mathcal{T}^*)
\end{align*}
$$

Likewise, we extend $\mathcal{I}$ into $\mathcal{I}^*$:

$$ 
\begin{align*}
\mathcal{I}^* &\leftarrow \{e \in \{0, \dots, n\} \mid \text{ChallInpEq}(e) = \text{true}\} \\
\text{true} &\leftarrow \text{ChallInpEq}(e) \Leftrightarrow (e \in \mathcal{I}) \lor (\text{ChallInpEq}(e-1) \land e \in \mathcal{T}^*) \lor \\
&\phantom{\leftarrow} (\text{ChallInpEq}(e+1) \land e+1 \in \mathcal{T}^*)
\end{align*}
$$

# Appendix C Correctness of GAINE

GAINE is correct, even for non-abelian group actions.

**Proposition 2 (Correctness of updates).** Let $k_e, k_{e+1} \in G$ be two keys and $C_e := k_e \star s$ for some $s \in S$. If $\Delta_{e+1} := \text{TokenGen}(k_e, k_{e+1})$, then $\text{Upd}(\Delta_{e+1}, C_e) = k_{e+1} \star s$.
Proof. By definition of TokenGen, we have $\Delta_{e+1} := k_{e+1}k_e^{-1}$. By definition of Upd, we have

$$ \mathrm{Upd}(\Delta_{e+1}, C_e) = \Delta_{e+1} \star C_e = (k_{e+1}k_e^{-1}) \star (k_e \star s) = k_{e+1} \star s $$

where the last equality holds because of the compatibility of the group action (see Item 2 of Definition 1) and because $k_e^{-1}$ is the inverse of $k_e$ in the group $G$.

**Proposition 3 (Correctness).** *The GAINE scheme is correct.*

Proof. Let $0 \le e_1 \le e_2 \le n+1$ be two epochs and let us consider a ciphertext $C_{e_2}$ updated through the successive tokens $\Delta_{i+1}$ for $i \in [e_1, e_2-1]$ from an initial ciphertext $C_{e_1}$ that is the encryption of a message $m$ under the key $k_{e-1}$ as in Definition 5. By definition of $C_{e_1} := \mathrm{Enc}(k_{e_1}, M)$, we have $C_{e_1} = k_{e_1} \star \pi(N \| M)$ for some random nonce $N$. By applying Proposition 2 on the updates of $C_{e_1}$, we have that $C_{e_2} = k_{e_2} \star \pi(N \| M)$. Then, we get

$$ k_{e_2}^{-1} \star C_{e_2} = k_{e_2}^{-1} \star (k_{e_2} \star \pi(N \| M)) = 1_G \star \pi(N \| M) = \pi(N \| M) $$

where the penultimate equality holds because of the compatibility of the group action (see Item 2 of Definition 1) and the last equality holds because of the identity property of the group action (see Item 1 of Definition 1). Finally, we have $\pi^{-1}(k_{e_2}^{-1} \star C_{e_2}) = N \| M$ and $\mathrm{Dec}(k_{e_2}, C_{e_2})$ returns $M$.

# Appendix D The Check algorithm

In our proofs, reductions play hybrid games and guess the location of the $i$-th insulated region. If the adversary sends a corrupt query inside this insulated region, the guess is wrong and reductions have to abort. We use the algorithm Check of [9], described in Fig. 1, to check if this event happens.

Check(inp, $\hat{e}$; e; fwl, fwr)

1. if $\hat{e} > e$

2. return $\perp$

3. if inp = key and $\hat{e} \in \{\mathrm{fwl}, \dots, \mathrm{fwr}\}$

4. return ABORT

5. if inp = token and $\hat{e} \in \{\mathrm{fwl}, \dots, \mathrm{fwr} + 1\}$

6. return ABORT

**Fig. 1.** Algorithm Check of [9] used in our proofs. $\hat{e}$ is the epoch in the adversary's request and $e$ is the current epoch.

# Appendix E Proof of Theorem 1

We follow the proof strategy of [9] and use their hybrid argument across insulated regions. In each hybrid, we can embed at one firewall of the insulated region and
simulate all tokens within that insulated region to answer queries to both $\mathcal{O}.$Upd and $\mathcal{O}.$Upd$\tilde{\mathcal{C}}$. In GAINE, we update a ciphertext from epoch $e$ to epoch $e+1$ by computing the action of the group element $k_{e+1}k_e^{-1}$. Fresh ciphertexts are randomized using a nonce $N$ but updates are deterministic, thus our reduction will need to provide consistent ciphertexts to the adversary, i.e., the $N$ value must be consistent.

We give a reduction $\mathcal{B}$ which receives a group action $(G, S, \star)$ and an oracle $\mathcal{O}.$Sample that returns either tuples of the form $(s_i, g \star s_i)$ or $(s_i, u_i)$ where $g \stackrel{\$}{\leftarrow} G$ and $s_i, u_i \stackrel{\$}{\leftarrow} S$. $\mathcal{B}$ will use the tuples of $\mathcal{O}.$Sample to perfectly simulate the detIND-UE-CPA experiment for GAINE when those tuples are of the form $(s_i, g \star s_i)$ (and a random experiment otherwise). The idea is to embed $g$ to a well chosen epoch key by using $s_i$ as randomness and $g \star s_i$ as ciphertext value. Thus, if we know an efficient adversary $\mathcal{A}$ against the detIND-UE-CPA security of GAINE, using the hybrid argument of [9], $\mathcal{B}$ can use $\mathcal{A}$ to break the weak pseudorandomness of $(G, S, \star)$.

*Proof. Play hybrid games.* We partition the non corrupted key space as follows: $\{0, \dots, n\} \setminus \mathcal{K}^* = \cup_{(j,fw_l_j,fw_r_j) \in \mathcal{F}^W} \{fw_l_j \dots fw_r_j\}$, where $fw_l_i$ and $fw_r_i$ are firewalls of the $i$-th insulated region. For $b \in \{0, 1\}$, define game $\mathcal{G}_i^b$ as $\mathbf{Exp}_{\text{GAINE},\mathcal{A}}^{\text{detIND-UE-CPA-b}}$ except for:

1. The game randomly picks $fw_l_i, fwr_i \stackrel{\$}{\leftarrow} \{0, \dots, n\}$ and if they are not the $i$-th firewalls, it aborts and returns a random bit $b'$. This loss is upper-bounded by $(n+1)^2$.

2. For the challenge (made in epoch $\tilde{e}$ on input $(\tilde{M}, \tilde{C}))$, the game returns an updated version of $\tilde{C}$ if $\tilde{e} < fw_l_i$ and it returns an encryption of $\tilde{M}$ if $\tilde{e} > fwr_i$. Finally, if $fw_l_i \le \tilde{e} \le fwr_i$, the game returns an encryption of $\tilde{M}$ if $b=0$ and an updated version of $\tilde{C}$ if $b=1$.

3. After $\mathcal{A}$ outputs $b'$, the game returns $b'$ if $\text{twf} \ne 1$ or some additional trivial win condition triggers.

If $fw_l_i, fwr_i$ are the desired values, then $\mathcal{G}_i^0$ is $\mathbf{Exp}_{\text{GAINE},\mathcal{A}}^{\text{detIND-UE-CPA-0}}$, i.e., all challenges are encryptions of $\tilde{M}$. Let $\ell$ be the total number of insulated regions (bounded by $n+1$), such that $\mathcal{G}_i^1$ is $\mathbf{Exp}_{\text{GAINE},\mathcal{A}}^{\text{detIND-UE-CPA-1}}$, i.e., all challenges are updates of $\tilde{C}$. Let $E$ be the event that $fw_l_i$ and $fwr_i$ are the desired values. By definition, for any $1 \le i \le n+1$ and $b \in \{0, 1\}$, we have $\Pr[\mathcal{G}_i^b = 1 | \neg E] = 1/2$. Then

$$ \Pr[\mathcal{G}_{\ell}^{1} = 1] = \Pr[\mathcal{G}_{\ell}^{1} = 1 | E] \cdot \Pr[E] + \Pr[\mathcal{G}_{\ell}^{1} = 1 | \neg E] \cdot \Pr[\neg E] \\ = \Pr[\mathbf{Exp}_{\text{GAINE},\mathcal{A}}^{\text{detIND-UE-CPA-1}} = 1] \cdot \frac{1}{(n+1)^2} + \frac{1}{2} \cdot (1 - \frac{1}{(n+1)^2}), \text{and} $$

$$ \Pr[\mathcal{G}_1^0 = 1] = \Pr[\mathbf{Exp}_{\text{GAINE},\mathcal{A}}^{\text{detIND-UE-CPA-0}} = 1] \cdot \frac{1}{(n+1)^2} + \frac{1}{2} \cdot (1 - \frac{1}{(n+1)^2}) $$

Thus, we have $|\Pr[\mathcal{G}_\ell^1 = 1] - \Pr[\mathcal{G}_1^0 = 1]| = \frac{1}{(n+1)^2} \cdot \mathbf{Adv}_{\text{GAINE},\mathcal{A}}^{\text{detIND-UE-CPA}}(\lambda)$.
Notice that the games $G_{i-1}^1$ and $G_i^0$ behave in the same way: for the challenge query and $\mathcal{O}\text{Upd}\tilde{\mathcal{C}}$, in an epoch in the first $i-1$ insulated regions, the reduction returns an update of $\tilde{C}$, otherwise it returns an encryption of $\tilde{M}$. Thus, for any $\ell \le n+1$, $|\text{Pr}[G_\ell^1 = 1] - \text{Pr}[G_1^0 = 1]| \le \sum_{i=1}^\ell |\text{Pr}[G_i^1 = 1] - \text{Pr}[G_i^0 = 1]|$. In the following, we prove that for any $1 \le i \le \ell$, $|\text{Pr}[G_i^1 = 1] - \text{Pr}[G_i^0 = 1]| \le 2\text{Adv}_{\mathcal{G},\mathcal{A},\mathcal{B}}^{\text{wk-PR}}(\lambda)$ for a reduction $\mathcal{B}$.

In hybrid $i$. Let $\mathcal{A}_i$ be an adversary trying to distinguish $G_i^0$ from $G_i^1$. For all queries concerning epochs outside of the $i$-th insulated region, the responses of both games are the same. Thus, we assume that $\mathcal{A}_i$ asks for at least one challenge ciphertext in an epoch within the $i$-th insulated region. This is where we will embed the weak pseudorandom group action samples in our reduction.

We construct a reduction $\mathcal{B}$, presented in Fig. 2, that is playing the weak pseudorandom group action game (Definition 3) and will simulate the responses of queries made by adversary $\mathcal{A}_i$. Since we do not assume the group action $(G, S, \star)$ to be abelian, we define $(\prod_{i=0}^n g_i) \star s := (g_0g_1 \dots g_n) \star s$ for $s \in S$ and $g_0, \dots, g_n \in G$.

Recall that $\mathcal{A}_i$ is an adversary attempting to distinguish $G_i^0$ from $G_i^1$. $\mathcal{B}$ will try to use $\mathcal{A}$ to break the weak pseudorandomness of the group action $(G, S, \star)$. In $\text{Exp}_{\mathcal{G},\mathcal{A},\mathcal{B}}^{\text{wk-PR}}(\lambda)$, when $\mathcal{O}\text{Sample}$ returns pairs of the form $(s_j, g \star s_j)$ for $g \stackrel{\$}{\leftarrow} G$ and $s_j \stackrel{\$}{\leftarrow} S$, $\mathcal{B}$ will perfectly simulate the environment of $\mathcal{A}_i$ in $G_i^b$. When $\mathcal{O}\text{Sample}$ returns pairs of the form $(s_j, t_j)$ for $s_j, t_j \stackrel{\$}{\leftarrow} S$, $\mathcal{B}$ will give random inputs to $\mathcal{A}_i$ such that $\mathcal{A}_i$ distinguishes $G_i^0$ from $\tilde{G}_i^1$ with advantage 0. We explain how our reduction $\mathcal{B}$ does this without knowing which $\mathcal{O}\text{Sample}$ oracle was provided to it.

The reduction $\mathcal{B}$ receives the oracle $\mathcal{O}\text{Sample}$, takes $b \stackrel{\$}{\leftarrow} \{0, 1\}$ and simulates $G_i^b$. Whenever the reduction needs to provide an output of $\pi(\cdot)$ to $\mathcal{A}_i$, it chooses some set value $s \in S$ such that $\pi(\cdot) = s$. In this setting, computing $\pi^{-1}$ is simply a lookup to this mapping of the ideal cipher $\pi$. We explain our simulation:

Initially,

1. $\mathcal{B}$ guesses the values of $\text{fwl}_i$ and $\text{fwr}_i$.

2. $\mathcal{B}$ generates all keys and tokens except for $k_{\text{fwl}_i}, \dots, k_{\text{fwr}_i}, \Delta_{\text{fwl}_i}, \Delta_{\text{fwr}_i+1}$. If $\mathcal{A}_i$ corrupts these keys and tokens, this means that the firewall guess is wrong and the reduction aborts the game using the Check algorithm of Appendix D.

$\mathcal{B}$ will operate so as to embed the value $g$ used by $\mathcal{O}\text{Sample}$ to the key $k_{\text{fwl}_i}$ and the value $g k_{\text{fwl}_{i-1}}^{-1}$ to the token $\Delta_{\text{fwl}_i}$. If $\mathcal{O}\text{Sample}$ returns uniformly distributed pairs of set elements instead, all the ciphertexts inside insulated region $i$ will be random set elements (no key or token could possibly explain these ciphertexts).

To simulate a non-challenge ciphertext that is:

* An $\mathcal{O}\text{Enc}$ query in epoch $e \in \{0, \dots, \text{fwl}_i - 1\} \cup \{\text{fwr}_i + 1, \dots, n\}$: $\mathcal{B}$ queries $\mathcal{O}\text{Sample}$ to get a pair $(s, t) \in S^2$. $\mathcal{B}$ uses $s$ as a random value by programming $\pi(\cdot) \leftarrow s$ (so the randomness will be consistent with calls that $\mathcal{A}_i$ makes to $\mathcal{O}\text{Upd}$), computes the ciphertext $C_e = k_e \star s$ (the value of $k_e$ is known to
Reduction $\mathcal{B}$ playing

$$ \mathbf{Exp}_{\mathcal{G}, \mathcal{A}, \mathcal{B}}^{\text{wk-PR-b}^*}(\lambda) $$

1. receive $(G, S, \star)$ and $\mathcal{O}.\text{Sample}$

2. do Setup$(1^{\lambda})$

3. $\bar{M}, \bar{C} \leftarrow \mathcal{A}^{\text{ors}}(\lambda)$

4. phase $\leftarrow 1$

5. $\tilde{C}_{\tilde{e}} \leftarrow \mathcal{O}.\text{Chall}(\bar{M}, \bar{C})$

6. $b' \leftarrow \mathcal{A}^{\text{ors}, \mathcal{O}.\text{Upd}\tilde{C}}(\tilde{C}_{\tilde{e}})$

7. twf $\leftarrow 1$ if

8. $C^* \cap K^* \neq \emptyset$ or

9. $\mathcal{I}^* \cap C^* \neq \emptyset$

10. if ABORT occurred or
    twf = 1

11. $b' \stackrel{\$}{\leftarrow} \{0, 1\}$

12. return $b'$

13. if $(i, \text{fwl}_i, \text{fwr}_i) \notin \mathcal{F}W$

14. $b' \stackrel{\$}{\leftarrow} \{0, 1\}$

15. return $b'$

16. if $b' = b$

17. return 0

18. else

19. return 1

### Setup$(1^{\lambda})$

1. $b \stackrel{\$}{\leftarrow} \{0, 1\}$

2. pp $\leftarrow$ GAINE .$\text{Setup}$(1$^{\lambda}$)

3. $k_0 \leftarrow$
    GAINE.$\text{KeyGen}$(pp)

4. $\Delta_0 \leftarrow \bot$

5. e, $c_2$, phase, twf $\leftarrow 0$

6. $\mathcal{L}, \tilde{\mathcal{L}}, \mathcal{C}, \mathcal{K}, \mathcal{T} \leftarrow \emptyset$

7. $\text{fwl}_i, \text{fwr}_i \stackrel{\$}{\leftarrow} \{0, \dots, n\}$

8. for $j \in \{0, \dots, \text{fwl}_i - 1\}$
    do

9. $k_j \stackrel{\$}{\leftarrow} G; \Delta_j \leftarrow$
    $k_j k_{j-1}^{\frac{1}{\infty}}$

10. for $j \in \{\text{fwr}_i + 1, \dots, n\}$
    do

11. $k_j \stackrel{\$}{\leftarrow} G; \Delta_j \leftarrow$
    $k_j k_{j-1}^{\frac{1}{\infty}}$

12. for $j \in \{\text{fwl}_i + 1, \dots, \text{fwr}_i\}$
    do

13. $\Delta_j \stackrel{\$}{\leftarrow} G$

$\mathcal{O}.\text{Enc}(M)$

1. $c \leftarrow c + 1$

2. $(\text{inf}_1, \text{inf}_2) \leftarrow$

$\mathcal{O}.\text{Sample}()$

3. $\pi(N \| M) \leftarrow \text{inf}_1$

4. if $e \in \{0, \text{fwl}_i - 1\} \cup \{\text{fwr}_i + 1, \dots, n\}$
    do

5. $C_e \leftarrow k_e \star \text{inf}_1$

6. else

7. $C_{\text{fwl}_i} \leftarrow \text{inf}_2$

8. for $j \in \{\text{fwl}_i + 1, \dots, e\}$
    do

9. $C_j \leftarrow \Delta_j \star C_{j-1}$

10. inf $\leftarrow (\text{inf}_1, \text{inf}_2)$

11. $\mathcal{L} \leftarrow \mathcal{L} \cup \{(c, C_e, e; \text{inf})\}$

12. return $C_e$

$\mathcal{O}.\text{Next}$

1. $e \leftarrow e + 1$

$\mathcal{O}.\text{Upd}(C_{e-1})$

1. if $(c, C_{e-1}, e-1; \text{inf}) \notin \mathcal{L}$
    do

2. return $\bot$

3. if $e \in \{1, \dots, \text{fwl}_i - 1\} \cup \{\text{fwr}_i + 1, \dots, n\}$
    do

4. $(\text{inf}_1, \text{inf}_2) \leftarrow \text{inf}$

5. $C_e \leftarrow k_e \star \text{inf}_1$

6. else

7. $(\text{inf}_1, \text{inf}_2) \leftarrow \text{inf}$

8. $C_{\text{fwl}_i} \leftarrow \text{inf}_2$

9. for $j \in \{\text{fwl}_i + 1, \dots, e\}$
    do

10. $C_j \leftarrow \Delta_j \star C_{j-1}$

11. $\mathcal{L} \leftarrow \mathcal{L} \cup \{(c, C_e, e; \text{inf})\}$

12. return $C_e$

$\mathcal{O}.\text{Corr}(\text{inp}, \hat{e})$

1. do

Check $(\text{inp}, \hat{e}; e; \text{fwl}_i, \text{fwr}_i)$

2. if $\text{inp} = \text{key}$

3. $\mathcal{K} \leftarrow \mathcal{K} \cup \{\hat{e}\}$

4. return $k_e$

5. if $\text{inp} = \text{token}$

6. $\mathcal{T} \leftarrow \mathcal{T} \cup \{\hat{e}\}$

7. return $\Delta_{\hat{e}}$

$\mathcal{O}.\text{Chall}(\bar{M}, \bar{C})$

1. if $(c, \bar{C}, \bar{e} - 1; \text{inf}) \notin \mathcal{L}$

2. return ABORT

3. if $b = 0$

4. $(s, t) \leftarrow \mathcal{O}.\text{Sample}()$

5. $\pi(N \| \bar{M}) \leftarrow s$

6. $\tilde{C}_{\text{fwl}_i} \leftarrow t$

7. else

8. $(\text{inf}_1, \text{inf}_2) \leftarrow \text{inf}$

9. $\pi(N \| \bar{M}) \stackrel{\$}{\leftarrow} S$

10. $\tilde{C}_{\text{fwl}_i} \leftarrow \text{inf}_2$

11. for $j \in \{0, \dots, \text{fwl}_i - 1\}$
    do

12. $\tilde{C}_j \leftarrow$
    $(\prod_{k=j}^{1} \Delta_k)(\prod_{k=1}^{\tilde{e}-1} \Delta_k^{-1}) \star$
    $\tilde{C} \text{ //left}$

13. for $j \in \{\text{fwl}_i + 1, \dots, \text{fwr}_i\}$
    do

14. $\tilde{C}_j \leftarrow \Delta_j \star \tilde{C}_{j-1}$
    //embed
    do

15. for $j \in \{\text{fwr}_i + 1, \dots, n\}$
    do

16. $\tilde{C}_j \leftarrow k_j \star \pi(N \| \bar{M})$

//right
17. $\tilde{\mathcal{L}} \leftarrow \bigcup_{j=0}^{n} \{(\tilde{C}_j, j)\}$

18. return $\tilde{C}_e$

$\mathcal{O}.\text{Upd}\tilde{C}$

2. find $(\tilde{C}_e, e) \in \tilde{\mathcal{L}}$

3. return $\tilde{C}_e$

**Fig. 2.** Our reduction $\mathcal{B}$ for proof of th. **1** in hybrid $i$. $\text{inf}$ encodes fixed programming information: it marks two set elements $(\text{inf}_1, \text{inf}_2)$ sampled with $\mathcal{O}.\text{Sample}$. $\text{inf}_1$ is the randomness used during encryption and $\text{inf}_2$ is the ciphertext value in epoch $\text{fwl}_i$. $\text{ors}$ refers to the set $\{\mathcal{O}.\text{Enc}, \mathcal{O}.\text{Next}, \mathcal{O}.\text{Upd}, \mathcal{O}.\text{Corr}\}$. $\bowtie$ indicates that $\Delta_0$ and $\Delta_{\text{fwr}_i+1}$ are skipped in the computation.
B in these epochs) and stores $(s, t)$ in its memory for later use. To respond to O. Upd queries in these epochs, B computes $C_e = k_e \star s$ using the randomness $s$ generated during the first encryption of the input ciphertext.

* An O. Enc query in epoch $e \in \{\text{fwl}_i, \dots, \text{fwr}_i\}$: B queries O. Sample to get a pair $(s, t) \in S^2$ and programs $\pi(\cdot) \leftarrow s$. It sets $C_{\text{fwl}_i} = t$ (so that all ciphertexts will be encrypted under the key $g$ in epoch $\text{fwl}_i$ if O. Sample returns pairs of the form $(s_j, g \star s_j)$) and updates $C_{\text{fwl}_i}$ to the right epoch $e$ using its simulated tokens (remember that B does not know the keys inside the $i$-th insulated region). To respond to O. Upd queries in these epochs, B uses the value $t$ (if $t = g \star s$ then the randomness will still be consistent) generated during the first encryption of the input ciphertext as ciphertext value in epoch $\text{fwl}_i$ and updates $t$ to the right epoch $e$ using its simulated tokens.

During the challenge call, the adversary will provide a ciphertext $\tilde{C}$ which was created during the $c$-th call to O. Enc. The adversary cannot ask for an update of the $c$-th encryption in an epoch $e \ge \text{fwl}_i$, as this would trigger the trivial win condition $[\text{fwl}_i, \text{fwr}_i] \subseteq \mathcal{I}^* \cap \mathcal{C}^* \neq \emptyset$.

To simulate challenge-equal ciphertext in an epoch that is:

* To the left of the $i$-th insulated region: B simulates GAINE. Upd($\tilde{C}$) using tokens that it created itself.

* Within the $i$-th insulated region: B simulates GAINE. Upd($\tilde{C}$) if $b = 1$, and simulates GAINE. Enc($\tilde{M}$) if $b = 0$. More precisely, if O. Sample returns pairs of the form $(s_j, g \star s_j)$, B embeds $g$ to $k_{\text{fwl}_i}$ and $gk_{\text{fwl}_{i-1}}^{-1}$ to $\Delta_{\text{fwl}_i}$. If $b = 0$, the reduction samples $(s, t) \leftarrow O. Sample()$, gives value $s$ to $\pi(N \| \tilde{M})$ and $t$ to $\tilde{C}_{\text{fwl}_i}$ (we want $k_{\text{fwl}_i} = g$) since

$$ \tilde{C}_{\text{fwl}_i} = \text{GAINE.Enc}(\tilde{M}) = k_{\text{fwl}_i} \star \pi(N \| \tilde{M}) $$

If $b = 1$, assume that $\tilde{C}$ is an update of $\tilde{C}_{\text{ec}}$, the output of the $c$-th O. Enc query. B sampled $(s, t) \leftarrow O. Sample()$ and used $s$ as randomness to create $\tilde{C}_{\text{ec}}$ and to update it in epochs $e < \text{fwl}_i$. The reduction gives value $t$ to $\tilde{C}_{\text{fwl}_i}$ (we want $\Delta_{\text{fwl}_i} = gk_{\text{fwl}_{i-1}}^{-1}$) since

$$ \tilde{C}_{\text{fwl}_i} = \text{GAINE. Upd}(\tilde{C}) = \Delta_{\text{fwl}_i} \star (k_{\text{fwl}_{i-1}} \star s) $$

Furthermore, the reduction uses tokens $\Delta_{\text{fwl}_{i+1}}, \dots, \Delta_{\text{fwr}_i}$ to update $\tilde{C}_{\text{fwl}_i}$ to simulate all challenge ciphertexts in epochs within the insulated region.

* To the right of the $i$-th insulated region: B simulates GAINE. Enc($\tilde{M}$) using the keys that it created itself.

Eventually, B receives the output bit $b'$ from $\mathcal{A}_i$. If $b' = b$, then B guesses that O. Sample returned pairs of the form $(s_j, g \star s_j)$ (returns 0 to the wk-PR challenger), otherwise, B guesses that it has seen uniformly chosen pairs of set elements (returns 1). If B receives an oracle O. Sample that samples pairs of the form $(s_j, g \star s_j)$, then B perfectly simulates the environment of $\mathcal{A}_i$ in $\mathcal{G}_i^b$. If B
receives an oracle $\mathcal{O}$.Sample that samples pairs uniformly at random, then $\mathcal{B}$ wins with probability $1/2$. We have

$$ 
\begin{aligned}
\mathbf{Adv}_{\mathcal{G},\mathcal{A},\mathcal{B}}^{\text{wk-PR}}(\lambda) &= \left|1/2 - \Pr[\mathbf{Exp}_{\mathcal{G},\mathcal{A},\mathcal{B}}^{\text{wk-PR-0}} = 1]\right| \\
&= \left|1/2 - \left(1/2 \Pr[\mathcal{G}_i^0 = 0] + 1/2 \Pr[\mathcal{G}_i^1 = 1]\right)\right| \\
&= \left|1/2 - 1/2(1 - \Pr[\mathcal{G}_i^0 = 1]) - 1/2 \Pr[\mathcal{G}_i^1 = 1]\right| \\
&= 1/2 \left|\Pr[\mathcal{G}_i^0 = 1] - \Pr[\mathcal{G}_i^1 = 1]\right|
\end{aligned}
$$

Finally, we get

$$ 
\begin{aligned}
\frac{1}{(n+1)^2} \mathbf{Adv}_{\text{GAINE},\mathcal{A}}^{\text{detIND-UE-CPA}}(\lambda) &\le \sum_{i=1}^{\ell} |\Pr[\mathcal{G}_i^1 = 1] - \Pr[\mathcal{G}_i^0 = 1]| \\
&= 2\ell \mathbf{Adv}_{\mathcal{G},\mathcal{A},\mathcal{B}}^{\text{wk-PR}}(\lambda) \\
&\le 2(n+1) \mathbf{Adv}_{\mathcal{G},\mathcal{A},\mathcal{B}}^{\text{wk-PR}}(\lambda)
\end{aligned}
$$

Thus, $\mathbf{Adv}_{\text{GAINE},\mathcal{A}}^{\text{detIND-UE-CPA}}(\lambda) \le 2(n+1)^3 \mathbf{Adv}_{\mathcal{G},\mathcal{A},\mathcal{B}}^{\text{wk-PR}}(\lambda)$.

## Appendix F detIND-UE-CCA security of GAINE

In [9, sec. 5.1.1], a variant of SHINE with added ciphertext integrity, called SHINE0, is given by using $N \| M \|_0^t$, for some $t$, as input of the permutation $\pi$ during encryption and by checking that the 0 string is still present during decryption (if not $\perp$ is returned). This version of SHINE is shown to be detIND-UE-CCA secure under CDH [9, th. 5]. We define GAINE0 (see Fig. 6) similarly to SHINE0 and prove that it is detIND-UE-CCA secure if the group action is weakly unpredictable. Informally, $(G, S, \star)$ is weakly unpredictable if, given polynomially many tuples of the form $(s_i, g \star s_i)$ where $g \stackrel{\$}{\leftarrow} G$ and each $s_i \stackrel{\$}{\leftarrow} S$, there is no PPT adversary that can compute $g \star s^*$ for a given challenge $s^* \stackrel{\$}{\leftarrow} S$. A full proof and precise definitions are given in Appendix F.1.

The problematic ciphertext expansion of SHINE0 is reduced to almost nothing in the construction of OCBSHINE of [9, sec. 5.1.3] which is inspired by the authenticated encryption scheme OCB [32]. Once again, we can adapt this construction to GAINE.

That being said, finding a post-quantum instantiation for GAINE0 would make it the first post-quantum detIND-UE-CCA UE scheme. Indeed, the two LWE-based schemes of Jiang [22] and Nishimaki [28] are only randIND-UE-CPA secure. Finally, it is also worth noting that [9, Th. 2.2, 2.4 & 2.6] showed that detIND-UE-CCA security implies the detIND-ENC-CCA and detIND-UPD-CCA security of [24], so GAINE0 is also CCA secure in the [24] sense.

We now give the remaining details needed to understand the CCA security definitions for UE and the proof of the detIND-UE-CCA security of GAINE0.
## F.1 Weakly unpredictable group actions

Let $\mathcal{G}\mathcal{A}$ be a group action family.

**Definition 4 (Weak Unpredictable Group Action [2]).** Let $(G, S, \star)$ be $\mathcal{G}\mathcal{A}(\lambda)$ for some security parameter $\lambda$. Let $\mathcal{D}_G$ and $\mathcal{D}_S$ be distributions on $G$ and $S$ respectively. For $g \in G$, let $\pi_g: S \to S$ be the permutation defined by $\pi_g: s \mapsto g \star s$. For a permutation $f \in \mathcal{G}(S)$, we use $f^\$$ to denote the randomized oracle that, when queried, samples $s \leftarrow \mathcal{D}_S$ and outputs $(s, f(s))$. We say that $(G, S, \star)$ is $(\mathcal{D}_G, \mathcal{D}_S)$-weakly unpredictable if, for all PPT adversaries $\mathcal{A}$, we have:

$$ \mathbf{Adv}_{\mathcal{G}\mathcal{A},\mathcal{A}}^{\text{wk-UP}}(\lambda) := \Pr[\mathcal{A}^{\pi_g^\$}(s^*) = \pi_g(s^*)] \le \text{negl}(\lambda) $$

where $g \leftarrow \mathcal{D}_G$ and $s^* \leftarrow \mathcal{D}_S$. We denote this experiment by $\mathbf{Exp}_{\mathcal{G}\mathcal{A},\mathcal{A}}^{\text{wk-UP}}$.

Informally, $(G, S, \star)$ is $(\mathcal{D}_G, \mathcal{D}_S)$-weakly unpredictable if, given polynomially many tuples of the form $(s_i, g \star s_i)$ where $g \leftarrow \mathcal{D}_G$ and each $s_i \xleftarrow{\$} \mathcal{D}_S$, there is no PPT adversary that can compute $g \star s^*$ for a given challenge $s^* \leftarrow \mathcal{D}_S$. If both distributions are uniform, we simply speak of a weakly unpredictable group action.

## F.2 Ciphertext integrity game: definitions and composition result

We follow the presentation of [9]. In the ciphertext integrity (CTXT) game, the adversary is given access to oracles $\mathcal{O}.Enc$, $\mathcal{O}.Next$, $\mathcal{O}.Upd$ and $\mathcal{O}.Corr$. At some point $\mathcal{A}$ attempts to provide a ciphertext forgery via the oracle $\mathcal{O}.Try$ defined in Fig. 3. $\mathcal{A}$ wins the game if its forgery is valid, i.e.,, if it decrypts to a message and not $\perp$. If $\mathcal{A}$ is allowed to ask a single $\mathcal{O}.Try$ query, we speak of the INT-CTXT$^s$ notion. If $\mathcal{A}$ can send multiple $\mathcal{O}.Try$ queries, we speak of the INT-CTXT notion instead. INT-CTXT$^s$ and INT-CTXT are proved to be equivalent in [9, Lemma 1]. Thus, we only define the INT-CTXT$^s$ advantage (in Definition 5).

$\mathcal{O}.Try(\tilde{C})$
1. **if** phase = 1
2. **return** $\perp$
3. **phase** $\leftarrow 1$
4. **if** $e \in \mathcal{K}^*$ **or** $\tilde{C} \in \mathcal{L}^*$
5. **twf** $\leftarrow 1$
6. **M** **or** $\perp \leftarrow \text{UE.Dec}(k_e, \tilde{C})$
7. **if** $M \neq \perp$
8. **win** $\leftarrow 1$

<caption>Fig. 3. The oracle $\mathcal{O}.Try$ for the INT-CTXT$^s$ security notion.</caption>
**Definition 5 ([9]).** Let UE = {UE.KeyGen, UE(TokenGen, UE.Enc, UE.Dec, UE.Upd} be an UE scheme. The INT-CTXT<sup>s</sup> advantage of an adversary A against UE is defined as

$$ \mathbf{Adv}_{\text{UE},A}^{\text{INT-CTXT}^s}(\lambda) := \Pr[\mathbf{Exp}_{\text{UE},A}^{\text{INT-CTXT}^s} = 1] $$

where the experiment $\mathbf{Exp}_{\text{UE},A}^{\text{INT-CTXT}^s}$ is given in Fig. 4.

$$ \mathbf{Exp}_{\text{UE},A}^{\text{INT-CTXT}^s}(\lambda) $$

1. do UE.setup(1<sup>λ</sup>)

2. win ← 0

3. A<sup>○.Enc,○.Next,○.Upd,○.Corr,○.Try</sup>(λ)

4. if twf = 1

5. win ← 0

6. return win

**Fig. 4.** The INT-CTXT<sup>s</sup> experiment for UE scheme UE and adversary A. Trivial win conditions are discussed in Appendix F.2.

*Trivial wins in ciphertext integrity games.* Recall that our UE schemes all have deterministic updates, we follow the analysis of [9,23]. The adversary can corrupt an epoch key and use it to forge ciphertexts in this epoch. Thus, we exclude this trivial win by setting twf to 1 when the adversary provides a forgery in an epoch in $K^*$.

Next, suppose that the adversary knows a ciphertext $(C, e_1) \in \mathcal{L}$ and tokens from epoch $e_1+1$ to epoch $e_2$. Then, updating $C$ to epoch $e_2$ provides a forgery in epoch $e_2$. We exclude this trivial wins by defining $\mathcal{L}^*$ to be the extended set of $\mathcal{L}$ in which the adversary has learned or inferred information via token corruption. If $\mathcal{O}$.Try receives a ciphertext of $\mathcal{L}^*$, it sets twf to 1. We give an algorithm of [9] to compute $\mathcal{L}^*$ during the game in Fig. 5.

*Composition result for CPA, CTXT and CCA security.* In [9, Theorem 3], the authors show the following generic composition result for UE: CPA + CTXT $\Rightarrow$ CCA. We will use this result to prove that GAINE can be made detIND-UE-CCA secure. This is the first post-quantum UE scheme to attain this security notion.

## F.3 GAINE with zeros: GAINE0

We add ciphertext integrity to GAINE using the technique of [9, sec. 5.1.1] for their SHINE0 scheme. Take message space $\mathcal{M} = \{0, 1\}^m$ and nonce space $\mathcal{N} = \{0, 1\}^v$. Let $(G, S, \star)$ be a MEGA with permutation $\pi : \{0, 1\}^{m+v+t} \to S$. The encryption algorithm of GAINE0 feeds as input to $\pi$ the concatenation of the message, the random nonce, and a zero string of length $t$. The decryption returns $\perp$ if the decrypted value does not end with $0^t$. GAINE0 is defined in Fig. 6
Update $\mathcal{L}^*$

1. if $\mathcal{O}.Enc$ or $\mathcal{O}.Upd$ happens

2. $\mathcal{L}^* \leftarrow \mathcal{L}^* \cup \{(\cdot, C, \cdot)\}$

3. if $\mathcal{O}.Corr$(token, ·) happens

4. for $i \in \mathcal{T}^*$

5. for $(j, C_{i-1}, i - 1) \in \mathcal{L}^*$

6. $C_i \leftarrow \text{UE}\cdot\text{Upd}(\Delta_i, C_{i-1})$

7. $\mathcal{L}^* \leftarrow \mathcal{L}^* \cup \{(j, C_i, i)\}$

<figure><img src="image_5.png" /><figcaption>Fig. 6. GAINE0: our generalization of the SHINE0 scheme using group actions.</figcaption></figure>
## F.4 GAINE0 is INT-CTXTS

We prove the following theorem.

**Theorem 1 (GAINE0 is INT-CTXTS).** Let GAINE0 be the UE scheme described in Fig. 6 for a MEGA family $GA$. For any ideal cipher model adversary $A$ that makes at most $Q_E$ encryption queries before calling $O$. Try, there exists a reduction $B$ such that

$$ \mathbf{Adv}_{\text{GAINE0},A}^{\text{INT-CTXTS}}(\lambda) \le \mathcal{O}(1)Q_E(n+1)^2 \mathbf{Adv}_{\text{GA},B}^{\text{wk-UP}}(\lambda) + \text{negl}(\lambda) $$

where $\mathbf{Adv}_{\text{GA},B}^{\text{wk-UP}}(\lambda)$ is defined in Definition 4

*Remark 1.* Combining the results of [9, Theorem 3], Theorem 1 and Theorem 1, we have that GAINE0 is detIND-UE-CCA.

We follow the proof technique of [9] and its presentation.

*Proof method.* The challenger of the INT-CTXTS game keeps a list of consistent values for ciphertexts, i.e.,, the underlying permutation output. Let $\tilde{C}$ be a forgery attempt sent to $O$. Try in epoch $\tilde{e}$ and let $\tilde{c} := k_{\tilde{e}}^{-1} \star \tilde{C}$ be the underlying permutation output.

1. If $\tilde{c}$ is a new value, since $\pi$ is a random permutation, then the INT-CTXTS challenger simulates $\pi^{-1}(\tilde{c})$ to be a random string. The probability that this string ends by $0^t$ is negligible, and this carries over to the probability that the adversary wins the INT-CTXTS game.

2. If $\tilde{c}$ already exists, suppose that this happens with probability $p$. We construct a reduction $B$ playing the wk-UP game such that it wins with probability $p/(Q_E(n+1)^2)$. $B$ guesses the location of the firewalls around the challenge epoch, embeds the wk-UP values and simulates the INT-CTXTS game, using any successfully-forged ciphertext to compute the group action forgery for its wk-UP challenger.

*Proof.* The following proof is practically the same as in [9], we just replaced exponentiations by group actions and CDH by wk-UP. We give the proof of [9] for completeness.

Note that the probability of a random string ends by $0^t$ is $1/2^t$. In the INT-CTXTS game, the adversary ultimately sends a forgery $C^*$ to the $O$. Try oracle. If the trivial win condition does not trigger, then $C^*$ is a new ciphertext to the challenger and there exists an insulated region around the challenge epoch. We split the proof into two parts on if $k_e^{-1} \star C^*$ is a new value to the challenger:

1. If $k_e^{-1} \star C^*$ is a new value, the random permutation $\pi^{-1}$ will pick a random string $a$ as the output of $\pi^{-1}(k_e^{-1} \star C^*)$. The probability of $a$ ending with $0^t$ is upper bounded by $1/2^t$.
2. If $k_e^{-1} \star C^*$ is an existing value, denote this event as $E_3$, we claim that the probability of $E_3$ happens is very low. Which means it is hard to provide a valid forgery with a known permutation value. In other words, without the knowledge of the encryption key, it is difficult to provide a correct group action. Formally, we prove the following inequality in Lemma 1:

$$ \Pr[E_3] := \Pr[k_e^{-1} \star C^* \text{ exists, } C^* \text{ is new}] \le Q_E(n+1)^2 \mathbf{Adv}_{\mathcal{G},A}^{\text{wk-UP}} $$

In order to analyze the security, we define some events:

* $E_1 := \{C^* \text{ is new}\}$,

* $E_2 := \{k_e^{-1} \star C^* \text{ is new, } C^* \text{ is new}\}$,

* Recall $E_3 := \{k_e^{-1} \star C^* \text{ exists, } C^* \text{ is new}\}$.

Denote the experiment $\mathbf{Exp}_{\text{GAINE0},A}^{\text{INT-CTXT}^s}$ to be $\mathbf{Exp}$. We have:

* $\Pr[\mathbf{Exp} = 1 | \neg E_1] = 0$.

* We proved $\Pr[\mathbf{Exp} = 1 | E_2] \le 1/2^t$ in part 1.

* Events $\neg E_1, E_2, E_3$ are disjoint from each other, so $\Pr[\neg E_1] + \Pr[E_2] + \Pr[E_3] = 1$.

* We prove $\Pr[E_3] \le Q_E(n+1)^2 \mathbf{Adv}_{\mathcal{G},A}^{\text{wk-UP}}$ in Lemma 1. Applying the above properties, we can compute the INT-CTXT$^s$ advantage

$$ \begin{aligned} \mathbf{Adv}_{\text{GAINE0},A}^{\text{INT-CTXT}^s}(\lambda) &= \Pr[\mathbf{Exp} = 1] \\ &= \Pr[\mathbf{Exp} = 1 | \neg E_1] \cdot \Pr[\neg E_1] + \Pr[\mathbf{Exp} = 1 | E_2] \cdot \Pr[E_2] \\ &\quad + \Pr[\mathbf{Exp} = 1 | E_3] \cdot \Pr[E_3] \\ &= \Pr[\mathbf{Exp} = 1 | E_2] \cdot \Pr[E_2] + \Pr[\mathbf{Exp} = 1 | E_3] \cdot \Pr[E_3] \\ &\le \Pr[\mathbf{Exp} = 1 | E_2] + \Pr[E_3] \\ &\le 1/2^t + Q_E(n+1)^2 \mathbf{Adv}_{\mathcal{G},A}^{\text{wk-UP}} \end{aligned} $$

**Lemma 1.** Let $\mathcal{A}$ be the MEGA family used in GAINE0. Let $\mathcal{A}$ be an INT-CTXT$^s$ adversary against GAINE0 that asks at most $Q_E$ queries to $\mathcal{O}$.Enc before it sends its $\mathcal{O}$.Try query. Suppose that $\tilde{C}$ is a forgery attempt provided by $\mathcal{A}$ and that its corresponding permutation value is $\tilde{c}$. Define $E$ to be the event that $\tilde{c}$ is an existed value but $\tilde{C}$ is a new one. Then, there exists a reduction $\mathcal{B}$ such that

$$ \Pr[E] \le Q_E(n+1)^2 \mathbf{Adv}_{\mathcal{G},\mathcal{B}}^{\text{wk-UP}} $$

*Proof.* Suppose that $\mathcal{A}$ is an adversary against INT-CTXT$^s$, and that it can provide a forgery such that $\tilde{C}$ is a new ciphertext but the underlying permutation value is an existing one with probability $\Pr[E]$. We give a reduction $\mathcal{B}$, in Fig. 7, that wins the wk-UP game with probability $\Pr[E]/(Q_E(n+1)^2)$.

$\mathcal{B}$ guesses the location of firewalls (fwl and fwr) around the epoch when $\mathcal{O}$.Try is queried. Furthermore, it guesses which message (the h-th encryption) will be the underlying message of the forgery. Then, $\mathcal{B}$ receives the wk-UP values $(G, S, \star)$, $\mathcal{O}$.Sample and $s^*$, where $\mathcal{O}$.Sample returns tuples of the form $(s_i, g \star s_i)$
Reduction $\mathcal{B}$ playing

$\mathbf{Exp}_{\mathcal{G},\mathcal{A},\mathcal{B}}^{\mathrm{wk-UP}}(\lambda)$

1. receive $(G, S, \star)$,
   $\mathcal{O}$.Sample and $s^*$

2. do Setup$(1^\lambda)$

3. $\mathcal{A}^{\mathrm{ors}}(\lambda)$

4. if ABORT occurred or
   twf = 1

5. win $\leftarrow 0$

6. else

7. return win

Setup$(1^\lambda)$

1. pp $\leftarrow$ GAINE0 Gibb's Setup$(1^\lambda)$

2. $k_0 \leftarrow$
   GAINE0.KeyGen(pp)

3. $\Delta_0 \leftarrow \bot$

4. e, c, phase, win, twf $\leftarrow 0$

5. $\mathcal{L}^*, \mathcal{K}, \mathcal{T} \leftarrow \emptyset$

6. $\hat{\mathrm{fwl}}, \hat{\mathrm{fwr}} \stackrel{\$}{\leftarrow} \{0, \dots, n\}$

7. $h \stackrel{\$}{\leftarrow} \{1, \dots, Q_E\}$

8. for $j \in \{0, \dots, \hat{\mathrm{fwl}} - 1\} \cup \{\hat{\mathrm{fwr}} + 1, \dots, n\}$ do

9. $k_j \stackrel{\$}{\leftarrow} G; \Delta_j \leftarrow k_j k_{j-1}^{-1} \mathop{\&}^\infty$

10. for $j \in \{\hat{\mathrm{fwl}}+1, \dots, \hat{\mathrm{fwr}}\}$ do

11. $\Delta_j \stackrel{\$}{\leftarrow} G$

$\mathcal{O}.\mathrm{Enc}(M)$

1. $c \leftarrow c + 1$

2. if $c = h$

3. if $e < \hat{\mathrm{fwl}}$

4. $\pi(N \| M \| 0^t) \leftarrow s^*$

5. $C_e \leftarrow k_e \star s^*$

6. else

7. return ABORT

8. else

9. $(\inf_1, \inf_2) \leftarrow \mathcal{O}.\mathrm{Sample}()$

10. if $e \in \{0, \hat{\mathrm{fwl}} - 1\} \cup \{\hat{\mathrm{fwr}} + 1, \dots, n\}$

11. $\pi(N \| M \| 0^t) \leftarrow \inf_1$

12. $C_e \leftarrow k_e \star \inf_1$

13. else

14. $C_{\hat{\mathrm{fwl}}} \leftarrow \inf_2$

15. for $j \in \{\hat{\mathrm{fwl}} + 1, \dots, e\}$ do

16. $C_j \leftarrow \Delta_j \star C_{j-1}$

17. $\inf \leftarrow (\inf_1, \inf_2)$

18. $\mathcal{L}^* \leftarrow \mathcal{L}^* \cup \{(c, C_e, e; \inf)\}^>$

19. return $C_e$

$\mathcal{O}.\mathrm{Next}$

1. $e \leftarrow e + 1$

$\mathcal{O}.\mathrm{Upd}(C_{e-1})$

1. if $(c, C_{e-1}, e-1; \inf) \notin \mathcal{L}^*$

2. return $\bot$

3. if $c = h$

4. if $e < \hat{\mathrm{fwl}}$

5. $C_e \leftarrow \Delta_e \star C_{e-1}$

6. else

7. return ABORT

8. else

9. if $e \in \{1, \dots, \hat{\mathrm{fwl}} - 1\} \cup \{\hat{\mathrm{fwr}} + 1, \dots, n\}$

10. $(\inf_1, \inf_2) \leftarrow \inf$

11. $C_e \leftarrow k_e \star \inf_1$

12. else

13. $(\inf_1, \inf_2) \leftarrow \inf$

14. $C_{\hat{\mathrm{fwl}}} \leftarrow \inf_2$

15. for $j \in \{\hat{\mathrm{fwl}} + 1, \dots, e\}$ do

16. $C_j \leftarrow \Delta_j \star C_{j-1}$

17. $\mathcal{L}^* \leftarrow \mathcal{L}^* \cup \{(c, C_e, e; \inf)\}^>$

18. return $C_e$

$\mathcal{O}.\mathrm{Corr}(\mathrm{inp}, \hat{e})$

1. do

Check inp, $\hat{e}$; e; $\hat{\mathrm{fwl}}, \hat{\mathrm{fwr}}$

2. if inp = key

3. $\mathcal{K} \leftarrow \mathcal{K} \cup \{\hat{e}\}$

4. return $k_e$

5. if inp = token

6. $\mathcal{T} \leftarrow \mathcal{T} \cup \{\hat{e}\}$

7. for $i \in \mathcal{T}^*$ do

8. for $(j, C_{i-1}, i - 1; \inf) \in \mathcal{L}^*$ do

9. $C_i \leftarrow \mathcal{O}.\mathrm{Upd}(C_{i-1})$

10. $\mathcal{L}^* \leftarrow \mathcal{L}^* \cup \{(j, C_i, i; \inf)\}$

11. return $\Delta_{\hat{e}}$

$\mathcal{O}.\mathrm{Try}(\tilde{C})$

1. if phase = 1

2. return $\bot$

3. phase $\leftarrow 1$

4. if $\tilde{e} \in \mathcal{K}^*$ or $\tilde{C} \in \mathcal{L}^*$

5. twf $\leftarrow 1$

6. if $\tilde{e} \notin \{\hat{\mathrm{fwl}}, \dots, \hat{\mathrm{fwr}}\}$

7. twf $\leftarrow 1$

8. $y \leftarrow (\prod_{e=\tilde{e}}^{\hat{\mathrm{fwl}}+1} \Delta_e^{-1}) \star \tilde{C}$

9. output $y$ to $\mathbf{Exp}_{\mathcal{G},\mathcal{A},\mathcal{B}}^{\mathrm{wk-UP}}$; get $b$

10. win $\leftarrow b$

**Fig. 7.** Our reduction $\mathcal{B}$ for proof of Lemma 1. *ors* refers to the set $\{\mathcal{O}.\mathrm{Enc}, \mathcal{O}.\mathrm{Next}, \mathcal{O}.\mathrm{Upd}, \mathcal{O}.\mathrm{Corr}, \mathcal{O}.\mathrm{Try}\}$. $\bowtie$ indicates that $\Delta_0$ and $\Delta_{\hat{\mathrm{fwr}}+1}$ are skipped in the computation. $>$ indicates that $\inf$ is empty when $c = h$.
for a fixed $g \stackrel{\$}{\leftarrow} G$ and $s_i \stackrel{\$}{\leftarrow} S$. $\mathcal{B}$ embeds $g$ (the group element used in $\mathcal{O Sample}$) to $k_{\hat{\text{fwl}}}$ by using the elements sampled by $\mathcal{O Sample}$ as ciphertexts in epoch $\hat{\text{fwl}}$. On the $h$-th encryption, $\mathcal{B}$ embeds $s^*$ to $\pi(N\|M\|0^t)$. When $\mathcal{B}$ receives a forgery $\tilde{C}$ for the $h$-th encryption in epoch $\tilde{e} \in \{\hat{\text{fwl}}, \dots, \hat{\text{fwr}}\}$, it can downgrade $\tilde{C}$ to epoch $\hat{\text{fwl}}$ (where it embedded $g$ to the epoch key). Then, $(\prod_{e=\tilde{e}}^{\hat{\text{fwl}}+1} \Delta_e^{-1}) \star \tilde{C} = g \star s^*$ with probability $\text{Pr}[E]/(Q_E(n+1)^2)$, which is the advantage of winning the $\text{Exp}_{\mathcal{G}, \mathcal{A}, \mathcal{B}}^{\text{wk-UP}}$ game.

## F.5 Dealing with bad ciphertext expansion

The problematic ciphertext expansion of SHINE0 is reduced to almost nothing in the construction of OCBSHINE of [9, sec. 5.1.3] which is inspired by the authenticated encryption scheme OCB [32]. Once again, we can adapt this construction and proof to GAINE0 to get the OCBGAINE variant. See [9, Figure 27 & 28] for more details.

# Appendix G Diagram for Triple Orbital Group Actions

We present a diagram to give some intuition about TOGA in Fig. 8.

<figure><img src="image_6.png" /><figcaption>**Fig. 8.** Diagram for a TOGA $A, H, S, \star_A, \sim_A, \star_H$.</figcaption></figure>