nach oben

Designs, Codes and Cryptography

Erschienen in:

01.07.2016

Tightly secure signatures and public-key encryption

verfasst von: Dennis Hofheinz, Tibor Jager

Erschienen in: Designs, Codes and Cryptography | Ausgabe 1/2016

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We construct the first public-key encryption (PKE) scheme whose chosen-ciphertext (i.e., IND-CCA) security can be proved under a standard assumption and does not degrade in either the number of users or the number of ciphertexts. In particular, our scheme can be safely deployed in settings in which no a-priori bound on the number of encryptions and/or users is known. As a central technical building block, we devise the first structure-preserving signature scheme with a tight security reduction. (This signature scheme may be of independent interest.) Combining this scheme with Groth–Sahai proofs yields a tightly simulation-sound non-interactive zero-knowledge proof system for group equations. If we use this proof system in the Naor–Yung double encryption scheme, we obtain a tightly IND-CCA secure PKE scheme from the decision linear assumption. We point out that our techniques are not specific to PKE security. Rather, we view our signature scheme and proof system as general building blocks that can help to achieve a tight security reduction.

Vorheriger Artikel Almost separating and almost secure frameproof codes over -ary alphabets

Nächster Artikel On small gaps between the elements of multiplicative subgroups of finite fields

Nur mit Berechtigung zugänglich

Bellare et al. [11] show that the security loss of Cramer–Shoup encryption [21] does not depend on the number of users; however, their reduction loss still grows linearly in the number of ciphertexts per user. On of the IND-SO-CCA secure PKE schemes of Hofheinz [39] also achieves a form of tight security (in the single-user but multi-challenge setting); however, this work relies on a non-standard multi-challenge assumption.

However, we expect that our constructions also naturally generalize to the—potentially weaker—\(K\)-Linear assumption and to suitable subgroup decision assumptions.

We construct tightly secure structure-preserving signatures. (In fact, our schemes can sign their own public key; such signature schemes are commonly also referred to as automorphic.) While there exist tightly secure signature schemes (e.g., [12, 14, 20, 31, 43, 55]), and structure-preserving signature schemes (e.g., [3, 19, 28]), our scheme seems to be the first to achieve both properties. This combination of properties is crucial for our applications.

By a simulation-sound zero-knowledge proof system, we mean one in which it is infeasible to generate valid proofs for false statements, even when already having observed many simulated proofs for possibly false statements.

We remark that a tight security proof of the Naor–Yung-based encryption scheme in a security model with many challenge ciphertexts requires to substitute many ciphertexts at once with encryptions of random messages. This in turn requires a proof system which allows to simulate proofs for many (possibly false) statements, while still preserving soundness. Simulation-soundness in this sense is not achieved, e.g., by the original GS proof system from [37].

We highlight that (1) actually consists of three pairing product equations. This can in part be justified by [3, Theorem 2], which states that already any secure structure-preserving two-time signature scheme must have at least two verification equations.

As pointed out by an anonymous reviewer, this construction also has another interpretation. Namely, since our one-time signature scheme can be interpreted as a commitment scheme (see the note after Lemma 1), combining it with a non-adaptively secure signature scheme to obtain adaptive security can be viewed as a variant of the construction from [17].

We note that perfect soundness (i.e., \(\epsilon _\mathsf {snd}=0\)) can be achieved as in [36, Sect. 6] with a slightly more complicated setup. In a nutshell, we could add a non-DLIN-tuple \(T\in {\mathbb {G}} ^6\) to CRS and prove that either \(S\) is satisfiable, or \(T\) is a DLIN-tuple and we know a \({\mathsf {TSig}}\)-signature for \({ vk }_{\mathsf {tots}}\) (or both). A simulator \({\mathcal {S}}\) would of course change \(T\) to a DLIN-tuple in simulated CRSs. We omit the details.

Abe M., Fuchsbauer G., Groth J., Haralambiev K., Ohkubo M.: Structure-preserving signatures and commitments to group elements. In: Rabin T. (ed.) Advances in Cryptology—CRYPTO 2010. Lecture Notes in Computer Science, vol. 6223, pp. 209–236. Springer, Berlin (2010).

Abe M., Haralambiev K., Ohkubo M.: Signing on elements in bilinear groups for modular protocol design. Cryptology ePrint Archive, Report 2010/133 (2010) http://eprint.iacr.org/.

Abe M., Groth J., Haralambiev K., Ohkubo M.: Optimal structure-preserving signatures in asymmetric bilinear groups. In: Rogaway P. (ed.) Advances in Cryptology—CRYPTO 2011. Lecture Notes in Computer Science, vol. 6841, pp. 649–666. Springer, Berlin (2011).

