Forward-Secure Revocable Secret Handshakes from Lattices

Abstract

Secret handshake ($\textsf{SH}$), as a fundamental privacy-preserving primitive, allows members from the same organization to anonymously authenticate each other. Since its proposal by Balfanz et al., numerous constructions have been proposed, among which only the ones separately designed by Zhang et al. over coding and An et al. over lattice are secure against quantum attacks. However, none of known schemes consider the issue of key exposure, which is a common threat to cryptosystem implementations. To guarantee users’ privacy against the key exposure attack, forward-secure mechanism is believed to be a promising countermeasure, where secret keys are periodically evolved in such a one-way manner that, past transactions of users are protected even if a break-in happens.

In this work we formalize the model of forward-secure secret handshake and present the first lattice-based instantiation, where ABB $\textsf{HIBE}$ is applied to handle key evolution process through regarding time periods as hierarchies. In particular, dynamic revocability is captured by upgrading the static verifier-local revocation techniques into updatable ones. To achieve anonymous handshake with ease, we present a generic way of transforming zero-knowledge argument systems termed as Fiat-Shamir with abort, into mutual authentication protocols. Our scheme is proved secure under the Short Integer Solution ($\textsf{SIS}$) and Learning With Errors ($\textsf{LWE}$) assumptions in the random oracle model.

1 Introduction

Secret Handshake, introduced by Balfanz et al. [7], is a fundamental anonymity primitive, where potential members form different groups and conduct an interactive protocol to authenticate each other. The mutual handshake is successful if and only if both parties belong to the same organization. Except for the affiliations, no extra information (including the identities) about the involved members will be leaked. Therefore, secret handshakes provide all-sided privacy-preserving property for enrolled members. To date, many practical applications of secret handshakes in social networks have been explored, such as online dating, mobile access [30] and e-healthcare [39], etc.

Unfortunately, most online infrastructures offering authentication interface run in the unprotected environment, where key exposure can be one of the most fatal damages as it thoroughly destroys the expected security [36]. Forward-secure mechanism [8, 21], is a promising method to address the above problem, which preserves the validity of users’ past actions. Its core design is a key evolving technique that proceeds as follows. The lifetime of the related scheme is divided into discrete periods. Upon each new period advancing, a subsequent secret key is evolved from the current one via a one-way key update algorithm. Then the current key is erased from the user’s records. Due to the one-wayness of the evolving method, the security of past periods’ keys is preserved after a break-in at some group member. By leveraging this technique, numerous cryptographic primitives supporting forward security have been constructed, such as digital signature [1, 12, 32] and public-key encryption [10, 15].

Compared with the cases of ordinary signatures or authentication protocols, key exposure can be more damaging to $\textsf{SH}$ systems. Once an adversary obtains the exposed credential of some legitimate user, it can impersonate that user to authenticate any others from the same group, such that a successful handshake no longer ensures a valid authentication. Besides, due to the anonymity of interactions, key exposure essentially undermines the whole group as it invalidates all previously completed handshakes within that group, regardless of who the participants were. Moreover, malicious users, who communicated with honest ones (after authenticating each other) and got their handshakes opened, may defend themselves by giving away their credentials over the Internet and claiming that some hacker conducted the behaviors. Albeit the potential threats of credentials being compromised, no previous $\textsf{SH}$ schemes considered this issue, except the construction of Wen et al. [38], where users are provided with a series of random credentials corresponding to discrete time periods. However, this countermeasure obviously brings huge storage cost and falls short of being succinct. On the other side, to conceptually explore the security against key exposure in $\textsf{SH}$, it would be better to first formalize the related generic model.

Our Contributions. This work exploits the field of forward-secure secret handshakes. Our contributions are summarized in the following.

• By carefully reforming the desired functionalities and security notations, we adapt the basic model of $\textsf{SH}$ to the forward-secure setting.

• Under the above model, we present a lattice-based $\textsf{SH}$ scheme. In particular,

  • We upgrade the static verifier-local revocation method into time-advanced updatable one, and prove that the iterative process works exactly in a zero-knowledge manner.

  • We show how to transform a special type of zero-knowledge system into an anonymous mutual authentication protocol, in a generic manner.

Other Related Works. Following Balfanz et al.’s pioneering work [7], early $\textsf{SH}$ constructions [17, 22, 43] employed one-time pseudonyms, which bears huge storage cost. One more efficient method is to apply reusable credentials. Xu and Yung [40] first designed a such scheme with weaker unlinkability. Ateniese et al. [6] proposed an efficient unlinkable secret handshake scheme in the standard model. Subsequently, Jarecki and Liu [23] proposed a framework for unlinkable secret handshake scheme that supports both traceability and revocation. From then on, various $\textsf{SH}$ schemes offering different functionalities were proposed [20, 37, 39]. However, these schemes are designed over number-theoretic assumptions and are vulnerable to quantum attacks. As all we know, only the ones separately proposed by Zhang et al. over coding theory [42] and An et al. [5] over lattice are secure against quantum computations.

Note that none of existing $\textsf{SH}$ schemes has formally considered the issue of key exposure, let alone propose available schemes over post-quantum candidates.

Organization. In Sect. 2, we recall some necessary background and techniques. Model and security requirements of forward-secure secret handshakes are provided in Sect. 3. Section 4 describes the supporting zero-knowledge argument system, which is further modified to support mutual authentication in a handshake. In Sect. 5, we present our lattice-based secret handshake scheme, followed by the analysis of efficiency and security.

2 Preliminaries

Vectors will be denoted in bold lower-case letters and matrices will be denoted in bold upper-case letters. Let $\Vert \cdot \Vert$ and $\Vert \cdot \Vert _\infty$ denote the Euclidean norm $(\ell _2)$ and infinity norm $(\ell _\infty )$, respectively. The Euclidean norm of matrix $\textbf{B}\in \mathbb R^{m\times n}$ with columns $(\textbf{b}_i)_{i\le n}$ is denoted by $\Vert \textbf{B}\Vert =\textrm{max}_{i\le n}\Vert {\textbf{b}_i} \Vert$. If $\textbf{B}$ is full column-rank, let $\widetilde{\textbf{B}}$ denote its Gram-Schmidt orthogonalization. The concatenation of matrices $\textbf{A}\in \mathbb {R}^{n\times m}$ and $\textbf{B}\in \mathbb {R}^{n\times k}$ is denoted by $[\textbf{A}|\textbf{B}]$. For positive integer n, let [n] denote the set $\{1,\ldots ,n\}$. If S is a finite set, denote by U(S) the uniform distribution over S and by $x\hookleftarrow D$ sampling x according to the distribution D.

2.1 Background on Lattices

Classic Lattices and Gaussian Distribution. Let $n,m,q\in \mathbb Z^+$ with $q>2$. For $\textbf{A}\in \mathbb Z_q^{n\times m}$, define two lattices as $\mathrm {\varLambda }^{\bot }(\textbf{A})=\{\textbf{x}\in \mathbb Z^m\; |\; \textbf{A}\cdot \textbf{x}=\textbf{0 }\mod q\}$ and $\mathrm {\varLambda }^{\textbf{u}}(\textbf{A})=\{\textbf{x}\in \mathbb Z^m \;|\; \textbf{A}\cdot \textbf{x}=\textbf{u}\mod q\}$. For a real $\sigma >0$, a vector $\textbf{c}\in \mathbb R^n$ and n-dimensional lattice L, define the function $\rho _{\sigma ,\textbf{c}}(\textbf{x})= \textrm{exp}(-\pi \Vert {\textbf{x}-\textbf{c}} \Vert ^2/\sigma ^2)$. The discrete Gaussian distribution over L with parameter $\sigma$ and center $\textbf{c}$ is defined as $D_{L,\sigma ,\textbf{c}}(\textbf{x}) = \frac{\rho _{\sigma ,\textbf{c}}(\textbf{x})}{\rho _{\sigma ,\textbf{c}}(L)}$ (write $D_{L,\sigma }(\textbf{x})$ for short when $\textbf{c}=0$).

Lemma 1

([19, 29]). Given integers n, $q \ge 2$, and $\sigma \ge \omega (\sqrt{\log n})$. we have $\textrm{Pr}_{\textbf{x}\hookleftarrow D_{\mathbb Z^n,\sigma }}[\Vert \textbf{x}\Vert _\infty \ge \sigma \cdot \log {n}]$ is negligible.

Lattice Algorithms. The following facts describe the algorithms for trapdoor generation, Gaussian sampling, lattice basis randomization and delegations.

Lemma 2

([4]). Given integers $n>0$, $m=O(n\log n)$, $q\ge 2$, this PPT algorithm $\textsf{TrapGen}(n,m,q)$ returns a matrix pair $(\textbf{A},\textbf{T}_{\textbf{A}})$ satisfies that i) $\textbf{A}\in \mathbb Z_q^{n\times m}$ is within negligible statistical distance from uniform. ii) $\textbf{T}_{\textbf{A}}$ is a basis of $\mathrm {\varLambda }^{\bot }(\textbf{A})$ and $\Vert \widetilde{\textbf{T}_{\textbf{A}}}\Vert \le \mathcal O(\sqrt{n\log q})$.

Lemma 3

([19]). Given matrices $\textbf{A}\in \mathbb Z^{n\times m}$, $\textbf{T}_{\textbf{A}} \in \mathbb Z^{m\times m}$ as a basis of $\mathrm {\varLambda }^{\bot }(\textbf{A})$, vector $\textbf{u}\in \mathbb Z^{n}_q$ and gaussian parameter $\sigma \ge \omega (\sqrt{\log n})\cdot \Vert \widetilde{\textbf{T}_{\textbf{A}}}\Vert$, this PPT algorithm $\textsf{SamplePre}(\textbf{A},\textbf{T}_{\textbf{A}},\textbf{u},\sigma )$ returns a vector $\textbf{v}\in \mathrm {\varLambda }^{\textbf{u}}(\textbf{A})$ sampled from a distribution statistically close to $D_{\mathrm {\varLambda }^{\textbf{u}}(\textbf{A}),\sigma }$.

Lemma 4

([16]). Given matrix $\textbf{T}_{\textbf{A}}$ be a basis of lattice $\mathrm {\varLambda }^{\bot }(\textbf{A})$ and gaussian parameter $\sigma \ge \Vert \widetilde{\textbf{T}_{\textbf{A}}}\Vert \cdot \omega {\sqrt{\log n}}$, this PPT algorithm $\textsf{RandBasis}(\textbf{T}_{\textbf{A}},\sigma )$ outputs a new a basis $\textbf{T}'_{\textbf{A}}$ of $\mathrm {\varLambda }^{\bot }(\textbf{A})$ such that $\Vert {\textbf{T}'_{\textbf{A}}}\Vert \le \sigma \cdot \sqrt{m}$ and the distribution of $\textbf{T}'_{\textbf{A}}$ does not depend on $\textbf{T}_{\textbf{A}}$ up to a statistical distance.

Besides, the following depicts that lattice basis can be efficiently delegated and simulated, which will be used in the user key update and security proof.

Lemma 5

([2, 16]). Set $\sigma _R=\sqrt{n\log q}\cdot \omega (\sqrt{\log m})$, let $\mathcal D_{m\times m}$ denote the distribution of matrices in $\mathbb Z^{m\times m}$ defined as $(D_{\mathbb Z^m,\sigma _R})^m$ conditioned on the sampled matrix being “$\mathbb Z_q$-invertible”. Given matrices $\textbf{A}\in \mathbb Z^{n\times m}$, $\textbf{T}_{\textbf{A}} \in \mathbb Z^{m\times m}$ as a basis of $\mathrm {\varLambda }^{\bot }(\textbf{A})$, $\textbf{R}\in \mathbb Z_q^{m\times m}$ as a product of $\ell$ matrices sampled from $\mathcal D_{m\times m}$. Then:

• 1. Let ${\textbf{A}'}\in \mathbb Z^{n\times m'}$ be any matrix containing $\textbf{A}$ as a submatrix. This deterministic polynomial-time algorithm $\textsf{ExtBasis}(\textbf{T}_{\textbf{A}},\textbf{A}')$ outputs a basis $\textbf{T}_{\textbf{A}'}$ of $\mathrm {\varLambda }^{\bot }(\textbf{A}')$ with $\Vert \widetilde{\textbf{T}_{\textbf{A}'}}\Vert =\Vert \widetilde{\textbf{T}_{\textbf{A}}}\Vert$.

• 2. This PPT algorithm $\textsf{SampleR}(1^m)$ outputs a matrix $\textbf{R}\in \mathbb Z^{m\times m}$ from a distribution that is statistically close to $\mathcal D_{m\times m}$.

• 3. Let Gaussian parameter $\sigma \ge \Vert \widetilde{\textbf{T}_{\textbf{A}}}\Vert \cdot (\sigma _R \sqrt{m}\omega (\log ^{1/2} m))^\ell \cdot \omega (\log m)$. This PPT algorithm $\textsf{BasisDel}(\textbf{A},\textbf{R},\textbf{T}_{\textbf{A}},\sigma )$ outputs a basis $\textbf{T}_{\textbf{B}}$ of $\mathrm {\varLambda }^{\bot }(\textbf{A}\textbf{R}^{-1})$ distributed statistically close to the distribution $\textsf{RandBasis}(\textbf{T},\sigma )$, where $\textbf{T}$ is an arbitrary basis of $\mathrm {\varLambda }^{\bot }(\textbf{A}\textbf{R}^{-1})$ satisfying $\Vert \widetilde{\textbf{T}}\Vert <\sigma /\omega (\sqrt{\log m})$.

• 4. This PPT algorithm $\textsf{SampleRwithBasis}(\textbf{A})$ outputs a matrix $\textbf{R}$ sampled from a distribution statistically close to $\mathcal D_{m\times m}$ and a basis $\textbf{T}_{\textbf{B}}$ of $\mathrm {\varLambda }^{\bot }(\textbf{A}\textbf{R}^{-1})$ having $\Vert \widetilde{\textbf{T}_{\textbf{B}}}\Vert \le \sigma _R/\omega (\sqrt{\log m})$.

Computational Lattice Problems. We recall the definitions and hardness results of $\textsf{SIS}$, $\textsf{ISIS}$ and $\textsf{LWE}$, on which the security of our scheme provably relies.

Definition 1

([3, 19]). Given parameters $m,q,\beta$ the functions of n, uniformly random vector $\textbf{u}\in \mathbb Z_q^n$ and matrix $\textbf{A}\in \mathbb Z_q^{n \times m}$, $\textsf{SIS}_{n,m,q,\beta }$ (resp., $\textsf{ISIS}_{n,m,q,\beta }$) demands to find a non-zero vector $\textbf{x}\in \mathrm {\varLambda }^{\bot }(\textbf{A})$ (resp., $\mathrm {\varLambda }^{\textbf{u}}(\textbf{A})$) such that $\Vert \textbf{x}\Vert \le \beta$.

For any $q\ge \beta \cdot \omega (\sqrt{n\log n})$, hardness of $\textsf{SIS}_{n,m,q,\beta }$ and $\textsf{ISIS}_{n,m,q,\beta }$ is given by a worst-case to average-case reduction from $\textsf{SIVP}_{\gamma }$ for some $\gamma =\beta \cdot \widetilde{\mathcal O}(\sqrt{nm})$.

Definition 2

([35]). Let $n,m \ge 1, q\ge 2$, and Let $\chi$ be a probability distribution over $\mathbb Z$. For $\textbf{s}\in \mathbb Z_q^n$, let $A_{\textbf{s},\chi }$ be the distribution obtained by sampling $\textbf{a}{\mathop {\leftarrow }\limits ^{\$}} \mathbb Z_q^n$ and $e \hookleftarrow \chi$, and outputting the pair $(\textbf{a},\textbf{a}^\top \cdot \textbf{s}+e )\in \mathbb Z_q^n \times \mathbb Z_q$. Decision$\text{- }\textsf{LWE}_{n,q,\chi }$ problem is to distinguish m samples from $A_{\textbf{s},\chi }$ (let $\textbf{s}\leftarrow U(\mathbb Z_q^n)$) and m samples chosen according to the uniform distribution over $\mathbb Z_q^n \times \mathbb Z_q$. Search$\text{- }\textsf{LWE}_{n,q,\chi }$ problem is to find the uniformly random $\textbf{s}$ given m samples from $A_{\textbf{s},\chi }$.

For prime power q, $\beta \ge \sqrt{n} \mathcal O(\log n), \gamma =\widetilde{\mathcal O}(nq/\beta )$, and a $\beta$-bounded distribution $\chi$, decision$\text{- }\textsf{LWE}_{n,q,\chi }$ problem is as least as hard as $\textsf{SIVP}_\gamma$. Also, decision$\text{- }\textsf{LWE}$ is proved to be equivalent to search$\text{- }\textsf{LWE}$ up to some polynomial increase of the sample number m (see [33]). In this work, for a discrete Gaussian distribution $\chi$ (i.e., $\chi =D_{\mathbb Z_m,\sigma }$), we write decision$\text{- }\textsf{LWE}_{n,q,\chi }$ as $\textsf{LWE}_{n,q,\sigma }$ for short.

2.2 Efficient Signature Scheme from Lattices

Libert et al. in [24] proposed a signature scheme (extended from the B$\ddot{\mathrm o}$hl et al.’s signature [9]) with efficient protocols, of which a variant will serve for the joining phase in our scheme. The scheme utilizes the following parameters: security parameter $\lambda$; integers $\ell =\textsf{poly}(\lambda )$, $n=\mathcal O(\lambda )$, $q=\widetilde{\mathcal O}(n^4)$ and $m=2n\lceil {\log q}\rceil$; Gaussian parameter $\sigma =\varOmega (\sqrt{n\log q})$; public key $\textsf{pk}:=(\textbf{G},\textbf{G}_0,\textbf{G}_1,\textbf{D},\textbf{D}_0,\textbf{D}_1,\textbf{u})$ and private key $\textsf{sk}:=\textbf{T}_{\textbf{G}}$, where $(\textbf{G},\textbf{T}_{\textbf{G}})\leftarrow \textsf{TrapGen}(n,m,q)$, $\textbf{D}\hookleftarrow U(\mathbb Z_q^{n\times m/2})$, $\textbf{G}_i,\textbf{D}_i\hookleftarrow U(\mathbb Z_q^{n\times m})$ for $i\in \{0,1\}$ and $\textbf{u}\hookleftarrow U(\mathbb Z_q^{n})$.

To make a signature on $\textbf{m}\in \{0,1\}^m$, one first chooses $i\hookleftarrow [2^\ell ]$ and builds the encoding matrix $\textbf{G}_i=[\textbf{G}|\textbf{G}_0+i\textbf{G}_1]$ with its delegated basis $\textbf{T}_i$, then computes the chameleon hash of $\textbf{m}$ as $\textbf{c}_M=\textbf{D}_0\cdot \textbf{r}+\textbf{D}_1\cdot \textbf{m}$ with vector $\textbf{r}\hookleftarrow D_{\mathbb Z^m,\sigma }$, which is used to define $\textbf{u}_M=\textbf{u}+\textbf{D}\cdot \textsf{vdec}_{n,q-1}(\textbf{c}_M)$. The resulted signature is $sig=(i,\textbf{d},\textbf{r})$ where $\textbf{d}\in \mathbb Z_q^{2m}$ is a short vector in $D_{\mathrm {\varLambda }^{\textbf{u}_M}(\textbf{G}_i),\sigma }$. The verification step is conducted via checking if $\textbf{G}_i\cdot \textbf{d}=\textbf{u}+\textbf{D}\cdot \textsf{vdec}_{n,q-1}(\textbf{D}_0\cdot \textbf{r}+\textbf{D}_1\cdot \textbf{m})$, $\Vert {\textbf{d}}\Vert <\sigma \sqrt{2m}$ and $\Vert {\textbf{r}}\Vert <\sigma \sqrt{m}$. It was proved in [24] that the signature above is secure under chosen-message attacks under the $\textsf{SIS}$ assumption.

2.3 Zero-Knowledge Argument Systems

In a zero-knowledge argument of knowledge ($\textsf{ZKAoK}$) system [13], a prover proves the possession of some witness for an NP relation to a verifier, without revealing any additional information. Generally, a secure $\textsf{ZKAoK}$ must satisfy 3 requirements: completeness, proof of knowledge and (honest verifier) zero knowledge.

Yang et al. [41] have proposed an efficient lattice-based $\textsf{ZKAoK}$ for relation:

$$\mathcal R=\{(\boldsymbol{M},\boldsymbol{y}, \mathcal L),(\boldsymbol{x}):\boldsymbol{M}\cdot \boldsymbol{x}=\boldsymbol{y} \wedge \forall (i,j,k)\in \mathcal L,\boldsymbol{x}[i]=\boldsymbol{x}[j]\cdot \boldsymbol{x}[k]\},$$

where $\boldsymbol{x}\in \mathbb Z_q^{\mathfrak n}$ is the secret witness and set $\mathcal L$ defines quadratic constraints over $\boldsymbol{x}$. The protocol can be further transformed into an $\textsf{NIZKAoK}$ consisting of two algorithms $\texttt{Prove}$ and $\texttt{Verify}$ via Fiat-Shamir heuristic. $\texttt{Prove}$ produces commitments $cmt=({cmt}_s,{cmt}_r)$, a challenge $ch=\mathcal G(cmt,\cdot )$ where $\mathcal G$ is a random oracle, and some responses rsp related to ch and cmt. Then $({cmt}_s,ch,rsp)$ is sent to a verifier, on input which $\texttt{Verify}$ recovers reserved commitment ${cmt}_r$ and computes $ch'$ by assembling cmt, it finally checks $ch'{\mathop {=}\limits ^{?}}ch$ to verify the $\textsf{ZK}$ proof. In this paper, we will adapt the $\textsf{NIZKAoK}$ to an anonymous mutual authentication protocol.

Theorem 1

The scheme described in Fig. 2 of [41] is a secure $\textsf{NIZKAoK}$ with negligible completeness and soundness error, under the hardness assumptions of $\textsf{SIS}$ and $\textsf{LWE}$, and has well-designed simulator and knowledge extractor.

2.4 LWE-Based Key Exchange

Derived from the design in [18, 34] describes an $\textsf{LWE}$-based key exchange using reconciliation mechanism, which yields keys indistinguishable from random. Let $\chi$ be a probability distribution over $\mathbb Z_q$, integer $\theta$ be the number of bits for key extraction and $\textbf{K}$ is a public matrix. The following protocol is utilized to produce a communication key in our scheme.

• Alice samples a secret matrix $\textbf{S}_a \hookleftarrow \chi (\mathbb Z^{n\times m}_q)$ and a small noise $\textbf{E}_a \hookleftarrow \chi (\mathbb Z^{n\times m}_q)$. Then, she computes $\textbf{C}_a =\textbf{K}\cdot \textbf{S}_a+\textbf{E}_a$ and sends it to Bob.

• Receiving $\textbf{C}_a$, Bob chooses his secret matrix $\textbf{S}_b \hookleftarrow \chi (\mathbb Z^{m\times n}_q)$ and computes $\textbf{C}_b =\textbf{K}\cdot \textbf{S}_b+\textbf{E}_b$, where $\textbf{E}_b \hookleftarrow \chi (\mathbb Z^{m\times n}_q)$. Then he samples a noise $\textbf{E}'_b \hookleftarrow \chi (\mathbb Z^{m\times m}_q)$ and sets $\textbf{V}_b=\textbf{S}_b \cdot \textbf{C}_a+\textbf{E}'_b$. Such that he extracts the shared secret key $\textbf{K}_b=\textsf{Extract}(\textbf{V}_b)$, namely, $\textbf{K}_b[i,j]=\textsf{round}((2^{\theta }/{q_1})\cdot \textbf{V}_b[i,j])\mod 2^\theta .$. Bob also produces a check matrix $\textbf{M}=\textsf{Check}(\textbf{V}_b)$ as $\textbf{M}[i,j]=\textsf{floor}((2^{\theta +1}/{q_1})\cdot \textbf{V}_b[i,j]) \mod 2.$ Finally, Bob sends $(\textbf{C}_b,\textbf{M})$ to Alice.

• With $(\textbf{C}_b,\textbf{M})$, Alice computes $\textbf{V}_a=\textbf{C}_b \cdot \textbf{S}_a$ and obtains $\textbf{K}_a=\textsf{Recon}(\textbf{V}_a,\textbf{M})$ via $\textbf{K}_a[i,j]=\textsf{round}((2^{\theta }/{q_1})\cdot \textbf{V}_a[i,j]+\frac{1}{4}\cdot (2\textbf{M}[i,j]-1))\mod 2^\theta .$

Theorem 2

([18]). The key exchange above produces the same shared key, i.e., $\textbf{K}_a=\textbf{K}_b$, with overwhelming probability via applying suitable parameters.

3 Model of Forward-Secure Secret Handshakes

As its analogues of group signature [26, 32], we consider $\textsf{SH}$ schemes having lifetime divided into discrete time periods, at the beginning of which group members autonomously update the secret keys for forward security. Let time period $t=0$ be the moment that an $\textsf{SH}$ system is activated, and assume that a handshake always finishes during the period at which it starts. The syntax of forward secure secret handshake ($\textsf{FSSH}$) is formalized as follows.

• $\textsf{Setup}$. Given a security parameter $\lambda \in \mathbb N$, this algorithm, possibly run by a trusted party or decentralized setting, generates public parameter $\textsf{par}$.

• $\textsf{CreateGroup}$. Given $\textsf{par}$, group authority ($\textsf{GA}$) invokes this algorithm to create a group. It publishes the group public key $\textsf{gpk}$ and retains secret key $\textsf{gsk}$.

• $\textsf{AddMember}$. This protocol is run between a potential user U and $\textsf{GA}$ to enroll the user into a chosen group. At time period t, U generates individual key pair $(\textsf{upk},\textsf{usk}_t)$ and sends $\textsf{upk}$ to $\textsf{GA}$. If it terminates successfully, $\textsf{GA}$ issues a group credential $\textsf{cred}_0$ (including a unique group identity $\textsf{ID}$) to U and adds $\textsf{cred}_0$ to user’s registration table $\textsf{Reg}$.

• $\textsf{Update}_{\mathsf U}$. On input user’s private pair $(\textsf{cred}_{t-1},\textsf{usk}_{t-1})$ at the beginning of time period t, this one-way algorithm evolves it into $(\textsf{cred}_{t},\textsf{usk}_{t})$.

• $\textsf{Handshake}$. This is a mutual authentication protocol between two participants (A, B). It outputs 1 and produces a session key for both active parties at the current time period t if and only if they belong to the same group.

• $\textsf{TraceMember}$. Given a handshake transcript, $\textsf{GA}$ runs this algorithm to trace the involved users, or outputs $\perp$ to indicate a failure.

• $\textsf{RemoveMember}$. This algorithm is invoked by $\textsf{GA}$ to revoke an active member. $\textsf{GA}$ also publishes some updated group information of that group for current time period, such that users can conduct revocation check.

Based on the considerations in [7, 26], we reform the security requirements an $\textsf{FSSH}$ must satisfy as Completeness, Forward impersonator resistance, Detector resistance and Backward unlinkability, all of which are defined via the corresponding experiments. Hereafter we use $\textsf{CU}$ and $\textsf{CG}$ to denote the corruption list of users and groups, respectively.

Completeness demands that $\textsf{Handshake}$ outputs 1 with overwhelming probability if both participants are active with updated secret keys and belong to the same group. Moreover, $\textsf{TraceMember}$ can always identify the involved users. For plain description, we define an auxiliary polynomial-time algorithm $\textsf{IsActive}(\textsf{ID},t):$ outputs 1 if $\textsf{ID}$ is active at current time period t and 0 otherwise.

Definition 3

The completeness is achieved if the following experiment returns 1 with negligible probability.

$\textrm{Experiment}$: $\textbf{Exp}^{\textsf{COM}}_{\mathcal A}(\lambda )$

$\textsf{par}\leftarrow \textsf{Setup}(\lambda ),\;(\textsf{gpk,gsk})\leftarrow \mathsf {CreateGroup(par)}$.

$\{(\textsf{ID}_0,\textsf{cred}_{0\Vert \overline{t}},\textsf{usk}_{0\Vert \overline{t}}),(\textsf{ID}_1,\textsf{cred}_{1\Vert \overline{t}},\textsf{usk}_{1\Vert \overline{t}})\} \leftarrow \textsf{AddMember}(\textsf{gpk,gsk},\overline{t})$

$\textsf{IsActive}(\textsf{ID}_b,t)=1 \wedge \textsf{usk}_{b\Vert t}\leftarrow \mathsf {Update_U}(\textsf{cred}_b,\textsf{usk}_{b\Vert t-1})$ for $b \in \{0,1\}$.

If $\textsf{Handshake}(\textsf{ID}_0,\textsf{ID}_1,t)=0$ with transcript T or $\textsf{TraceMember}(T)\notin \{\textsf{ID}_0$,$\textsf{ID}_1\}$,

then return 1 else retun 0.

Forward impersonator resistance requires that it is infeasible for any PPT adversary $\mathcal A$ to impersonate an uncorrupted user, or some corrupted user at the period preceding the one where she was broken into, even if it can corrupt all the users and groups (except the chosen group) via accessing the following oracles.

Below are oracles that entitle $\mathcal A$ to obtain exterior information of an $\textsf{FSSH}$.

• $\textsf{KeyP}(\textsf{par})$ simulates to create a new group and returns $\textsf{gpk}$ to $\mathcal A$.

• $\textsf{HS}(U,V)$ simulates a two-party handshake by generating the transcripts during the interaction.

• $\textsf{Trace}({T})$ returns the participant of transcript T. Hereafter we require that T is not generated from the challenging oracles.

