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

 v(E)− y x (x1 E)− Z mod p = k, as:
 × · × 1 · ·
 (E) 1 y+1 (x E) 1 Z
 v − · x 1· − · mod p = k (10)
 × 1
 From (10) to:
 1 1
 (x E) 1 Z (E− y+1)−
 v = k (x )− 1· − · · mod p (11)
 × 1
  
 From (11), we can calculate u by (9): u = v 1 k mod p.
 − ×
 From values of u and v, we can calculate R of the signature by (2): R = ux2 mod p, and calculate S by (3):
 S = vx2 mod p
 So that, the signature algorithm is described on Algorithm 2 as:
 In which:
 - M: message must be signed, with: M 0, 1
 ∈{ }∞
 - H(.): hash function H : 0, 1 Z , with: q < n < p
 { }∗ → n
 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
 ← 1 (E 1 y+1) 1
 4: v k (x ) (x1 E)− Z − · − mod p
 ← × 1 − · ·
 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:
 E y (R S ) mod p
 R S y ×
 ≡ ×
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 1)/q ((x )− x ) mod q | − { } k →
1 <α<p, x = α mod p, x (1, q), y = (x ) 1 · 2 mod p,1< k < p, Z = x mod p, E = H(M),
 1 − 2 ∈ 1 1
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
 1 1 1
 (x1 E)− Z (E− y+1)− 1 x2 x2
v = k (x1)− · · · mod p, u = v− k mod p, R = u mod p, S = v 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:
 1 1
 E x E E y x E Z x2 E
 A = R mod p = u 2· mod p = v − · x 1· − · · mod p
 × 1
 E 1 y x E x E 1 Z x E x y x x Z y Z
 = v − · · 2· x 1· − · · 2· mod p = v 2· x 1· 2· mod p = S y mod p (15)
 × 1  × 1  ×
 Otherwise, from (2), (3), (8), (11) and (14), we have:
 1 1 x2
 x x (E)− y (x E) Z x
 Z¯ = R S mod p = u 2 v 2 mod p = v · (x ) 1· − · v 2 mod p
 × × × 1 ×
 E 1 y x +x (x ) 1 x E 1 Z (E 1 y+1) x (x ) 1 x E 1 Z
 = v − · · 2 2 x 1 − · 2· − · mod p = v − · · 2 x 1 − · 2· − · mod p
 × 1  × 1 
 1
 1 + − 1 +
 (x ) 1 E 1 Z (E− y 1) (E− y 1) x2 (x ) 1 x E 1 Z
 = k (x )− 1 − · − · · · · · x 1 − · 2· − · mod p
 × 1 × 1
 (x ) 1 E 1 Z x2 (x ) 1 x E 1 Z x (x ) 1 x E 1 Z (x ) 1 x E 1 Z
 = k (x )− 1 − · − · x 1 − · 2· − · mod p = k 2 x − 1 − · 2· − · x 1 − · 2· − · mod p
  × 1  × 1 × 1 × 1
 = kx2 p = Z
  mod  (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 A OLD 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:
 E y (R S ) mod p
 R S y · 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 Huu Mong, 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] Shimin Wei. 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.