A new digital signature scheme based on the hardness of some expanded root problems

ScienceDirect
Available online at www.sciencedirect.com
Procedia Computer Science 171 (2020) 541–550
1877-0509 © 2020 The Authors. Published by Elsevier B.V.
This is an open access article under the CC BY-NC-ND license (
Peer-review under responsibility of the scientific committee of the Third International Conference on Computing and Network 
Communications (CoCoNet’19).
10.1016/j.procs.2020.04.058
10.1016/j.procs.2020.04.058 1877-0509
© 2020 The Authors. Published by Elsevier B.V.
This is an open access article under the CC BY-NC-ND license (
Peer-review under responsibility of the scientific committee of the Third International Conference on Computing and Network 
Communications (CoCoNet’19).
Available online at www.sciencedirect.com
Procedia Computer Science 00 (2019) 000–000
www.elsevier.com/locate/procedia
Third International Conference on Computing and Network Communications (CoCoNet’19)
A new digital signature scheme based on the hardness of some
expanded root problems
Van Luu Xuana,∗, Dung Luu Hongb
aPeople’s Security Academy, Hanoi, Vietnam
bMilitary Technology Academy, Hanoi, Vietnam
Abstract
This paper presents a new digital signature scheme which is based on the hardness of solving root problem and some expanded root
problems on Zp. The expanded root problem is a new form of difficult problem without efficient solution, also originally proposed
and applied to build digital signature algorithms. This proposed scheme enable to build a high-security digital signature platform
for practical applications.
© 2020 The Authors. Published by Elsevier B.V.
This is an open access article under the - - license ( ons.org/licenses/by-nc-nd/4.0/)
r-r i r r s si ilit f t s i tifi itt f t ir I t r ti l f r ti t r
( et’19).
Keywords: Digital Signature; Digital Signature Scheme; Root Problem; Discrete Logarithm Problem.
1. Introduction
The approach of improving the safety of digital signature algorithms based on the difficulty of solving simultane-
ously two difficult problems has attracted much attention from researchers. In [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], authors
have proposed some signature algorithms built on simultaneously two problems of numerical factorization and dis-
crete logarithm. In this paper, with the aim of improving the safety of digital signature algorithms, we continue to
develop the proposed method in [11] on the basis of the difficulty of solving root problem and expanded root problem
on Zp. This is a new form of difficult problem proposed and applied to the construction of digital signature algorithms
and is promising to create highly secure algorithms for practical applications.
∗ Corresponding author. Tel.: +84-986-240-555.
E-mail address: vanlx.hvan@gmail.com
1877-0509© 2020 The Authors. Published by Elsevier B.V.
This is an open access article under the CC BY-NC-ND license (
Peer-review under responsibility of the scientific committee of the Third International Conference on Computing and Network Communications
(CoCoNet’19).
Available online at www.sciencedirect.com
Procedia Computer Science 00 (2019) 000–000
www.elsevier.com/locate/procedia
Third International Conference on Computing and Network Communications (CoCoNet’19)
A new digital signature scheme based on the hardness of some
expanded root problems
Van Luu Xuana,∗, Dung Luu Hongb
aPeople’s Security Academy, Hanoi, Vietnam
bMilitary Technology Academy, Hanoi, Vietnam
Abstract
This paper presents a new digital signature scheme which is based on the hardness of solving root problem and some expanded root
problems on Zp. The expanded root problem is a new form of difficult problem without efficient solution, also originally proposed
and applied to build digital signature algorithms. This proposed scheme enable to build a high-security digital signature platform
for practical applications.
© 2020 The Authors. Published by Elsevier B.V.
This is an open access article under the CC BY-NC-ND license (
Peer-review under responsibility of the scientific committee of the Third International Conference on Computing and Network
Communications (CoCoNet’19).
Keywords: Digital Signature; Digital Signature Scheme; Root Problem; Discrete Logarithm Problem.
1. Introduction
The approach of improving the safety of digital signature algorithms based on the difficulty of solving simultane-
ously two difficult problems has attracted much attention from researchers. In [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], authors
have proposed some signature algorithms built on simultaneously two problems of numerical factorization and dis-
crete logarithm. In this paper, with the aim of improving the safety of digital signature algorithms, we continue to
develop the proposed method in [11] on the basis of the difficulty of solving root problem and expanded root problem
on Zp. This is a new form of difficult problem proposed and applied to the construction of digital signature algorithms
and is promising to create highly secure algorithms for practical applications.
∗ Corresponding author. Tel.: +84-986-240-555.
E-mail address: vanlx.hvan@gmail.com
1877-0509© 2020 The Authors. Published by Elsevier B.V.
This is an open access article under the CC BY-NC-ND license (
Peer-review under responsibility of the scientific committee of the Third International Conference on Computing and Network Communications
(CoCoNet’19).
542 Van Luu Xuan et al. / Procedia Computer Science 171 (2020) 541–550
2 Van Luu Xuan, Dung Luu Hong / Procedia Computer Science 00 (2019) 000–000
2. Constructing digital signature scheme based on the difficult of solving expanded root problem on Zp
2.1. Root problem and expanded root problem on Zp
2.1.1. Root problem on Zp
Given a pair of positive integers (p, e), with p and e are prime numbers. Root problem on Zp (known as RP(p,e)
problem - RP) is stated as:
Let a positive number y ∈ Z∗p, find x satisfy following equation:
xe mod p = y
In [12], N.A. Moldov ... on H : {0, 1}∗ → Zn, with: q < n < p
 Van Luu Xuan et al. / Procedia Computer Science 171 (2020) 541–550 545
Van Luu Xuan, Dung Luu Hong / Procedia Computer Science 00 (2019) 000–000 5
Algorithm 2 Signature Algorithm
Require: (p, q, x1, x2, y)
Ensure: (R, S )
1: E = H(M)
2: select k : 1 < k < p − 1
3: Z ← kx2 mod p
4: v ← (k × (x1)−(x1·E)−1·Z)(E−1·y+1)−1 mod p
5: u ← v−1 × k mod p
6: R ← ux2 mod p
7: S ← vx2 mod p
8: if (R == 1) or (S == 1) then
9: go to 2
10: end if
11: return (R, S )
- (R, S ): signature of U on M.
2.2.3. Testing Algorithm
Testing algorithm of this scheme is assumed that:
RE ≡ S y × y(R×S ) mod p
Here, E is a value representing for the message that need to be verified: E = H(M). If M and the signature (R, S )
satisfy the above equation then the signature is valid and the message will be verified by originality also integrity.
Otherwise, the signature is invalid and the signature is denied by the originality and integrity. Therefore, if the left
side of testing equation is calculated as:
A = RE mod p (12)
and the right side of testing equation is calculated as:
B = S y × (y)Z¯ mod p (13)
in which:
Z¯ = R × S mod p (14)
Then, the condition for valid signature is: A = B.
And after that, the testing algorithm of the new proposed scheme is described in Algorithm 3 as:
2.2.4. On the validity of newly proposed scheme
The problem to prove here is: Let (p, q) are two prime number with q|(p − 1), H : {0, 1}∗ → Zn, q < n < p,
1 < α < p, x1 = α(p−1)/q mod p, x2 ∈ (1, q), y = (x1)((x1)−1·x2) mod q mod p, 1 < k < p, Z = x1k mod p, E = H(M),
546 Van Luu Xuan et al. / Procedia Computer Science 171 (2020) 541–550
6 Van Luu Xuan, Dung Luu Hong / Procedia Computer Science 00 (2019) 000–000
Algorithm 3 Signature Testing Algorithm
Require: p, y, M,R, S
Ensure: True/False
1: E = H(M)
2: A← RE mod p
3: Z¯ ← (R × S ) mod p
4: B← S y × yZ¯ mod p
5: if (A == B) then
6: return True
7: else
8: return False
9: end if
v =
(
k × (x1)−(x1·E)−1·Z)(E−1·y+1)−1 mod p, u = v−1 × k mod p, R = ux2 mod p, S = vx2 mod p. If: Z¯ = (R × S ) mod p,
A = RE mod p, B = S y × (y)Z¯ mod p then: A = B.
The validity of new proposed scheme is proved as:
From (1), (2), (3), (8), (12), (13), we have:
A = RE mod p = ux2·E mod p =
(
vE
−1·y × x1x1·E−1·Z)x2·E mod p
= vE
−1·y·x2·E × x1x1·E−1·Z·x2·E mod p = vx2·y × x1x1·x2·Z mod p = S y × yZ mod p (15)
Otherwise, from (2), (3), (8), (11) and (14), we have:
Z¯ = R × S mod p = ux2 × vx2 mod p = (v(E)−1·y × (x1)(x1·E)−1·Z)x2 × vx2 mod p
= vE
−1·y·x2+x2 × x1(x1)−1·x2·E−1·Z mod p = v(E−1·y+1)·x2 × x1(x1)−1·x2·E−1·Z mod p
=
(
k × (x1)−(x1)−1·E−1·Z)(E−1·y+1)−1·(E−1·y+1)·x2 × x1(x1)−1·x2·E−1·Z mod p
=
(
k × (x1)−(x1)−1·E−1·Z)x2 × x1(x1)−1·x2·E−1·Z mod p = kx2 × x1−(x1)−1·x2·E−1·Z × x1(x1)−1·x2·E−1·Z mod p
= kx2 mod p = Z (16)
Instead (16) to (13), we have:
B = S y × yZ¯ mod p = S y × yZ mod p (17)
From (15) and (17), we have the proof: A = B.
2.2.5. Example
The validity of new proposed scheme is described as the following example:
Parameter and key generation (Algorithm 1).
- Value of p:
68725163710421602525769907649847349329224561651150857096507740072082323110310009374626929
45762504617393960391562394950632907091543448989544193214592175683
 Van Luu Xuan et al. / Procedia Computer Science 171 (2020) 541–550 547
Van Luu Xuan, Dung Luu Hong / Procedia Computer Science 00 (2019) 000–000 7
- Value of q:
1229353517661692379939850342145572622305317605641
- Value of x1:
48051669699286430325099769873197409889390233413921550229794703034625811701849122800410981
64431906367648400948993087914186826814010243861628321531667037565
- Value of x2:
23073770065849979343190666414655409505239998680501822563389127241299376348313476642260085
65199631700372364386528066873934507473557102474896716270086057443
- Value of y:
31035198833232843882397651497983019282008523275800995271592114816098672156191817113438410
22257651799534012056142561395275385765922049867235333739317328265
Signature generation (Algorithm 2).
Input: p, y, x1, x2, M.
Output: (R, S ).
- Message (M):
THIS IS A NEW DIGITAL SIGNATURE ALGORITHM BASED ON THE DIFFICULTY OF SOLVING ROOT PROBLEM!
- Value of k:
56054882373940052940382534700828762997073970656272410226211739800032725425048499016111980
37824843077954493170976665392676379313068956430786101689256561432
- Value of E:
164724432859035768377941367089088508283699589158
- Value of R:
27356778595947718593693754486784230049686914758139517791792546918262551906727787028522248
52246763639649168728753893156814096587757189737152146987611762254
- Value of S :
10849339093448725247612028286262363200243662111874586041904748822259466734113954753234428
80250469877662543154926515638329966224451399913196679722869742636
Signature Verification (Algorithm 3).
Input: p, y,R, S , M.
+ Case No.1:
- The message (M):
THIS IS A NEW DIGITAL SIGNATURE ALGORITHM BASED ON THE DIFFICULTY OF SOLVING ROOT PROBLEM!
- Value of R:
27356778595947718593693754486784230049686914758139517791792546918262551906727787028522248
52246763639649168728753893156814096587757189737152146987611762254
- Value of S :
10849339093448725247612028286262363200243662111874586041904748822259466734113954753234428
80250469877662543154926515638329966224451399913196679722869742636
548 Van Luu Xuan et al. / Procedia Computer Science 171 (2020) 541–550
8 Van Luu Xuan, Dung Luu Hong / Procedia Computer Science 00 (2019) 000–000
- Value of E:
164724432859035768377941367089088508283699589158
- Value of Z:
21325989222147974235975689940302670607160165308180760712030407188875470952902300474997284
13712252199799522946391316983964172350910682094020869864086971180
- Value of A:
12436550186398065363210033079526099066591495476943468492025367910310767982615715824040074
31149425123227042774397989352912769621036566366202192813936089096
- Value of B:
12436550186398065363210033079526099066591495476943468492025367910310767982615715824040074
31149425123227042774397989352912769621036566366202192813936089096
Output: (R, S ) = True.
So that, both the signature and message are not modified, then the result shows that, the signature is valid, and
therefore, the message is verified for its origin and integrity.
+ Case No.2: The message M is fake.
- The message (M):
THIS IS AOLD DIGITAL SIGNATURE ALGORITHM BASED ON THE DIFFICULTY OF SOLVING ROOT PROBLEM!
- Value of R:
27356778595947718593693754486784230049686914758139517791792546918262551906727787028522248
52246763639649168728753893156814096587757189737152146987611762254
- Value of S :
10849339093448725247612028286262363200243662111874586041904748822259466734113954753234428
80250469877662543154926515638329966224451399913196679722869742636
- Value of E:
137309531708235136146636939266564663192268424479
- Value of Z:
21325989222147974235975689940302670607160165308180760712030407188875470952902300474997284
13712252199799522946391316983964172350910682094020869864086971180
- Value of A:
81571510084965727178898520362744046651728762621092246000009956000764507342909118437829677
25869677018466528754758262503459412689766173150373948330214621000
- Value of B:
12436550186398065363210033079526099066591495476943468492025367910310767982615715824040074
31149425123227042774397989352912769621036566366202192813936089096
Output:(R, S ) = False.
In this case, the message (M) has been modified, then the result is a disclaimer of the validity of the signature and
message.
+ Case No.3: R of digital signature is fake.
- The message M:
 Van Luu Xuan et al. / Procedia Computer Science 171 (2020) 541–550 549
Van Luu Xuan, Dung Luu Hong / Procedia Computer Science 00 (2019) 000–000 9
THIS IS A NEW DIGITAL SIGNATURE ALGORITHM BASED ON THE DIFFICULTY OF SOLVING ROOT PROBLEM!
- Value of R:
27356778595947718593693754486784230049686914758139517791792546918262551906727787028522248
52246763639649168728753893156814096587757189737152146987611762250
- Value of S :
10849339093448725247612028286262363200243662111874586041904748822259466734113954753234428
80250469877662543154926515638329966224451399913196679722869742636
- Value of E:
164724432859035768377941367089088508283699589158
- Value of Z:
46653796558774675771297484445100567135410078511833273640919151971919927126756490836686498
38472877306543310718247649381277214544648531430778344187200176319
- Value of A:
14036831179406576392626651928854133371327332083813967907862511781656394453680225630632640
35189903952297795147634315689543260582904527823816470119180632727
- Value of B:
36949700290200180172576125012312232378553164985761068058987377316009925158907911960905367
11471846069179956547875817335498147313249185266537697304318318790
Output: (R, S ) = False.
In this case, the signature has been modified, then the result shows that the signature and message was denied for
validity.
2.2.6. Security level of the newly proposed scheme
The safety level of the proposed scheme can be assessed by its ability to resist some types of attacks such as:
- The secret key attack
In the new proposed scheme, the pair of parameters x1 and x2 are both used as private keys to create a signature.
Therefore, the algorithm is only broken if both parameters are exposed, in other words, the attacker must solve the
expanded root problem on Zp. Therefore, the safety level of the new proposed scheme in terms of attack resistance to
expose the private key is assessed by the difficulty of solving the above problem.
It should be noted that this is a new kind of problem, even if there are polynomial time algorithms for resolve Root
Problem (RP), it does not mean that this problem will be solved. In addition, the parameter q is also used as a private
key in the signing algorithm. Thus, in order to break down the security of the algorithm, the attacker must also solve
the problem of finding the order of x1. However, finding the order of x1 is impossible, because x1 is a secret parameter.
- Forged signature attack
From the verifying algorithm (Algorithm 3) of the new proposed scheme, a fake pair (R, S ) will be recognized as
a valid signature with an message M if the condition is met:
RE ≡ S y × y(R·S ) mod p mod p (18)
From (18), if R is selected before calculating S then the condition (18) will take the following form:
S y ≡ aS mod p (19)
550 Van Luu Xuan et al. / Procedia Computer Science 171 (2020) 541–550
10 Van Luu Xuan, Dung Luu Hong / Procedia Computer Science 00 (2019) 000–000
If S is selected before calculating R then the condition (18) will becomes:
RE ≡ bR mod p (20)
With a, b are constant numbers, it is easy to see that (19) and (20) are in the second form of expanded root problem
without an efficient solution.
3. Conclusion
This paper proposes a new digital signature scheme based on the difficulty of solving expanded root problems
on Zp. Therefore, the safety level of the algorithms built by this method will be ensured by the difficulty of solving
expanded root problems. In mathematics, this is a form of problem without solution before. Therefore, the newly
proposed scheme can be used to develop a digital signature algorithm class for applications that require a high security
in practice.
References
[1] N.A. Moldovyan A.N. Berezin and V.A. Shcherbacov. 2013. “Cryptoschemes Based on Difficulty of Simultaneous Solving Two Different
Difficult Problems”. Computer Science Journal of Moldova 21, 2 (2013).
[2] Pham Van Hiep, Nguyen HuuMong, and Luu Hong Dung. 2018. “Constructing a digital signature algorithm based on the difficult of co-resolve
two hard problems: integer factorization and discrete logarithm”. Journal of Science and Technology of Danang University 7 (2018).
[3] Eddie Shahrie Ismail, Tahat N.M.F., and Rokiah. R. Ahmad. 2008. “A New Digital Signature Scheme Based on Factoring and Discrete Loga-
rithms”. Journal of Mathematics and Statistics (April 2008).
[4] Z. Y. Shen and X. Y. Yu. 2004. “Digital signature scheme based on discrete logarithms and factoring”. Information Technology 28 (June 2004),
21–22.
[5] Nguyen Vinh Thai and Luu Hong Dung. 2018. “A public key cryptosystem based on the difficult of co-resolved two hard problems: discrete
logarithm and root finding”. Journal on Information and Communications, Ministry of Information and Communications (12 2018).
[6] Swati Verma1 and Birendra Kumar Sharma. 2011. “A New Digital Signature Scheme Based on Two Hard Problems”. International Journal of
Pure and Applied Sciences and Technology 5, 2 (2011), 55–59
[7] Sushila Vishnoi and Vishal Shrivastava. 2012. “A new Digital Signature Algorithm based on Factorization and Discrete Logarithm problem”.
International Journal of Computer Trends and Technology 3, 4 (2012).
[8] ShiminWei. 2007. “Digital Signature Scheme Based on Two Hard Problems”. International Journal of Computer Science and Network Security
7, 12 (Dec. 2007), 207–209.
[9] Q. X. WU, Y. X. Yang, and Z. M. HU. 2001. “New signature schemes based on discrete logarithms and factoring”. Journal of Beijing University
of Posts and Telecommunications 24, 1 (Jan. 2001), 61–65.
[10] Qin Yanlin and Wu Xiaoping. 2009. “New Digital Signature Scheme Based on both ECDLP and IFP”. In Proceedings of the 2nd IEEE
International Conference on Computer Science and Information Technology. IEEE, 348–351.
[11] Luu Hong Dung, Tong Minh Duc, and Luu Xuan Van. 2018. “A new method for constructing digital signature schemes base on difficulty
of the integer factorization and discrete logarithm root problems the Zn”. In Proceedings of the 11th Fundamental and Applied IT Research
Conference. 1–9.
[12] N.A. Moldovyan. 2008. “Digital Signature Scheme Based on a New Hard Problem”. Computer Science Journal of Moldova 16, 2 (2008).
[13] T. Elgamal. 1985. “A public key cryptosystem and a signature scheme based on discrete logarithms”. IEEE Transactions on Information Theory
IT-31, 4 (1985), 469–472.