Secure Group Communications Using Twisted Group Rings

Abstract

In this paper we introduce a Group Key Management protocol following the idea of the classical protocol that extends the well-known Diffie–Hellman key agreement to a group of users. The protocol is defined in a non-commutative setting, more precisely, in a twisted dihedral group ring. The protocol is defined for an arbitrary cocycle, extending previous key agreements considered for two users. The main objective of this work is to show that there is no lack of security derived from the fact that a larger amount of public information is known by an external observer.

1. Introduction

In recent years, new hard problems have been proposed in public key cryptography, since those that we are using might be not secure soon. When two parties want to communicate through an insecure channel, they need to undertake a key agreement, which consists of agreeing on a secret shared key by exchanging information that does not compromise the common key.

The first widely used protocol that allows this to happen was proposed in 1976 by W. Diffie and M. Hellman [1], and works as follows:

Let Alice and Bob be two users, who want to agree on a common key through an insecure channel. Consider p a prime number, ${\mathbb{Z}}_p^{*}$ the multiplicative group of integers modulo p, and g a primitive root modulo p, all of them public.

(i)

Alice chooses a secret integer a, and sends Bob $p_A=g^a($mod $p)$.

(ii)

Bob chooses a secret integer b, and sends Alice $p_B=g^b($mod $p)$.

(iii)

Alice computes $p_B^a($mod $p)$, and Bob computes $p_A^b($mod $p)$, so both obtain the same value, which is the secret shared key $K=g^{ab}($mod $p)$.

Information shared does not compromise the shared key since the underlying problem an attacker would need to solve, the so-called Discrete Logarithm Problem (DLP) is believed to be hard. This key agreement can be seen as an example of the protocol by Maze et al. [2] in a general setting:

Let S be a finite set, G an abelian semigroup, $\varphi$ a $G-$action on S, and a public element $s\in S$.

(i)

Alice chooses $a\in G$, and sends Bob $p_A=\varphi (a,s)$.

(ii)

Bob chooses $b\in G$, and sends Alice $p_B=\varphi (b,s)$.

(iii)

Alice computes $\varphi (a,p_B)$, and Bob computes $\varphi (b,p_A)$, so both obtain the secret shared key $K=\varphi (a,\varphi (b,s\left)\right)=\varphi (b,\varphi (a,s\left)\right)$.

The underlying problem that gives sense to its security is known as the Semigroup Action Problem (SAP).

Semigroup Action Problem. Given a semigroup action $\varphi$ of the group G on a set S and elements $x\in S$ and $y\in G$, find $g\in G$ such that $\varphi (g,x)=y$.

Motivated by this, the authors proposed in [3] a new setting, and some protocols, which extend these techniques to a non-commutative setting. In this case this is a twisted group ring, an extension of group rings, that have also been recently used in cryptography (cf. [4,5,6,7]). The action proposed in [3] is the two-sided multiplication in a twisted group ring. Thus the problem which the security of this new proposal is based on, is a modification in the twisted case of the so-called Decomposition Problem (DP).

Decomposition Problem. Given a group G, $(x,y)\in G\times G$ and $S\subset G$, the problem is to find $z_1,z_2\in S$ such that $y=z_{1}x{z}_2$.

A natural problem is how to extend this kind of key management protocol for two users to a greater set of these. In the classic Diffie–Hellman protocol, a solution is proposed in [8]; and in the more general case of SAP, this solution can be found in [9]. In both cases, it is shown that the extra information shared in the case of a n users, key exchange (≥2) does not imply any information leakage than in to the 2-users case.

Our aim in this work is to show that in this new setting, which differs from those above, given the non-commutativity of twisted group rings, these kind of protocols could be useful as well. Moreover, they could even avoid possible threats in the known cases.

2. Results

2.1. Algebraic Setting

In this section, twisted group rings are defined, and we also show some properties that allow the key exchange.

Definition 1.

Let K be a ring and G a finite multiplicative group. Let $U\left(K\right)$ be the units of K. We call the map $\alpha :G\times G\to U\left(K\right)$ a 2-cocycle if $\alpha (1,1)=1$ and for all $g,h,k\in G$ it satisfies the equation

$$\alpha (g,hk)\alpha (h,k)=\alpha (gh,k)\alpha (g,h)$$

(1)

We denote the set of all 2-cocycles of G by $Z^2(G,U\left(K\right))$.

Definition 2.

Let K be a ring, G be a multiplicative group, and $\alpha \in Z^2(G,U\left(K\right))$. The group ring $K^{\alpha }G$ is defined to be the set of all finite sums of the form

$$\sum _{g_i\in G}{r}_i{g}_i,$$

where $r_i\in K$ and all but a finite number of $r_i$ are zero.

The sum of two elements in $K^{\alpha }G$ is defined by

$$\begin{array}{c}\hfill \left(\sum _{g_i\in G}{r}_i{g}_i\right)+\left(\sum _{g_i\in G}{s}_i{g}_i\right)=\sum _{g_i\in G}(r_i+s_i)g_i.\end{array}$$

and their product, which is twisted by a cocycle, is given by

$$\left(\sum _{g_i\in G}{r}_i{g}_i\right)·\left(\sum _{g_i\in G}{s}_i{g}_i\right)=\sum _{g_i\in G}\left(\sum _{g_j{g}_k=g_i}{r}_j{s}_k\alpha (g_j,g_k)\right)g_i.$$

Let K be a finite field, G the dihedral group of $2m$ elements [10],

$$D_{2m}=\langle x,y:x^m=y^2=1,y{x}^a=x^{m-a}y\rangle$$

and $\alpha \in Z^2(D_{2m},K)$. Let $C_m=\langle x\rangle$ be the cyclic subgroup of $D_{2m}$ generated by x. Then we have that $K^{\alpha }{D}_{2m}$ is a free $K^{\alpha }{C}_m$ module with basis $\{1,y\}$, and therefore $K^{\alpha }{D}_{2m}$ is the direct sum of the $K-$vector spaces:

$$K^{\alpha }{D}_{2m}=K^{\alpha }{C}_m\oplus K^{\alpha }{C}_{m}y$$

Definition 3.

For a given 2-cocycle $\alpha \in Z^2(D_{2m},U\left(K\right))$, we define the reversible subspace of $R=K^{\alpha }G$ (where G is either $C_m$ or $C_{m}y$) as the vector subspace

$$\Gamma \left[R\right]=\left\{\sum _{i=0}^{m-1}{r}_i{x}^i{y}^k\in R:r_i=r_{m-i}\right\}.$$

We will denote ${\displaystyle {\Gamma }_{\alpha }=\Gamma \left[K^{\alpha }{C}_{m}y\right]=\left\{\sum _{i=0}^{m-1}{r}_i{x}^i{y}^k\in K^{\alpha }{C}_{m}y:r_i=r_{m-i}\right\}.}$

Now we establish some useful properties that will allow the introduction of the group key management protocol.

Definition 4.

Let $R=K^{\alpha }{D}_{2m}$ and α be a 2-cocycle. Given $h\in R$,

$$h=\sum _{\begin{array}{c}0\le i\le m-1\\ k=0,1\end{array}}{r}_i{x}^i{y}^k,$$

where $r_i\in K$ and $x,y\in D_{2m}$, we define $h^{*}\in K^{\alpha }{D}_{2m}$ as

$$h^{*}=\sum _{\begin{array}{c}0\le i\le m-1\\ k=0,1\end{array}}{r}_i\alpha {(x^{i}y,x^j{y}^k)}^{-1}{x}^i{y}^k,$$

Lemma 1.

There exist group rings $R=K^{\alpha }{D}_{2m}$, such that, given two elements $h_1,h_2\in R$,

(a) 

If $h_1,h_2\in K^{\alpha }{C}_n$, then $h_1{h}_2=h_2{h}_1$.

(b) 

If $h_1,h_2\in {\Gamma }_{\alpha }$, then $h_1{h}_2^{*}=h_2{h}_1^{*}$, and $h_1^{*}{h}_2=h_2^{*}{h}_1$.

Before giving a proof of this lemma, let us give a couple of illustrative examples.

Example 1.

Let K and $D_{2m}$ be as previously introduced.

• Let t be a primitive root of unity of K. The map ${\alpha }_1\in Z^2(D_{2m},K^{*})$ defined by ${\alpha }_1(\delta ,\mu )=1$ for $\delta =x^i,\mu =x^j{y}^k$, and ${\alpha }_1(\delta ,\mu )=t^j$ for $\delta =x^{i}y,\mu =x^j{y}^k$, where $i,j=1,\dots ,2m-1$, is a 2-cocycle that verifies Lemma 1. A proof can be found in [3].
• Let λ an element in $K^{*}$. The map ${\alpha }_2\in Z^2(D_{2m},K^{*})$ defined by ${\alpha }_2(\delta ,\mu )=\lambda$ for $\delta =x^{i}y,\mu =x^{j}y$, and ${\alpha }_2(\delta ,\mu )=1$ otherwise, where $i,j=1,\dots ,2m-1$, is a 2-cocycle that verifies Lemma 1. A proof of (a) and (b.1) can be found in [11]. We now provide a proof for (b.2).

Proof (Proof of Lemma 1)

Let $R=K^{{\alpha }_2}{D}_{2m}$, where ${\alpha }_2$ is the 2-cocycle defined above. Let $h_1,h_2\in {\Gamma }_{\alpha }$, Φ and $\phi \left(h_1\right)=\widehat{h_1}$ as defined in [11]. The equalities (a) and (b) $h_1{h}_2^{*}=h_2{h}_1^{*}$ were proven in [11]. It remains to prove that $h_1^{*}{h}_2=h_2^{*}{h}_1$. Using ([11], Lemma 3.8), we can prove the following:

$$\begin{array}{ccc}\hfill h_1^{*}{h}_2& =& \widehat{\Phi \left(h_1\right)\overline{y}}\Phi \left(h_2\right)y=\Phi \left(h_1\right)\widehat{\overline{y}}\overline{y}\Phi \left(h_2\right)={\lambda }^2\Phi \left(h_1\right)\Phi \left(h_2\right)\hfill \\ & =& {\lambda }^2\Phi \left(h_2\right)\Phi \left(h_2\right)=\Phi \left(h_1\right)\widehat{\overline{y}}\overline{y}\Phi \left(h_1\right)=\widehat{\Phi \left(h_2\right)y}\Phi \left(h_1\right)y=h_2^{*}{h}_1\hfill \end{array}$$