Abe M., Chase M., David B., Kohlweiss M., Nishimaki R., Ohkubo M.: Constant-size structure-preserving signatures: generic constructions and simple assumptions. In: Wang X., Sako K. (eds.) Advances in Cryptology—ASIACRYPT 2012. Lecture Notes in Computer Science, vol. 7658, pp. 4–24. Springer, Berlin (2012). doi:10.1007/978-3-642-34961-4_3.

Abe M., David B., Kohlweiss M., Nishimaki R., Ohkubo M.: Tagged one-time signatures: tight security and optimal tag size. In: Kurosawa K., Hanaoka G. (eds.) PKC 2013: 16th International Workshop on Theory and Practice in Public Key Cryptography. Lecture Notes in Computer Science, vol. 7778, pp. 312–331. Springer, Berlin (2013). doi:10.1007/978-3-642-36362-7_20.

Bellare M., Rogaway P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Ashby V. (ed.) ACM CCS 93: 1st Conference on Computer and Communications Security, pp. 62–73. ACM Press, Fairfax (1993).

Bellare M., Rogaway P.: The security of triple encryption and a framework for code-based game-playing proofs. In: Vaudenay S. (ed.) Advances in Cryptology—EUROCRYPT 2006. Lecture Notes in Computer Science, vol. 4004, pp. 409–426. Springer, Berlin (2006).

Bellare M., Shoup S.: Two-tier signatures, strongly unforgeable signatures, and Fiat-Shamir without random oracles. In: Okamoto T., Wang X. (eds.) PKC 2007: 10th International Conference on Theory and Practice of Public Key Cryptography. Lecture Notes in Computer Science, vol. 4450, pp. 201–216. Springer, Berlin (2007).

Bellare M., Desai A., Jokipii E., Rogaway P.: A concrete security treatment of symmetric encryption. In: 38th Annual Symposium on Foundations of Computer Science, pp. 394–403. IEEE Computer Society Press, Miami Beach (1997).

10.

Bellare M., Desai A., Pointcheval D., Rogaway P.: Relations among notions of security for public-key encryption schemes. In: Krawczyk H. (ed.): Advances in Cryptology—CRYPTO’98. Lecture Notes in Computer Science, vol. 1462, pp. 26–45. Springer, Berlin (1998).

11.

Bellare M., Boldyreva A., Micali S.: Public-key encryption in a multi-user setting: security proofs and improvements. In: Preneel B. (ed.) Advances in Cryptology—EUROCRYPT 2000. Lecture Notes in Computer Science, vol. 1807, pp. 259–274. Springer, Berlin (2000).

12.

Bernstein D.J.: Proving tight security for Rabin-Williams signatures. In: Smart N.P. (ed.): Advances in Cryptology—EUROCRYPT 2008. Lecture Notes in Computer Science, vol. 4965, pp. 70–87. Springer, Berlin (2008).

13.

Boneh D., Boyen X.: Efficient selective-ID secure identity based encryption without random oracles. In: Cachin C., Camenisch J. (eds.) Advances in Cryptology—EUROCRYPT 2004. Lecture Notes in Computer Science, vol. 3027, pp. 223–238. Springer, Berlin (2004).

14.

Boneh D., Mironov I., Shoup V.: A secure signature scheme from bilinear maps. In: Joye M. (ed.) Topics in Cryptology—CT-RSA 2003. Lecture Notes in Computer Science, vol. 2612, pp. 98–110. Springer, Berlin (2003).

15.

Boneh D., Boyen X., Shacham H.: Short group signatures. In: Franklin M. (ed.): Advances in Cryptology—CRYPTO 2004. Lecture Notes in Computer Science, vol. 3152, pp. 41–55. Springer, Berlin (2004).

16.

Camenisch J., Chandran N., Shoup V.: A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks. In: Joux A. (ed.): Advances in Cryptology—EUROCRYPT 2009. Lecture Notes in Computer Science, vol. 5479, pp. 351–368. Springer, Berlin (2009).

17.

Canetti R., Halevi S., Katz J.: A forward-secure public-key encryption scheme. In: Biham E. (ed.): Advances in Cryptology—EUROCRYPT 2003. Lecture Notes in Computer Science, vol. 2656, pp. 255–271. Springer, Berlin (2003).

18.

Cathalo J., Libert B., Yung M.: Group encryption: non-interactive realization in the standard model. In: Matsui M. (ed.) Advances in Cryptology—ASIACRYPT 2009. Lecture Notes in Computer Science, vol. 5912, pp. 179–196. Springer, Berlin (2009).

19.

Chase M., Kohlweiss M.: A domain transformation for structure-preserving signatures on group elements. Cryptology ePrint Archive, Report 2011/342 (2011). http://eprint.iacr.org/.

20.

