1 Department of Applied Mathematics and Cryptography, Malek Ashtar University of Technology, Isfahan, Iran.

2 Department of Applied Mathematics and Cryptography, Malek Ashtar University of Technology.



A non-interactive (t,n)-publicly veri able secret sharing scheme (non-interactive (t,n)-PVSS scheme) is a (t,n)-secret sharing scheme in which anyone, not only the participants of the scheme, can verify the correctness of the produced shares without interacting with the dealer and participants. The (t,n)-PVSS schemes have found a lot of applications in cryptography because they are suitable for
real-life scenarios in which an external verifier is required to check the correctness of the produced shares without interacting with the dealer and participants. In this paper, we propose a non-interactive (t,n)-PVSS scheme using the non-homogeneous linear recursions (NHLRs), and prove its security with a formal method. We compare the computational complexity of our scheme with that of
Schoenmakers's scheme and show that our non-interactive (t,n)-PVSS scheme runs faster than Schoenmakers's scheme when n > 5 and n> t >(2n+9)/n. The communicational complexity of our scheme is almost equal to that of Schoenmakers's scheme.


[1] Bagher Bagherpour, Ali Zaghian and Mahdi Sajadieh, Sigma protocols for faster proof of simultaneous homomorphism relations, IET information security, pages 508–514, 2019.

[2] Norman L Biggs, Discrete Mathematics, revised ed, Oxford University Press, New York, 1989. [3] George R Blakley, Safeguarding cryptographic keys, International Workshop on Managing Requirements Knowledge, pages 313–317, 1979.

[4] David Chaum and Torben P Pedersen, Wallet databases with observers, In: Advances in Cryptology–CRYPTO ’92, Lecture Notes in Computer Science, vol. 740, pages 89–105, Springer, Berlin, 1992.

[5] Benny Chor, Shafi Goldwasser, Silvio Micali and Baruch Awerbuch, Verifiable secret sharing and achieving simultaneity in the presence of faults, FOCS’ 85, IEEE Computer Society, Washington, pages 383–395, 1985.

[6] Massoud H Dehkordi and Samaneh Mashhadi, New efficient and practical verifiable multi-secret sharing schemes, Information Science, 178, pages 2262–2274, 2008.

[7] Massoud H Dehkordi and Samaneh Mashhadi, An efficient threshold verifiable multi-secret sharing, Computer Standards and Interfaces, 30, pages 187–190, 2008.

[8] Paul Feldman, A practical scheme for noninteractive verifiable secret sharing, FOCS’ 87, IEEE computer society, Washington, pages 427– 437, 1987.

[9] Amos Fiat and Adi Shamir, How to prove yourself: practical solutions to identification and signature problems, Advances in Cryptology-CRYPTO’86, Lecture notes in compute science, 263, pages 186– 194, Springer, Berlin, 1986.

[10] Yuanju Gan, Lihua Wang, Ping Pan and Yixian Yang, publicly verifiable secret sharing scheme with provable security against chosen secret attacks, International journal of distributed sensor and networks, pages 1–9, 2013.

[11] Somayeh Heidarvand and Jorge L Villar, Public verifiability of pairings in secret sharing schemes, SAC 2008, pages 294–308, 2009.

[12] Amir Herzberg, Stanislaw Jarecki, Hugo Krawczyk and Moti Yung, Proactive secret sharing or How to cope with perpetual leakage, CRYPTO’95, LNCS 963, pages 339–359, Springer-Verlag, 1995.

[13] Chunqiang Hu, Xiaofeng Liao and Xiuzhen Cheng, Verifiable multi-secret sharing based on LFSR sequences, Theoretical Computer Science, 445, pages 52–62, 2012.

[14] Mahabir P Jhanwar, Ayineedi Venkateswarlu and Reihaneh Safavi-Naini, Paillier-based publicly verifiable (non-interactive) secret sharing, Designs, codes and Cryptography, 18 March 2014.

[15] Mahabir P Jhanwar, A practical (non-interactive) publicly verifiable secret sharing scheme, LNCS 6672, pages 273–287, 2011.

[16] Yanhong Liu, Futai Zhang and Jie Zhang, Attacks to some verifiable multi-secret sharing schemes and two improved schemes, Information Science, 329, pages 524–539, 2016.

[17] Samaneh Mashhadi, Secure publicly verifiable and proactive secret sharing schemes with general access structures, Information Science, 378, pages 99–108, 2017.

[18] Silvio Micali, Fair public-key cryptosystems, Advances in Cryptology-CRYPTO 1992, Lecture Notes in Computer Science, vol. 740, pages 113– 138, Springer, Berlin, 1993.

[19] Torben P Pedersen, Non-interactive and Information-Theoretic Secure Verifiable secret sharing, Advances in Cryptology-CRYPTO’91 , pages 129–140, 1992.

[20] Alexandre Ruiz and Jorge L Villar, Publicly verifiable secret sharing from paillier’s cryptosystem, WEWORC 2005, LNI p-74, pages 98–108, 2005.

[21] Adi Shamir, How to share a secret, Communications of the ACM, 22, pages 612–613. 1979.

[22] Berry Schoenmakers, A simple publicly verifiable secret sharing scheme and its application to electronic voting, Advances in CryptologyCRYPTO’99, Lecture Notes in Computer Science, pages 148–164, vol. 1666, Springer, Berlin, 1999.

[23] Jun Shao and Zhenfu Cao, A new efficient (t, n) verifiable multi-secret sharing scheme based on YCH scheme, Applied Mathematics and Computation, 168, pages 135–140, 2005. [24] Markus Stadler, Publicly verifiable secret sharing, Advances in Cryptology-EUROCRYPT’96, Lecture Notes in Computer Science, pages 190– 199, Springer, Berlin, 1996.

[25] Theodore M Wong, Chenxi Wang and Jeannette M Wing, Verifiable secret redistribution for archive systems, Proceedings of the first International IEEE security in storage workshop (SISW’02), 2003.

[26] Tsu Y Wu and Yuh M Tseng, A pairing-based publicly verifiable secret sharing scheme, Journal of Systems Science and Complexity, 24, pages 186–194, 2011.