nach oben

Erschienen in:

2022 | OriginalPaper | Buchkapitel

Practical Non-interactive Publicly Verifiable Secret Sharing with Thousands of Parties

verfasst von : Craig Gentry, Shai Halevi, Vadim Lyubashevsky

Erschienen in: Advances in Cryptology – EUROCRYPT 2022

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Non-interactive publicly verifiable secret sharing (PVSS) schemes enables (re-)sharing of secrets in a decentralized setting in the presence of malicious parties. A recently proposed application of PVSS schemes is to enable permissionless proof-of-stake blockchains to “keep a secret” via a sequence of committees that share that secret. These committees can use the secret to produce signatures on the blockchain’s behalf, or to disclose hidden data conditioned on consensus that some event has occurred. That application needs very large committees with thousands of parties, so the PVSS scheme in use must be efficient enough to support such large committees, in terms of both computation and communication. Yet, previous PVSS schemes have large proofs and/or require many exponentiations over large groups.

We present a non-interactive PVSS scheme in which the underlying encryption scheme is based on the learning with errors (LWE) problem. While lattice-based encryption schemes are very fast, they often have long ciphertexts and public keys. We use the following two techniques to conserve bandwidth: First, we adapt the Peikert-Vaikuntanathan-Waters (PVW) encryption scheme to the multi-receiver setting, so that the bulk of the parties’ keys is a common random string. The resulting scheme yields \(\varOmega (1)\) amortized plaintext/ciphertext rate, where concretely the rate is \(\approx 1/60\) for 100 parties, \(\approx 1/8\) for 1000 parties, and approaching 1/2 as the number of parties grows. Second, we use bulletproofs over a DL-group of order about 256 bits to get compact proofs of correct encryption/decryption of shares.

Alternating between the lattice and DL settings is relatively painless, as we equate the LWE modulus with the order of the group. We also show how to reduce the the number of exponentiations in the bulletproofs by applying Johnson-Lindenstrauss-like compression to reduce the dimension of the vectors whose properties must be verified.

An implementation of our PVSS with 1000 parties showed that it is feasible even at that size, and should remain so even with one or two order of magnitude increase in the committee size.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Secure Multiparty Computation with Sublinear Preprocessing

Nächstes Kapitel Sine Series Approximation of the Mod Function for Bootstrapping of Approximate HE

Clearly such schemes must rely on some form of PKI.

The implementation should also support committees that are one or two orders of magnitude larger, with only a mild increase in runtime.

In earlier work, Fouque and Stern [20] informally present a somewhat similar scheme.

Lindell et al. also constructed a scheme that avoids Paillier, but with much higher bandwidth.

Of course, this statement refers to basic, possibly additively homomorphic lattice-based encryption schemes, not fully homomorphic encryption.

Despite being compact, bulletproofs have linear verification complexity. The Dory scheme [35] is similar to bulletproofs, but with logarithmic verification complexity.

In the real scheme, each user creates several such vectors, but we defer this discussion to the body of the paper.

For convenience, we have described the system as having only k members total, but consecutive k-member committees could be non-overlapping subsets of a larger set of parties.

Unlike the more standard LWE encryption in which the message also needs to be small, we use a version of the scheme implicit in [27] where the messages can be arbitrarily large in \(\mathbb {Z}_q\), but the length of \(\vec m\) has to increase to encode all of the message. We describe this in Sect. 2.2.

There are concrete bounds for tails of some of these distributions (e.g. [1]), but they are asymptotic and are looser than necessary for our concrete parameters.

The reason that this encoding method is better for us, is that it allows us to work only with \(\mathbb {Z}_q\) elements. In other variants of Regev encryption one usually must work with both \(\mathbb {Z}_q\) and \(\mathbb {Z}_p\) for some \(p\ll q\).

Up to a distance negligible in \(\kappa \).

The adversary sends not only B but also S, E to the challenger, since in our protocol it will have to prove knowledge of these matrices so they can be extracted from it.

See Sect. 3.1 for the reason for the offset vectors.

The \(\chi ^2\) distribution with k degrees of freedom is the distribution of \(\sum \limits _{i=1}^k x_i^2\) where \(x_i\leftarrow \mathcal {N}\).

More generally, to show that \(x\in [a,b]\) it is sufficient to show that \((x-a)(b-x)\) is non-negative.

Jumping ahead, in our setting we have \(b^*>2^{104}\) and \(d=256\), so we can handle bounds up to \(b\approx 2^{190}\). The bounds that we actually need to prove will all be much much smaller.

In our setting we have \(b_*>2^{90}\), so the term \(\frac{2}{\sqrt{b_*}}\) is insignificant.

Achlioptas, D.: Database-friendly random projections: Johnson-lindenstrauss with binary coins. J. Comput. Syst. Sci. 66(4), 671–687 (2003). https://doi.org/10.1016/S0022-0000(03)00025-4, special Issue on PODS 2001

Agrawal, S., Stehlé, D., Yadav, A.: Towards practical and round-optimal lattice-based threshold and blind signatures. IACR Cryptol. ePrint Arch. 2021, 381 (2021). https://eprint.iacr.org/2021/381

Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. 9, 169–203 (2015). https://doi.org/10.1515/jmc-2015-0016, https://bitbucket.org/malb/lwe-estimator/src/master/

Bai, S., Lepoint, T., Roux-Langlois, A., Sakzad, A., Stehlé, D., Steinfeld, R.: Improved security proofs in lattice-based cryptography: using the Rényi divergence rather than the statistical distance. J. Cryptol. 31(2), 610–640 (2017). https://doi.org/10.1007/s00145-017-9265-9CrossRefMATH

Baum, C., Damgård, I., Larsen, K.G., Nielsen, M.: How to prove knowledge of small secrets. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 478–498. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53015-3_17CrossRef

Baum, C., Lyubashevsky, V.: Simple amortized proofs of shortness for linear relations over polynomial rings. IACR Cryptol. ePrint Arch, p. 759 (2017)

Benhamouda, F., et al.: Can a public blockchain keep a secret? In: TCC (2020). https://eprint.iacr.org/2020/464. https://doi.org/10.1007/978-3-030-64375-1_10

Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiably encrypted signatures from bilinear maps. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 416–432. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_26CrossRef

Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. In: International conference on the theory and application of cryptology and information security, pp. 514–532. Springer (2001). https://doi.org/10.1007/s00145-004-0314-9

10.

Bootle, J., Chiesa, A., Sotiraki, K.: Sumcheck arguments and their applications. In: Advances in Cryptology – CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part I, 742–773 (2021). https://doi.org/10.1007/978-3-030-84242-0_26

11.

Boudot, F., Traoré, J.: Efficient publicly verifiable secret sharing schemes with fast or delayed recovery. In: Varadharajan, V., Mu, Y. (eds.) ICICS 1999. LNCS, vol. 1726, pp. 87–102. Springer, Heidelberg (1999). https://doi.org/10.1007/978-3-540-47942-0_8CrossRef

12.

Brakerski, Z., Döttling, N., Garg, S., Malavolta, G.: Leveraging linear decryption: rate-1 fully-homomorphic encryption and time-lock puzzles. In: Hofheinz, D., Rosen, A. (eds.) TCC 2019. LNCS, vol. 11892, pp. 407–437. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-36033-7_16CrossRef

13.

Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: 2018 IEEE Symposium on Security and Privacy, SP 2018, Proceedings, 21–23 May 2018, San Francisco, California, USA, pp. 315–334. IEEE Computer Society (2018). https://doi.org/10.1109/SP.2018.00020

14.

Camenisch, J., Shoup, V.: Practical verifiable encryption and decryption of discrete logarithms. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 126–144. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_8CrossRef

15.

Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: 34th ACM STOC, pp. 494–503. ACM Press, May 2002. https://doi.org/10.1145/509907.509980

16.

Chor, B., Goldwasser, S., Micali, S., Awerbuch, B.: Verifiable secret sharing and achieving simultaneity in the presence of faults. In: 26th Annual Symposium on Foundations of Computer Science (SFCS 1985), pp. 383–395. IEEE (1985)

17.

Costa, N., Martínez, R., Morillo, P.: Proof of a shuffle for lattice-based cryptography. In: Lipmaa, H., Mitrokotsa, A., Matulevičius, R. (eds.) NordSec 2017. LNCS, vol. 10674, pp. 280–296. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70290-2_17CrossRef

18.

del Pino, R., Lyubashevsky, V.: Amortization with fewer equations for proving knowledge of small secrets. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10403, pp. 365–394. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63697-9_13CrossRef

19.

D’Souza, R., Jao, D., Mironov, I., Pandey, O.: Publicly verifiable secret sharing for cloud-based key management. In: Bernstein, D.J., Chatterjee, S. (eds.) INDOCRYPT 2011. LNCS, vol. 7107, pp. 290–309. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25578-6_21CrossRef

20.

Fouque, P.-A., Stern, J.: One round threshold discrete-log key generation without private channels. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 300–316. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44586-2_22CrossRefMATH

21.

Fuchsbauer, G.: Commuting signatures and verifiable encryption. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 224–245. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_14CrossRef

22.

Fujisaki, E., Okamoto, T.: A practical and provably secure scheme for publicly verifiable secret sharing and its applications. In: International Conference on the Theory and Applications of Cryptographic Techniques, pp. 32–46. Springer (1998). https://doi.org/10.1007/BFb0054115

23.

Gennaro, R., Goldfeder, S.: Fast multiparty threshold ECDSA with fast trustless setup. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 1179–1194 (2018)

24.

Gentry, C., Halevi, S.: Compressible FHE with applications to PIR. In: Hofheinz, D., Rosen, A. (eds.) TCC 2019. LNCS, vol. 11892, pp. 438–464. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-36033-7_17CrossRef

25.

Gentry, C., Halevi, S., Lyubashevsky, V.: Practical non-interactive publicly verifiable secret sharing with thousands of parties. https://eprint.iacr.org/2021/1397 (2021)

26.

Gentry, C., Halevi, S., Magri, B., Nielsen, J.B., Yakoubov, S.: Random-index PIR and applications. In: Nissim, K., Waters, B. (eds.) Theory of Cryptography. TCC 2021. LNCS, vol. 13044. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-90456-2_2

27.

Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti, R., Garay, J.A. (eds.) Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, 18–22 August 2013, Santa Barbara, CA, USA. Proceedings, Part I. Lecture Notes in Computer Science, vol. 8042, pp. 75–92. Springer (2013). https://doi.org/10.1007/978-3-642-40041-4_5

28.

Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in np have zero-knowledge proof systems. J. ACM (JACM) 38(3), 690–728 (1991)MathSciNetCrossRef

29.

Groth, J.: On the size of pairing-based non-interactive arguments. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 305–326. Springer (2016). https://doi.org/10.1007/978-3-662-49896-5_11

30.

Groth, J.: Applied crypto: introducing noninteractive distributed key generation (2021). https://medium.com/dfinity/applied-crypto-one-public-key-for-the-internet-computer-ni-dkg-4af800db869d

31.

Groth, J.: Non-interactive distributed key generation and key resharing. Cryptology ePrint Archive, Report 2021/339 (2021). https://eprint.iacr.org/2021/339

32.

Heidarvand, S., Villar, J.L.: Public verifiability from pairings in secret sharing schemes. In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) SAC 2008. LNCS, vol. 5381, pp. 294–308. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04159-4_19CrossRefMATH

33.

Jhanwar, M.P., Venkateswarlu, A., Safavi-Naini, R.: Paillier-based publicly verifiable (non-interactive) secret sharing. Des. Codes Cryptograph. 73(2), 529–546 (2014). https://doi.org/10.1007/s10623-014-9952-6MathSciNetCrossRefMATH

34.

Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space 26. Contemporary mathematics 26 (1984)

35.

Lee, J.: Dory: efficient, transparent arguments for generalised inner products and polynomial commitments. In: Nissim, K., Waters, B. (eds.) Theory of Cryptography. TCC 2021. LNCS, vol. 13043. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-90453-1_1

36.

Libert, B., Ling, S., Mouhartem, F., Nguyen, K., Wang, H.: Zero-knowledge arguments for matrix-vector relations and lattice-based group encryption. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 101–131. Springer (2016). https://doi.org/10.1007/978-3-662-53890-6_4

37.

Lindell, Y., Nof, A.: Fast secure multiparty ECDSA with practical distributed key generation and applications to cryptocurrency custody. In: ACM CCS 18, pp. 1837–1854. ACM Press (2018). https://doi.org/10.1145/3243734.3243788

38.

Lyubashevsky, V.: Lattice-based identification schemes secure under active attacks. In: Cramer, R. (ed.) PKC 2008. LNCS, vol. 4939, pp. 162–179. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78440-1_10CrossRef

39.

Lyubashevsky, V.: Fiat-Shamir with aborts: applications to lattice and factoring-based signatures. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 598–616. Springer, Heidelberg, December 2009. https://doi.org/10.1007/978-3-642-10366-7_35

40.

