Lattice-Based Group Encryption with Full Dynamicity and Message Filtering Policy

Abstract

Group encryption (GE) is a fundamental privacy-preserving primitive analog of group signatures, which allows users to decrypt specific ciphertexts while hiding themselves within a crowd. Since its first birth, numerous constructions have been proposed, among which the schemes separately constructed by Libert et al. (Asiacrypt 2016) over lattices and by Nguyen et al. (PKC 2021) over coding theory are post-quantum secure. Though the last scheme, at the first time, achieved the full dynamicity (allowing group users to join or leave the group in their ease) and message filtering policy, which greatly improved the state-of-affairs of GE systems, its practical applications are still limited due to the rather complicated design, inefficiency and the weaker security (secure in the random oracle model). In return, the Libert et al.’s scheme possesses a solid security (secure in the standard model), but it lacks the previous functions and still suffers from inefficiency because of extremely using lattice trapdoors. In this work, we re-formalize the model and security definitions of fully dynamic group encryption (FDGE) that are essentially equivalent to but more succinct than Nguyen et al.’s; Then, we provide a generic and efficient zero-knowledge proof method for proving that a binary vector is non-zero over lattices, on which a proof for the Prohibitive message filtering policy in the lattice setting is first achieved (yet in a simple manner); Finally, by combining appropriate cryptographic materials and our presented zero-knowledge proofs, we achieve the first lattice-based FDGE scheme in a simpler manner, which needs no any lattice trapdoor and is proved secure in the standard model (assuming interaction during the proof phase), outweighing the existing post-quantum secure GE systems in terms of functions, efficiency and security.

1 Introduction

Group encryption (GE), introduced by Kiayias, Tsiounis and Yung (KTY) [21] as the natural encryption analog of group signature (GS) that was first conceptualized by Chaum and van Heyst [16], is a fundamental anonymity primitive that allows anonymizing valid decryptors within a population of certified users. Since the pioneering work [21], GE has found a wide range of applications (see, e.g., [21, 25, 35]) in filtering malformed encrypted emails, building oblivious retriever storage systems, trusted third parties as well as hierarchical group signatures [42]. Because of the duality, these two primitives share some common design ideas in offering user memberships and generating anonymous signatures/ciphertexts.

In the design of these two anonymity primitives, to build a group of certified users is a key component. In general, there are three types of groups optional for GS: The simplest choice is the static group [6], in which the group population is fixed at the setup phase and the public/private key pairs of group members are assigned by the group manager (GM) as memberships; The partially dynamic group [7, 22, 40] is then introduced to support dynamic and concurrent user enrollments but deny membership revocation. In such a group, a prospective user generates a key pair on his own, and then becomes a valid group member only when his application for joining the group is accepted by the GM, who computes a signature on user’s public key and returns it back as the membership. Despite an essential functionality, support for membership revocation is quite challenging to realize in an efficient manner, since it requires that the signing algorithm is disabled for revoked users and no significant increase for workloads of other parties (i.e., managers, non-revoked users and verifiers) is seen. To address this problem, several approaches [8, 11, 12, 36] have been suggested, resulting into the fully dynamic groups [9], where membership revocation is additionally allowed.

Unlike the context of group signature, the GE always uses the partially dynamic group in its design since its first formalization [21] for security reasons. This type of group allows prospective users dynamically and concurrently to join the group, but any valid application for revoking membership is rejected, which is quite unsatisfactory in the realistic world. In fact, group signatures with full dynamicity have attracted much attention and have been constructed both on pairing assumptions [28, 33] and lattice assumptions [31]. To change this situation, in PKC 2021, Nguyen et al. [35] first considered the full dynamicity in the context of group encryption and proposed a code-based instantiation secure in the random oracle model. In their design, they also first considered the message filtering policies which are quite useful for practical applications of GE systems. However, their formalization of FDGE is adapted directly from that of fully dynamic group signature [9] and hard to understand. Moreover, the construction is rather complicated and inefficient even in the random oracle model. Therefore, it is encouraging to design a group encryption that captures the full dynamicity, message filtering policy and a solid security in a relatively simple manner.

Our Contributions. Motivated by the above discussion, we reconsider the full dynamicity in the context of group encryption, and propose a lattice-based instantiation in a simpler manner that shares the same functions as the existing FDGE scheme [35] and meanwhile outweighs all available post-quantum secure schemes [25, 35] in terms of functions, efficiency and security. Our contributions are summarized as follows:

• By introducing appropriate ingredients into the KTY model that supports dynamic user enrollments but denies membership revocations, we re-formalize the model and security requirements of FDGE that are essentially equal to but more succinct and understandable than the currently existing model.

• We provide a generic and efficient zero-knowledge proof method for demonstrating that some binary vector is non-zero over lattices, on which we first achieve a lattice-based proof (also generic and efficient) for Prohibitive message filtering policy. Both proofs will serve for our subsequent construction.

• By making use of appropriate cryptographic materials and the presented zero-knowledge proofs, we achieve the first lattice-based group encryption secure in the standard model and with full dynamicity in a free-of-trapdoor manner, which meets our formalized model and outweighs all existing post-quantum secure GE schemes in terms of functions and efficiency.

Related Work. The privacy-preserving cryptography has been an extremely active research area in the last decades. As one of the fundamental anonymity primitives, group encryption thus has attracted noticeable attention in recent years. The relevant concepts and definitions were first introduced by Kiayias, Tsiounis and Yung [21], who also then put forth a modular design consisting of zero-knowledge proofs, digital signatures (e.g., [13]) and anonymous CCA2-secure public-key encryptions (e.g., [37]). Later, Cathalo et al. [15] designed a non-interactive scheme in the standard model for the goal of optimizing the number of rounds. Similarly, over weaker assumptions, Aimani et al. [1] proposed more practical schemes by utilizing succinct approaches to protect the identity of group members. For sake of balancing better privacy vs. safety, Libert et al. [29] supposed a variant with public traceability to specific ciphertexts, which was inspired from traceable signatures [20]. Further, to strengthen secrecy, Izabachène et al. [19] constructed traceable variants that are free of subliminal channels, stressing confidentiality, anonymity and traceability. However, all these instantiations are proposed over number-theoretic assumptions and are vulnerable under quantum attacks. This situation has been unchanged until Libert et al. [25] proposed the currently only existing lattice-based scheme recently.

What should be noted out is that, all the group encryptions discussed above only offer partial dynamicity that allows concurrent user enrollments but denies membership revocations, which is quite unsatisfactory in the most realistic applications. To end this situation, more currently, Nguyen et al. [35] proposed a fully dynamic group encryption scheme secure in the random oracle from coding theory, where they also achieved the message filtering policies. However, their model is directly adapted from that of fully dynamic group signature [9] and is tedious. Moreover, the proposed scheme is rather complicated and inefficient together with provable security in the random oracle model. This motivates us to construct a fully dynamic group encryption, in a simple manner, that share practical functions similar to the scheme [35] while obtaining high efficiency and solid security (against quantum attacks).

Organization. In the forthcoming sections, we briefly recall the needed lattice techniques and cryptographic blocks in Sect. 2. The formalized model of FDGE is given in Sect. 3. Section 4 describes our new techniques used for demonstrating inequalities of binary vectors and the underlying zero-knowledge argument system. In Sect. 5, we describe our scheme that captures all desired properties, of which analysis is given. Finally, Sect. 6 concludes our work.

2 Preliminaries

Notations. For any positive integers $n\ge k$, we denote the set $\{1,...,n\}$ by [n], the set $\{k,...,n\}$ by [k, n]. All vectors are written as bold lower-case letters in the column form, and matrices as bold upper-case letters. For $\mathbf {b}\in \mathbb {R}^n$ and $\mathbf {B}\in \mathbb {R}^{n\times m}$ with columns $(\mathbf{b} _i)_i$, their Euclidean $l_2$ norms are respectively written as $\Vert \mathbf{b} \Vert$ and $\Vert \mathbf{B} \Vert =\text {max}_{i\le m} \Vert \mathbf{b} _i\Vert$. If a given set $\mathcal {S}$ is finite, we let $U(\mathcal {S})$ to denote the uniform distribution over it and use $x \hookleftarrow D$ to represent the sampling action according to the distribution D. For two same-size binary vectors $\mathbf {x}$ and $\mathbf {y}$, we use $d_{H}(\mathbf{x} ,\mathbf{y} )$ to denote their Hamming distance, which is equal to $l_1$ norm $\Vert \mathbf{x} \oplus \mathbf{y} \Vert _1$.

2.1 Lattices and Computational Problems

As in [14, 18], we use the notations L to denote lattices defined by $\varLambda _q^{\bot }(\mathbf {A}):=\{\mathbf{e }\in \mathbb {Z}^m|\ \mathbf{A }\cdot \mathbf{e }=\mathbf{0} ^n \bmod q \}$ or $\varLambda _q^{{ \mathbf {u}}}({\mathbf {A}}):=\{{\mathbf {e}}\in \mathbb {Z}^m|\ \mathrm {\mathbf {A}}\cdot {\mathbf {e}}= {\mathbf {u}} \bmod q \}$ w.l.o.g., where $\mathbf {A}\in \mathbb {Z}_q^{n\times m}$. Accordingly, use the notation $\mathcal {D}_{L,\sigma ,\mathbf{c} }$ to denote the discrete Gaussian distributions of the support L, center $\mathbf {c}\in \mathbb {R}^m$ and parameter $\sigma >0$, which is defined by $\mathcal {D}_{L,\sigma ,\mathbf{c} }(\mathbf{x} )=\frac{\rho _{\sigma ,\mathbf{c} }(\mathbf{x} )}{\rho _{\sigma ,\mathbf{c} }(L)}$ for each $\mathbf {x}\in L$ where $\rho _{\sigma ,\mathbf{c} }(\mathbf{x} )=\text {exp}(-\pi \Vert \mathbf{x} -\mathbf{c} \Vert ^2/\sigma ^2)$ is the Gaussian function over $\mathbb {R}^m$. When $\mathbf {c}=\mathbf{0}$, we also write the Gaussian distributions as $\mathcal {D}_{L,\sigma }$ for short. The following fact ensures that the outputs of the discrete Gaussian distribution are always short.

Lemma 1

([3]) Given any $L\subseteq \mathbb {R}^n$ and $\sigma >0$, Pr$_\mathbf{b\mathbf \hookleftarrow D_{L,\sigma }}[\Vert \mathbf{b}\mathbf \Vert \le \sqrt{n}\sigma ]\ge 1-2^{-\varOmega (n)}$.

For appropriate parameters, the syndrome $\mathbf {u}=\mathbf{A} \cdot \mathbf{e}$ with $\mathbf {A}\in \mathbb {Z}_q^{n\times m}$ and $\mathbf {e}\in \mathbb {Z}_q^{m}$ is nearly uniform over $\mathbb {Z}_q^n$.

Lemma 2

([18]) Given positive integers n, q with q prime, let $m\ge 2n \log q$ and $s\ge \omega (\sqrt{\log m})$. Then for any $\mathrm {\mathbf {A}}\hookleftarrow U(\mathbb {Z}_q^{n\times m})$, the distribution of the syndrome $\mathrm {\mathbf {u}}=\mathrm {\mathbf {A}}\cdot \mathrm {\mathbf {e}} \bmod q$ is within negligible distance to the uniform distribution over $\mathbb {Z}_q^n$, where $\mathrm {\mathbf {e}} \hookleftarrow D_{\mathbb {Z}^m,s}$.

The computational lattice problems and associated hardness claims used in this work are stated as follows.

Definition 1

(SIS). Given appropriate positive integers $n, m,q,\beta$, the SIS$_{n,m,q,\beta }$ problem is defined as: for any A$\hookleftarrow U(\mathbb {Z}_q^{n\times m})$, search a non-zero vector $\mathrm {\mathbf {x}} \in \mathbb {Z}^{m}$ such that $\mathrm {\mathbf {A}}\cdot \mathrm {\mathbf {x}}=\mathrm {\mathbf {0}}$ and $\Vert \mathbf{x} \Vert \le \beta$.

By choosing appropriate parameters, the standard worst-case lattice problem SIVP$_\gamma$ can be reduced to the average-case SIS$_{n,m,q,\beta }$ problem. Such an example is followed by setting $m,\beta =\textsf {poly}(n)$; $q \ge \sqrt{n}\beta$ and $\gamma =\widetilde{\mathcal {O}}(\sqrt{n}\beta )$ (e.g., [2, 18, 32]).

Definition 2

(LWE). Given appropriate positive integers n, m, q, and a probability distribution on $\mathbb {Z}$ denoted as $\chi$. For secret s $\in {\mathbb {Z}_q^{n}}$, define A$_\mathbf{s ,\chi }$ as the distribution generated by sampling $\mathrm {\mathbf {a}}$ $\hookleftarrow U(\mathbb {Z}_q^{n})$ and $e \hookleftarrow \chi$, and returning ($\mathrm {\mathbf {a}}$, $\mathrm {\mathbf {a}}^{\mathrm {{T}}}\cdot$ s$+e)\in {\mathbb {Z}_q^{n}\times \mathbb {Z}_q }$. The goal of LWE$_{n,q,\chi }$ is to distinguish m samples from A$_\mathbf{s , \chi }$ and m samples from $U(\mathbb {Z}_q^{n}\times \mathbb {Z}_q)$, respectively.

For prime power q, one can build a discrete integer distribution $\chi$ bounded by $B\ge \sqrt{n}\omega (\log n)$, for which there exists an efficient reduction from the $\textsf {SIVP}_{\widetilde{\mathcal {O}}(nq/B)}$ problem to the LWE$_{n,q,\chi }$ problem (e.g., [10, 38, 39]).

2.2 LNWX Lattice-Based Accumulators

The LNWX accumulator [31] is an updatable variant opposed to the static counterpart [26], and we will use it in our construction to achieve dynamic group users enrollments and membership revocations. The accumulator is built on a family of hash functions $\mathcal {H}=\{h_\mathrm {\mathbf {A}}|\mathrm {\mathbf {A}}\in \mathbb {Z}_q^{n \times m}\}$ with $\mathrm {\mathbf {A}}=\big [\mathrm {\mathbf {A}}_0|\mathrm {\mathbf {A}}_1\big ]\in \mathbb {Z}_q^{n \times m}$ which hash $(\mathrm {\mathbf {u}}_0, \mathrm {\mathbf {u}}_1)\in (\{0,1\}^{nk})^2$ into $h_\mathrm {\mathbf {A}}(\mathrm {\mathbf {u}}_0, \mathrm {\mathbf {u}}_1)=\mathrm {\textsf {bin}} \big (\mathrm {\mathbf {A}}_0\cdot \mathrm {\mathbf {u}}_0+\mathrm {\mathbf {A}}_1\cdot \mathrm {\mathbf {u}}_1 \bmod q \big )\in \{0,1\}^{nk}$. Its security is ensured by the hardness of the SIS problem.

Informally, as in [4, 12, 36], the accumulator is defined by the algorithms $(\textsf {TSetup},\textsf {TAcc},\textsf {TWitness},\textsf {TVerify},\textsf {TUpdate})$. Namely, for a Merkle-tree with $N=2^{\ell }$ leaves, algorithm TSetup takes a random $\mathbf {A}\in \mathbb {Z}_q^{n \times m}$ to form a hash function $h_\mathbf{A}$; Algorithm TAcc accumulates all values $R=\{\mathrm {\mathbf {d}}_0, ...,\mathrm {\mathbf {d}}_{N-1}\}$ of each length nk on leaves into the root u via the recursive computations shown as $\mathbf {u}_{b_1,...,b_i}=h_\mathbf{A} (\mathbf{u} _{b_1,...,b_i,0}, \mathbf{u} _{b_1,...,b_i,1})$ for any node at depth $i\in [\ell ]$ and $\mathbf {u}=h_\mathbf{A} (\mathbf{u} _0,\mathbf{u} _1)$, where $(b_1,...,b_i)\in \{0,1\}^i$; Algorithm TWitness returns $\perp$ if $\mathbf {d}\notin R$, otherwise computes the witness $w=\big ((j_1,...,j_{\ell }),(\mathbf{u} _{j_1,...,j_{\ell -1},\bar{j_{\ell }}},...,\mathbf{u} _{j_1,\bar{j_2}},\mathbf{u} _{\bar{j_1}})\big )\in \{0,1\}^{\ell }\times \big (\{0,1\}^{nk}\big )^{\ell }$ demonstrating that $\mathbf {d}=\mathbf{d} _j\in R$ for some $j\in [0,N-1]$ with $\textsf {bin}(j)=(j_1,...,j_\ell )$, where $\bar{b}$ denotes the bit $1-b$ for a chosen bit b; Then, given a witness $w=\big ((j_1,...,j_{\ell }),(\mathbf{w} _{\ell },...,\mathbf{w} _1)\big )\in \{0,1\}^{\ell }\times \big (\{0,1\}^{nk}\big )^{\ell }$, and set $\mathbf {v}_\ell =\mathbf{d}$, algorithm TVerify computes the path $\mathbf {v}_{\ell -1},...,\mathbf{v} _{0}\in \{0,1\}^{nk}$ via the recursive formula $\mathbf {v}_i=\bar{j}_{i+1}\cdot h_\mathbf{A} (\mathbf{v} _{i+1},\mathbf{w} _{i+1})+j_{i+1}\cdot h_\mathbf{A} (\mathbf{w} _{i+1},\mathbf{v} _{i+1})$ for any $j\in [0,N-1]$ and $i\in [\ell -1]$ with initial setting $\mathbf {u}=\mathbf{v} _0$; Finally, when a value at position j is replaced by $\mathbf {p}$, algorithm $\textsf {TUpdate}(\textsf {bin}(j),\mathbf{p} )$ efficiently updates the accumulator by simply updating the hash values of nodes on path from the specific leaf to the root, then the algorithm $\textsf {TWitness}$ outputs the updated paths and maintains other values unchanged.

2.3 GPV Dual Encryption

The GPV encryption presented in [18] features the public-key anonymity and is efficient because of being free of lattice trapdoors. We now recall a variant that would be used in our construction. Choose positive integers n and $q\ge 2$ and set $k=\lfloor \log q\rfloor$ and $m=2nk$. Select a random public matrix $\mathbf {A}\in \mathbb {Z}_q^{n\times m}$. Given a Gaussian parameter $\sigma$, a Gaussian distribution $D_{\mathbb {Z}^m,\sigma }$ and an error distribution $\chi ^m$, one samples a short matrix $\mathbf {E}$ from $D_{\mathbb {Z}^m,\sigma }^{m}$ as the secret key $\textsf {sk}$, and computes a corresponding public matrix $\mathbf {U}=\mathbf{A} \cdot \mathbf{E} \in \mathbb {Z}_q^{n\times m}$ as the public key $\textsf {pk}$. To encrypt a message $\mathbf {m}\in \{0,1\}^m$, one samples a random vector $\mathbf {s}\hookleftarrow U(\{0,1\}^n)$ and two random vectors $\mathbf {x},\mathbf{y} \hookleftarrow \chi ^m$ to compute the ciphertext $\mathbf {c}=(\mathbf{c} _1,\mathbf{c} _2)$ as: $\mathbf {c}_1=\mathbf{A} ^{\top }\cdot \mathbf{s} + \mathbf{x} , \mathbf{c} _2=\mathbf{U} ^{\top }\cdot \mathbf{s} + \mathbf{y} +\mathbf{m} \cdot \lfloor \frac{q}{2}\rceil$. When the decryptor wants to recover the message $\mathbf {m}$, he uses the preserved key $\textsf {sk}=\mathbf{E}$ to compute $\lfloor (\mathbf{c} _2-\mathbf{E} ^{\top }\cdot \mathbf{c} _1)/\frac{q}{2}\rceil$.

2.4 Zero-Knowledge Argument of Knowledge

A zero-knowledge argument system of knowledge (ZKAoK) is a two-party interactive protocol, where a prover $\mathcal {P}$ triggers a proof to convince the verifier $\mathcal {V}$ that he knows a witness of the specific statement while not revealing any additional information. More formally, given an NP relation defined by a set of statements-witnesses $R=\{(y,w)\}\in \{0,1\}^*\times \{0,1\}^*$, the associated ZKAoK is defined via an interactive game $\langle \mathcal {P},\mathcal {V}\rangle$ with completeness $\delta _c$ and soundness error $\delta _s$ as:

• Completeness. For any given $(y,w)\in R$, $\mathrm {Pr}[\langle \mathcal {P}(y,w), \mathcal {V}(y)\rangle \ne 1]\le \delta _c$.

• Soundness. Given any $(y,w)\notin R, \forall$ PPT $\widehat{\mathcal {P}}$: $\mathrm {Pr}[\langle \widehat{\mathcal {P}}(y,w), \mathcal {V}(y)\rangle =1]\le \delta _s$.

In the lattice setting, the Stern-like argument system [41] is a generic framework with statistical ZK property and soundness 2/3, and has been widely applied in the constructions of advanced cryptographic schemes [23, 25, 26, 30]. Its key idea is to use “decomposition-extension-permutation" techniques to transform the targeted NP relations into those suitable for the framework, which in general increases double to four times communication cost and makes the system quite inefficient in practice together with soundness 2/3. In this work, we use a currently presented framework referred as Yang et al.’s argument system [43] which uses novel techniques to capture the computational ZK property and an inverse polynomial soundness. Let us recall it below.

The Abstraction of the Argument System. The desired ZKAoK system provided in Sect. 4 is covered within the following abstraction:

$$\begin{aligned} R=\{(\mathbf{M} ,\mathbf{y} ),(\mathbf{x} ): \mathbf{M} \cdot \mathbf{x} = \mathbf{y} \wedge \mathbf{x} \in \textsf {cond}\}, \end{aligned}$$

(1)

where $\mathbf {M}, \mathbf{y}$ are the public matrix and vector, respectively, and the vector $\mathbf {x}$ is the secret witness, additionally $\textsf {cond}$ represents the set of conditions that x should satisfy, which covers all possible constraints such as short vectors, quadratic relations. Actually, the set cond is always equally represented by a set $\mathcal {M}=\{(h,i,j)\}$ consisting of index tuples of x that satisfy the relation $\mathbf {x}[h]=\mathbf{x} [i]\cdot \mathbf{x} [j]$.

3 Model and Security Requirements of Fully Dynamic Group Encryption

In this section, by introducing a time factor and a group updating algorithm into the KTY model [21], also taking less oracles than that of [35], we provide the formalized model and security definitions of the fully dynamic group encryption (FDGE) primitive, which are appropriately upgraded and modified from the KTY model [21] that is only suitable for partially dynamic groups.

Like the KTY model [21], the FDGE also involves several parties: a group manager (GM) that managers a group of users, an opening authority (OA) that is empowered to revoke the anonymity of recipients should the misbehavior arise, and a set of prospective users as well as a sender producing well-formed ciphertexts for certified group members. In the forthcoming model, users join/leave the group under the permission of GM who can regularly edit and publish authentic group information $\textsf {info}_\tau$ at growing epoch $\tau$, thereby anyone can learn the knowledge about changes of the group including, current/excluded group members. Additionally, by comparing two group information $\textsf {info}_{\tau _1}$ and $\textsf {info}_{\tau _2}$ under the convention that $\tau _1 < \tau _2$ if $\textsf {info}_{\tau _1}$ is published before $\textsf {info}_{\tau _2}$, one can even identify revoked users at the recent epoch. The formalized fully dynamic group encryption is defined via the following tuple of algorithms:

• $\textsf {SETUP}(\lambda )$ : This algorithm consists of three procedures and generates group public key $\textsf {gpk}=(\textsf {pp},\textsf {pk}_\textsf {GM},\textsf {pk}_\textsf {OA})$ as follows:

  • SETUP$_\textsf {init}(1^{\lambda })$ : On input the security parameter $\lambda$, output public parameters $\textsf {pp}$.

  • SETUP$_\textsf {GM}(\textsf {pp})$ : Given $\textsf {pp}$, output the GM’s key pair $(\textsf {pk}_\textsf {GM},\textsf {sk}_\textsf {GM})$.

  • SETUP$_\textsf {OA}(\textsf {pp})$ : Given $\textsf {pp}$, output a key pair $(\textsf {pk}_\textsf {OA},\textsf {sk}_\textsf {OA})$ for the OA.

  An interaction occurs between the GM and the OA, successfully creating group public key gpk at its end, while the GM initializes the group information info and the registration table reg.

• UKGEN(pp): On input pp, this algorithm produces a user key pair $(\textsf {pk}_\textsf {U},\textsf {sk}_\textsf {U})$.

• $\langle \textsf {JOIN}(\textsf {sk}_\textsf {U}), \textsf {ISSUE}(\textsf {sk}_\textsf {GM})\rangle (\textsf {info}_{\tau },\textsf {gpk},\textsf {pk}_\textsf {U})$ : This is an interaction run by the GM and a prospective user at epoch $\tau$, whose successful completion enrolls a new group member with an identifier uid and makes the algorithm JOIN and algorithm ISSUE store group member secret key $\textsf {sk}[\textsf {uid}]$ and public key certificate cert$_{\textsf {pk}_\textsf {U}}$ in the table reg with same index, respectively.

• $\textsf {GUPDATE}(\textsf {gpk},\textsf {sk}_\textsf {GM},\textsf {info}_{\tau _{\text {current}}},\mathcal {S},\mathbf{reg} )$ : Given $\textsf {gpk},\textsf {sk}_\textsf {GM},\textsf {info}_{\tau _{\text {current}}}$, table reg, a set $\mathcal {S}$ of active users to be removed, GM runs this algorithm to generate new group information $\textsf {info}_{\tau _{\text {current}}+1}$ and update the table reg, while advancing the epoch and outputting $\perp$ if there is no change to the group.

• $\langle \mathcal {G}_r,\mathcal {R},\textsf {sample}_\mathcal {R}\rangle (\textsf {pp})$ : Given pp, procedure $\textsf {sample}_\mathcal {R}$ samples a statement-witness pair $(x,w)\in \mathcal {R}$ by using the key pair $(\textsf {pk}_\mathcal {R},\textsf {sk}_\mathcal {R})$ itself produced by procedure $\mathcal {G}_r$, where $\textsf {sk}_\mathcal {R}$ may be empty in the most of real realizations.

• $\textsf {ENC}(\textsf {gpk},\textsf {pk}_\textsf {U},\textsf {cert}_\textsf {U}, \textsf {info}_{\tau },x,w,L)$ : This algorithm is executed by sender to compute a group encryption $\varPsi$ on witness w with a label L under some public key $\textsf {pk}_\textsf {U}$. It returns $\perp$ if the target group user is inactive at epoch $\tau$.

• $\textsf {DEC}(\textsf {sk}_\textsf {U},\varPsi ,L)$ : The target receiver decrypts the ciphertext $\varPsi$ via this algorithm.

• $\textsf {OPEN}(\textsf {sk}_\textsf {OA},\textsf {info}_{\tau },\mathbf{reg} ,\varPsi ,L)$ : This algorithm is run by OA to return an identity uid of a group member who has secret information to decrypt the ciphertext together with a proof $\pi$ attributing $\varPsi$ to user uid or to return $(\perp , \pi )$ if it fails to trace the receiver.

• $\langle \mathcal {P}(\textsf {pk}_\textsf {U},\textsf {cert}_\textsf {U},w,coins _\varPsi ),\mathcal {V}(\pi _\varPsi )\rangle (\textsf {gpk},\textsf {info}_{\tau },x,\varPsi ,L)$ : This is an interactive procedure run between sender and verifier which, given inputs, convinces verifier that the ciphertext $\varPsi$ is well-formed and is actually generated for one of active group members at epoch $\tau$. For security requirements, as in [21], the FDGE scheme considers correctness, message secrecy, anonymity and soundness, whose definitions are given via corresponding experiments below, respectively.

Correctness asks that a ciphertext generated by a genuine sender is always decrypted successfully by algorithm DEC, and that procedure OPEN can always identify the receiver, as well as produces a proof that can be accepted by verifier.

Definition 3

The correctness is satisfied if the following experiment returns 1 with negligible probability.

Message Secrecy demands that it is difficult for any PPT adversary to distinguish a ciphertext generated by a random plaintext from a one done by a specific relation pair, even if the adversary can corrupt all parties except the honest receiver via accessing to the following stateful and stateless oracles:

• DEC(sk,$\cdot$): is a stateless decryption oracle with a restriction not to decrypt a ciphertext-label pair $(\varPsi , L)$ termed as $\textsf {DEC}^{\lnot \langle \varPsi , L\rangle }$.

• CH$_\textsf {ror}^{b}$($\lambda$, pk, $\tau ,w, L$): is a one-time oracle used for generating real-or-random challenge ciphertexts according to the choice of coin b at epoch $\tau$. It returns $(\varPsi ,coins _\varPsi )$ with $\varPsi \leftarrow \textsf {ENC}(\textsf {pk}_\textsf {GM}, \textsf {pk}_\textsf {OA}, \textsf {pk}, \textsf {cert}_\textsf {pk}, \textsf {info}_\tau , w,L)$ if $b=1$. Otherwise, return $(\varPsi ,coins _\varPsi )$ with $\varPsi \leftarrow \textsf {ENC}(\textsf {pk}_\textsf {GM}, \textsf {pk}_\textsf {OA}, \textsf {pk}, \textsf {cert}_\textsf {pk}, \textsf {info}_\tau , w',L)$ where $w'$ is a uniformly random plaintext of length $\mathcal {O}(\lambda )$ sampled in the plaintext space, and coins$_\varPsi$ represents the random coins used to compute $\varPsi$.

• PROVE$_\mathcal {P,P'}^{b}(\textsf {pk}_\textsf {GM}, \textsf {pk}_\textsf {OA}, \textsf {pk}, \textsf {cert}_\textsf {pk},\textsf {info}_\tau , x, w, \varPsi , L, coins _\varPsi )$: is a stateful oracle that generates an actual proof $\pi _\varPsi$ or a simulated proof $\pi _\varPsi '$ for epoch $\tau$ by running the real prover $\mathcal {P}$ when $b=1$ and running the simulator $\mathcal {P}'$ else wise. It can be invoked a polynomial number times.

The usage of these oracles describes a experiment where the whole system is under the control of adversary except the member chosen as recipient. It shows the advantage of the adversary in mounting the attack against message secrecy.

Definition 4

The message secrecy is achieved if, for any PPT adversary, the absolute difference of probability of outputting 1 between the following experiments $\mathrm {\mathbf {Exp}}^{\textsf {sec}-1}_\mathcal {A}(\lambda )$ and $\mathrm {\mathbf {Exp}}^{\textsf {sec}-0}_\mathcal {A}(\lambda )$ is negligible.

Anonymity requires that it is infeasible for any PPT adversary to distinguish ciphertexts computed under two valid public keys of its choice, even if it controls the entire system except the OA and two well-behaved users via accessing the following oracles:

• CH$_\textsf {anon}^{b}(\textsf {pk}_\textsf {GM}, \textsf {pk}_\textsf {OA}, \textsf {pk}_0, \textsf {pk}_1,\textsf {info}_\tau , w, L$): is a challenge oracle that returns a pair $(\varPsi , coins _\varPsi )$ consisting of a ciphertext $\varPsi \leftarrow \textsf {ENC}(\textsf {pk}_\textsf {GM}, \textsf {pk}_\textsf {OA}, \textsf {pk}_b, \textsf {cert}_{\textsf {pk}_b}, \textsf {info}_\tau , w, L)$ and the coin tosses coins$_\varPsi$ used for generating $\varPsi$ when a plaintext w and two possible public keys $\textsf {pk}_0,\textsf {pk}_1$ are given.

• USER$(\textsf {pk}_\textsf {GM}, \tau )$: is a stateful oracle that simulates two instantiations of $\textsf {J}_\textsf {user}$ via valid certificates {cert$_{\textsf {pk}_b}\}_{b=0}^1$ supplied by adversarial GM in string keys at epoch $\tau$, where honest outputs termed as $\{(\textsf {pk}_b, \textsf {sk}_b,\textsf {cert}_{\textsf {pk}_b})\}_{b=0}^1$ are stored.

• OPEN($\textsf {sk}_\textsf {OA}, \textsf {info}_\tau ,\mathbf{reg} , \cdot$): is a stateless oracle that executes opening operation on behalf of OA for the received ciphertext and reveals the identity of the receiver.

These above oracles can be used in a experiment that models the anonymity property, which reveals the advantage of adversary in this attack game.

Definition 5

The FDGE scheme satisfies anonymity if, for any PPT adversary, the absolute difference of probability of outputting 1 between the following experiments and is negligible.

Soundness requires that it is infeasible for any PPT adversary to produce a convincing valid ciphertext that opens to unregistered group member or invalid public key, even if it can choose OA’s key, and is given access to the REG oracle. In the following, $\textsf {database}, \mathcal {PK}$ and $\mathcal {C}$ are respectively used to represent the sets of registered public keys, valid keys and valid ciphertexts.

Definition 6

An FDGE scheme is sound if, for any PPT adversary, the experiment below returns 1 with negligible probability.

To meet the above security requirement that pk must belong to the language of valid public keys, we use the Gaussian short vectors as shown in Sect. 5.1 to generate dense space for public keys, which simplifies our definitions.

4 The Underlying Zero-Knowledge Layer

In this section, we first introduce the needed decomposition techniques in Sect. 4.1. Then, we provide two generic and efficient zero-knowledge proofs for inequality relations of binary vectors (one is for non-zero binary vectors, and the other is for Hamming distance) that can work well in any lattice-based ZK framework and serve for our argument system. Finally, based on the techniques prepared in previous sections, we establish the argument system in Sect. 4.3 in the Yang et al.’s framework [43] recalled in Sect. 2.4. The argument system obtains great efficiency gains compared to that run in the Stern-type framework [41] since our system avoids using the “decomposition-extension-permutation” techniques (which at least increases the witness size double to four times) and also avoids repeating the protocol hundreds times (which incurs a drastic increase in communication cost) towards a negligible soundness as in [41].

4.1 Warm-Up: Decompositions

We briefly recall several decomposition techniques from [24, 30] that would be used in constructing our argument system. We start with the integer decomposition function, i.e., for any non-negative integer i, let $\delta _i=\lceil \log (i+1)\rceil$, define $\textsf {bin}(i)=(i^{(1)},...,i^{(\delta _i)})^{\top }\in \{0,1\}^{\delta _i}$ and $\mathbf {g}_{\delta _i}=(1,2,...,2^{\delta _i-1})$, then it follows that $i=\sum _{j=1}^{\delta _i}2^{j-1}\cdot i^{(j)}=\mathbf{g} _{\delta _i}\cdot \textsf {bin}(i)$.

To decompose any integer $i\in [0,\beta ]$ for a positive integer $\beta$, set $\delta _\beta \text {:}=\lceil \log _2 (\beta +1) \rceil$ and compute an integer sequence $\{\beta _1,...,\beta _{\delta _\beta }\}$ via $\beta _j=\lfloor \frac{\beta +2^{j-1}}{2^j}\rfloor , \forall j\in [1,\delta _\beta ]$. Then, we have $i=\sum _{j=1}^{\delta _\beta }\beta _j\cdot i^{(j)}=\mathbf{g} _{\delta _\beta }'\cdot \textsf {bin}'(\beta )$, where $\mathbf {g}_{\delta _\beta }'=(\beta _1,...,\beta _{\delta _\beta })$ and $\textsf {bin}_{\beta }'(i)=(i^{(1)},...,i^{(\delta _\beta )}) \in \{0,1\}^{\delta _{\beta }}$ which is a binary tuple computed in an interactive manner. This defines an integer decomposition function as idec$_\beta (i)=(i^{(1)}, ..., i^{(\delta _\beta )})^{\top }\in \{0,1\}^{\delta _\beta }$ for any integer $i\in [0,\beta ]$. Combining with $\mathbf {H}_{\mathfrak {m},\beta }=\mathbf{I} _\mathfrak {m}\otimes \mathbf{g} _{\delta _\beta }'$, we can similarly define decomposition functions for vectors and matrices (see, [25, 26]):

• vdec$_{\mathfrak {m},\beta }: {[0,\beta ]}^{\mathfrak {m}}\rightarrow \{0,1\}^{\mathfrak {m}\delta _\beta }$ maps any $\beta$-bounded non-negative vector $\mathbf {v}={(v_1,...,v_{\mathfrak {m}})}^{\top }$ to $(\textsf {idec}_\beta {(v_1)}^{\top }\Vert \ ...\ \Vert \textsf {idec}_\beta {(v_{\mathfrak {m}})}^{\top })^{\top }$ by applying $\textsf {idec}_{\beta }(\cdot )$ to each entry of $\mathbf {v}$, which holds that $\mathbf {H}_{\mathfrak {m},\beta }\cdot \textsf {vdec}_{\mathfrak {m},\beta }(\mathbf{v} )=\mathbf{v}$.

• mdec$_{n,m,q}:\mathbb {Z}_q^{m\times n}\rightarrow \{0,1\}^{nm\delta _{q-1}}$ maps a matrix X$=[\mathbf{x} _1|\ ...\ |\mathbf{x} _n]\in \mathbb {Z}_q^{m\times n}$ to the size-$nm\delta _{q-1}$ binary vector ${(\textsf {vedc}_{m,q-1}{(\mathbf{x} _1)}^{\top } \Vert \ ...\ \Vert \textsf {vedc}_{m,q-1}{(\mathbf{x} _{n})}^{\top })}^{\top }$ by imposing $\textsf {vdec}_{m,q-1}(\cdot )$ on the each column of $\mathbf {X}$ and concatenating the obtained binary vectors in the increasing order of the indexes of columns.

We note that, hereunder this section, when needing to decompose a bounded-$\beta$ vector $\mathbf {v}\in [-\beta ,\beta ]^{\mathfrak {m}}$, we will first lift it to $\mathbf {v}+\boldsymbol{\beta }\in [0,2\beta ]^{\mathfrak {m}}$, then perform $\textsf {vdec}_{\mathfrak {m},2\beta }(\cdot )$ on the transformed vector where $\boldsymbol{\beta }=(\beta ,...,\beta )$ consists of $\mathfrak {m}$’s $\beta$, with taking appropriate modifications for the involved matrices and vectors. This transformation-and-decomposition strategy will be quite useful for the construction of our $\textsf {ZK}$ argument system.

4.2 Proving Inequality Relations for Binary Vectors

In this section, we first provide a ZK proof for demonstrating a binary vector p is non-zero (used to demonstrate a group user is activated) that can efficiently work well in any lattice-based ZK framework, on which we construct a ZK proof for the Prohibitive message filtering policy (used to demonstrate the validity of the encrypted witness) which is achieved over lattices at the first time and is generic and efficient. Startlingly, our proof methods can be extended to prove inequalities of general vectors, thus it is independent of interest.

Proving Binary Vectors $\mathbf {p}\ne \mathbf{0}$. Let n, q be positive integers with $n<q$ and $\mathbf {p}\in \{0,1\}^n$, our aim is to prove the secret $\mathbf {p}\ne \mathbf{0}$ in the Yang et al.’s framework [43]. Actually, this problem has been solved in the Stern-like framework [31] in spite of inefficiency and worse usability (i.e., it can not work in the Yang et al.’s framework [43]), where the system was established by appending $n-1$ “dummy" entries to extend the targeted vector $\mathbf {p}\in \{0,1\}^n$ to $\mathbf {p}'\in \{0,1\}^{2n-1}$ of Hamming weight n exactly and running the Stern-like protocol. To handle the task in the Yang et al.’s framework [43], one may find a possible solution in [27] where numerous lattice-based range arguments were developed to prove private integer relations such as $X\in [\alpha ,\beta ]$ for public integers $\alpha ,\beta \ge 0$. But the techniques used there are invalid in proving that one knows at least a private $X_{j}$ among a given set $\{X_1,...,X_n\}$ each of which is bounded by $[\alpha _i,\beta _i]$ with $i\in [n]$ satisfies that $\alpha _{j}<X_{j} \le \beta _{j}$, which essentially generalizes our problem when setting $\mathbf {p}=(X_1,...,X_n)^{\top }$ and $\alpha _i=0$ and $\beta _i=1$ for all $i\in [n]$. We now develop new techniques to address this problem.

An important observation is that, the task to prove $\mathbf {p}\ne \mathbf{0}$ is equivalent to that proving that there is at least an entry of $\mathbf {p}$ is $>0$. To end this, intuitively, it suffices to prove the $\mathbf {p}$’s Hamming weight is $\ge 1$. In the following, we provide two efficient solutions, where the first is somewhat tedious, and then second is succinct and will be applied in the construction of our argument system.

Let $\mathbf {J}_n=(1,...,1)^{\top }\in \mathbb {Z}_q^{n}$ of which all entries are 1’s. Suppose that the Hamming weight of binary vector $\mathbf {p}$ is $\ge 1$, then we can establish our argument system by proving that one knows a complementary binary vector $\mathbf {q}\in \{0,1\}^n$ with Hamming weight $\le n-1$ such that $\mathbf {p}+\mathbf{q} =\mathbf{J} _n \bmod q$. The inequality can be solved by decomposing $\mathbf {J}_n^{\top }\cdot \mathbf{q}$ via the vector $\mathbf {g}_{\delta _{\beta }}'$ with setting $\beta =n-1$ as in Sect. 4.1. Then, it suffices for a prover to prove that he knows private vectors $\mathbf {p},\mathbf{q} \in \{0,1\}^n$ and $\mathbf {q}' \in \{0,1\}^{\delta _{n-1}}$ such that the following conditions hold:

$$\begin{aligned} {\left\{ \begin{array}{ll} \mathbf{p} +\mathbf{q} =\mathbf{J} _n \bmod q,\\ \mathbf{J} _n^{\top }\cdot \mathbf{q} =\mathbf{g} '_{\delta _{n-1}}\cdot \mathbf{q} ' \bmod q. \end{array}\right. } \end{aligned}$$

(2)

Note that the above solution not only works well in the Yang et al.’s framework [43] but does well in the Stern-like framework [31], and is more efficient when used in the previous framework. In fact, to further achieve efficiency gains, we can directly go to prove the Hamming weight of $\mathbf {p}$ is $\ge 1$, i.e., go to prove $\mathbf {J}_n^{\top }\cdot \mathbf{p} \ge 1$. Interestingly, we observe that the proof for this relation can be reduced to that one knows a secret non-negative integer $b\le {n-1}$ such that $\mathbf {J}_n^{\top }\cdot \mathbf{p} =1+b$. Combining with the decomposition techniques defined in Sect. 4.1, we equally write the relation as (assuming a private vector $\mathbf {q}\in \{0,1\}^{\delta _{n-1}}$)

$$\begin{aligned} \mathbf{J} _n^{\top }\cdot \mathbf{p} -\mathbf{g} '_{\delta _{n-1}}\cdot \mathbf{q} =1 \bmod q. \end{aligned}$$

(3)

The last above solution is more efficient since it saves $50\%$ size compared to the previous one, and both present solutions are generic and more efficient when working in [43] than that of [31]. Besides, our solutions can be readily extended to prove that one knows a private $\mathbf {x}$ having $l_{\infty }$ or $l_{2}$ norm bounded by $[\alpha ,\beta ]$ with integers $\alpha ,\beta \ge 0$.

Proving Bounded Hamming Distance.In general, there two commonly used message filtering policies termed as “Permisive” and “Prohibitive”. Our task is to establish the argument system for the latter, and that for previous is trivial and is omitted in this work. Given positive integers $m\ge t\ge d$, and binary vectors $\mathbf {m}\in \{0,1\}^m$ and $\mathbf {y}_i\in \{0,1\}^t$ with $i\in [m-t+1]$, we use $\mathbf {y}_i\sqsubset \mathbf{m}$ to mean that $\mathbf {y}_i$ is a substring of $\mathbf {m}$, i.e., there exist strings $\mathbf {x}_i,\mathbf{z} _i\in \{0,1\}^{\le m-t}$ such that $[\mathbf{x} _i^{\top }|\mathbf{y} _i^{\top }|\mathbf{z} _i^{\top }]^{\top }=\mathbf{m}$. Actually, the relation $\mathbf {y}_i \sqsubset \mathbf{m}$ is equivalent to the equality $\mathbf {B}_{i}\cdot \mathbf{m} =\mathbf{y} _i$ where $\mathbf {B}_{i}\in \mathbb {Z}_q^{t \times m}$ is a public matrix of the form $[\mathbf{0} |\mathbf{I} _t|\mathbf{0} ]$. Now we define the message filtering policy “Prohibitive” used in this work:

$$\begin{aligned} R_\textsf {prohi}=\{((\mathbf{s} _{i})_{i=1}^{e},\mathbf{m} )\in (\{0,1\}^{t})^{e}\times \{0,1\}^m: d_{H}(\mathbf{s} _{i},\mathbf{y} )\ge d, \forall i\in [e], \forall \mathbf{y} \sqsubset \mathbf{m} )\}. \end{aligned}$$

To build an argument system for the relation $R_\textsf {prohi}$, we begin with building a system for the simple relation $d_{H}(\mathbf{x} ,\mathbf{y} )\ge d$ with $\mathbf {x},\mathbf{y} \in \{0,1\}^n$ being public and secret. In the context of lattices, the proof is needed to be proceeded in mod q (involved with the dimension n for security, e.g., $q \ge \sqrt{n}$) instead of mod 2, which is always an open problem. Now we use a novel idea to address it. For any $x,y\in \{0,1\}$, we observe that $x \oplus y=x+y-2x\cdot y$, which follows that $\mathbf {x}\oplus \mathbf{y} =\mathbf{x} +\mathbf{y} -2(x_1\cdot y_1,...,x_n\cdot y_n){\top }$ for binary vectors $\mathbf {x}=(x_1,...,x_n)^{\top }$ and $\mathbf {y}=(y_1,...,y_n)^{\top }$. Then, the task to prove $d_{H}(\mathbf{x} ,\mathbf{y} ) \ge d$ can be reduced to proving $\Vert \mathbf{x} +\mathbf{y} -2(x_1\cdot y_1,...,x_n\cdot y_n)^{\top }\Vert _1\ge d$. By extending the proof method just developed above, in the setting of mod q, our task is reduced to proving that we hold a secret vector $\mathbf {z}\in \{0,1\}^{\delta _{n-d}}$ such that the following equation holds:

$$\begin{aligned} \mathbf{J} _n^{\top }\cdot (\mathbf{x} +\mathbf{y} -2(x_1\cdot y_1,...,x_n\cdot y_n)^{\top }) - \mathbf{g} _{\delta _{n-d}}'\cdot \mathbf{z} =d \bmod q. \end{aligned}$$

Based on the above result, for each $i\in [e],j\in [m-t+1]$, let $\mathbf {s}_i=(s_{i,1},...,s_{i,t})^{\top }$, $\mathbf {y}_j=\mathbf{B} _{j}\cdot \mathbf{m}$ with $\mathbf {y}_j=(y_{j,1},...,y_{j,t})$ and $\mathbf {B}_{j,1}^{\top }, ...,\mathbf{B} _{j,t}^{\top }$ be the row vectors of $\mathbf {B}_j$ (which essentially ensures that $y_{j,k}=\mathbf{B} _{j,k}^{\top }\cdot \mathbf{m}$). Then, the task to prove the relation $R_\textsf {prohi}$ is equal to proving that one knows secret vectors $\mathbf {z}_{i,j}\in \{0,1\}^{\delta _{m-d}}$ such that ($\forall i\in [e], j\in [m-t+1]$):

$$\begin{aligned} \mathbf{J} _n^{\top }\cdot (\mathbf{s} _i+\mathbf{B} _j\cdot \mathbf{m} -2(s_{i,1}\cdot \mathbf{B} _{j,1}^{\top },...,s_{i,t}\cdot \mathbf{B} _{j,t}^{\top })^{\top }\cdot \mathbf{m} ) - \mathbf{g} _{\delta _{m-d}}'\cdot \mathbf{z} _{i,j}=d \bmod q. \end{aligned}$$

(4)

Then, let $\mathbf {B}_{i,j}=\mathbf{J} _n^{\top }\cdot (\mathbf{B} _j-2(s_{i,1}\cdot \mathbf{B} _{j,1}^{\top },...,s_{i,t}\cdot \mathbf{B} _{j,t}^{\top })^{\top })\in \mathbb {Z}_q^{1\times m}$ and $d_{i,j}=d+\mathbf{J} _n^{\top }\cdot \mathbf{s} _i\in \mathbb {Z}_q$, which is followed by $\mathbf {B}_{[i]}=[\mathbf{B} _{i,1}^{\top },...,\mathbf{B} _{i,m-t+1}^{\top }]^{\top }\in \mathbb {Z}_q^{(m-t+1)\times m}$ and $\mathbf {B}=[\mathbf{B} _{[1]}^{\top },...,\mathbf{B} _{[e]}^{\top }]^{\top }\in \mathbb {Z}_q^{(m-t+1)e\times m}$. Accordingly, build $\mathbf {z}_{[i]}=[\mathbf{z} _{i,1}^{\top },...,\mathbf{z} _{i,m-t+1}^{\top }]^{\top } \in \mathbb {Z}_q^{(m-t+1) \delta _{m-d}}$, $\mathbf {z}=[\mathbf{z} _{[1]}^{\top },...,\mathbf{z} _{[e]}^{\top }]^{\top }\in \mathbb {Z}_q^{(m-t+1)e\delta _{m-d}}$, and $\mathbf {d}_{[i]}=[d_{i,1},...,d_{i,m-t+1}]^{\top } \in \mathbb {Z}_q^{m-t+1}$ and $\mathbf {d}=[\mathbf{d} _{[1]}^{\top },...,\mathbf{d} _{[e]}^{\top }]^{\top }\in \mathbb {Z}_q^{(m-t+1)e}$. Combining with the definition $\mathbf {I}_\mathbf{g '}=\mathbf{I} _{(m-t+1)e}\otimes \mathbf{g} _{\delta _{m-d}}'$, the relation $R_\textsf {prohi}$ is equally written as:

$$\begin{aligned}{}[\mathbf{B} ,\mathbf{I} _\mathbf{g '}]\cdot \begin{pmatrix} \mathbf{m} \\ \mathbf{z} \end{pmatrix}=\mathbf{d} \bmod q. \end{aligned}$$

(5)

Run the above result in the Yang et al.’s framework [43], then the argument for bounded Hamming distance is established. It is seen that the above proof method is also generic and efficient.

4.3 The Underlying ZKAoK

We now state our argument system under the abstract framework provided in [43] as recalled in Sect. 2.4 for a wide of lattice relations to fulfill our intricate task. Given the same settings of parameters as in Sect. 5.1, let $\textsf {bin}(j)=(j_1,...,j_{\ell })\in \{0, 1\}^{\ell }$, $\mathbf {j}=\textsf {bin}(j)^{\top }$, $\mathbf {A}=[\mathbf{A} _1|\mathbf{A} _2]$ and $\mathbf {a}_{j,i}=\textsf {mdec}_{n,m,q}(\mathbf{U} _{j,i}^{\top })$ for each $i\in \{1,2\}$. As in [26, 31], take the operator $\textsf {ext}(\cdot ,\cdot )$ to express $\textsf {ext}(b,\mathbf{v} )=\begin{pmatrix} \bar{b}\cdot \mathbf{v} \\ b\cdot \mathbf{v} \end{pmatrix}$. Our protocol can be summarized as follows:

Public Input: Matrices $\mathbf {A}$, $\mathbf {G}$, $\mathbf {F}$, $\mathbf {B}$, $\mathbf {A}_\textsf {rec}$, $\mathbf {A}_\textsf {oa}$, $\mathbf {U}_{\textsf {oa},1}$, $\mathbf {U}_{\textsf {oa},2}$, $\mathbf {I}_\mathbf{g} '$, and vectors $\mathbf {u}_\tau$, $\mathbf {J}_{nk}$, $\mathbf {g}_{\delta _{nk-1}}'$, $\{\mathbf {c}_{\textsf {rec},i}^{(1)},\mathbf {c}_{\textsf {rec},i}^{(2)},\mathbf {c}_{\textsf {oa},i}^{(1)},\mathbf {c}_{\textsf {oa},i}^{(2)}\}_{i\in \{1,2\}},\mathbf{d}$.

Prover’s Goal: Prove possession of the secret inputs in the following system

$$\begin{aligned} {\left\{ \begin{array}{ll} \mathbf{j} =(j_1,...,j_{\ell })^{\top }, \big (\mathbf{p} _j, (\mathbf{w} _{\ell }^{(j)},...,\mathbf{w} _{1}^{(j)})\big )\in (\{0, 1\}^{nk})^{\ell +1}\; \text {with} \;\mathbf{p} _j \ne \mathbf{0} , \\ \mathbf{q} _j\in \{0,1\}^{\delta _{nk-1}},\mathbf{a} _{j,1},\mathbf{a} _{j,2} \in \{0,1\}^{nmk}, \\ \mathbf{m} \in \{0,1\}^{m}, \mathbf{z} \in \{0,1\}^{(m-t+1)e\delta _{m-d}}, \\ i=1,2:\mathbf{s} _{\textsf {rec},i}, \mathbf{s} _{\textsf {oa},i} \in \{0,1\}^n,\\ \mathbf{x} _{\textsf {rec},i}, \mathbf{y} _{\textsf {rec},i}, \mathbf{x} _{\textsf {oa},i} \in [-B,B]^{m},\mathbf{y} _{\textsf {oa},i} \in [-B,B]^{\ell } \\ \end{array}\right. } \end{aligned}$$

(6)

such that the following system of modular linear equations holds:

$$\begin{aligned} {\left\{ \begin{array}{ll} \mathbf{G} \cdot \mathbf{u} _\tau =\mathbf{A} \cdot \textsf {ext}(j_1, \mathbf{v} _1^{(j)})+\mathbf{A} \cdot \textsf {ext}(\bar{j}_1,\mathbf{w} _1^{(j)}) \bmod q,\mathbf{v} _\ell ^{(j)}=\mathbf{p} _j,\\ i\in [1,\ell -1]:\\ \mathbf{0} =\mathbf{A} \cdot \textsf {ext}(j_{i+1}, \mathbf{v} _{i+1}^{(j)})+\mathbf{A} \cdot \textsf {ext}(\bar{j}_{i+1}, \mathbf{w} _{i+1}^{(j)})+(-\mathbf{G} )\cdot \mathbf{v} _{i}^{(j)}\bmod q,\\ 1=\mathbf{J} _{nk}^{\top }\cdot \mathbf{p} _j+(-\mathbf{g} _{\delta _{nk-1}}')\cdot \mathbf{q} _j \bmod q,\\ \mathbf{0} =\mathbf{G} \cdot \mathbf{p} _j+(-\mathbf{F} )\cdot (\mathbf{a} _{j,1}^{\top }|| \mathbf{a} _{j,2}^{\top })^{\top }\bmod q,\\ r=\{1,2\}: \mathbf{c} _{\textsf {rec},r}^{(1)}= \mathbf{A} _\textsf {rec}^{\top }\cdot \mathbf{s} _{\textsf {rec},r}+\mathbf{x} _{\textsf {rec},r} \bmod q,\\ \mathbf{c} _{\textsf {rec},r}^{(2)}= \mathbf{U} _{j,r}^{\top }\cdot \mathbf{s} _{\textsf {rec},r}+\mathbf{y} _{\textsf {rec},r}+\mathbf{m} \cdot \lfloor \frac{q}{2} \rceil \bmod q, \\ \mathbf{d} =[\mathbf{B} , \mathbf{I} _\mathbf{g} ']\cdot [\mathbf{m} ^{\top }, \mathbf{z} ^{\top }]^{\top } \bmod q,\\ \mathbf{c} _{\textsf {oa},r}^{(1)}=\mathbf{A} _\textsf {oa}^{\top }\cdot \mathbf{s} _{\textsf {oa},r}+ \mathbf{x} _{\textsf {oa},r} \bmod q,\\ \mathbf{c} _{\textsf {oa},r}^{(2)}= \mathbf{U} _{\textsf {oa},r}^{\top }\cdot \mathbf{s} _{\textsf {oa},r}+\mathbf{y} _{\textsf {oa},r}+\mathbf{j} \cdot \lfloor \frac{q}{2} \rceil \bmod q, \end{array}\right. } \end{aligned}$$

(7)

To proceed the proof, we first build two argument systems $\varPi _1$ suitable for accumulator values problem and plain encryption, and $\varPi _2$ suitable for encryption with hidden matrices, respectively, then establish the final system $\varPi _\textsf {GE}$ which covers all the above involved relations. The concrete steps are made as follows:

Build System $\varPi _1$. This system covers ($\ell +6$) equations consisting of the first ($\ell +2$) and the last four ones from the above equation system (7). Our task is to construct a ZKAoK system for the following relation:

$$\begin{aligned} R_1=\{(\mathbf{M} _1,\mathbf{y} _1),(\mathbf{x} _1): \mathbf{M} _1\cdot \mathbf{x} _1= \mathbf{y} _1 \wedge \mathbf{x} _{1}\in \textsf {cond}_1\}. \end{aligned}$$

(8)

In the above, the matrix $\mathbf {M}_1$ consists of the involved public matrices and vectors $\{\mathbf {A},\mathbf {G},\mathbf {J}_{nk},\mathbf {g}_{\delta _{nk-1}}',\mathbf {F}, \mathbf {A}_\textsf {oa},\mathbf {U}_{\textsf {oa},1}, \mathbf {U}_{\textsf {oa},2}\}$ by an appropriate arrangement, and vectors $\mathbf {x}_1$ and $\mathbf {y}_1$ are similarly made by private inputs $\{ \mathbf {j},\{\mathbf {v}_i\}_i,\{\mathbf {w}_i\}_i,\mathbf {p}_j,\mathbf {q}_j,\mathbf {q}_j', \{\mathbf {s}_{\textsf {oa},i}\}_i,\{\mathbf {x}_{\textsf {oa},i}\}_i,\{\mathbf {y}_{\textsf {oa},i}\}_i\}$ and public vectors $\{\mathbf {G}\cdot \mathbf {u}_\tau ,\mathbf {J}_{nk}, \{\mathbf {c}_{\textsf {oa},i}^{(1)},\mathbf {c}_{\textsf {oa},i}^{(2)}\}_i\}$, and the $\textsf {cond}_1$ is the set of conditions that the private inputs should meet given in system (6). We now describe the constructions of desired variables.

We achieve our goal by a sequence of steps. Let $\mathbf {b}_1,\mathbf {b}_2$ be constant vectors, respectively, of the form $\mathbf {b}_1=(B,...,B)^{\top }\in \mathbb {Z}_q^{m}$ and $\mathbf {b}_2=(B,...,B)^{\top }\in \mathbb {Z}_q^{\ell }$. Then, conduct the following.

• 1. Transform the inputs bounded by some positive integer to ones with non-negative entries. Concretely, for each $i\in \{1,2\}$, set $\mathbf {x}'_{\textsf {oa},i}=\mathbf {x}_{\textsf {oa},i}+\mathbf {b}_1\in [0,2B]^{m}$, and $\mathbf {y}'_{\textsf {oa},i}=\mathbf {y}_{\textsf {oa},i}+\mathbf {b}_2\in [0,2B]^{\ell }$.

• 2. Decompose the above newly transformed vectors $\mathbf {x}'_{\textsf {oa},i},\mathbf {y}'_{\textsf {oa},i}$. For each $i\in \{1,2\}$, apply the operator $\textsf {vdec}(\cdot )$ defined in Sect. 4.1 to the above targeted vectors to produce binary vectors $\mathbf {x}''_{\textsf {oa},i},\mathbf {y}''_{\textsf {oa},i}$ of size $m\delta _{2B}$ and $\ell \delta _{2B}$, respectively, such that $\mathbf {x}'_{\textsf {oa},i}=\mathbf {H}_{m,2B}\cdot \mathbf {x}''_{\textsf {oa},i}$ and $\mathbf {y}'_{\textsf {oa},i}=\mathbf {H}_{\ell ,2B}\cdot \mathbf {y}''_{\textsf {oa},i}$.

• 3. Modify the involved public vectors accordingly. For each $i\in \{1,2\}$, set $\mathbf {c}_{\textsf {oa},i}^{(1)'}=\mathbf {c}_{\textsf {oa},i}^{(1)}+\mathbf {b}_1$ and $\mathbf {c}_{\textsf {oa},i}^{(2)'}=\mathbf {c}_{\textsf {oa},i}^{(2)}+\mathbf {b}_2$.

• 4. Rewrite the first $\ell$ equations. For each $i\in [1,\ell ]$, by $\mathbf {A}=[\mathbf {A}_1|\mathbf {A}_2]$ and the operator $\textsf {ext}(\cdot ,\cdot )$, we have $\mathbf {A}\cdot \textsf {ext}(j_{i}, \mathbf {v}_{i}^{(j)})+\mathbf {A}\cdot \textsf {ext}(\bar{j}_{i}, \mathbf {w}_{i}^{(j)})=\mathbf {A}_1\cdot \mathbf {v}_i+(\mathbf {A}_2-\mathbf {A}_1)\cdot j_i\mathbf {v}_i+\mathbf {A}_2\cdot \mathbf {w}_i+(\mathbf {A}_1-\mathbf {A}_2)\cdot j_i\mathbf {w}_i$. Let $\mathbf {A}_{(1,2)}=[\mathbf {A}_1 | \mathbf {A}_2-\mathbf {A}_1| \mathbf {A}_2| \mathbf {A}_1-\mathbf {A}_2]$, $\mathbf {A}_{[1,2]}=[-\mathbf {G}|\mathbf {0}_3|\mathbf {A}_1 | \mathbf {A}_2-\mathbf {A}_1| \mathbf {A}_2| \mathbf {A}_1-\mathbf {A}_2]$ (where $\mathbf {0}_3$ means a block of form $[\mathbf {0}|\mathbf {0}|\mathbf {0}] \in (\mathbb {Z}_q^{n\times m})^3$) and $\mathbf {u}'=[(\mathbf {G}\cdot \mathbf {u}_\tau )^{\top }|\mathbf {0}^{\top }]^{\top }$, set a matrix $\mathbf {A}_{[1,\ell ]}=\begin{pmatrix} \mathbf {A}_{(1,2)}\\ \ \ \mathbf {A}_{[1,2]} \\ \ \ \ddots \end{pmatrix}$ consisting of a $\mathbf {A}_{(1,2)}$ and $(\ell -1)$’s $\mathbf {A}_{[1,2]}$ such that, for each $i\in [2,\ell -1]$, the component $-\mathbf {G}$ from the i-th block $\mathbf {A}_{[1,2]}$ and the component $\mathbf {A}_1$ from the last block $\mathbf {A}_{(1,2)}$ or from the last $\mathbf {A}_{[1,2]}$ are in the same column. Accordingly, for each $i\in [1,\ell ]$, we set $\mathbf {x}_{i,\mathbf {v}_i,\mathbf {w}_i}=[\mathbf {v}_i^{\top }|(j_i\mathbf {v}_i)^{\top }|\mathbf {w}_i^{\top }|(j_i\mathbf {w}_i)^{\top }]^{\top }$, and further set $\mathbf {x}_{\ell ,\mathbf {v},\mathbf {w}}=[\mathbf {x}_{1,\mathbf {v}_1,\mathbf {w}_1}^{\top }|\cdots |\mathbf {x}_{\ell ,\mathbf {v}_\ell ,\mathbf {w}_\ell }^{\top }]^{\top }$, which gives that $\mathbf {u}'=\mathbf {A}_{[1,\ell ]}\cdot \mathbf {x}_{\ell ,\mathbf {v},\mathbf {w}}$.

After the above treatments, the targeted system is equally changed as:

$$\begin{aligned} {\left\{ \begin{array}{ll} \mathbf{u} '=\mathbf{A} _{[1,\ell ]}\cdot \mathbf{x} _{\ell ,\mathbf{v} ,\mathbf{w} },\\ 1=\mathbf{J} _{nk}^{\top }\cdot \mathbf{p} _j+(-\mathbf{g} _{\delta _{nk-1}}')\cdot \mathbf{q} _j,\\ \mathbf{0} =\mathbf{G} \cdot \mathbf{p} _j+(-\mathbf{F} )\cdot [\mathbf{a} _{j,1}^{\top }|\mathbf{a} _{j,2}^{\top }]^{\top }\bmod q,\\ i\in \{1,2\}: \mathbf{c} _{\textsf {oa},i}^{(1)'}= \mathbf{A} _\textsf {oa}\cdot \mathbf{s} _{\textsf {oa},i}+ \mathbf{H} _{m,2B}\cdot \mathbf{x} ''_{\textsf {oa},i} \bmod q, \\ \mathbf{c} _{\textsf {oa},i}^{(2)'}= \mathbf{U} _{\textsf {oa},i}^{\top }\cdot \mathbf{s} _{\textsf {oa},i}+\mathbf{H} _{\ell ,2B}\cdot \mathbf{y} ''_{\textsf {oa},i}+\mathbf{j} \cdot \lfloor \frac{q}{2} \rfloor \bmod q.\\ \end{array}\right. } \end{aligned}$$

(9)

Basing on the above preparations, we obtain the desired variables as follows:

• 1. Build the public matrix $\mathbf {M}_1$ and the public vector $\mathbf {y}_1$. Set $\mathbf {A}':=\mathbf {A}_{[1,\ell -1]}, \mathbf {A}'_1:=\mathbf {A}_2-\mathbf {A}_1, \mathbf {A}'_2:=\mathbf {A}_1-\mathbf {A}_2, \mathbf {I}'_\ell :=\lfloor \frac{q}{2}\rfloor \cdot \mathbf {I}_\ell$, $\mathbf {g}':=-\mathbf {g}_{\delta _{nk-1}}'$, $\mathbf {F}':=-\mathbf {F}$, $\mathbf {G}':=-\mathbf {G}$ and $\mathbf {H}'_k:=\mathbf {H}_{k,2B}$ with $k\in \{\ell ,m\}$. Use the matrices in (9) to construct the desired matrix $\mathbf {M}_1$ and vector $\mathbf {y}_1$ as (here we abuse notation and use $[\mathbf {A}^{'\top }|\mathbf {G}^{'\top }]^{\top }$ to represent that the matrix $\mathbf {G}'$ and the component $\mathbf {A}_1$ from the last row of $\mathbf {A}'$ are in the same column)

  $$\begin{aligned} \left( \begin{array}{cccccccccccccccccc} \mathbf{0} &{}\mathbf{A} '&{}\mathbf{0} _3&{}\mathbf{0} &{}\mathbf{0} &{} \mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} \\ \mathbf{0} &{}\mathbf{G} '&{}\mathbf{0} _3&{}\mathbf{A} _1&{}\mathbf{A} _1'&{}\mathbf{A} _2&{} \mathbf{A} _2' &{} \mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} \\ \mathbf{0} &{}\mathbf{0} &{}\mathbf{0} _3&{}\mathbf{0} &{}\mathbf{0} &{} \mathbf{0} &{}\mathbf{0} &{} \mathbf{J} _{nk}^{\top } &{} \mathbf{g} ' &{}\mathbf{0} &{} \mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} \\ \mathbf{0} &{}\mathbf{0} &{}\mathbf{0} _3&{}\mathbf{0} &{}\mathbf{0} &{} \mathbf{0} &{}\mathbf{0} &{} \mathbf{0} &{} \mathbf{0} &{}\mathbf{A} _\textsf {oa}&{} \mathbf{H} '_{m}&{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} \\ \mathbf{I} '_\ell &{}\mathbf{0} &{}\mathbf{0} _3&{}\mathbf{0} &{}\mathbf{0} &{} \mathbf{0} &{}\mathbf{0} &{} \mathbf{0} &{} \mathbf{0} &{}\mathbf{U} _\textsf {oa,1}^{\top }&{} \mathbf{0} &{} \mathbf{H} '_{\ell }&{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} \\ \mathbf{0} &{}\mathbf{0} &{}\mathbf{0} _3&{}\mathbf{0} &{}\mathbf{0} &{} \mathbf{0} &{}\mathbf{0} &{} \mathbf{0} &{} \mathbf{0} &{}\mathbf{0} &{} \mathbf{0} &{} \mathbf{0} &{}\mathbf{A} _\textsf {oa}&{}\mathbf{H} '_{m}&{}\mathbf{0} &{}\mathbf{0} \\ \mathbf{I} '_\ell &{} \mathbf{0} &{}\mathbf{0} _3&{}\mathbf{0} &{}\mathbf{0} &{} \mathbf{0} &{}\mathbf{0} &{} \mathbf{0} &{} \mathbf{0} &{}\mathbf{0} &{} \mathbf{0} &{} \mathbf{0} &{}\mathbf{U} _\textsf {oa,2}^{\top }&{}\mathbf{0} &{}\mathbf{H} '_{\ell }&{}\mathbf{0} \\ \mathbf{0} &{}\mathbf{0} &{}\mathbf{0} _3&{}\mathbf{G} &{}\mathbf{0} &{}\mathbf{0} &{} \mathbf{0} &{} \mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{F} '\end{array} \right) , \begin{pmatrix} \mathbf{u} '\\ 1 \\ \mathbf{c} _\textsf {{oa},1}^{(1)'}\\ \mathbf{c} _{\textsf {oa},1}^{(2)'} \\ \mathbf{c} _\textsf {{oa},2}^{(1)'}\\ \mathbf{c} _{\textsf {oa},2}^{(2)'}\\ \mathbf{0} \end{pmatrix}. \end{aligned}$$

• 2. Build the private input $\mathbf {x}_1$. Arrange the modified private inputs shown in the system (9), establish the desired private vector $\mathbf {x}_1=(\mathbf{j} ^\top ,\mathbf {x}_{\ell ,\mathbf {v},\mathbf {w}}^\top ,\mathbf {q}_{j}^\top ,\mathbf {s}_{\textsf {oa},1}^{\top }, \mathbf {x}_{\textsf {oa},1}^{''\top }, \mathbf {y}_{\textsf {oa},1}^{''\top }, \mathbf {s}_{\textsf {oa},2}^{\top },\mathbf {x}_{\textsf {oa},2}^{''\top },\mathbf {y}_{\textsf {oa},2}^{''\top },\mathbf {a}_{j,1}^{\top },\mathbf {a}_{j,2}^{\top })^\top$ with size $n_1$, where $n_1=\ell +2n+\delta _{nk-1}+2(m+\ell )\delta _{2B}+4\ell nk+2nmk$.

• 3. Build the set of conditions $\textsf {cond}_1$. Let $\mathcal {M}_1$ be the set of triple indexes (h, i, l) of $\mathbf {x}_1$ with $h,i,l\in [n_1]$ such that $\mathbf {x}_1[h]=\mathbf {x}_1[i]\cdot \mathbf {x}_1[l]$. The set $\mathcal {M}_1$ is equivalent to the set $\textsf {cond}_1$. We now state the structure of $\mathcal {M}_1$:

  • a. Observe that all entries of $\mathbf {x}_1$ are binary, we note that the choices $(h,i,l)=(i,i,i)_{i\in [n_1]}$ are in the set $\mathcal {M}_1$.

  • b. Now consider the corresponding choices of $\mathcal {M}_1$ for $j_i\mathbf {v}_i, j_i\mathbf {w}_i$ for all $i\in [\ell ]$: for $j_i\mathbf {v}_i$, the choices consist of $(h,i,l)=(\ell +(4i'-3)nk+l',i',\ell + (4i'-4)nk+l')_{i'\in [\ell ],l'\in [nk]}$. Whereas, for $j_i\mathbf {w}_i$, the desired indexes are given by $(h,i,l)=(\ell +(4i'-1)nk+l',i',\ell + (4i'-2)nk+l')_{i'\in [\ell ],l'\in [nk]}$.

This constructs the argument system $\varPi _1$ for the relation $R_1$, and by running the protocol in Sect. 4.3, the desired argument system is obtained.

Build System $\varPi _2$. This system covers the remaining five equations from the system (7). Our task is to construct a similar ZKAoK system for the following relation:

$$\begin{aligned} R_2=\{(\mathbf{M} _2,\mathbf{y} _2),(\mathbf{x} _2): \mathbf{M} _2\cdot \mathbf{x} _2= \mathbf{y} _2 \wedge \mathbf{x} _{2}\in \textsf {cond}_2\}. \end{aligned}$$

(10)

As in the above system $\varPi _1$, the involved variables are respectively defined. We take similar strategies to proceed the present task.

• 1. For each $i\in \{1,2\}$, transform the private inputs $\mathbf {x}_{\textsf {rec},i},\mathbf {y}_{\textsf {rec},i}$ to ones that only have non-negative entries. Concretely, set $\mathbf {x}'_{\textsf {rec},i}=\mathbf {x}_{\textsf {rec},i}+\mathbf {b}_1, \mathbf {y}'_{\textsf {rec},i}=\mathbf {y}_{\textsf {rec},i}+\mathbf {b}_1,\in [0,2B]^{m}$.

• 2. Decompose the above newly generated vectors. For each $i\in \{1,2\}$, impose the function $\textsf {vdec}(\cdot )$ on these vectors, respectively, to yield size-$m\delta _{2B}$ binary vectors $\mathbf {x}''_{\textsf {rec},i}$ and $\mathbf {y}''_{\textsf {rec},i}$ such that $\mathbf {x}'_{\textsf {rec},i}=\mathbf {H}_{m,2B}\cdot \mathbf {x}''_{\textsf {rec},i}, \mathbf {y}'_{\textsf {rec},i}=\mathbf {H}_{m,2B}\cdot \mathbf {y}''_{\textsf {rec},i}$.

• 3. Change the corresponding public matrices and vectors. Consider the decomposition of $\mathbf {U}_{j,i}^{\top }\cdot \mathbf {s}_{\textsf {rec},i}$ with $i=1,2$. Let $\mathbf {U}_{j,i}^{\top }=[\mathbf {u}_{j,i}^{(1)\top }|...|\mathbf {u}_{j,i}^{(n)\top }]\in \mathbb {Z}_q^{m\times n}$ and $\mathbf {s}_{\textsf {rec},i}=(s_{\textsf {rec},i}^{(1)},...,s_{\textsf {rec},i}^{(n)})^{\top }\in \{0,1\}^{n}$. In light of operators $\textsf {vdec}(\cdot )$ and $\textsf {mdec}(\cdot )$, we have $\mathbf {U}_{j,i}^{\top }\cdot \mathbf {s}_{\textsf {rec},i}=\Sigma _{t=1}^{n}\mathbf {u}_{j,i}^{(t)\top } \cdot s_{\textsf {rec},i}^{(t)}=\Sigma _{t=1}^{n} \mathbf {H}_{m,q-1}\cdot \mathbf {a}_{j,i}^{(t)}\cdot s_{\textsf {rec},i}^{(t)}=\mathbf {H}_{m,q-1}\cdot \mathbf {s}_{\textsf {rec},i,mk}^{\top }\cdot \mathbf {a}_{j,i}$, where $\mathbf {a}_{j,i}^{(t)}\in \{0,1\}^{mk}$ is the binary decomposition of the vector $\mathbf {u}_{j,i}^{(t)\top }$ and $\mathbf {s}_{\textsf {rec},i,mk}=(\overbrace{s_{\textsf {rec},i}^{(1)},...,s_{\textsf {rec},i}^{(1)}}^{mk's \; \text {times}},...,\overbrace{s_{\textsf {rec},i}^{(n)},...,s_{\textsf {rec},i}^{(n)}}^{mk's \; \text {times}})^{\top }$. Additionally, for all $i=1,2$, set vectors as: $\mathbf {c}_{\textsf {rec},i}^{(1)'}=\mathbf {c}_{\textsf {rec},i}^{(1)}+\mathbf {b}_1$ and $\mathbf {c}_{\textsf {rec},i}^{(2)'}=\mathbf {c}_{\textsf {rec},i}^{(2)}+\mathbf {b}_1$.

After making the above treatments, the targeted system is equally changed as:

$$\begin{aligned} {\left\{ \begin{array}{ll} i\in \{1,2\}: \mathbf{c} _{\textsf {rec},i}^{(1)'}= \mathbf{A} _\textsf {rec}^{\top }\cdot \mathbf{s} _{\textsf {rec},i}+\mathbf{H} _{m,2B}\cdot \mathbf{x} _{\textsf {rec},i}'' \bmod q,\\ \mathbf{c} _{\textsf {rec},i}^{(2)'}= \mathbf{H} _{m,q-1}\cdot \mathbf{s} _{\textsf {rec},i,mk}^{\top }\cdot \mathbf{a} _{j,i}+\mathbf{H} _{m,2B}\cdot \mathbf{y} _{\textsf {rec},i}''+\mathbf{m} \cdot \lfloor \frac{q}{2} \rceil \bmod q, \\ \mathbf{d} =[\mathbf{B} , \mathbf{I} _\mathbf{g} ']\cdot [\mathbf{m} ^{\top },\mathbf{z} ^{\top }]^{\top }\bmod q, \end{array}\right. } \end{aligned}$$

(11)

This proceeds the following constructions of variables.

• 1. For simplicity, let $\mathbf {H}_m''=\mathbf {H}_{m,q-1}$ and $\mathbf {I}_m'=\lfloor \frac{q}{2}\rfloor \mathbf {I}_m$. Similar to what in system $\varPi _1$, build the public matrix $\mathbf {M}_2$ and the public vector $\mathbf {y}_2$ as

  $$\begin{aligned} \left( \begin{array}{ccccccccccc} \mathbf{0} &{} \mathbf{A} _\textsf {rec}^{\top } &{}\mathbf{0} &{}\mathbf{H} _{m}'&{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} \\ \mathbf{0} &{} \mathbf{0} &{}\mathbf{H} _{m}''&{}\mathbf{0} &{}\mathbf{H} _{m}'&{}\mathbf{0} &{}\mathbf{0} &{} \mathbf{0} &{}\mathbf{0} &{} \mathbf{I} _m' &{}\mathbf{0} \\ \mathbf{0} &{} \mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{A} _\textsf {rec}^{\top }&{}\mathbf{0} &{}\mathbf{H} _{m}'&{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} \\ \mathbf{0} &{} \mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{H} _{m}''&{} \mathbf{0} &{}\mathbf{H} _{m}'&{} \mathbf{I} _m'&{}\mathbf{0} \\ \mathbf{0} &{} \mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{}\mathbf{0} &{} \mathbf{0} &{}\mathbf{0} &{} \mathbf{B} &{}\mathbf{I} _\mathbf{g} '\\ \end{array} \right) \; \text {and}\; \begin{pmatrix} \mathbf{c} _{\textsf {rec},1}^{(1)'}\\ \mathbf{c} _{\textsf {rec},1}^{(2)'}\\ \mathbf{c} _{\textsf {rec},2}^{(1)'}\\ \mathbf{c} _{\textsf {rec},2}^{(2)'}\\ \mathbf{d} \end{pmatrix}. \end{aligned}$$

• 2. Build the private input $\mathbf {x}_2$. According to the public variables $\mathbf {M}_2$ and $\mathbf {y}_2$ above, we build the private vector $\mathbf {x}_2=(\mathbf {a}_{j,1}^{\top },\mathbf {a}_{j,2}^{\top },\mathbf {s}_{\textsf {rec},1}^{\top }, (\mathbf {s}_{\textsf {rec},1,mk}^{\top }\cdot \mathbf {a}_{j,1})^{\top },\mathbf {x}_{\textsf {rec},1}^{''\top }, \mathbf {y}_{\textsf {rec},1}^{''\top }, \mathbf {s}_{\textsf {rec},2}^{\top },(\mathbf {s}_{\textsf {rec},2,mk}^{\top }\cdot \mathbf {a}_{j,2})^{\top },\mathbf {x}_{\textsf {rec},2}^{''\top },\mathbf {y}_{\textsf {rec},2}^{''\top },\mathbf {m}^{\top },\mathbf {z}^{\top })^{\top }$ which has size $n_2=m+2n+2m(k+nk+2\delta _{2B})+(m-t+1)e\delta _{m-d}$.

• 3. Consider the set of conditions $\textsf {cond}_2$. Similarly, let $\mathcal {M}_2$ be the set of triple indexes (h, i, l) of $\mathbf {x}_2$ with $h,i,l\in [n_2]$ such that $\mathbf {x}_2[h]=\mathbf {x}_2[i]\cdot \mathbf {x}_2[l]$. It can be seen that the defined set of indexes is equal to the original set $\textsf {cond}_2$. Now we present the structure of set $\mathcal {M}_2$:

  • a. Observe that all components of $\mathbf {x}_2$ are binary vectors, which gives that such indexes $(h,i,l)=(i,i,i)$ with $i\in [n_2]$ are in $\textsf {cond}_2$.

  • b. In addition, the hidden matrix constraint in the original system is equally to the conditions $\mathbf {s}_{\textsf {rec},i,mk}^{\top }\mathbf {a}_{j,i}=s_{\textsf {rec},i,mk}^{\top }\cdot \mathbf {a}_{j,i}$ for each $i\in \{1,2\}$ as in system (11). This allows us to compute another choice of indexes $(h,i,l)=(2nmk+n+(i'-1)mk+l',2nmk+i',l')_{i'\in [n],l'\in [mk]}\cup (3nmk+2n+2m\delta _{2B}+(i'-1)mk+l',3nmk+n+2m\delta _{2B}+i',nmk+l')_{i'\in [n],l'\in [mk]}$.

This completes the task of constructing argument system $\varPi _2$ by running the protocol given in Sect. 4.3.

Build System $\varPi _\textsf {GE}$. The final system is the desired one which covers the system $\varPi _1$ and the system $\varPi _2$ simultaneously, whose definition is shown as follows:

$$\begin{aligned} R_\textsf {GE}=\{(\mathbf{M} ,\mathbf{y} ),(\mathbf{x} ): \mathbf{M} \cdot \mathbf{x} = \mathbf{y} \wedge \mathbf{x} \in \textsf {cond}\}. \end{aligned}$$

(12)

To build the system, we write $\mathbf {M}_1=[\mathbf {M}_{1,1}|\mathbf {M}_{1,2}]$ and $\mathbf {M}_2=[\mathbf {M}_{2,1}|\mathbf {M}_{2,2}]$, then build $\mathbf {M}=\begin{pmatrix} \mathbf {M}_{1,1} &{} \mathbf {M}_{1,2} &{} \mathbf {0}\\ \mathbf {0}&{}\mathbf {M}_{2,1}&{}\mathbf {M}_{2,2}\end{pmatrix}$, where the blocks $\mathbf {M}_{1,2}$ and $\mathbf {M}_{2,1}$ respectively represent the last column and the first column of $\mathbf {M}_1$ and $\mathbf {M}_2$. Accordingly, we build $\mathbf {x}=\begin{pmatrix} \mathbf {x}_1 \\ \mathbf {x}_2/\{[\mathbf {a}_{j,1}^{\top }|\mathbf {a}_{j,2}^{\top }]^{\top }\} \end{pmatrix}$, $\mathbf {y}=\begin{pmatrix} \mathbf {y}_1 \\ \mathbf {y}_2 \end{pmatrix}$ and $\textsf {cond}=\textsf {cond}_1\cap \textsf {cond}_2$, then a system that is suitable for the framework established in [43] is obtained. Now the family $\mathcal {M}$ of triples corresponding to the set $\textsf {cond}$ is somewhat modified, i.e., $\mathcal {M}=\mathcal {M}_1\cup \mathcal {M}'_2$, where $\mathcal {M}'_2=\{(h,i,l)\}=\{(i,i,i)\}_{i\in [n_1+1,n_1+n_2-2nmk]}\cup (n_1+n+(i'-1)mk+l',n_1+i',n_1-2nmk+l')_{i'\in [n],l'\in [mk]}\cup (n_1+nmk+2n+2m\delta _{2B}+(i'-1)mk+l',n_1+nmk+n+2m\delta _{2B}+i',n_1-nmk+l')_{i'\in [n],l'\in [mk]}$. Then, the prover runs an interactive protocol with the verifier as shown in [43], and the desired $\textsf {ZKAoK}$ system is established.

5 Our Fully Dynamic Lattice-Based Group Encryption

This section describes how to make use of the LNWX accumulator [31], GPV dual encryption [18] and the ZKAoK system built in Sect. 4 to construct our fully dynamic lattice-based group encryption in a relatively simple manner. In our design, this scheme first achieves the “Prohibitive” message filtering policy in the lattice setting and is free of lattice trapdoors throughout the design, resulting into great efficiency gains. All of these efforts yield a much more practical group encryption, also secure against the potential quantum attacks. We now briefly interpret the overview of our techniques.

Our inspiration begins with a main observation that, by using an updatable accumulator [31], one can directly upgrade the static group signature scheme [26] to one offering full dynamicity [31] at a reasonable cost, where the GM creates and revokes group membership via altering the hash value p of user’s public key (non-zero for activated users and 0 otherwise). Following the idea, combining with the GPV dual encryption [18], we consider: For a group of $N=2^{\ell }$ members, given $\mathbf {A}_\textsf {rec}\in \mathbb {Z}_q^{n\times m}$, users sample two random short matrices $\mathbf {E}_{j,1},\mathbf {E}_{j,2}\in \mathbb {Z}_q^{m\times m}$ from a given Gaussian distribution to generate nearly uniform $\mathbf {U}_{j,i}=\mathbf {A}\cdot \mathbf {E}_{j,i}\in \mathbb {Z}_q^{n \times m}$ with $i\in \{1,2\}$, resulting secret/public key pairs $(\textsf {sk}_j,\textsf {pk}_j)=(\mathbf {E}_{j,1},(\mathbf {U}_{j,1},\mathbf {U}_{j,2}))$ with hash values $\mathbf {p}_j=\textsf {bin}(\mathbf {F}\cdot [\mathbf {a}_{j,1}^{\top }|\mathbf {a}_{j,2}^{\top }]^{\top })\in \{0,1\}^{nk}$ where $\mathbf {a}_{j,i}=\textsf {mdec}_{n,m,k}(\mathbf {U}_{j,i}^{\top }) \in \{0,1\}^{nmk}$. Then, the manager builds an efficiently updatable tree on top of values $\mathbf {p}_0,\cdots ,\mathbf {p}_{N-1}$ and publishes the tree root u as well as the witness for the fact $\mathbf {p}_j$ was accumulated in u. Particularly, the GM conducts: (i)-For an invalid user who has not joined the group or has been excluded from the group, set the j-th leaf value $\mathbf {p}_j$ as 0; (ii)-For a valid user who joins the group and has not left the group, set the corresponding value as $\mathbf {p}_j$, the hash value of the public key $\textsf {pk}_j$; (iii)-With these rules, the GM can build an efficiently updatable tree with comparative complexity $\mathcal {O}(\log N)$, for which he only needs to alter the values at specific leaves and along their paths to the root rather than to reconstruct the whole tree when group information changes. These executions guarantee that all active users (with $\mathbf {p}\ne \mathbf {0}$) in the given epoch can be accumulated into the dynamic root while no any inactive user cannot, which effectively separates active users who can receive the valid ciphertexts from those who cannot in any growing epoch.

When moving to the stage of generating a group encryption, the sender fetches the public key $(\mathbf {U}_{j,1},\mathbf {U}_{j,2})$ and the associated membership witness $w^{(j)}$ of the target group member from group information, then samples a witness in light of the given Prohibitive message filtering policy and computes the ciphertext (we apply the Naor-Yung transformation technique [34] for CCA-2 security) and an associated proof which shows that the ciphertext is well-formed and $\mathbf {p}_j\ne \mathbf {0}$. In order for the proof to work in the Yang et al.’s ZK framework [43], we use the proof techniques we just provided in Sect. 4.2 and then resort to the argument system built in Sect. 4.3.

We also note that the dynamicity described in [31] is de facto limited to once enrollment and once revocation. To realize stronger dynamicity that users are allowed to join or leave the group at will, some modifications on procedures $\langle \textsf {JOIN},\textsf {ISSUE}\rangle$ and $\textsf {GUPDATE}$ are needed. Concretely, we take some significant modifications for the procedures of user registering and user leaving, such that group users indeed obtain the expected dynamicity as long as their reasonable applications are accepted by the GM.

5.1 Description of the Scheme

As in [35], we assume that our scheme allows encrypting witness $\mathbf {m}\in \{0,1\}^m$ that meets both message filtering policies termed as Permissive¹ and Prohibitive (shown in Sect. 4.2), which use constraints stronger than those used in [21, 25]. For simplicity, we only take the latter policy in our scheme. Procedures of constructing the FDGE scheme are shown as follows.

• SETUP$_\text {init}$ ($1^{\lambda }$): This algorithm conducts the following:

  • Set the possibly maximum number of group users as $N=2^{\ell }=\textsf {poly}(\lambda )$.

  • Select integer $n=\mathcal {O}(\lambda )$ and prime $q=\widetilde{\mathcal {O}}( n^{2})$. Let $k=\lceil \log q \rceil$, $m=2nk$.

  • Pick a discrete distribution $\chi$ over $\mathbb {Z}$ of the bound $B=\sqrt{n}\omega (\log n)$.

  • Select a Gaussian parameter $\sigma =\varOmega {(\sqrt{n\log q}\log n)}$, and build a discrete Gaussian distribution $D_{\mathbb {Z},\sigma }$ with upper bound $\beta =\sigma \cdot \omega {(\log n)}$.

  • Take public parameters $\textsf {pp}_\textsf {COM}$ for the homomorphic commitment scheme like [5] which serves as a key building block in the construction of the interactive game $\langle \mathcal {P,V}\rangle$.

  • Pick a random matrix F$\hookleftarrow \mathbb {Z}_q^{n \times 2nmk}$ which hashes users’ public keys from $\mathbb {Z}_q^{n \times 2m}$ to $\mathbb {Z}_q^n$.

  • Set a gadget matrix G = I$_n\otimes \mathbf {g}_k$ with the definition given in Sect. 4.1. Pick matrices $\mathbf {A}_\textsf {rec}, \mathbf {A}_\textsf {oa}\hookleftarrow U(\mathbb {Z}_q^{n\times m})$ that will be used to generate public keys for group users and the opening authority, respectively.

  Output

  pp$=\{N, \ell , \lambda , n, q, k, m, B, \chi , \sigma , \beta , \textsf {pp}_\textsf {COM}, \mathbf {F},\mathbf {G}, \mathbf {A}_\textsf {rec}, \mathbf {A}_\textsf {oa}\}$.

• SETUP$_\textsf {GM}$ (pp): This algorithm picks a random matrix $\mathbf {A}=[\mathbf {A}_1|\mathbf {A}_2]\hookleftarrow \mathbb {Z}_q^{n\times m}$ consisting of two same-size matrices, and samples $\textsf {sk}_\textsf {GM}\hookleftarrow \{0,1\}^{m}$ and computes $\textsf {pk}_\textsf {GM}=\mathbf {A}\cdot \textsf {sk}_\textsf {GM}$, resulting a key pair $(\textsf {pk}_\textsf {GM},\textsf {sk}_\textsf {GM})$ for the GM. Here, we take $\textsf {pk}_\textsf {GM}$ as an identifier of the group and assume that only the GM (i.e., the party holding $\textsf {sk}_\textsf {GM}$) can edit and publish the group information.

• SETUP$_\textsf {OA}$ (pp): This procedure samples two short secret matrices $\mathbf {E}_{\textsf {oa},i}$ with $i\in \{1,2\}$ from the distribution $D_{\mathbb {Z}^{m},\sigma }^{\ell }$ to generate two corresponding matrices $\mathbf {U}_{\textsf {oa},i}=\mathbf {A}_\textsf {oa}\cdot \mathbf {E}_{\textsf {oa},i} \in \mathbb {Z}_q^{n\times \ell }$, which forms the secret key $\textsf {sk}_\textsf {OA}=\mathbf {E}_{\textsf {oa},1}\in \mathbb {Z}_q^{m\times \ell }$ and the public key $\textsf {pk}_\textsf {OA}=(\mathbf {U}_{\textsf {oa},1},\mathbf {U}_{\textsf {oa},2})\in (\mathbb {Z}_q^{n \times \ell })^2$ for the $\textsf {OA}$.

  When GM receives $\textsf {pk}_\textsf {OA}$ sent from the OA, it executes the following:

  • 1. Build table reg: =$(\{\mathbf {reg}[j][i]\}_{j\in [0,N-1], i\in \{1,2\}})$ initialized as $\mathbf {reg}[j][1]=\mathbf {0}^{nk}$ and $\mathbf {reg}[j][2]=0$. Note that the former records the user’s registered public key, while the latter stores the epoch at which an execution of joining protocol is performed.

  • 2. Build a Merkle tree $\mathcal {T}$ on top of $\{\mathbf {reg}[j][1]\}_{j\in [0,N-1]}$ whose initial values are zero and then changed with users’ public keys by the GM when one successfully joins the group or the group executes an updating operation.

  • 3. Set the counter of users $c:=0$.

  Then, GM outputs gpk = (pp, pk$_\textsf {GM}$, pk$_\textsf {OA}$) and publicizes the initial group information $\textsf {info}=\emptyset$, while $\mathcal {T}$ as well as c is kept by him self.

• UKGEN(pp): For each $j\in [0,N-1]$ and each $i\in \{1,2\}$, user $\textsf {U}_j$ samples two secret matrices $\mathbf {E}_{j,i}$ from the Gaussian distribution $D_{\mathbb {Z}^m,\sigma }^m$ to generate two corresponding public matrices $\mathbf {U}_{j,i}=\mathbf {A}_{\textsf {rec}}\cdot \mathbf {E}_{j,i}\in \mathbb {Z}_q^{n\times m}$, which forms the secret key $\textsf {sk}_{j}=\mathbf {E}_{j,1}\in \mathbb {Z}_q^{m \times m}$ and the public key $\textsf {pk}_{j}=(\mathbf {U}_{j,1},\mathbf {U}_{j,2})\in (\mathbb {Z}_q^{n \times m})^2$. Then, the user computes a hash value $\mathbf {p}_j=\textsf {bin}(\mathbf {F}\cdot (\mathbf {a}_{j,1}^{\top }||\mathbf {a}_{j,2}^{\top })^{\top })\in \{0,1\}^{nk}$ with $\mathbf {a}_{j,i}=\textsf {mdec}_{n,m,q}(\mathbf {U}_{j,i}^{\top })\in \{0,1\}^{nmk}$ for each $i\in \{1,2\}$. We note that all honestly generated $\textsf {pk}_{j}$’s are non-zero and pairwise distinct, since the probability that users take zero-matrix $\mathbf {U}_{j,i}$ or same matrix (i.e., $\mathbf {U}_{j,i}=\mathbf {U}_{j',i'}$ for some $j\ne j'$ or $i\ne i'$ ), or finds a collision for hash function $\mathbf {F}$ is negligible (due to the assumed hardness of the SIS problem).

• $\langle \textsf {JOIN}(\textsf {sk});\textsf {ISSUE}(\textsf {sk}_\textsf {GM})\rangle (\textsf {gpk},\textsf {pk},\textsf {info}_\tau )\textsf {:}$ Let $\mathcal {S}_0$ be a set of indexes i of which associated public keys of group users are zero, with the initialization $\{\mathbf {reg}[j][1]\}$. When a user holding key pair $(\textsf {pk},\textsf {sk})$ with binary hash $\mathbf {p}$ wants to join the group at the epoch $\tau$, he sends $\mathbf {p}$ to the GM who proceeds the following procedures with him after the request is accepted:

  • 1. GM picks a random $j\in \mathcal {S}_0$ and sets a member identifier $\textsf {bin}(j)\in \{0,1\}^{\ell }$ for the user, and executes the following:

    • Update $\mathcal {T}$ by running procedure $\textsf {TUpdate}_\mathbf {A}(\textsf {bin}(j),\mathbf {p}_j)$.

    • Register the user to table reg as $\mathbf {reg}[j][1]:=\mathbf {p}_j$.

    • Update the set $\mathcal {S}_0:=\mathcal {S}_0-\{j\}$, increase the counter $c:=c+1$.

  • 2. When specific enrollment requests at a same epoch are ending, basing on the above updated results (note that the update process is essentially like that of running algorithm $\textsf {TAcc}_\mathbf {A}(\cdot )$ on $\mathbf {reg}[\cdot ][1]=\{\mathbf {reg}[j][1]\}_{j}$ for the generation of root value $\mathbf {u}$, thus same results are led), the GM runs algorithm $\textsf {TWitness}_\mathbf {A}(\mathbf {reg}[\cdot ][1],\mathbf {p}_j)$ to output a witness

    $$\begin{aligned} w^{(j)}=\big ((j_1,...,j_{\ell })\in \{0,1\}^{\ell },(\mathbf{w} _{\ell }^{(j)},...,\mathbf{w} _1^{(1)})\in (\{0,1\})^{\ell }\big ) \end{aligned}$$

    to the fact that $\mathbf {p}_j$ is accumulated in u.

  • 3. User checks the validity of $w^{(j)}$ by algorithm $\textsf {TVerify}_\mathbf {A}(\mathbf {u},\mathbf {p}_j,w^{(j)})$ and outputs $\perp$ if it is unaccepted. Otherwise, set $\textsf {wit}_{j}=(\mathbf {u},w^{(j)})$ as the witness of $\textsf {pk}_j$ being accumulated into the root u, which plays the similar role to a certificate of public key issued by the GM.

• $\textsf {GUPDATE}(\textsf {gpk},\textsf {sk}_\textsf {GM},\textsf {info}_{\tau _\text {current}}, \mathcal {S},\mathbf {reg})$: GM updates the group information while advancing the epoch by running this algorithm as follows.

  • 1. Let $\mathcal {S}$ be a set of verified public keys of group users to be removed. If $\mathcal {S}=\emptyset$, go to Step 2. Otherwise, let $\mathcal {S}=\{\mathbf {reg}[j_i][1]\}_{i=1}^{r}$ for some $r\in [1,N]$ and $j_i\in [0, N-1]$ for all $i \in [r]$, then GM runs $\textsf {TUpdate}_\mathbf {A}(\textsf {bin}(j_i),\mathbf {0}^{nk})$ to update the tree $\mathcal {T}$, followed by $\mathcal {S}_0:=\mathcal {S}_0 \bigcup \mathcal {S}$.

  • 2. By construction, each zero-value leaf in $\mathcal {T}$ corresponds to an inactive user, i.e., one that is revoked or has not yet got membership. This means that only active users capable of decrypting well-formed ciphertexts generated in the new epoch $\tau _{new}$ will have non-zero hash values of public keys $\{\mathbf {p}_j\}_j$, that are accumulated in the root $\mathbf {u}_{\tau _{\text {new}}}$ of the updated tree. For each j, let $w^{(j)}\in \{0,1\}^{\ell }\times (\{0,1\}^{nk})^{\ell }$ be the witness showing that $\mathbf {p}_j$ is accumulated in $\mathbf {u}_{\tau _{\text {new}}}$. GM publishes the updated group information:

    $$\begin{aligned} \textsf {info}_{\tau _{\text {new}}}=\big (\mathbf{u} _{\tau _{\text {new}}},\{w^{(j)}\}_j\big ). \end{aligned}$$

  As described below, in order to verify ciphertexts bound to epoch $\tau$, the verifier only needs to download the first component $\mathbf {u}_\tau$ of size $\widetilde{\mathcal {O}}(\lambda )$ bits. Meanwhile, to compute a well-formed ciphertext, it is sufficient for sender to download the witness of size $\widetilde{\mathcal {O}}(\ell \lambda )$ of some active user.

• $\langle \mathcal {G}_r, \textsf {sample}_{\mathcal {R}}\rangle \textsf {:}$ Algorithm $\mathcal {G}_r$ outputs parameters (t, e) for the Prohibitive policy to form (pk$_{\mathcal {R}}$, sk$_{\mathcal {R}}$)= $((t,e),\varepsilon )$. Then algorithm sample$_{\mathcal {R}}$ takes pk$_{\mathcal {R}}$ as input, and returns a set $\{\mathbf {s}_1,...,\mathbf {s}_e\}\in (\{0,1\}^t)^e$ and a witness $\mathbf {m}\in \{0,1\}^m$ such that they hold for the relation $R_\textsf {prohi}$ (i.e., meet the Eq. (5)).

• $\textsf {ENC}(\textsf {pk}_{\textsf {GM}},\textsf {pk}_{\textsf {OA}},\textsf {pk}_{j},\textsf {wit}_{j}, \textsf {info}_\tau , \{\mathbf {s}_i\}_{i=1}^e,\mathbf {m},L)\textsf {:}$ To encrypt the sampled witness m with the group information $\textsf {info}_\tau$ at epoch $\tau$, sender first checks whether a witness associated with $\textsf {bin}(j)$ is contained in $\textsf {info}_\tau$. If it is not this case, return $\perp$. Otherwise, the sender downloads $\mathbf {u}_\tau$ and some witness $(\textsf {bin}(j),(\mathbf {w}_\ell ,...,\mathbf {w}_1))$ from $\textsf {info}_\tau$, then parses $\textsf {pk}_{\textsf {OA}}$ as ($\mathbf {U}_{\textsf {oa},1},\mathbf {U}_{\textsf {oa},2}$) and $\textsf {wit}_{j}$ as $(\mathbf {u}_\tau ,w^{(j)})$ for some $j\in [0, N-1]$, and proceeds as follows.

  • 1. Encrypt the witness $\mathbf {m}\in \{0,1\}^m$ under $\textsf {U}_j$’s public key $\textsf {pk}_j\in (\mathbb {Z}_q^{n\times m})^2$. For each $i\in \{1,2\}$, randomly take a tuple $(\mathbf {s}_{\textsf {rec},i},\mathbf {x}_{\textsf {rec},i},\mathbf {y}_{\textsf {rec},i})\in U(\{0,1\}^n) \times (\chi ^m)^2$ to form the private parameter set $\textsf {rand}_\textsf {rec}=(\mathbf {s}_{\textsf {rec},i},\mathbf {x}_{\textsf {rec},i},\mathbf {y}_{\textsf {rec},i})_{i\in \{1,2\}}$. Compute the corresponding ciphertext $\mathbf {c}_{\textsf {rec},i}=(\mathbf {c}_{\textsf {rec},i}^{(1)}, \mathbf {c}_{\textsf {rec},i}^{(2)})\in (\mathbb {Z}_q^{m})^2$ as

    $$\begin{aligned} \mathbf{c} _{\textsf {rec},i}^{(1)}= \mathbf{A} _\textsf {rec}^{\top }\cdot \mathbf{s} _{\textsf {rec},i}+\mathbf{x} _{\textsf {rec},i} \bmod q, \mathbf{c} _{\textsf {rec},i}^{(2)}= \mathbf{U} _{j,i}^{\top }\cdot \mathbf{s} _{\textsf {rec},i}+\mathbf{y} _{\textsf {rec},i}+\mathbf{m} \cdot \lfloor \frac{q}{2} \rceil , \end{aligned}$$

    (13)

    which follows the ciphertext $\mathbf {c}_\textsf {rec}=(\mathbf {c}_{\textsf {rec},1},\mathbf {c}_{\textsf {rec},2}) \in (\mathbb {Z}_q^{m}\times \mathbb {Z}_q^{m})^2$.

  • 2. Encrypt the user identifier $\mathbf {j}\in \{0,1\}^{\ell }$ of user $\textsf {U}_j$ by taking similar operations as above. First take a random tuple $(\mathbf {s}_{\textsf {oa},i},\mathbf {x}_{\textsf {oa},i},\mathbf {y}_{\textsf {oa},i})\in U(\{0,1\}^n) \times \chi ^{m}\times \chi ^{\ell }$ for each $i\in \{1,2\}$, which forms the private randomness set $\textsf {rand}_\textsf {oa}=(\mathbf {s}_{\textsf {oa},i},\mathbf {x}_{\textsf {oa},i},\mathbf {y}_{\textsf {oa},i})_{i}$. Compute the corresponding ciphertext $\mathbf {c}_{\textsf {oa},i}=(\mathbf {c}_{\textsf {oa},i}^{(1)}, \mathbf {c}_{\textsf {oa},i}^{(2)})\in (\mathbb {Z}_q^{m}\times \mathbb {Z}_q^{\ell })$ as

    $$\begin{aligned} \mathbf{c} _{\textsf {oa},i}^{(1)}=\mathbf{A} _\textsf {oa}^{\top }\cdot \mathbf{s} _{\textsf {oa},i}+ \mathbf{x} _{\textsf {oa},i} \bmod q,\mathbf{c} _{\textsf {oa},i}^{(2)}= \mathbf{U} _{\textsf {oa},i}^{\top }\cdot \mathbf{s} _{\textsf {oa},i}+\mathbf{y} _{\textsf {oa},i}+\mathbf{j} \cdot \lfloor \frac{q}{2} \rceil , \end{aligned}$$

    (14)

    which follows the identity ciphertext $\mathbf {c}_\textsf {oa}=(\mathbf{c} _{\textsf {oa},1},\mathbf {c}_{\textsf {oa},2}) \in (\mathbb {Z}_q^{m}\times \mathbb {Z}_q^{\ell })^2$.

  Finally, put the above ciphertexts together, we obtain the ciphertext $\varPsi =\big (\mathbf {c}_{\textsf {rec}}, \mathbf {c}_{\textsf {oa}} \big )$ and the state information coins$_{\varPsi }=\big ( \textsf {rand}_{\textsf {rec}},\textsf {rand}_{\textsf {oa}} \big )$.

• $\textsf {DEC}(\textsf {sk}_{j}, \varPsi , L)\textsf {:}$ This algorithm takes the following steps to decrypt $\varPsi$:

  • 1. Parse the secret key sk$_j$ as $\mathbf {E}_{j,1}$ and the ciphertext $\varPsi$ as $\big (\mathbf {c}_{\textsf {rec}}, \mathbf {c}_{\textsf {oa}} \big )$.

  • 2. Use the secret key $\mathbf {E}_{j,1}$ to proceed the decryption of $\mathbf {c}_{\textsf {rec}}$ as

    $$\begin{aligned} \mathbf{m} =\left\lfloor \left( \mathbf{c} _{\textsf {rec},1}^{(2)}-\mathbf{E} _{j,1}^{\top }\cdot \mathbf{c} _{\textsf {rec},1}^{(1)}\right) /\Big \lfloor \frac{q}{2} \Big \rceil \right\rceil . \end{aligned}$$

    (15)

    Then, output m if it satisfies the relation $R_\textsf {prohi}$. Otherwise, return $\perp$.

• $\textsf {OPEN}(\textsf {sk}_{\textsf {OA}}, \textsf {info}_\tau , \mathbf {reg}, \varPsi , L)\textsf {:}$ This algorithm decrypts the ciphertext $\mathbf {c}_{\textsf {oa}}=(\mathbf {c}_{\textsf {oa},1},\mathbf {c}_{\textsf {oa},2})$ by proceeding the following steps:

  • 1. Parse the secret key sk$_\textsf {oa}$ as E$_{\textsf {oa},1}$ and the ciphertext $\varPsi$ as $\big (\mathbf {c}_{\textsf {rec}}, \mathbf {c}_{\textsf {oa}} \big )$.

  • 2. To reveal the targeted recipient, use $\mathbf {E}_{\textsf {oa},1}$ to decrypt the $\mathbf {c}_{\textsf {oa},1}$ as

    $$\begin{aligned} \mathbf{j} '=\left\lfloor \left( \mathbf{c} _{\textsf {oa},1}^{(2)}-\mathbf{E} _{\textsf {oa},1}^{\top }\cdot \mathbf{c} _{\textsf {oa},1}^{(1)}\right) /\Big \lfloor \frac{q}{2} \Big \rceil \right\rceil . \end{aligned}$$

    (16)

  • 3. Check that whether the group information $\textsf {info}_\tau$ includes a witness containing $\mathbf {j}'$ or not, and return $\perp$ if it is not this case.

  • 4. Let $j'\in [0,N-1]$ be the integer whose binary decomposition is $\mathbf {j}'$, if $\mathbf {reg}[j'][1]=\mathbf {0}^{nk}$ in table reg, then return $\perp$.

• $\langle \mathcal {P}(\textsf {pk}_j,\textsf {wit}_j,\mathbf {m},coins _\varPsi ),\mathcal {V}(\pi _\varPsi )\rangle (\textsf {gpk},\textsf {info}_{\tau },\{\mathbf {s}_i\}_{i=1}^e,\varPsi ,L) \textsf {:}$ Given the common inputs $\textsf {gpk}, \textsf {info}_{\tau }, \{\mathbf {s}_i\}_{i=1}^e, \varPsi$ and L. The prover’s secret inputs consist of a witness $\mathbf {m}\in \{0,1\}^m$, $\textsf {pk}_j=(\mathbf {U}_{j,1},\mathbf {U}_{j,2})\in (\mathbb {Z}_q^{n\times m})^2$, certificate $\textsf {wit}_j=(\mathbf {u}_\tau , w^{(j)})$ and random coins coins$_{\varPsi }=\big (\mathbf {s}_{\textsf {rec},i}, \mathbf {x}_{\textsf {rec},i}, \mathbf {y}_{\textsf {rec},i}; \mathbf {s}_{\textsf {oa},i}, \mathbf {x}_{\textsf {oa},i},\mathbf {y}_{\textsf {oa},i}\big )_{i\in \{1,2\}}$, while the verifier takes $\pi _\varPsi$ as its private input.

  The prover constructs a zero-knowledge argument system $\pi _\varPsi$ to convince the verifier that the secret inputs he makes satisfy the following conditions (details of which are shown in Sect. 4):

  • $\mathbf {G}\cdot \mathbf {p}_j=\mathbf {F}\cdot (\mathbf {a}_{j,1}^{\top }||\mathbf {a}_{j,2}^{\top })^{\top }\bmod q$.

  • TVerify$_\mathbf {A}\big (\mathbf {u},\mathbf {p}_{j},w^{(j)}\big )=1$ and $\mathbf {p}_j \ne \mathbf {0}$.

  • Witness $\mathbf {m}$ satisfies the relation $R_\textsf {prohi}$ defined in Sect. 4.2.

  • For each $i\in \{0,1\}$, vectors $\mathbf {s}_{\textsf {rec},i},\mathbf {s}_{\textsf {oa},i}$ are of the form $\{0,1\}$, and vectors $\mathbf {x}_{\textsf {rec},i}, \mathbf {y}_{\textsf {rec},i},\mathbf {x}_{\textsf {oa},i}, \mathbf{y} _{\textsf {oa},i}$ have infinity B-bounded norm.

  • Equations of (13) and (14) hold.

Correctness. The correctness of the proposed group encryption follows from correctly decrypting the GPV dual ciphertexts, which may cause some decryption errors. Indeed, during the decryption procedure of DEC(sk$_j$, $\varPsi , L$), we have:

$$\begin{aligned} \mathbf{c} _{\textsf {rec},1}^{(2)}-\mathbf{E} _{j,1}^{\top }\cdot \mathbf{c} _{\textsf {rec},1}^{(1)}=\mathbf{y} _{\textsf {rec},1}-\mathbf{E} _{j,1}^{\top }\cdot \mathbf{x} _{\textsf {rec},1}+\mathbf{m} \cdot \Big \lfloor \frac{q}{2} \Big \rfloor . \end{aligned}$$

(17)

Note that $\Vert \mathbf {x}_{\textsf {rec},1}\Vert _{\infty }$ and $\Vert \mathbf {y}_{\textsf {rec},1}\Vert _{\infty }$ both have upper bound B, and $\Vert \mathbf {E}_{j,1}\Vert _\infty$ is bounded by $\beta$. Then $\Vert \mathbf {y}_{\textsf {rec},1}-\mathbf {E}_{j,1}^{\top }\cdot \mathbf {x}_{\textsf {rec},1}\Vert _\infty \le B+ m\beta B$ and is further bounded by $\widetilde{\mathcal {O}}(n^{1.5})$ which is smaller than $q/5=\widetilde{\mathcal {O}}(n^{2})$. As a result, the decryption algorithm returns m with overwhelming probability. This gives the correctness of DEC(sk$_j$ , $\varPsi , L$). For OPEN(sk$_\mathsf {OA}$, $\varPsi , L$), a similar analysis is proceeded and $\Vert \mathbf {y}_{\textsf {oa},1}-\mathbf {E}_{\textsf {oa},1}^{\top }\cdot \mathbf {x}_{\textsf {oa},1}\Vert _\infty$ is also bounded by $\widetilde{\mathcal {O}}(n^{1.5})$.

Finally, we argue that if a sender honestly follows all the prescribed algorithms for the specific certified group user, valid witness-vectors to be used in the protocol $\langle \mathcal {P,V}\rangle$ are able to be computed and the present proof is accepted by the verifier, thanks to the completeness of the argument system in Sect. 4.3.

5.2 Analysis of the Scheme

Security Analysis. We provide provable security analysis for our scheme under the SIS and LWE hardness assumptions via the classical reduction methods. These security results and associated proofs are shown in the following.

Theorem 1

The anonymity is satisfied if the $\mathrm {\textsf {LWE}}_{n,q,\chi }$ assumption holds.

Proof

We prove the anonymity using a sequence of indistinguishable games, where we begin with running the experiment $\mathbf {Exp}_{\mathcal {A}}^{\textsf {anon}-0}$ and end with the experiment $\mathbf {Exp}_{\mathcal {A}}^{\textsf {anon}-1}$ from Definition 5 to show that the advantage for the adversary succeeding in the last game is negligible. For simplicity, hereunder we take PPT algorithms $\mathcal {A}$ and $\mathcal {B}$ as the adversary and challenger, respectively, and denote by $W_i$ the event that the adversary $\mathcal {A}$ returns $b'=1$ in game i.

Game 1: This is the real experiment $\mathbf {Exp}_{\mathcal {A}}^{\textsf {anon}-0}$ except that $\mathcal {B}$ retains $\mathbf {E}_{\textsf {oa},2}$, which makes no any difference in the adversary’s view since $\mathbf {E}_{\textsf {oa},2}$ is not used in the following real experiment. Concretely, the challenger $\mathcal {B}$ publicizes the parameters pp containing $\mathbf {A}_\textsf {rec}, \mathbf {A}_\textsf {oa} \in \mathbb {Z}^{n\times m},\mathbf {F}\in \mathbb {Z}_q^{n\times 2nmk}$ as a part, and sends the opening public key $\textsf {pk}_\textsf {OA}=(\mathbf {U}_{\textsf {oa},1}, \mathbf {U}_{\textsf {oa},2}) \in (\mathbb {Z}_q^{n\times m})^2$ to $\mathcal {A}$ who certifies the honest group members on behalf of $\mathrm {\textsf {GM}}$ by invoking the $\mathrm {\textsf {USER}}$ oracle. Specially, after receiving two users’ public keys $\mathrm {\textsf {pk}}_{0}=(\mathbf {U}_{0,1},\mathbf {U}_{0,2}) \in (\mathbb {Z}_q^{n\times m})^2$ and $\mathrm {\textsf {pk}}_{1}=(\mathbf {U}_{1,1},\mathbf {U}_{1,2}) \in (\mathbb {Z}_q^{n\times m})^2$ of challenger’s choice, $\mathcal {A}$ registers the keys in the table reg and conducts a number of queries w.r.t. opening and decryption algorithms, whose response is handled by $\mathcal {B}$ by using $\textsf {sk}_\textsf {OA}=\mathbf {E}_{\textsf {oa},1}$ and $\textsf {sk}_{0}=\mathbf {E}_{0,1}, \textsf {sk}_{1}=\mathbf {E}_{1,1}$. Then, the adversary moves to the challenge phase to provide a valid witness $\mathbf {m}\in \{0,1\}^m$ satisfying the Prohibitive for challenge. In return, the challenger takes the bit $b=0$ and computes a group encryption $\varPsi ^*=(\mathrm {\mathbf {c}}_{\mathrm {\textsf {rec}}}^*,\mathrm {\mathbf {c}}_{\mathrm {\textsf {oa}}}^*)$ of the witness $\mathrm {\mathbf {m}}$ under $\mathrm {\textsf {pk}}_{b}=(\mathbf {U}_{b,1},\mathbf {U}_{b,2})$, and the user identity $\mathbf {j}_b=\mathbf {j}_0$ under $\mathrm {\textsf {pk}}_\textsf {oa}=(\mathbf {U}_{\textsf {oa},1},\mathbf {U}_{\textsf {oa},2})$ with $\mathbf {c}_\textsf {oa}= (\mathbf {c}_{\textsf {oa},1},\mathbf {c}_{\textsf {oa},2})$, which follows real proofs $\pi _{\varPsi ^*}^*$ of $\varPsi ^*$ and queries of opening and decryption under the natural restrictions of the security definition. When $\mathcal {A}$ halts, it returns a bit $b'\in \{0,1\}$ and the challenger $\mathcal {B}$ returns 1 iff $b'=b$. Otherwise, $\mathcal {B}$ outputs 0 indicating that the adversary fails in this game, which gives the success probability $\text {Pr}[W_1=1]$.

Game 2: This game is like Game 1 except one change in executing the ciphertext opening oracle $\textsf {OPEN}(\textsf {sk}_\textsf {oa},.)$. Concretely, $\mathcal {B}$ uses $\mathbf {E}_{\textsf {oa},2}\in \mathbb {Z}_q^{m \times \ell }$ instead of $\textsf {sk}_\textsf {oa}=\mathbf {E}_{\textsf {oa},1} \in \mathbb {Z}_q^{m \times \ell }$ to decrypt $\mathbf {c}_\textsf {oa}$ among the ciphertext $\varPsi =(\mathbf {c}_\textsf {rec}, \mathbf {c}_\textsf {oa})$. It can be seen that, in the $\mathcal {A}$’s view, this game is the same as Game 1 until the event $F_1$ that $\mathcal {A}$ queries the opening oracle $\textsf {OPEN}(\textsf {sk}_\textsf {oa},.)$ for a ciphertext $\varPsi =(\mathbf {c}_\textsf {rec}, \mathbf {c}_{\textsf {oa},1}, \mathbf {c}_{\textsf {oa},2})$ where $\mathbf {c}_{\textsf {oa},1}, \mathbf {c}_{\textsf {oa},2}$ encrypt two distinct $\ell$-size identities. By the soundness of our argument presented in Sect. 4.3, $\mathrm {Pr}[W_2]-\mathrm {Pr}[W_1]$ is bounded by $\mathrm {Pr}[F_1]$ which itself is bounded by $\mathbf {Adv}_\mathcal {B}^{\textsf {sound}}(\lambda )$.

Game 3: This game is identical to Game 2 except a modification in the generation of proofs $\pi _{\varPsi ^*}^*$. Instead of employing the real random coins ) used for $\varPsi ^*$ to generate proofs, we employ the zero-knowledge simulator of argument system described in Sect. 4.3 once invoking $\mathrm {\textsf {PROVE}}_{\mathcal {P},\mathcal {P}'}^b$ after the challenge phase (note that, given trusted public parameters, the computationally indistinguishable simulation is achieved via the techniques [17] without increasing the number of rounds). Here the computational $\mathrm {\textsf {ZK}}$ property ensures that, for any PPT adversary, the change is unnoticed: $|\mathrm {Pr}[W_3]-\mathrm {Pr}[W_2]|\in \mathrm {\textsf {negl}}(\lambda )$.

Game 4: This game is same as Game 3 except that we modify the generation of $\varPsi ^*=( \mathbf {c}_\textsf {rec}^*, \mathbf {c}_\textsf {oa}^*)$ with $\mathbf {c}_\textsf {oa}^*=(\mathbf {c}_{\textsf {oa},1}^*, \mathbf {c}_{\textsf {oa},2}^*)$ by encrypting a random size-$\ell$ identity $\mathbf {j}_1$ as $\mathrm {\mathbf {c}}_\mathrm {\textsf {oa},1}^*$, while still retaining $\mathrm {\mathbf {c}}_\mathrm {\textsf {oa},2}^*$ for the encryption of the index $\mathbf {j}_0$ corresponding to user $\textsf {U}_0$. By the semantic security of GPV dual encryption [18] (assuming the hardness of LWE problem) for public key $\textsf {pk}_\textsf {oa}=(\mathbf {U}_{\textsf {oa},1},\mathbf {U}_{\textsf {oa},2})$, this game is identical to Game 3, i.e., $|\mathrm {Pr}[W_4]-\mathrm {Pr}[W_3]|\le \mathrm {\mathbf {Adv}}^{\mathrm {\textsf {LWE}}}(\lambda )$.

Game 5: This game makes one change by switching back to the application of $\mathrm {\mathbf {E}}_{\textsf {oa},1}\in \mathbb {Z}_q^{m\times \ell }$ for the $\textsf {OPEN}(\textsf {sk}_{\textsf {oa}},\cdot )$ queries with discarding $\mathrm {\mathbf {E}}_{\textsf {oa},2}$, and the modification is invariant to the adversary except the event $F_2$, where the queries to the DEC for a valid ciphertext $\varPsi$ containing $\mathbf {c}_{\textsf {oa},1}^*,\mathbf {c}_{\textsf {oa},2}^*$ encrypting distinct $\ell$-size identities $\mathbf {j}_0$ and $\mathbf {j}_1$, happens. But, the occurrence of $F_2$ implies that the simulation soundness of the underlying ZKAoK system used to generate $\varPi _\textsf {GE}$ is broken. This results into $|\mathrm {Pr}[W_5=1]-\mathrm {Pr}[W_4=1]|\le \mathrm {\mathbf {Adv}}_{\varPi _\textsf {GE}}^{\mathrm {\textsf {sound}}}(\lambda )=\mathrm {\textsf {negl}}(\lambda )$.

Game 6: Here, this experiment performs a modification to the Game 5 only by taking $\mathbf {c}_{\textsf {oa},2}$ as the encryption of $\mathbf {j}_1$ for the challenge ciphertext $\varPsi ^*=(\mathbf {c}_\textsf {rec}^*, \mathbf {c}_\textsf {oa}^*)$ with $\mathbf {c}_\textsf {oa}^*=(\mathbf {c}_{\textsf {oa},1}^*, \mathbf {c}_{\textsf {oa},2}^*)$. Note that this change is unnoticed to $\mathcal {A}$ due to the semantic security the encryption shares for public key $\mathbf {U}_{\textsf {oa},2}$, and also for the application of $\mathrm {\mathbf {E}}_{\textsf {oa},1}$ to the $\mathrm {\textsf {OPEN}}$, we have $|\mathrm { Pr}[W_6=1]-\mathrm {Pr}[W_5=1]|=\mathrm {\textsf {negl}}(\lambda )$.

Game 7: This experiment generates a real proof for ciphertext $\varPsi ^*=(\mathbf {c}_\textsf {rec}^*, \mathbf {c}_\textsf {oa}^*)$ instead of using simulated proof, which is the only modification different from Game 6. The computational zero-knowledgeness of the underlying ZKAoK system makes the difference between Game 6 and Game 7 negligible, i.e., $\mathrm {Pr}[W_6=1]\approx \mathrm {Pr}[W_7=1]$. This is actually the experiment $\mathrm {\mathbf {Exp}}_\mathcal {A}^{\mathrm {\textsf {anon}}-1}(\lambda )$, which directly leads that $\mathrm {Pr}[W_7=1]=\mathrm {\mathbf {Exp}}_\mathcal {A}^{\mathrm {\textsf {anon}}-1}(\lambda )$. By these above games, we have $|\mathrm {\mathbf {Exp}}_\mathcal {A}^{\mathrm {\textsf {anon}}-1}(\lambda )-\mathrm {\mathbf {Exp}}_\mathcal {A}^{\mathrm {\textsf {anon}}-0}(\lambda )|=\mathrm {\textsf {negl}}(\lambda )$. This proves the anonymity.    $\square$

Theorem 2

The message secrecy is satisfied if the $\mathrm {\textsf {LWE}}_{n,q,\chi }$ assumption holds.

Proof

In a similar manner to that used in proving Theorem 1, we complete the proof via a sequence of indistinguishable games in which the first one is exactly the experiment $\mathbf {Exp}_{\mathcal {A}}^{\textsf {sec}-1}$ which generates a real ciphertext and an associated real proof while the last one is the experiment $\mathbf {Exp}_{\mathcal {A}}^{\textsf {sec}-0}$ that outputs a random ciphertext and an associated simulated proof. For simplicity, we use $\mathcal {A},\mathcal {B}$ to represent the adversary and challenger, respectively. In addition, we also denote by $W_i$ the event that the adversary $\mathcal {A}$ returns $b'=1$ in game i.

Game 1: This is the real experiment $\mathbf {Exp}_{\mathcal {A}}^{\textsf {sec}-1}$ except that $\mathcal {B}$ retains $\mathbf {E}_{j,2}$, which makes no any difference in the adversary’s view since $\mathbf {E}_{j,2}$ is not used in the following real experiment. Concretely, $\mathcal {A}$ is first fed with public parameters pp including $\mathbf {A}_\textsf {rec}\in \mathbb {Z}_q^{n\times m}$ by challenger. Then, under its whole control, the adversary generates public keys $\textsf {pk}_\textsf {OA}=(\mathbf {U}_{\textsf {oa},1}, \mathbf {U}_{\textsf {oa},2})\in (\mathbb {Z}_q^{n\times m})^2$ and $\textsf {pk}_\textsf {GM}$, and triggers the JOIN protocol with the challenger to register and certify the public key $\textsf {pk}_j=(\mathbf {U}_{j,1},\mathbf {U}_{j,2})\in (\mathbb {Z}_q^{n\times m})^2$ for some honest receiver of the challenger’s choice. After that, the adversary $\mathcal {A}$ makes a polynomial number of queries to $\textsf {DEC}$ oracle which is faithfully handled by the challenger using $\mathbf {E}_{j,1}$. Then, $\mathcal {A}$ provides a valid witness $\mathbf {m}\in \{0,1\}^m$ satisfying the Prohibitive for challenge. Subsequently, the challenger take $b=1$ and computes a ciphertext $\varPsi ^*=(\mathbf {c}_\textsf {rec}^*, \mathbf {c}_\textsf {oa}^*)$ which contains a group encryption of the real plaintext $\mathrm {\mathbf {m}}$ under $\mathrm {\textsf {pk}}_j$ and returns it back as a challenger ciphertext. Then, a polynomial number of real proofs $\pi _{\varPsi ^*}^*$ which are associated with the challenge ciphertext $\varPsi ^*$ are followed, and the decryption oracle with obvious restrictions is further granted. After doing this, $\mathcal {A}$ halts this game and outputs its guess bit $b'\in \{0,1\}$.

Game 2: This game is identical to Game 1 except one change in handling the ciphertext decryption oracle $\textsf {DEC}(\textsf {sk}_j,.)$. Concretely, $\mathcal {B}$ uses $\mathbf {E}_{j,2}\in \mathbb {Z}_q^{m \times m}$ instead of $\textsf {sk}_j=\mathbf {E}_{j,1} \in \mathbb {Z}_q^{m \times m}$ to decrypt $\mathbf {c}_\textsf {rec}$ among the ciphertext $\varPsi =(\mathbf {c}_\textsf {rec}, \mathbf {c}_\textsf {oa})$. In the $\mathcal {A}$’s view, this game is the same as Game 1 until the event $F_3$ that $\mathcal {A}$ queries a ciphertext $\varPsi =(\mathbf {c}_{\textsf {rec},1}, \mathbf {c}_{\textsf {rec},2}, \mathbf {c}_\textsf {oa})$ where $\mathbf {c}_{\textsf {rec},1}, \mathbf {c}_{\textsf {rec},2}$ encrypts two distinct m-size messages. By the soundness of our argument presented in Sect. 4.3, $\mathrm {Pr}[W_2]-\mathrm {Pr}[W_1]$ is bounded by $\mathrm {Pr}[F_3]\le \mathbf {Adv}_\mathcal {B}^{\textsf {sound}}(\lambda )$.

Game 3: This game is like Game 2 except a modification in generating proofs $\pi _{\varPsi ^*}^*$. Instead of employing the real random coins $coins _\varPsi ^*=$ ($\{\mathrm {\mathbf {s}}_{\mathrm {\textsf {rec}},i}^*\}_i,\{\mathrm {\mathbf {x}}_{\mathrm {\textsf {rec}},i}^*\}_i,$ $\{\mathrm {\mathbf {y}}_{\mathrm {\textsf {rec}},i}^*\}_i,\{ \mathrm {\mathbf {s}}_{\mathrm {\textsf {oa}},i}^*\}_i, \{\mathrm {\mathbf {x}}_{\mathrm {\textsf {oa}},i}^*\}_i,\{\mathrm {\mathbf {y}}_{\mathrm {\textsf {oa}},i}^*\}_i$) used for $\varPsi ^*$ to generate proofs, we rather to apply the zero-knowledge simulator presented in Sect. 4.3 once invoking $\mathrm {\textsf {PROVE}}_{\mathcal {P},\mathcal {P}'}^b$ after the challenge phase (i.e., given trusted public parameters, the computationally indistinguishable simulation is achieved with the techniques [17]). Here the computational $\mathrm {\textsf {ZK}}$ property ensures that, for any PPT adversary, the change is unnoticed: $|\mathrm {Pr}[W_3]- \mathrm {Pr}[W_2]|\in \mathrm {\textsf {negl}}(\lambda )$.

Game 4: In this game, we modify the generation of $\varPsi ^*=( \mathbf {c}_\textsf {rec}^*, \mathbf {c}_\textsf {oa}^*)$ with $\mathbf {c}_\textsf {rec}^*=(\mathbf {c}_{\textsf {rec},1}^*, \mathbf {c}_{\textsf {rec},2}^*)$ by encrypting a random size-m message $\mathbf {m}'\in R_\textsf {pro}$ as $\mathrm {\mathbf {c}}_\mathrm {\textsf {rec},1}^*$, while still retaining $\mathrm {\mathbf {c}}_\mathrm {\textsf {rec},2}^*$ for the encryption of $\mathbf {m}\in R_\textsf {pro}$. By the semantic security of GPV dual encryption [18] (under the hardness assumption of the LWE problem) for public key $\textsf {pk}_j=(\mathbf {U}_{j,1},\mathbf {U}_{j,2})$, this game is identical to Game 3, i.e., $|\mathrm {Pr}[W_4]- \mathrm {Pr}[W_3]|\le \mathrm {\mathbf {Adv}}^{\mathrm {\textsf {LWE}}}(\lambda )$.

Game 5: This game makes one change by switching back to the application of $\mathrm {\mathbf {E}}_{j,1}\in \mathbb {Z}_q^{m\times m}$ for the $\textsf {DEC}(\textsf {sk}_j,\cdot )$ queries with discarding $\mathrm {\mathbf {E}}_{j,2}$, and the modification is invariant to the adversary except the event $F_4$, where the queries to the DEC for a valid ciphertext $\varPsi$ containing $\mathbf {c}_{\textsf {rec},1}^*,\mathbf {c}_{\textsf {rec},2}^*$ encrypting distinct messages satisfied the $R_\textsf {Pro}$ relation, happens. But, the occurrence of $F_4$ implies that the simulation soundness of the underlying ZKAoK system used to generate $\varPi _\textsf {GE}$ is broken. This results into $|\mathrm {Pr}[W_5=1]-\mathrm {Pr}[W_4=1]|\le \mathrm {\mathbf {Adv}}_{\varPi _\textsf {GE}}^{\mathrm {\textsf {sound}}}(\lambda )=\mathrm {\textsf {negl}}(\lambda )$.

Game 6: Here, this experiment performs a modification to the Game 5 only by taking $\mathbf {c}_{\textsf {rec},2}$ as the encryption of $\mathbf {m}'\in R_\textsf {Pro}$ for the challenge ciphertext $\varPsi ^*=(\mathbf {c}_\textsf {rec}^*, \mathbf {c}_\textsf {oa}^*)$ with $\mathbf {c}_\textsf {rec}^*=(\mathbf {c}_{\textsf {rec},1}^*, \mathbf {c}_{\textsf {rec},2}^*)$. Note that this change is unnoticed to $\mathcal {A}$ due to the semantic security the encryption shares for public key $\mathbf {U}_{j,2}$, and also for the application of $\mathrm {\mathbf {E}}_{j,1}$ to the $\mathrm {\textsf {DEC}}$, we have $|\mathrm {Pr}[W_6=1]- \mathrm {Pr}[W_5=1]|=\mathrm {\textsf {negl}}(\lambda )$.

Game 7: Here, this experiment generates a real proof for ciphertext $\varPsi ^*=(\mathbf {c}_\textsf {rec}^*, \mathbf {c}_\textsf {oa}^*)$ instead of using simulated proof, which is the only modification different to Game 6. The computational zero-knowledgeness of the underlying ZKAoK system makes the difference between Game 6 and Game 7 negligible, i.e., $\mathrm {Pr}[W_6=1]\approx \mathrm {Pr}[W_7=1]$. This is actually the experiment $\mathrm {\mathbf {Exp}}_\mathcal {A}^{\mathrm {\textsf {sec}}-0}(\lambda )$, which directly leads that $\mathrm {Pr}[W_7=1]=\mathrm {\mathbf {Exp}}_\mathcal {A}^{\mathrm {\textsf {sec}}-0}(\lambda )$. Thus, we have $|\mathrm {\mathbf {Exp}}_\mathcal {A}^{\mathrm {\textsf {sec}}-1}(\lambda )-\mathrm {\mathbf {Exp}}_\mathcal {A}^{\mathrm {\textsf {sec}}-0}(\lambda )|=\mathrm {\textsf {negl}}(\lambda )$, which proves the message security.    $\square$

Theorem 3

The scheme is sound assuming that the $\mathrm {\textsf {SIS}}$ assumption holds.

Proof

It suffices for us to prove these facts: for a given message filtering policy $\textsf {Prohibitive}$, a ciphertext $\varPsi ^*=(\mathbf {c}_{\textsf {rec}^*},\mathbf {c}_{\textsf {oa}^*})$, a Label L and an associated with proof $\varPsi ^*$, the public key associated with the identity revealed by the adversary is valid, certified, unique and the provided ciphertext $\varPsi ^*$ is encrypted under this key. By the Lemma 2, the distribution of public keys is uniform, which ensures the public key is dense. In other words, the public is valid. In addition, the public key is unique since an occurring collision breaks the injective property of the mapping $\mathbf {F}\cdot [\mathbf {a}_1^{\top }|\mathbf {a}_2^{\top }]$. Thus, we only need to prove the other two cases.

• a. The public key is certified (activated). If not, for some $j\in [0,N-1]$, there is an associated binary vector $\mathbf {p}_j\ne \mathbf {0}$ being accumulated into the published root value u, but it is not equal to any value $\textsf {bin}(\mathbf {F}\cdot [\mathbf {a}_1^{\top }|\mathbf {a}_2^{\top }])$, which contradicts the security of the accumulator.

• b. The ciphertext is actually an encryption of witness $\mathbf {m}$ under this public key. If not, this event implies a breach in the computational soundness of our argument system and the binding property of the commitment scheme, which breaks the assumed hardness of the $\textsf {SIS}$ problem.    $\square$

Efficiency Analysis. It can be seen that all algorithms used for the construction of the present group encryption are polynomially effective. The efficiency evaluation of the scheme is shown as follows.

• The public key of GM is a vector with bit-size $\widetilde{\mathcal {O}}({\lambda })$, and that of OA and users are respectively a matrix of bit-size $\widetilde{\mathcal {O}}({\lambda }^2)$.

• The GM’s secret key is given by a bit string of size $\widetilde{\mathcal {O}}({\lambda })$, and the secret keys of OA and users are respectively a small-norm matrix of bit size $\widetilde{\mathcal {O}}({\lambda }^2)$.

• The ciphertext $\varPsi$ consists of $\mathbf {c}_\textsf {rec}=(\mathbf {c}_{\textsf {rec},1},\mathbf {c}_{\textsf {rec},2})\in (\mathbb {Z}_q^{m}\times \mathbb {Z}_q^{m})^2$ and $\mathbf {c}_\textsf {oa}=(\mathbf {c}_{\textsf {oa},1},\mathbf {c}_{\textsf {oa},2})\in (\mathbb {Z}_q^{m}\times \mathbb {Z}_q^{\ell })^2$, which leads the total bit size $\widetilde{\mathcal {O}}(\lambda +\ell )$.

• The communication cost of the protocol $\langle \mathcal {P,V}\rangle$ largely relies on the bit-size of witness x with size $n_2=m+2n+2m(k+nk+2\delta _{2B})+(m-t+1)e\delta _{m-d}$ shown in Sect. 4.3, which leads $\widetilde{\mathcal {O}}(\lambda ^2)$ bit-size.

In Table 1, given a security parameter $\lambda$, let $N=2^\ell$, $\kappa$ and $\Sigma$ be the group size, the number of protocol repetitions and a one-time signature, respectively, we give a somewhat rough comparison between our scheme and the currently existing post-quantum secure group encryption schemes [25] (lattice-based variant) and [35] (code-based variant) in terms of functionality, efficiency and security. In the solid security, the full dynamicity is achieved with a highly reasonable cost: the GM only needs to update values of size $\widetilde{\mathcal {O}}(\ell \lambda )$ when group information changes.

Table 1. Comparison between schemes [25, 35] and ours

To better understand the advantage of our design, we also give a slightly concrete efficiency comparison between our scheme and the post-quantum safe schemes [25] and [35] for a same group size $N=2^{10}$ toward the 80-bit security. By using the security analysis techniques shown in [35, 43, and references therein], we choose the trade-off parameters as , and for these schemes and ours, respectively. The results are shown in Table 2 where all the sizes of keys, ciphertexts and communication cost are almost highly superior than those of previous schemes. Particularly, our scheme obtains the drastic efficiency gains compared to [25] due to the free-of-trapdoor design. Besides, the group update cost of [35] and ours is 10.00 KB and 5.15 KB, respectively.

Table 2. Efficiency comparison between schemes [25, 35] and ours

6 Conclusion

In this paper, we provide a re-formalized definition and security model of FDGE that is essentially equal to but more succinct than that of [35]. Then, we provide two generic and efficient zero-knowledge proof methods for demonstrating the inequalities of binary vectors, which can be readily extended to the case of general vectors. Finally, combining the appropriate cryptographic materials and the proof techniques just presented, we achieve the first lattice-based group encryption system which meanwhile offers the full dynamicity and the message filtering policy. Our scheme is constructed in a simpler manner and nearly outweighs the post-quantum secure ones [25, 35] in terms of functions, efficiency and security.