Sage Journals: Discover world-class research

Abstract

We put forth the notion of publicly evaluable pseudorandom functions (PEPRFs), which can be viewed as a counterpart of standard pseudorandom functions (PRFs) in the public-key setting. Briefly, PEPRFs are defined over domain X containing a language L associated with a hard relation $R_{L}$ , and each secret key $sk$ is associated with a public key $pk$ . For any $x \in L$ , in addition to evaluate $F_{sk} (x)$ using $sk$ as standard PRFs, one is also able to evaluate $F_{sk} (x)$ with $pk$ , x and a witness w for $x \in L$ . We consider two security notions for PEPRFs. The basic one is weak pseudorandomness which stipulates a PEPRF cannot be distinguished from a real random function on uniformly random chosen inputs. The strengthened one is adaptive weak pseudorandomness which requires a PEPRF remains weak pseudorandom even when an adversary is given adaptive access to an evaluation oracle. We conduct a formal study of PEPRFs, focusing on applications, constructions, and extensions.

∙ We show how to construct chosen-plaintext secure (CPA) and chosen-ciphertext secure (CCA) public-key encryption (PKE) schemes from (adaptive) PEPRFs. The construction is simple, black-box, and admits a direct proof of security. We provide evidence that (adaptive) PEPRFs exist by showing constructions from injective trapdoor functions, hash proof systems, extractable hash proof systems, as well as a construction from puncturable PRFs with program obfuscation.

∙ We introduce the notion of publicly sampleable PRFs (PSPRFs), which is a relaxation of PEPRFs, but nonetheless imply PKE. We show (adaptive) PSPRFs are implied by (adaptive) trapdoor relations. This helps us to unify and clarify many PKE schemes from seemingly unrelated general assumptions and paradigms under the notion of PSPRFs.

∙ We explore similar extension on recently emerging constrained PRFs, and introduce the notion of publicly evaluable constrained PRFs, which, as an immediate application, implies attribute-based encryption.

∙ We propose a twist on PEPRFs, which we call publicly evaluable and verifiable functions (PEVFs). Compared to PEPRFs, PEVFs have an additional promising property named public verifiability while the best possible security degrades to unpredictability. We justify the applicability of PEVFs by presenting a simple construction of “hash-and-sign” signatures, both in the random oracle model and the standard model.

Keywords

Publicly evaluable pseudorandom function hash proof system extractable hash proof system trapdoor function

Get full access to this article

View all access options for this article.

References

Alwen ,

Dodis ,

Naor ,

Segev ,

Walfish and

Wichs , Public-key encryption in the bounded-retrieval model, in: Advances in Cryptology – EUROCRYPT 2010, LNCS, Vol. 6110, Springer, 2010, pp. 113–134.

P.V.

Ananth ,

Gupta ,

Ishai and

Sahai , Optimizing obfuscation: Avoiding Barrington’s theorem, in: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, 2014, pp. 646–658.

Barak ,

Garg ,

Y.T.

Kalai ,

Paneth and

Sahai , Protecting obfuscation against algebraic attacks, in: Advances in Cryptology – EUROCRYPT 2014, LNCS, Vol. 8441, Springer, 2014, pp. 221–238.

Bellare and

Cash , Pseudorandom functions and permutations provably secure against related-key attacks, in: Advances in Cryptology – CRYPTO 2010, LNCS, Vol. 6223, Springer, 2010, pp. 666–684.

Bellare and

Kohno , A theoretical treatment of related-key attacks: Rka-prps, rka-prfs, and applications, in: Advances in Cryptology – EUROCRYPT 2003, LNCS, Vol. 2656, Springer, 2003, pp. 491–506.

Bellare and

Rogaway , The exact security of digital signatures – How to sign with rsa and rabin, in: Advances in Cryptology – EUROCRYPT 1996, LNCS, Vol. 1070, 1996, pp. 399–416.

Bellare ,

Tung Hoang and

Rogaway , Foundations of garbled circuits, in: ACM Conference on Computer and Communications Security, CCS 2012, ACM, 2012, pp. 784–796.

Bentahar ,

Farshim ,

Malone-Lee and

N.P.

Smart , Generic constructions of identity-based and certificateless kems, Journal of Cryptology 21(2) (2008), 178–199.

Berman and

Haitner , From non-adaptive to adaptive pseudorandom functions, in: Theory of Cryptography – 9th Theory of Cryptography Conference, TCC 2012, LNCS, Vol. 7194, Springer, 2012, pp. 357–368.

10.

Boneh ,

Canetti ,

Halevi and

Katz , Chosen-ciphertext security from identity-based encryption, SIAM Journal on Computation 36(5) (2007), 1301–1328.

11.

Boneh ,

Lynn and

Shacham , Short signatures from the Weil pairing, in: Advances in Cryptology – ASIACRYPT 2001, LNCS, Vol. 2248, 2001, pp. 514–532.

12.

Boneh and

Waters , Constrained pseudorandom functions and their applications, in: Advances in Cryptology – ASIACRYPT 2013, LNCS, Vol. 8270, Springer, 2013, pp. 280–300.

13.

Boneh and

Zhandry , Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation, in: Advances in Cryptology – CRYPTO 2014, LNCS, Vol. 8616, Springer, 2014, pp. 480–499.

14.

Boyen ,

Mei and

Waters , Direct chosen ciphertext security from identity-based techniques, in: CCS 2005, ACM, 2005, pp. 320–329.

15.

Boyle ,

Goldwasser and

Ivan , Functional signatures and pseudorandom functions, in: 17th International Conference on Practice and Theory in Public-Key Cryptography, PKC 2014, LNCS, Vol. 8383, Springer, 2014, pp. 501–519.

16.

Cash ,

Kiltz and

Shoup , The twin Diffie–Hellman problem and applications, J. Cryptology 22(4) (2009), 470–504.

17.

Chen and

Zhang , Publicly evaluable pseudorandom functions and their applications, Cryptology ePrint Archive, Report 2014/306, 2014, available at: http://eprint.iacr.org/2014/306.

18.

Chen ,

Zhang ,

Lin and

Cao , Anonymous identity-based hash proof system and its applications, in: Provable Security – 6th International Conference, ProvSec 2012, LNCS, Vol. 7496, Springer, 2012, pp. 143–160.

19.

Chen ,

Zhang ,

Lin and

Cao , Identity-based extractable hash proofs and their applications, in: International Conference on Applied Cryptography and Network Security – ACNS 2012, LNCS, Vol. 7341, Springer, 2012, pp. 153–170.

20.

J.H.

Cheon ,

Han ,

Lee ,

Ryu and

Stehlé , Cryptanalysis of the multilinear map over the integers, in: Advances in Cryptology – EUROCRYPT 2015, LNCS, Vol. 9056, Springer, 2015, pp. 3–12.

21.

J.H.

Cheon ,

Lee and

Ryu , Cryptanalysis of the new CLT multilinear maps, IACR Cryptology ePrint Archive 2015 (2015), 934.

22.

J.-S.

Coron ,

Gentry ,

Halevi ,

Lepoint ,

H.K.

Maji ,

Miles ,

Raykova ,

Sahai and

Tibouchi , Zeroizing without low-level zeroes: New MMAP attacks and their limitations, in: Advances in Cryptology – CRYPTO 2015, LNCS, Vol. 9215, Springer, 2015, pp. 247–266.

23.

J.-S.

Coron ,

Lepoint and

Tibouchi , Practical multilinear maps over the integers, in: Advances in Cryptology – CRYPTO 2013, LNCS, Vol. 8042, Springer, 2013, pp. 476–493.

24.

J.-S.

Coron ,

Lepoint and

Tibouchi , New multilinear maps over the integers, in: Advances in Cryptology – CRYPTO 2015, LNCS, Vol. 9215, Springer, 2015, pp. 267–286.

25.

Cramer ,

Hofheinz and

Kiltz , A twist on the Naor-Yung paradigm and its application to efficient cca-secure encryption from hard search problems, in: Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, LNCS, Vol. 5978, Springer, 2010, pp. 146–164.

26.

Cramer and

Shoup , A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack, in: Advances in Cryptology – CRYPTO 1998, LNCS, Vol. 1462, Springer, 1998, pp. 13–25.

27.

Cramer and

Shoup , Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption, in: Advances in Cryptology – EUROCRYPT 2002, LNCS, Vol. 2332, Springer, 2002, pp. 45–64.

28.

Cramer and

Shoup , Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack, SIAM Journal on Computing 33 (2003), 167–226.

29.

Dachman-Soled , A black-box construction of a cca2 encryption scheme from a plaintext aware encryption scheme, IACR Cryptology ePrint Archive 2013 (2013), 680.

30.

Diffie and

M.E.

Hellman , New directions in cryptograpgy, IEEE Transactions on Infomation Theory 22(6) (1976), 644–654.

31.

Dolev ,

Dwork and

Naor , Nonmalleable cryptography, SIAM J. Comput. 30(2) (2000), 391–437.

32.

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

33.

Garg ,

Gentry and

Halevi , Candidate multilinear maps from ideal lattices, in: Advances in Cryptology – EUROCRYPT 2013, LNCS, Vol. 7881, Springer, 2013, pp. 1–17.

34.

Garg ,

Gentry ,

Halevi ,

Raykova ,

Sahai and

Waters , Candidate indistinguishability obfuscation and functional encryption for all circuits, in: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, IEEE Computer Society, 2013, pp. 40–49.

35.

Garg ,

Gentry ,

Halevi ,

Sahai and

Waters , Attribute-based encryption for circuits from multilinear maps, in: Advances in Cryptology – CRYPTO 2013, LNCS, Vol. 8043, Springer, 2013, pp. 479–499.

36.

Gertner ,

Malkin and

Reingold , On the impossibility of basing trapdoor functions on trapdoor predicates, in: 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, IEEE Computer Society, 2001, pp. 126–135.

37.

Goldreich ,

Goldwasser and

Micali , How to construct random functions, J. ACM 33(4) (1986), 792–807.

38.

Goldwasser and

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

39.

Hanaoka and

Kurosawa , Efficient chosen ciphertext secure public key encryption under the computational Diffie–Hellman assumption, in: Advances in Cryptology – ASIACRYPT 2008, LNCS, Vol. 5350, Springer, 2008, pp. 308–325.

40.

Haralambiev ,

Jager ,

Kiltz and

Shoup , Simple and efficient public-key encryption from computational Diffie–Hellman in the standard model, in: Public Key Cryptography – PKC 2010, LNCS, Vol. 6056, Springer, 2010, pp. 1–18.

41.

Håstad ,

Impagliazzo ,

L.A.

Levin and

Luby , A pseudorandom generator from any one-way function, SIAM J. Comput. 28(4) (1999), 1364–1396.

42.

Hazay ,

López-Alt ,

Wee and

Wichs , Leakage-resilient cryptography from minimal assumptions, in: Advances in Cryptology – EUROCRYPT 2013, LNCS, Vol. 7881, Springer, 2013, pp. 160–176.

43.

Hofheinz and

Kiltz , Secure hybrid encryption from weakened key encapsulation, in: Advances in Cryptology – CRYPTO 2007, LNCS, Vol. 4622, Springer, 2007, pp. 553–571.

44.

Hofheinz and

Kiltz , Practical chosen ciphertext secure encryption from factoring, in: Advances in Cryptology – EUROCRYPT 2009, LNCS, Vol. 5479, Springer, 2009, pp. 313–332.

45.

Hohenberger ,

A.B.

Lewko and

Waters , Detecting dangerous queries: A new approach for chosen ciphertext security, in: Advances in Cryptology – EUROCRYPT 2012, LNCS, Vol. 7237, Springer, 2012, pp. 663–681.

46.

Hohenberger ,

Sahai and

Waters , Replacing a random oracle: Full domain hash from indistinguishability obfuscation, in: Advances in Cryptology – EUROCRYPT 2014, LNCS, Vol. 8441, Springer, 2014, pp. 201–220.

47.

Impagliazzo , A personal view of average-case complexity, in: Proceedings of the Tenth Annual Structure in Complexity Theory Conference, STOC 1995, IEEE Computer Society, 1995, pp. 134–147.

48.

Kiayias ,

Papadopoulos ,

Triandopoulos and

Zacharias , Delegatable pseudorandom functions and applications, in: 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS 2013, ACM, 2013, pp. 669–684.

49.

Kiltz , On the limitations of the spread of an ibe-to-pke transformation, in: Public Key Cryptography – PKC 2006, LNCS, Vol. 3958, Springer, 2006, pp. 274–289.

50.

Kiltz ,

Mohassel and

O’Neill , Adaptive trapdoor functions and chosen-ciphertext security, in: Advances in Cryptology – EUROCRYPT 2010, LNCS, Vol. 6110, Springer, 2010, pp. 673–692.

51.

Kiltz ,

Pietrzak ,

Stam and

Yung , A new randomness extraction paradigm for hybrid encryption, in: Advances in Cryptology – EUROCRYPT 2009, LNCS, Vol. 5479, Springer, 2009, pp. 590–609.

52.

Kiltz and

Vahlis , Cca2 secure ibe: Standard model efficiency through authenticated symmetric encryption, in: CT-RSA, LNCS, Vol. 4964, Springer, 2008, pp. 221–238.

53.

Kurosawa and

Desmedt , A new paradigm of hybrid encryption scheme, in: Advances in Cryptology – CRYPTO 2004, LNCS, Vol. 3152, Springer, 2004, pp. 426–442.

54.

Lin and

Tessaro , Amplification of chosen-ciphertext security, in: Advances in Cryptology – EUROCRYPT 2013, LNCS, Vol. 7881, Springer, 2013, pp. 503–519.

55.

Matsuda and

Hanaoka , Chosen ciphertext security via point obfuscation, in: TCC 2014, LNCS, Vol. 8349, Springer, 2014, pp. 95–120.

56.

Naor and

Reingold , Number-theoretic constructions of efficient pseudo-random functions, J. ACM 51(2) (2004), 231–262.

57.

Naor and

Yung , Public-key cryptosystems provably secure against chosen ciphertext attacks, in: Proceedings of the 22th Annual ACM Symposium on Theory of Computing, STOC 1990, ACM, 1990, pp. 427–437.

58.

Pass ,

Seth and

Telang , Indistinguishability obfuscation from semantically-secure multilinear encodings, in: Advances in Cryptology – CRYPTO 2014, LNCS, Vol. 8616, Springer, 2014, pp. 500–517.

59.

Peikert , Lattice cryptography for the Internet, in: Post-Quantum Cryptography – 6th International Workshop, PQCrypto 2014, LNCS, Vol. 8772, Springer, 2014, pp. 197–219.

60.

Peikert and

Waters , Lossy trapdoor functions and their applications, in: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC 2008, ACM, 2008, pp. 187–196.

61.

Rabin , Probabilistic algorithms in finite fields, SIAM Journal on Computation 9 (1981), 273–280.

62.

Rivest ,

Shamir and

Adleman , A method for obtaining digital signatures and public key cryptosystems, Communications of the ACM 21(2) (1978), 120–126.

63.

Rosen and

Segev , Chosen-ciphertext security via correlated products, SIAM J. Comput. 39(7) (2010), 3058–3088.

64.

Sahai and

Waters , Fuzzy identity based encryption, in: Advances in Cryptology – EUROCRYPT 2005, LNCS, Vol. 3494, Springer, 2005, pp. 457–473.

65.

Sahai and

Waters , How to use indistinguishability obfuscation: Deniable encryption, and more, in: Symposium on Theory of Computing, STOC 2014, ACM, 2014, pp. 475–484.

66.

Wee , Efficient chosen-ciphertext security via extractable hash proofs, in: Advances in Cryptology – CRYPTO 2010, LNCS, Vol. 6223, Springer, 2010, pp. 314–332.

67.

Zhandry , How to avoid obfuscation using witness prfs, in: Theory of Cryptography – 13th International Conference, TCC 2016-A, LNCS, Vol. 9563, Springer, 2016, pp. 421–448.