□

2.2. Key Management over Twisted Group Rings

In this section, we propose a key management protocol for n users. Let us define the action $\varphi$

$$\varphi :(K^{\alpha }{C}_m\times K^{\alpha }{C}_{m}y)\times R⟶R$$

$$\varphi (s_i,h)={\delta }_{i}h{\mu }_i$$

where $s_i=({\delta }_i,{\mu }_i)$. Note that

$$\varphi \left(s_i\varphi (s_j,h)\right)=\varphi (s_i{s}_j,h)$$

We will sometimes write $\varphi (s_i{s}_j,h)$ to refer to $\varphi (s_i,\varphi (s_j,h))$, to make some definitions more readable.

Let $h\in R$ be a random public element and assume that $R=K^{\alpha }{C}_m\oplus K^{\alpha }{C}_{m}y$ verifies Lemma 1. For $i=1,\dots ,n$, user $U_i$ holds a secret pair $s_i=({\delta }_i,{\mu }_i)$, where ${\delta }_i\in K^{\alpha }{C}_m$ and ${\mu }_i\in {\Gamma }_{\alpha }\subset K^{\alpha }{C}_{m}y$. Let us define the action $\varphi$ by means of a two-sided product $\varphi (s_i,h)={\delta }_{i}h{\mu }_i$. We will denote $s_i^{*}=({\delta }_i,{\mu }_i^{*})$. The initial key agreement for n users is given by the following steps:

(i)

For $i=1,\cdots ,n-1$, user $U_i$ sends to user $U_{i+1}$ the message

$$\{C_i^1,C_i^2,\dots ,C_i^{i+1}\},$$

where $C_1^1=h$, $C_1^2={\delta }_{1}h{\mu }_1$ and

• for $i>1$ even, $C_i^j=\varphi (s_i,C_{i-1}^j)$, when $j<i$, $C_i^i=C_{i-1}^i$, $C_i^{i+1}=\varphi (s_i^{*},C_{i-1}^i)$,
• for $i>1$ odd, $C_i^j=\varphi (s_i^{*},C_{i-1}^j)$, when $j<i$, $C_i^i=C_{i-1}^i$, $C_i^{i+1}=\varphi (s_i,C_{i-1}^i)$.

(ii)

User $U_n$ computes the shared key $\varphi (s_n,C_{n-1}^n)$ in case n is odd and $\varphi (s_n^{*},C_{n-1}^n)$ if n otherwise.

(iii)

User $U_n$ broadcasts

$$\{C_n^1,C_n^2,\dots ,C_n^{n-1}\}.$$

(iv)

User $U_i$ ($i=1,\cdots ,n-1$) computes $\varphi (s_i,C_n^i)$ if n is odd or $\varphi (s_i^{*},C_n^i)$ if n is even.

This protocol allows all users to obtain a common shared key. For $\alpha ={\alpha }_1$, this was shown in Proposition 3 of [3]. Now we prove it for $\alpha ={\alpha }_2$.

Proposition 1.

Let $R=K^{{\alpha }_2}{D}_{2m}$. After this protocol, users $U_1,\cdots ,U_n$ agree on a common key.

Proof of Proposition 1.

Firstly, we will consider that n is odd. Let us show that users $U_1,\cdots ,U_{n-1}$ get the same key and that this is equal to $U_n$ key. To do so, we will prove by induction that

$$\varphi (s_i,C_n^i)=\varphi (s_j,C_n^j)$$

for $i\ne j$, $i,j\in \{1,\cdots ,n-1\}$ and that these are also equal to the key that $U_n$ recovers, $\varphi (s_n,C_{n-1}^n)$. For $n=3$,

$$\begin{array}{ccc}\hfill \varphi (s_1,C_3^1)& =& \varphi (s_1,{\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*})\hfill \\ & =& {\delta }_1{\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*}{\mu }_1\hfill \\ & =& {\delta }_2{\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*}{\mu }_2\hfill \\ & =& \varphi (s_2,{\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*})\hfill \\ & =& \varphi (s_2,C_3^2)\hfill \end{array}$$

using the commutativity rules given by in Lemma 1,

$${\mu }_2{\mu }_3^{*}{\mu }_1={\mu }_2{\mu }_1^{*}{\mu }_3={\mu }_1{\mu }_2^{*}{\mu }_3={\mu }_1{\mu }_3^{*}{\mu }_2.$$

Moreover, $\varphi (s_3,C_2^3)={\delta }_3{\delta }_2{\delta }_{1}h{\mu }_1{\mu }_2^{*}{\mu }_3={\delta }_2{\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*}{\mu }_2=\varphi (s_2,C_3^2)$.

Now, suppose that

$$\varphi (s_i,C_n^i)=\varphi (s_j,C_n^j).$$

Then we have

$$\begin{array}{ccc}\hfill \varphi (s_i^{*},C_{n+1}^i)& =& \varphi (s_i^{*},\varphi (s_{n+1},C_n^i))\hfill \\ & =& \varphi (s_i^{*}{s}_{n+1},C_n^i)\hfill \\ & =& \varphi (s_{n+1}^{*}{s}_i,C_n^i)\hfill \\ & =& \varphi (s_{n+1}^{*},\varphi (s_i,C_n^i))\hfill \\ & =& \varphi (s_{n+1}^{*},\varphi (s_j,C_n^j))\hfill \\ & =& \varphi (s_{n+1}^{*}{s}_j,C_n^j)\hfill \\ & =& \varphi (s_j^{*}{s}_{n+1},C_n^j)\hfill \\ & =& \varphi (s_j^{*},\varphi (s_{n+1},C_n^j))\hfill \\ & =& \varphi (s_j^{*},C_{n+1}^j)\hfill \end{array}$$

and

$$\begin{array}{ccc}\hfill \varphi (s_n,C_{n-1}^n)& =& \varphi (s_n,\varphi (s_{n-1}^{*},C_{n-1}^{n-2}))\hfill \\ & =& \varphi (s_n{s}_{n-1}^{*},C_{n-1}^{n-2})\hfill \\ & =& \varphi (s_{n-1}{s}_n^{*},C_{n-1}^{n-1})\hfill \\ & =& \varphi (s_{n-1},\varphi (s_n^{*},C_{n-1}^{n-1}))\hfill \\ & =& \varphi (s_{n-1},C_n^{n-1})\hfill \end{array}$$

So all users $U_1,\cdots ,U_n$ get the same key for n odd.

Secondly, we show that this also works for n even. We prove by induction that

$$\varphi (s_i^{*},C_n^i)=\varphi (s_j^{*},C_n^j)$$

for $i\ne j$, $i,j\in \{1,\cdots ,n-1\}$. And this also equals $U_n$ key, $\varphi (s_n,C_{n-1}^n)$. For $n=4$,

$$\begin{array}{ccc}\hfill \varphi (s_1^{*},\varphi (s_4,C_3^1))& =& \varphi (s_1^{*},{\delta }_4{\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*}{\mu }_4)\hfill \\ & =& {\delta }_1{\delta }_4{\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*}{\mu }_4{\mu }_1^{*}\hfill \\ & =& {\delta }_2{\delta }_4{\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*}{\mu }_4{\mu }_2^{*}\hfill \\ & =& \varphi (s_2^{*},{\delta }_4{\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*}{\mu }_4)\hfill \\ & =& \varphi (s_2^{*},\varphi (s_4,C_3^2)),\hfill \end{array}$$

$$\begin{array}{ccc}\hfill \varphi (s_1^{*},\varphi (s_4,C_3^1))& =& \varphi (s_1^{*},{\delta }_4{\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*}{\mu }_4)\hfill \\ & =& {\delta }_1{\delta }_4{\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*}{\mu }_4{\mu }_1^{*}\hfill \\ & =& {\delta }_3{\delta }_4{\delta }_2{\delta }_{1}h{\mu }_1{\mu }_2^{*}{\mu }_4{\mu }_3^{*}\hfill \\ & =& \varphi (s_3^{*},{\delta }_4{\delta }_2{\delta }_{1}h{\mu }_1{\mu }_2^{*}{\mu }_4)\hfill \\ & =& \varphi (s_3^{*},\varphi (s_4,C_3^3))\hfill \end{array}$$

using that ${\delta }_i\in K^{\alpha }{C}_m$ commute and

$${\mu }_2{\mu }_3^{*}{\mu }_4{\mu }_1^{*}={\mu }_3{\mu }_2^{*}{\mu }_4{\mu }_1^{*}={\mu }_3{\mu }_4^{*}{\mu }_2{\mu }_1^{*}={\mu }_3{\mu }_4^{*}{\mu }_1{\mu }_2^{*}={\mu }_3{\mu }_1^{*}{\mu }_4{\mu }_2^{*}={\mu }_1{\mu }_3^{*}{\mu }_4{\mu }_2^{*},$$

$${\mu }_2{\mu }_3^{*}{\mu }_4{\mu }_1^{*}={\mu }_2{\mu }_4^{*}{\mu }_1{\mu }_3^{*}={\mu }_2{\mu }_1^{*}{\mu }_4{\mu }_3^{*}={\mu }_1{\mu }_2^{*}{\mu }_4{\mu }_3^{*}.$$

In addition, $\varphi (s_4^{*},C_3^4)={\delta }_4{\delta }_3{\delta }_2{\delta }_{1}h{\mu }_1{\mu }_2^{*}{\mu }_3{\mu }_4^{*}={\delta }_3{\delta }_4{\mu }_2{\mu }_{1}h{\mu }_1{\mu }_2^{*}{\mu }_4{\mu }_3^{*}=\varphi (s_3^{*},\varphi (s_4,C_3^3))$.

Suppose now that

$$\varphi \left(s_i^{*},C_n^i\right)=\varphi \left(s_j^{*},C_n^j\right).$$

