## 1 Introduction

*et al.*, 2019).

*et al.*, 2019).

*et al.*, 2019).

- • Eavesdropping attacks: the adversary can eavesdrop on the legal communications between parties and can obtain the transcript of several interactions between them. As a consequence, the adversary can decrypt secret messages or compromise the secret key.
- • Active attacks: the adversary uses the interaction to try and learn something that will let it impersonate Alice to the Bank and the Bank to Alice. Suppose Alice runs an identification protocol with the Bank over the internet. An active adversary controls the channel and can block or inject messages at will. The adversary waits for Alice to run the identification protocol with the Bank and relays all protocol messages from one side to the other. Once the identification protocol completes successfully, the adversary sends requests to the Bank that appear to be originating from Alice. The bank honors these requests, thinking that they came from Alice. In effect, the adversary uses Alice to authenticate to the Bank and then “hijacks” the session to send his own messages to the Bank. As a consequence of these attacks, the adversary can decrypt secret messages exchanged between parties or compromise their secret keys.

*et al.*, 2009). An attacker capable of eavesdropping on traffic is also able to inject its own messages. The protocol completely falls apart in the presence of an active adversary who controls the network. The main reason is the lack of authentication. Alice sets up a shared secret, but she has no idea with whom the secret is shared. The same holds for the Bank. An active attacker can abuse this to expose all traffic between Alice and the Bank. This attack works against any key exchange protocol that does not include authentication. Moreover, neither KAP, nor identification protocols alone are secure against the MiM attack (Boneh and Shoup, 2020).

*p*.

*m*was used directly in the algorithm instead of H$(m)$. This enables an attack called an existential forgery, as described in the paper of Pointcheval and Stern (Pointcheval and Stern, 2000).

*q*. The main drawback of ElGamal signature is that it has considerable long keys.

*et al.*, 2009; Seurin, 2012).

*et al.*, 2008, 2017; Sakalauskas and Mihalkovich, 2014, 2017; Sakalauskas, 2018). In Sakalauskas and Mihalkovich (2018) it is proved that inversion of MPF corresponds to NP-complete problem. This proof was based on the result presented in Sakalauskas (2012).

## 2 Preliminaries

*q*with generator

*g*. In our case ${G_{q}}$ is a subgroup of the cyclic multiplicative group of integers ${Z_{p}^{\ast }}=\{1,2,\dots ,p-1\}$ where

*p*is prime and multiplication is performed modulo

*p*. Prime

*p*is of

*n*bit length, where

*n*is a security parameter.

*q*is a prime factor of $p-1$, then according to Lagrange’s theorem and its consequences all elements of ${G_{q}}$ are generators. Then for all

*g*in ${G_{q}}$ the following identity holds

*x*be an integer $1\leqslant x\leqslant q-1$, then discrete exponent function dexp() in ${G_{q}}$ is defined as follows:

*g*is a discrete logarithm function’s base defined in (2.2).

*g*is a generator in ${G_{q}}$ then function dexp() is one-to-one and performs the following mapping where ${Z_{q-1}}=\{0,1,2,\dots ,q-1\}$ is a ring of integers with addition and multiplication modulo

*q*. This mapping plays a very important role in security considerations of cryptographic protocols based on dexp() function.

##### Definition 2.2.

*x*in (2.2) when

*g*,

*p*and

*a*are given is negligible.

##### Definition 2.3.

*F*is said to be one-way if: 1) for given $x\in A$, it is computationally easy to compute $y=F(x)$, which corresponds to the direct

*F*value computation; 2) for given $y\in B$, it is computationally hard to compute (at least single) $x\in A$ such that $F(x)=y$, which corresponds to the inverse

*F*value computation.

*p*can be done efficiently even for large numbers commonly referred to as square-and-multiply algorithms. But its inverse value computation corresponds to DLP and is reckoned as hard using classical (non-quantum) computers. But nevertheless, due to Shor (1997) DLP can be solved in polynomial-time using quantum algorithms running on quantum computers.

*p*and

*q*are sufficiently large and suitably chosen primes the discrete logarithm problem in the group ${G_{q}}$ being a subgroup of ${Z_{q-1}}$ is believed to be hard to compute. Prime

*p*should be at least 2048-bits, and

*q*should be at least 256-bits.

*p*and generator

*g*of group ${G_{q}}$.

*r*from the set

*S*then we write:

*p*of at least 2048 bits length, i.e. $|p|=2048$. Prime

*p*should be suitably chosen in such a way that $(p-1)$ should have a prime divider

*q*of 256 bit length, i.e. $|q|=256$. Then the Bank finds a generator