• $\textsf{Remove}(U)$ simulates to revoke user U from her G, it also updates the corresponding group information at current period t.

The other oracles below enable $\mathcal A$ to break into the internal of an $\textsf{FSSH}$.

• $\textsf{CorU}(U,G)$ is a user corruption oracle. It returns user’s $\textsf{cred}$ and $\textsf{usk}$ of U in group G to $\mathcal A$ at period t, then it adds $(\textsf{ID}_U,G,t)$ to $\textsf{CU}$.

• $\textsf{AddU}(U,G)$ enrolls a user U whose key pair is chosen by $\mathcal A$ to G at period t. It also adds $(\textsf{ID}_U,G,t)$ to $\textsf{CU}$. Compared with $\textsf{CorU}$, $\textsf{AddU}$ endows $\mathcal A$ with more power to create dummy users or perform injection attacks.

• $\textsf{KeyG}(\textsf{par})$ returns $\textsf{msk}$ of some group G to $\mathcal A$ and adds G to $\textsf{CG}$, meaning that G is under the control of $\mathcal A$.

Now we describe the challenge game of forward impersonator resistance.

• $\textsf{Chal}^{\mathsf {F\text{- }IR}}(\textsf{ID},G,t)$ simulates $\textsf{ID}$ of group G and executes a handshake with $\mathcal A$ using the updated secret key of $\textsf{ID}$ at period t. It returns 1 if the protocol outputs 1 and 0 otherwise.

Hereafter we denote the transcript of $\mathcal A$ during the challenge game as T.

Definition 4

Forward impersonator resistance is achieved if, for any $\mathcal A$, the following experiment returns 1 with negligible probability.

$\textrm{Experiment}$: $\textbf{Exp}^{\mathsf {F\text{- }IR}}_{\mathcal A}(\lambda )$

$\textsf{par}\leftarrow \textsf{Setup}(\lambda )$, $\textsf{CG}$, $\textsf{CU}:=\emptyset$.

$(\textsf{ID}^*,G^*,t^*) \leftarrow \mathcal A^{\textsf{KeyP},\textsf{HS},\textsf{Trace},\textsf{Remove},\textsf{CorU,AddU},\textsf{KeyG}(\lnot G^*)}(\textsf{par})$.

If $\textsf{Chal}^{F\text{- }IR}(\textsf{ID}^*,G^*,t^*)=0$, return 0. Else if for $\textsf{ID}'\leftarrow \textsf{TraceMember}(T):$

$(\textsf{ID}',\cdot ,\cdot \;)\notin \textsf{CU}$ or $\;t^*<t\;\textrm{for}\;(\textsf{ID}',\cdot ,t)\in \textsf{CU}$, return 1. Else return 0.

Detector resistance makes sure that $\mathcal A$ cannot succeed when he activates a handshake with an honest and active user to identify her affiliation at the chosen time period, even if it can corrupt all the users and groups (except the chosen group). The related challenge game is described as follows.

• $\textsf{Chal}^{\textsf{DR}}_b(\textsf{ID},G,t)$ chooses a random bit $b \in \{0,1\}$. For $b=0$, it simulates $\textsf{ID}$ from G to handshake with $\mathcal A$. For $b=1$, it simulates an arbitrary (active) user $\textsf{ID}_r$ to handshake with $\mathcal A$. Then $\mathcal A$ guesses the value of b as $b^*$.

Definition 5

Detector resistance is achieved if, for any $\mathcal A$, the absolute difference of probability of outputting 1 between $\textbf{Exp}^{\mathsf {DR-1}}_{\mathcal A}$ and $\textbf{Exp}^{\mathsf {DR-0}}_{\mathcal A}$ is negligible.

$\textrm{Experiment}$: $\textbf{Exp}^{\mathsf {DR-b}}_{\mathcal A}(\lambda )$

$\textsf{par}\leftarrow \textsf{Setup}(\lambda )$, $\textsf{CG}$, $\textsf{CU}:=\emptyset$.

$(\textsf{ID}^*,G^*,t^*) \leftarrow \mathcal A^{\textsf{KeyP},\textsf{HS},\textsf{Trace},\textsf{Remove},\textsf{CorU,AddU},\textsf{KeyG}(\lnot G^*)}(\textsf{par})$, ${\textsf{Chal}^{\textsf{DR}}_b(\textsf{ID}^*,G^*,t^*)},$

holding that for $\textsf{ID}'\leftarrow \textsf{TraceMember}(T),\;(\textsf{ID}',\cdot ,\cdot \;)\notin \textsf{CU}$ or $\textsf{IsActive}(\textsf{ID}',t^*)=0$.

Return $b^*\leftarrow \mathcal A^{\textsf{KeyP},\textsf{HS},\textsf{Trace},\textsf{Remove},\textsf{CorU,AddU},\textsf{KeyG}(\lnot G^*)}(\textsf{par})$.

Backward Unlinkability ensures that no adversary can distinguish whether two handshakes (executed during two distinct periods) involve the same honest user, even if it can corrupt any user and any group (except the chosen pair), and that user is later revoked. Below is the related challenge game.

• $\textsf{Chal}^{\mathsf {B\text{- }Unlink}}_b(\textsf{ID}_0,G_0,\textsf{ID}_1,G_1,t)$ first picks a random bit $b\in \{0,1\}$, then it successionally simulates $\textsf{ID}_0$ and $\textsf{ID}_b$ to handshake with $\mathcal A$ using evolved secret. Finally $\mathcal A$ guesses the value of b as $b^*$.

Definition 6

Backward unlinkability is achieved if, for any $\mathcal A$, the absolute difference of probability of outputting 1 between $\textbf{Exp}^{\mathsf {B\text{- }Unlink-1}}_{\mathcal A}$ and $\textbf{Exp}^{\mathsf {B\text{- }Unlink-0}}_{\mathcal A}$ is negligible.

$\textrm{Experiment}$: $\textbf{Exp}^{\mathsf {B\text{- }Unlink-b}}_{\mathcal A}(\lambda )$

$\textsf{par}\leftarrow \textsf{Setup}(\lambda )$, $\textsf{CoG}$, $\textsf{CoU}:=\emptyset$.

$(\textsf{ID}_0,G_0,\textsf{ID}_1,G_1,t) \leftarrow \mathcal A^{\textsf{KeyP},\textsf{HS},\textsf{Trace},\textsf{Remove},\textsf{CorU,AddU},\textsf{KeyG}(\lnot G^*)}(\textsf{par})$,

holding that $G_i\notin \textsf{CG}\wedge (\textsf{ID}_i,G_i,\cdot \;)\notin \textsf{CU}$ for $i\in \{0,1\}$.

$b^*\leftarrow \mathcal A^{\textsf{Chal}^{B\text{- }Unlink}_b(\textsf{ID}_0,G_0,\textsf{ID}_1,G_1,t)}(\textsf{par}).$ Return $b^*$.

Note that if $\mathcal A$ has corrupted some user of $G_i$ for $i\in \{0,1\}$, then he is only allowed to choose target users within that group, i.e., $G_0=G_1$.

4 The Supporting Zero-Knowledge Layer

In this section, we first construct a system that allows obtaining $\textsf{ZKAoK}$ for some relations, which are linear equations within users’ credential and secret key of our $\textsf{FSSH}$ scheme. Then we clarify why $\textsf{ZK}$ argument cannot be directly used in a handshake procedure, for this reason we further present a generic way of transforming $\textsf{ZK}$ systems termed as Fiat-Shamir with abort into mutual authentication protocols, where participants can “handshake” with each other and negotiate a session key.

Below we extensively use the decomposition techniques in [24, 27]. Namely, for any integer $\beta >0$, let $\delta _\beta =\lceil {\log (\beta +1)} \rceil$ and $\beta _j=\lfloor {\frac{\beta +2^{j-1}}{2^j}} \rfloor \; \forall j \in [1,\delta _\beta ]$. Then any $i \in [0,\beta ]$ can be decomposed as $i=\textbf{h}_{\beta }\cdot \textsf{idec}_{\beta }(i)$, where $\textbf{h}_{\beta }=(\beta _1,\ldots , \beta _{\delta _\beta })$ and $\textsf{idec}_{\beta }$ is a binary function. Further, [25] build two more functions for decomposing vectors and matrices: $\textsf{vdec}_{m,\beta }:[0,\beta ]^m\rightarrow \{0,1\}^{m\delta _\beta }$; $\textsf{mdec}_{n,m,q}:\mathbb Z_q^{m\times n}\rightarrow \{0,1\}^{nm\delta _{q-1}}$. (see [25] or the full version of this paper for detailed definitions.)

4.1 ZKAoK System for Proving a Valid User

Now we describe the system that produces $\textsf{ZK}$ arguments for users’ secret. Given the same situation as that of $\textsf{Handshake}$ in Sect. 5 with extra setting: $\textbf{H}_{m,\beta }=\textbf{I}_m\otimes \textbf{h}_{\beta }$, $t_i=t_{add}+i$ for $i\in [t^*]$, $\textbf{h}_{N}=(N_1,\ldots ,N_{\ell })$, $\textbf{a}'= (\textbf{a}_1^{'\top }\;\ldots \;\textbf{a}_n^{'\top })^\top =\textsf{mdec}_{n,m,q}(\textbf{A}^\top )$, $\textbf{b}=\textsf{vdec}_{2n,q-1}(\textbf{h})$, $\textbf{w}=(\textbf{w}_1^\top \;\ldots \;\textbf{w}_n^\top )^\top =\textsf{mdec}_{n,m,q}(\textbf{A}_t^\top )$ and $\textbf{z}=\textsf{vdec}_{n,q-1}(\textbf{D}_0 \cdot \textbf{r}+\textbf{D}_1\cdot \textbf{b})$, the desired system is summarized as follows.

Public Input: Matrices $\textbf{G},\textbf{G}_0,\textbf{G}_1,\textbf{D},\textbf{D}_0,\textbf{D}_1,\textbf{B},\textbf{P},\textbf{W}$; Vectors $\textbf{u},\textbf{t},\textbf{w},\textbf{k}$; Integer $t^*$. System public parameter $\textsf{par}$.

Prover’s Witness: Vectors and Matrices which satisfy the following constraints

$$\begin{aligned} {\left\{ \begin{array}{ll} \textsf{ID}= {\textbf{i}}\in \{0,1\}^{\ell },\textsf{urt}_t=\textbf{q}\in \mathbb Z_q^n,\textbf{d}=(\textbf{d}_1^\top \;\textbf{d}_2^\top )^\top \in \{-\beta ,\beta \}^{2m},\\ \textbf{r}\in \{-\beta ,\beta \}^{m},\textbf{a}'\in \{0,1\}^{nmk},\textbf{b}\in \{0,1\}^{2nk},\textbf{v}\in \{-\beta _d,\beta _d\}^{m}\\ \textbf{e}\in \{-B,B\}^{m},\textbf{s}\in \{-B,B\}^{n},\textbf{e}_1\in \{-B,B\}^{m},\textbf{e}_2\in \{-B,B\}^{\ell },\\ \textbf{A}=[\textbf{a}_{1}|\ldots |\textbf{a}_{n}]\in \mathbb Z_q^{n\times m},\textbf{A}_t^\top =[\textbf{a}_{t,1}|\ldots |\textbf{a}_{t,n}]\in \mathbb Z_q^{m\times n}. \end{array}\right. } \end{aligned}$$

(1)

Prover’s Goal: Convince the verifier in zero-knowledge that the following set of modular linear equations holds¹ (under the same modulus q):

(2)

Since Set 2 is somewhat complicated, we first design two sub-systems: $\varPi _1$ arguing that user’s credential is issued via making a signature on her public key, and her secret key is updated rightly with time advances.; $\varPi _2$ evidencing that 1) her updatable revocation token is rightly derived from the public key and embedded in an $\textsf{LWE}$ function; 2) her identity is correctly encrypted with ciphertexts $(\textbf{c}_1,\textbf{c}_2)$. Then we establish $\varPi _{hs}$ by combining $\varPi _1$ and $\varPi _2$.

Build System $\varPi _1$. This system covers the first five equations of Set 2. Our goal is to integrate these linear equations into a uniform relation

$$\mathcal R_{1}=\{(\textbf{M}_1,\textbf{y}_1, \mathcal L_1),(\textbf{x}_1):\textbf{M}_1\cdot \textbf{x}_1=\textbf{y}_1 \wedge \textbf{x}_1\in \textsf{cons}_1\}.$$

Let $\boldsymbol{\beta }=(\beta \,\ldots \,\beta )^\top ,\boldsymbol{\beta }_d=(\beta _d\,\ldots \,\beta _d)^\top \in \mathbb Z_q^{m}$. First perform the following steps.

• 1. Set $\textbf{r}'=\textbf{r}+\boldsymbol{\beta }\in [0,2\beta ]^{m}$, $\textbf{d}_j^{'\top }=\textbf{d}_j+\boldsymbol{\beta }\in [0,2\beta ]^{m}$ for each $j \in \{1,2\}$ and $\textbf{v}'=\textbf{v}+\boldsymbol{\beta }_d\in [0,2\beta _d]^{m}$. Decompose $\textbf{r}',\textbf{d}'_j,\textbf{v}'$ such that $\textbf{r}'=\textbf{H}_{m,2\beta }\cdot \textbf{r}''$, $\textbf{d}'_j=\textbf{H}_{m,2\beta }\cdot \textbf{d}''_j$ for $j\in \{1,2\}$ and $\textbf{v}'=\textbf{H}_{m,2\beta _d}\cdot \textbf{v}''$, respectively.

• 2. Set matrices $\textbf{G}'=\textbf{G}\cdot \textbf{H}_{m,2\beta }$, $\textbf{G}'_0=\textbf{G}_0\cdot \textbf{H}_{m,2\beta }$, $\textbf{D}'_0=\textbf{D}_0\cdot \textbf{H}_{m,2\beta }$ and $\textbf{G}'_j=N_j\textbf{G}_1\cdot \textbf{H}_{m,2\beta }$ for each $j\in [\ell ]$. Assemble auxiliary matrices $\textbf{G}''_j=-N_j\textbf{G}_1\cdot \boldsymbol{\beta }$ for each $j\in [\ell ]$, and vectors $\textbf{u}'=\textbf{u}+(\textbf{G}+\textbf{G}_0)\cdot \boldsymbol{\beta }$, $\textbf{u}_1=\textbf{D}\cdot \boldsymbol{\beta }$.

• 3. Denote $[\textbf{G}'|\textbf{G}'_0|\textbf{G}'_1|\ldots |\textbf{G}'_\ell ]$ and $[\textbf{G}''_1|\ldots |\textbf{G}''_\ell ]$ as $\bar{\textbf{G}}'$ and $\bar{\textbf{G}}''$, respectively.

• 4. Denote transpose of product $(\textbf{R}_1^{\textbf{t}[d]})^{-1}\ldots (\textbf{R}_d^{\textbf{t}[1]})^{-1}$ as $\textbf{R}^{(\textbf{t})}$. Define $\textbf{N}=\textbf{R}^{(\textbf{t})}\cdot \textbf{H}_{m,q-1}$, and build the extension matrix $\textbf{L}_1=\textbf{I}_m\otimes \textbf{N}$, $\textbf{L}_2=\textbf{I}_n\otimes \textbf{1}^m$.

• 5. Let $\textbf{c}=(\textbf{a}_{t,1}[1]\textbf{v}[1]\;\ldots \;\textbf{a}_{t,1}[m]\textbf{v}[m]\;\ldots \;\textbf{a}_{t,n}[1]\textbf{v}[1]\;\ldots \;\textbf{a}_{t,n}[m]\textbf{v}[m])\in \textbf{Z}_q^{mn}$.

Through the above settings, we can change the target part of Set 2 into:

$$\begin{aligned} {\left\{ \begin{array}{ll} \textbf{F}\cdot \textbf{a}-\textbf{H}_{2n,q-1}\cdot \textbf{b}=\textbf{0 },\\ \textbf{D}'_0\cdot \textbf{r}''+\textbf{D}_1\cdot \textbf{b}-\textbf{H}_{n,q-1}\cdot \textbf{z}=\textbf{u}_1,\\ \bar{\textbf{G}}'\cdot (\textbf{d}''_1,\textbf{d}''_2,{\textbf{i}}[1]\textbf{d}''_2,\ldots ,{\textbf{i}}[\ell ]\textbf{d}''_2)^\top +\bar{\textbf{G}}''\cdot {\textbf{i}}-\textbf{D}\cdot \textbf{z}=\textbf{u}',\\ \textbf{L}_1\cdot [\textbf{a}'_1|\ldots |\textbf{a}'_n]- [\textbf{a}_{t,1}|\ldots |\textbf{a}_{t,n}]=\textbf{0 },\\ (\textbf{a}_{t,1}^\top \textbf{v}\;\ldots \;\textbf{a}_{t,n}^\top \textbf{v})^\top =\textbf{u},\\ \textbf{H}_{m,2\beta _d}\cdot \textbf{v}''-\textbf{v}-\boldsymbol{\beta }_d=\textbf{0 }. \end{array}\right. } \end{aligned}$$

(3)

After the above preparations, we can obtain the desired variables as follows:

• 1. Denote $-\textbf{H}_{n,q-1}$, $-\textbf{H}_{2n,q-1}$ and $\textbf{H}_{m,2\beta _d}$ by $\textbf{H}_1$, $\textbf{H}_2$ and $\textbf{H}_3$, respectively. Build the public matrix $\textbf{M}_1$ and vector $\textbf{y}_1$ as

  

• 2. The private witness $\textbf{x}$ can be build as

  $$(\;\textbf{a}^{'\top }\,\;\textbf{b}^\top \,\;\textbf{r}^{''\top } \,\;\textbf{z}^\top \,\;{\textbf{i}}^\top \,\,\textbf{d}_1^{''\top }\,\;\textbf{d}_2^{''\top }\,\;{\textbf{i}}[1]\textbf{d}_2^{''\top }\ldots {\textbf{i}}[\ell ]\textbf{d}_2^{''\top }\,\;\textbf{a}_{t,1}^\top \ldots \textbf{a}_{t,n}^\top \;\;\textbf{c}^\top \;\;\textbf{v}^{''\top }\;\;\textbf{v}^\top )^\top .$$

• 3. Then set $\textsf{cons}_1=\mathcal L_{1,1}\cup \mathcal L_{1,2}\cup \mathcal L_{1,3}$ where

  $$ {\left\{ \begin{array}{ll} \mathcal L_{1,1}=\{(i,i,i)\},\, i \in [1,(m+3)nk+\ell +3m\delta _{2\beta }];\\ \mathcal L_{1,2}=\{((m+3)nk+\ell +(3m+\ell )\delta _{2\beta }+mn+(u-1)m+v,\\ \qquad \quad \quad (m+3)nk+\ell +(3m+\ell )\delta _{2\beta }+(u-1)m+v,\\ \qquad \quad \quad (m+3)nk+\ell +(3m+\ell )\delta _{2\beta }+2mn+2m\delta _{\beta _d}+v)\},\\ \qquad \quad \quad u\in [n],v\in [m];\\ \mathcal L_{1,3}=\{(i,i,i)\},\,i\in [(m+3)nk+\ell +(3m+\ell )\delta _{2\beta }+2mn+1,\\ \qquad \qquad \qquad \qquad \quad \;(m+3)nk+\ell +(3m+\ell )\delta _{2\beta }+2mn+2m\delta _{\beta _d}], \end{array}\right. } $$

  where $\mathcal L_{1,1}$ indicates that $\textbf{a}',\textbf{b},\textbf{r}'',\textbf{z},{\textbf{i}},\textbf{d}''_1$ and $\textbf{d}''_2$ are all binary vectors, $\mathcal L_{1,2}$ ensures that $\textbf{c}[(u-1)m+v]=\textbf{a}_{t,u}[v]\cdot \textbf{v}[v]$ for $(u,v)\in [n]\times [m]$, and $\mathcal L_{1,3}$ ensures that $\textbf{v}''$ is binary.

Build System $\varPi _2$. This system also covers the rest part by a unified relation

$$\mathcal R_{2}=\{(\textbf{M}_2,\textbf{y}_2, \mathcal L_2),(\textbf{x}_2):\textbf{M}_2\cdot \textbf{x}_2=\textbf{y}_2 \wedge \textbf{x}_2\in \textsf{cons}_2\},$$

which evidences the correct embedding of user’s revocation token and identity. The concrete construction of $\varPi _2$ is much like that of $\varPi _1$ and we also take some preprocessing.

• 1. Let $\textbf{b}_1=(B\;\ldots \;B)^\top \in \textbf{Z}_q^m$, $\textbf{b}_2=(B\;\ldots \;B)^\top \in \textbf{Z}_q^n$ and $\textbf{b}_3=(B\;\ldots \;B)^\top \in \textbf{Z}_q^\ell$.

• 2. Set $\textbf{e}'=\textbf{e}+\textbf{b}_1$, $\textbf{s}'=\textbf{s}+\textbf{b}_2$, $\textbf{e}_1'=\textbf{e}_1+\textbf{b}_1$ and $\textbf{e}_2'=\textbf{e}_2+\textbf{b}_3$. Decompose them via functions $\textsf{vdec}$ and $\textsf{mdec}$ to get vectors $\textbf{e}'',\textbf{s}'',\textbf{e}''_1,\textbf{e}''_2$.

• 3. Compute time-binding vectors $\textbf{t}'_0=\textbf{Q}_2\cdot \textbf{t}_{add}$ and $\textbf{t}'_i=\textbf{Q}_2\cdot \textbf{t}_{i}$ for $i\in [t^*]$, set $\textbf{t}'=(\textbf{t}^{'\top }_0\;\textbf{t}^{'\top }_1\;\ldots \;\textbf{t}^{'\top }_{t^*})^\top$. Assemble quasi-diagonal matrices $\textbf{L}_3$ and $\textbf{L}_4$ as

  

• 4. Set $\textbf{B}'=\textbf{B}^\top \cdot \textbf{H}_{n,2B}$, $\textbf{P}'=\textbf{P}^\top \cdot \textbf{H}_{n,2B}$, $\textbf{I}'=\lfloor {\frac{q}{2}}\rfloor \cdot \textbf{I}_{\ell }$, $\textbf{w}'=\textbf{w}+\textbf{b}_1$, $\textbf{c}'_1=\textbf{c}_1+\textbf{b}_1+\textbf{B}^\top \cdot \textbf{b}_2$ and $\textbf{c}'_2=\textbf{c}_2+\textbf{b}_3+\textbf{B}^\top \cdot \textbf{b}_2$.

Use $\textbf{H}_4$ and $\textbf{H}_5$ to denote $\textbf{H}_{m,2B}$ and $\textbf{H}_{\ell ,2B}$, respectively. Then we can construct the target variables as follows:

• 1. Build the public matrix $\textbf{M}_2$ and vector $\textbf{y}_2$ as

  

• 2. Set $\textbf{x}_2=(\;\textbf{a}_1^\top \;\;\textbf{q}_0^\top \;\ldots \;\textbf{q}_{t^*}^\top \;\;\textbf{q}^{'\top }\;\;\textbf{q}^{'\top }_0\;\ldots \;\textbf{q}^{'\top }_{t^*-1}\;\;\textbf{e}^{''\top }\;\;\textbf{s}^{''\top }\;\;\textbf{e}_1^{''\top }\;\;\textbf{e}_2^{''\top }\;\;\textbf{i})^\top ,$ which has length $\mathfrak n_2=(t^*+2)n+(t^*+1)nk+(2m+n+\ell )\delta _{2B}+\ell$.

• 3. The constriants over $\textbf{x}_2$ is $\textsf{cons}_2=\{(i,i,i)\},\;i\in [(t^*+2)n+1,(t^*+2)n+(t^*+1)nk+(2m+n+\ell )\delta _{2B}+\ell ],$ indicating that $\textbf{q}^{'},\;\textbf{q}^{'}_0,\ldots ,\textbf{q}^{'}_{t^*-1},\;\textbf{e}^{'',},\;\textbf{s}^{''},\;\textbf{e}_1^{''},\;\textbf{e}_2^{''}$ and $\textbf{i}$ are all binary.

Build System $\boldsymbol{\varPi }_{\boldsymbol{hs}}$. We obtain the desired system $\varPi _{hs}$ by instantiating the framework in Sect. 2.3 with $\varPi _1$ and $\varPi _2$. Namely, for the final relation

$$\mathcal R_{hs}=\{(\textbf{M},\textbf{y}, \mathcal L),(\textbf{x}):\textbf{M}\cdot \textbf{x}=\textbf{y}\wedge \textbf{x}\in \textsf{cons}\},$$

set $\textbf{M}=\begin{pmatrix} \textbf{M}_1&{} \textbf{0 }\\ \textbf{0 }&{} \textbf{M}_2 \end{pmatrix}$, $\textbf{x}=\begin{pmatrix}\textbf{x}_1\\ \textbf{x}_2 \end{pmatrix}$, $\textbf{y}=\begin{pmatrix}\textbf{y}_1\\ \textbf{y}_2 \end{pmatrix}$ and $\textsf{cons}=\textsf{cons}_1 \cup \textsf{cons}'_2\cup \textsf{cons}'_3$, where $\textsf{cons}'_2$ is simply performing right shift in $\textsf{cons}_2$ by the size of $\textbf{x}_1$, and $\textsf{cons}'_3=(i,j,j)$ ensures that vector $\textbf{i}$ in two sub-systems is the same one.

4.2 Transformation to Anonymous Mutual Authentication

Although users in our $\textsf{FSSH}$ scheme can invoke $\varPi _{hs}$ to obtain $\textsf{ZK}$ proof for their group secrets, they cannot directly send the proof in $\textsf{Handshake}$. The reason is that the other participant receiving that proof can unilaterally verify its validity, so as to verify the legality of the sender without any further interactions, which obviously violates the demand for mutual authentication.

To fill the gap, below we show how to adapt the Fiat-Shamir-type framework [41], by transforming one-side identification into mutual authentication.

• $\texttt{Prove}_{\texttt{hs}}:$ On input public parameter and secret witness, produce commitments $cmt=({cmt}_s,{cmt}_r)$ and $ch=\mathcal G(cmt,\cdot )$ the same as the original algorithm. Then additionally compute a mixed challenge $\widetilde{ch}=ch\oplus \textbf{C}$ where $\textbf{C}$ is interim matrix in a $\textsf{KE}$, and generate rsp using $(cmt,\widetilde{ch})$. Finally output $\pi =({cmt}_s,\widetilde{ch},rsp)$.

• $\texttt{Verify}_{\texttt{hs}}:$ Recover ${cmt}_r$ via rsp and $\widetilde{ch}$ as $\texttt{Verify}$ does, then get the original challenge $ch'=\mathcal G(cmt,\cdot )$ by assembling $cmt=({cmt}_s,{cmt}_r)$, so as to retrieve the hidden message $\textbf{C}={ch}'\oplus \widetilde{ch}$.

Here the key point is that a receiver can no longer check the validity of the proof by checking $ch'{\mathop {=}\limits ^{?}}ch$, since he only receives $\widetilde{ch}$. On the other side, a $\textsf{KE}$ element can be recovered to negotiate a communication key for both participants, whose hash value is further dispatched to conduct authentication. This strategy can be seen as a generic way of transforming $\textsf{ZK}$ systems termed as Fiat-Shamir with abort into anonymous mutual authentication, for which a concrete instantiation is detailed in $\textsf{Handshake}$ of our main scheme.

5 FSSH with Revocability from Lattices

In this section, by devising updatable VLR method and adaptively applying the building blocks recalled in Sect. 2, we present the first $\textsf{FSSH}$ with revocability from lattice. To clarify the roadmap on how to make all things work, below we first give some key points of our construction.

When enrolling in a group, potential user first samples her initial public/secret key pair $(\textbf{A}, \textbf{T})$ via $\textsf{Trapdoor}$ and sends $\textbf{A}$ to $\textsf{GA}$, on which $\textsf{GA}$ produces an unforgeable signature [24] as her credential. Since users retain the secret keys, even a malicious $\textsf{GA}$ can not frame a legal user. To enable periodical key updating, we combine the binary-tree representation technique and ABB HIBE [2]. Namely, each node of the tree is assigned a short-norm invertible matrix $\textbf{R}_i^b$ for $i\in [d]$ and $b\in \{0,1\}$, and successive periods are associated with leaves of the binary tree in the LTR order. At the joining period $\textbf{t}=(\textbf{t}[1],\ldots ,\textbf{t}[d])$, users extract the corresponding key (trapdoor) $\textbf{T}_t$ at this leaf for $\textbf{A}(\textbf{R}_{d}^{\textbf{t}[d]}\ldots \textbf{R}_1^{\textbf{t}[1]})^{-1}$ by use of $\textsf{BasisDel}$. Observe that users can generate possible trapdoors of any leaves from the root key $\textbf{T}$. Thus, one trivial method of key update is to precompute all possible $\textbf{T}_t$ and then delete the previous one upon new period advancing. However, as noted in [28], this will bring key size undesirable dependency on T. Considering the level structure of a binary-tree, it suffices to only record the keys for sub-set $\textsf{Evolve}_{(t\rightarrow T-1)}$ [12, 26], which contains exactly one ancestor of each leaf between $[t,T-1]$ and has size at most $\log T$. Under this setting, users can update $\textsf{usk}_t$ into $\textsf{usk}_{t+1}$ (consisting of trapdoors for elements in $\textsf{Evolve}_{(t+1\rightarrow T-1)}$), by repeatedly invoking $\textsf{BasisDel}$ within $\textsf{Evolve}_{(t\rightarrow T-1)}$.

Now we demonstrate how to achieve revocability by applying VLR mechanism [11], where a revocation token $\textsf{urt}$ is issued to a user and will be published when she is revoked. Similar to the case of key exposure, it is worthwhile to protect user’s anonymity of previous behaviors even if her token is revealed (known as backward unlinkability [31]). We tackle this problem by subtly devising an updatable VLR algorithm: $\textsf{urt}_{ t}=\textbf{Q}\cdot (\textsf{vdec}(\textsf{urt}_{t-1}),\textbf{t})^\top \in \mathbb Z_q^n$. Choosing uniformly random $\textbf{Q}$, this equation is linked to an $\textsf{ISIS}$ instance, so as to achieve one-wayness of updating. Besides, we embed the time tag into the token to enable synchronous revocation check, such that expired tokens cannot be reused. Finally, to bind $\textsf{urt}_{ t}$ to user’s secret, we set the initial token as $\textbf{Q}\cdot (\textsf{vdec}(\textbf{a}_{0}),\textbf{t})^\top$, where $\textbf{a}_{0}$ is the first column of $\textbf{A}$. When executing a handshake, users need to demonstrate in zero-knowledge the possession of a valid secret. This task is done by reducing the overall linear relations set to system $\varPi _{hs}$ designed in Sect. 4.1. In particular, to argue the current $\textsf{urt}_{t}$ and $\textsf{usk}_{t}$ are correctly derived from the previous ones and are compatible with each other, we unify a time-advancing chain of iterative equations into a universal matrix-vector formula, which can be seen as a generic way of proving updatable VLR in zero-knowledge.

Finally, by combining the modified $\textsf{ZK}$ system in Sect. 4.2 with a $\textsf{KE}$ protocol [18], we obtain the desired algorithm $\textsf{Handshake}$, where participants can anonymously authenticate each other and negotiate a session key.

5.1 Description of the Scheme

As in [12, 26, 28], we imagine a binary tree of depth $d=\log T$ where the root has tag $\epsilon$. For a node at depth $\le d$ with tag w, its left and right children have tags w0 and w1, respectively. Lifetime of our scheme is divided into $T=2^d$ discrete periods, such that successive periods $t\in [T]$ are associated with leaves of the binary tree in the LTR order. To derive keys from previous periods, let $\textsf{Evolve}_{(t\rightarrow T-1)}$ be the set containing exactly one ancestor of each leaf or the leaf itself between period t and $T-1$. This set can be determined by function $\textsf{sibling}$ in [12] or algorithm $\textsf{NodeSelect}$ in [26]. Our $\textsf{FSSH}$ scheme is described as follows.

• $\textsf{Setup}$. Given a security parameter $\lambda \in \mathbb N$, this algorithm specifies the following:

  • Maximum member size of a group $N=2^\ell$, time period bound $T=2^d$.

  • Integer $n=\mathcal O(\lambda )$, prime modulus $q=\widetilde{\mathcal O}(n^2)>T$, $k=\lceil {\log q} \rceil$ and dimension $m=2nk,\overline{m}=nk$. B-bounded distribution $\chi$ over $\mathbb Z$ with $B=\sqrt{n}\omega (\log n)$.

  • Discrete Gaussian distribution $D_{\mathbb Z,\sigma }$ with parameter $\sigma =\varOmega (\sqrt{n\log q}\log n)$. Let $\beta =\lceil \sigma \cdot \log n\rceil$ be the upper bound of samples from $D_{\mathbb Z,\sigma }$.

  • Guassian parameters $\overline{\sigma }_i=m^{\frac{3}{2}i+\frac{1}{2}}\cdot \omega (\log ^{2k}n)$ for $i \in [d]$, and $\sigma _d=\overline{\sigma }_d\sqrt{m} \omega (\sqrt{\log m})$. Integer bound $\beta _d=\lceil {\sigma _d\cdot \log n}\rceil$.

  • Uniformly random vector $\textbf{u}_0\in \mathbb Z_{q}^{n}$ and matrices $\textbf{R}^b_i \leftarrow \textsf{SampleR}(1^m)$ for all $i\in [d]$ and $b\in \{0,1\}$, $\textbf{Q}=[\textbf{Q}_1|\textbf{Q}_2]\in \mathbb Z^{n\times (nk+d)}_q$, $\textbf{F}\in \mathbb Z^{2n\times nmk}_q$, $\textbf{K}\in \mathbb Z_{q_1}^{n_1\times n_1}$.

  • Matrix dimensions $n_1=\textsf{poly}(\lambda ), m_1=\mathcal {O} (n_1)$, integer modulus $q_{1} = 2^{\mathcal {O} (n_3)}$, and integer $\theta \ge \frac{2\lambda }{n_1m_1}$ for session key exchange.

  • Discrete Gaussian distribution $\chi _1$ over $\mathbb Z$ with deviation $\sigma _1 > \sqrt{\frac{2n_1}{\pi }}$.

  • Injective mapping $F: \mathbb Z_{q_1}^{n_1\times m_1} \rightarrow [-p,p]^t$ and its inverse $F^{-1}$, where p, t are defined in [41]. Random oracle $\mathcal H_0: \{0,1\}^* \rightarrow \mathbb Z_q^{m\times n}$ and collision resistant hash function $\mathcal H_1: \{0,1\}^* \rightarrow \mathbb Z_q^*$.

  Outputs global public parameter

  $$\begin{aligned} \begin{aligned} \qquad \textsf{par}=\{&N,\ell ,T,d,n,q,k,m,\overline{m},\chi ,B,\sigma ,\beta ,\{\overline{\sigma }_k\}^d_{k=1},\sigma _d,\beta _d,\textbf{R}^0_1,\textbf{R}^1_1,\ldots ,\textbf{R}^0_d,\textbf{R}^1_d,\\&\textbf{Q},\textbf{F},n_1,m_1,q_1,\theta ,\chi _1,\sigma _1,\textbf{u}_0,\textbf{K},F,F^{-1},\mathcal H_0,\mathcal H_1,\mathcal H_2\}. \end{aligned} \end{aligned}$$

• $\textsf{CreateGroup}$. On input $\textsf{par}$, $\textsf{GA}$ performs the following to establish a new group.

  • 1. Run $\textsf{TrapGen}(n,m,q)$ to get a tuple $(\textbf{G},\mathbf {T_{G}})$, then sample matrices $\textbf{G}_0,\textbf{G}_1,\textbf{D}_0,\textbf{D}_1 \leftarrow U(\mathbb Z_q^{n\times m})$, $\textbf{D}\leftarrow U(\mathbb Z_q^{n\times \overline{m}})$ and vector $\textbf{u}\leftarrow U(\mathbb Z_q^{n})$.

  • 2. Run $\textsf{TrapGen}(n,m,q)$ to generate a tracing key pair $(\textbf{B,S})$ (assume all groups share the same tracing keys).

  • 3. Set registration table $\textsf{reg}=\emptyset$ and secret key $\textsf{gsk}=(\mathbf {T_{G}},\textbf{S})$; Publish group public key $\textsf{gpk}=(\textbf{G},\textbf{G}_0,\textbf{G}_1,\textbf{D},\textbf{D}_0,\textbf{D}_1,\textbf{B},\textbf{u})$ and revocation list $\textsf{RL}=\emptyset$.

• $\textsf{AddMember}$. At time period t, one prospective user $U_i$ and $\textsf{GA}$ interact in the following protocol to enroll her in group G. Denote $\textbf{t}=(\textbf{t}[1],\ldots ,\textbf{t}[d])$ as the binary representation of t with length d hereunder.

  • 1. $U_i$ runs $\textsf{TrapGen}(n,m,q)$ to generate a pair $(\textbf{A}_i, \textbf{T}_i)$, and builds the set $\textsf{Evolve}_{(t\rightarrow T-1)}$. For $\textbf{s}\in \textsf{Evolve}_{(t\rightarrow T-1)}$, if $\textbf{s}=\perp$, set $\textsf{usk}_{i\Vert t}[\textbf{s}]=\perp$. Otherwise, denote $d_{\textbf{s}}$ as the length of $\textbf{s}$ holding $d_{\textbf{s}}\le d$, set matrix $\textbf{R}^{(\textbf{s})}=(\textbf{R}_1^{\textbf{s}[1]})^{-1}\;(\textbf{R}_2^{\textbf{s}[2]})^{-1}\ldots (\textbf{R}_{d_s}^{\textbf{s}[d_s]})^{-1}\in \mathbb Z^{n\times m}_q,$ and proceed as follows:

    • a) If $d_{\textbf{s}}=d$, compute a short vector $\textbf{v}_{i\Vert \textbf{s}}$ via $\textsf{SamplePre}(\textbf{A}_i\textbf{R}^{(\textbf{s})},\textsf{BasisDel}(\textbf{A}_i,(\textbf{R}^{(\textbf{s})})^{-1},\textbf{T}_i,\overline{\sigma }_{d}),\textbf{u},\sigma _d).$ Set $\textsf{usk}_{i\Vert t}[\textbf{s}]=\textbf{v}_{i\Vert \textbf{s}}$.

    • b) Else, evaluate $\textsf{BasisDel}(\textbf{A}_i,(\textbf{R}^{(\textbf{s})})^{-1},\textbf{T}_i,\overline{\sigma }_{d_{\textbf{s}}})$ to obtain a short basis $\textbf{T}_{i\Vert \textbf{s}}$ for $\mathrm {\varLambda }_q^{\perp }(\textbf{A}_i\textbf{R}^{(\textbf{s})})$, and set $\textsf{usk}_{i\Vert t}[\textbf{s}]=\textbf{T}_{i\Vert \textbf{s}}$.

    Now let $\textsf{upk}_i=\textbf{A}_i$ be the long-term public key and $\textsf{usk}_{i\Vert t}=\{\textsf{usk}_{i\Vert t}[\textbf{s}]\mid \textbf{s}\in \textsf{Evolve}_{(t\rightarrow T-1)}\}$ be the initial secret key of $U_i$. Finally, $U_i$ samples a proof vector $\textbf{v}_i\leftarrow \textsf{SamplePre}(\textbf{A}_i,\textbf{T}_i,\textbf{u}_0,\sigma _d)$ and sends $(\textbf{A}_i,\textbf{v}_i)$ to $\textsf{GA}$. She discards the original $\textbf{T}_i$ for forward security.

  • 2. Upon receiving the request from $U_i$, $\textsf{GA}$ first checks: (i) whether there is a collision between $\textbf{A}_i$ and the previous records of users’ public keys; (ii) whether $\textbf{A}_i$ is valid w.r.t. $\textbf{v}_i$ by verifying $\textbf{A}_i \textbf{v}_i=\textbf{u}_0$ and $\Vert {\textbf{v}_i}\Vert _\infty \le \beta _d$. If either case occurs, $\textsf{GA}$ outputs $\perp$ and aborts. Otherwise, $\textsf{GA}$ performs the following steps to issue a credential to $U_i$.

    • a) To generate user’s revocation token, set $\textsf{urt}_{i\Vert t}=\textbf{Q}_1 \cdot \textsf{vdec}_{n,q-1}(\textbf{a}_{i,0})+\textbf{Q}_2\cdot \textbf{t}\in \mathbb Z_q^n$, where $\textbf{a}_{i,0}$ is the first column of $\textbf{A}_i$ and we assume that it is a non-zero vector. In the long term, the current time period is embedded in the corresponding token, such that no adversary can deploy a previous token to conduct a handshake.

    • b) Choose a random spare $\textbf{i}\in \{0,1\}^\ell$ for user’s identity $\textsf{ID}_i$ having decimal value i. Then hash $U_i$’s public key as $\textbf{h}_i=\textbf{F}\cdot \textsf{mdec}_{n,m,q}(\textbf{A}_i^\top )\in \mathbb Z^{2n}_q$.

    • c) Encode the identity through building the compressed matrix $\textbf{G}^{(i)}=[\textbf{G}| \textbf{G}_0+i\cdot \textbf{G}_1]$. Runs $\textsf{ExtBasis}(\textbf{G}^{(i)},\mathbf {T_G})$ to get a basis $\textbf{T}_{\textbf{G}}^{(i)}$ for $\textbf{G}^{(i)}$.

    • d) Sample $\textbf{r}_i \hookleftarrow D_{\mathbb Z^m,\sigma }$, and compute the chameleon hash of $\textbf{h}_i$ as $\textbf{c}_i=\textbf{D}_0\cdot \textbf{r}_i+ \textbf{D}_1\cdot \textsf{vdec}_{2n,q-1}(\textbf{h}_i)$.

    • e) Invoke $\textsf{SamplePre}(\textbf{G}^{(i)},\textbf{T}_{\textbf{G}}^{(i)},\textbf{u}+\textbf{D}\cdot \textsf{vdec}_{n,q-1}(\textbf{c}_i),\sigma )$ to obtain a short vector $\textbf{d}_i \in \mathbb Z^{2m}$ satisfying that

      $$\begin{aligned} \textbf{G}^{(i)}\textbf{d}_i=\textbf{u}+\textbf{D}\cdot \textsf{vdec}_{n,q-1}(\textbf{c}_i) \mod q, \end{aligned}$$

      (4)

      then return the credential $\textsf{cred}_i=(\textsf{upk}_i,\textsf{ID}_i,\textsf{urt}_{i\Vert t},\textbf{d}_i,\textbf{r}_i)$ to $U_i$ and adds $\textsf{cred}_i$ to table $\textsf{reg}$.

  • 3. $U_i$ verifies that $\textsf{cred}_i$ is consistent with Eq. 4 and $\textbf{d}_i\in [-\beta ,\beta ]^{2m}$, $\textbf{r}_i\in [-\beta ,\beta ]^{m}$. She aborts if it is not the case. To avoid confusion, use $t_{i,add}=t$ to denote the time period at which $U_i$ has been registered.

• $\mathsf {Update_{U}}$. At the beginning of time period t, member $U_i$ conducts the following procedures to update her secret pair $(\textsf{cred}_{i\Vert t-1},\textsf{usk}_{i\Vert t-1})$. For revocation token update, compute $\textsf{urt}_{i\Vert t}=\textbf{Q}_1\cdot \textsf{vdec}_{n,q-1}(\textsf{urt}_{i\Vert t-1})+\textbf{Q}_2\cdot \textbf{t}\in \mathbb Z_q^n$. W.L.O.G, we assume that there is no all-zero token or two identical tokens. (Otherwise, the user would find a solution to $\textsf{SIS}_{n,q,\sqrt{nk+d}}$ problem associated with matrix $\textbf{Q}$, which is of negligible probability.) For the secret key derivation, first specify the node set $\textsf{Evolve}_{(t\rightarrow T-1)}$. Then for $\textbf{s}\in \textsf{Evolve}_{(t\rightarrow T-1)}$, if $\textbf{s}=\perp$, set $\textsf{usk}_{i\Vert t}[\textbf{s}]=\perp$, otherwise, there exists exactly one $\textbf{s}' \in \textsf{Evolve}_{(t-1\rightarrow T-1)}$ as the prefix of $\textbf{s}$, i.e., $\textbf{s}=\textbf{s}'\Vert \textbf{x}$ for some binary string $\textbf{x}$. Consider two cases:

  • 1. If $\textbf{s}=\textbf{s}'$, set $\textsf{usk}_{i\Vert t}[\textbf{s}]=\textsf{usk}_{i\Vert t-1}[\textbf{s}']$.

  • 2. Else, it holds that $\textbf{x}$ is not empty and $\textsf{usk}_{i\Vert t-1}[\textbf{s}']=\textbf{T}_{i\Vert \textbf{s}'}$ is a short basis. Compute matrix $\textbf{R}^{(\textbf{x})}=(\textbf{R}_{1+d_{\textbf{s}'}}^{\textbf{x}[1]})^{-1}\;(\textbf{R}_{2+d_{\textbf{s}'}}^{\textbf{x}[2]})^{-1}\ldots (\textbf{R}_{d_{\textbf{s}}}^{\textbf{x}[d_{\textbf{x}}]})^{-1},$ then consider the following two sub-cases:

    • a) If $d_{\textbf{s}}=d$, generate a short vector $\textbf{v}_{i\Vert \textbf{s}}$ by running $\textsf{SamplePre}(\textbf{A}_i\textbf{R}^{(\textbf{s}')} \textbf{R}^{(\textbf{x})},\textsf{BasisDel}(\textbf{A}_i\textbf{R}^{(\textbf{s}')},(\textbf{R}^{(\textbf{x})})^{-1},\textbf{T}_{i\Vert \textbf{s}'},\overline{\sigma }_{d_{\textbf{s}}}),\textbf{u},\sigma _d).$ Set $\textsf{usk}_{i\Vert t}[\textbf{s}]=\textbf{v}_{i\Vert \textbf{s}}$.

    • b) If $d_{\textbf{s}}<d$, run $\textsf{BasisDel}(\textbf{A}_i\textbf{R}^{(\textbf{s}')},(\textbf{R}^{(\textbf{x})})^{-1},\textbf{T}_{i\Vert \textbf{s}'},\overline{\sigma }_{d_{\textbf{s}}})$ to obtain a short basis $\textbf{T}_{i\Vert \textbf{s}}$, and set $\textsf{usk}_{i\Vert t}[\textbf{s}]=\textbf{T}_{i\Vert \textbf{s}}$.

  Set $\textsf{usk}_{i\Vert t}=\{\textsf{usk}_{i\Vert t}[\textbf{s}]\mid \textbf{s}\in \textsf{Evolve}_{(t\rightarrow T-1)}\}$ and erases the previous one.

• $\textsf{Handshake}$. At time period t, suppose a member A from group $G_a$ with $\textsf{gpk}_a=(\textbf{G}^{(a)},\textbf{G}_0^{(a)},\textbf{G}_1^{(a)},\textbf{D}^{(a)},\textbf{D}_0^{(a)},\textbf{D}_1^{(a)},\textbf{B},\textbf{u}_a)$, $\textsf{cred}_a=(\textsf{upk}_a,\textsf{ID}_a,\textsf{urt}_{a\Vert t},\textbf{d}_a,\textbf{r}_a)$, revocation list $\textsf{RL}_a$, $\textsf{usk}_{a\Vert t}=\{\textsf{usk}_{a\Vert t}[\textbf{s}] \mid \textbf{s}\in \textsf{Evolve}_{t\rightarrow T-1}\}$, and another member B from group $G_b$ having $(\textsf{gpk}_b,\textsf{cred}_b,\textsf{RL}_b,\textsf{usk}_{b\Vert t})$ of same structure, aim to execute a handshake. They proceed the following two-round protocol.

  • 1. $A\rightarrow B:(\texttt{PROOF}_a)$

    • a) A samples a small private key $\textbf{S}_a \hookleftarrow \chi _1(\mathbb Z_{q_1}^{n_1 \times m_1})$ and a small noise $\textbf{E}_a \hookleftarrow \chi _1(\mathbb Z_{q_1}^{n_1 \times m_1})$. Then she computes $\textbf{C}_a=\textbf{K}\cdot \textbf{S}_a+\textbf{E}_a \in \mathbb Z_{q_1}^{n_1 \times m_1}$.

    • b) Parse $\textsf{upk}_a=\textbf{A}_{a}$, A fetches the secret key for string $\textbf{t}$ from $\textsf{usk}_{a\Vert t}$ as $\textbf{v}_{a\Vert \textbf{t}}$ and assembles the corresponding matrix $\textbf{A}_{a\Vert t}$ as

      $$\begin{aligned} \textbf{A}_{a\Vert t}=\textbf{A}_a\;(\textbf{R}_1^{\textbf{t}[1]})^{-1}\;(\textbf{R}_2^{\textbf{t}[2]})^{-1}\ldots (\textbf{R}_d^{\textbf{t}[d]})^{-1}\in \mathbb Z_q^{n\times m}. \end{aligned}$$

      (5)

    • c) A samples $\rho _a{\mathop {\leftarrow }\limits ^{\$}} \{0,1\}^{n}$ and let $\textbf{W}_a=\mathcal H_0(\textsf{gpk}_a,\rho _a)$. Next, she computes $\textbf{w}_a=\textbf{W}_a\cdot \textsf{urt}_{a\Vert t}+\textbf{e}_a \mod q$ where $\textbf{e}_a \hookleftarrow \chi ^m$.

    • d) A samples $\textbf{P}_a \leftarrow U(\mathbb Z_q^{n\times \ell })$, $\textbf{s}^{(a)} \hookleftarrow \chi ^n$, $\textbf{e}^{(a)}_1\hookleftarrow \chi ^m$, $\textbf{e}^{(a)}_2\hookleftarrow \chi ^{\ell }$, so that produces the ciphertext $(\textbf{c}^{(a)}_1,\textbf{c}^{(a)}_2)$ as

      $$\begin{aligned} (\textbf{c}^{(a)}_1=\textbf{B}^\top \cdot \textbf{s}^{(a)}+\textbf{e}^{(a)}_1,\textbf{c}^{(a)}_2=\textbf{P}_a^\top \cdot \textbf{s}^{(a)}+\textbf{e}^{(a)}_2+\lfloor {\frac{q}{2}}\rfloor \cdot \textsf{ID}_a). \end{aligned}$$

      (6)

    • e) With public input $\textsf{pp}_a=(\textsf{par},\textsf{gpk}_a,\textbf{c}^{(a)}_1,\textbf{c}^{(a)}_2,t_a)$ where $t_a=t-t_{a,add}$, A runs $\texttt{Prove}_{\texttt{hs}}$ designed in Sect. 4.2 to generate a proof $\pi _a$ for $\xi _a=(\textsf{ID}_a,\textsf{urt}_{a\Vert t},\textbf{d}_a,\textbf{r}_a,\textbf{A}_{a},\textbf{v}_{a\Vert \textbf{t}},\textbf{e}_a,\textbf{s}^{(a)}, \textbf{e}^{(a)}_1,\textbf{e}^{(a)}_2),$ satisfying that:

      • $\textsf{urt}_{a\Vert t}$ is correctly derived from $\textbf{A}_{a}$ after $t_a$ times of updates.

      • $(\textsf{ID}_a,\textbf{d}_a,\textbf{r}_a)$ satisfies Eq. 4 with the specific form in $\textsf{AddMember}$.

      • $\textbf{W}_a\cdot \textsf{rt}_a+\textbf{e}_a=\textbf{w}_a$ and $\Vert {\textbf{e}_{a}}\Vert _\infty \le B$.

      • Eq. 5 holds with $\textbf{A}_{a\Vert t}\cdot \textbf{v}_{a\Vert \textbf{t}}=\textbf{u}_a \mod q$ and $\Vert {\textbf{v}_{a\Vert \textbf{t}}}\Vert _\infty \le \beta _d$.

      • Eq. 6 holds with $\Vert {\textbf{s}^{(a)}}\Vert _\infty \le B$, $\Vert {\textbf{e}^{(a)}_1}\Vert _\infty \le B$, and $\Vert {\textbf{e}^{(a)}_2}\Vert _\infty \le B$.

      Note that the challenge part of $\pi _a$ is modified as $\widetilde{ch}_a:={ch}_a \oplus F(\boldsymbol{C}_a)$.

    • f) A finally sends $\texttt{PROOF}_a=(\rho _a,\textbf{w}_a,\textbf{P}_a,\textbf{c}^{(a)}_1,\textbf{c}^{(a)}_2,t_a,\pi _a)$ to B.

  • 2. $B\rightarrow A:(\texttt{PROOF}_b,\texttt{V}_b)$

    • a) B computes $\textbf{W}'_a=\mathcal H_0(\textsf{gpk}_b,\rho _a)$. Then he checks if there exists an index i such that $\textbf{e}_i'=\textbf{w}_a-\textbf{W}'_a\cdot \textbf{v}_i$ and $\Vert {\textbf{e}_i'}\Vert _\infty \le B$ for $\textbf{v}_i \in \textsf{RL}_b$. If so, B sends A a random pair $(\texttt{PROOF}_b,\texttt{V}_b)$ and aborts. Otherwise, he continues to perform the following steps.

    • b) B runs $\texttt{Verify}_{\texttt{hs}}(\textsf{pp}'_a,\pi _a)$ where $\textsf{pp}'_a=(\textsf{par},\textsf{gpk}_b,\textbf{c}^{(a)}_1,\textbf{c}^{(a)}_2,t_a)$, to recover the hidden message of A as $\textbf{C}'_a=F^{-1}(ch'_a\oplus \widetilde{ch}_a)$.

    • c) B samples his ephemeral private key $\textbf{S}_b \hookleftarrow \chi _1(\mathbb Z_{q_1}^{n_1 \times m_1})$ and a small noise $\textbf{E}_b \hookleftarrow \chi _1(\mathbb Z_{q_1}^{n_1 \times m_1})$. Then B computes $\textbf{C}_b=\textbf{K}\cdot \textbf{S}_b+\textbf{E}_b$.

    • d) Similarly, B computes the $\textsf{LWE}$ function of his revocation token as $\textbf{w}_b=\textbf{W}_b\cdot \textsf{urt}_{b\Vert t}+\textbf{e}_b$, and encrypts his identity as $(\textbf{c}^{(b)}_1,\textbf{c}^{(b)}_2)$.

    • e) With analogous public input $\textsf{pp}_b$, B runs $\texttt{Prove}_{\texttt{hs}}$ to generate an argument $\pi _b$ for his secret tuple $\xi _b$, of which each element meets the similar constraints as that of $\xi _a$. Remark $\widetilde{ch}_b:={ch}_b \oplus F(\boldsymbol{C}^\top _b)$.

    • f) Upon obtaining $\textbf{C}'_a$, B generates the check matrix $\textbf{M}$ and the communication key $\textbf{K}_b$ as depicted in Sect. 2.4. Then B computes the authentication code $\texttt{V}_b=\mathcal H_1(\textbf{K}_b\Vert \textbf{C}_b\Vert \textbf{0})$.

    • g) B dispatches $\texttt{PROOF}_b=(\rho _b,\textbf{w}_b,\textbf{P}_b,\textbf{c}^{(b)}_1,\textbf{c}^{(b)}_2,t_b,\pi _b,\textbf{M})$ and $\texttt{V}_b$ to A.

  • 3. $A\rightarrow B:(\texttt{V}_a)$

    • a) A computes $\textbf{W}'_b=\mathcal H_0(\textsf{gpk}_a,\rho _b)$ and also checks if there exists an index j such that $\textbf{e}_j'=\textbf{w}_b-\textbf{W}'_b\cdot \textbf{v}_j$ and $\Vert {\textbf{e}_j'}\Vert _\infty \le B$ for $\textbf{v}_j \in \textsf{RL}_a$. If so, A responds a random value $\texttt{V}_a \leftarrow U(\{0,1\}^{q_1}$, outputs 0 and aborts. Otherwise, A moves to execute the following steps.

    • b) A also runs $\texttt{Verify}_{\texttt{hs}}(\textsf{pp}'_b,\pi _b)$ to retrieve ${\textbf{C}'}_b^\top =F^{-1}(\widetilde{ch}_b\oplus ch'_b)$.

    • c) A extracts the shared key $\textbf{K}_a$ following the steps in Sect. 2.4. Then A verifies that $\texttt{V}_b {\mathop {=}\limits ^{?}}\mathcal H_1(\textbf{K}_a \Vert \textbf{C}'_b \Vert \textbf{0})$. If so, A outputs 1 and sends $\texttt{V}_a=\mathcal H(\textbf{K}_a \Vert \textbf{C}_a \Vert \textbf{1})$ to B. Else, A outputs 0 and responds a random $\texttt{V}_a$.

    • d) B verifies $\texttt{V}_a$ via a similar equation $\texttt{V}_a {\mathop {=}\limits ^{?}}\mathcal H_1(\textbf{K}_b \Vert \textbf{C}'_a \Vert \textbf{1})$. B outputs 1 if the equation holds, else he outputs 0.

• $\textsf{TraceMember}$. With transcript $(\texttt{PROOF},\texttt{V})$ of a handshake executed at time period t, $\textsf{TA}$ performs the following steps to trace the involved group member:

  • 1. Parse $\texttt{PROOF}=(\rho ,\textbf{w},\textbf{P},\textbf{c}_1,\textbf{c}_2,t^*,\pi )$ where $\textbf{P}=[\textbf{p}_1\vert \ldots \vert \textbf{p}_\ell ] \in \mathbb Z_q^{n\times \ell }$. Then for all $i\in [\ell ]$, invoke $\textsf{SamplePre}(\textbf{B},\textbf{S},\textbf{p}_i, \sigma )$ to obtain a small vector $\textbf{f}_i$. Set $\textbf{F}=[\textbf{f}_1\vert \ldots \vert \textbf{f}_{\ell }]$ such that $\textbf{B}\cdot \textbf{F}=\textbf{P}\mod q$.

  • 2. Decrypt $(\textbf{c}_1,\textbf{c}_2)$ by computing $\textsf{ID}=\lfloor {{\textbf{c}_2-\textbf{F}^\top \cdot \textbf{c}_1}/{\lfloor {q/2}\rfloor }}\rfloor \in \{0,1\}^{\ell }.$

  • 3. If there exists an elements $\textsf{ID}_i=\textsf{ID}$, return $\textsf{ID}_i$. Otherwise, output $\perp$.

• $\textsf{RemoveMember}$. To remove $\textsf{ID}_i$ from group G at the beginning of period t, $\textsf{GA}$ gets the initial revocation token $\textsf{urt}_{i\Vert t_{i,add}}$ of $\textsf{ID}_i$ from table $\textsf{Reg}$, and adds it to public list $\textsf{RL}$. Since the current token can be computed from the initial one, for simplicity we assume the elements of $\textsf{RL}$ are all the updated ones.

5.2 Analysis of the Scheme

Completeness. We demonstrate that our scheme is complete with overwhelming probability if A and B belong to the same group ($\textsf{gpk}_1=\textsf{gpk}_2$) with unrevoked and updated group secret, and they both follow the specified protocol.

First, by completeness of system $\varPi _{hs}$, both A and B can produce a valid proof ($\pi _a,\pi _b$) at the first round of a handshake, which means that the receiver can always rightly recover the original challenge ${ch}'=ch$, such that they can retrieve the hidden message $\textbf{C}'=\textbf{C}$. It follows that $\textbf{K}_a\ne \textbf{K}_b$ with negligible probability from Theorem 2. Therefore, the two members can verify the corresponding equations successfully, i.e., the message authentication code $\texttt{V}_a$ ($\texttt{V}_b$) is correct. Consequently, the handshake protocol will output 1 for both participants.

Next, we show that $\textsf{TraceMember}$ always outputs $\textsf{ID}_a$ ($\textsf{ID}_b$). Observe that, the decryption procedure computes $\textbf{c}_{2}-\textbf{F}^\top \cdot \textbf{c}_{1}=\textbf{P}^\top \cdot \textbf{s}+\textbf{e}_2+\lfloor {\frac{q}{2}} \rfloor \cdot \textsf{ID}- \textbf{F}^\top \cdot (\textbf{B}^\top \cdot \textbf{s}+\textbf{e}_1)$, which can be further simplified into $\textbf{e}_2-\textbf{F}^\top \cdot \textbf{e}_1+\lfloor {\frac{q}{2}} \rfloor \cdot \textsf{ID}$, where $\Vert \textbf{e}_1\Vert _\infty \le B$, $\Vert \textbf{e}_2\Vert _\infty \le B$, and $\Vert \textbf{f}_i\Vert _\infty \le \lceil {\sigma \cdot \log m}\rceil$ implied by Lemma 1. Recall that $q=\widetilde{\mathcal O}(n^2)$, $m=2n\log q$ and $B=\sqrt{n}\omega (\log n)$. Hence we always have $\Vert {\textbf{e}_2-\textbf{F}^\top \cdot \textbf{e}_1} \Vert _\infty \le B+m\cdot B \cdot \lceil {\sigma \cdot \log m}\rceil < q/5$, inducing that the $\textsf{ID}=\textsf{ID}_a$.

Security. Now we give security analysis for our scheme, proof of the following theorem is deferred to Appendix A.

Theorem 3

In the random oracle model, our scheme satisfies the forward impersonator resistance, detector resistance and backward unlinkability under the $\textsf{SIS}$, $\textsf{ISIS}$ and $\textsf{LWE}$ assumptions.

Efficiency. Finally we analyze the complexity of our scheme, with respect to security parameter $\lambda$, two system parameters $\ell =\log N$ and $d=\log T$.

• Group public key contains several matrices and a vector with bit-size $\widetilde{\mathcal O}(\lambda ^2)$.

• Group credential consists of 4 vectors and has bit-size $\widetilde{\mathcal O}(\lambda +\ell )$.

• User secret key has one vector from $\textsf{SamplePre}$ and at most d trapdoor matrices from $\textsf{BasisDel}$, all of which have bit-size $\widetilde{\mathcal O}(\lambda ^2d^3)$.

• The communication cost of a handshake protocol can be viewed as four parts: $(\rho ,\textbf{w},\textbf{P},t)$ for revocation check; Modified $\textsf{ZK}$ argument $\pi _{hs}$, whose bit-size largely relies on the length of witness $\textbf{x}$ and can be quantized as $\widetilde{\mathcal O}(\lambda ^2+d\cdot \lambda +\ell ^2)$; Two $\textsf{IBE}$ ciphertexts and one authentication code. Overall, the dispatched data has bit-size $\widetilde{\mathcal O}(\lambda ^2+(d+\ell )\cdot \lambda +\ell ^2)$.

• Dynamic revocation list has bit-size $\widetilde{\mathcal O}(N\cdot \lambda )$.

Table 1. Comparison between scheme [5] and ours.

In Table 1, we give a detailed comparison of our scheme with the only known lattice-based one [5], in terms of efficiency and functionality. Note that forward security is achieved with a reasonable increase in communication cost, thanks to the more efficient $\textsf{ZK}$ system [41]. Besides, our scheme allows dynamic user enrollment. In other words, users autonomously generate their secret keys rather than being issued by $\textsf{GA}$, which prevents malicious $\textsf{GA}$ from framing honest users.

A A Deferred Proof of Theorem 3

Proof

We prove Theorem 3 by separately proving that our scheme satisfies the 3 required properties defined in Sect. 3.

Forward Impersonator Resistance. We prove this property by contradiction. Suppose that a PPT adversary $\mathcal A$ succeeds in experiment $\textbf{Exp}^{\mathsf F\text{- }\textsf{IR}}_{\mathcal A}$ with non-negligible advantage $\epsilon$. Then we can build a PPT algorithm $\mathcal B$ that solves $\textsf{SIS}_{n,m,q,2\sqrt{m}\beta _d}$ problem with non-negligible probability.

Given an $\textsf{SIS}$ instance $\textbf{A}\in \mathbb Z_q^{n\times m}$, the goal of $\mathcal B$ is to find a non-zero vector $\textbf{z}\in \mathbb Z_q^m$ such that $\textbf{A}\cdot \textbf{z}=\textbf{0}\mod q$ and $\Vert {\textbf{z}}\Vert \le \sqrt{m}\beta$. Towards this goal, $\mathcal B$ first prepares a simulated attack environment for $\mathcal A$ as follows:

• Randomly guess the target user’s identity $\textsf{ID}^*: \textbf{i}^*\in \{0,1\}^\ell$ and forgery time period $t^*\in [0,T-1]$.

• Sample random matrices $\textbf{R}_1^{\textbf{t}^*[1]},\textbf{R}_2^{\textbf{t}^*[2]},\ldots ,\textbf{R}_d^{\textbf{t}^*[d]}\in \mathbb Z^{m\times m}$ from the distribution $\mathcal D_{m\times m}$. Set $\textbf{A}_{i^*}=\textbf{A}\;\textbf{R}_d^{\textbf{t}^*[d]}\cdots \textbf{R}_2^{\textbf{t}^*[2]}\;\textbf{R}_1^{\textbf{t}^*[1]}\in \mathbb Z_q^{n\times m}$, which is the public key of target user $\textsf{ID}^*$.

• Sample $\textbf{v}\hookleftarrow D_{\mathbb Z^m,\sigma _d}$. If $\Vert {\textbf{v}}\Vert _\infty >\beta _d$, then repeat the sampling. Compute $\textbf{u}^*=\textbf{A}\cdot \textbf{v}\mod q$.

• Assemble d matrices $\textbf{F}_j=\textbf{A}_{i^*}\;(\textbf{R}_1^{\textbf{t}^*[1]})^{-1}\ldots (\textbf{R}_j^{\textbf{t}^*[j]})^{-1}$ for $j\in [0,d-1]$ ($\textbf{F}_0=\textbf{A}_{i^*}$). For each $\textbf{F}_j$, invoke $\textsf{SampleRwithBasis}(\textbf{F}_j)$ to obtain a matrix $\textbf{R}_{j+1}^{1-\textbf{t}^*[j+1]}$, along with a short basis $\textbf{T}_{j+1}$ for $\mathrm {\varLambda }^{\bot }(\textbf{F}'_{j+1})$ where $\textbf{F}'_{j+1}=\textbf{F}_j\;(\textbf{R}_{j+1}^{1-\textbf{t}^*[j+1]})^{-1}$. As the simulation in [2], $\mathcal B$ can use these bases to generate $\textsf{ID}^*$’s secret key for every period $t'>t^*$.

• Generate other elements of $(\textsf{gpk}^*,\textsf{gsk}^*)$ for group $G^*$ that $\textsf{ID}^*$ belongs to.

• Operates as $\textsf{GA}$ in algorithm $\textsf{AddMember}$ to determine the target user’s credential $\textsf{cred}_{\textsf{ID}^*\Vert t^* }$ at period $t^*$.

Note that, by construction, the distribution of $(\textsf{par}^*,\textsf{gpk}^*,\textsf{gsk}^*,\textsf{cred}_{\textsf{ID}^*\Vert t^* })$ is statistically close to that of the real scheme, and the choice of $(\textsf{ID}^*,t^*)$ is hidden from the adversary.

$\mathcal B$ responds to $\mathcal A$’s queries of $\{\textsf{KeyP,Trace,Remove,AddU,KeyG}\}$ exactly the same as the real scheme. For other queries at current period t, $\mathcal B$ interacts with $\mathcal A$ as follows.

• When $\mathcal A$ queries random oracles $\mathcal H_0$ or $\mathcal G$, $\mathcal B$ replies with uniformly random strings and records the inputs/outputs of these queries.

• For queries of oracle $\textsf{CorU}$, if the requested user has been already corrupted, i.e., $(\textsf{ID},\cdot ,\cdot ,\;)\in \textsf{CU}$, $\mathcal B$ aborts. Otherwise, consider two cases:

  • i) The chosen user’s identity is $\textsf{ID}^*$. If $t\le t^*$, $\mathcal B$ aborts. Otherwise, for each node $\textbf{s}\in \textsf{Evolve}_{t\rightarrow T-1}$, denote the length of $\textbf{s}$ as $d_{\textbf{s}}$, $\mathcal B$ first computes the smallest index $j_{\textbf{s}}$ such that $1\le j_{\textbf{s}} \le d_{\textbf{s}}$ and $\textbf{s}[j_{\textbf{s}}]\ne \textbf{t}^*[j_{\textbf{s}}]$. After setting delegation matrix ${\textbf{R}}^{(\textbf{s})}=(\textbf{R}_{j_{\textbf{s}}+1}^{\textbf{s}[j_{\textbf{s}}+1]})^{-1}\cdots (\textbf{R}_{d_{\textbf{s}}}^{\textbf{s}[d_{\textbf{s}}]})^{-1}$, $\mathcal B$ computes $\textsf{usk}_{i^*\Vert t}[\textbf{s}]$ via $\textsf{SamplePre}(\textbf{F}'_{j_{\textbf{s}}}\textbf{R}^{(\textbf{s})},\textsf{BasisDel}(\textbf{F}'_{j_{\textbf{s}}},(\textbf{R}^{(\textbf{s})})^{-1},\textbf{T}_{j_{\textbf{s}}},\overline{\sigma }_{d_{\textbf{s}}}),\textbf{u},\sigma _d)$ if $d_{\textbf{s}}=d$, or via $\textsf{BasisDel}(\textbf{F}'_{j_{\textbf{s}}},(\textbf{R}^{(\textbf{s})})^{-1},\textbf{T}_{j_{\textbf{s}}},\overline{\sigma }_{d_{\textbf{s}}})$ if $d_{\textbf{s}}<d$. Next, $\mathcal B$ builds $\textsf{usk}_{i^*\Vert t}$ and derives $\textsf{cred}_{i^*\Vert t}$ as in our main scheme. Finally $\mathcal B$ returns the secret pair to $\mathcal A$ and adds $(\textsf{ID}^*,G^*,t)$ to $\textsf{CU}$. Note that $\mathcal A$ can not obtain the target user’s secret until period $t^*+1$.

  • ii) $\textsf{ID}\ne \textsf{ID}^*$, then $\mathcal B$ can perfectly answer the query as it stores the initial secret key (a short basis $\textbf{T}$) when $\textsf{ID}$ was enrolled in group G. In other words, $\mathcal B$ performs as that in $\textsf{Update}_{\mathsf U}$ to derive user’s secret pair $(\textsf{cred}_{\textsf{ID}\Vert t},\textsf{usk}_{\textsf{ID}\Vert t})$ and returns it to $\mathcal A$. Finally, it adds $(\textsf{ID},G,t)$ to $\textsf{CU}$.

• For queries of oracle $\textsf{HS}$ with input $\textsf{ID}$, if $(\textsf{ID},\cdot ,\cdot \;)\in \textsf{CU}$, $\mathcal B$ aborts. Otherwise, if $\textsf{ID}\ne \textsf{ID}^*$ or $t>t^*$, $\mathcal B$ acts as in algorithm $\textsf{Handshake}$ using the corresponding secrets. Else, $\mathcal B$ has to answer without using the user’s secret key. To do so, $\mathcal B$ also performs the same as in $\textsf{Handshake}$, except that in the second flow $\mathcal B$ generates a simulated proof $\pi '$ by utilizing the well-designed simulator of applied $\textsf{NIZKAoK}$ [41].

We claim that $\mathcal A$ cannot distinguish whether it interacts with a real challenger or with $\mathcal B$. First, the secret pair of $\textsf{ID}^*$ given to $\mathcal A$ after period $t^*$ is indistinguishable from the real one, due to the facts that

• i) the revocation token is uniform over $\mathbb Z_q^n$ and other elements of $\textsf{cred}_{\textsf{ID}^*\Vert t }$ are produced in the same way as that in $\textsf{AddMember}$;

• ii) the outputs of $\textsf{BasisDel}$ are uniformly random by Lemma 5. Second, the handshake queries make no difference to the view of $\mathcal A$, implied by the zero knowledge property of the underlying $\textsf{NIZKAoK}$.