Then we have

$$\begin{array}{ccc}\hfill \varphi (s_i,C_{n+1}^i)& =& \varphi \left(s_i,\varphi (s_{n+1}^{*},C_n^i)\right)\hfill \\ & =& \varphi \left(s_i,\varphi (s_{n+1}^{*},C_n^i)\right)\hfill \\ & =& \varphi \left(s_i{s}_{n+1}^{*},C_n^i)\right)\hfill \\ & =& \varphi \left(s_{n+1}{s}_i^{*},C_n^i)\right)\hfill \\ & =& \varphi \left(s_{n+1},\varphi (s_i^{*},C_n^i)\right)\hfill \\ & =& \varphi \left(s_{n+1},\varphi (s_j^{*},C_n^j)\right)\hfill \\ & =& \varphi \left(s_{n+1}{s}_j^{*},C_n^j)\right)\hfill \\ & =& \varphi \left(s_j{s}_{n+1}^{*},C_n^j\right)\hfill \\ & =& \varphi \left(s_j,\varphi (s_{n+1}^{*},C_n^j)\right)\hfill \\ & =& \varphi (s_j,C_{n+1}^j).\hfill \end{array}$$

So the shared key $\varphi \left(s_i,\varphi (s_{n+1}^{*},C_n^i)\right)$ is the same for every $i\in \{1,\cdots ,n-1\}$, and also,

$$\begin{array}{ccc}\hfill \varphi (s_n^{*},C_{n-1}^n)& =& \varphi (s_n^{*},\varphi (s_{n-1},C_{n-1}^{n-2}))\hfill \\ & =& \varphi (s_n^{*}{s}_{n-1},C_{n-1}^{n-2})\hfill \\ & =& \varphi (s_{n-1}^{*}{s}_n,C_{n-1}^{n-1})\hfill \\ & =& \varphi (s_{n-1}^{*},\varphi (s_n,C_{n-1}^{n-1}))\hfill \\ & =& \varphi (s_{n-1}^{*},C_n^{n-1})\hfill \end{array}$$

so all users $U_1,\cdots ,U_n$ have the same shared key, and we are done. □

Note that this protocol in $K^{{\alpha }_2}{D}_{2m}$, for $n=2$ users, is described in ([3], Section 3 ) and later in ([11], Protocol 1) using the cocycles of Example 1 respectively.

For clarity, we include an example for a small number n of users $(n>2)$:

Example 2.

For a small number of users, n, the key establishment is as follows:

(i) 

For $i=1,\cdots ,n-1$, user $U_i$ sends to user $U_{i+1}$ the following messages:

• $U_1$ sends to $U_2$$\{C_1^1,C_1^2\}=\{h,{\delta }_{1}h{\mu }_1\}$.
• $U_2$ sends to $U_3$$\{C_2^1,C_2^2,C_2^3\}=\{{\delta }_{2}h{\mu }_2,{\delta }_{1}h{\mu }_1,{\delta }_2{\delta }_{1}h{\mu }_1{\mu }_2^{*}\}$.

(ii) 

Then if $n=3$, given that n is odd, user $U_3$ computes the shared key $\varphi (s_3,C_2^3)={\delta }_3{\delta }_2{\delta }_{1}h{\mu }_1{\mu }_2^{*}{\mu }_3$.

(iii) 

User $U_3$ broadcast $\{C_3^1,C_3^2\}=\{{\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*},{\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*}\}$

(iv) 

Then users $U_1$ and $U_2$ compute the shared key as follows:

• $U_1$ computes $\varphi (s_1^{*},C_4^1)={\delta }_1{\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*}{\mu }_1$.
• $U_2$ computes $\varphi (s_2^{*},C_4^2)={\delta }_2{\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*}{\mu }_2$.

These are equal to the key computed by $U_3$, as shown in Proposition 1.

If $n=4$, given that n is even, the protocol works as follows:

(i) 

Users $U_1,U_2$ send the same messages as before, and $U_3$ sends to $U_4$$\{C_3^1,C_3^2,C_3^3,C_3^4\}=\{{\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*},{\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*},{\delta }_2{\delta }_{1}h{\mu }_1{\mu }_2^{*},{\delta }_3{\delta }_2{\delta }_{1}h{\mu }_1{\mu }_2^{*}{\mu }_3\}$.

(ii) 

Then user $U_4$ computes the shared key $\varphi (s_4^{*},C_3^4)={\delta }_4{\delta }_3{\delta }_2{\delta }_{1}h{\mu }_1{\mu }_2^{*}{\mu }_3{\mu }_4^{*}$.

(iii) 

User $U_4$ broadcast $\{C_4^1,C_4^2,C_4^3\}=\{{\delta }_4{\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*}{\mu }_4,{\delta }_4{\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*}{\mu }_4,{\delta }_4{\delta }_2{\delta }_{1}h{\mu }_1{\mu }_2^{*}{\mu }_4\}$

(iv) 

Then users $U_1,\cdots ,U_3$ compute the shared key as follows:

• $U_1$ computes $\varphi (s_1^{*},C_4^1)={\delta }_1{\delta }_4{\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*}{\mu }_4{\mu }_1^{*}$.
• $U_2$ computes $\varphi (s_2^{*},C_4^2)={\delta }_2{\delta }_4{\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*}{\mu }_4{\mu }_2^{*}$.
• $U_3$ computes $\varphi (s_3^{*},C_4^3)={\delta }_3{\delta }_4{\delta }_2{\delta }_{1}h{\mu }_1{\mu }_2^{*}{\mu }_4{\mu }_3^{*}$.

All users obtain the same key, as shown in Proposition 1.

We have described the so-called Initial Key Agreement (IKA), but another important process in group communications is rekeying through the Auxiliary Key Agreement (AKA), which takes advantage of the information that was sent before to create a new key in a group when necessary, and is more computationally efficient than IKA. There exist three situations: the members of the group stay the same, a member leaves the group, or someone new joins it. It is important than the AKA happens in all these three situations, to ensure forward and backward security, as shown in [8,12,13].

In the first situation, every user $U_i$ has the information $C_n^i$ received from the user $U_n$. The rekeying process can be carried out by any of them. We call this user $U_c$. He chooses a new element $\widetilde{s_c}=(\widetilde{{\delta }_c},\widetilde{{\mu }_c})$, where $\widetilde{{\delta }_c}\in K^{\alpha }{C}_m$ and $\widetilde{{\mu }_c}\in {\Gamma }_{\alpha }\subset K^{\alpha }{C}_{m}y$. If n is odd, he changes his private key to ${\widetilde{s_c}}^{*}{s}_c$ and broadcasts the message

$$\{\varphi ({\widetilde{s_c}}^{*},C_n^1),\varphi ({\widetilde{s_c}}^{*},C_n^2),\cdots ,\varphi ({\widetilde{s_c}}^{*},C_n^{c-1}),C_n^c,\varphi ({\widetilde{s_c}}^{*},C_n^{c+1}),\cdots ,\varphi ({\widetilde{s_c}}^{*},C_n^n)\}.$$

If n is even, he changes his private key to $\widetilde{s_c}{s}_c^{*}$ and broadcasts the message

$$\{\varphi (\widetilde{s_c},C_n^1),\varphi (\widetilde{s_c},C_n^2),\cdots ,\varphi (\widetilde{s_c},C_n^{c-1}),C_n^c,\varphi (\widetilde{s_c},C_n^{c+1}),\cdots ,\varphi (\widetilde{s_c},C_n^n)\}.$$

Then every user recovers the common key using the private key $s_i$ if n is even, and $s_i^{*}$ if n is odd. A proof can be found in [3].

In the second case, when some user leaves the group, the corresponding position in the rekeying message is omitted.

In the last case, when a new user $U_{n+1}$ joins the group, if n is odd, then $U_c$ adds the element $\varphi (\widetilde{s_c},C_n^n)$ and sends the new user the following

$$\{\varphi (\widetilde{s_c},C_n^1),\varphi (\widetilde{s_c},C_n^2),\cdots ,\varphi (\widetilde{s_c},C_n^{c-1}),C_n^c,\varphi (\widetilde{s_c},C_n^{c+1}),\cdots ,\varphi (\widetilde{s_c},C_n^{n-1}),\varphi (\widetilde{s_c},C_n^n)\}.$$

If n is even, $U_c$ adds the element $\varphi ({\widetilde{s_c}}^{*},C_n^n)$ and sends to $U_{n+1}$ the following:

$$\{\varphi ({\widetilde{s_c}}^{*},C_n^1),\varphi ({\widetilde{s_c}}^{*},C_n^2),\cdots ,\varphi ({\widetilde{s_c}}^{*},C_n^{c-1}),C_n^c,\varphi ({\widetilde{s_c}}^{*},C_n^{c+1}),\cdots ,\varphi ({\widetilde{s_c}}^{*},C_n^{n-1}),\varphi ({\widetilde{s_c}}^{*},C_n^n)\}.$$

Finally, user $U_{n+1}$ proceeds to step 3 of the group key protocol and sends the other users the information to obtain the shared key using their private keys.

2.3. Security of the Group Key Management

In this section, we show that the extra information sent in the protocol for n users does not implies aditional information leakage for an attacker respect to the 2-users case. For this purpose, we define the following random variables, choosing X randomly from ${(K^{\alpha }{C}_m\times {\Gamma }_{\alpha })}^n$:

$$A_n=\left(view(n,X),y\right),fory\in Rrandomlychosen.$$

$$D_n=\left\{\genfrac{}{}{0pt}{}{\left(view(n,X),\varphi (s_n^{*}{s}_{n-1}{s}_{n-2}^{*}\cdots s_3{s}_2^{*}{s}_1,h),h)\right),ifniseven.}{\left(view(n,X),\varphi (s_n{s}_{n-1}^{*}{s}_{n-2}\cdots s_3{s}_2^{*}{s}_1,h)\right),ifnisodd.}\right.$$

where

