Verifiably encrypted signatures: security revisited and a new construction. (English) Zbl 1504.94212

Pernul, Günther (ed.) et al., Computer security – ESORICS 2015. 20th European symposium on research in computer security, Vienna, Austria, September 21–25, 2015. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 9326, 146-164 (2015).
Summary: In structure-preserving signatures on equivalence classes (SPS-EQ-\( \mathcal{R}\)), introduced in [C. Hanser and D. Slamanig, Lect. Notes Comput. Sci. 8873, 491–511 (2014; Zbl 1306.94060)], each message \(M\) in \((\mathbb{G}^\ast)^\ell\) is associated to its projective equivalence class, and a signature commits to the equivalence class: anybody can transfer the signature to a new, scaled, representative.
In this work, we give the first black-box construction of a public-key encryption scheme from any SPS-EQ-\( \mathcal{R}\) satisfying a simple new property which we call perfect composition. The construction does notinvolve any non-black-box technique and the implication is that such SPS-EQ-\( \mathcal{R}\) cannot be constructed from one-way functions in a black-box way. The main idea of our scheme is to build a verifiable encrypted signature (VES) first and then apply the general transformation suggested by T. Calderon et al. [ibid. 8366, 349–366 (2014; Zbl 1290.94146)].
The original definition of VES requires that the underlying signature scheme be correct and secure in addition to other security properties. The latter have been extended in subsequent literature, but the former requirements have sometimes been neglected, leaving a hole in the security notion. We show that Calderon et al.’s notion of resolution independence fills this gap.
For the entire collection see [Zbl 1492.68028].


94A62 Authentication, digital signatures and secret sharing
94A60 Cryptography
Full Text: DOI


