# 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:

show all references

##### References:
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$
 [1] Jintai Ding, Sihem Mesnager, Lih-Chung Wang. Letters for post-quantum cryptography standard evaluation. Advances in Mathematics of Communications, 2020, 14 (1) : i-i. doi: 10.3934/amc.2020012 [2] Gerhard Frey. Relations between arithmetic geometry and public key cryptography. Advances in Mathematics of Communications, 2010, 4 (2) : 281-305. doi: 10.3934/amc.2010.4.281 [3] Gérard Maze, Chris Monico, Joachim Rosenthal. Public key cryptography based on semigroup actions. Advances in Mathematics of Communications, 2007, 1 (4) : 489-507. doi: 10.3934/amc.2007.1.489 [4] Philip Lafrance, Alfred Menezes. On the security of the WOTS-PRF signature scheme. Advances in Mathematics of Communications, 2019, 13 (1) : 185-193. doi: 10.3934/amc.2019012 [5] Felipe Cabarcas, Daniel Cabarcas, John Baena. Efficient public-key operation in multivariate schemes. Advances in Mathematics of Communications, 2019, 13 (2) : 343-371. doi: 10.3934/amc.2019023 [6] Jintai Ding, Zheng Zhang, Joshua Deaton. The singularity attack to the multivariate signature scheme HIMQ-3. Advances in Mathematics of Communications, 2021, 15 (1) : 65-72. doi: 10.3934/amc.2020043 [7] Yang Lu, Quanling Zhang, Jiguo Li. An improved certificateless strong key-insulated signature scheme in the standard model. Advances in Mathematics of Communications, 2015, 9 (3) : 353-373. doi: 10.3934/amc.2015.9.353 [8] Meenakshi Kansal, Ratna Dutta, Sourav Mukhopadhyay. Group signature from lattices preserving forward security in dynamic setting. Advances in Mathematics of Communications, 2020, 14 (4) : 535-553. doi: 10.3934/amc.2020027 [9] Lidong Chen, Dustin Moody. New mission and opportunity for mathematics researchers: Cryptography in the quantum era. Advances in Mathematics of Communications, 2020, 14 (1) : 161-169. doi: 10.3934/amc.2020013 [10] Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2021, 15 (1) : 113-130. doi: 10.3934/amc.2020046 [11] Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281 [12] Sanjit Chatterjee, Berkant Ustaoğlu. Malleability and ownership of proxy signatures: Towards a stronger definition and its limitations. Advances in Mathematics of Communications, 2020, 14 (2) : 177-205. doi: 10.3934/amc.2020015 [13] Ke Gu, Xinying Dong, Linyu Wang. Efficient traceable ring signature scheme without pairings. Advances in Mathematics of Communications, 2020, 14 (2) : 207-232. doi: 10.3934/amc.2020016 [14] Diego F. Aranha, Ricardo Dahab, Julio López, Leonardo B. Oliveira. Efficient implementation of elliptic curve cryptography in wireless sensors. Advances in Mathematics of Communications, 2010, 4 (2) : 169-187. doi: 10.3934/amc.2010.4.169 [15] Andreas Klein. How to say yes, no and maybe with visual cryptography. Advances in Mathematics of Communications, 2008, 2 (3) : 249-259. doi: 10.3934/amc.2008.2.249 [16] Anna-Lena Horlemann-Trautmann, Violetta Weger. Information set decoding in the Lee metric with applications to cryptography. Advances in Mathematics of Communications, 2021, 15 (4) : 677-699. doi: 10.3934/amc.2020089 [17] Neal Koblitz, Alfred Menezes. Critical perspectives on provable security: Fifteen years of "another look" papers. Advances in Mathematics of Communications, 2019, 13 (4) : 517-558. doi: 10.3934/amc.2019034 [18] Jie Xu, Lanjun Dang. An efficient RFID anonymous batch authentication protocol based on group signature. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1489-1500. doi: 10.3934/dcdss.2019102 [19] Joan-Josep Climent, Juan Antonio López-Ramos. Public key protocols over the ring $E_{p}^{(m)}$. Advances in Mathematics of Communications, 2016, 10 (4) : 861-870. doi: 10.3934/amc.2016046 [20] Mohammad Sadeq Dousti, Rasool Jalili. FORSAKES: A forward-secure authenticated key exchange protocol based on symmetric key-evolving schemes. Advances in Mathematics of Communications, 2015, 9 (4) : 471-514. doi: 10.3934/amc.2015.9.471

2020 Impact Factor: 0.935