Lyubashevsky, V.: Basic lattice cryptography: encryption and Fiat-Shamir signatures. https://www.tinyurl.com/latticesurvey. Accessed Apr 2021 (2020)

41.

Lyubashevsky, V., Nguyen, N.K., Seiler, G.: Practical lattice-based zero-knowledge proofs for integer relations. In: CCS, pp. 1051–1070. ACM (2020). https://doi.org/10.1145/3372297.3417894

42.

Lyubashevsky, V., Nguyen, N.K., Seiler, G.: Shorter lattice-based zero-knowledge proofs via one-time commitments. In: Garay, J.A. (ed.) Public-Key Cryptography - PKC 2021, Part I. Lecture Notes in Computer Science, vol. 12710, pp. 215–241. Springer (2021). https://doi.org/10.1007/978-3-030-75245-3_9

43.

Melchor, C.A., Barrier, J., Fousse, L., Killijian, M.O.: XPIR: private information retrieval for everyone. Proc. Privacy Enhancing Technol. 2016, 155–174 (2016)CrossRef

44.

Olumofin, F., Goldberg, I.: Revisiting the computational practicality of private information retrieval. In: Danezis, G. (ed.) FC 2011. LNCS, vol. 7035, pp. 158–172. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-27576-0_13CrossRef

45.

Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_16CrossRef

46.

Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. In: 2013 IEEE Symposium on Security and Privacy, pp. 238–252. IEEE (2013). https://doi.org/10.1109/SP.2013.47

47.

Peikert, C., Vaikuntanathan, V., Waters, B.: A framework for efficient and composable oblivious transfer. In: Wagner, D.A. (ed.) Advances in Cryptology - CRYPTO 2008, 28th Annual International Cryptology Conference, Santa Barbara, CA, USA, 17–21 August 2008. Proceedings. Lecture Notes in Computer Science, vol. 5157, pp. 554–571. Springer (2008). https://doi.org/10.1007/978-3-540-85174-5_31

48.

Rambaud, M., Urban, A.: Almost-asynchronous MPC under honest majority, revisited. IACR Cryptol. ePrint Arch. 2021, 503 (2021)

49.

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 34:1–34:40 (2009). http://doi.acm.org/10.1145/1568318.1568324

50.

Reyzin, L., Smith, A., Yakoubov, S.: Turning hate into love: compact homomorphic ad hoc threshold encryption for scalable MPC. In: International Symposium on Cyber Security Cryptography and Machine Learning, pp. 361–378. Springer (2021). https://doi.org/10.1007/978-3-030-78086-9_27

51.

Ruiz, A., Villar, J.L.: Publicly verifiable secret sharing from Paillier’s cryptosystem. In: WEWoRC 2005-Western European Workshop on Research in Cryptology. Gesellschaft für Informatik eV (2005)

52.

Schoenmakers, B.: A simple publicly verifiable secret sharing scheme and its application to electronic voting. In: Annual International Cryptology Conference, pp. 148–164. Springer (1999). https://doi.org/10.1007/3-540-48405-1_10

53.

Sion, R., Carbunar, B.: On the computational practicality of private information retrieval. In: Proceedings of the Network and Distributed Systems Security Symposium, pp. 2006–06. Internet Society (2007)

54.

Stadler, M.: Publicly verifiable secret sharing. In: Advances in Cryptology - EUROCRYPT ’96, International Conference on the Theory and Application of Cryptographic Techniques, 12–16 May 1996, Saragossa, Spain, Proceeding. Lecture Notes in Computer Science, vol. 1070, pp. 190–199. Springer (1996). https://doi.org/10.1007/3-540-68339-9_17

55.

Wu, T.Y., Tseng, Y.M.: A pairing-based publicly verifiable secret sharing scheme. J. Syst. Sci. Complex. 24(1), 186–194 (2011)MathSciNetCrossRef

56.

Young, A., Yung, M.: A PVSS as hard as discrete log and shareholder separability. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 287–299. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44586-2_21CrossRef

Titel: Practical Non-interactive Publicly Verifiable Secret Sharing with Thousands of Parties
verfasst von: Craig Gentry
Shai Halevi
Vadim Lyubashevsky
Verlag: Springer International Publishing
Buch: Advances in Cryptology – EUROCRYPT 2022
Print ISBN: 978-3-031-06943-7

Electronic ISBN: 978-3-031-06944-4

Copyright-Jahr: 2022
DOI: https://doi.org/10.1007/978-3-031-06944-4_16

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner