# Signature Scheme Using the Root Extraction Problem on Quaternions

Authors: Baocang Wang; Yupu Hu
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

The root extraction problem over quaternion rings modulo an RSA integer is defined, and the intractability of the problem is examined. A signature scheme is constructed based on the root extraction problem. It is proven that an adversary can forge a signature on a message if and only if he can extract the roots for some quaternion integers. The performance and other security related issues are also discussed.


---

## Body

## 1. Introduction

Cryptographic algorithms are important tools to resolve the security issues in open networks, amongst which the public key cryptographic schemes [1] may be the most powerful tool. In a public key cryptosystem, two separate keys are deployed. One key is kept secret and can be used to decrypt ciphertexts or sign messages, and the other key can be published and is used for encrypting plaintexts or verifying signatures. It requires that it should be computationally infeasible to derive the secret key from the public key. In public key cryptography, three categories of algorithms are widely used in network and information security engineering according to their functionalities, namely, key exchange protocols [2], public key encryption schemes [3], and digital signature schemes [4]. The key exchange protocols are used to establish the shared keys between two communication parties. The public key encryption algorithm allows the encryption key to be published without compromising the security of the decryption key and hence does not require securely initializing a shared key between the communication sender and receiver. A digital signature scheme is used to create a digital signature on a message by using the secret key, so a signature scheme allows the authenticity of a message or a document by using the public key to verify the validity of the signature.It is striking to note that most of the widely used unbroken public key cryptosystems are based on some number-theoretic intractability assumptions such as the integer factorization problem, the discrete logarithm problem defined over finite fields, and the elliptic curve discrete logarithm problem [1]. However, we have a strong desire to enrich the public key cryptographic toolkits to avoid putting all application-oriented eggs in one cryptographic basket. So tremendous efforts had been made to develop public key cryptosystems from other problems. In particular, it seems a nice idea to introduce some noncommutative algebraic structures [5–13] in the design of public key ciphers to destroy the commutativity property commonly shared in the widely used public key cryptosystems.In the realm of noncommutative public key cryptography, some key exchange protocols and public key encryption schemes were developed, amongst which are the notable AAG commutator key exchange protocol [14] and its variants [15–17], the MOR encryption algorithm [18], the MST cryptosystems [19, 20], and the braid public key encryption schemes [21] and their instantiations on other generalized noncommutative groups [7, 11–13]. On the one hand, many of the previous proposals were shown vulnerable to some attacks [22–34]. On the other hand, very few secure signature schemes were known in the literature of noncommutative public key cryptography [35–41]. The known signature schemes may have at least one of the flaws listed below.(i)
The security of the signature schemes cannot be mathematically proven [35–38]. Only the three schemes in [39–41] satisfy the provable security goals.(ii)
Some signature schemes [39–41] utilized some nonstandard intractability assumptions. These newly defined mathematical problems were not fully studied, so if the underlying intractability was not true, these schemes would be insecure.(iii)
The intractability problems were not tightly used in the construction of the signature schemes [35], which makes it possible for an adversary to forge a signature on a message just by solving an easy problem but not necessarily the underlying intractable problem [42, 43].In this paper, we propose a novel signature scheme from the root extraction problem defined on the quaternion ring modulo an RSA integer. Our proposal overcomes the flaws existing in the known signature schemes.(i)
The security is based on the root extraction problem over quaternions, which can be seen as the generalizations of the standard RSA problem and the quadratic residue problem modulo an RSA modulus. So the intractability assumption of our proposal is well established.(ii)
The security of the proposed signature scheme is tightly dependent on the root extraction problem over quaternion rings. Any adversary must solve the underlying intractability problem in order to successfully recover the secret key or forge a signature.(iii)
The proposal is provably secure. We prove that an adversary can forge a signature for a given message if and only if he can extract thee-th root for a given quaternion number.We also provide a thorough security scrutiny on the proposed signature scheme with respect to key recovery attacks and partial key exposure attacks. Performance analysis demonstrates that the proposal is efficient and practical.The rest of the paper is organized as follows. In Section2, we provide some preliminaries about the quaternion algebra, discuss the related root extraction problem, and provide the signature scheme. In Section 3, we analyze the proposal with respect to performance and security. Finally, we conclude the work in Section 4.


## 2. Proposal

We first review some definitions about quaternion algebra and then elaborate on the proposed signature scheme.


### 2.1. Notations

Throughout this paper, we useR to denote the field of real numbers and use the symbol Z to denote the ring of integers. For a positive integer N∈Z, the modular reduction of an integer a∈Z modulo N means the unique nonnegative least remainder b∈Z of a divided by N such that b∈ZN={0,1,…,N-1}, and we denote b=a(mod N). The greatest common divisor of two integers a and b is denoted by gcd(a,b). We use ZN* to denote the set {a∈ZN:gcd(a,N)=1}. For any integer a∈ZN* there exists a unique integer b∈ZN* called the modular inverse of a modulo N such that ab=1(mod N), and we denote b=a-1(mod N).


### 2.2. Arithmetic Operations on Quaternions

The number system of quaternions is the extension of the number system of complex numbers. Formally, we denote the set of quaternions as(1)H={a=a1+a2i+a3j+a4k:a1,a2,a3,a4∈R}.We define three operations on quaternions, namely, addition, scalar multiplication, and quaternion multiplication. For two quaternionsa=a1+a2i+a3j+a4k and b=b1+b2i+b3j+b4k in H, their sum is defined as c=c1+c2i+c3j+c4k with ci=ai+bi for 1≤i≤4. We define the scalar multiplication of a=a1+a2i+a3j+a4k∈H and a∈R as aa=aa1+aa2i+aa3j+aa4k. The quaternion multiplication is somewhat more complicated to define. We first define i2=j2=k2=ijk=-1 and then we can derive the following relations:
(2)ij=k,ji=-k,jk=i,kj=-i,ki=j,ik=-j,
from which we can easily see that quaternion multiplication is noncommutative. So the product of a=a1+a2i+a3j+a4k and b=b1+b2i+b3j+b4k can be easily computed via
(3)ab=a1b+a2ib+a3jb+a4kb=a1b1+a1b2i+a1b3j+a1b4k+a2b1i+a2b2i2+a2b3ij+a2b4ik+a3b1j+a3b2ji+a3b3j2+a3b4jk+a4b1k+a4b2ki+a4b3kj+a4b4k2=(a1b1-a2b2-a3b3-a4b4)+(a1b2+a2b1+a3b4-a4b3)i+(a1b3-a2b4+a3b1+a4b2)j+(a1b4+a2b3-a3b2+a4b1)k.The norm and conjugate ofa=a1+a2i+a3j+a4k are defined as ∥a∥=a12+a22+a32+a42 and a*=a1-a2i-a3j-a4k, respectively. It is easy to verify that ∥a∥=aa*=a*a.For a positive integerN∈Z and a quaternion a=a1+a2i+a3j+a4k, we define a modulo N as
(4)a(mod⁡N)=a1(mod⁡N)+a2(mod⁡N)i+a3(mod⁡N)j+a4(mod⁡N)k.Thus, we can define the setHN={a(mod N):a∈H}. We call a quaternion a invertible modulo N if and only if there exists a quaternion b such that ab=ba=1(mod N), and we denote b=a-1(mod N). We use the symbol HN* to denote the set consisting of all the invertible quaternions in HN. It is easy to verify that a quaternion a∈HN is invertible if and only if gcd(∥a∥,N)=1. When gcd(∥a∥,N)=1, the inverse of a modulo N is easy to compute; namely, a-1=∥a∥-2a*(mod N), where ∥a∥-1 denotes the modular inverse of ∥a∥ modulo N.


### 2.3. Root Extraction Problem overHN

We define thee-th root extraction problem over HN.Definition 1 (thee-th root extraction problem over HN).
Given two positive integersN∈Z and 2≤e∈Z and a quaternion a∈HN, the e-th root extraction problem over HN is defined as finding a quaternion b∈HN if any such that be=a(mod N). In particular, when e=2, the problem is called the quadratic root extraction problem over HN.In this paper, we consider the case ofN being an RSA modulus, namely, N=pq being the product of two distinct large primes p and q. From the above definitions, we can see that when e is relatively prime to ϕ(N)=(p-1)(q-1), the e-th root extraction problem over HN is a generalization of the RSA problem, which asks for the e-th root b for a given integer a∈ZN; namely, a=be(mod N). The quadratic root extraction problem over HN is a generalization of the quadratic residue problem, which is defined as finding an integer b∈ZN such that a=b2(mod N) for the given integer a∈ZN. The quadratic residue problem is proven to be equivalent to the problem of factoring the modulus N in the construction of the Rabin public key cryptosystem [44]. We note that the RSA problem and the quadratic residue problem are widely believed as intractable and had been widely used in the design of public key cryptographic primitives. So we conjecture that the e-th root extraction problem over HN is also intractable.


### 2.4. Quaternion Signature Scheme

Quaternion algebra had been used to design a signature scheme [35]. However, the signature scheme was soon broken [42, 43] by solving a quadratic congruence x2+y2=m(mod N) with the Pollard-Schnorr algorithm [45].We develop a new quaternion signature scheme in the sequel. To begin with, we first define three system parameters: the binary lengthn∈Z of the modulus N, the binary length k∈Z of the hashed value of a message m∈{0,1}*, and 2≤e∈Z. Typically, we set n=1024, k=160, and e=3. We also define a hash function H which maps a message bit string with an arbitrary length into a k-bit-long string; namely, H:{0,1}*→{0,1}k. In this paper, we write a binary number as a string of symbols.


#### 2.4.1. Key Generation

The key generation algorithm runs as follows. Firstly, the signer randomly chooses two distinctn/2-bit-long primes p and q and computes their product N=pq. Then, the signer randomly and uniformly chooses two quaternions b∈HN and r∈HN* and computes a=rber-1(mod N). Finally, the signer publishes the public key as (a,N,H,e) and keeps the secret key as (b,r-1).


#### 2.4.2. Signature

To sign a messagem, the signer firstly computes the hashed value of m; namely, h=H(m). Then, the signer randomly and uniformly chooses a quaternion s∈HN* and computes t=sr-1(mod N) and u=sbhs-1(mod N). Finally, the signer sends (t,u) to the verifier as the signature on the message m.