After $\mathcal A$ halts with her output $\texttt{PROOF}^*=(\rho ^*,\textbf{w}^*,\textbf{P}^*,\textbf{c}^*_1,\textbf{c}^*_2,\hat{t},\pi ^*)$ at period $t'$, $\mathcal B$ checks if $t'=t^*$. If not, the guess of the impersonator period $t^*$ fails and $\mathcal B$ aborts. Else, parse $\pi ^*=(cmt^*_s,\widetilde{ch}^*,rsp^*)$, since $\mathcal A$ wins, we argue that by completeness of our scheme, $\mathcal A$ must have queried the related random oracle $\mathcal G$ via Fiat-Shamir heuristic on input $\eta ^*=(cmt^*,\textsf{pp}^*)$. Otherwise, guessing correctly this value occurs only with negligible probability $\epsilon '={(\frac{1}{2p+1})}^t$. Therefore, with probability at least $\epsilon -\epsilon '$, the tuple $\eta ^*$ has been an input of one hash query, denoted as $\kappa ^* \le q_{\mathcal G}$, where $q_{\mathcal G}$ is the total number of queries to $\mathcal G$ made by $\mathcal A$.

Next, $\mathcal B$ picks $\kappa ^*$ as the target forking point and replays $\mathcal A$ polynomial time. For each new run, $\mathcal B$ starts with the same random tape and input as in the original execution, but from the $\kappa ^*$-th query onwards, $\mathcal B$ will reply to $\mathcal A$ with fresh and independent hash values. Moreover, $\mathcal B$ always replies as in the original run for queries of $\mathcal H_0$. Note that the input of $\kappa ^*$ hash query must be $\eta ^*$. The Forking Lemma in [14] implies that, with probability larger than 1/2, $\mathcal B$ can obtain 3 forks involving the same tuple $\eta ^*$, but with pairwise distinct challenges

$$\widetilde{ch}^*_{1},\;\widetilde{ch}^*_{2},\;\widetilde{ch}^*_{3} \in {[-p,p]}^t.$$

Moreover, by the binding property of used commitment scheme, $\mathcal B$ can obtain 3 valid tuples from the output of $\mathcal A$ as

$$\left\{ ({ch}^*_{1},cmt^*,rsp^*_{1}), ({ch}^*_{2},cmt^*,rsp^*_{2}),{ch}^*_{3},cmt^*,rsp^*_{3}\right\} ,$$

by first recovering the unsent ${cmt}^*_r$ and then the original ${ch}^*$. Then by proof of knowledge of system $\varPi _{hs}$, $\mathcal B$ can extract the witness

$$\xi ^*=(\textsf{ID}',\textsf{urt}^*_{\textsf{ID}'\Vert t^*},\textbf{d}^*,\textbf{r}^*,\textbf{A}_{i^*},\textbf{v}_{\textsf{ID}'\Vert \textbf{t}^*},\textbf{e}^*,\textbf{s}^*, \textbf{e}^*_1,\textbf{e}^*_2),$$

which satisfies that

• $\textsf{urt}^*_{\textsf{ID}'\Vert t^*}$ is correctly derived from $\textbf{A}_{i^*}$ after $\hat{t}$ times of updates.

• Triple $(\textsf{ID}',\textbf{d}^*,\textbf{r}^*)$ has the specific form as that in algorithm $\textsf{AddMember}$ and satisfies Eq. 4.

• $\textbf{W}^*\cdot \textsf{urt}^*_{\textsf{ID}'\Vert t^*}+\textbf{e}^*=\textbf{w}^*$ and $\Vert {\textbf{e}^*}\Vert _\infty \le B$, where $\textbf{W}^*=\mathcal H_1(\textsf{gpk}^*,\rho ^*)$.

• $\textbf{A}_{\textsf{ID}'\Vert t^*}=\textbf{A}_{i^*}\;(\textbf{R}_1^{\textbf{t}^*[1]})^{-1}\;(\textbf{R}_2^{\textbf{t}^*[2]})^{-1}\ldots (\textbf{R}_d^{\textbf{t}^*[d]})^{-1}$.

• $\textbf{A}_{\textsf{ID}'\Vert t^*}\cdot \textbf{v}_{\textsf{ID}'\Vert \textbf{t}^*}=\textbf{u}^* \mod q$ and $\Vert {\textbf{v}_{\textsf{ID}'\Vert \textbf{t}^*}}\Vert _\infty \le \beta _d$.

• $\textbf{c}^*_1=\textbf{B}^{^*\top }\cdot \textbf{s}^*+\textbf{e}^*_1,\textbf{c}^*_2=\textbf{P}^{*\top } \cdot \textbf{s}^*+\textbf{e}^*_2+\lfloor {\frac{q}{2}}\rfloor \cdot \textsf{ID}'$, where $\Vert {\textbf{s}^*}\Vert _\infty \le B$, $\Vert {\textbf{e}^*_1}\Vert _\infty \le B$, and $\Vert {\textbf{e}^*_2}\Vert _\infty \le B$.

Now consider the following cases:

a. There is no element in table $\textsf{reg}$ that contains $\textsf{ID}'$. This implies that the pair $\left( \textbf{A}^*,(\textsf{ID}',\textbf{d}^*,\textbf{r}^*)\right)$ forms a forgery for the $\textsf{SIS}$-based signature of Sect. 2.2.

b. $\textsf{ID}'\ne \textsf{ID}^*$, indicating the guess of the impersonator user fails, then $\mathcal B$ aborts.

c. Conditioned on guessing correctly $t^*$ and $\textsf{ID}^*$, we have that $\textbf{A}_{\textsf{ID}'\Vert t^*}\cdot \textbf{v}_{\textsf{ID}'\Vert \textbf{t}^*}=\textbf{A}\cdot \textbf{v}_{\textsf{ID}'\Vert \textbf{t}^*}=\textbf{u}^* \mod q$, recall that $\textbf{A}_{i^*}=\textbf{A}\;\textbf{R}_d^{\textbf{t}^*[d]}\cdots \textbf{R}_2^{\textbf{t}^*[2]}\;\textbf{R}_1^{\textbf{t}^*[1]}$. Besides, with the fact that $\mathcal A$ either queried the secret key of $\textsf{ID}^*$ after period $t^*$ or never requested it at all, it is clear that $\textbf{v}$ is not known to $\mathcal A$. In this sense, because $\textbf{v}$ has large min-entropy given $\textbf{u}^*$, we argue that $\textbf{v}_{\textsf{ID}'\Vert \textbf{t}^*}\ne \textbf{v}$ with overwhelming probability. Now let $\textbf{z}=\textbf{v}_{\textsf{ID}'\Vert \textbf{t}^*}- \textbf{v}\in \mathbb Z_q^m$, it holds that i) $\textbf{z}\ne \textbf{0}$; ii) $\textbf{A}\cdot \textbf{z}=\textbf{0 }\mod q$; iii) $\Vert {\textbf{z}}\Vert \le \sqrt{m}\cdot \Vert {\textbf{z}}\Vert _\infty \le \sqrt{m} \cdot (\Vert {\textbf{v}_{\textsf{ID}'\Vert \textbf{t}^*}}\Vert _\infty +\Vert {\textbf{v}}\Vert _\infty )\le 2\sqrt{m}\beta _d$. $\mathcal B$ finally outputs $\textbf{z}$, which is a valid solution of the given $\textsf{SIS}_{n,m,q,2\sqrt{m}\beta _d}$ instance.

We observe that the probability that $\mathcal B$ does not abort is at least $\frac{1}{q_G\cdot N\cdot T}$, and conditioned on not aborting, it can solve the $\textsf{SIS}_{n,m,q,2\sqrt{m}\beta _d}$ problem with probability larger than 1/2.

Detector Resistance. We define a sequence of hybrid games $\mathsf G^b_i$ for $i\in [0,5]$ and $\mathsf G_6$, such that game $\mathsf G^b_0$, for $b\in \{0,1\}$, is the original experiment $\textbf{Exp}^{\mathsf {DR-b}}_{\mathcal A}$. We then prove that any two consecutive games are indistinguishable. Detector resistance follows from the fact that game $\mathsf G_6$ is independent of the bit b. For consistency, use $\textsf{ID}_b$ to denote the involved user ($\textsf{ID}_b=\textsf{ID}^*$ or $\textsf{ID}_r$ for $b=0$ or 1, respectively).

Game $\mathsf G_0^{b}$: This is exactly the original game $\textbf{Exp}^{\mathsf {DR-b}}_{\mathcal A}$, where $\mathcal B$ relies with random strings for oracle queries of $\mathcal H_0$ and $\mathcal G$.

Game $\mathsf G_1^{b}$: This game is the same as Game $\mathsf G_0^{b}$ with only one modification: at the challenge query $\textsf{Chal}_b^{\textsf{DR}}$, we utilize the well-designed simulator in [41], so as to produce a simulated proof $\widetilde{\pi }^*$, which is computationally indistinguishable from the real one due to zero knowledge of the underlying system.

Game $\mathsf G_2^{b}$: There is one change in Game $\mathsf G_2^{b}$: for the token embedding step in the challenge query, compute the $\textsf{LWE}$ function of revocation token using a random nonce $\textbf{s}$ instead of the real value $\textsf{urt}_{\textsf{ID}_b\Vert t^*}$, namely, $\textbf{w}^*=\textbf{W}\cdot \textbf{s}+\textbf{e}^* \mod q$ where $\textbf{s}\leftarrow U(\mathbb Z_q^n)$. Recall that the current token $\textsf{urt}_{\textsf{ID}_b\Vert t^*}=\textbf{Q}_1\cdot \textsf{vdec}_{n,q-1}(\textsf{urt}_{\textsf{ID}_b\Vert t^*-1})+\textbf{Q}_2\cdot \textbf{t}^*$ is statistically close to uniform over $\mathbb Z_q^n$. Thus, Game $\mathsf G_2^{b}$ and $\mathsf G_1^{b}$ are statistically indistinguishable.

Game $\mathsf G_3^{b}$: This game follows Game $\mathsf G_2^{b}$ with one difference: sample $\textbf{w}^*$ uniformly from $\mathbb Z_q^m$. Note that in the previous game, $\textbf{W}$ is uniformly random over $\mathbb Z_q^{m\times n}$, so the pair $(\textbf{W},\textbf{w}^*)$ is a valid $\textsf{LWE}_{n,q,\chi }$ instance and its distribution is computationally close to the uniform distribution over $\mathbb Z_q^{m\times n} \times \mathbb Z_q^m$. Thus, the two games are computationally indistinguishable.

Game $\mathsf G_4^{b}$: This game conducts the same as that in Game $\mathsf G_3^{b}$, except that it uses matrix $\textbf{B}'\leftarrow U(\mathbb Z_q^{n\times m})$ to encrypt users’ identity. From Lemma 2, we know that the original matrix $\textbf{B}$ is statistically close to uniform over $\mathbb Z_q^{n\times m}$. Hence, the two games are statistically indistinguishable.

Game $\mathsf G_5^{b}$: This game encrypts the identity with random samples, namely, it generates ciphertexts $\textbf{c}'_1=\textbf{z}_1$ and $\textbf{c}'_2=\textbf{z}_2+\lfloor {\frac{q}{2}}\rfloor \cdot \textsf{ID}_b$ where $\textbf{z}_1\leftarrow U(\mathbb Z_q^m)$, $\textbf{z}_2\leftarrow U(\mathbb Z_q^\ell )$. Based on the hardness of decision$\text{- }\textsf{LWE}$, we have that Game $\mathsf G_5^{b}$ and $\mathsf G_4^{b}$ are computationally indistinguishable.

Game $\mathsf G_6$: This game is the same as Game $\mathsf G_5^{b}$ except that it replaces the ciphertexts with random vectors, i.e., $\textbf{c}''_1=\textbf{z}'_1$ and $\textbf{c}''_2=\textbf{z}'_2$ where $\textbf{z}'_1\leftarrow U(\mathbb Z_q^m)$, $\textbf{z}'_2\leftarrow U(\mathbb Z_q^\ell )$. Since users’ identity is an unknown random string in the view of $\mathcal A$, it is clear that Game $\mathsf G_6$ and $\mathsf G_5^{b}$ are statistically indistinguishable.

Combine the whole analysis above, we have that

$$\mathsf G_0^{0}{\mathop {\approx }\limits ^{c}}\mathsf G_1^{0}{\mathop {\approx }\limits ^{s}}\mathsf G_2^{0}{\mathop {\approx }\limits ^{c}}\mathsf G_3^{0}{\mathop {\approx }\limits ^{s}}\mathsf G_4^{0}{\mathop {\approx }\limits ^{c}}\mathsf G_5^{0}{\mathop {\approx }\limits ^{s}}\mathsf G_6,\;\mathsf G_6{\mathop {\approx }\limits ^{s}}\mathsf G_5^{1}{\mathop {\approx }\limits ^{c}}\mathsf G_4^{1}{\mathop {\approx }\limits ^{s}}\mathsf G_3^{1}{\mathop {\approx }\limits ^{c}}\mathsf G_2^{1}{\mathop {\approx }\limits ^{s}}\mathsf G_1^{1}{\mathop {\approx }\limits ^{c}}\mathsf G_0^{1},$$

it then follows that $|\textrm{Pr}[\textbf{Exp}^{\mathsf {DR-1}}_{\mathcal A}=1]-\textrm{Pr}[\textbf{Exp}^{\mathsf {DR-0}}_{\mathcal A}=1]|=\textsf{negl}(\lambda ).$ This concludes the proof.

Backward Unlinkability. Experiment $\textbf{Exp}^{\mathsf {B\text{- }Unlink-b}}_{\mathcal A}$ is much similar to $\textbf{Exp}^{\mathsf {DR-b}}_{\mathcal A}$, in the sense that the challenger also picks one out of two users to simulate a handshake with $\mathcal A$ twice, except now the arbitrary user is predetermined as $\textsf{ID}_1$. Therefore we can also build a sequence of hybrid games to prove this property as the above constructions, with the only difference that we need to additionally argue the anonymity of revoked users (attribute “backward”). To this effect, it suffices to prove that the publicity of revocation tokens at period $t'$ brings no advantage for $\mathcal A$ at period t holding $t<t'$. We tackle this issue in two steps:

First we demonstrate that the update algorithm for revocation token is one-way, i.e., it is impossible to recover a previous token from the current one, the claimed fact is as follows.

Lemma 6

The update function of revocation token defined in algorithm $\mathsf {{Update}_U}$ is one-way, assuming the hardness of $\textsf{ISIS}_{n,q,\sqrt{nk}}$ problem.

Proof

Let $\textbf{u}=\textsf{urt}_{i\Vert t}-\textbf{Q}_2\cdot \textbf{t}\in \mathbb Z_q^n$, if one can recover the previous token $\textsf{urt}_{i\Vert t-1}:=\textbf{v}\in \mathbb Z_q^n$ from the current one, satisfying that $\textsf{urt}_{i\Vert t}=\textbf{Q}_1\cdot \textsf{vdec}_{n,q-1}(\textbf{v})+\textbf{Q}_2\cdot \textbf{t}\mod q$, then one can obtain a non-zero vector $\textbf{z}=\textsf{vdec}_{n,q-1}(\textbf{v}) \in \{0,1\}^{nk}$ such that $\textbf{Q}_1\cdot \textbf{z}=\textbf{u}\mod q$. In other words, $\textbf{z}$ is a valid solution to the $\textsf{ISIS}_{n,q,\sqrt{nk}}$ problem associated with matrix $\textbf{Q}_1$ and vector $\textbf{u}$.

Next we show that $\mathcal A$ gains no extra advantage after knowing later revocation tokens (e.g., $\textsf{urt}_{i\Vert t+1}$). It suffices to prove that $\mathcal A$ still can not distinguish the $\textsf{LWE}$ instance $(\textbf{W}, \textbf{w}^*)$ in Game $\mathsf G_2^{b}$ from real random samples.

Suppose that now Game $\mathsf G_2^{b}$ and $\mathsf G_3^{b}$ are distinguishable with a non-negligible advantage, which directly implies that $\mathcal A$ solves decision$\text{- }\textsf{LWE}$ with non-negligible probability. It then follows that $\mathcal A$ can also solve search$\text{- }\textsf{LWE}$ with non-negligible probability and a larger sample number $m'=\textsf{poly}(m)$, implying $\mathcal A$ can find the secret token $\textsf{urt}_{i\Vert t}$ at current period t by use of $\textsf{urt}_{i\Vert t+1}$. In this way, $\mathcal A$ will break the one-way property of the update function stated in Lemma 6.