• $view(n,X):=$ the ordered set of all $\varphi (s_{i_1}{s}_{i_2}^{*}{s}_{i_3}\cdots s_{m-2}^{*}{s}_{m-1}{s}_m^{*},h)$, for all proper subsets $\{i_1,\cdots ,i_m\}$ of $\{1,\cdots ,n\}$; $m\in \{1,\cdots ,n-1\}$.

when n is even, and

• $view(n,X):=$ the ordered set of all $\varphi (s_{i_1}{s}_{i_2}^{*}{s}_{i_3}\cdots s_{m-2}{s}_{m-1}^{*}{s}_m,h)$, for all proper subsets $\{i_1,\cdots ,i_m\}$ of $\{1,\cdots ,n\}$; $m\in \{1,\cdots ,n-1\}$.

when n is odd.

Also note that $\varphi (s_n^{*}{s}_{n-1}{s}_{n-2}^{*}\cdots s_3{s}_2^{*}{s}_1,h)$, or $\varphi (s_n{s}_{n-1}^{*}{s}_{n-2}\cdots s_3{s}_2^{*}{s}_1,h)$, is the common secret key, is case n is even or odd respectively.

Let the relation ∼ be polynomial indistinguishability, as defined in [8]. In this context, it means that no polynomial-time algorithm can distinguish between a key and a random value in $K^{\alpha }{D}_{2m}$ with probability significantly greater than $\frac{1}{2}$. We can derive the following result on ∼.

Proposition 2.

The relation ∼ is an equivalence relation.

A proof of this proposition can be found in [14]. Before we prove the main result, let us show that

Lemma 2.

We can write $view(n,\{s_1,s_2\}\cup X)$, with $X=\{s_3,\cdots ,s_n\}$ as a permutation of

$$V=(view(n-1,\left\{s_1\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}\cdots s_2,h),view(n-1,\left\{s_2\right\}\cup X),$$

$$\varphi (s_n{s}_{n-1}^{*}{s}_{n-2}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{s_2^{*}{s}_1\right\}\cup X))$$

when n is even, and as a permutation of

$$V=(view(n-1,\left\{s_1\right\}\cup X),\varphi (s_n^{*}{s}_{n-1}{s}_{n-2}^{*}\cdots s_2,h),view(n-1,\left\{s_2\right\}\cup X),$$

$$\varphi (s_n^{*}{s}_{n-1}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{s_1{s}_2^{*}\right\}\cup X))$$

when n is odd.

Proof of Lemma 2.

Now we show that both sets are equal. First, we prove that $view(n,\{s_1,s_2\}$

$\cup X)\subset V$: Let $a\in view(n,\{s_1,s_2\}\cup X)$:

• If n is even:

  (i)

  If a contains $s_2^{*}{s}_1(=s_1^{*}{s}_2)$, then it belongs to $view(n-1,\left\{s_2^{*}{s}_1\right\}\cup X)\subset V$.

  (ii)

  If a does not contain $s_1$ (or $s_1^{*})$,

  -

  but it contains all the remaining elements, $s_2^{(*)},\cdots ,s_n^{(*)}$, then it belongs to $\varphi (s_n{s}_{n-1}^{*}\cdots s_3^{*}{s}_2,h)\subset V$.

  -

  and if it does not contain all the remaining elements, then it belongs to $view(n-1,\left\{s_2\right\}\cup X)\subset V$.

  (iii)

  If a does not contain $s_2$ (or $s_2^{*})$,

  -

  but it contains all the remaining elements, $s_1^{(*)},s_3^{(*)},\cdots ,s_n^{(*)}$, then it belongs to $\varphi (s_n{s}_{n-1}^{*}\cdots s_3^{*}{s}_1,h)\subset V$.

  -

  and if it does not contain all the remaining elements, then it belongs to $view(n-1,\left\{s_1\right\}\cup X)\subset V$.

  (iv)

  Finally, if a does not contain $s_1$ neither $s_2$, it belongs to any of the following $view(n-1,\left\{s_1\right\}\cup X),view(n-1,\left\{s_2\right\}\cup X),view(n-1,\left\{s_1{s}_2^{*}\right\}\subset V$.

• If n is odd:

  (i)

  If a contains $s_2^{*}{s}_1(=s_1^{*}{s}_2)$, then it belongs to $view(n-1,\left\{s_2^{*}{s}_1\right\}\cup X)\subset V$.

  (ii)

  If a does not contain $s_1$ (or $s_1^{*})$,

  -

  but it contains all the remaining elements, $s_2^{(*)},\cdots ,s_n^{(*)}$, then it belongs to $\varphi (s_n^{*}{s}_{n-1}\cdots s_3^{*}{s}_2,h)\subset V$.

  -

  and if it does not contain all the remaining elements, then it belongs to $view(n-1,\left\{s_2\right\}\cup X)\subset V$.

  (iii)

  If a does not contain $s_2$ (or $s_2^{*})$,

  -

  but it contains all the remaining elements, $s_1^{(*)},s_3^{(*)},\cdots ,s_n^{(*)}$, then it belongs to $\varphi (s_n^{*}{s}_{n-1}\cdots s_3^{*}{s}_1,h)\subset V$.

  -

  and if it does not contain all the remaining elements, then it belongs to $view(n-1,\left\{s_1\right\}\cup X)\subset V$.

  (iv)

  Finally, if a does not contain $s_1$ neither $s_2$, it belongs to any of the following $view(n-1,\left\{s_1\right\}\cup X),view(n-1,\left\{s_2\right\}\cup X),view(n-1,\left\{s_1{s}_2^{*}\right\}\subset V$.

The reverse inclusion, $V\subset view(n,\{s_1,s_2\})$ is true since all the elements in V belong to $view(n,\{s_1,s_2\}\cup X)$ by definition. □

In ([3], Section 3) it is first described a decisional problem related to the key agreement protocol for $n=2$. Let us recall from ([11], Definition 4.7) a formal definition of this decisional problem.

For a given adversary $\mathcal{A}$ we define the following experiment:

• The challenger computes

  (i)

  $({\delta }_1,{\mu }_1)\stackrel{R}{\leftarrow }{K}^{\alpha }{C}_m\times {\Gamma }_{\alpha }$;

  (ii)

  $({\delta }_2,{\mu }_2)\stackrel{R}{\leftarrow }{K}^{\alpha }{C}_m\times {\Gamma }_{\alpha }$;

  (iii)

  $({\delta }_3,{\mu }_3)\stackrel{R}{\leftarrow }{K}^{\alpha }{C}_m\times {\Gamma }_{\alpha }$;

  (iv)

  ${\mathrm{pub}}_1\leftarrow {\delta }_{1}h{\mu }_1;{\mathrm{pub}}_2\leftarrow {\delta }_{2}h{\mu }_2$;

  (v)

  $r_0\leftarrow {\delta }_2{\mathrm{pub}}_1{\mu }_2^{*};r_1={\delta }_{3}h{\mu }_3$;

  and gives the triple (${\mathrm{pub}}_1,{\mathrm{pub}}_2,k_b$) to the adversary.

• The adversary outputs a bit $\overline{b}\in \{0,1\}$.

If $W_b$ is the event that $\mathcal{A}$ outputs 1 in the experiment, we define $\mathcal{A}$’s advantage in solving the Decisional Dihedral Product Problem for $K^{\alpha }{D}_{2m}$ as

$$\mathrm{DDPadv}[\mathcal{A},K^{\alpha }{D}_{2m}]=|\mathrm{Pr}\left[W_0\right]-\mathrm{Pr}\left[W_1\right]|.$$

We say then that the Decisional Dihedral Product Problem is hard or that the Decisional Dihedral Product Assumption holds for $K^{\alpha }{D}_{2m}$ if for all efficient adversaries $\mathcal{A}$, the quantity $\mathrm{DDPadv}[\mathcal{A},K^{\alpha }{D}_{2m}]$ is negligible.

Let us finally prove, following the idea of [8], that if the Decisional Dihedral Product Assumption holds, then the Group Key Management verifies that an adversary cannot distinguish the shared group key from an arbitrary element. To do so we prove the following:

Theorem 1.

For any $n>2$, $A_2\sim D_2$ implies that $A_n\sim D_n$.

Proof of Theorem 1.

We show this is true by induction on n. Assume that $A_2\sim D_2$ and $A_i\sim D_i$, $i\in \{3,\cdots ,n-1\}$. Thus, we have to show that $A_n\sim D_n$. We define the random variables $B_n,C_n$, and show that $A_n\sim B_n\sim C_n\sim D_n$, and since ∼ is a equivalence relation, by transitivity, this implies that $A_n\sim D_n$.

We split the proof in two cases:

(a)

Assume n is even:

We redefine $A_n,D_n$ using Lemma 2, and define $B_n,C_n$ as follows:

• $A_n=(view(n-1,\left\{s_1\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}\cdots s_2,h),view(n-1,\left\{s_2\right\}\cup X),$
  $\varphi (s_n{s}_{n-1}^{*}{s}_{n-2}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{s_2^{*}{s}_1\right\}\cup X),y)$
• $B_n=(view(n-1,\left\{s_1\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}\cdots s_2,h),view(n-1,\left\{s_2\right\}\cup X),$
  $\varphi (s_n{s}_{n-1}^{*}{s}_{n-2}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{c\right\}\cup X),y)$
• $C_n=(view(n-1,\left\{s_1\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}\cdots s_2,h),view(n-1,\left\{s_2\right\}\cup X),$
  $\varphi (s_n{s}_{n-1}^{*}{s}_{n-2}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{c\right\}\cup X),\varphi (s_n^{*}{s}_{n-1}\cdots s_4^{*}{s}_{3}c,h))$
• $D_n=(view(n-1,\left\{s_1\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}\cdots s_2,h),view(n-1,\left\{s_2\right\}\cup X),$
  $\varphi (s_n{s}_{n-1}^{*}{s}_{n-2}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{s_2^{*}{s}_1\right\}\cup X),\varphi (s_n^{*}{s}_{n-1}\cdots s_4^{*}{s}_3{s}_2^{*}{s}_1,h))$

choosing $s_1,s_2\in R_1\times A_2$, $c\in R_1\times A_1$; and $X\in {(R_1\times A_2)}^{n-2},y\in R_{1}h{A}_1$ randomly. Note that only the last two components vary.

$A_2\sim D_2⟹A_n\sim B_n$

Suppose, for the sake of contradiction, that an adversary Eve distinguishes $A_n$ and $B_n$. We produce an instance of $A_n\nsim B_n$ for Eve

$$\begin{array}{ccc}\hfill A_n& =& (view(n-1,\left\{s_1\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}\cdots s_2,h),view(n-1,\left\{s_2\right\}\cup X),\hfill \\ & & \varphi (s_n{s}_{n-1}^{*}{s}_{n-2}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{s_2^{*}{s}_1\right\}\cup X),y)\hfill \\ & =& ({\delta }_{\mathit{1}}\mathit{h}{\mu }_{\mathit{1}},\cdots ,{\delta }_n{\delta }_{n-1}\cdots {\delta }_4{\delta }_{3}h{\mu }_3{\mu }_4^{*}\cdots {\mu }_{n-1}{\mu }_n^{*},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\delta }_{\mathit{2}}\mathit{h}{\mu }_{\mathit{2}},\cdots ,{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*}\cdots {\mu }_{n-2}^{*}{\mu }_{n-1},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_1{\mu }_2^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\delta }_{\mathit{2}}{\delta }_{\mathit{1}}\mathit{h}{\mu }_{\mathit{1}}{\mu }_{\mathit{2}}^{*},\cdots ,{\delta }_{n-1}{\delta }_{n-2}\cdots {\delta }_3\left({\delta }_2{\delta }_1\right)h\left({\mu }_1{\mu }_2^{*}\right){\mu }_3\cdots {\mu }_{n-2}^{*}{\mu }_{n-1},y)\hfill \\ \\ \hfill B_n& =& view(n-1,\left\{s_1\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}\cdots s_2,h),view(n-1,\left\{s_2\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}{s}_{n-2}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{c\right\}\cup X),y\hfill \\ & & \varphi (s_n^{*}{s}_{n-1}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{c\right\}\cup X),y)\hfill \\ & =& ({\mathit{\delta }}_{\mathit{1}}\mathit{h}{\mathit{\mu }}_{\mathit{1}},\cdots ,{\delta }_n{\delta }_{n-1}\cdots {\delta }_4{\delta }_{3}h{\mu }_3{\mu }_4^{*}\cdots {\mu }_{n-1}{\mu }_n^{*},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\mathit{\delta }}_{\mathit{2}}\mathit{h}{\mathit{\mu }}_{\mathit{2}},\cdots ,{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*}\cdots {\mu }_{n-2}^{*}{\mu }_{n-1},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_1{\mu }_2^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\mathit{c}}_{\mathit{1}}{\mathit{hc}}_{\mathit{2}},\cdots ,{\delta }_{n-1}{\delta }_{n-2}\cdots {\delta }_3\left(c_1\right)h\left(c_2\right){\mu }_3\dots {\mu }_{n-2}{\mu }_{n-1}^{*},y)\hfill \end{array}$$

if Eve distinguishes $A_n$ and $B_n$, then in particular, she distinguishes ${\delta }_2{\delta }_{1}h{\mu }_1{\mu }_2^{*}$ from $c_{1}h{c}_2$ (given ${\delta }_{1}h{\mu }_1$ and ${\delta }_{2}h{\mu }_2)$, which means that she distinguishes

$$\begin{array}{ccc}\hfill A_2& =& \left(view(2,\{s_1,s_2\}),y\right)\hfill \\ & =& \left({\delta }_{1}h{\mu }_1,{\delta }_{2}h{\mu }_2,y\right)\hfill \\ \\ \hfill D_2& =& \left(view(2,\{s_1,s_2\}),\varphi (s_2^{*}{s}_1,h)\right)\hfill \\ & =& \left({\delta }_{1}h{\mu }_1,{\delta }_{2}h{\mu }_2,{\delta }_2{\delta }_{1}h{\mu }_1{\mu }_2^{*}\right)\hfill \end{array}$$

which contradicts our hypothesis.

$A_{n-2}\sim D_{n-2}⟹B_n\sim C_n$

Suppose towards the sake of contradiction that an adversary Eve distinguishes $B_n$ and $C_n$. We produce and instance of $B_n\nsim C_n$ for Eve

$$\begin{array}{ccc}\hfill B_n& =& (view(n-1,\left\{s_1\right\}\cup X),\varphi (s_n^{*}{s}_{n-1}\cdots s_3^{*}{s}_2,h),\hfill \\ & & view(n-1,\left\{s_2\right\}\cup X),\varphi (s_n^{*}{s}_{n-1}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{c\right\}\cup X),y)\hfill \\ & =& ({\delta }_{1}h{\mu }_1,\cdots ,{\delta }_n{\delta }_{n-1}\cdots {\delta }_4{\delta }_{3}h{\mu }_3{\mu }_4^{*}\cdots {\mu }_{n-1}{\mu }_n^{*},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\delta }_{2}h{\mu }_2,\cdots ,{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*}\cdots {\mu }_{n-2}^{*}{\mu }_{n-1},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_1{\mu }_2^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\mathit{c}}_{\mathit{1}}{\mathit{hc}}_{\mathit{2}},\cdots ,{\delta }_{\mathit{n}-\mathit{1}}\cdots {\delta }_{\mathit{5}}{\delta }_{\mathit{4}}\left({\delta }_{\mathit{3}}{\mathit{c}}_{\mathit{1}}\right)\mathit{h}\left({\mathit{c}}_{\mathit{2}}{\mu }_{\mathit{3}}\right){\mu }_{\mathit{4}}^{*}{\mu }_{\mathit{5}}\dots {\mu }_{\mathit{n}-\mathit{2}}{\mu }_{\mathit{n}-\mathit{1}}^{*},\mathit{y})\hfill \\ \\ \hfill C_n& =& (view(n-1,\left\{s_1\right\}\cup X),\varphi (s_n^{*}{s}_{n-1}\cdots s_3^{*}{s}_2,h),view(n-1,\left\{s_2\right\}\cup X),\hfill \\ & & \varphi (s_n{s}_{n-1}^{*}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{c\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}\cdots s_5{s}_4^{*}{s}_{3}c,h))\hfill \\ & =& ({\delta }_{1}h{\mu }_1,\cdots ,{\delta }_n{\delta }_{n-1}\cdots {\delta }_4{\delta }_{3}h{\mu }_3{\mu }_4^{*}\cdots {\mu }_{n-1}{\mu }_n^{*},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\delta }_{2}h{\mu }_2,\cdots ,{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*}\cdots {\mu }_{n-2}^{*}{\mu }_{n-1},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_1{\mu }_2^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\mathit{c}}_{\mathit{1}}{\mathit{hc}}_{\mathit{2}},\cdots ,{\delta }_{\mathit{n}-\mathit{1}}\cdots {\delta }_{\mathit{5}}{\delta }_{\mathit{4}}\left({\delta }_{\mathit{3}}{\mathit{c}}_{\mathit{1}}\right)\mathit{h}\left({\mathit{c}}_{\mathit{2}}{\mu }_{\mathit{3}}\right){\mu }_{\mathit{4}}^{*}{\mu }_{\mathit{5}}\cdots {\mu }_{\mathit{n}-\mathit{2}}{\mu }_{\mathit{n}-\mathit{1}}^{*},{\delta }_{\mathit{n}}\cdots {\delta }_{\mathit{4}}\left({\delta }_{\mathit{3}}{\mathit{c}}_{\mathit{1}}\right)\mathit{h}\left({\mathit{c}}_{\mathit{2}}{\mu }_{\mathit{3}}\right){\mu }_{\mathit{4}}^{*}\hfill \\ & & {\mu }_{\mathit{5}}\cdots {\mu }_{\mathit{n}})\hfill \end{array}$$

if Eve distinguishes $B_n$ and $C_n$ in polynomial time, in particular, she distinguishes y and $\varphi (s_n^{*}{s}_{n-1}\cdots s_4^{*}\left(s_{3}c\right),h)$ (given $view(n-1,\{c\}\cup X))$. Let

$$\left((view(n-2,\{c{s}_3,s_4,s_5,\cdots ,s_{n-1},s_n\}),y\right)$$

be an instance of $A_{n-2},D_{n-2}$:

$$\begin{array}{ccc}\hfill A_{n-2}& =& \left((view(n-2,\{s_{3}c,s_4,s_5,\cdots ,s_{n-1},s_n\}),y\right)\hfill \\ & =& (\left({\delta }_3{c}_1\right)h\left(c_2{\mu }_3\right),{\delta }_{4}h{\mu }_4,\cdots ,{\delta }_{n}h{\mu }_n,{\delta }_4\left({\delta }_3{c}_1\right)h\left(c_2{\mu }_3\right){\mu }_4^{*}\cdots ,{\delta }_n\left({\delta }_3{c}_1\right)h\left(c_2{\mu }_3\right){\mu }_n^{*},\hfill \\ & & {\delta }_5{\delta }_4\left({\delta }_3{c}_1\right)h\left(c_2{\mu }_3\right){\mu }_4^{*}{\mu }_5,\cdots ,{\delta }_n{\delta }_{n-1}\cdots {\delta }_4{\delta }_{3}h{\mu }_3{\mu }_4^{*}\cdots {\mu }_{n-1}{\mu }_n,y)\hfill \\ \\ \hfill D_{n-2}& =& \left(view(n-2,\{s_{3}c,s_4,s_5,\cdots ,s_{n-1},s_n\}),\varphi (s_n^{*}{s}_{n-1}\cdots s_4^{*}\left(s_{3}c\right),h)\right)\hfill \\ & =& (\left({\delta }_3{c}_1\right)h\left(c_2{\mu }_3\right),{\delta }_{4}h{\mu }_4,\cdots ,{\delta }_{n}h{\mu }_n,{\delta }_4\left({\delta }_3{c}_1\right)h\left(c_2{\mu }_3\right){\mu }_4^{*}\cdots ,{\delta }_n\left({\delta }_3{c}_1\right)h\left(c_2{\mu }_3\right){\mu }_n^{*},\hfill \\ & & {\delta }_5{\delta }_4\left({\delta }_3{c}_1\right)h\left(c_2{\mu }_3\right){\mu }_4^{*}{\mu }_5,\cdots ,{\delta }_n{\delta }_{n-1}\cdots {\delta }_5{\delta }_{4}h{\mu }_4{\mu }_5^{*}\cdots {\mu }_{n-1}{\mu }_n,{\delta }_n{\delta }_{n-1}\cdots {\delta }_4\left({\delta }_3{c}_1\right)\hfill \\ & & h\left(c_2{\mu }_3\right){\mu }_4^{*}\cdots {\mu }_{n-1}{\mu }_n)\hfill \end{array}$$

since Eve can distinguish y and $\varphi (s_n^{*}{s}_{n-1}\cdots s_4^{*}\left(s_{3}c\right),h)$ given $view(n-1,\{c\}\cup X)$, then in particular she distinguishes y and $\varphi (s_n^{*}{s}_{n-1}\cdots s_4^{*}\left(s_{3}c\right),h)$ given $view(n-2,\{s_{3}c,s_4,s_5,\cdots ,s_{n-1},s_n\})\subset view(n-1,\left\{c\right\}\cup X)$, and this means $A_{n-2}\nsim D_{n-2}$, but this contradicts our hypothesis.

$A_2\sim D_2⟹C_n\sim D_n$

Suppose, for the sake of contradiction, that an adversary Eve distinguishes $C_n$ and $D_n$. We produce and instance of $C_n\nsim D_n$ for Eve

$$\begin{array}{ccc}\hfill C_n& =& (view(n-1,\left\{s_1\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}\cdots s_2,h),view(n-1,\left\{s_2\right\}\cup X),\hfill \\ & & \varphi (s_n{s}_{n-1}^{*}{s}_{n-2}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{c\right\}\cup X),\varphi (s_n^{*}{s}_{n-1}\cdots s_4^{*}{s}_{3}c,h))\hfill \\ & =& ({\delta }_{1}h{\mu }_1,\cdots ,{\delta }_n{\delta }_{n-1}\cdots {\delta }_4{\delta }_{3}h{\mu }_3{\mu }_4^{*}\cdots {\mu }_{n-1}{\mu }_n^{*},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\delta }_{2}h{\mu }_2,\cdots ,{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*}\cdots {\mu }_{n-2}^{*}{\mu }_{n-1},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_1{\mu }_2^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\mathit{c}}_{\mathit{1}}{\mathit{hc}}_{\mathit{2}},\cdots ,{\delta }_{n-1}{\delta }_{n-2}\cdots {\delta }_3{c}_{1}h{c}_2{\mu }_3\cdots {\mu }_{n-2}^{*}{\mu }_{n-1},{\delta }_n{\delta }_{n-1}\cdots {\delta }_4{\delta }_3{c}_{1}h{c}_2{\mu }_3{\mu }_4^{*}\cdots {\mu }_{n-1}{\mu }_n)\hfill \\ \\ \hfill D_n& =& (view(n-1,\left\{s_1\right\}\cup X),K(n-1,\left\{s_1\right\}\cup X),view(n-1,\left\{s_2\right\}\cup X),\hfill \\ & & K(n-1,\left\{s_2\right\}\cup X),view(n-1,\left\{s_2^{*}{s}_1\right\}\cup X),\varphi (s_n^{*}{s}_{n-1}\cdots s_4^{*}{s}_3{s}_2^{*}{s}_1,h))\hfill \\ & =& ({\delta }_{1}h{\mu }_1,\cdots ,{\delta }_n{\delta }_{n-1}\cdots {\delta }_4{\delta }_{3}h{\mu }_3{\mu }_4^{*}\cdots {\mu }_{n-1}{\mu }_n^{*},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\delta }_{2}h{\mu }_2,\cdots ,{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*}\cdots {\mu }_{n-2}^{*}{\mu }_{n-1},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_1{\mu }_2^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\delta }_{\mathit{2}}{\delta }_{\mathit{1}}\mathit{h}{\mu }_{\mathit{1}}{\mu }_{\mathit{2}}^{*},\cdots ,{\delta }_{n-1}{\delta }_{n-2}\cdots {\delta }_3\left({\delta }_2{\delta }_1\right)h\left({\mu }_1{\mu }_2^{*}\right){\mu }_3\cdots {\mu }_{n-2}^{*}{\mu }_{n-1},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3\left({\delta }_2{\delta }_1\right)\hfill \\ & & h\left({\mu }_1{\mu }_2^{*}\right){\mu }_3\cdots {\mu }_{n-1}{\mu }_n^{*})\hfill \end{array}$$

as in the first case, if Eve distinguishes $A_n$ and $B_n$, then in particular, she distinguishes ${\delta }_2{\delta }_{1}h{\mu }_1{\mu }_2^{*}$ from $c_{1}h{c}_2$ (given ${\delta }_{1}h{\mu }_1$ and ${\delta }_{2}h{\mu }_2)$, which means that she distinguishes

$$\begin{array}{ccc}\hfill A_2& =& \left(view(2,\{s_1,s_2\}),y\right)\hfill \\ & =& \left({\delta }_{1}h{\mu }_1,{\delta }_{2}h{\mu }_2,y\right)\hfill \\ \\ \hfill D_2& =& \left(view(2,\{s_1,s_2\}),\varphi (s_2^{*}{s}_1,h)\right)\hfill \\ & =& \left({\delta }_{1}h{\mu }_1,{\delta }_{2}h{\mu }_2,{\delta }_2{\delta }_{1}h{\mu }_1{\mu }_2^{*}\right)\hfill \end{array}$$

which contradicts our hypothesis.

(b)

Similarly, if n is odd:

We redefine $A_n,D_n$ using Lemma 2, and define $B_n,C_n$ as follows:

• $A_n=(view(n-1,\left\{s_1\right\}\cup X),\varphi (s_n^{*}{s}_{n-1}\cdots s_3^{*}{s}_2,h),view(n-1,\left\{s_2\right\}\cup X),$
  $\varphi (s_n^{*}{s}_{n-1}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{s_2^{*}{s}_1\right\}\cup X),y)$
• $B_n=(view(n-1,\left\{s_1\right\}\cup X),\varphi (s_n^{*}{s}_{n-1}\cdots s_2,h),view(n-1,\left\{s_2\right\}\cup X),$
  $\varphi (s_n^{*}{s}_{n-1}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{c\right\}\cup X),y)$
• $C_n=(view(n-1,\left\{s_1\right\}\cup X),\varphi (s_n^{*}{s}_{n-1}\cdots s_2,h),view(n-1,\left\{s_2\right\}\cup X),$
  $\varphi (s_n^{*}{s}_{n-1}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{c\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}\cdots s_5{s}_4^{*}{s}_{3}c,h))$
• $D_n=(view(n-1,\left\{s_1\right\}\cup X),\varphi (s_n^{*}{s}_{n-1}\cdots s_2,h),view(n-1,\left\{s_2\right\}\cup X),$
  $\varphi (s_n^{*}{s}_{n-1}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{s_2^{*}{s}_1\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}\cdots s_5{s}_4^{*}{s}_3{s}_2^{*}{s}_1,h))$

choosing $s_1,s_2\in R_1\times A_2$, $c\in R_1\times A_1$; and $X\in {(R_1\times A_2)}^{n-2},y\in R_{1}h{A}_2$ randomly.

$A_2\sim D_2⟹A_n\sim B_n$.

Suppose towards the sake of contradiction that an adversary Eve distinguishes $A_n$ and $B_n$. We produce an instance of $A_n\nsim B_n$ for Eve

$$\begin{array}{ccc}\hfill A_n& =& (view(n-1,\left\{s_1\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}\cdots s_2,h),view(n-1,\left\{s_2\right\}\cup X),\hfill \\ & & \varphi (s_n{s}_{n-1}^{*}{s}_{n-2}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{s_2^{*}{s}_1\right\}\cup X),y)\hfill \\ & =& ({\delta }_{\mathit{1}}\mathit{h}{\mu }_{\mathit{1}},\cdots ,{\delta }_n{\delta }_{n-1}\cdots {\delta }_4{\delta }_{3}h{\mu }_3{\mu }_4^{*}\cdots {\mu }_{n-1}{\mu }_n^{*},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\delta }_{\mathit{2}}\mathit{h}{\mu }_{\mathit{2}},\cdots ,{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*}\cdots {\mu }_{n-2}^{*}{\mu }_{n-1},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_1{\mu }_2^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\delta }_{\mathit{2}}{\delta }_{\mathit{1}}\mathit{h}{\mu }_{\mathit{1}}{\mu }_{\mathit{2}}^{*},\cdots ,{\delta }_{n-1}{\delta }_{n-2}\cdots {\delta }_3\left({\delta }_2{\delta }_1\right)h\left({\mu }_1{\mu }_2^{*}\right){\mu }_3\cdots {\mu }_{n-2}^{*}{\mu }_{n-1},y)\hfill \\ \\ \hfill B_n& =& view(n-1,\left\{s_1\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}\cdots s_2,h),view(n-1,\left\{s_2\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}{s}_{n-2}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{c\right\}\cup X),y\hfill \\ & & \varphi (s_n^{*}{s}_{n-1}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{c\right\}\cup X),y)\hfill \\ & =& ({\mathit{\delta }}_{\mathit{1}}\mathit{h}{\mathit{\mu }}_{\mathit{1}},\cdots ,{\delta }_n{\delta }_{n-1}\cdots {\delta }_4{\delta }_{3}h{\mu }_3{\mu }_4^{*}\cdots {\mu }_{n-1}{\mu }_n^{*},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\mathit{\delta }}_{\mathit{2}}\mathit{h}{\mathit{\mu }}_{\mathit{2}},\cdots ,{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*}\cdots {\mu }_{n-2}^{*}{\mu }_{n-1},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_1{\mu }_2^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\mathit{c}}_{\mathit{1}}{\mathit{hc}}_{\mathit{2}},\cdots ,{\delta }_{n-1}{\delta }_{n-2}\cdots {\delta }_3\left(c_1\right)h\left(c_2\right){\mu }_3\dots {\mu }_{n-2}{\mu }_{n-1}^{*},y)\hfill \end{array}$$

