Article

Commuting signatures and verifiable encryption

Author:

Georg FuchsbauerAuthors Info & Claims

EUROCRYPT'11: Proceedings of the 30th Annual international conference on Theory and applications of cryptographic techniques: advances in cryptology

Pages 224 - 245

Published: 15 May 2011 Publication History

Abstract

Verifiable encryption allows one to encrypt a signature while preserving its public verifiability. We introduce a new primitive called commuting signatures and verifiable encryption that extends this in multiple ways, such as enabling encryption of both signature and message while proving validity. More importantly, given a ciphertext, a signer can create a verifiably encrypted signature on the encrypted (unknown) message, which leads to the same result as first signing the message and then verifiably encrypting the message/signature pair; thus, signing and encrypting commute. Our instantiation is based on the recently introduced automorphic signatures and Groth-Sahai proofs, which we show to be homomorphic. We also prove a series of other properties and provide a novel approach to simulation.

As an application, we give an instantiation of delegatable anonymous credentials, a primitive introduced by Belenkiy et al. Our construction is arguably simpler than theirs and it is the first to provide non-interactive (and thus concurrently secure) issuing and delegation protocols, which are significantly more efficient. Moreover, the size of our credentials and the cost of verification are less than half of those of the previous instantiation. All our constructions are proven secure in the standard model under known non-interactive assumptions.

References

[1]

Abe, M., Fujisaki, E.: How to date blind signatures. In: Kim, K., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol. 1163, pp. 244-251. Springer, Heidelberg (1996).

Digital Library

[2]

Abe, M., Fuchsbauer, G., Groth, J., Haralambiev, K., Ohkubo, M.: Structure-Preserving Signatures and Commitments to Group Elements. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 209-236. Springer, Heidelberg (2010).

Digital Library

[3]

Boneh, D., Boyen, X.: Short signatures without random oracles. In: Cachin, C., Camenisch, J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 56-73. Springer, Heidelberg (2004).

[4]

Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41-55. Springer, Heidelberg (2004).

[5]

Belenkiy, M., Camenisch, J., Chase, M., Kohlweiss, M., Lysyanskaya, A., Shacham, H.: Randomizable proofs and delegatable anonymous credentials. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 108-125. Springer, Heidelberg (2009).

Digital Library

[6]

Belenkiy, M., Chase, M., Kohlweiss, M., Lysyanskaya, A.: P-signatures and noninteractive anonymous credentials. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 356-374. Springer, Heidelberg (2008).

Digital Library

[7]

Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications. In: STOC, pp. 103-112. ACM Press, New York (1988).

Digital Library

[8]

Blazy, O., Fuchsbauer, G., Pointcheval, D., Vergnaud, D.: Signatures on randomizable ciphertexts. In: Gennaro, R. (ed.) PKC 2011. LNCS, vol. 6571, pp. 403-422. Springer, Heidelberg (2011).

Digital Library

[9]

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).

Digital Library

[10]

Bellare, M., Hofheinz, D., Yilek, S.: Possibility and impossibility results for encryption and commitment secure under selective opening. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 1-35. Springer, Heidelberg (2009).

Digital Library

[11]

Brands, S.: Rethinking public key infrastructure and digital certificates--building privacy. PhD thesis, Eindhoven Inst. of Tech., The Netherlands (1999).

[12]

Boyen, X., Waters, B.: Full-domain subgroup hiding and constant-size group signatures. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 1-15. Springer, Heidelberg (2007).

Digital Library

[13]

Chaum, D.: Blind signatures for untraceable payments. In: Chaum, D., Rivest, R.L., Sherman, A.T. (eds.) CRYPTO 1982, pp. 199-203. Plenum Press, New York (1983).

[14]

Chaum, D.: Security without identification: Transaction systems to make big brother obsolete. Commun. ACM 28(10), 1030-1044 (1985).

Digital Library

[15]

Camenisch, J., Lysyanskaya, A.: An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 93-118. Springer, Heidelberg (2001).

Digital Library

[16]

Camenisch, J., Lysyanskaya, A.: A signature scheme with efficient protocols. In: Cimato, S., Galdi, C., Persiano, G. (eds.) SCN 2002. LNCS, vol. 2576, pp. 268-289. Springer, Heidelberg (2003).

Digital Library

[17]

Camenisch, J., Lysyanskaya, A.: Signature schemes and anonymous credentials from bilinear maps. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 56-72. Springer, Heidelberg (2004).

[18]

Chase, M., Lysyanskaya, A.: On signatures of knowledge. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 78-96. Springer, Heidelberg (2006).

Digital Library

[19]

Damgård, I.: Payment systems and credential mechanisms with provable security against abuse by individuals. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 328-335. Springer, Heidelberg (1990).

Digital Library

[20]

Dodis, Y., Haralambiev, K., López-Alt, A., Wichs, D.: Cryptography against continuous memory attacks. In: FOCS, pp. 511-520. IEEE Computer Society, Los Alamitos (2010).

Digital Library

[21]

Fischlin, M.: Round-optimal composable blind signatures in the common reference string model. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 60-77. Springer, Heidelberg (2006).

Digital Library

[22]

Fuchsbauer, G., Pointcheval, D.: Anonymous proxy signatures. In: Ostrovsky, R., De Prisco, R., Visconti, I. (eds.) SCN 2008. LNCS, vol. 5229, pp. 201-217. Springer, Heidelberg (2008).

Digital Library

[23]

Fuchsbauer, G., Pointcheval, D., Vergnaud, D.: Transferable constant-size fair E-cash. In: Garay, J.A., Miyaji, A., Otsuka, A. (eds.) CANS 2009. LNCS, vol. 5888, pp. 226-247. Springer, Heidelberg (2009).

Digital Library

[24]

Fuchsbauer, G.: Automorphic signatures in bilinear groups and an application to round-optimal blind signatures. Cryptology ePrint Archive, Report 2009/320 (2009), http://eprint.iacr.org/2009/320, an extended abstract appeared as part of {AFG+10}.

[25]

Fuchsbauer, G.: Commuting signatures and verifiable encryption and an application to non-interactively delegatable credentials. Cryptology ePrint Archive, Report 2010/233 (2010), http://eprint.iacr.org/2010/233

[26]

Groth, J., Ostrovsky, R., Sahai, A.: Perfect non-interactive zero knowledge for NP. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 339-358. Springer, Heidelberg (2006).

Digital Library

[27]

Galbraith, S.D., Paterson, K.G., Smart, N.P.: Pairings for cryptographers. Discrete Applied Mathematics 156(16), 3113-3121 (2008).

Digital Library

[28]

Groth, J., Sahai, A.: Efficient non-interactive proof systems for bilinear groups. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 415-432. Springer, Heidelberg (2008).

Digital Library

[29]

Lysyanskaya, A., Rivest, R.L., Sahai, A., Wolf, S.: Pseudonym systems. In: Heys, H.M., Adams, C.M. (eds.) SAC 1999. LNCS, vol. 1758, pp. 184-199. Springer, Heidelberg (2000).

Digital Library

[30]

Pointcheval, D., Stern, J.: Provably secure blind signature schemes. In: Kim, K., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol. 1163, pp. 252-265. Springer, Heidelberg (1996).

Digital Library

[31]

Rückert, M., Schröder, D.: Security of verifiably encrypted signatures and a construction without random oracles. In: Shacham, H., Waters, B. (eds.) Pairing 2009. LNCS, vol. 5671, pp. 17-34. Springer, Heidelberg (2009).

Digital Library

Cited By

Pussewalage HOleshchuk V(2019)An Anonymous Delegatable Attribute-based Credential Scheme for a Collaborative E-health EnvironmentACM Transactions on Internet Technology10.1145/333885419:3(1-22)Online publication date: 6-Sep-2019
https://dl.acm.org/doi/10.1145/3338854
Gritti CÖnen MMolva RHung CPapadopoulos G(2019)Privacy-preserving delegable authentication in the internet of thingsProceedings of the 34th ACM/SIGAPP Symposium on Applied Computing10.1145/3297280.3297365(861-869)Online publication date: 8-Apr-2019
https://dl.acm.org/doi/10.1145/3297280.3297365
Abe MGroth JKohlweiss MOhkubo MTibouchi M(2019)Efficient Fully Structure-Preserving Signatures and Shrinking CommitmentsJournal of Cryptology10.1007/s00145-018-9300-532:3(973-1025)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/s00145-018-9300-5
Show More Cited By

Commuting signatures and verifiable encryption
1. Security and privacy

Recommendations

Privacy-Enhancing Proxy Signatures from Non-interactive Anonymous Credentials
DBSec 2014: Proceedings of the 28th Annual IFIP WG 11.3 Working Conference on Data and Applications Security and Privacy XXVIII - Volume 8566

Proxy signatures enable an originator to delegate the signing rights for a restricted set of messages to a proxy. The proxy is then able to produce valid signatures only for messages from this delegated set on behalf of the originator. Recently, two ...
Certificate-based verifiably encrypted signatures from pairings

We propose a new verifiably encrypted signature scheme from pairings by choosing a certificate authority (CA) as an adjudicator. In this scheme, a certificate, or generally, a signature acts not only as the binding of the public key and its holder, but ...
Security Arguments for Digital Signatures and Blind Signatures

Since the appearance of public-key cryptography in the seminal Diffie--Hellman paper, many new schemes have been proposed and many have been broken. Thus, the simple fact that a cryptographic algorithm withstands cryptanalytic attacks for several years ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

EUROCRYPT'11: Proceedings of the 30th Annual international conference on Theory and applications of cryptographic techniques: advances in cryptology

May 2011

628 pages

ISBN:9783642204647

Editor:
Kenneth G. Paterson
Information Security Group, Royal Holloway, University of London, Egham, Surrey, UK

Sponsors

QI: Qualcomm Inc.
ERDF: The European Regional Development Fund
Guardtime: Guardtime
Swedbank: Swedbank

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 15 May 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pussewalage HOleshchuk V(2019)An Anonymous Delegatable Attribute-based Credential Scheme for a Collaborative E-health EnvironmentACM Transactions on Internet Technology10.1145/333885419:3(1-22)Online publication date: 6-Sep-2019
https://dl.acm.org/doi/10.1145/3338854
Gritti CÖnen MMolva RHung CPapadopoulos G(2019)Privacy-preserving delegable authentication in the internet of thingsProceedings of the 34th ACM/SIGAPP Symposium on Applied Computing10.1145/3297280.3297365(861-869)Online publication date: 8-Apr-2019
https://dl.acm.org/doi/10.1145/3297280.3297365
Abe MGroth JKohlweiss MOhkubo MTibouchi M(2019)Efficient Fully Structure-Preserving Signatures and Shrinking CommitmentsJournal of Cryptology10.1007/s00145-018-9300-532:3(973-1025)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/s00145-018-9300-5
Fuchsbauer GHanser CSlamanig D(2019)Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous CredentialsJournal of Cryptology10.1007/s00145-018-9281-432:2(498-546)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s00145-018-9281-4
Jutla CRoy A(2017)Improved Structure Preserving Signatures Under Standard Bilinear AssumptionsProceedings, Part II, of the 20th IACR International Conference on Public-Key Cryptography --- PKC 2017 - Volume 1017510.1007/978-3-662-54388-7_7(183-209)Online publication date: 28-Mar-2017
https://dl.acm.org/doi/10.1007/978-3-662-54388-7_7
Abe MChase MDavid BKohlweiss MNishimaki ROhkubo M(2016)Constant-Size Structure-Preserving SignaturesJournal of Cryptology10.1007/s00145-015-9211-729:4(833-878)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1007/s00145-015-9211-7
Abe MFuchsbauer GGroth JHaralambiev KOhkubo M(2016)Structure-Preserving Signatures and Commitments to Group ElementsJournal of Cryptology10.1007/s00145-014-9196-729:2(363-421)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1007/s00145-014-9196-7
Wang YZhang ZMatsuda THanaoka GTanaka K(2016)How to Obtain Fully Structure-Preserving Automorphic Signatures from Structure-Preserving OnesProceedings, Part II, of the 22nd International Conference on Advances in Cryptology --- ASIACRYPT 2016 - Volume 1003210.1007/978-3-662-53890-6_16(465-495)Online publication date: 4-Dec-2016
https://dl.acm.org/doi/10.1007/978-3-662-53890-6_16
Hofheinz D(2016)Algebraic PartitioningProceedings, Part I, of the 13th International Conference on Theory of Cryptography - Volume 956210.1007/978-3-662-49096-9_11(251-281)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.1007/978-3-662-49096-9_11
Ghadafi E(2016)Short Structure-Preserving SignaturesProceedings of the RSA Conference on Topics in Cryptology - CT-RSA 2016 - Volume 961010.1007/978-3-319-29485-8_18(305-321)Online publication date: 29-Feb-2016
https://dl.acm.org/doi/10.1007/978-3-319-29485-8_18
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents