Ramp Scheme Based on CRT for Polynomial Ring over Finite Field

doi:10.1007/s11424-022-1292-4

Journal of Systems Science and Complexity ›› 2023, Vol. 36 ›› Issue (1): 129-150.DOI: 10.1007/s11424-022-1292-4

Previous Articles Next Articles

Ramp Scheme Based on CRT for Polynomial Ring over Finite Field

DING Jian^1,2, KE Pinhui³, LIN Changlu³, WANG Huaxiong⁴

1. College of Computer and Cyber Security, Fujian Normal University, Fuzhou 350007, China;
2. School of Mathematics and Big Data, Chaohu Univeristy, Hefei 238024, China;
3. School of Mathematics and Statistics, and Fujian Provincial Key Lab of Network Security and Cryptology, Fujian Normal University, Fuzhou 350007, China;
4. School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 639798, Singapore

Received:2021-08-12 Revised:2021-10-06 Online:2023-01-25 Published:2023-02-09
Supported by:
This paper was supported by the National Natural Science Foundation of China under Grant Nos. U1705264, 61572132, 61772292 and 61772476, the Natural Science Foundation of Fujian Province under Grant No. 2019J01275, University Natural Science Research Project of Anhui Province under Grant No. KJ2020A0779, the Singapore Ministry of Education under Grant Nos. RG12/19 and RG21/18 (S)

PDF ( 31 ) Cited

DING Jian, KE Pinhui, LIN Changlu, WANG Huaxiong. Ramp Scheme Based on CRT for Polynomial Ring over Finite Field[J]. Journal of Systems Science and Complexity, 2023, 36(1): 129-150.

Chinese Reminder Theorem (CRT) for integers has been widely used to construct secret sharing schemes for different scenarios, but these schemes have lower information rates than that of Lagrange interpolation-based schemes. In ASIACRYPT 2018, Ning, et al. constructed a perfect $(r,n)$-threshold scheme based on CRT for polynomial ring over finite field, and the corresponding information rate is one which is the greatest case for a $(r,n)$-threshold scheme. However, for many practical purposes, the information rate of Ning, et al. scheme is low and perfect security is too much security. In this work, the authors generalize the Ning, et al. $(r,n)$-threshold scheme to a $(t,r,n)$-ramp scheme based on CRT for polynomial ring over finite field, which attains the greatest information rate $(r-t)$ for a $(t,r,n)$-ramp scheme. Moreover, for any given $2\leq r_1 < r_2\leq n$, the ramp scheme can be used to construct a $(r_1,n)$-threshold scheme that is threshold changeable to $(r',n)$-threshold scheme for all $r'\in \{r_1+1,r_1+2,\cdots,r_2\}$. The threshold changeable secret sharing (TCSS) scheme has a greater information rate than other existing TCSS schemes of this type.

Key words: Chinese Reminder Theorem, polynomial ring, ramp scheme, threshold changeable secret sharing

[1] Blakley G R, Safeguarding cryptographic keys, Proceedings of the National Computer Conference'1979, AFIPS Proceedings, 1979, 48:313-317.
[2] Shamir A, How to share a secret, Communications of the ACM, 1979, 22(11):612-613.
[3] Asmuth C and Bloom J, A modular approach to key safeguarding, IEEE Trans. Inf. Theory, 1983, 29(2):208-210.
[4] Harn L and Miao F, Weighted secret sharing based on the Chinese Remainder Theorem, Int. Netw. Secur., 2014, 16(6):420-425.
[5] Harn L and Miao F, Multilevel threshold secret sharing based on the Chinese Remainder Theorem, Inf. Process. Lett., 2014, 114(9):504-509.
[6] Liu Y, Harn L, and Chang C C, A novel verifiable secret sharing mechanism using theory of numbers and a method for sharing secrets, Int. J. Commun. Syst., 2015, 28(7):1282-1292.
[7] Blakley G R and Meadows C, Security of ramp schemes, Eds. by Blakley G R, Chaum D. Advances in Cryptology-CRYPTO 1984, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 1985, 196:242-268.
[8] Huang W, Langberg M, Kliewer J, et al., Communication efficient secret sharing, IEEE Trans. Inf. Theory, 2016, 62(12):7195-7206.
[9] Ning Y, Miao F, Huang W, et al., Constructing ideal secret sharing schemes based on Chinese Remainder Theorem, Eds. by Peyrin T, Galbraith S. Advances in Cryptology-ASIACRYPT 2018, Lecture Notes in Computer Science, Springer, Cham, 2018, 11274:310-331.
[10] Martin K M, Pieprzyk J, Safavi-Naini R, et al., Changing thresholds in the absence of secure channels, Information Security and Privacy, ACISP 1999, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 1999, 1587:177-191.
[11] Wang H and Wong D S, On secret reconstruction in secret sharing schemes, IEEE Trans. Inf. Theory, 2008, 54(1):473-480.
[12] Zhang Z, Chee Y M, Ling S, et al., Threshold changeable secret sharing schemes revisited, Theor. Compu. Sci., 2012, 418:106-115.
[13] Bitar R and Rouayheb S E, Staircase codes for secret sharing with optimal communication and read overheads, IEEE Trans. Inf. Theory, 2018, 64(6):4191-4206.
[14] Lin F, Ling S, Wang H, et al., Threshold changeable ramp secret sharing, Eds. by Mu Y, Deng R, Huang X. Cryptology and Network Security, CANS 2019, Lecture Notes in Computer Science, Springer, Cham, 2019, 11829:308-327.
[15] Steinfeld R, Pieprzyk J, and Wang H, Lattice-based threshold-changeability for standard crt secret-sharing schemes, Finite Fields Their Appl., 2006, 12(4):653-680.
[16] Steinfeld R, Pieprzyk J, and Wang H, Lattice-based threshold changeability for standard shamir secret-sharing schemes, IEEE Trans. Inf. Theory, 2007, 53(7):2542-2559.
[17] Ding J, Lin C, and Lin F, Optimal threshold changeable secret sharing with new threshold change range, Eds. by Nguyen K, et al., ProvSec 2020, LNCS, 2020, 12505:361-378.
[18] Harn L, Group authentication, IEEE Trans. Comput., 2013, 62(9):1893-1898.
[19] Harn L, Secure secret reconstruction and multi-secret sharing schemes with unconditional security, Security Comm. Networks, 2014, 7(3):567-573.
[20] Harn L and Hsu C F, Dynamic threshold secret reconstruction and its application to the threshold cryptography, Inf. Process. Lett., 2015, 115(11):851-857.
[21] Jamshidpour S and Ahmadian Z, Security analysis of a dynamic threshold secret sharing scheme using linear subspace method, Inf. Process. Lett., 2020, 163:105994.
[22] Ahmadian Z and Jamshidpour S, Linear subspace cryptanalysis of a secret sharing-based group authentication scheme, IEEE Trans. Inf. Forensics Secur., 2019, 13(2):502-510.
[23] Jia X, Wang D, Nie D, et al., A new threshold changeable secret sharing scheme based on the Chinese Remainder Theorem, Inf. Sci., 2019, 47:313-330.
[24] Lang S, Algebra, Graduate Texts in Mathematics, 3rd Ed., Springer, New York, vol. 211, 2002.
[25] Cohen H, A Course in Algorithmic Algebraic Number Theory, Springer, Heidelberg, vol. 138. 1993.
[26] Stinson D R, Cryptography, Theory and Practice, 3rd Ed., Chapman and Hall/CRC, Boca Raton, 2006.

[1]	SUN Yao,HUANG Zhenyu,LIN Dongdai,WANG Dingkang. On Implementing the Symbolic Preprocessing Function over Boolean Polynomial Rings in Gr¨obner Basis Algorithms Using Linear Algebra [J]. Journal of Systems Science and Complexity, 2016, 29(3): 789-804.

Viewed

Full text

Abstract