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

Fully-Succinct Multi-key Homomorphic Signatures from Standard Assumptions

  • Conference paper
  • First Online:
Advances in Cryptology – CRYPTO 2024 (CRYPTO 2024)

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

Included in the following conference series:

  • 681 Accesses

Abstract

Multi-Key Homomorphic Signatures (MKHS) allow one to evaluate a function on data signed by distinct users while producing a succinct and publicly-verifiable certificate of the correctness of the result. All the constructions of MKHS in the state of the art achieve a weak level of succinctness where signatures are succinct in the total number of inputs but grow linearly with the number of users involved in the computation. The only exception is a SNARK-based construction which relies on a strong notion of knowledge soundness in the presence of signing oracles that not only requires non-falsifiable assumptions but also encounters some impossibility results.

In this work, we present the first construction of MKHS that are fully succinct (also with respect to the number of users) while achieving adaptive security under standard falsifiable assumptions. Our result is achieved through a novel combination of batch arguments for NP (BARGs) and functional commitments (FC), and yields diverse MKHS instantiations for circuits of unbounded depth based on either pairing or lattice assumptions. Additionally, our schemes support efficient verification with pre-processing, and they can easily be extended to achieve multi-hop evaluation and context-hiding.

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 109.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 79.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.

    HS may incorporate additional useful properties, such as amortized efficiency (enabling verification in time independent of the complexity of f, after preprocessing) and context-hiding (preventing the verifier to learn information on the inputs beyond the computation’s output); see Sect. 3 for more details.

  2. 2.

    The term \(\textsf{poly}(\lambda , m)\) appears since the \(\textsf{EffVer}\) algorithm needs to at least read the output \(\boldsymbol{y}\), that has length m.

  3. 3.

    We note that in some algebraic schemes, only the section of \(\textsf{aux}\) corresponding to the set S may be needed.

  4. 4.

    Though not formalized, this is the same notion used in the MKHS scheme of [17].

  5. 5.

    Precisely, we can build a CFC supporting a single input commitment; this is however enough in our application of composable MKHS.

  6. 6.

    In the same works, SECs are constructed from the same assumptions as a building block for BARGs.

