Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On Sigma-Protocols and (Packed) Black-Box Secret Sharing Schemes

  • Conference paper
  • First Online:
Public-Key Cryptography – PKC 2024 (PKC 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14602))

Included in the following conference series:

Abstract

\(\varSigma \)-protocols are a widely utilized, relatively simple and well understood type of zero-knowledge proofs. However, the well known Schnorr \(\varSigma \)-protocol for proving knowledge of discrete logarithm in a cyclic group of known prime order, and similar protocols working over this type of groups, are hard to generalize to dealing with other groups, in particular those of hidden order, due to the inability of the knowledge extractor to invert elements modulo the order.

In this paper, we introduce a universal construction of \(\varSigma \)-protocols designed to prove knowledge of preimages of group homomorphisms for any abelian finite group. In order to do this, we first establish a general construction of a \(\varSigma \)-protocol for \(\mathfrak {R}\)-module homomorphism given only a linear secret sharing scheme over the ring \(\mathfrak {R}\), where zero knowledge and special soundness can be related to the privacy and reconstruction properties of the secret sharing scheme. Then, we introduce a new construction of 2-out-of-n packed black-box secret sharing scheme capable of sharing k elements of an arbitrary (abelian, finite) group where each share consists of \(k+\log n-3\) group elements. From these two elements we obtain a generic “batch” \(\varSigma \)-protocol for proving knowledge of k preimages of elements via the same group homomorphism, which communicates \(k+\lambda -3\) elements of the group to achieve \(2^{-\lambda }\) knowledge error. For the case of class groups, we show that our \(\varSigma \)-protocol improves in several aspects on existing proofs for knowledge of discrete logarithm and other related statements that have been used in a number of works.

Finally, we extend our constructions from group homomorphisms to the case of ZK-ready functions, introduced by Cramer and Damgård in Crypto 09, which in particular include the case of proofs of knowledge of plaintext (and randomness) for some linearly homomorphic encryption schemes such as Joye-Libert encryption. However, in the case of Joye-Libert, we show a better alternative, using Shamir secret sharing over Galois rings, which achieves \(2^{-k}\) knowledge soundness by communicating k ciphertexts to prove k statements.

This work has been partially supported by the grant PIPF-2022/COM-25517, funded by the Madrid Regional Government, and by the projects SecuRing (PID2019-110873RJ-I00/MCIN/AEI/10.13039/501100011033), PRODIGY (TED2021-132464B-I00) funded by MCIN/AEI/10.13039/501100011033/ and the European Union NextGenerationEU/PRTR, and CONFIDENTIAL-6G funded by the European Union (GA 101096435). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Commission. Neither the European Union nor the European Commission can be held responsible for them.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 119.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 139.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Note \(\pmb {\overline{\lambda }}^{(i)}\cdot x_i\) denotes the coordinate-wise action of vector \(\pmb {\overline{\lambda }}^{(i)}\in \mathfrak {R}^{k+e}\) on the element \(x_i\in \mathfrak {M}_2\), that is, if \(\pmb {\overline{\lambda }}^{(i)}=(\overline{\lambda }^{(i)}_1,\dots ,\overline{\lambda }^{(i)}_{k+e})\), then \(\overline{\lambda }^{(i)}\cdot x_i=(\overline{\lambda }^{(i)}_1\cdot x_i,\dots ,\overline{\lambda }^{(i)}_{k+e}\cdot x_i)\).

  2. 2.

    The matrices have been found by first taking matrices \(N'_i\) representing multiplication by different elements of the fields \(\mathbb {F}_{2^k}\), which leads to \(\det (N'_i-N'_j)=1 \mod 2\), and then (for \(k=3\)) using brute force to fix the cases where \(\det (N'_i-N'_j)\ne \pm 1\).

  3. 3.

    We do point out that it may be worthwhile to investigate whether the techniques from Sect. 6.1 using Galois rings can be used to construct proofs of plaintext knowledge in that case.

  4. 4.

    e.g. \((2^l-1)+1=0\) in \(\mathbb {Z}_{2^l}\), but \(f(2^l-1,1)\cdot f(1,1)=g^{2^l}\ne f(0,1)\).

  5. 5.

    In the example of the previous footnote if \(u=2^l-1\), \(u'=1\), we would have \((u+u')_{\mathbb {Z}}=2^l\), so \(q(u,u')=1\) and \(\delta (u,u')=g\). Indeed \(f(2^l-1,1)\cdot f(1,1)=g^{2^l}=f(0,g)=f(0,1\cdot g)\).

References

  1. Abspoel, M., Cramer, R., Damgård, I., Escudero, D., Yuan, C.: Efficient information-theoretic secure multiparty computation over \(\mathbb{Z} /p^k\mathbb{Z} \) via galois rings. In: Hofheinz, D., Rosen, A. (eds.) TCC 2019, Part I. LNCS, vol. 11891, pp. 471–501. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-36030-6_19

    Chapter  Google Scholar 

  2. Attema, T., Cascudo, I., Cramer, R., Damgård, I., Escudero, D.: Vector commitments over rings and compressed \(\varSigma \)-protocols. In: Kiltz, E., Vaikuntanathan, V. (eds.) TCC 2022, Part I. LNCS, vol. 13747, pp. 173–202. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-22318-1_7

    Chapter  Google Scholar 

  3. Attema, T., Cramer, R.: Compressed \(\varSigma \)-protocol theory and practical application to plug & play secure algorithmics. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. Part III, volume 12172 of LNCS, pp. 513–543. Springer, Heidelberg (2020)

    Chapter  Google Scholar 

  4. Ball, M., Çakan, A., Malkin, T.: Linear threshold secret-sharing with binary reconstruction. In: Tessaro, S. (ed.) 2nd Conference on Information-Theoretic Cryptography, ITC 2021, July 23-26, 2021, Virtual Conference, LIPIcs, vol. 199, pp. 12:1–12:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

    Google Scholar 

  5. Bartoli, C., Cascudo, I.: On sigma-protocols and (packed) black-box secret sharing schemes. Cryptology ePrint Archive, Paper 2023/1652 (2023). https://eprint.iacr.org/2023/1652

  6. Bouvier, C., Castagnos, G., Imbert, L., Laguillaumie, F.: I want to ride my BICYCL : BICYCL implements cryptography in class groups. J. Cryptol. 36(3), 17 (2023)

    Article  MathSciNet  Google Scholar 

  7. Braun, L., Damgård, I., Orlandi, C.: Secure multiparty computation from threshold encryption based on class groups. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. LNCS, vol. 14081, pp. 613–645. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-38557-5_20

    Chapter  Google Scholar 

  8. 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, pp. 315–334. IEEE Computer Society Press (2018)

    Google Scholar 

  9. Castagnos, G., Catalano, D., Laguillaumie, F., Savasta, F., Tucker, I.: Two-party ECDSA from hash proof systems and efficient instantiations. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part III. LNCS, vol. 11694, pp. 191–221. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-26954-8_7

    Chapter  Google Scholar 

  10. Castagnos, G., Catalano, D., Laguillaumie, F., Savasta, F., Tucker, I.: Bandwidth-efficient threshold EC-DSA. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) PKC 2020, Part II. LNCS, vol. 12111, pp. 266–296. Springer, Heidelberg (2020). https://doi.org/10.1007/978-3-030-45388-6_10

    Chapter  Google Scholar 

  11. Castagnos, G., Laguillaumie, F.: Linearly homomorphic encryption from \(\sf DDH\). In: Nyberg, K. (ed.) CT-RSA 2015. LNCS, vol. 9048, pp. 487–505. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-16715-2_26

    Chapter  Google Scholar 

  12. Castagnos, G., Laguillaumie, F., Tucker, I.: Practical fully secure unrestricted inner product functional encryption modulo p. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11273, pp. 733–764. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03329-3_25

    Chapter  Google Scholar 

  13. Castagnos, G., Laguillaumie, F., Tucker, I.: Threshold linearly homomorphic encryption on \(\textbf{Z} /2^{k}\textbf{Z} \). In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022, Part II. LNCS, vol. 13792, pp. 99–129. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-22966-4_4

    Chapter  Google Scholar 

  14. Catalano, D., Di Raimondo, M., Fiore, D., Giacomelli, I.: Mon\(\mathbb{Z} _{2^{k}}\)a: fast maliciously secure two party computation on \(\mathbb{Z} _{2^{k}}\). In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) PKC 2020, Part II. LNCS, vol. 12111, pp. 357–386. Springer, Heidelberg (2020). https://doi.org/10.1007/978-3-030-45388-6_13

    Chapter  Google Scholar 

  15. Cramer, R., Damgård, I.: On the amortized complexity of zero-knowledge protocols. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 177–191. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_11

    Chapter  Google Scholar 

  16. Cramer, R., Damgård, I., Keller, M.: On the amortized complexity of zero-knowledge protocols. J. Cryptol. 27(2), 284–316 (2014)

    Article  MathSciNet  Google Scholar 

  17. Cramer, R., Fehr, S.: Optimal black-box secret sharing over arbitrary Abelian groups. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 272–287. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45708-9_18

    Chapter  Google Scholar 

  18. Cramer, R., Fehr, S., Stam, M.: Black-box secret sharing from primitive sets in algebraic number fields. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 344–360. Springer, Heidelberg (2005). https://doi.org/10.1007/11535218_21

    Chapter  Google Scholar 

  19. Cramer, R., Xing, C.: Blackbox secret sharing revisited: a coding-theoretic approach with application to expansionless near-threshold schemes. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 499–528. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45721-1_18

    Chapter  Google Scholar 

  20. Das, P., Jacobson, M.J., Scheidler, R.: Improved efficiency of a linearly homomorphic cryptosystem. In: Carlet, C., Guilley, S., Nitaj, A., Souidi, E.M. (eds.) C2SI 2019. LNCS, vol. 11445, pp. 349–368. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-16458-4_20

    Chapter  Google Scholar 

  21. Desmedt, Y., Frankel, Y.: Threshold cryptosystems. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 307–315. Springer, New York (1990). https://doi.org/10.1007/0-387-34805-0_28

    Chapter  Google Scholar 

  22. Franklin, M.K., Yung, M.: Communication complexity of secure computation (extended abstract). In: 24th ACM STOC, pp. 699–710. ACM Press (1992)

    Google Scholar 

  23. Gennaro, R., Leigh, D., Sundaram, R., Yerazunis, W.: Batching schnorr identification scheme with applications to privacy-preserving authorization and low-bandwidth communication devices. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 276–292. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30539-2_20

    Chapter  Google Scholar 

  24. Guillou, L.C., Quisquater, J.-J.: A “Paradoxical’’ Indentity-based signature scheme resulting from zero-knowledge. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 216–231. Springer, New York (1990). https://doi.org/10.1007/0-387-34799-2_16

    Chapter  Google Scholar 

  25. Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge proofs from secure multiparty computation. SIAM J. Comput. 39(3), 1121–1152 (2009)

    Article  MathSciNet  Google Scholar 

  26. Joye, M., Libert, B.: Efficient cryptosystems from \(2^k\)-th power residue symbols. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 76–92. Springer, Heidelberg (2013). https://doi.org/10.1007/s00145-016-9229-5

    Chapter  Google Scholar 

  27. Karchmer, M., Wigderson, A.: Characterizing non-deterministic circuit size. In: 25th ACM STOC, pp. 532–540. ACM Press (1993)

    Google Scholar 

  28. Karchmer, M., Wigderson, A.: On span programs. In: Proceedings of the Eight Annual Structure in Complexity Theory Conference, San Diego, CA, USA, May 18-21, 1993, pp. 102–111. IEEE Computer Society (1993)

    Google Scholar 

  29. Maurer, U.M.: Unifying zero-knowledge proofs of knowledge. In: Preneel, B. (ed.) AFRICACRYPT 2009. LNCS, vol. 5580, pp. 272–286. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02384-2_17

    Chapter  Google Scholar 

  30. Okamoto, T., Uchiyama, S.: A new public-key cryptosystem as secure as factoring. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 308–318. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054135

    Chapter  Google Scholar 

  31. 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_16

    Chapter  Google Scholar 

  32. Schnorr, C.P.: Efficient identification and signatures for smart cards. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 239–252. Springer, New York (1990). https://doi.org/10.1007/0-387-34805-0_22

    Chapter  Google Scholar 

  33. Xue, H.,et al.: Efficient multiplicative-to-additive function from Joye-Libert cryptosystem and its application to threshold ECDSA. Cryptology ePrint Archive, Paper 2023/1312 (2023). https://eprint.iacr.org/2023/1312. To appear in ACM CCS 23

  34. Zhang, M., Chen, Y., Yao, C., Wang, Z.: Sigma protocols from verifiable secret sharing and their applications. In: Guo, J., Steinfeld, R. (eds.) ASIACRYPT 2023. LNCS, pp. 208–242. Springer, Singapore (2023). https://doi.org/10.1007/978-981-99-8724-5_7

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IMDEA Software Institute, Madrid, Spain

    Claudia Bartoli & Ignacio Cascudo

  2. Universidad Politécnica de Madrid, Madrid, Spain

    Claudia Bartoli

Authors
  1. Claudia Bartoli
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ignacio Cascudo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Claudia Bartoli .

Editor information

Editors and Affiliations

  1. The University of Sydney, Sydney, NSW, Australia

    Qiang Tang

  2. The Australian National University, Acton, ACT, Australia

    Vanessa Teague

Rights and permissions

Reprints and permissions

Copyright information

© 2024 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Bartoli, C., Cascudo, I. (2024). On Sigma-Protocols and (Packed) Black-Box Secret Sharing Schemes. In: Tang, Q., Teague, V. (eds) Public-Key Cryptography – PKC 2024. PKC 2024. Lecture Notes in Computer Science, vol 14602. Springer, Cham. https://doi.org/10.1007/978-3-031-57722-2_14

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-57722-2_14

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-57721-5

  • Online ISBN: 978-3-031-57722-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation