nach oben

Designs, Codes and Cryptography

Erschienen in:

25.08.2016

On the power of rewinding simulators in functional encryption

verfasst von: Angelo De Caro, Vincenzo Iovino

Erschienen in: Designs, Codes and Cryptography | Ausgabe 3/2017

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

In a seminal work, Boneh, Sahai and Waters (BSW) [TCC’11] showed that for functional encryption the indistinguishability notion of security (IND-Security) is weaker than simulation-based security (SIM-Security), and that SIM-Security is in general impossible to achieve. This has opened up the door to a plethora of papers showing feasibility and new impossibility results. Nevertheless, the quest for better definitions that (1) overcome the limitations of IND-Security and (2) the known impossibility results, is still open. In this work, we explore the benefits and the limits of using efficient rewinding black-box simulators to argue security. To do so, we introduce a new simulation-based security definition, that we call rewinding simulation-based security (RSIM-Security), that is weaker than the previous ones but it is still sufficiently strong to not meet pathological schemes as it is the case for IND-Security (that is implied by the RSIM). This is achieved by retaining a strong simulation-based flavour but adding more rewinding power to the simulator having care to guarantee that it can not learn more than what the adversary would learn in any run of the experiment. What we found is that for RSIM the BSW impossibility result does not hold and that IND-Security is equivalent to RSIM-Security for attribute-based encryption in the standard model. Nevertheless, we prove that there is a setting where rewinding simulators are of no help. The adversary can put in place a strategy that forces the simulator to rewind continuously.

Vorheriger Artikel Constructions of maximum distance separable symbol-pair codes using cyclic and constacyclic codes

Nächster Artikel Construction of low-hit-zone frequency hopping sequences with optimal partial Hamming correlation by interleaving techniques

Nur mit Berechtigung zugänglich

Agrawal et al. [3] shows that their impossibility result holds in a variant of the selective security model, called by [18] fully non-adaptive model, where the adversary makes simultaneous key-generation and challenge message queries before seeing the public parameters.

Precisely, the functional encryption scheme of [19] only achieves \((\mathsf{poly},\mathsf{poly},\mathsf{poly})\)-sel-IND-Security but later [16] and [6] provided schemes that avoid the selective security model.

Note that we do not refer to their latest eprint revision but at the specific version posted on 6 March 2014 that has been updated after and in the subsequent revisions represents an extended abstract of the paper appeared in [5].

Precisely, we show a stronger result that \((0,\mathsf{poly},1)\)- RSIM-Security with negligible advantage is not achievable in the standard model in the auxiliary input setting (see Sect. 3). The auxiliary input setting has been already used by [10] in the same context.

See [1, 10] for a discussion about this condition.

Precisely, it would be possible at the cost of non-efficient simulation.

Recall that \({\mathbf {x}}\) is a vector of challenge messages in which, for \(j\in [\ell ]\), the j-th component consists of a pair \((\mathsf{ind}_j,\mathsf{m}_j)\), where \(\mathsf{ind}_j\) is the “index“ and \(\mathsf{m}_j\) is the “payload“.

A similar problem arises in the context of rewinding simulators for constant-round zero-knowledge as in [22].

We remark that our inner-product is defined over \({\mathbb {Z}}_2\) so the predicate is different from that of [32].

The challenge index output by the adversary consists of a tuple \((x_1,\ldots ,x_\ell )\) of vectors where each element \(x_i\in \{0,1\}^n\) for \(i=1,\ldots ,\ell \). For simplicity, henceforth we interpret such challenges as vectors in \(\{0,1\}^{n\cdot \ell }\).

The authors of [18] proved this fact that will appear in the full version of their paper.

For sake of simplicity we implicitly assume that the functionality is not parameterized by the security parameter but this can be generalized easily.

Abdalla M., Bellare M., Neve G.: Robust encryption. In: Micciancio D. (ed.) TCC 2010: 7th Theory of Cryptography Conference, Zurich, 9–11 Feb. Lecture Notes in Computer Science, vol. 5978, pp. 480–497. Springer, Berlin (2010).

Agrawal S., Freeman D.M., Vaikuntanathan V.: Functional encryption for inner product predicates from learning with errors. In: Lee D.H., Wang X. (eds.) Advances in Cryptology—ASIACRYPT 2011, Seoul, 4–8 Dec 2011. Lecture Notes in Computer Science, vol. 7073, pp. 21–40 . Springer, Berlin (2011).

Agrawal S., Gorbunov S., Vaikuntanathan V., Wee H.: Functional encryption: new perspectives and lower bounds. In: Canetti R., Garay J.A. (eds.) Advances in Cryptology—CRYPTO 2013, Part II, Santa Barbara, 18–22 Aug 2013. Lecture Notes in Computer Science, vol. 8043, pp. 500–518. Springer, Berlin (2013).

Agrawal S., Agrawal S., Badrinarayanan S., Kumarasubramanian A., Prabhakaran M., Sahai A.: Function private functional encryption and property preserving encryption: new definitions and positive results. Cryptology ePrint Archive, Report 2013/744, Version posted on 6 Mar 2014. http://eprint.iacr.org/2013/744/20140306:053744 (2014).

Agrawal S., Agrawal S., Badrinarayanan S., Kumarasubramanian A., Prabhakaran M., Sahai A.: On the practical security of inner product functional encryption. In: Proceedings of Public-Key Cryptography—PKC 2015—18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, 30 Mar–1 Apr 2015, pp. 777–798 (2015).

Ananth P., Boneh D., Garg S., Sahai A., Zhandry M.: Differing-inputs obfuscation and applications. Cryptology ePrint Archive, Report 2013/689. http://eprint.iacr.org/2013/689 (2013).

Backes M., Müller-Quade J., Unruh D.: On the necessity of rewinding in secure multiparty computation. In: Vadhan S.P. (ed.) TCC 2007: 4th Theory of Cryptography Conference, Amsterdam, 21–24 Feb 2007. Lecture Notes in Computer Science, vol. 4392, pp. 157–173. Springer, Berlin (2007).

Barbosa M., Farshim P.: On the semantic security of functional encryption schemes. In: Kurosawa K., Hanaoka G. (eds.) PKC 2013: 16th International Workshop on Theory and Practice in Public Key Cryptography, Nara, 26 Feb–1 Mar 2013. Lecture Notes in Computer Science, vol. 7778, pp. 143–161. Springer, Berlin (2013).

Barkol O., Ishai Y.: Secure computation of constant-depth circuits with applications to database search problems. In: Shoup V. (ed.) Advances in Cryptology—CRYPTO 2005, Santa Barbara, 14–18 Aug 2005. Lecture Notes in Computer Science, vol. 3621, pp. 395–411. Springer, Berlin (2005).

10.

Bellare M., O’Neill A.: Semantically-secure functional encryption: possibility results, impossibility results and the quest for a general definition. In: Proceedings of Cryptology and Network Security—12th International Conference, CANS 2013, Paraty, 20–22 Nov 2013, pp. 218–234 (2013).

11.

Bellare M., Dowsley R., Waters B., Yilek S.: Standard security does not imply security against selective-opening. In: Pointcheval D., Johansson T. (eds.) Advances in Cryptology—EUROCRYPT 2012, Cambridge, 15–19 Apr 2012. Lecture Notes in Computer Science, vol. 7237, pp. 645–662. Springer, Berlin (2012).

12.

Boneh D., Boyen X.: Efficient selective identity-based encryption without random oracles. J. Cryptol 24(4), 659–693 (2011).MathSciNetCrossRefMATH

13.

Boneh D., Franklin M.K.: Identity-based encryption from the Weil pairing. In: Kilian J. (ed.) Advances in Cryptology—CRYPTO 2001, Santa Barbara, 19–23 Aug 2001. Lecture Notes in Computer Science, vol. 2139, pp. 213–229. Springer, Berlin (2001).

14.

Boneh D., Waters B.: Conjunctive, subset, and range queries on encrypted data. In: Vadhan S.P. (ed.) TCC 2007: 4th Theory of Cryptography Conference, Amsterdam, 21–24 Feb 2007. Lecture Notes in Computer Science, vol. 4392, pp. 535–554. Springer, Berlin (2007).

15.

Boneh D., Sahai A., Waters B.: Functional encryption: definitions and challenges. In: Ishai Y. (ed.) TCC 2011: 8th Theory of Cryptography Conference, Providence, 28–30 Mar 2011. Lecture Notes in Computer Science, vol. 6597, pp. 253–273. Springer, Berlin (2011).

16.

Boyle E., Chung K.-M., Pass R.: On extractability obfuscation. In: Lindell Y. (ed.) TCC 2014: 11th Theory of Cryptography Conference, San Diego, 24–26 Feb 2014. Lecture Notes in Computer Science, vol. 8349, pp. 52–73. Springer, Berlin (2014).

17.

Cocks C.: An identity based encryption scheme based on quadratic residues. In: Honary B. (ed.) 8th IMA International Conference on Cryptography and Coding, Cirencester, 17–19 Dec 2001. Lecture Notes in Computer Science, vol. 2260, pp. 360–363. Springer, Berlin (2001).

18.

De Caro A., Iovino V., Jain A., O’Neill A., Paneth O., Persiano G.: On the achievability of simulation-based security for functional encryption. In: Canetti R., Garay J.A. (eds.) Advances in Cryptology—CRYPTO 2013, Part II, Santa Barbara, 18–22 Aug 2013. Lecture Notes in Computer Science, vol. 8043, pp. 519–535. Springer, Berlin (2013).

19.

Garg S., Gentry C., Halevi S., Raykova M., Sahai A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: 54th Annual Symposium on Foundations of Computer Science, Berkeley, 26–29 Oct 2013, pp. 40–49. IEEE Computer Society Press, Berkeley (2013).

20.

Garg S., Gentry C., Halevi S., Sahai A., Waters B.: Attribute-based encryption for circuits from multilinear maps. In: Canetti R., Garay J.A. (eds.) Advances in Cryptology–CRYPTO 2013, Part II, Santa Barbara, 18–22 Aug 2013. Lecture Notes in Computer Science, vol. 8043, pp. 479–499. Springer, Berlin (2013).

21.

Gentry C.: Practical identity-based encryption without random oracles. In: Vaudenay S. (ed.) Advances in Cryptology—EUROCRYPT 2006, St. Petersburg, 28 May–1 June 2006. Lecture Notes in Computer Science, vol. 4004, pp. 445–464. Springer, Berlin (2006).

22.

Goldreich O., Kahan A.: How to construct constant-round zero-knowledge proof systems for NP. J. Cryptol. 9(3), 167–190 (1996).MathSciNetCrossRefMATH

23.

Goldreich O., Micali S., Wigderson A.: Proofs that yield nothing but their validity and a methodology of cryptographic protocol design (extended abstract). In: 27th Annual Symposium on Foundations of Computer Science, Toronto, 27–29 Oct 1986, pp. 174–187. IEEE Computer Society Press, Berkely (1986).

24.

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

25.

Goldwasser S., Micali S., Rackoff C.: The knowledge complexity of interactive proof-systems (extended abstract). In: Proceedings of the 17th Annual ACM Symposium on Theory of Computing, Providence, 6–8 May 1985, pp. 291–304 (1985).

26.

Goldwasser S., Kalai Y.T., Popa R.A. , Vaikuntanathan V., Zeldovich N.: Reusable garbled circuits and succinct functional encryption. In: Boneh D., Roughgarden , Feigenbaum J., (eds.) 45th Annual ACM Symposium on Theory of Computing, Palo Alto, 1–4 June 2013, pp. 555–564. ACM Press, New York (2013).

27.

Gorbunov S., Vaikuntanathan V., Wee H.: Functional encryption with bounded collusions via multi-party computation. In: Safavi-Naini R., Canetti R. (eds.) Advances in Cryptology—CRYPTO 2012, Santa Barbara, 19–23 Aug 2012. Lecture Notes in Computer Science, vol. 7417, pp. 162–179. Springer, Berlin (2012).

28.

Gorbunov S., Vaikuntanathan V., We H.: Functional encryption with bounded collusions via multi-party computation. In: Safavi-Naini R., Canetti R. (eds.) CRYPTO. Lecture Notes in Computer Science, vol. 7417, pp. 162–179. Springer, Berlin (2012).

29.

Gorbunov S., Vaikuntanathan V., Wee H.: Attribute-based encryption for circuits. In: Boneh D., Roughgarden T., Feigenbaum J. (eds.) STOC, pp. 545–554. ACM, New York (2013).

30.

Goyal V., Pandey O., Sahai A., Waters B.: Attribute-based encryption for fine-grained access control of encrypted data. In: Juels A., Wright R.N., Vimercati S., (eds.) ACM CCS 06: 13th Conference on Computer and Communications Security, Alexandria, 30 Oct–3 Nov 2006, pp. 89–98. ACM Press, New York. Available as Cryptology ePrint Archive Report 2006/309 (2006).

31.

Iovino V., Żebrowski K.: Simulation-based secure functional encryption in the random oracle model. In: Proceedings of Progress in Cryptology— ATINCRYPT 2015—4th International Conference on Cryptology and Information Security in Latin America, Guadalajara, 23–26 Aug 2015, pp. 21–39 (2015).

32.

Katz J., Sahai A., Waters B.: Predicate encryption supporting disjunctions, polynomial equations, and inner products. In: Smart N.P. (ed.) Advances in Cryptology—EUROCRYPT 2008, Istanbul, 13–17 Apr 2008. Lecture Notes in Computer Science, vol. 4965, pp. 146–162. Springer, Berlin (2008).

33.

Lewko A.B., Okamoto T., Sahai A., Takashima K., Waters B.: Fully secure functional encryption: attribute-based encryption and (hierarchical) inner product encryption. In: Gilbert H. (ed.) Advances in Cryptology—EUROCRYPT 2010, French Riviera, 30 May–3 June 2010. Lecture Notes in Computer Science, vol. 6110, pp. 62–91. Springer, Berlin (2010).

34.

Okamoto T., Takashima K.: Adaptively attribute-hiding (hierarchical) inner product encryption. In: Pointcheval D., Johansson T. (eds.) Advances in Cryptology—EUROCRYPT 2012, Cambridge, 15–19 Apr 2012. Lecture Notes in Computer Science, vol. 7237, pp. 591–608. Springer, Berlin (2012).

35.

O’Neill A: Definitional issues in functional encryption. Cryptology ePrint Archive, Report 2010/556. http://eprint.iacr.org/ (2010).

36.

Sahai A., Waters B.R.: Fuzzy identity-based encryption. In: Cramer R. (ed.) Advances in Cryptology—EUROCRYPT 2005, Aarhus, 22–26 May 2005. Lecture Notes in Computer Science, vol. 3494, pp. 457–473. Springer, Berlin (2005).

37.

Shamir A.: Identity-based cryptosystems and signature schemes. In: Blakley G.R., Chaum D. (eds.) Advances in Cryptology—CRYPTO’84, Santa Barbara, 19–23 Aug 1984. Lecture Notes in Computer Science, vol. 196, pp. 47–53. Springer, Berlin (1984).

38.

Waters B.: Functional encryption for regular languages. In: Safavi-Naini R., Canetti R., (eds.) Advances in Cryptology—CRYPTO 2012, Santa Barbara, 19–23 Aug 2012. Lecture Notes in Computer Science, pp. 218–235. Springer, Berlin (2012).

Titel: On the power of rewinding simulators in functional encryption
verfasst von: Angelo De Caro
Vincenzo Iovino
Publikationsdatum: 25.08.2016
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 3/2017
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-016-0272-x

Springer Professional

Abstract

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

Weitere Artikel der Ausgabe 3/2017

Doubly resolvable Steiner quadruple systems and related designs

Constructions of maximum distance separable symbol-pair codes using cyclic and constacyclic codes

Galois self-dual constacyclic codes

Higher order differentiation over finite fields with applications to generalising the cube attack

Construction of low-hit-zone frequency hopping sequences with optimal partial Hamming correlation by interleaving techniques

Cryptanalysis of multilinear maps from ideal lattices: revisited