if Eve distinguishes $A_n$ and $B_n$, then in particular, she distinguishes ${\delta }_2{\delta }_{1}h{\mu }_1{\mu }_2^{*}$ from $c_{1}h{c}_2$ (given ${\delta }_{1}h{\mu }_1$ and ${\delta }_{2}h{\mu }_2)$, which means that she distinguishes

$$\begin{array}{ccc}\hfill A_2& =& \left(view(2,\{s_1,s_2\}),y\right)\hfill \\ & =& \left({\delta }_{1}h{\mu }_1,{\delta }_{2}h{\mu }_2,y\right)\hfill \\ \\ \hfill D_2& =& \left(view(2,\{s_1,s_2\}),\varphi (s_2^{*}{s}_1,h)\right)\hfill \\ & =& \left({\delta }_{1}h{\mu }_1,{\delta }_{2}h{\mu }_2,{\delta }_2{\delta }_{1}h{\mu }_1{\mu }_2^{*}\right)\hfill \end{array}$$

which contradicts our hypothesis.

$A_{n-2}\sim D_{n-2}⟹B_n\sim C_n$.

Suppose, for the sake of contradiction, that an adversary Eve distinguishes $B_n$ and $C_n$. We produce and instance of $B_n\nsim C_n$ for Eve

$$\begin{array}{ccc}\hfill B_n& =& (view(n-1,\left\{s_1\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}\cdots s_2,h),view(n-1,\left\{s_2\right\}\cup X),\hfill \\ & & \varphi (s_n{s}_{n-1}^{*}{s}_{n-2}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{c\right\}\cup X),y)\hfill \\ & =& ({\delta }_{1}h{\mu }_1,\cdots ,{\delta }_n{\delta }_{n-1}\cdots {\delta }_4{\delta }_{3}h{\mu }_3{\mu }_4^{*}\cdots {\mu }_{n-1}{\mu }_n^{*},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\delta }_{2}h{\mu }_2,\cdots ,{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*}\cdots {\mu }_{n-2}^{*}{\mu }_{n-1},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_1{\mu }_2^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\mathit{c}}_{\mathit{1}}{\mathit{hc}}_{\mathit{2}},\cdots ,{\delta }_{\mathit{n}-\mathit{1}}\cdots {\delta }_{\mathit{5}}{\delta }_{\mathit{4}}\left({\delta }_{\mathit{3}}{\mathit{c}}_{\mathit{1}}\right)\mathit{h}\left({\mathit{c}}_{\mathit{2}}{\mu }_{\mathit{3}}\right){\mu }_{\mathit{4}}^{*}{\mu }_{\mathit{5}}\cdots {\mu }_{\mathit{n}-\mathit{2}}^{*}{\mu }_{\mathit{n}-\mathit{1}},\mathit{y})\hfill \\ \\ \hfill C_n& =& (view(n-1,\left\{s_1\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}\cdots s_2,h),view(n-1,\left\{s_2\right\}\cup X),\hfill \\ & & \varphi (s_n{s}_{n-1}^{*}{s}_{n-2}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{c\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}\cdots s_4^{*}{s}_{3}c,h))\hfill \\ & =& ({\delta }_{1}h{\mu }_1,\cdots ,{\delta }_n{\delta }_{n-1}\cdots {\delta }_4{\delta }_{3}h{\mu }_3{\mu }_4^{*}\cdots {\mu }_{n-1}{\mu }_n^{*},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\delta }_{2}h{\mu }_2,\cdots ,{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*}\cdots {\mu }_{n-2}^{*}{\mu }_{n-1},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_1{\mu }_2^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\mathit{c}}_{\mathit{1}}{\mathit{hc}}_{\mathit{2}},\cdots ,{\delta }_{\mathit{n}-\mathit{1}}\cdots {\delta }_{\mathit{5}}{\delta }_{\mathit{4}}\left({\delta }_{\mathit{3}}{\mathit{c}}_{\mathit{1}}\right)\mathit{h}\left({\mathit{c}}_{\mathit{2}}{\mu }_{\mathit{3}}\right){\mu }_{\mathit{4}}^{*}{\mu }_{\mathit{5}}\cdots {\mu }_{\mathit{n}-\mathit{2}}^{*}{\mu }_{\mathit{n}-\mathit{1}},{\delta }_{\mathit{n}}\cdots {\delta }_{\mathit{4}}\left({\delta }_{\mathit{3}}{\mathit{c}}_{\mathit{1}}\right)\hfill \\ & & \mathit{h}\left({\mathit{c}}_{\mathit{2}}{\mu }_{\mathit{3}}\right){\mu }_{\mathit{4}}^{*}{\mu }_{\mathit{5}}\cdots {\mu }_{\mathit{n}}^{*})\hfill \end{array}$$

if Eve distinguishes $B_n$ and $C_n$ in polynomial time, in particular, she distinguishes y and $\varphi (s_n{s}_{n-1}^{*}\cdots s_5{s}_4^{*}\left(s_{3}c\right),h)$ (given $view(n-1,\{c\}\cup X))$. Let

$$\left((view(n-2,\{c{s}_3,s_4,s_5,\cdots ,s_{n-1},s_n\}),y\right)$$

be an instance of $A_{n-2},D_{n-2}$:

$$\begin{array}{ccc}\hfill A_{n-2}& =& \left((view(n-2,\{s_{3}c,s_4,s_5,\cdots ,s_{n-1},s_n\}),y\right)\hfill \\ & =& (\left({\delta }_3{c}_1\right)h\left(c_2{\mu }_3\right),{\delta }_{4}h{\mu }_4,\cdots ,{\delta }_{n}h{\mu }_n,{\delta }_4\left({\delta }_3{c}_1\right)h\left(c_2{\mu }_3\right){\mu }_4^{*}\cdots ,{\delta }_n\left({\delta }_3{c}_1\right)h\left(c_2{\mu }_3\right){\mu }_n^{*},\hfill \\ & & {\delta }_5{\delta }_4\left({\delta }_3{c}_1\right)h\left(c_2{\mu }_3\right){\mu }_4^{*}{\mu }_5,\cdots ,{\delta }_n{\delta }_{n-1}\cdots {\delta }_4{\delta }_{3}h{\mu }_3{\mu }_4^{*}\cdots {\mu }_{n-1}^{*}{\mu }_n,y)\hfill \\ \\ \hfill D_{n-2}& =& \left(view(n-2,\{s_{3}c,s_4,s_5,\cdots ,s_{n-1},s_n\}),\varphi (s_n{s}_{n-1}^{*}\cdots s_5{s}_4^{*}\left(s_{3}c\right),h)\right)\hfill \\ & =& (\left({\delta }_3{c}_1\right)h\left(c_2{\mu }_3\right),{\delta }_{4}h{\mu }_4,\cdots ,{\delta }_{n}h{\mu }_n,{\delta }_4\left({\delta }_3{c}_1\right)h\left(c_2{\mu }_3\right){\mu }_4^{*}\cdots ,{\delta }_n\left({\delta }_3{c}_1\right)h\left(c_2{\mu }_3\right){\mu }_n^{*},\hfill \\ & & {\delta }_5{\delta }_4\left({\delta }_3{c}_1\right)h\left(c_2{\mu }_3\right){\mu }_4^{*}{\mu }_5,\cdots ,{\delta }_n{\delta }_{n-1}\cdots {\delta }_5{\delta }_{4}h{\mu }_4{\mu }_5^{*}\cdots {\mu }_{n-1}^{*}{\mu }_n,{\delta }_n{\delta }_{n-1}\cdots {\delta }_4\left({\delta }_3{c}_1\right)\hfill \\ & & h\left(c_2{\mu }_3\right){\mu }_4^{*}\cdots {\mu }_{n-1}^{*}{\mu }_n)\hfill \end{array}$$

since Eve can distinguish y and $\varphi (s_n{s}_{n-1}^{*}\cdots s_5{s}_4^{*}\left(s_{3}c\right),h)$ given $view(n-1,\{c\}\cup X)$, then in particular she distinguishes y and $\varphi (s_n^{*}{s}_{n-1}\cdots s_4^{*}\left(s_{3}c\right),h)$ given $view(n-2,\{s_{3}c,s_4,s_5,\cdots ,s_{n-1},s_n\})\subset view(n-1,\left\{c\right\}\cup X)$, and this means $A_{n-2}\nsim D_{n-2}$, but this contradicts our hypothesis.

$A_2\sim D_2⟹C_n\sim D_n$.

Suppose towards the sake of contradiction that an adversary Eve distinguishes $C_n$ and $D_n$. We produce and instance of $C_n\nsim D_n$ for Eve

$$\begin{array}{ccc}\hfill C_n& =& (view(n-1,\left\{s_1\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}\cdots s_2,h),view(n-1,\left\{s_2\right\}\cup X),\hfill \\ & & \varphi (s_n{s}_{n-1}^{*}{s}_{n-2}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{c\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}\cdots s_4^{*}{s}_{3}c,h))\hfill \\ & =& ({\delta }_{1}h{\mu }_1,\cdots ,{\delta }_n{\delta }_{n-1}\cdots {\delta }_4{\delta }_{3}h{\mu }_3{\mu }_4^{*}\cdots {\mu }_{n-1}{\mu }_n^{*},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\delta }_{2}h{\mu }_2,\cdots ,{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*}\cdots {\mu }_{n-2}^{*}{\mu }_{n-1},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_1{\mu }_2^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\mathit{c}}_{\mathit{1}}{\mathit{hc}}_{\mathit{2}},\cdots ,{\delta }_{n-1}{\delta }_{n-2}\cdots {\delta }_3{c}_{1}h{c}_2{\mu }_3\cdots {\mu }_{n-2}^{*}{\mu }_{n-1},{\delta }_n{\delta }_{n-1}\cdots {\delta }_4{\delta }_3{c}_{1}h{c}_2{\mu }_3{\mu }_4^{*}\cdots {\mu }_{n-1}{\mu }_n)\hfill \\ \\ \hfill D_n& =& (view(n-1,\left\{s_1\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}\cdots s_2,h),view(n-1,\left\{s_2\right\}\cup X),\hfill \\ & & \varphi (s_n{s}_{n-1}^{*}{s}_{n-2}\cdots s_3^{*}{s}_1,h),view(n-1,\left\{s_2^{*}{s}_1\right\}\cup X),\varphi (s_n{s}_{n-1}^{*}\cdots s_4^{*}{s}_3{s}_2^{*}{s}_1,h))\hfill \\ & =& ({\delta }_{1}h{\mu }_1,\cdots ,{\delta }_n{\delta }_{n-1}\cdots {\delta }_4{\delta }_{3}h{\mu }_3{\mu }_4^{*}\cdots {\mu }_{n-1}{\mu }_n^{*},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{1}h{\mu }_1{\mu }_3^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\delta }_{2}h{\mu }_2,\cdots ,{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_2{\mu }_3^{*}\cdots {\mu }_{n-2}^{*}{\mu }_{n-1},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3{\delta }_{2}h{\mu }_1{\mu }_2^{*}{\mu }_4\cdots {\mu }_{n-1}^{*}{\mu }_n,\hfill \\ & & {\delta }_{\mathit{2}}{\delta }_{\mathit{1}}\mathit{h}{\mu }_{\mathit{1}}{\mu }_{\mathit{2}}^{*},\cdots ,{\delta }_{n-1}{\delta }_{n-2}\cdots {\delta }_3\left({\delta }_2{\delta }_1\right)h\left({\mu }_1{\mu }_2^{*}\right){\mu }_3\cdots {\mu }_{n-2}^{*}{\mu }_{n-1},{\delta }_n{\delta }_{n-1}\cdots {\delta }_3\left({\delta }_2{\delta }_1\right)\hfill \\ & & h\left({\mu }_1{\mu }_2^{*}\right){\mu }_3\cdots {\mu }_{n-1}{\mu }_n^{*})\hfill \end{array}$$