#### 2.4.3. Verification

Upon receiving the signature(t,u), the verifier firstly computes h=H(m) and v=ah(mod N). Then, the verifier decides whether or not the equation ue=tvt-1(mod N) is satisfied. If the equation is satisfied, the verifier accepts (t,u) as a valid signature on the message m. Otherwise, the verifier refuses to accept (t,u) as a valid signature on m.


#### 2.4.4. Why Verification Works

We explain why a valid signature(t,u) on the message m can pass the verification equation ue=tvt-1(mod N). Note that
(5)tvt-1=(sr-1)ah(sr-1)-1=sr-1(rber-1)hrs-1=sbehs-1=(sbhs-1)e=ue(mod⁡N).So a valid signature(t,u) on the message m can pass the verification process.


## 2.1. Notations

Throughout this paper, we useR to denote the field of real numbers and use the symbol Z to denote the ring of integers. For a positive integer N∈Z, the modular reduction of an integer a∈Z modulo N means the unique nonnegative least remainder b∈Z of a divided by N such that b∈ZN={0,1,…,N-1}, and we denote b=a(mod N). The greatest common divisor of two integers a and b is denoted by gcd(a,b). We use ZN* to denote the set {a∈ZN:gcd(a,N)=1}. For any integer a∈ZN* there exists a unique integer b∈ZN* called the modular inverse of a modulo N such that ab=1(mod N), and we denote b=a-1(mod N).


## 2.2. Arithmetic Operations on Quaternions

The number system of quaternions is the extension of the number system of complex numbers. Formally, we denote the set of quaternions as(1)H={a=a1+a2i+a3j+a4k:a1,a2,a3,a4∈R}.We define three operations on quaternions, namely, addition, scalar multiplication, and quaternion multiplication. For two quaternionsa=a1+a2i+a3j+a4k and b=b1+b2i+b3j+b4k in H, their sum is defined as c=c1+c2i+c3j+c4k with ci=ai+bi for 1≤i≤4. We define the scalar multiplication of a=a1+a2i+a3j+a4k∈H and a∈R as aa=aa1+aa2i+aa3j+aa4k. The quaternion multiplication is somewhat more complicated to define. We first define i2=j2=k2=ijk=-1 and then we can derive the following relations:
(2)ij=k,ji=-k,jk=i,kj=-i,ki=j,ik=-j,
from which we can easily see that quaternion multiplication is noncommutative. So the product of a=a1+a2i+a3j+a4k and b=b1+b2i+b3j+b4k can be easily computed via
(3)ab=a1b+a2ib+a3jb+a4kb=a1b1+a1b2i+a1b3j+a1b4k+a2b1i+a2b2i2+a2b3ij+a2b4ik+a3b1j+a3b2ji+a3b3j2+a3b4jk+a4b1k+a4b2ki+a4b3kj+a4b4k2=(a1b1-a2b2-a3b3-a4b4)+(a1b2+a2b1+a3b4-a4b3)i+(a1b3-a2b4+a3b1+a4b2)j+(a1b4+a2b3-a3b2+a4b1)k.The norm and conjugate ofa=a1+a2i+a3j+a4k are defined as ∥a∥=a12+a22+a32+a42 and a*=a1-a2i-a3j-a4k, respectively. It is easy to verify that ∥a∥=aa*=a*a.For a positive integerN∈Z and a quaternion a=a1+a2i+a3j+a4k, we define a modulo N as
(4)a(mod⁡N)=a1(mod⁡N)+a2(mod⁡N)i+a3(mod⁡N)j+a4(mod⁡N)k.Thus, we can define the setHN={a(mod N):a∈H}. We call a quaternion a invertible modulo N if and only if there exists a quaternion b such that ab=ba=1(mod N), and we denote b=a-1(mod N). We use the symbol HN* to denote the set consisting of all the invertible quaternions in HN. It is easy to verify that a quaternion a∈HN is invertible if and only if gcd(∥a∥,N)=1. When gcd(∥a∥,N)=1, the inverse of a modulo N is easy to compute; namely, a-1=∥a∥-2a*(mod N), where ∥a∥-1 denotes the modular inverse of ∥a∥ modulo N.


## 2.3. Root Extraction Problem overHN

We define thee-th root extraction problem over HN.Definition 1 (thee-th root extraction problem over HN).
Given two positive integersN∈Z and 2≤e∈Z and a quaternion a∈HN, the e-th root extraction problem over HN is defined as finding a quaternion b∈HN if any such that be=a(mod N). In particular, when e=2, the problem is called the quadratic root extraction problem over HN.In this paper, we consider the case ofN being an RSA modulus, namely, N=pq being the product of two distinct large primes p and q. From the above definitions, we can see that when e is relatively prime to ϕ(N)=(p-1)(q-1), the e-th root extraction problem over HN is a generalization of the RSA problem, which asks for the e-th root b for a given integer a∈ZN; namely, a=be(mod N). The quadratic root extraction problem over HN is a generalization of the quadratic residue problem, which is defined as finding an integer b∈ZN such that a=b2(mod N) for the given integer a∈ZN. The quadratic residue problem is proven to be equivalent to the problem of factoring the modulus N in the construction of the Rabin public key cryptosystem [44]. We note that the RSA problem and the quadratic residue problem are widely believed as intractable and had been widely used in the design of public key cryptographic primitives. So we conjecture that the e-th root extraction problem over HN is also intractable.


## 2.4. Quaternion Signature Scheme

Quaternion algebra had been used to design a signature scheme [35]. However, the signature scheme was soon broken [42, 43] by solving a quadratic congruence x2+y2=m(mod N) with the Pollard-Schnorr algorithm [45].We develop a new quaternion signature scheme in the sequel. To begin with, we first define three system parameters: the binary lengthn∈Z of the modulus N, the binary length k∈Z of the hashed value of a message m∈{0,1}*, and 2≤e∈Z. Typically, we set n=1024, k=160, and e=3. We also define a hash function H which maps a message bit string with an arbitrary length into a k-bit-long string; namely, H:{0,1}*→{0,1}k. In this paper, we write a binary number as a string of symbols.


### 2.4.1. Key Generation

The key generation algorithm runs as follows. Firstly, the signer randomly chooses two distinctn/2-bit-long primes p and q and computes their product N=pq. Then, the signer randomly and uniformly chooses two quaternions b∈HN and r∈HN* and computes a=rber-1(mod N). Finally, the signer publishes the public key as (a,N,H,e) and keeps the secret key as (b,r-1).


### 2.4.2. Signature

To sign a messagem, the signer firstly computes the hashed value of m; namely, h=H(m). Then, the signer randomly and uniformly chooses a quaternion s∈HN* and computes t=sr-1(mod N) and u=sbhs-1(mod N). Finally, the signer sends (t,u) to the verifier as the signature on the message m.


### 2.4.3. Verification

Upon receiving the signature(t,u), the verifier firstly computes h=H(m) and v=ah(mod N). Then, the verifier decides whether or not the equation ue=tvt-1(mod N) is satisfied. If the equation is satisfied, the verifier accepts (t,u) as a valid signature on the message m. Otherwise, the verifier refuses to accept (t,u) as a valid signature on m.


### 2.4.4. Why Verification Works

We explain why a valid signature(t,u) on the message m can pass the verification equation ue=tvt-1(mod N). Note that
(5)tvt-1=(sr-1)ah(sr-1)-1=sr-1(rber-1)hrs-1=sbehs-1=(sbhs-1)e=ue(mod⁡N).So a valid signature(t,u) on the message m can pass the verification process.


## 2.4.1. Key Generation

The key generation algorithm runs as follows. Firstly, the signer randomly chooses two distinctn/2-bit-long primes p and q and computes their product N=pq. Then, the signer randomly and uniformly chooses two quaternions b∈HN and r∈HN* and computes a=rber-1(mod N). Finally, the signer publishes the public key as (a,N,H,e) and keeps the secret key as (b,r-1).


## 2.4.2. Signature

To sign a messagem, the signer firstly computes the hashed value of m; namely, h=H(m). Then, the signer randomly and uniformly chooses a quaternion s∈HN* and computes t=sr-1(mod N) and u=sbhs-1(mod N). Finally, the signer sends (t,u) to the verifier as the signature on the message m.


## 2.4.3. Verification

Upon receiving the signature(t,u), the verifier firstly computes h=H(m) and v=ah(mod N). Then, the verifier decides whether or not the equation ue=tvt-1(mod N) is satisfied. If the equation is satisfied, the verifier accepts (t,u) as a valid signature on the message m. Otherwise, the verifier refuses to accept (t,u) as a valid signature on m.


## 2.4.4. Why Verification Works

We explain why a valid signature(t,u) on the message m can pass the verification equation ue=tvt-1(mod N). Note that
(5)tvt-1=(sr-1)ah(sr-1)-1=sr-1(rber-1)hrs-1=sbehs-1=(sbhs-1)e=ue(mod⁡N).So a valid signature(t,u) on the message m can pass the verification process.


## 3. Analysis

### 3.1. Security

We analyze the security of the proposed quaternion signature scheme.


#### 3.1.1. Key Security