Chevallier-Mames B., Joye M.: A practical and tightly secure signature scheme without hash function. In: Abe M. (ed.) Topics in Cryptology—CT-RSA 2007. Lecture Notes in Computer Science, vol. 4377, pp. 339–356. Springer, Berlin (2007).

21.

Cramer R., Shoup V.: A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In: Krawczyk H. (ed.): Advances in Cryptology—CRYPTO’98. Lecture Notes in Computer Science, vol. 1462, pp. 13–25. Springer, Berlin (1998).

22.

Cramer R, Shoup V.: Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In: Knudsen L.R. (ed.) Advances in Cryptology—EUROCRYPT 2002. Lecture Notes in Computer Science, vol. 2332, pp. 45–64. Springer, Berlin (2002).

23.

Damgård I., Nielsen J.B.: Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor. In: Yung M. (ed.) Advances in Cryptology—CRYPTO 2002. Lecture Notes in Computer Science, vol. 2442, pp. 581–596. Springer, Berlin (2002).

24.

Dodis Y., Haralambiev K., López-Alt A., Wichs D.: Efficient public-key cryptography in the presence of key leakage. In: Abe M. (ed.) Advances in Cryptology—ASIACRYPT 2010. Lecture Notes in Computer Science, vol. 6477, pp. 613–631. Springer, Berlin (2010).

25.

Dolev D., Dwork C., Naor M.: Nonmalleable cryptography. SIAM J. Comput. 30(2), 391–437 (2000).

26.

ElGamal T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31, 469–472 (1985).

27.

Even S., Goldreich O., Micali S.: On-line/off-line digital signatures. J. Cryptol. 9(1), 35–67 (1996).

28.

Fuchsbauer G.: Automorphic signatures and applications. PhD thesis, ENS, Paris (2010).

29.

Fujisaki E., Okamoto T.: Secure integration of asymmetric and symmetric encryption schemes. In: Wiener M.J. (ed.) Advances in Cryptology—CRYPTO’99. Lecture Notes in Computer Science, vol. 1666, pp. 537–554. Springer, Berlin (1999).

30.

Galbraith S.D., Malone-Lee J., Smart N.P.: Public key signatures in the multi-user setting. Inf. Process. Lett. 83(5), 263–266 (2002). doi:10.1016/S0020-0190(01)00338-6.

31.

Gennaro R., Halevi S., Rabin T.: Secure hash-and-sign signatures without the random oracle. In: Stern J. (ed.) Advances in Cryptology—EUROCRYPT’99. Lecture Notes in Computer Science, vol. 1592, pp. 123–139. Springer, Berlin (1999).

32.

Goldreich O.: Two remarks concerning the Goldwasser-Micali-Rivest signature scheme. In: Odlyzko A.M. (ed.) Advances in Cryptology—CRYPTO’86. Lecture Notes in Computer Science, vol. 263, pp. 104–110. Springer, Berlin (1986).

33.

Goldwasser S., Micali S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270–299 (1984).

34.

Goldwasser S., Micali S., Rivest R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281–308 (1988).

35.

Green M., Hohenberger S.: Practical adaptive oblivious transfer from simple assumptions. In: Ishai Y. (ed.) TCC 2011: 8th Theory of Cryptography Conference. Lecture Notes in Computer Science, vol. 6597, pp. 347–363. Springer, Berlin (2011).

36.

Groth J.: Simulation-sound NIZK proofs for a practical language and constant size group signatures. In: Lai X., Chen K. (eds.) Advances in Cryptology—ASIACRYPT 2006. Lecture Notes in Computer Science, vol. 4284, pp. 444–459. Springer, Berlin (2006).

37.

Groth J., Sahai A.: Efficient non-interactive proof systems for bilinear groups. In: Smart N.P. (ed.): Advances in Cryptology—EUROCRYPT 2008. Lecture Notes in Computer Science, vol. 4965, pp. 415–432. Springer, Berlin (2008).

38.

Groth J., Sahai A.: Efficient noninteractive proof systems for bilinear groups. SIAM J. Comput. 41(5), 1193–1232 (2012).

39.

Hofheinz D.: All-but-many lossy trapdoor functions. In: Pointcheval D., Johansson T. (eds.) Advances in Cryptology—EUROCRYPT 2012. Lecture Notes in Computer Science, vol. 7237, pp. 209–227. Springer, Berlin (2012).

40.

Hofheinz D., Jager T.: Tightly secure signatures and public-key encryption. In: Safavi-Naini R., Canetti R. (eds.) Advances in Cryptology—CRYPTO 2012. Lecture Notes in Computer Science, vol. 7417, pp. 590–607. Springer, Berlin (2012).

41.

Hofheinz D., Kiltz E.: Secure hybrid encryption from weakened key encapsulation. In: Menezes A. (ed.) Advances in Cryptology—CRYPTO 2007. Lecture Notes in Computer Science, vol. 4622, pp. 553–571. Springer, Berlin (2007).

42.

Hofheinz D., Kiltz E.: Practical chosen ciphertext secure encryption from factoring. In: Joux A. (ed.): Advances in Cryptology—EUROCRYPT 2009. Lecture Notes in Computer Science, vol. 5479, pp. 313–332. Springer, Berlin (2009).

43.

Joye M.: An efficient on-line/off-line signature scheme without random oracles. In: Franklin M.K., Hui L.C.K., Wong D.S. (eds.) CANS 08: 7th International Conference on Cryptology and Network Security. Lecture Notes in Computer Science, vol. 5339, pp. 98–107. Springer, Berlin (2008).

44.

Katz J., Wang N.: Efficiency improvements for signature schemes with tight security reductions. In: Jajodia S., Atluri V., Jaeger T. (eds.) ACM CCS 03: 10th Conference on Computer and Communications Security, pp. 155–164. ACM Press, Washington, DC (2003).

45.

Krawczyk H., Rabin T.: Chameleon signatures. In: ISOC Network and Distributed System Security Symposium—NDSS: The Internet Society. San Diego (2000).

46.

Kurosawa K., Desmedt Y.: A new paradigm of hybrid encryption scheme. In: Franklin M. (ed.): Advances in Cryptology—CRYPTO 2004. Lecture Notes in Computer Science, vol. 3152, pp. 426–442. Springer, Berlin (2004).

47.

Lewko A.B., Waters B.: Efficient pseudorandom functions from the decisional linear assumption and weaker variants. In: Al-Shaer E., Jha S., Keromytis A.D. (eds.) ACM CCS 09: 16th Conference on Computer and Communications Security, pp. 112–120. ACM Press, Chicago (2009).

48.

Lewko A.B., Waters B.: New techniques for dual system encryption and fully secure HIBE with short ciphertexts. In: Micciancio D. (ed.) TCC 2010: 7th Theory of Cryptography Conference. Lecture Notes in Computer Science, vol. 5978, pp. 455–479. Springer, Berlin (2010).

49.

Lindell Y.: A simpler construction of cca2-secure public-key encryption under general assumptions. In: Biham E. (ed.): Advances in Cryptology—EUROCRYPT 2003. Lecture Notes in Computer Science, vol. 2656, pp. 241–254. Springer, Berlin (2003)

50.

Merkle R.C.: A certified digital signature. In: Brassard G. (ed.) Advances in Cryptology—CRYPTO’89. Lecture Notes in Computer Science, vol. 435, pp. 218–238. Springer, Berlin (1989).

51.

Naor M., Yung M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: 22nd Annual ACM Symposium on Theory of Computing, pp. 427–437. ACM Press, Baltimore (1990).

52.

Pedersen T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum J. (ed.): Advances in Cryptology—CRYPTO’91. Lecture Notes in Computer Science, vol. 576, pp. 129–140. Springer, Berlin (1991).

53.

Rackoff C., Simon, D.R.: Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. In: Feigenbaum J. (ed.): Advances in Cryptology—CRYPTO’91. Lecture Notes in Computer Science, vol. 576, pp. 433–444. Springer, Berlin (1991).

54.

Sahai, A.: Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In: 40th Annual Symposium on Foundations of Computer Science, pp. 543–553. IEEE Computer Society Press, New York (1999).

55.

Schäge S.: Tight proofs for signature schemes without random oracles. In: Paterson K.G. (ed.) Advances in Cryptology—EUROCRYPT 2011. Lecture Notes in Computer Science, vol. 6632, pp. 189–206. Springer, Berlin (2011).

56.

Shoup V.: Sequences of games: a tool for taming complexity in security proofs. Cryptology ePrint Archive, Report 2004/332 (2004). http://eprint.iacr.org/.

57.

Waters B.: Dual system encryption: Realizing fully secure IBE and HIBE under simple assumptions. In: Halevi S. (ed.) Advances in Cryptology—CRYPTO 2009. Lecture Notes in Computer Science, vol. 5677, pp. 619–636. Springer, Berlin (2009).

Titel: Tightly secure signatures and public-key encryption
verfasst von: Dennis Hofheinz
Tibor Jager
Publikationsdatum: 01.07.2016
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 1/2016
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-015-0062-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 1/2016

Perfect codes in Doob graphs

A general check digit system based on finite groups

Rank-metric codes and their duality theory

On small gaps between the elements of multiplicative subgroups of finite fields

Almost separating and almost secure frameproof codes over -ary alphabets

Constructions and analysis of some efficient --visual cryptographic schemes using linear algebraic techniques