as in the first case, if Eve distinguishes $A_n$ and $B_n$, then in particular, she distinguishes ${\delta }_2{\delta }_{1}h{\mu }_1{\mu }_2^{*}$ from $c_{1}h{c}_2$ (given ${\delta }_{1}h{\mu }_1$ and ${\delta }_{2}h{\mu }_2)$, which means that she distinguishes

$$\begin{array}{ccc}\hfill A_2& =& \left(view(2,\{s_1,s_2\}),y\right)\hfill \\ & =& \left({\delta }_{1}h{\mu }_1,{\delta }_{2}h{\mu }_2,y\right)\hfill \\ \\ \hfill D_2& =& \left(view(2,\{s_1,s_2\}),\varphi (s_2^{*}{s}_1,h)\right)\hfill \\ & =& \left({\delta }_{1}h{\mu }_1,{\delta }_{2}h{\mu }_2,{\delta }_2{\delta }_{1}h{\mu }_1{\mu }_2^{*}\right)\hfill \end{array}$$

which contradicts our hypothesis.

□

So in the Initial Key Agreement the n-users underlying decisional problem is as hard as the 2-users decisional problem. This is also true in the Auxiliary Key Agreement. We can say the protocol provides forward and backward security, i.e. any former or future users cannot distinguish future or past distributed keys, as it is shown in the following result.

Corollary 1.

The AKA provides forward and backward security.

Proof of Corollary 1.

Let Eve be a powerful adversary, that knows all the information of a past user or a future user. She would know a subset of $view(k,\epsilon )$, where k is the number of current users, and $\epsilon$ the secret keys.

In the first case, when the members of the group stay the same, note that the key update adds a new secret key (and we consider it as a new user). Then we substitute n with $k=n+1$, $\varphi (s_n^{*}{s}_{n-1}\cdots s_4^{*}{s}_3{s}_2^{*}{s}_1,h)$ (or $\varphi (s_n{s}_{n-1}^{*}\cdots s_3{s}_2^{*}{s}_1,h))$ with $\varphi (\widetilde{s_c}{s}_n^{*}{s}_{n-1}\cdots s_3{s}_2^{*}{s}_1,h)$ (resp. $\varphi ({\widetilde{s_c}}^{*}{s}_n{s}_{n-1}^{*}\cdots s_3{s}_2^{*}{s}_1,h))$ if n is even (if n is odd), and X with $\epsilon =\{s_1,s_2,\cdots ,s_{c-1},s_c,$$s_{c+1},\cdots ,s_{n-1},s_n,s_c^{\prime }\}$ in Theorem 1. It follows that

$$A_k=\left(view(k,\epsilon ),y\right),fory\in Rrandomlychosen.$$

$$D_k=\left\{\genfrac{}{}{0pt}{}{\left(view(k,\epsilon ),\varphi (\widetilde{s_c}{s}_n^{*}{s}_{n-1}\cdots s_3{s}_2^{*}{s}_1,h)\right),ifkisodd.}{\left(view(k,\epsilon ),\varphi ({\widetilde{s_c}}^{*}{s}_n{s}_{n-1}^{*}\cdots s_3{s}_2^{*}{s}_1,h))\right),ifkiseven.}\right.$$

and it still verifies that if $A_2\sim D_2$, then $A_k\sim D_k$.

When a user leaves, the key update also adds a new secret key, so we replace n with $k=n+1$ (the user left, but we suppose that Eve had access to the communications before that happened, and that private key is still part of the common secret key). The rest is the same, so we get again the first case, and the AKA benefits form the same security benefits in this case.

When a new users joins the group, we need to replace $k=n+2$ (the new secret key and the key update), $\varphi (s_n^{*}{s}_{n-1}\cdots s_4^{*}{s}_3{s}_2^{*}{s}_1,h)$ (or $\varphi (s_n{s}_{n-1}^{*}\cdots s_3{s}_2^{*}{s}_1,h))$ with $\varphi (s_{n+1}^{*}\widetilde{s_c}{s}_n^{*}{s}_{n-1}\cdots$$s_3{s}_2^{*}{s}_1,h)$ (resp. $\varphi (s_{n+1}{\widetilde{s_c}}^{*}{s}_n{s}_{n-1}^{*}\cdots$$s_3{s}_2^{*}{s}_1,h\left)\right)$ if n is even (resp. if n is odd), and X with $\epsilon =\{s_1,s_2,\cdots ,$$s_{n-1},s_n,s_{n+1},s_c^{\prime }\}$ in Theorem 1. It follows that

$$A_k=\left(view(k,\epsilon ),y\right),fory\in Rrandomlychosen.$$

$$D_k=\left\{\genfrac{}{}{0pt}{}{\left(view(k,\epsilon ),\varphi (s_{n+1}^{*}\widetilde{s_c}{s}_n^{*}{s}_{n-1}\cdots s_3{s}_2^{*}{s}_1,h)\right),ifkiseven.}{\left(view(k,\epsilon ),\varphi (s_{n+1}{\widetilde{s_c}}^{*}{s}_n{s}_{n-1}^{*}\cdots s_3{s}_2^{*}{s}_1,h))\right),ifkisodd.}\right.$$

and it still verifies that if $A_2\sim D_2$, then $A_k\sim D_k$, so the Auxiliary Key Agreement benefits from the same security properties. □

Note that we could also consider $D_k$ as

$$D_k=\left\{\genfrac{}{}{0pt}{}{\left(view(k,\epsilon ),\varphi (\widetilde{s_c},K_p))\right),ifkisodd.}{\left(view(k,\epsilon ),\varphi ({\widetilde{s_c}}^{*},K_p))\right),ifkiseven.}\right.$$

where $K_p$ would be the former key, when the number of users stay the same or someone left, and

$$D_k=\left\{\genfrac{}{}{0pt}{}{\left(view(k,\epsilon ),\varphi (s_{n+1}^{*}\widetilde{s_c},K_p))\right),ifkiseven.}{\left(view(k,\epsilon ),\varphi (s_{n+1}{\widetilde{s_c}}^{*},K_p))\right),ifkisodd.}\right.$$

when a new user joins the group.

Also note that in the key refresh, we consider $k=n+1$ in the first two cases, but the set of secret keys are $\{s_1,s_2,\cdots ,s_{c-1},{\widetilde{s_c}}^{*}{s}_c,s_{c+1},\cdots ,s_{n-1},s_n\}$ when n is odd, and $\{s_1,s_2,\cdots ,s_{c-1},\widetilde{s_c}{s}_c^{*},s_{c+1},\cdots ,s_n\}$ when n is even, i.e. the number of stored keys stay the same, and the private key of the user $U_c$ is $\widetilde{s_c^{*}}{s}_c$ or $\widetilde{s_c}{s}_c^{*}$ depending on whether the number of users is even or odd. Finally when $k=n+2$, the set of secret keys has just one new key, from the new user $U_{n+1}$, so it is $\{s_1,s_2,\cdots ,s_{c-1},{\widetilde{s_c}}^{*}{s}_c,s_{c+1},\cdots ,s_{n-1},s_n,s_{n+1}\}$ when n is odd, and $\{s_1,s_2,\cdots ,s_{c-1},\widetilde{s_c}{s}_c^{*},s_{c+1},\cdots ,s_n,s_{n+1}\}$ whenever n is even.

3. Discussion

In [8], Steiner et al. showed that Diffie–Hellman classical key exchange could be extended to a group of users. Many authors have studied similar Diffie–Hellman protocols until Maze et al. in [2] introduced a protocol in a more general setting as is the case of the action of a commutative semigroup over any set, extending all previous cases, and this was extended to a group of users in [9]. In this paper, we have shown a general result, concerning not only the number of users involved, but also a more general setting, as is the case of a noncommutative ring. The commutativity condition which is fundamental in [9] is substituted by a setting where non-commutativity is somehow controlled by a relation, in this case, given by a cocycle. In Proposition 1 we extend the protocols introduced in [3] and [11] for two users to a finite set of users and for every cocycle. Later, in Theorem 1, we prove that the security of this new protocol does not depend on the number of users, i.e., there is no information leakage even in this case where the amount of public information is noticeably greater.