The secret key of the proposed signature scheme consists ofb∈HN and r∈HN*. We have the following result with respect to the key security.Theorem 2.
Any adversary can recover the secret key(b,r) from the public key (a,N,H,e) if and only if he can extract the e-th root for a∈HN.Proof.
We first prove the sufficiency of the theorem. Assume that the adversary can extract thee-th root for a∈HN, and we denote it as c∈HN; namely, ce=a(mod N). Then, we randomly choose r∈HN* and compute b=r-1cr(mod N). Then, (b,r) can serve as the secret key of the proposed signature scheme; namely, b and r satisfy a=rber-1(mod N). This is because
(6)rber-1=r(r-1cr)er-1=rr-1cerr-1=ce=a(mod⁡N).
Then, we prove the necessity of the theorem. We assume that the adversary recovers the secret key(b,r). So b and r satisfy a=rber-1(mod N); namely, a=rber-1=(rbr-1)e(mod N), from which we immediately derive an e-th root rbr-1(mod N)∈HN for a∈HN.Theorem 3.
Assume that there exists a polynomial-time algorithmA to break the key security of the proposed quaternion signature scheme. For any quaternion a∈HN such that a has an e-th root in HN, then there exists a polynomial-time algorithm B to determine the e-root of a.Proof.
We want to construct a polynomial-time algorithmB such that given the input (a,N,e), the algorithm B outputs the e-th root for a∈HN. To do this, we just need to show that we can derive a public key from (a,N,e) and then access the algorithm A to recover the corresponding secret key.
We denote thee-th root of a∈HN as c∈HN; namely, ce=a(mod N) and H is a hash function. Thus, we randomly choose r∈HN*, and from the proof of Theorem 2 we know that b=r-1cr(mod N) and r can serve as the secret key of the signature scheme with the corresponding public key (a,N,H,e). So the algorithm B runs as follows. Firstly, B defines a hash function H; then the algorithm B feeds the public key (a,N,H,e) into the algorithm A to obtain the output (b,r) by the algorithm A. Finally, the algorithm B computes and outputs rbr-1(mod N)∈HN. It can be easily verified that rbr-1(mod N) is an e-root of a and that the algorithm B can be carried out in polynomial time.The above theorems say that if the adversary can break the key security of the proposed signature scheme, the adversary can also solve a random instance of thee-th root extraction problem over HN, which seems computationally intractable.


#### 3.1.2. Partial Key Exposure Attacks

We discuss the attacks assuming that the adversary knows the quaternionb or r. If the adversary knows the quaternion r, the adversary can get be=r-1ar(mod N). So the adversary needs to compute the e-root of the quaternion r-1ar∈HN to derive b, which seems computationally impossible. We also have the following result.Theorem 4.
There exist at leastϕ(N)=(p-1)(q-1) quaternions r∈HN* such that a=rber-1(mod⁡ N). If the adversary knows b∈HN, there exists an algorithm A to compute such an r at the cost of O(log⁡23N) bit operations.Proof.
Note that the secret keysb and r satisfy a=rber-1(mod N). So we have gcd⁡(∥r∥,N)=1. Then, for an integer α∈ZN*, if we denote rα=αr(mod N), we must have gcd⁡(∥αr∥,N)=gcd⁡(α∥r∥,N)=1. So rα∈HN* satisfies rαberα-1=αrbe(αr)-1=αrbeα-1r-1=rber-1=a(mod N). Note that ZN* have ϕ(N)=(p-1)(q-1) distinct integers, so we conclude that there exist at least ϕ(N)=(p-1)(q-1) quaternions r∈HN* such that a=rber-1(mod N).
If the adversary knowsb, we know that ar=rbe(mod⁡N), from which the adversary can obtain four linear congruences modulo N by associating the constants and the coefficients of i, j, and k. Thus, we solve the linear congruences by using, for example, the Gaussian elimination algorithm to obtain the coefficients of the quaternion r, which only costs O(log⁡23N) bit operations.The above theorem says that we must keepb secret. Otherwise, the adversary can retrieve the whole secret key in polynomial time.


#### 3.1.3. Signature Forgery Attacks

Given a messagem, we discuss the difficulty for the adversary to forge a signature (u,t) on the message m such that the signature (u,t) can pass the verification equation ue=tvt-1(mod N).Theorem 5.
An adversary can produce a signature(u,t) on a given message m if and only if he can extract the e-th root for v=ah=aH(m)(mod⁡ N).Proof.
We first prove the sufficiency. We assume that the adversary can extract thee-th root denoted as w∈HN for v=ah=aH(m)(mod N); namely, v=ah=we(mod N). The adversary randomly chooses a quaternion t∈HN* and computes u=twt-1(mod N). Note that
(7)ue=(twt-1)e=twet-1=tvt-1(mod⁡N).
So(u,t) can pass the verification equation ue=tvt-1(mod N); namely, a valid signature (u,t) on the message m is forged.
Then, we prove the necessity. If the adversary forges a signature(u,t) on a given message m satisfying ue=tvt-1(mod N), so v=t-1uet=(t-1ut)e(mod N). Thus, an e-th root t-1ut(mod N) is determined for the quaternion v∈HN.The above theorem says that there is only one way for the adversary to forge a signature(u,t) for a given message m, that is, to extract the e-th root for the quaternion v=ah=aH(m)(mod N). However, the e-th root extraction problem over HN is assumed to be intractable. So it is computationally infeasible to forge a signature for a given message.


### 3.2. Performance

We analyze the performance of related issues.


### 3.3. Quaternion Modular Exponentiation Operation

In the proposed signature scheme, quaternion modular exponentiations are often used. For example, in the signature generation algorithm, we need to computebh(mod N), and in the verification algorithm we also need to compute v=ah(mod N). The quaternion modular exponentiation can be performed via a square-and-multiply approach. To illustrate, we let the binary representation of h be h=hk-1⋯h1h0=∑i=0k-1hi2i with hi=0 or 1. Given b∈HN, we firstly set b0=b and compute bi=bi-12=b2i(mod N) for i=1,…,k-1. Then, we compute
(8)bh=∏i=0k-1bihi=∏hi=1bi(mod⁡N).This is because(9)bh=b∑i=0k-1hi2i=∏i=0n-1bhi2i=∏i=0n-1(b2i)hi=∏i=0k-1bihi(mod⁡N).Therefore, to computebh(mod N) we firstly need to do (k-1) quaternion modular multiplications to compute bi and then on average k/2 quaternion modular multiplications to compute ∏hi=1‍bi(mod N). The quaternion modular exponentiation bh(mod N) needs about 3k/2 quaternion modular multiplications.


### 3.4. Computational Costs

We consider the computational costs for signing a message and verifying a signature.In the signature generation phase, we need to do the computationst=sr-1(mod⁡N) and u=sbhs-1(mod N) (here we ignore the computational inexpensive hash operations), which are equivalent to 3 quaternion modular multiplications and one quaternion modular exponentiation. According to the aforementioned analysis, the total computations are equivalent about 3+3k/2 quaternion modular multiplications. We recall the quaternion modular multiplicative operation in Section 2.2. One quaternion modular multiplication costs about 16 modular multiplications. However, we note that modular multiplication modulo N achieves a quadratic complexity; namely, O(log⁡22N)=O(n2). So the computational complexity for the signature scheme is given as O(kn2).In the verification process, we need to computev=ah(mod N) (a quaternion modular exponentiation), ue(mod N) (two quaternion modular multiplications according to the square-and-multiply approach; namely, u1=u2(mod N) and ue=u3=u1u(mod N)), and tvt-1(mod N) (two quaternion modular multiplications). So the computational costs are about 4+3k/2 quaternion modular multiplications. Therefore, the computational complexity for the verification algorithm is also O(kn2).


## 3.1. Security

We analyze the security of the proposed quaternion signature scheme.


### 3.1.1. Key Security

The secret key of the proposed signature scheme consists ofb∈HN and r∈HN*. We have the following result with respect to the key security.Theorem 2.
Any adversary can recover the secret key(b,r) from the public key (a,N,H,e) if and only if he can extract the e-th root for a∈HN.Proof.
We first prove the sufficiency of the theorem. Assume that the adversary can extract thee-th root for a∈HN, and we denote it as c∈HN; namely, ce=a(mod N). Then, we randomly choose r∈HN* and compute b=r-1cr(mod N). Then, (b,r) can serve as the secret key of the proposed signature scheme; namely, b and r satisfy a=rber-1(mod N). This is because
(6)rber-1=r(r-1cr)er-1=rr-1cerr-1=ce=a(mod⁡N).
Then, we prove the necessity of the theorem. We assume that the adversary recovers the secret key(b,r). So b and r satisfy a=rber-1(mod N); namely, a=rber-1=(rbr-1)e(mod N), from which we immediately derive an e-th root rbr-1(mod N)∈HN for a∈HN.Theorem 3.
Assume that there exists a polynomial-time algorithmA to break the key security of the proposed quaternion signature scheme. For any quaternion a∈HN such that a has an e-th root in HN, then there exists a polynomial-time algorithm B to determine the e-root of a.Proof.
We want to construct a polynomial-time algorithmB such that given the input (a,N,e), the algorithm B outputs the e-th root for a∈HN. To do this, we just need to show that we can derive a public key from (a,N,e) and then access the algorithm A to recover the corresponding secret key.
We denote thee-th root of a∈HN as c∈HN; namely, ce=a(mod N) and H is a hash function. Thus, we randomly choose r∈HN*, and from the proof of Theorem 2 we know that b=r-1cr(mod N) and r can serve as the secret key of the signature scheme with the corresponding public key (a,N,H,e). So the algorithm B runs as follows. Firstly, B defines a hash function H; then the algorithm B feeds the public key (a,N,H,e) into the algorithm A to obtain the output (b,r) by the algorithm A. Finally, the algorithm B computes and outputs rbr-1(mod N)∈HN. It can be easily verified that rbr-1(mod N) is an e-root of a and that the algorithm B can be carried out in polynomial time.The above theorems say that if the adversary can break the key security of the proposed signature scheme, the adversary can also solve a random instance of thee-th root extraction problem over HN, which seems computationally intractable.


### 3.1.2. Partial Key Exposure Attacks

We discuss the attacks assuming that the adversary knows the quaternionb or r. If the adversary knows the quaternion r, the adversary can get be=r-1ar(mod N). So the adversary needs to compute the e-root of the quaternion r-1ar∈HN to derive b, which seems computationally impossible. We also have the following result.Theorem 4.
There exist at leastϕ(N)=(p-1)(q-1) quaternions r∈HN* such that a=rber-1(mod⁡ N). If the adversary knows b∈HN, there exists an algorithm A to compute such an r at the cost of O(log⁡23N) bit operations.Proof.
Note that the secret keysb and r satisfy a=rber-1(mod N). So we have gcd⁡(∥r∥,N)=1. Then, for an integer α∈ZN*, if we denote rα=αr(mod N), we must have gcd⁡(∥αr∥,N)=gcd⁡(α∥r∥,N)=1. So rα∈HN* satisfies rαberα-1=αrbe(αr)-1=αrbeα-1r-1=rber-1=a(mod N). Note that ZN* have ϕ(N)=(p-1)(q-1) distinct integers, so we conclude that there exist at least ϕ(N)=(p-1)(q-1) quaternions r∈HN* such that a=rber-1(mod N).
If the adversary knowsb, we know that ar=rbe(mod⁡N), from which the adversary can obtain four linear congruences modulo N by associating the constants and the coefficients of i, j, and k. Thus, we solve the linear congruences by using, for example, the Gaussian elimination algorithm to obtain the coefficients of the quaternion r, which only costs O(log⁡23N) bit operations.The above theorem says that we must keepb secret. Otherwise, the adversary can retrieve the whole secret key in polynomial time.


### 3.1.3. Signature Forgery Attacks

Given a messagem, we discuss the difficulty for the adversary to forge a signature (u,t) on the message m such that the signature (u,t) can pass the verification equation ue=tvt-1(mod N).Theorem 5.
An adversary can produce a signature(u,t) on a given message m if and only if he can extract the e-th root for v=ah=aH(m)(mod⁡ N).Proof.
We first prove the sufficiency. We assume that the adversary can extract thee-th root denoted as w∈HN for v=ah=aH(m)(mod N); namely, v=ah=we(mod N). The adversary randomly chooses a quaternion t∈HN* and computes u=twt-1(mod N). Note that
(7)ue=(twt-1)e=twet-1=tvt-1(mod⁡N).
So(u,t) can pass the verification equation ue=tvt-1(mod N); namely, a valid signature (u,t) on the message m is forged.
Then, we prove the necessity. If the adversary forges a signature(u,t) on a given message m satisfying ue=tvt-1(mod N), so v=t-1uet=(t-1ut)e(mod N). Thus, an e-th root t-1ut(mod N) is determined for the quaternion v∈HN.The above theorem says that there is only one way for the adversary to forge a signature(u,t) for a given message m, that is, to extract the e-th root for the quaternion v=ah=aH(m)(mod N). However, the e-th root extraction problem over HN is assumed to be intractable. So it is computationally infeasible to forge a signature for a given message.


## 3.1.1. Key Security

The secret key of the proposed signature scheme consists ofb∈HN and r∈HN*. We have the following result with respect to the key security.Theorem 2.
Any adversary can recover the secret key(b,r) from the public key (a,N,H,e) if and only if he can extract the e-th root for a∈HN.Proof.
We first prove the sufficiency of the theorem. Assume that the adversary can extract thee-th root for a∈HN, and we denote it as c∈HN; namely, ce=a(mod N). Then, we randomly choose r∈HN* and compute b=r-1cr(mod N). Then, (b,r) can serve as the secret key of the proposed signature scheme; namely, b and r satisfy a=rber-1(mod N). This is because
(6)rber-1=r(r-1cr)er-1=rr-1cerr-1=ce=a(mod⁡N).
Then, we prove the necessity of the theorem. We assume that the adversary recovers the secret key(b,r). So b and r satisfy a=rber-1(mod N); namely, a=rber-1=(rbr-1)e(mod N), from which we immediately derive an e-th root rbr-1(mod N)∈HN for a∈HN.Theorem 3.
Assume that there exists a polynomial-time algorithmA to break the key security of the proposed quaternion signature scheme. For any quaternion a∈HN such that a has an e-th root in HN, then there exists a polynomial-time algorithm B to determine the e-root of a.Proof.
We want to construct a polynomial-time algorithmB such that given the input (a,N,e), the algorithm B outputs the e-th root for a∈HN. To do this, we just need to show that we can derive a public key from (a,N,e) and then access the algorithm A to recover the corresponding secret key.
We denote thee-th root of a∈HN as c∈HN; namely, ce=a(mod N) and H is a hash function. Thus, we randomly choose r∈HN*, and from the proof of Theorem 2 we know that b=r-1cr(mod N) and r can serve as the secret key of the signature scheme with the corresponding public key (a,N,H,e). So the algorithm B runs as follows. Firstly, B defines a hash function H; then the algorithm B feeds the public key (a,N,H,e) into the algorithm A to obtain the output (b,r) by the algorithm A. Finally, the algorithm B computes and outputs rbr-1(mod N)∈HN. It can be easily verified that rbr-1(mod N) is an e-root of a and that the algorithm B can be carried out in polynomial time.The above theorems say that if the adversary can break the key security of the proposed signature scheme, the adversary can also solve a random instance of thee-th root extraction problem over HN, which seems computationally intractable.


## 3.1.2. Partial Key Exposure Attacks

We discuss the attacks assuming that the adversary knows the quaternionb or r. If the adversary knows the quaternion r, the adversary can get be=r-1ar(mod N). So the adversary needs to compute the e-root of the quaternion r-1ar∈HN to derive b, which seems computationally impossible. We also have the following result.Theorem 4.
There exist at leastϕ(N)=(p-1)(q-1) quaternions r∈HN* such that a=rber-1(mod⁡ N). If the adversary knows b∈HN, there exists an algorithm A to compute such an r at the cost of O(log⁡23N) bit operations.Proof.
Note that the secret keysb and r satisfy a=rber-1(mod N). So we have gcd⁡(∥r∥,N)=1. Then, for an integer α∈ZN*, if we denote rα=αr(mod N), we must have gcd⁡(∥αr∥,N)=gcd⁡(α∥r∥,N)=1. So rα∈HN* satisfies rαberα-1=αrbe(αr)-1=αrbeα-1r-1=rber-1=a(mod N). Note that ZN* have ϕ(N)=(p-1)(q-1) distinct integers, so we conclude that there exist at least ϕ(N)=(p-1)(q-1) quaternions r∈HN* such that a=rber-1(mod N).
If the adversary knowsb, we know that ar=rbe(mod⁡N), from which the adversary can obtain four linear congruences modulo N by associating the constants and the coefficients of i, j, and k. Thus, we solve the linear congruences by using, for example, the Gaussian elimination algorithm to obtain the coefficients of the quaternion r, which only costs O(log⁡23N) bit operations.The above theorem says that we must keepb secret. Otherwise, the adversary can retrieve the whole secret key in polynomial time.


## 3.1.3. Signature Forgery Attacks

Given a messagem, we discuss the difficulty for the adversary to forge a signature (u,t) on the message m such that the signature (u,t) can pass the verification equation ue=tvt-1(mod N).Theorem 5.
An adversary can produce a signature(u,t) on a given message m if and only if he can extract the e-th root for v=ah=aH(m)(mod⁡ N).Proof.
We first prove the sufficiency. We assume that the adversary can extract thee-th root denoted as w∈HN for v=ah=aH(m)(mod N); namely, v=ah=we(mod N). The adversary randomly chooses a quaternion t∈HN* and computes u=twt-1(mod N). Note that
(7)ue=(twt-1)e=twet-1=tvt-1(mod⁡N).
So(u,t) can pass the verification equation ue=tvt-1(mod N); namely, a valid signature (u,t) on the message m is forged.
Then, we prove the necessity. If the adversary forges a signature(u,t) on a given message m satisfying ue=tvt-1(mod N), so v=t-1uet=(t-1ut)e(mod N). Thus, an e-th root t-1ut(mod N) is determined for the quaternion v∈HN.The above theorem says that there is only one way for the adversary to forge a signature(u,t) for a given message m, that is, to extract the e-th root for the quaternion v=ah=aH(m)(mod N). However, the e-th root extraction problem over HN is assumed to be intractable. So it is computationally infeasible to forge a signature for a given message.


## 3.2. Performance

We analyze the performance of related issues.


## 3.3. Quaternion Modular Exponentiation Operation

In the proposed signature scheme, quaternion modular exponentiations are often used. For example, in the signature generation algorithm, we need to computebh(mod N), and in the verification algorithm we also need to compute v=ah(mod N). The quaternion modular exponentiation can be performed via a square-and-multiply approach. To illustrate, we let the binary representation of h be h=hk-1⋯h1h0=∑i=0k-1hi2i with hi=0 or 1. Given b∈HN, we firstly set b0=b and compute bi=bi-12=b2i(mod N) for i=1,…,k-1. Then, we compute
(8)bh=∏i=0k-1bihi=∏hi=1bi(mod⁡N).This is because(9)bh=b∑i=0k-1hi2i=∏i=0n-1bhi2i=∏i=0n-1(b2i)hi=∏i=0k-1bihi(mod⁡N).Therefore, to computebh(mod N) we firstly need to do (k-1) quaternion modular multiplications to compute bi and then on average k/2 quaternion modular multiplications to compute ∏hi=1‍bi(mod N). The quaternion modular exponentiation bh(mod N) needs about 3k/2 quaternion modular multiplications.


## 3.4. Computational Costs

We consider the computational costs for signing a message and verifying a signature.In the signature generation phase, we need to do the computationst=sr-1(mod⁡N) and u=sbhs-1(mod N) (here we ignore the computational inexpensive hash operations), which are equivalent to 3 quaternion modular multiplications and one quaternion modular exponentiation. According to the aforementioned analysis, the total computations are equivalent about 3+3k/2 quaternion modular multiplications. We recall the quaternion modular multiplicative operation in Section 2.2. One quaternion modular multiplication costs about 16 modular multiplications. However, we note that modular multiplication modulo N achieves a quadratic complexity; namely, O(log⁡22N)=O(n2). So the computational complexity for the signature scheme is given as O(kn2).In the verification process, we need to computev=ah(mod N) (a quaternion modular exponentiation), ue(mod N) (two quaternion modular multiplications according to the square-and-multiply approach; namely, u1=u2(mod N) and ue=u3=u1u(mod N)), and tvt-1(mod N) (two quaternion modular multiplications). So the computational costs are about 4+3k/2 quaternion modular multiplications. Therefore, the computational complexity for the verification algorithm is also O(kn2).


## 4. Conclusion

In this paper, a quaternion signature scheme was proposed based on the root extraction problem defined over quaternion algebraic structures. The signature scheme only performsO(kn2) bit operations to sign a message and to verify a signature, and hence the proposal is practical. We showed that the key security is equivalent to a random instance of the e-th root extraction problem defined over HN, and the signature forgery security is equivalent to extracting the e-th root for the quaternion v=ah=aH(m)(mod N). Hence, our proposal satisfies some provable security goals.



---

*Source: 819182-2014-05-28.xml*