*g*of defined above group ${G_{q}}$.

### 2.1 Diffie–Hellman Key Agreement Protocol (DH-KAP)

*k*.

##### Definition 2.5.

##### Definition 2.6.

##### Definition 2.7.

*w*when

*p*and

*q*are sufficiently large.

*et al.*, 2009). This attack is executed in the following way:

- 1. Alice randomly generates a secret number
*u*in the interval $1<u<p-1$. She computes a session parameter ${k_{A}}={g^{u}}\operatorname{mod} p$ and sends ${k_{A}}$ to the Bank.Then Adversary intercepts ${k_{A}}$ and terminates message transmission to the Bank. Adversary impersonating the Bank against Alice randomly generates a secret number*z*in the interval $1<z<p-1$, computes a session parameter ${k_{Z1}}={g^{z}}\operatorname{mod} p$ and sends ${k_{Z1}}$ to Alice. Analogously, Adversary impersonating Alice against the Bank randomly generates a secret number*w*in the interval $1<w<p-1$, computes a session parameter ${k_{Z2}}={g^{w}}\operatorname{mod} p$ and sends ${k_{Z2}}$ to the Bank. - 2. Alice presuming that message ${k_{Z1}}$ is received from the Bank, computes the agreed secret key ${k_{AZ}}={({k_{Z1}})^{u}}\operatorname{mod} p$.Adversary computes the same secret key ${k_{ZA}}={({k_{A}})^{z}}\operatorname{mod} p$.
- 3. The Bank presuming that ${k_{Z2}}$ is received from Alice, randomly generates a secret number
*v*in the interval $1<v<p-1$. It computes a session parameter ${k_{B}}={g^{v}}\operatorname{mod} p$ and sends ${k_{B}}$ to Alice but this message is intercepted by Adversary. The Bank computes the agreed secret key ${k_{BZ}}={({k_{Z2}})^{v}}\operatorname{mod} p$ as well.Adversary computes the same secret key ${k_{ZB}}={({k_{B}})^{w}}\operatorname{mod} p$.

*k1*which can be decrypted by Alice and vice versa. Alice and the Bank do not suspect that Adversary impersonates both of them.

### 2.2 ElGamal Encryption

*m*be a message to be encrypted by Alice and sent to the Bank. To obtain unambiguous encryption

*m*must satisfy the following inequality $1<m<q$. Encryption is performed using $\text{SP}=(p,g)$ and the Bank’s $\text{PuK}=b$. Encryption is executed in the following way.

*k*, $1<k<q$ and computes

### 2.3 Schnorr Identification Protocol (S-Id)

*x*, not revealing it and the Bank as a verifier V is either accepting this proof if (2.18) identity holds, or rejecting it otherwise. So SID is called

**proof-of-knowledge**.

- 1.
**Completeness:**if the statement is true, the honest verifier V, that is one following the protocol properly, will be convinced of this fact by an honest prover P. - 2.
**Soundness:**if the statement $\text{PuK}=a$ is false, no cheating prover P can convince the honest verifier V that he knows the secret, except with some small probability. - 3.
**Zero-knowledge:**if the statement $\text{PuK}=a$ is true, no verifier learns anything other than the fact that the statement is true. In other words, just knowing the statement but not the secret is sufficient to be convinced that the prover knows the secret. This is formalized by showing that every verifier has some*simulator*that, given only the statement to be proved but without any access to the prover, can produce a conversation that “looks like” an interaction between the honest prover and the verifier in question.

*x*) and V$(a)$ respectively generating a

**conversation**$(l,h,r)\in {G_{q}}\times {Z_{q}}\times {Z_{q}}$. This conversation is an accepting conversation for

*a*if (2.18) holds.

##### Proposition 2.9.

*If the challenge space was small then Schnorr’s identification protocol is insecure.*

##### Comment 2.10.

*N*, i.e. $|{Z_{q}}|=N$. Then, in its impersonation attempt, an adversary could use the simulator to prepare an accepting conversation $(l,h,r)$, send

*l*to V, and then hope that the challenge chosen by V is equal to its prepared challenge

*h*. If so, the adversary could then respond with

*r*, and so make V accept. Thus, Schnorr’s identification protocol is broken with advantage $1/N$; therefore, the challenge space ${Z_{q}}$ must be super-poly in order to ensure security. In our case it is $N={2^{q}}$.

##### Theorem 2.11.

*Under the one-wayness assumption for Gen, and assuming*$|{Z_{q}}|=N$

*is super-poly, Schnorr’s identification protocol is secure against eavesdropping attacks.*

##### Definition 2.12.

##### Proof.

*h*and

*a*are independent, and are uniformly distributed in ${Z_{q}}$. Moreover, for given

*h*and

*a*, the value

*l*is uniquely determined by the equation ${g^{r}}=l{a^{h}}\operatorname{mod} p$ since according to (2.4) dexp() function is one-to-one. Then

*l*has the same distribution as the output distribution of the simulator Sim. □

### 2.4 Schnorr Signature Scheme (S-Sig)

*m*be a message in ${Z_{q}}$ to be signed by the Bank and sent to Alice. Parties are using cryptographic secure H-function to create and verify the signature on the message digest obtained by this function. For signature creation the Bank uses system parameters $SP=(p,g)$ and the Bank’s $\text{PrK}=y$. Let H-function be a mapping H: ${G_{q}}\times {Z_{q}}\to {Z_{q}}$.

*z*, $1<z<q$ and computes first component

*t*of his signature:

*h*and second component

*s*of his signature:

*h*is $\sigma =(s,t)$. Then the Bank sends

*m*and

*σ*to Alice.

*True*if (2.22) is valid.

## 3 AKAP Protocols

*a*) respectively. We assume that the Bank is the trusted party and therefore it can prove its identity to users by its signature and PuK${_{B}}$ certificate realized in the lower level protocols such as SSL/TLS. But nevertheless, we supply AKAP1 and AKAP2 by extra identification of the Bank by signing its challenge sent to the user.

**AKAP1**

- 2. After receiving $(l,a)$ the Bank verifies if the user with his/her public key
*a*is included in its customers’ database and belongs to Alice. If it is ok, then the Bank seeks Alice to prove that she knows to correspond her private key*x*.The Bank chooses a random number $v=\operatorname{rand}({Z_{q}})$ and computes**challenge***h*in the following way The Bank signs challenge*h*using his ${\text{PrK}_{B}}=y$ by Schnorr signature scheme obtaining signature*σ*The Bank sends $(h,\sigma )$ to Alice. - 3. Alice verifies the validity of signature
*σ*on challenge*h*with the Bank’s ${\text{PuK}_{B}}=b$. If it is ok, Alice computes a secret session key ${k_{AB}}$ according to Diffie–Hellman key exchange protocol Having her secrets*u*and*x*Alice computes the following response Alice sends $(r)$ to the Bank.

*r*the Bank verifies if Alice knows her private key

*x*corresponding to her public key

*a*, which is registered in the Bank’s database. The verification equation is the following:

*k*.

*a*is encrypted and the adversary cannot distinguish if either the same person or two different persons are communicating with the Bank when he is eavesdropping and analysing any two different communications.

**AKAP2**

- 1. Alice chooses a random secret number $u=\operatorname{rand}({Z_{q}})$ and computes commitment ${d_{A}}$ This commitment is also a partial key for DH-KAP.To reduce computations Alice uses ${d_{A}}$ to encrypt her ${\text{PuK}_{A}}=a$ by ElGamal encryption scheme to the recipient, the Bank, by computing The ciphertext is ${c_{A}}=({e_{A}},{d_{A}})$. In our case ${d_{A}}$ plays a triple role: commitment, partial key and second component of ciphertext ${c_{A}}$.The ciphertext $({c_{A}})$ is sent to the Bank.
- 2. After receiving ${c_{A}}$ the Bank decrypts ${c_{A}}$ using the Bank’s ${\text{PrK}_{B}}=y$ and obtains Alice’s ${\text{PuK}_{A}}=a$ The Bank verifies if the user with his/her public key is included in its customers’ database and belongs to Alice. If Yes, then the Bank seeks Alice to prove that she knows her corresponding private key
*x*. Otherwise, protocol is terminated.The Bank chooses a random secret number $v=\operatorname{rand}({Z_{q}})$ and computes**challenge***h*The Bank encrypts*h*by ElGamal encryption scheme to recipient Alice by choosing a random secret number $z=\operatorname{rand}({Z_{q}})$ and computing ciphertext $c=(e,d)$To confirm its identity the Bank signs component*e*by choosing a random secret number $w=\operatorname{rand}({Z_{q}})$ and computing Schnorr signature $\sigma =(s,t)$ using its ${\text{PrK}_{B}}=y$ The Bank sends $(c,\sigma )$ to Alice. - 3. Alice verifies the validity of signature
*σ*on value*e*with the Bank’s ${\text{PuK}_{B}}=b$ with verification function $\text{Ver}(b,\sigma ,e)$ in (2.23).If it is the case, then Alice decrypts*c*using her ${\text{PrK}_{A}}=x$ thus obtaining**challenge***h*Alice computes the common secret session key ${k_{AB}}$ Then Alice completes AKAP2 by computing her**response***r*Alice sends $(r)$ to the Bank.

*r*the Bank verifies if Alice is the correct prover. He verifies if the following identity holds

## 4 AKAP Protocol Security Analysis

*X*and

*A*be finite sets and

*R*is a binary relation $R\subseteq X\times A$ on $X\times A$. Then referencing to Boneh and Shoup (2020) we have the following definition.

##### Definition 4.1.

*X*and

*A*are efficiently recognizable finite sets. Elements of

*X*are called witnesses for elements of

*A*and elements of

*A*are called statements.

##### Proof.

*x*is in ${Z_{q}}$ is trivial. Let $a\in {Z_{p}^{\ast }}$ then to decide if $a\in {G_{q}}$ is required to verify the identity (2.1). If it is the case, then $a\in {G_{q}}$ since dexp() function is one-to-one and all elements in ${G_{q}}$ (except 1) are generators. Then for every statement $a\in {G_{q}}$ there exists a unique witness

*x*.

*x*such that ${g^{x}}=a\operatorname{mod} p$ corresponds to solving the DLP.

*l*is a commitment,

*h*-challenge and

*r*-response. □

##### Definition 4.2.

- – To start the protocol, P computes commitment
*l*and sends it to V; - – Upon receiving P’s commitment
*l*, V chooses a challenge*h*at random from a finite super-poly challenge space*C*, and sends*h*to P; - – Upon receiving V’s challenge
*h*, P computes a response*r*, and sends*r*to V; - – Upon receiving P’s response
*r*, V outputs either accept or reject, which must be computed strictly as a function of the statement*a*and the conversation $(l,h,r)$. In particular, V does not make any random choices other than the selection of the challenge*h*. All other computations are completely deterministic.

*x*, rather than the witness/statement pair $(x,a)$, as formally required in the definition of any Sigma protocol. Therefore the conversation $(l,h,r)$ is changed to the conversation $(l,a,h,r)$.

**Completeness:**

**Soundness:**

*x*can succeed in convincing the verifier V.

##### Definition 4.4.

*C*. We say that (P, V) is special honest verifier zero knowledge, or special HVZK if there exists an efficient probabilistic algorithm Sim called a simulator that takes as input $(a,h)$, and satisfies the following properties:

- • for all inputs $(a,h)$, algorithm Sim always outputs a pair $(l,r)$ such that $(l,h,r)$ is an accepting conversation for
*a*; - • for all $(x,a)$ in
*R*, if anybody computes $h=\operatorname{rand}({Z_{q}})$ and $(l,r)=\text{Sim}(a,h)$, then $(l,h,r)$ has the same distribution as that of a transcript of a conversation between P$(x,a)$ and V$(a)$.

*h*as an additional input; second, it is required that the simulator produce an accepting conversation even when the statement

*a*does not have a witness

*x*. These two properties are the reason for the introduction of the notion of special HVZK.

##### Proof.

##### Theorem 4.6.

*Let*(P, V)

*be a Sigma identification protocol for an effective relation R with super-poly challenge space. Assume that*(P, V)

*provides knowledge soundness and is special*HVZK

*. Furthermore, assume that the key generation algorithm Gen for R is one-way. Then Sigma identification protocol with parameters*(Gen, P, V)

*is secure against active attacks.*

##### Proof.

*R*in (4.1) is an effective binary relation. The challenge space

*C*is super-poly since $|C|={2^{q}}$. Referencing to Theorem 4.3 AKAP1 provides knowledge soundness and referencing to Theorem 4.5 AKAP1 is HVZK. Under the DL assumption and conjectured one-wayness of dexp() function key generation algorithm Gen for

*R*is one-way. □

*h*in AKAP1 is encrypted and signed. This encrypt and sign paradigm avoids the chosen-ciphertext attack and is CCA-secure encryption (Boneh and Shoup, 2020).

## 5 Discussions and Further Works

*et al.*, 2008, 2017; Sakalauskas and Mihalkovich, 2014, 2017; Sakalauskas, 2018). MPF has some similarities with discrete exponent function. In Sakalauskas and Mihalkovich (2018) it is proved that inversion of MPF corresponds to a NP-complete problem. This proof was based on the result presented in Sakalauskas (2012). So far, the only key agreement protocol and asymmetric encryption scheme were realized using MPF but we think that the other protocols suitable for AKAP construction can be realized as well. Hence we expect that referencing to the results presented in this paper we could construct new AKAP based on MPF and prove its security using a similar methodology to the one presented in this paper.