[1] Abe, M.; Fuchsbauer, G.; Groth, J.; Haralambiev, K.; Ohkubo, M.; Rabin, T., Structure-preserving signatures and commitments to group elements, Advances in Cryptology - CRYPTO 2010, 209-236, 2010, Heidelberg: Springer, Heidelberg · Zbl 1280.94102 · doi:10.1007/978-3-642-14623-7_12
[2] Barreto, PSLM; Naehrig, M.; Preneel, B.; Tavares, S., Pairing-friendly elliptic curves of prime order, Selected Areas in Cryptography, 319-331, 2006, Heidelberg: Springer, Heidelberg · Zbl 1151.94479 · doi:10.1007/11693383_22
[3] Boneh, D.; Gentry, C.; Lynn, B.; Shacham, H.; Biham, E., Aggregate and verifiably encrypted signatures from bilinear maps, Advances in Cryptology - EUROCRPYT 2003, 416-432, 2003, Heidelberg: Springer, Heidelberg · Zbl 1038.94553 · doi:10.1007/3-540-39200-9_26
[4] Boneh, D., Papakonstantinou, P.A., Rackoff, C., Vahlis, Y., Waters, B.: On the impossibility of basing identity based encryption on trapdoor permutations. In: 49th FOCS, pp. 283-292. IEEE Computer Society Press, Philadelphia, 25-28 October 2008
[5] Calderon, T.; Meiklejohn, S.; Shacham, H.; Waters, B.; Benaloh, J., Rethinking verifiably encrypted signatures: a gap in functionality and potential solutions, Topics in Cryptology - CT-RSA 2014, 349-366, 2014, Heidelberg: Springer, Heidelberg · Zbl 1290.94146 · doi:10.1007/978-3-319-04852-9_18
[6] Camenisch, JL; Lysyanskaya, A.; Yung, M., Dynamic accumulators and application to efficient revocation of anonymous credentials, Advances in Cryptology - CRYPTO 2002, 61, 2002, Heidelberg: Springer, Heidelberg · Zbl 1026.94545 · doi:10.1007/3-540-45708-9_5
[7] Chatterjee, S.; Menezes, A., On cryptographic protocols employing asymmetric pairings - the role of \(\psi\) revisited, Discrete Appl. Math., 159, 13, 1311-1322, 2011 · Zbl 1250.94031 · doi:10.1016/j.dam.2011.04.021
[8] Fuchsbauer, G.; Paterson, KG, Commuting signatures and verifiable encryption, Advances in Cryptology - EUROCRYPT 2011, 224-245, 2011, Heidelberg: Springer, Heidelberg · Zbl 1281.94079 · doi:10.1007/978-3-642-20465-4_14
[9] Fuchsbauer, G., Hanser, C., Slamanig, D.: EUF-CMA-secure structure-preserving signatures on equivalence classes. Cryptology ePrint Archive, Report 2014/944 (2014). http://eprint.iacr.org/2014/944
[10] Fuchsbauer, G.; Hanser, C.; Slamanig, D.; Gennaro, R.; Robshaw, M., Practical round-optimal blind signatures in the standard model, Advances in Cryptology - CRYPTO 2015, 233-253, 2015, Heidelberg: Springer, Heidelberg · Zbl 1351.94045 · doi:10.1007/978-3-662-48000-7_12
[11] Gertner, Y., Kannan, S., Malkin, T., Reingold, O., Viswanathan, M.: The relationship between public key encryption and oblivious transfer. In: 41st FOCS, pp. 325-335. IEEE Computer Society Press, Redondo Beach, 12-14 November 2000
[12] Gertner, Y.; Malkin, T.; Myers, S.; Vadhan, SP, Towards a separation of semantic and CCA security for public key encryption, Theory of Cryptography, 434-455, 2007, Heidelberg: Springer, Heidelberg · Zbl 1129.94021 · doi:10.1007/978-3-540-70936-7_24
[13] Goldreich, O., Foundations of Cryptography: Basic Tools, 2001, Cambridge: Cambridge University Press, Cambridge · Zbl 1007.94016 · doi:10.1017/CBO9780511546891
[14] Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: 21st ACM STOC, pp. 25-32. ACM Press, Seattle, 15-17 May 1989
[15] Groth, J.; Sahai, A.; Smart, NP, Efficient non-interactive proof systems for bilinear groups, Advances in Cryptology - EUROCRYPT 2008, 415-432, 2008, Heidelberg: Springer, Heidelberg · Zbl 1149.94320 · doi:10.1007/978-3-540-78967-3_24
[16] Hanser, C.; Slamanig, D.; Sarkar, P.; Iwata, T., Structure-preserving signatures on equivalence classes and their application to anonymous credentials, Advances in Cryptology - ASIACRYPT 2014, 491-511, 2014, Heidelberg: Springer, Heidelberg · Zbl 1306.94060
[17] Håstad, J.; Impagliazzo, R.; Levin, LA; Luby, M., A pseudorandom generator from any one-way function, SIAM J. Comput., 28, 4, 1364-1396, 1999 · Zbl 0940.68048 · doi:10.1137/S0097539793244708
[18] Hess, F., On the security of the verifiably-encrypted signature scheme of boneh, gentry, lynn and shacham, Inf. Process. Lett., 89, 3, 111-114, 2004 · Zbl 1183.68265 · doi:10.1016/j.ipl.2003.10.008
[19] Impagliazzo, R., Luby, M.: One-way functions are essential for complexity based cryptography (extended abstract). In: 30th FOCS, pp. 230-235. IEEE Computer Society Press, Research Triangle Park, 30 October - 1 November 1989
[20] Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: 21st ACM STOC, pp. 44-61. ACM Press, Seattle, 15-17 May 1989
[21] Lamport, L.: Constructing digital signatures from a one-way function. Technical report SRI-CSL-98, SRI International Computer Science Laboratory, October 1979
[22] Lu, S.; Ostrovsky, R.; Sahai, A.; Shacham, H.; Waters, B.; Vaudenay, S., Sequential aggregate signatures and multisignatures without random oracles, Advances in Cryptology - EUROCRYPT 2006, 465-485, 2006, Heidelberg: Springer, Heidelberg · Zbl 1140.94358 · doi:10.1007/11761679_28
[23] Pfitzmann, B.; Sadeghi, A-R; Okamoto, T., Anonymous fingerprinting with direct non-repudiation, Advances in Cryptology - ASIACRYPT 2000, 401, 2000, Heidelberg: Springer, Heidelberg · Zbl 0974.94025 · doi:10.1007/3-540-44448-3_31
[24] Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: 22nd ACM STOC, pp. 387-394. ACM Press, Baltimore, 14-16 May 1990
[25] Rosen, A.; Segev, G.; Reingold, O., Chosen-ciphertext security via correlated products, Theory of Cryptography, 419-436, 2009, Heidelberg: Springer, Heidelberg · Zbl 1213.94130 · doi:10.1007/978-3-642-00457-5_25
[26] Rückert, M.; Roy, B.; Sendrier, N., Verifiably encrypted signatures from RSA without NIZKs, Progress in Cryptology - INDOCRYPT 2009, 363-377, 2009, Heidelberg: Springer, Heidelberg · Zbl 1252.94111 · doi:10.1007/978-3-642-10628-6_24
[27] Rückert, M.; Schröder, D.; Shacham, H.; Waters, B., Security of verifiably encrypted signatures and a construction without random oracles, Pairing-Based Cryptography - Pairing 2009, 17-34, 2009, Heidelberg: Springer, Heidelberg · Zbl 1248.94092 · doi:10.1007/978-3-642-03298-1_2
[28] Vahlis, Y.; Micciancio, D., Two Is a crowd? a black-box separation of one-wayness and security under correlated inputs, Theory of Cryptography, 165-182, 2010, Heidelberg: Springer, Heidelberg · Zbl 1274.94120 · doi:10.1007/978-3-642-11799-2_11
[29] Zhang, F.; Safavi-Naini, R.; Susilo, W.; Johansson, T.; Maitra, S., Efficient verifiably encrypted signature and partially blind signature from bilinear pairings, Progress in Cryptology - INDOCRYPT 2003, 191-204, 2003, Heidelberg: Springer, Heidelberg · Zbl 1123.94369 · doi:10.1007/978-3-540-24582-7_14
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.