nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Multi-key Homomorphic Signatures Unforgeable Under Insider Corruption

verfasst von : Russell W. F. Lai, Raymond K. H. Tai, Harry W. H. Wong, Sherman S. M. Chow

Erschienen in: Advances in Cryptology – ASIACRYPT 2018

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

Homomorphic signatures (HS) allows the derivation of the signature of the message-function pair (m, g), where \(m = g(m_1, \ldots , m_K)\), given the signatures of each of the input messages \(m_k\) signed under the same key. Multi-key HS (M-HS) introduced by Fiore et al. (ASIACRYPT’16) further enhances the utility by allowing evaluation of signatures under different keys. The unforgeability of existing M-HS notions assumes that all signers are honest. We consider a setting where an arbitrary number of signers can be corrupted, called unforgeability under corruption, which is typical for natural applications (e.g., verifiable multi-party computation) of M-HS. Surprisingly, there is a huge gap between M-HS (for arbitrary circuits) with and without unforgeability under corruption: While the latter can be constructed from standard lattice assumptions (ASIACRYPT’16), we show that the former likely relies on non-falsifiable assumptions. Specifically, we propose a generic construction of M-HS with unforgeability under corruption from zero-knowledge succinct non-interactive argument of knowledge (ZK-SNARK) (and other standard assumptions), and then show that such M-HS implies zero-knowledge succinct non-interactive arguments (ZK-SNARG). Our results leave open the pressing question of what level of authenticity and utility can be achieved in the presence of corrupt signers under standard assumptions.

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 Compact Multi-signatures for Smaller Blockchains

Nächstes Kapitel Attribute-Based Signatures for Unbounded Languages from Standard Assumptions

Nur mit Berechtigung zugänglich

Our definition differs from [29] in that \(\mathsf {Eval}\) takes previous labeled programs as input. The “recursive-proof”-style construction seems to make this unavoidable, as the evaluator needs to produce a proof for “I know some other proofs which satisfy some other statements”. These other statements (containing the previous programs) are part of the new statement to be proven. We are not aware of any SNARK in which the prover does not need to take the statement to be proven as input. Another plausible approach to avoid proving the possession of other proofs is that the evaluator “updates” the input proofs. However, “updatable” SNARK is not known to exist. In practice, an evaluator would naturally verify the input signatures before proceeding with evaluations. Since an evaluator is also a verifier, it would need to know the “history” (the previous labeled programs) of the input messages anyway.

Formally, a forgery would be certifying \((1, \mathcal {P}= (g, \tau _1,\ldots ,\tau _K))\) instead of (1, g).

To recover their definition in the multiple datasets setting, we need to add dataset identifiers to our definition. Since one can always include the dataset identifier in the label, and restrict a labeled program to be computed on inputs with the same dataset identifier, we just omit the dataset identifier in this paper.

Homomorphic encryption with targeted malleability [14] also used similar techniques.

Defined in this way, our scheme produces N \(\mathsf {crs} \)’s. We see two plausible approaches for just using one \(\mathsf {crs}\): (1) Define a single “über language” which captures all N languages, so we only have statements in one language to be proven. (2) If an “updatable” SNARK is available, the evaluator does not need to produce new proofs.

Function privacy of FS is very similar to zero-knowledge, except that the former is defined in “indistinguishability-style” while the latter is defined in “simulation-style”.

Ahn, J.H., Boneh, D., Camenisch, J., Hohenberger, S., Shelat, Waters, B.: Computing on authenticated data. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 1–20. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28914-9_1CrossRef

Asharov, G., Jain, A., López-Alt, A., Tromer, E., Vaikuntanathan, V., Wichs, D.: Multiparty computation with low communication, computation and interaction via threshold FHE. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 483–501. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_29CrossRef

Attrapadung, N., Libert, B., Peters, T.: Computing on authenticated data: new privacy definitions and constructions. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 367–385. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34961-4_23CrossRef

Attrapadung, N., Libert, B., Peters, T.: Efficient completely context-hiding quotable and linearly homomorphic signatures. In: Kurosawa and Hanaoka [42], pp. 386–404CrossRef

Backes, M., Dagdelen, Ö., Fischlin, M., Gajek, S., Meiser, S., Schröder, D.: Operational signature schemes. Cryptology ePrint Archive, Report 2014/820 (2014)

Backes, M., Meiser, S., Schröder, D.: Delegatable functional signatures. In: Cheng et al. [21], pp. 357–386

Bellare, M., Fuchsbauer, G.: Policy-based signatures. In: Krawczyk [41], pp. 520–537CrossRef

Bethencourt, J., Boneh, D., Waters, B.: Cryptographic methods for storing ballots on a voting machine. In: ISOC Network and Distributed System Security Symposium - NDSS 2007. The Internet Society, February/March 2007

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_5CrossRef

10.

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_10CrossRef

11.

Boneh, D., Freeman, D.M.: Linearly homomorphic signatures over binary fields and new tools for lattice-based signatures. In: Catalano et al. [18], pp. 1–16

12.

Boneh, D., et al.: Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits. In: Nguyen and Oswald [48], pp. 533–556CrossRef

13.

Boneh, D., Lewi, K., Montgomery, H., Raghunathan, A.: Key homomorphic PRFs and their applications. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 410–428. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_23CrossRef

14.

Boneh, D., Segev, G., Waters, B.: Targeted malleability: homomorphic encryption for restricted computations. In: Goldwasser, S. (ed.) ITCS 2012: 3rd Innovations in Theoretical Computer Science, pp. 350–366. Association for Computing Machinery, January 2012

15.

Boyen, X., Fan, X., Shi, E.: Adaptively secure fully homomorphic signatures based on lattices. Cryptology ePrint Archive, Report 2014/916 (2014)

16.

Boyle, E., Goldwasser, S., Ivan, I.: Functional signatures and pseudorandom functions. In: Krawczyk [41], pp. 501–519CrossRef

17.

Brakerski, Z., Kalai, Y.T.: A framework for efficient signatures, ring signatures and identity based encryption in the standard model. Cryptology ePrint Archive, Report 2010/086 (2010)

18.

Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.): PKC 2011. LNCS, vol. 6571. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19379-8CrossRefMATH

19.

Catalano, D., Fiore, D., Warinschi, B.: Efficient network coding signatures in the standard model. In: Fischlin et al. [31], pp. 680–696

20.

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_21CrossRef

21.

Cheng, C.-M., Chung, K.-M., Persiano, G., Yang, B.-Y. (eds.): PKC 2016. LNCS, vol. 9614. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49384-7CrossRefMATH

22.

Cheon, J.H., Takagi, T. (eds.): ASIACRYPT 2016. LNCS, vol. 10032. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6CrossRefMATH

23.

Chow, S.S.M.: Functional credentials for internet of things. In: Chow, R., Saldamli, G. (eds.) Proceedings of the 2nd ACM International Workshop on IoT Privacy, Trust, and Security, IoTPTS@AsiaCCS, Xi’an, China, 30 May 2016, p. 1. ACM (2016)

24.

Chow, S.S.M., Haralambiev, K.: Non-interactive confirmer signatures. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 49–64. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19074-2_4CrossRef

25.

Chow, S.S.M., Wei, V.K.W., Liu, J.K., Yuen, T.H.: Ring signatures without random oracles. In: Lin, F.C., Lee, D.T., Lin, B.S., Shieh, S., Jajodia, S. (eds.) ASIACCS 06: 1st ACM Symposium on Information, Computer and Communications Security, pp. 297–302. ACM Press, March 2006

26.

Danezis, G., Fournet, C., Groth, J., Kohlweiss, M.: Square span programs with applications to succinct NIZK arguments. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 532–550. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45611-8_28CrossRef

27.

Derler, D., Ramacher, S., Slamanig, D.: Homomorphic proxy re-authenticators and applications to verifiable multi-user data aggregation. In: Kiayias, A. (ed.) FC 2017. LNCS, vol. 10322, pp. 124–142. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70972-7_7CrossRef

28.

Derler, D., Slamanig, D.: Key-homomorphic signatures and applications to multiparty signatures and non-interactive zero-knowledge. Cryptology ePrint Archive, Report 2016/792 (2016)

29.

Fiore, D., Mitrokotsa, A., Nizzardo, L., Pagnin, E.: Multi-key homomorphic authenticators. In: Cheon and Takagi [22], pp. 499–530CrossRef

30.

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_5CrossRefMATH

31.

Fischlin, M., Buchmann, J., Manulis, M. (eds.): PKC 2012. LNCS, vol. 7293. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-30057-8CrossRefMATH

32.

Freeman, D.M.: Improved security for linearly homomorphic signatures: a generic framework. In: Fischlin et al. [31], pp. 697–714

33.

Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs and succinct NIZKs without PCPs. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 626–645. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_37CrossRef

34.

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_9CrossRef

35.

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_16CrossRef

36.

Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Fortnow, L., Vadhan, S.P. (eds.) 43rd Annual ACM Symposium on Theory of Computing, pp. 99–108. ACM Press, June 2011

37.

Gorbunov, S., Vaikuntanathan, V., Wichs, D.: Leveled fully homomorphic signatures from standard lattices. In: Servedio, R.A., Rubinfeld, R. (eds.) 47th Annual ACM Symposium on Theory of Computing, pp. 469–477. ACM Press, June 2015

38.

Groth, J.: On the size of pairing-based non-interactive arguments. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 305–326. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_11CrossRef

39.

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_17CrossRef

40.

Kiltz, E., Mityagin, A., Panjwani, S., Raghavan, B.: Append-only signatures. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 434–445. Springer, Heidelberg (2005). https://doi.org/10.1007/11523468_36CrossRef

41.

Krawczyk, H. (ed.): PKC 2014. LNCS, vol. 8383. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54631-0CrossRefMATH

42.

Kurosawa, K., Hanaoka, G. (eds.): PKC 2013. LNCS, vol. 7778. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36362-7CrossRefMATH

43.

Lamport, L.: Constructing digital signatures from a one-way function. Technical report SRI-CSL-98, SRI International Computer Science Laboratory, October 1979

44.

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_17CrossRef

45.

Libert, B., Peters, T., Joye, M., Yung, M.: Non-malleability from malleability: simulation-sound quasi-adaptive NIZK proofs and CCA2-secure encryption from homomorphic signatures. In: Nguyen and Oswald [48], pp. 514–532CrossRef

46.

Lipmaa, H.: Succinct non-interactive zero knowledge arguments from span programs and linear error-correcting codes. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013. LNCS, vol. 8269, pp. 41–60. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-42033-7_3CrossRef

47.

Micali, S.: Computationally sound proofs. SIAM J. Comput. 30(4), 1253–1298 (2000)MathSciNetCrossRef

48.

Nguyen, P.Q., Oswald, E. (eds.): EUROCRYPT 2014. LNCS, vol. 8441. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5CrossRef

49.

Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: 22nd Annual ACM Symposium on Theory of Computing, pp. 387–394. ACM Press, May 1990

50.

Steinfeld, R., Bull, L., Wang, H., Pieprzyk, J.: Universal designated-verifier signatures. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 523–542. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-40061-5_33CrossRef

Titel: Multi-key Homomorphic Signatures Unforgeable Under Insider Corruption
verfasst von: Russell W. F. Lai
Raymond K. H. Tai
Harry W. H. Wong
Sherman S. M. Chow
Verlag: Springer International Publishing
Buch: Advances in Cryptology – ASIACRYPT 2018
Print ISBN: 978-3-030-03328-6

Electronic ISBN: 978-3-030-03329-3

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-030-03329-3_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