References

  1. Aranha, D.F., Pagnin, E.: The simplest multi-key linearly homomorphic signature scheme. In: Schwabe, P., Thériault, N. (eds.) LATINCRYPT 2019. LNCS, vol. 11774, pp. 280–300. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-30530-7_14

    Chapter  Google Scholar 

  2. Attrapadung, N., Libert, B.: Homomorphic network coding signatures in the standard model. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 17–34. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19379-8_2

    Chapter  Google Scholar 

  3. Balbás, D., Catalano, D., Fiore, D., Lai, R.W.F.: Chainable functional commitments for unbounded-depth circuits. In: Rothblum, G., Wee, H. (eds.) Theory of Cryptography. TCC 2023. Lecture Notes in Computer Science, vol. 14371. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-48621-0_13

  4. Boneh, D., Freeman, D., Katz, J., Waters, B.: Signing a linear subspace: signature schemes for network coding. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 68–87. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00468-1_5

    Chapter  Google Scholar 

  5. Boneh, D., Freeman, D.M.: Homomorphic signatures for polynomial functions. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 149–168. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_10

    Chapter  Google Scholar 

  6. 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_26

    Chapter  Google Scholar 

  7. Catalano, D., Fiore, D.: Vector commitments and their applications. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 55–72. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36362-7_5

    Chapter  Google Scholar 

  8. Catalano, D., Fiore, D., Gennaro, R., Vamvourellis, K.: Algebraic (trapdoor) one-way functions and their applications. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 680–699. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_38

    Chapter  Google Scholar 

  9. Catalano, D., Fiore, D., Nizzardo, L.: Programmable hash functions go private: constructions and applications to (homomorphic) signatures with shorter public keys. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 254–274. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_13

    Chapter  Google Scholar 

  10. Catalano, D., Fiore, D., Tucker, I.: Additive-homomorphic functional commitments and applications to homomorphic signatures. In: Agrawal, S., Lin, D. (eds.) Advances in Cryptology – ASIACRYPT 2022. ASIACRYPT 2022, Part IV. LNCS, vol. 13794, pp. 159–188. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22972-5_6

  11. Catalano, D., Fiore, D., Warinschi, B.: Efficient network coding signatures in the standard model. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 680–696. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-30057-8_40

    Chapter  Google Scholar 

  12. Catalano, D., Fiore, D., Warinschi, B.: Homomorphic signatures with efficient verification for polynomial functions. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 371–389. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_21

    Chapter  Google Scholar 

  13. Choudhuri, A.R., Garg, S., Jain, A., Jin, Z., Zhang, J.: Correlation intractability and SNARGs from sub-exponential DDH. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology – CRYPTO 2023. CRYPTO 2023, Part IV. LNCS, vol. 14084, pp. 635–668. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-38551-3_20

  14. Choudhuri, A.R., Jain, A., Jin, Z.: Non-interactive Batch arguments for NP from standard assumptions. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12828, pp. 394–423. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84259-8_14

    Chapter  Google Scholar 

  15. Choudhuri, A.R., Jain, A., Jin, Z.: SNARGs for \(\cal{P}\) from LWE. In: 62nd FOCS, pp. 68–79. IEEE Computer Society Press (2022). https://doi.org/10.1109/FOCS52979.2021.00016

  16. Desmedt, Y.: Computer security by redefining what a computer is. In: NSPW (1993)

    Google Scholar 

  17. Fiore, D., Mitrokotsa, A., Nizzardo, L., Pagnin, E.: Multi-key homomorphic authenticators. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10032, pp. 499–530. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_17

    Chapter  Google Scholar 

  18. Fiore, D., Nitulescu, A.: On the (In)security of SNARKs in the presence of oracles. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9985, pp. 108–138. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53641-4_5

    Chapter  Google Scholar 

  19. Fiore, D., Pagnin, E.: Matrioska: a compiler for multi-key homomorphic signatures. In: Catalano, D., De Prisco, R. (eds.) SCN 2018. LNCS, vol. 11035, pp. 43–62. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98113-0_3

    Chapter  Google Scholar 

  20. Freeman, D.M.: Improved security for linearly homomorphic signatures: a generic framework. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 697–714. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-30057-8_41

    Chapter  Google Scholar 

  21. Gay, R., Ursu, B.: On Instantiating unleveled fully-homomorphic signatures from falsifiable assumptions. In: International Conference on Public Key Cryptography - PKC 2024 (2024), to appear

    Google Scholar 

  22. Gennaro, R., Katz, J., Krawczyk, H., Rabin, T.: Secure network coding over the integers. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 142–160. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13013-7_9

    Chapter  Google Scholar 

  23. Gennaro, R., Wichs, D.: Fully homomorphic message authenticators. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013. LNCS, vol. 8270, pp. 301–320. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-42045-0_16

    Chapter  Google Scholar 

  24. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) 41st ACM STOC, pp. 169–178. ACM Press (2009). https://doi.org/10.1145/1536414.1536440

  25. Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Fortnow, L., Vadhan, S.P. (eds.) 43rd ACM STOC, pp. 99–108. ACM Press (2011). https://doi.org/10.1145/1993636.1993651

  26. González, A., Zacharakis, A.: Fully-succinct publicly verifiable delegation from constant-size assumptions. In: Nissim, K., Waters, B. (eds.) TCC 2021. LNCS, vol. 13042, pp. 529–557. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-90459-3_18

    Chapter  Google Scholar 

  27. Gorbunov, S., Vaikuntanathan, V., Wichs, D.: Leveled fully homomorphic signatures from standard lattices. In: Servedio, R.A., Rubinfeld, R. (eds.) 47th ACM STOC, pp. 469–477. ACM Press (2015). https://doi.org/10.1145/2746539.2746576

  28. Hubacek, P., Wichs, D.: On the communication complexity of secure function evaluation with long output. In: Roughgarden, T. (ed.) ITCS 2015, pp. 163–172. ACM (2015). https://doi.org/10.1145/2688073.2688105

  29. Johnson, R., Molnar, D., Song, D., Wagner, D.: Homomorphic signature schemes. In: Preneel, B. (ed.) CT-RSA 2002. LNCS, vol. 2271, pp. 244–262. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45760-7_17

    Chapter  Google Scholar 

  30. Kalai, Y., Lombardi, A., Vaikuntanathan, V., Wichs, D.: Boosting batch arguments and ram delegation. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC), pp. 1545–1552. STOC 2023, Association for Computing Machinery, New York, NY, USA (2023). https://doi.org/10.1145/3564246.3585200

  31. Kalai, Y.T., Paneth, O., Yang, L.: How to delegate computations publicly. In: Charikar, M., Cohen, E. (eds.) 51st ACM STOC, pp. 1115–1124. ACM Press (2019). https://doi.org/10.1145/3313276.3316411

  32. Kalai, Y.T., Vaikuntanathan, V., Zhang, R.Y.: Somewhere statistical soundness, post-quantum security, and SNARGs. In: Nissim, K., Waters, B. (eds.) TCC 2021. LNCS, vol. 13042, pp. 330–368. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-90459-3_12

    Chapter  Google Scholar 

  33. Katsumata, S., Nishimaki, R., Yamada, S., Yamakawa, T.: Designated verifier/prover and preprocessing NIZKs from Diffie-Hellman assumptions. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 622–651. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_22

    Chapter  Google Scholar 

  34. Lai, R.W.F., Tai, R.K.H., Wong, H.W.H., Chow, S.S.M.: Multi-key homomorphic signatures unforgeable under insider corruption. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11273, pp. 465–492. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03329-3_16

    Chapter  Google Scholar 

  35. Libert, B., Peters, T., Joye, M., Yung, M.: Linearly homomorphic structure-preserving signatures and their applications. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 289–307. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_17

    Chapter  Google Scholar 

  36. Libert, B., Ramanna, S.C., Yung, M.: Functional commitment schemes: from polynomial commitments to pairing-based accumulators from simple assumptions. In: Chatzigiannakis, I., Mitzenmacher, M., Rabani, Y., Sangiorgi, D. (eds.) ICALP 2016. LIPIcs, vol. 55, pp. 30:1–30:14. Schloss Dagstuhl (2016). https://doi.org/10.4230/LIPIcs.ICALP.2016.30

  37. Okamoto, T., Pietrzak, K., Waters, B., Wichs, D.: New realizations of somewhere statistically binding hashing and positional accumulators. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 121–145. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48797-6_6

    Chapter  Google Scholar 

  38. Samarin, S.D., Fiore, D., Venturi, D., Amini, M.: A compiler for multi-key homomorphic signatures for turing machines. Theor. Comput. Sci. 889, 145–170 (2021). https://doi.org/10.1016/j.tcs.2021.08.002

    Article  MathSciNet  Google Scholar 

  39. Schabhüser, L., Butin, D., Buchmann, J.: Context hiding multi-key linearly homomorphic authenticators. In: Matsui, M. (ed.) CT-RSA 2019. LNCS, vol. 11405, pp. 493–513. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-12612-4_25

    Chapter  Google Scholar 

  40. Waters, B., Wu, D.J.: Batch arguments for NP and more from standard bilinear group assumptions. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology – CRYPTO 2022. CRYPTO 2022, Part II. LNCS, vol. 13508, pp. 433–463. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15979-4_15

  41. Wee, H., Wu, D.J.: Lattice-based functional commitments: Fast verification and cryptanalysis. In: Guo, J., Steinfeld, R. (eds.) ASIACRYPT 2023, Part V. LNCS, vol. 14442, pp. 201–235. Springer, Singapore (2023). https://doi.org/10.1007/978-981-99-8733-7_7

  42. Wee, H., Wu, D.J.: Succinct Functional Commitments for Circuits from k-Lin. In: Joye, M., Leander, G. (eds.) Advances in Cryptology – EUROCRYPT 2024. EUROCRYPT 2024. LNCS, pp. 280–310. Springer, Cham (2024). https://doi.org/10.1007/978-3-031-58723-8_10

Download references

Acknowledgements

This work is supported by the PICOCRYPT project that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101001283), partially supported by projects PRODIGY (TED2021-132464B-I00) and ESPADA (PID2022-142290OB-I00) funded by MCIN/AEI/10.13039/501100011033/ and the European Union NextGenerationEU / PRTR, and partially funded by Ministerio de Universidades (FPU21/00600).

Author information

Authors and Affiliations

  1. IMDEA Software Institute, Madrid, Spain

    Gaspard Anthoine, David Balbás & Dario Fiore

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

    Gaspard Anthoine & David Balbás

Authors
  1. Gaspard Anthoine
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. David Balbás
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dario Fiore
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Gaspard Anthoine .

Editor information

Editors and Affiliations

  1. Boston University, Boston, MA, USA

    Leonid Reyzin

  2. University of Waterloo, Waterloo, ON, Canada

    Douglas Stebila

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

Anthoine, G., Balbás, D., Fiore, D. (2024). Fully-Succinct Multi-key Homomorphic Signatures from Standard Assumptions. In: Reyzin, L., Stebila, D. (eds) Advances in Cryptology – CRYPTO 2024. CRYPTO 2024. Lecture Notes in Computer Science, vol 14922. Springer, Cham. https://doi.org/10.1007/978-3-031-68382-4_10

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-68382-4_10

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-68381-7

  • Online ISBN: 978-3-031-68382-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation