# American Institute of Mathematical Sciences

doi: 10.3934/amc.2021016
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

## Delegating signing rights in a multivariate proxy signature scheme

 1 Department of Mathematics, National Institute of Technology Jamshedpur, Jamshedpur-831014, India 2 Department of Applied Mathematics, Naval Postgraduate School, Monterey, CA 93943, USA 3 Department of Mathematics, The LNM Institute of Information Technology, Jaipur-302031, India

* Corresponding author: nknkundu@gmail.com

Received  October 2020 Revised  February 2021 Early access June 2021

Fund Project: The first author is supported by DRDO, India (ERIP/ER/202005001/M/01/1775)

In the context of digital signatures, the proxy signature holds a significant role of enabling an original signer to delegate its signing ability to another party (i.e., proxy signer). It has significant practical applications. Particularly it is useful in distributed systems, where delegation of authentication rights is quite common. For example, key sharing protocol, grid computing, and mobile communications. Currently, a large portion of existing proxy signature schemes are based on the hardness of problems like integer factoring, discrete logarithms, and/or elliptic curve discrete logarithms. However, with the rising of quantum computers, the problem of prime factorization and discrete logarithm will be solvable in polynomial-time, due to Shor's algorithm, which dilutes the security features of existing ElGamal, RSA, ECC, and the proxy signature schemes based on these problems. As a consequence, construction of secure and efficient post-quantum proxy signature becomes necessary. In this work, we develop a post-quantum proxy signature scheme Mult-proxy, relying on multivariate public key cryptography (MPKC), which is one of the most promising candidates of post-quantum cryptography. We employ a 5-pass identification protocol to design our proxy signature scheme. Our work attains the usual proxy criterion and a one-more-unforgeability criterion under the hardness of the Multivariate Quadratic polynomial (MQ) problem. It produces optimal size proxy signatures and optimal size proxy shares in the field of MPKC.

Citation: Sumit Kumar Debnath, Tanmay Choudhury, Pantelimon Stănică, Kunal Dey, Nibedita Kundu. Delegating signing rights in a multivariate proxy signature scheme. Advances in Mathematics of Communications, doi: 10.3934/amc.2021016
##### References:
 [1] A. K. Awasthi and S. Lal, Proxy blind signature scheme, Trans. on Cryptology, 2:1 (2005), 5-11. [2] D. J. Bernstein, Introduction to Post-Quantum Cryptography, Post-Quantum Cryptography, Springer–Berlin, Heidelberg, 2009, 1–14. doi: 10.1007/978-3-540-88702-7_1. [3] A. Bogdanov, T. Eisenbarth, A. Rupp and C. Wolf, Time-area optimized public-key engines: MQ-cryptosystems as replacement for elliptic curves?, Cryptographic Hardware and Embedded Systems, 5154 (2008), 45-61. [4] A. Boldyreva, A. Palacio and B. Warinschi, Secure proxy signature schemes for delegation of signing rights, J. Cryptology, 25 (2012), 57-115.  doi: 10.1007/s00145-010-9082-x. [5] A. I.-T. Chen, M.-S. Chen, T.-R. Chen, C.-M. Cheng, J. Ding, E. L.-H. Kuo, F. Y.-S. Lee and B.-Y. Yang, SSE implementation of multivariate PKCS on modern x86 CPUs, International Workshop on Cryptographic Hardware and Embedded Systems, (2009), 33–48. [6] J. Chen, J. Ling, J. Ning, E. Panaousis, G. Loukas, K. Liang and J. Chen, Post quantum proxy signature scheme based on the multivariate public key cryptographic signature, International J. Distributed Sensor Networks, 16 (2020). doi: 10.1177/1550147720914775. [7] M.-S. Chen, A. Hülsing, J. Rijneveld, S. Samardjiska and P. Schwabe, From 5-pass MQ-based identification to MQ-based signatures, Adv. Cryptology, 10032 (2016), 135-165.  doi: 10.1007/978-3-662-53890-6_5. [8] J. -Zhu Dai, X.-H. Yang and J.-X. Dong, Designated-receiver proxy signature scheme for electronic commerce, SMC'03 Conference Proceedings. 2003 IEEE International Conference on Systems, Man and Cybernetics. Conference Theme-System Security and Assurance (Cat. No. 03CH37483), IEEE, 1 (2003), 384-389. [9] J. Ding and D. Schmidt, Rainbow, a new multivariable polynomial signature scheme, International Conference on Applied Cryptography and Network Security, (2005), 164–175. doi: 10.1007/s40840-015-0125-1. [10] G. Fuchsbauer and D. Pointcheval, Anonymous proxy signatures, International Conference on Security and Cryptography for Networks, (2008), 201–217. [11] M. R. Garey and D. S. Johnson, Computers and Intractability: A guide to the theory of NP-completeness, Freeman San Francisco, 174 (1979). [12] A. Kipnis, J. Patarin and L. Goubin, Unbalanced oil and vinegar signature schemes, International Conference on the Theory and Applications of Cryptographic Techniques, (1999), 206–222. doi: 10.1007/3-540-48910-X_15. [13] Q. Lin, Ji n Li, Z. Huang, W. Chen and J. Shen, A short linearly homomorphic proxy signature scheme, IEEE Access, 6 (2018), 12966-12972. [14] M. Mambo, K. Usuda and E. Okamoto, Proxy signatures: Delegation of the power to sign messages, IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, 79:9 (1996), 1338-1354. [15] M. Mambo, K. Usuda and E. Okamoto, Proxy signatures for delegating signing operation, Proceedings of the 3rd ACM conference on Computer and Communications Security, (1996), 48–57. [16] T. Matsumoto and H. Imai, Public quadratic polynomial-tuples for efficient signature-verification and message-encryption, Workshop on the Theory and Application of Cryptographic Techniques, (1988), 419–453. doi: 10.1007/3-540-45961-8_39. [17] J. Patarin, Hidden fields equations (HFE) and isomorphisms of polynomials (IP): Two new families of asymmetric algorithms, International Conference on the Theory and Applications of Cryptographic Techniques, (1996), 33–48. [18] A. Petzoldt, M.-S. Chen, B.-Y. Yang, C. Tao and J. Ding, Design principles for HFEV-based multivariate signature schemes, International Conference on the Theory and Application of Cryptology and Information Security, (2015), 311–334. doi: 10.1007/978-3-662-48797-6_14. [19] E. Sakalauskas, The multivariate quadratic power problem over ZN is NP-complete, Information Technology and Control, 41:1 (2012), 33-39. [20] K. Sakumoto, T. Shirai and H. Hiwatari, Public-key identification schemes based on multivariate quadratic polynomials, Advances in Cryptology, 6841 (2011), 706-723.  doi: 10.1007/978-3-642-22792-9_40. [21] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Review, 41 (1999), 303-332.  doi: 10.1137/S0036144598347011. [22] S. Tang and L. Xu, Proxy signature scheme based on isomorphisms of polynomials, in International Conference on Network and System Security, (2012), 113–125. doi: 10.1007/978-3-642-34601-9_9. [23] G. Wang, F. Bao, J. Zhou and R. H Deng, Security analysis of some proxy signatures, International Conference on Information Security and Cryptology, (2003), 305–319. doi: 10.1007/978-3-540-24691-6_23. [24] F. Wu, W. Yao, X. Zhang, W. Wang and Z. Zheng, Identity-based proxy signature over NTRU lattice, International J. Communication Systems, 32 (2019), e3867. doi: 10.1002/dac.3867. [25] K. Zhang, Threshold proxy signature schemes, International Workshop on Information Security, (1997), 282–290. [26] H. Zhu, Y. Tan, X. Yu, Y. Xue, Q. Zhang, L. Zhu and Y. Li, An identity-based proxy signature on NTRU lattice, Chinese J. Electronics, 27:2 (2018), 297-303.

show all references

##### References:
 [1] A. K. Awasthi and S. Lal, Proxy blind signature scheme, Trans. on Cryptology, 2:1 (2005), 5-11. [2] D. J. Bernstein, Introduction to Post-Quantum Cryptography, Post-Quantum Cryptography, Springer–Berlin, Heidelberg, 2009, 1–14. doi: 10.1007/978-3-540-88702-7_1. [3] A. Bogdanov, T. Eisenbarth, A. Rupp and C. Wolf, Time-area optimized public-key engines: MQ-cryptosystems as replacement for elliptic curves?, Cryptographic Hardware and Embedded Systems, 5154 (2008), 45-61. [4] A. Boldyreva, A. Palacio and B. Warinschi, Secure proxy signature schemes for delegation of signing rights, J. Cryptology, 25 (2012), 57-115.  doi: 10.1007/s00145-010-9082-x. [5] A. I.-T. Chen, M.-S. Chen, T.-R. Chen, C.-M. Cheng, J. Ding, E. L.-H. Kuo, F. Y.-S. Lee and B.-Y. Yang, SSE implementation of multivariate PKCS on modern x86 CPUs, International Workshop on Cryptographic Hardware and Embedded Systems, (2009), 33–48. [6] J. Chen, J. Ling, J. Ning, E. Panaousis, G. Loukas, K. Liang and J. Chen, Post quantum proxy signature scheme based on the multivariate public key cryptographic signature, International J. Distributed Sensor Networks, 16 (2020). doi: 10.1177/1550147720914775. [7] M.-S. Chen, A. Hülsing, J. Rijneveld, S. Samardjiska and P. Schwabe, From 5-pass MQ-based identification to MQ-based signatures, Adv. Cryptology, 10032 (2016), 135-165.  doi: 10.1007/978-3-662-53890-6_5. [8] J. -Zhu Dai, X.-H. Yang and J.-X. Dong, Designated-receiver proxy signature scheme for electronic commerce, SMC'03 Conference Proceedings. 2003 IEEE International Conference on Systems, Man and Cybernetics. Conference Theme-System Security and Assurance (Cat. No. 03CH37483), IEEE, 1 (2003), 384-389. [9] J. Ding and D. Schmidt, Rainbow, a new multivariable polynomial signature scheme, International Conference on Applied Cryptography and Network Security, (2005), 164–175. doi: 10.1007/s40840-015-0125-1. [10] G. Fuchsbauer and D. Pointcheval, Anonymous proxy signatures, International Conference on Security and Cryptography for Networks, (2008), 201–217. [11] M. R. Garey and D. S. Johnson, Computers and Intractability: A guide to the theory of NP-completeness, Freeman San Francisco, 174 (1979). [12] A. Kipnis, J. Patarin and L. Goubin, Unbalanced oil and vinegar signature schemes, International Conference on the Theory and Applications of Cryptographic Techniques, (1999), 206–222. doi: 10.1007/3-540-48910-X_15. [13] Q. Lin, Ji n Li, Z. Huang, W. Chen and J. Shen, A short linearly homomorphic proxy signature scheme, IEEE Access, 6 (2018), 12966-12972. [14] M. Mambo, K. Usuda and E. Okamoto, Proxy signatures: Delegation of the power to sign messages, IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, 79:9 (1996), 1338-1354. [15] M. Mambo, K. Usuda and E. Okamoto, Proxy signatures for delegating signing operation, Proceedings of the 3rd ACM conference on Computer and Communications Security, (1996), 48–57. [16] T. Matsumoto and H. Imai, Public quadratic polynomial-tuples for efficient signature-verification and message-encryption, Workshop on the Theory and Application of Cryptographic Techniques, (1988), 419–453. doi: 10.1007/3-540-45961-8_39. [17] J. Patarin, Hidden fields equations (HFE) and isomorphisms of polynomials (IP): Two new families of asymmetric algorithms, International Conference on the Theory and Applications of Cryptographic Techniques, (1996), 33–48. [18] A. Petzoldt, M.-S. Chen, B.-Y. Yang, C. Tao and J. Ding, Design principles for HFEV-based multivariate signature schemes, International Conference on the Theory and Application of Cryptology and Information Security, (2015), 311–334. doi: 10.1007/978-3-662-48797-6_14. [19] E. Sakalauskas, The multivariate quadratic power problem over ZN is NP-complete, Information Technology and Control, 41:1 (2012), 33-39. [20] K. Sakumoto, T. Shirai and H. Hiwatari, Public-key identification schemes based on multivariate quadratic polynomials, Advances in Cryptology, 6841 (2011), 706-723.  doi: 10.1007/978-3-642-22792-9_40. [21] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Review, 41 (1999), 303-332.  doi: 10.1137/S0036144598347011. [22] S. Tang and L. Xu, Proxy signature scheme based on isomorphisms of polynomials, in International Conference on Network and System Security, (2012), 113–125. doi: 10.1007/978-3-642-34601-9_9. [23] G. Wang, F. Bao, J. Zhou and R. H Deng, Security analysis of some proxy signatures, International Conference on Information Security and Cryptology, (2003), 305–319. doi: 10.1007/978-3-540-24691-6_23. [24] F. Wu, W. Yao, X. Zhang, W. Wang and Z. Zheng, Identity-based proxy signature over NTRU lattice, International J. Communication Systems, 32 (2019), e3867. doi: 10.1002/dac.3867. [25] K. Zhang, Threshold proxy signature schemes, International Workshop on Information Security, (1997), 282–290. [26] H. Zhu, Y. Tan, X. Yu, Y. Xue, Q. Zhang, L. Zhu and Y. Li, An identity-based proxy signature on NTRU lattice, Chinese J. Electronics, 27:2 (2018), 297-303.
Communication flow in signature scheme
5-pass identification protocol
Our proxy signature protocol
General comparison of different key sizes of our scheme Mult-proxy, Tang and Xu's scheme [22] and Proxy Rainbow [6] with Rainbow [9] as central map
 Scheme Mult-proxy Tang and Xu's scheme [22] Proxy Rainbow [6] Delegation Partial with warrant Partial with warrant Partial with warrant O.S's pub-key $\frac{mn^2+3mn+2m}{2}\cdot p$ $(\frac{mn^2+3mn+2m}{2}+\xi)\cdot p$ $\frac{mn^2+3mn+2m}{2}\cdot p$ P.S's pub-key $\frac{mn^2+3mn+2m}{2}\cdot p$ $(\frac{mn^2+3mn+2m}{2}+\xi)\cdot p$ $\frac{mn^2+3mn+2m}{2}\cdot p$ O.S's sec-key $(m^2+n^2+m+n+\xi)\cdot p$ $(m^2+n^2+m+n)\cdot p$ $(m^2+n^2+m+n+\xi)\cdot p$ P.S's sec-key $(m^2+n^2+m+n+\xi)\cdot p$ $(m^2+n^2+m+n)\cdot p$ $(m^2+n^2+m+n+\xi)\cdot p$ Proxy share $n\cdot p$ $\frac{mn^2+2m^2+3mn+2n^2+4m+2n}{2}\cdot p$ $\frac{mn^2+2m^2+3mn+2n^2+4m+2n}{2}\cdot p$ Proxy sig $2k\cdot \omega+(k(m+2n)+n)\cdot p$ $k+k(m^2+n^2+m+n)\cdot p$ $\frac{3mn^2+9mn+6m+6n}{2}\cdot p$
 Scheme Mult-proxy Tang and Xu's scheme [22] Proxy Rainbow [6] Delegation Partial with warrant Partial with warrant Partial with warrant O.S's pub-key $\frac{mn^2+3mn+2m}{2}\cdot p$ $(\frac{mn^2+3mn+2m}{2}+\xi)\cdot p$ $\frac{mn^2+3mn+2m}{2}\cdot p$ P.S's pub-key $\frac{mn^2+3mn+2m}{2}\cdot p$ $(\frac{mn^2+3mn+2m}{2}+\xi)\cdot p$ $\frac{mn^2+3mn+2m}{2}\cdot p$ O.S's sec-key $(m^2+n^2+m+n+\xi)\cdot p$ $(m^2+n^2+m+n)\cdot p$ $(m^2+n^2+m+n+\xi)\cdot p$ P.S's sec-key $(m^2+n^2+m+n+\xi)\cdot p$ $(m^2+n^2+m+n)\cdot p$ $(m^2+n^2+m+n+\xi)\cdot p$ Proxy share $n\cdot p$ $\frac{mn^2+2m^2+3mn+2n^2+4m+2n}{2}\cdot p$ $\frac{mn^2+2m^2+3mn+2n^2+4m+2n}{2}\cdot p$ Proxy sig $2k\cdot \omega+(k(m+2n)+n)\cdot p$ $k+k(m^2+n^2+m+n)\cdot p$ $\frac{3mn^2+9mn+6m+6n}{2}\cdot p$
Numeric comparison of different key sizes of our scheme Mult-proxy, Tang and Xu's scheme [22] and Proxy Rainbow [6] with Rainbow [9] as central map
 Scheme Mult-proxy Tang and Xu's scheme [22] Proxy Rainbow [6] Parameters (256, 18, 12, 12) (256, 18, 12, 12) (256, 18, 12, 12) O.S's public key size (kB) $177.4$ $297.9$ $177.4$ P.S's public key size (kB) $177.4$ $297.9$ $177.4$ O.S's secret key size (kB) $139.4$ $18.8$ $139.4$ P.S's secret key size(kB) $139.4$ $18.8$ $139.4$ Proxy share size (kB) $0.33$ $196.2$ $196.2$ Proxy signature size (kB) $173.7$ $2424.9$ $533.1$ Parameters (256, 40, 24, 24) (256, 40, 24, 24) (256, 40, 24, 24) O.S's public key size (kB) $1501.9$ $2542.6$ $1501.9$ P.S's public key size (kB) $1501.9$ $2542.6$ $1501.9$ O.S's secret key size (kB) $1120.2$ $79.6$ $1120.2$ P.S's secret key size(kB) $1120.2$ $79.6$ $1120.2$ Proxy share size (kB) $0.7$ $1581.4$ $1581.4$ Proxy signature size (kB) $290.9$ $10263.7$ $4507.7$ Parameters (31, 28, 20, 20, 8) (31, 28, 20, 20, 8) (31, 28, 20, 20, 8) O.S's public key size (kB) $938.7$ $1935.5$ $938.7$ P.S's public key size (kB) $938.7$ $1935.5$ $938.7$ O.S's secret key size (kB) $1046.5$ $49.7$ $1046.5$ P.S's secret key size(kB) $1046.5$ $49.7$ $1046.5$ Proxy share size (kB) $0.43$ $988.4$ $988.4$ Proxy signature size (kB) $206$ $6414.8$ $2817.3$
 Scheme Mult-proxy Tang and Xu's scheme [22] Proxy Rainbow [6] Parameters (256, 18, 12, 12) (256, 18, 12, 12) (256, 18, 12, 12) O.S's public key size (kB) $177.4$ $297.9$ $177.4$ P.S's public key size (kB) $177.4$ $297.9$ $177.4$ O.S's secret key size (kB) $139.4$ $18.8$ $139.4$ P.S's secret key size(kB) $139.4$ $18.8$ $139.4$ Proxy share size (kB) $0.33$ $196.2$ $196.2$ Proxy signature size (kB) $173.7$ $2424.9$ $533.1$ Parameters (256, 40, 24, 24) (256, 40, 24, 24) (256, 40, 24, 24) O.S's public key size (kB) $1501.9$ $2542.6$ $1501.9$ P.S's public key size (kB) $1501.9$ $2542.6$ $1501.9$ O.S's secret key size (kB) $1120.2$ $79.6$ $1120.2$ P.S's secret key size(kB) $1120.2$ $79.6$ $1120.2$ Proxy share size (kB) $0.7$ $1581.4$ $1581.4$ Proxy signature size (kB) $290.9$ $10263.7$ $4507.7$ Parameters (31, 28, 20, 20, 8) (31, 28, 20, 20, 8) (31, 28, 20, 20, 8) O.S's public key size (kB) $938.7$ $1935.5$ $938.7$ P.S's public key size (kB) $938.7$ $1935.5$ $938.7$ O.S's secret key size (kB) $1046.5$ $49.7$ $1046.5$ P.S's secret key size(kB) $1046.5$ $49.7$ $1046.5$ Proxy share size (kB) $0.43$ $988.4$ $988.4$ Proxy signature size (kB) $206$ $6414.8$ $2817.3$

2021 Impact Factor: 1.015