Publicly evaluable pseudorandom functions and their applications

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

A preliminary version of this paper appears in SCN 2014 (9th Conference on Security and Cryptography for Networks).

1. Introduction

Pseudorandom functions (PRFs) [37] are a fundamental concept in modern cryptography. Loosely speaking, PRFs are a family of keyed functions $F : SK \times X \to Y$ such that: (1) it is easy to sample the functions and compute their values, i.e., given a secret key $sk$ , one can efficiently evaluate $F_{sk} (x)$ at all points $x \in X$ ; (2) given only black-box access to the function, no probabilistic polynomial-time (PPT) algorithm can distinguish $F_{sk}$ for a randomly chosen $sk$ from a real random function, or equivalently, without $sk$ no PPT algorithm can distinguish $F_{sk} (x)$ from random at all points $x \in X$ .

In this work, we extend the standard PRFs to what we call publicly evaluable PRFs, which partially fill the gap between the evaluation power with and without secret keys. In a publicly evaluable PRF, there exists a language $L \subseteq X$ with a hard relation $R_{L}$ , and each secret key $sk$ is associated with a public key $pk$ . In addition, for any $x \in L$ , except via a private evaluation algorithm with $sk$ , one can also efficiently compute the value of $F_{sk} (x)$ via a public evaluation algorithm with the corresponding public key $pk$ and a witness w for $x \in L$ . Regarding the security requirement for PEPRFs, we require weak pseudorandomness which ensures that no PPT adversary can distinguish $F_{sk}$ from a real random function on uniformly distributed challenge points in L (this differs from the standard pseudorandomness for PRFs in which challenge points are arbitrarily chosen by an adversary).

While PEPRFs are a conceptually simple extension of standard PRFs, they have surprisingly powerful applications beyond what is possible with standard PRFs. Most notably, as we will see shortly, they admit a simple and black-box construction of PKE.

1.1. Motivation

PRFs have a wide range of applications in cryptography. Perhaps the most simple application is an elegant construction of private-key encryption as follows: the secret key $sk$ of PRFs serves as the private key; to encrypt a message m, a sender first chooses a random $x \in X$ , and then outputs a ciphertext $(x, m \oplus F_{sk} (x))$ . It is tempting to think whether PRFs also yield PKE in the same way. However, the above construction fails in the public-key setting when $F$ is a standard PRF. This is because without $sk$ no PPT algorithm can evaluate $F_{sk} (x)$ (otherwise this violates the pseudorandomness of PRFs) and thus it is impossible to encrypt publicly. Moreover, since PRFs and one-way functions (OWFs) imply each other [37,41], the implications of PRFs are inherently confined in $Minicrypt$ .1

¹
According to [47], $Minicrypt$ refers to the world where one-way functions exist, but public-key cryptography does not; while $Cryptomania$ refers to the world where public-key cryptography is possible.

This result rules out the possibilities of constructing PKE from PRFs in a black-box manner.

Meanwhile, most existing PKE schemes based on various concrete hardness assumptions can be casted into several paradigms or general assumptions in the literature. In details, hash proof systems [27] encompass the PKE schemes [26,28,51,53], extractable hash proof systems [66] encompass the PKE schemes [14,16,40,44,49], one-way trapdoor permutations/functions encompass the PKE schemes [60–63].2

The references [61,62] actually refer to the padded version of RSA encryption and Rabin encryption.

However, the celebrated Goldwasser–Micali PKE [38] and ElGamal PKE [32] do not fit into any known paradigms or general assumptions.

Recently, indistinguishability obfuscation ( $i O$ ) together with puncturable PRFs (PPRFs) have proven to be an extremely powerful combination and have been used to construct a variety of cryptographic primitives, such as PKE, short signature, non-interactive zero knowledge proof, oblivious transfer [65], multiparty key exchange and traitor tracing [13], etc. On one hand, while these results are exciting, existing instantiations of candidate obfuscators [2,3,34,58] have several drawbacks in terms of efficiency [67] and inherently rely on multilinear maps. On the other hand, we observe that in the constructions of PKE and multiparty key exchange $i O$ is in fact compiling PPRFs into some kind of “publicly computable” PRFs as an intermediate primitive, which are in turn sufficient for the applications. However, no such “publicly computable” PRFs is known to date.

Motivated by the above discussion, we ask the following intriguing questions:

Can we adapt the concept of PRFs to the public-key setting? If so: Can it enable the above PRF-based private-key encryption to work the public-key setting? Can it be instantiated from standard assumptions? Can it be used to explain unclassified PKE schemes?

Fig. 1.

Summary of main results in this work. The bold lines and rectangles denote our contributions and our new concepts, while the dashed lines denote those from existing works.

1.2. Our contributions

We give positive answers to the above questions. Our main results (summarized in Fig. 1) are as follows:

In Section 3, we introduce the notion of publicly evaluable PRFs (PEPRFs), which is a counterpart of standard PRFs in the public-key setting. In a PEPRF, there is a language $L \subseteq X$ defined by a hard relation $R_{L}$ , and each secret key $sk$ is associated with a public key $pk$ . For any $x \in L$ , except via a private evaluation algorithm with $sk$ , one can efficiently evaluate $F_{sk} (x)$ using $pk$ and a witness w for $x \in L$ . We also formalize security notions for PEPRFs, namely weak pseudorandomness and adaptive weak pseudorandomness.

In Section 4, we demonstrate the power of PEPRFs by showing that they enable the PRF-based private-key encryption to work in the public-key setting, following the KEM-DEM methodology. In sketch, the public/secret key for PEPRF serves as the public/secret key for PKE. To encrypt a message m, a sender first samples a random $x \in L$ with witness w, then publicly evaluates $F_{sk} (x)$ from $pk$ , x and w, and outputs a ciphertext $(x, m \oplus F_{sk} (x))$ . To decrypt, a receiver simply uses $sk$ to compute $F_{sk} (x)$ privately, then recovers m. Such construction is simple, black-box, and admits a direct proof of security.3

³
For simplicity, we treat PKE schemes as key encapsulation mechanisms (KEM) in this work. It is well known that one can generically obtain a fully fledged CCA-secure PKE by combining a CCA-secure KEM (the requirement on KEM could be weaker [43]) and a data encapsulation mechanism (DEM) with appropriate security properties [28,52,53].

In particular, in Section 3.1 we show that the celebrated Goldwasser–Micali PKE and ElGamal PKE can be explained neatly by weak pseudorandom PEPRFs based on the quadratic residuosity assumption and the decisional Diffie–Hellman assumption, respectively.

In Section 5, Section 6 and Section 7, we show how to construct PEPRFs from trapdoor functions (TDFs), hash proof systems (HPSs), and extractable hash proof systems (EHPSs), respectively. This indicates that previous works on TDFs, HPSs and EHPSs implicitly constructed PEPRFs. Therefore, PEPRFs are abstraction of the common aspect of HPSs and EHPSs which are not formalized before. Moreover, existing constructions of TDFs, HPS and EHPS imply that PEPRFs can be instantiated from a variety of number-theoretic assumptions. In Section 8, we show that recent work [65] essentially suggests a way to compile puncturable PRFs to adaptive weak pseudorandom PEPRFs via indistinguishability obfuscator. This result reinforces the intuition that in several obfuscation-based constructions the indistinguishability obfuscator is in fact compiling puncturable PRFs into some kind of publicly computable PRFs as an intermediate object.

In Section 9, we introduce the notion of publicly sampleable PRFs (PSPRFs), which is a relaxation of PEPRFs, but nonetheless implies PKE. Of independent interest, we redefine the notion of trapdoor relations (TDRs). We show that injective TDFs imply “one-to-one” TDRs, while the latter further imply PSPRFs. This implication helps us to unify and clarify more PKE schemes based on different paradigms and general assumptions from a conceptual standpoint, and also suggests adaptive PSPRFs as a candidate of the weakest general assumption for CCA-secure PKE.

In Section 10, we introduce an extension of PEPRFs named publicly evaluable constrained PRFs (PECPRFs). An immediate application of PECPRFs is attribute-based encryption. We also present an instantiation of PECPRFs based on an attribute-based encryption scheme from multilinear maps [35].

In Section 11, we propose a twist on PEPRFs named publicly evaluable and verifiable functions (PEVFs), which enjoy an additional property named public verifiability and only require unpredictability rather than weak pseudorandomness. We demonstrate the utility of PEVFs by presenting a simple construction of “hash-and-sign” signatures, both in the random oracle model and the standard model.

1.3. Related work

CCA-secure PKE from general assumptions or paradigms. Except the effort on constructing CCA-secure PKE from specific assumptions [39,55] or from encryption schemes satisfying some weak security notions [10,25,29,31,45,54,57], it is of great theoretical interest to build CCA-secure PKE from general assumptions and paradigms. Cramer and Shoup [27] generalized their CCA-secure PKE construction [26] to the notion of hash proof systems (HPSs) and used it as a paradigm to construct CCA-secure PKE from various decisional assumptions. Kurosawa and Desmedt [53] and Kiltz et al. [51] later improved upon the original HPS paradigm. Peikert and Waters [60] proposed lossy trapdoor functions (LTDFs) and showed a black-box construction of CCA-secure PKE from them. Rosen and Segev [63] introduced correlated-product secure trapdoor functions (CP-TDFs) and also showed a construction of CCA-secure PKE from them. Moreover, they showed that CP-TDFs are strictly weaker than LTDFs by giving a black-box separation between them. Kiltz et al. [50] introduced (injective) adaptive trapdoor functions (ATDFs) which are strictly weaker than both LTDFs and CP-TDFs but suffice to imply CCA-secure PKE. Wee [66] introduced the notion of extractable hash proof systems (EHPSs) and used it as a paradigm to construct CCA-secure PKE from various search assumptions. Wee also showed that both EHPS and ATDFs imply (injective) adaptive trapdoor relations (ATDRs), which are sufficient to imply CCA-secure PKE. To the best of our knowledge, the notion of ATDRs is the weakest general assumption that implies CCA-secure PKE.

Constrained PRFs. Very recently, constrained PRFs are studied in three concurrent and independent works, by Kiayias et al. [48] under the name of delegatable PRFs, by Boneh and Waters [12] under the name of constrained PRFs, and by Boyle, Goldwasser, and Ivan [15] under the name of functional PRFs. In constrained PRFs, the secret key admits a delegation for a family of circuits, and the delegated key for circuit f enable one to compute the PRF value at any point x such that $f (x) = 1$ . This natural extension turns out to be useful since it has powerful applications outside the scope of standard PRFs, such as identity-based key exchange, and optimal private broadcast encryption.

Witness PRFs. Independently and concurrently of our work, Zhandry [67] introduces the notion of witness PRFs (WPRFs), which is similar in concept to PEPRFs. In a nutshell, both WPRFs and PEPRFs are defined with respect to a language and extend standard PRFs with the same extra functionality, i.e., one can publicly evaluate $F_{sk} (x)$ for $x \in L$ with its witness. The main differences between WPRFs and PEPRFs are as follows:

In WPRFs the associated relation of the language is required to be polynomially bounded, while in PEPRFs the associated relation of the language is required to be hard.

WPRFs require that $F_{sk} (x)$ is pseudorandom for any adversarially chosen $x \in X ∖ L$ , while PEPRFs only require that $F_{sk} (x)$ is pseudorandom for randomly chosen $x \in L$ .

WPRFs are introduced as a weaker primitive to replace indistinguishability obfuscation for several obfuscation-based applications. By utilizing the reduction from any

NP

language to the subset-sum problem, WPRFs can handle arbitrary

NP

languages. However, for applications of WPRFs whose functionalities rely on

F_{sk} (x)

for

x \in L

, such as public-key encryption, non-interactive key exchange, and hardcore functions for any one-way function, the underlying

NP

languages have to be at least hard-on-average (i.e., the associated relation is hard). This is because these applications usually need the indistinguishability between

x \overset{R}{\leftarrow} L

and

x \overset{R}{\leftarrow} X ∖ L

to argue

F_{sk} (x)

is computationally pseudorandom for

x \overset{R}{\leftarrow} L

2. Preliminaries

2.1. Basic notations

We review the basic terminology used throughout the paper. For a distribution or a set S, we write $s \overset{R}{\leftarrow} S$ to denote the operation of sampling s according to S or uniformly at random from S, and use $| S |$ to denote its size. For a set S, we let $U_{S}$ denote the uniform distribution over S.

We let $N$ denote the positive integers. The natural security parameter throughout the paper is λ, and all other quantities as well as all algorithms (including the adversary) are implicitly functions of λ. We write $poly (λ)$ to denote an arbitrary polynomial function in λ. We write $negl (λ)$ to denote an arbitrary negligible function in λ, which vanishes faster than the inverse of any polynomial. We say a probability is overwhelming if it is $1 - negl (λ)$ , and said to be noticeable if it is $1 / poly (λ)$ . A probabilistic polynomial-time (PPT) algorithm is a randomized algorithm that runs in time $poly (λ)$ . If $A$ is a randomized algorithm, we write $z \leftarrow A (x_{1}, \dots, x_{n}; r)$ to indicate that $A$ outputs z on inputs $(x_{1}, \dots, x_{n})$ and randomness r. We will omit r and write $z \leftarrow A (x_{1}, \dots, x_{n})$ . In addition, we assume an algorithm always outputs ⊥ when its input is ⊥.

The statistical distance between two random variables X and Y having a common domain S is $Δ [X, Y] = \frac{1}{2} \sum_{s \in S} | Pr [X = s] - Pr [Y = s] |$ . We write $\approx_{c}$ as shorthand for computationally indistinguishable.

2.2. Languages and relations

Cryptographic hard problems are usually given by a set of instances, which we denote by X. We call a subset L of X as a language, in which all its elements meet some property. Typically, a language L can be associated with a binary relation $R_{L} \subseteq X \times W$ , i.e., $x \in L \Leftrightarrow \exists w \in W$ s.t. $(x, w) \in R_{L}$ . The only restriction is that if $(x, w) \in R_{L}$ , then $| w | ⩽ poly (| x |)$ . We call $w \in W$ a witness for the membership of $x \in L$ . We recall some properties of relations as below.

Easy to sample a tuple: There exists a PPT algorithm $SampRel$ that on input a public description $pp$ for $R_{L}$ and fresh random coins r, outputs a random tuple $(x, w) \in R_{L}$ . We can further decompose $SampRel$ to $SampLan$ and $SampWit$ . The former on input $pp$ and r outputs $x \in L$ , while the latter on input $pp$ and r outputs $w \in W$ .4

⁴
When the context is clear, we usually omit $pp$ from the input of $SampRel$ .

Hereafter, let R be the random coins space of

SampRel

SampLan

, and

SampWit

. We require that for any

r \in R

, it holds that

(SampLan (r), SampWit (r)) \in R_{L}

Hard to find a witness: Given x where $(x, w) \leftarrow SampRel (pp; r)$ , no PPT algorithm can compute $w^{'}$ such that $(x, w^{'}) \in R_{L}$ with non-negligible probability.

Easy to verify a tuple: $R_{L}$ is polynomially-verifiable (i.e., $R_{L} \in P$ ).

We say a relation

R_{L}

is hard or one-way if it satisfies the first two properties. We say a relation

R_{L}

is polynomially bounded if it satisfies the third property. Polynomially bounded relations define the usual

NP

language. Definition 2.1 (Subset membership problem).

Let $L \subset X$ be a language, and both L and $X ∖ L$ allow efficiently uniform sampling (let $SampYes$ and $SampNo$ be the sampling algorithms respectively5

⁵
Without loss of generality, we assume $SampYes$ and $SampLan$ induce identical distribution over L.

). We say subset membership problem w.r.t.

(X, L)

is hard if:

\begin{matrix} U_{X ∖ L} \approx_{c} U_{L} . \end{matrix}

2.3. Pseudorandom functions

We first recap the definition of PRFs in order to compare them with PEPRFs more clearly.

Definition 2.2 (PRFs [37]).

A family of PRFs consists of three polynomial-time algorithms as follows:

$Setup (1^{λ})$ : on input $1^{λ}$ , output public parameters $pp = (F, SK, X, Y)$ (the sets $SK$ , X, and Y may be parameterized by λ), where $F : SK \times X \to Y$ can be viewed as a keyed function indexed by $SK$ , namely $F = {F_{sk}}_{sk \in SK}$ .

$KeyGen (pp)$ : on input $pp$ , output a secret key $sk \in SK$ .

$PrivEval (sk, x)$ : on input $sk$ and $x \in X$ , output $y \in Y$ .

Correctness.
For any $λ \in N$ , any $pp \leftarrow Setup (1^{λ})$ , any $sk \leftarrow KeyGen (pp)$ and any $x \in X$ , we have $F_{sk} (x) = PrivEval (sk, x)$ .
Security.
The standard security requirement for PRFs is pseudorandomness. Let $A$ be an adversary against PRFs and define its advantage as: $\begin{matrix} {Adv}_{A} (λ) = Pr [b = b^{'} : \begin{matrix} pp \leftarrow Setup (1^{λ}); \\ sk \leftarrow KeyGen (pp); \\ b \leftarrow {0, 1}; \\ b^{'} \leftarrow A^{O_{ror} (b, \cdot)} (pp) \end{matrix}] - \frac{1}{2}, \end{matrix}$ where $O_{ror} (0, x) = F_{sk} (x)$ , $O_{ror} (1, x) = H (x)$ (here $H$ is chosen uniformly at random from all the functions from X to Y6
⁶
To efficiently simulate access to a uniformly random function $H$ from X to Y, one may think of a process in which the adversary’s queries to $O_{ror} (1, \cdot)$ are “lazily” answered with independently and randomly chosen elements in Y, while keeping track of the answers so that queries made repeatedly are answered consistently.

). Note that $A$ can adaptively access the oracle $O_{ror} (b, \cdot)$ polynomial many times. We say that PRFs are pseudorandom if for any PPT adversary its advantage function ${Adv}_{A} (λ)$ is negligible in λ. We refer to such security as full PRF security.

Sometimes the full PRF security is not needed and it is sufficient if the function cannot be distinguished from a uniform random one when challenged on random inputs. The formalization of such relaxed requirement is weak pseudorandomness (weak PRF security), which is defined the same way as the full PRF security except that the inputs of oracle $O_{ror} (b, \cdot)$ are uniformly chosen from X by the challenger instead of adversarially chosen by $A$ . PRFs that satisfy weak pseudorandomness are referred to as weak PRFs.

3. Publicly evaluable PRFs

Here we define PEPRFs. We begin with the syntax and then define the security.

Definition 3.1 (Publicly evaluable PRFs).

A family of PEPRFs consists of four polynomial-time algorithms as below:

$Setup (1^{λ})$ : on input $1^{λ}$ , output public parameters $pp$ which includes $(F, PK, SK, X, L, W, Y)$ , where $F : SK \times X \to Y \cup ⊥$ could be viewed as a keyed function indexed by $SK$ , $L \subseteq X$ is a language defined by some hard relation $R_{L}$ , and W is the set of associated witnesses. We assume $R_{L}$ is efficiently sampleable, that is, there exists a PPT algorithm $SampRel$ which on input random coins r, output a random tuple $(x, w) \in R_{L}$ .

$KeyGen (pp)$ : on input $pp$ , output a secret key $sk$ and an associated public key $pk$ .7

⁷
In a standard PRF, it is also harmless to explicitly introduce a public key, which includes the information related to secret key that can be made public. For example, in the Naor–Reingold PRF [56] based on the DDH assumption: $F_{\vec{a}} (x) = {(g^{a_{0}})}^{\prod_{x_{i} = 1} a_{i}}$ , where $\vec{a} = (a_{0}, a_{1}, \dots, a_{n}) \in Z_{p}^{n}$ is the secret key, $g^{a_{i}}$ for $1 ⩽ i ⩽ n$ can be safely published as the public key. If no information can be made public, one can always assume $pk = {⊥}$ .

$PrivEval (sk, x)$ : on input $sk$ and $x \in X$ , output $y \in Y \cup ⊥$ .

$PubEval (pk, x, w)$ : on input $pk$ and $x \in L$ together with a witness $w \in W$ , output $y \in Y$ .

Correctness.

For any $λ \in N$ , any $pp \leftarrow Setup (1^{λ})$ and any $(pk, sk) \leftarrow KeyGen (pp)$ , we have: $\begin{array}{rcl} \forall x \in X : F_{sk} (x) = PrivEval (sk, x), \\ \forall x \in L with a witness w : F_{sk} (x) = PubEval (pk, x, w) . \end{array}$

Security.

Let $A$ be an adversary against PEPRFs and define its advantage as: $\begin{matrix} {Adv}_{A} (λ) = Pr [b = b^{'} : \begin{matrix} pp \leftarrow Setup (1^{λ}); \\ (pk, sk) \leftarrow KeyGen (pp); \\ {r_{i}^{*} \overset{R}{\leftarrow} R, (x_{i}^{*}, w_{i}^{*}) \leftarrow SampRel (r_{i}^{*})}_{i = 1}^{p (λ)}; \\ b \leftarrow {0, 1}; \\ b^{'} \leftarrow A^{O_{eval} (\cdot)} (pp, pk, {x_{i}^{*}, O_{ror} (b, x_{i}^{*})}_{i = 1}^{p (λ)}) \end{matrix}] - \frac{1}{2}, \end{matrix}$ where $p (λ)$ is any polynomial, $O_{eval} (x) = F_{sk} (x)$ , $O_{ror} (0, x) = F_{sk} (x)$ , $O_{ror} (1, x) = H (x)$ , and $A$ is not allowed to query $O_{eval} (\cdot)$ with any $x_{i}^{*}$ . We say that PEPRFs are adaptive weak pseudorandom if for any PPT adversary $A$ its advantage function ${Adv}_{A} (λ)$ is negligible in λ.8

⁸

The readers should not be confused with adaptive PRFs [9], where “adaptive” means that instead of deciding the queries in advance, an adversary can adaptively make queries to $O_{ror} (b, \cdot)$ based on previous queries.

The adaptive weak pseudorandomness captures the security against active adversaries, who are given adaptive access to the oracle

O_{eval} (\cdot)

. We also consider weak pseudorandomness which captures the security against static adversaries, who is not given access to oracle

O_{eval} (\cdot)

On the basis of previous works [4,5,42], one can also define more advanced security notions such as security against related-key attacks and security against key-leakage attacks for PEPRFs.

Remark 3.1.

Different from standard PRFs, PEPRFs require the existence of a language $L \subseteq X$ as well as a public evaluation algorithm. Due to this strengthening on functionality, we cannot hope to achieve full PRF security, and hence settling for weak PRF security is a natural choice.9

⁹

In the full PRF security experiment the inputs of $O_{ror} (b, \cdot)$ are chosen by an adversary, thus it may know the corresponding random coins and then evaluate $F_{sk} (x^{*})$ publicly.

Note that the weak PRF security implicitly requires that the associated relation

R_{L}

is hard.

Remark 3.2.

In some scenarios, it is more convenient to work with a definition that slightly restricts an adversary’s power, but is equivalent to Definition 3.1. That is, the query times $p (λ)$ by an adversary is fixed to 1. Due to the existence of oracle $O_{eval} (\cdot)$ , a standard hybrid argument can show that PEPRFs secure under this restricted definition are also secure under Definition 3.1. In the remainder of this paper, we will work with this restricted definition.

A possible relaxation. To be completely precise, it is not necessary to require the distribution of x induced by $SampRel (r)$ conditioned on $r \overset{R}{\leftarrow} R$ is identical or statistically close to uniform. Instead, it could be some other prescribed distribution χ. In this case, weak pseudorandomness extends naturally to χ-weak pseudorandomness.

A useful generalization. In some scenarios, it is more convenient to work with a more generalized notion in which we consider a collection of languages ${L_{pk}}_{pk \in PK}$ indexed by the public key rather than a fixed language L. Correspondingly, the sampling algorithm $SampRel$ takes $pk$ as an extra input to sample a random tuple $(x, w) \in R_{L_{pk}}$ . We refer to such generalized notion as PEPRFs for public-key dependent languages, and we will work with it when constructing adaptive PEPRFs from hash proof systems.

3.1. Two simple PEPRFs from number-theoretic assumptions

In what follows, we present two illustrative constructions of PEPRFs from the quadratic residuosity (QR) assumption (cf. Appendix A.6) and the decisional Diffie–Hellman (DDH) assumption (cf. Appendix A.7), respectively.

Construction 3.1 (PEPRFs based on the QR assumption).

We build PEPRFs from the QR assumption as follows:

$Setup (1^{λ})$ : run $(N, p, q) \leftarrow GenModulus (1^{λ})$ , set $X = Z_{N}^{*}$ , $Y = {0, 1}$ , $PK = {N} \times {QNR}_{N}^{+ 1}$ , $SK = {p} \times {q}$ , $W = Z_{N}^{*}$ , $F : SK \times X \to Y$ will be defined later; L be the set of elements in $Z_{N}^{*}$ having Jacobi symbol +1. Let z be an element in ${QNR}_{N}^{+ 1}$ , we can define $L = {x : \exists w \in W s.t. x = w^{2} mod N \lor x = z w^{2} mod N}$ , the corresponding sampling algorithm $SampRel$ on input $1^{λ}$ , public key $(N, z)$ , and random coins r, picks $w \overset{R}{\leftarrow} Z_{p}$ , computes either $x = w^{2} mod N$ or $x = z w^{2} mod N$ , then outputs $(x, w)$ .

$KeyGen (pp)$ : pick $z \overset{R}{\leftarrow} {QNR}_{N}^{+ 1}$ , output $pk = (N, z)$ and $sk = (p, q)$ .

$PrivEval (sk, x)$ : output 1 if ${Jacobi}_{p} (x) = {Jacobi}_{q} (x) = 1$ and 0 otherwise. This algorithm defines $F : SK \times X \to Y$ .

$PubEval (pk, x, w)$ : output 1 if $x = w^{2} mod N$ and 0 if $x = z w^{2} mod N$ .

It is easy to verify that the above PEPRFs are weak pseudorandom based on the QR assumption. Looking ahead, applying the construction shown in Section 4 to the PEPRFs yields the Goldwasser–Micali PKE [38].

Construction 3.2 (PEPRFs based on the DDH assumption).

We build PEPRFs from the DDH assumption as follows:

$Setup (1^{λ})$ : run $(G, p, g) \leftarrow GroupGen (1^{λ})$ , set $X = Y = PK = L = G$ , $SK = W = Z_{p}$ , $F : SK \times X \to Y$ is defined as $F_{sk} (x) = x^{sk}$ ; we can define $L = {x : \exists w \in W s.t. x = g^{w}}$ ; the corresponding sampling algorithm $SampRel$ on input λ and random coins r, picks $w \overset{R}{\leftarrow} Z_{p}$ , computes $x = g^{w}$ , then outputs $(x, w)$ .

$KeyGen (pp)$ : pick $sk \overset{R}{\leftarrow} Z_{p}$ , compute $pk = g^{sk}$ , output $(pk, sk)$ .

$PrivEval (sk, x)$ : output $x^{sk}$ .

$PubEval (pk, x, w)$ : output ${pk}^{w}$ .

It is easy to verify that the above PEPRFs are weak pseudorandom based on the DDH assumption. Looking ahead, applying the construction shown in Section 4 to the PEPRFs yields exactly the plain ElGamal PKE [32].

4. KEM from publicly evaluable PRFs

In this section, we present a simple and black-box construction of KEM from PEPRFs. For compactness, we refer the reader to Appendix A.1 for the definition and security notion of KEM.

Construction 4.1 (KEM from PEPRFs).

We show how to construct KEM from PEPRFs in a black-box manner as follows:

$Setup (1^{λ})$ : run $PEPRF . Setup (1^{λ})$ to generate $pp$ as public parameters.

$KeyGen (pp)$ : run $PEPRF . KeyGen (pp)$ to generate $(pk, sk)$ .

$Encaps (pk; r)$ : run $SampRel (r)$ to generate a random tuple $(x, w) \in R_{L}$ , set x as the ciphertext c and compute $PEPRF . PubEval (pk, x, w)$ as the DEM key k, output $(c, k)$ .

$Decaps (sk, c)$ : output $PEPRF . PrivEval (sk, c)$ .

Correctness of the above KEM construction follows immediately from correctness of PEPRFs. The security of the above construction is assessed in the following theorem. The proof is straightforward, which transforms an adversary $A$ against IND-CPA security (resp. IND-CCA security) of the KEM construction to a distinguisher $B$ against weak pseudorandomness (resp. adaptive weak pseudorandomness) of PEPRFs, and thus contradicts the assumed security of the underlying PEPRFs. We refer the reader to [17] for the full proof.

Theorem 4.1.
The KEM is CPA-secure (resp. CCA-secure) if the underlying PEPRFs are weak pseudorandom (resp. adaptive weak pseudorandom).

5. Connection to trapdoor functions

Trapdoor functions (TDFs) are a fundamental primitive introduced by Diffie and Hellman [30]. In the following, we recall the syntax and security notions of TDFs and then show how to construct PEPRFs from them.

Definition 5.1 (Trapdoor functions).

A family of trapdoor functions is given by four polynomial-time algorithms as below.

$Setup (1^{λ})$ : on input $1^{λ}$ , output public parameters $pp = (TDF, PK, SK, S, U)$ , where $TDF : PK \times S \to U$ can be viewed as a keyed function indexed by $PK$ . We assume the domain S is efficiently sampleable, that is, there exists a PPT algorithm $SampDom$ , which on input random coins $r \overset{R}{\leftarrow} R$ , output a random element $s \in S$ .

$KeyGen (pp)$ : on input $pp$ , output a public key $pk$ (serve as a key for evaluation) and a corresponding secret key $sk$ (serve as a trapdoor for inversion).

$Eval (pk, s)$ : on input $pk$ and $s \in S$ , output $u \leftarrow {TDF}_{pk} (s)$ .

$TdInv (sk, u)$ : on input $sk$ and $u \in U$ , output $s \in S$ or a distinguished symbol ⊥ indicating u does not have pre-image.

Correctness.
For any $λ \in N$ , any $pp \leftarrow Setup (1^{λ})$ , any $(pk, sk) \leftarrow KeyGen (pp)$ and any $s = Eval (pk, u)$ , we have $Eval (pk, TdInv (sk, s)) = s$ .
(Adaptive) One-wayness.
Let $A$ be an inverter against TDFs and define its advantage as: $\begin{matrix} {Adv}_{A} (λ) = Pr [s \in {TDF}_{pk}^{- 1} (u^{}) : \begin{matrix} pp \leftarrow Setup (1^{λ}); \\ (pk, sk) \leftarrow KeyGen (pp); \\ u^{} \leftarrow Eval (pk, s^{}), s^{} \leftarrow SampDom (r^{}); \\ s \leftarrow A^{O_{inv} (\cdot)} (pp, pk, u^{}) \end{matrix}], \end{matrix}$ where $O_{inv} (u) = TdInv (sk, u)$ , and $A$ is not allowed to query $O_{inv} (\cdot)$ for the challenge $u^{*}$ . We say that TDFs are adaptive one-way (or simply adaptive) [50] if for any PPT inverter its advantage is negligible in λ. The standard one-wayness can be defined similarly as above except that the adversary is not given access to the inversion oracle.

Definition 5.2 (Hardcore functions).

A polynomial-time algorithm $hc : S \to Y$ is said to be a hardcore function of a family of efficiently computable functions $F : PK \times S \to U$ if for any PPT algorithm $A$ , the following two distributions are computationally indistinguishable: $\begin{matrix} (pp, pk, F_{pk} (s), hc (s)) \approx_{c} (pp, pk, F_{pk} (s), y), \end{matrix}$ where $pp \leftarrow Setup (1^{λ})$ , $pk \leftarrow KeyGen (pp)$ , $s \leftarrow SampDom (r)$ , $y \overset{R}{\leftarrow} Y$ .

Corollary 1.
Let $F$ be a family of efficiently computable injective functions. $F$ is one-way if and only if $F$ has a hardcore function $hc$ .
Construction 5.1 (Construction from TDFs).

We show how to construct PEPRFs from a family of (adaptive) injective TDFs as follows:

$Setup (1^{λ})$ : on input $1^{λ}$ , run $TDF . Setup (λ)$ to generate $pp = (TDF, PK, SK, S, U)$ for TDFs, and let $hc : S \to Y$ be a corresponding hardcore function; then create public parameters $pp = (F, PK, SK, X, L, W, Y)$ for PEPRFs as follows: set $PK$ and $SK$ the same as that of TDFs, set Y the same as that of the hardcore function, set $X = U$ , $W = S$ , $F$ will be defined latter. The algorithm $TDF . Eval$ induces a collection of languages $L = {L_{pk}}_{pk \in PK}$ over X where each $L_{pk} = {x : \exists w \in W s.t. x = TDF . Eval (pk, w)}$ . The sampling algorithm $SampRel$ on input r, runs $s \leftarrow SampDom (r)$ , computes $u \leftarrow TDF . Eval (pk, s)$ , and then outputs $x = u$ and $w = s$ . We assume the public parameters $pp$ of TDFs and PEPRFs contain essentially the same information.

$KeyGen (pp)$ : on input $pp$ , output $(pk, sk) \leftarrow TDF . KeyGen (pp)$ .

$PrivEval (sk, x)$ : on input $sk$ and $x \in X$ , output $y \leftarrow hc (TDF . TdInv (sk, x))$ . This algorithm defines $F : SK \times X \to Y \cup ⊥$ .

$PubEval (pk, x, w)$ : on input $pk$ and $x \in L_{pk}$ together with a witness w, output $y \leftarrow hc (w)$ .

Correctness of the above construction follows from correctness and injectivity of TDFs. The security of the above construction is assessed in the following theorem. The proof is straightforward, which transforms an adversary $A$ against weak pseudorandomness (resp. adaptive weak pseudorandomness) of PEPRFs to an adversary $B$ against pseudorandomness (resp. adaptive pseudorandomness) of $hc$ , and thus contradicts to the assumed one-wayness (resp. adaptive one-wayness) of the underlying TDFs. We refer the reader to [17] for the full proof.

Theorem 5.1.
PEPRFs are weak pseudorandom (resp. adaptive weak pseudorandom) if the underlying TDFs are one-way (resp. adaptive one-way).

6. Connection to hash proof systems

Hash proof systems are introduced by Cramer and Shoup [27] as a paradigm of constructing PKE from a category of decisional problems, named subset membership problems. As a warm up, we first recall the notion of HPS and then show how to construct PEPRFs from them.

Definition 6.1 (Hash proof system).

An HPS consists of the following algorithms:

$Setup (1^{λ})$ : on input $1^{λ}$ , output public parameters $pp$ which includes an HPS instance $(Λ, SK, PK, X, L, W, Π, α)$ , where $Λ : SK \times X \to Π$ can be viewed as a keyed function indexed by $SK$ , L is a language defined over X, W is the associated witness set, and α is a projection from $SK$ to $PK$ .

$KeyGen (pp)$ : on input $pp$ , pick $sk \overset{R}{\leftarrow} SK$ , compute $pk \leftarrow α (sk)$ , output $(pk, sk)$ .

$PrivEval (sk, x)$ : on input $sk$ and x, output $π = Λ_{sk} (x)$ .

$PubEval (pk, x, w)$ : on input $pk$ and $x \in L$ together with a witness w, output $π = Λ_{sk} (x)$ .

Following [27,51] we introduce the following notions and properties for Λ on $X ∖ L$ .

Collision probability.
The collision probability of Λ is defined as: $\begin{matrix} δ = max_{x, x^{} \in X ∖ L, x \neq x^{}} (\underset{sk}{Pr} [Λ_{sk} (x) = Λ_{sk} (x^{})]) . \end{matrix}$
Universal ₁ .
Λ is ϵ-universal₁ if for all $x \in X ∖ L$ , $\begin{matrix} Δ [(pk, Λ_{sk} (x)), (pk, π)] ⩽ ϵ, \end{matrix}$ where $(pk, sk) \leftarrow KeyGen (λ)$ and $π \overset{R}{\leftarrow} Π$ .

[27] introduced a relaxation of universal₁ property, named smoothness, which only requires the universal₁ property holds in the average case.
Smoothness.
Λ is ϵ-smooth if for $x \overset{R}{\leftarrow} X ∖ L$ , $\begin{matrix} Δ [(pk, Λ_{sk} (x)), (pk, π)] ⩽ ϵ, \end{matrix}$ where $(pk, sk) \leftarrow KeyGen (λ)$ and $π \overset{R}{\leftarrow} Π$ .

[27] also introduced a strengthening of universal₁ property, named universal₂ property.
Universal ₂ .
Λ is ϵ-universal₂ if for all $x, x^{} \in X ∖ L$ with $x \neq x^{}$ , $\begin{matrix} Δ [(pk, Λ_{sk} (x^{}), Λ_{sk} (x)), (pk, Λ_{sk} (x^{*}), π)] ⩽ ϵ, \end{matrix}$ where $(pk, sk) \leftarrow KeyGen (λ)$ and $π \overset{R}{\leftarrow} Π$ .

Kiltz, Pietrzak, Stam, and Yung [51] (henceforth KPSY) provides a generic transform from universal₁ to universal₂ HPS. Given a $HPS$ with hash $Λ : SK \times X \to Π$ regarding projection $α : SK \to PK$ and a family of functions $H = {h : Π \to {0, 1}^{ℓ}}$ , we can define its hashed variant ${HPS}^{H}$ with hash $Λ^{H} : {SK}^{H} \times X \to {0, 1}^{ℓ}$ regarding $α^{H} : {SK}^{H} \to {PK}^{H}$ where ${PK}^{H} = PK \times H$ , ${SK}^{H} = SK \times H$ , $Λ^{H} ((sk, h), x) = h (Λ (sk, x))$ and $α^{H} (sk, h) = (α (sk), h)$ . Note that X and L are the same for $HPS$ and ${HPS}^{H}$ .
Theorem 6.1 ([51]).

Assume Λ is $ϵ_{1}$ -universal₁ with collision probability $δ ⩽ 1 / 2$ and $H = {h : Π \to {0, 1}^{ℓ}}$ (where $ℓ ⩾ 6$ ) is a family of 4-wise independent hash functions, then $Λ^{H}$ is $ϵ_{2}$ -universal₂ for: $\begin{matrix} ϵ_{2} = 2^{ℓ - \frac{λ - 1}{2}} + 3 ϵ_{1} + δ . \end{matrix}$

In what follows, we show how to build PEPRFs from different kinds of HPSs.

Construction 6.1 (Construction from smooth HPS).

We show how to construct weak pseudorandom PEPRFs from a smooth HPS w.r.t. $L \subset X$ as follows:

$Setup (1^{λ})$ : on input $1^{λ}$ , run $HPS . Setup (1^{λ})$ to generate a smooth HPS instance $pp = (Λ, PK, SK, X, L, W, Π, α)$ , then create $pp = (F, PK, SK, X, L, W, Y)$ for PEPRFs as follows: set $PK$ , $SK$ , X, L, and W the same as that of HPS, set $F = Λ$ , $Y = Π$ . We assume the public parameters $pp$ of HPS and PEPRFs contain essentially the same information.

$KeyGen (pp)$ : on input $pp$ , output $(pk, sk) \leftarrow HPS . KeyGen (pp)$ .

$PrivEval (sk, x)$ : on input $sk$ and $x \in X$ , output $y \leftarrow HPS . PrivEval (sk, x)$ .

$PubEval (pk, x, w)$ : on input $pk$ and $x \in L$ together with a witness $w \in W$ for x, output $y \leftarrow HPS . PubEval (pk, x, w)$ .

Construction 6.2 (Construction from smooth and universal₂ HPSs).

We show how to construct adaptive weak pseudorandom PEPRFs from a smooth ${HPS}_{1}$ and an universal₂ ${HPS}_{2}$ w.r.t. same language $\tilde{L} \subset \tilde{X}$ as follows:

$Setup (1^{λ})$ : on input $1^{λ}$ , run ${HPS}_{1} . Setup (1^{λ})$ to generate a smooth HPS instance ${pp}_{1} = (Λ^{1}, {PK}_{1}, {SK}_{1}, \tilde{X}, \tilde{L}, \tilde{W}, Π_{1}, α_{1})$ , run ${HPS}_{2} . Setup (1^{λ})$ to generate an universal₂ HPS instance ${pp}_{2} = (Λ^{2}, {PK}_{2}, {SK}_{2}, \tilde{X}, \tilde{L}, \tilde{W}, Π_{2}, α_{2})$ , then build public parameters $pp = (F, PK, SK, X, L, W, Y)$ for PEPRFs from ${pp}_{1}$ and ${pp}_{2}$ as follows, sets $X = \tilde{X} \times Π_{2}$ , $Y = Π_{1} \cup ⊥$ , $PK = {PK}_{1} \times {PK}_{2}$ , $SK = {SK}_{1} \times {SK}_{2}$ , $W = \tilde{W}$ , $F$ will be defined later. The algorithm ${HPS}_{2} . PubEval$ induces a collection of languages $L = {L_{pk}}_{pk \in PK}$ over $X = \tilde{X} \times Π_{2}$ , where each $L_{pk} = {x = (\tilde{x}, π_{2}) : \exists w \in W s.t. \tilde{x} \in \tilde{L} \land π_{2} = {HPS}_{2} . PubEval ({pk}_{2}, \tilde{x}, w)}$ . The corresponding sampling algorithm $L . SampRel$ on input $pk = ({pk}_{1}, p k_{2})$ and random coins r, runs $(\tilde{x}, \tilde{w}) \leftarrow \tilde{L} . SampRel (r)$ , computes $π_{2} \leftarrow {HPS}_{2} . PubEval ({pk}_{2}, \tilde{x}, \tilde{w})$ , sets $x = (\tilde{x}, π_{2})$ , $w = \tilde{w}$ , outputs $(x, w)$ . We assume the two HPSs share a common sampling algorithm and $pp = {pp}_{1} \cup {pp}_{2}$ .

$KeyGen (pp)$ : on input $pp = {pp}_{1} \cup {pp}_{2}$ , run ${HPS}_{1} . KeyGen ({pp}_{1})$ and ${HPS}_{2} . KeyGen ({pp}_{2})$ to get $({pk}_{1}, {sk}_{1})$ and $({pk}_{2}, {sk}_{2})$ respectively, output $pk = ({pk}_{1}, p k_{2})$ , $sk = ({sk}_{1}, {sk}_{2})$ .

$PrivEval (sk, x)$ : on input $sk = ({sk}_{1}, {sk}_{2})$ and $x = (\tilde{x}, π_{2})$ , output $y \leftarrow {HPS}_{1} . PrivEval ({sk}_{1}, \tilde{x})$ if $π_{2} = {HPS}_{2} . PrivEval ({sk}_{2}, \tilde{x})$ and ⊥ otherwise. This algorithm defines $F : SK \times X \to Y \cup ⊥$ .

$PubEval (pk, x, w)$ : on input $pk = ({pk}_{1}, p k_{2})$ and an element $x = (\tilde{x}, π_{2}) \in L_{pk}$ together with a witness w, output $y \leftarrow {HPS}_{1} . PubEval ({pk}_{1}, \tilde{x}, w)$ .

The security of the above two constructions is assessed in the following theorem. Its proof is similar to the one in [27]. We refer the reader to [17] for the full proof.

Theorem 6.2.
If the underlying subset membership problem is hard, then the PEPRFs from the smooth HPSs (resp. plus the universal ₂ HPSs) are weak pseudorandom (resp. adaptive weak pseudorandom).
Remark 6.1.
To ensure the adaptive weak pseudorandomness of the above construction, we can weaken universal₂ property to weak universal₂ property, which requires the former property holds when $x^{*} \overset{R}{\leftarrow} X ∖ L$ . This is because adaptive weak pseudorandomness only stipulates pseudorandomness holds on the average case.
Construction 6.3 (Construction from universal₁ HPS).

We show how to construct adaptive weak pseudorandom PEPRFs from an universal₁ HPS w.r.t. $\tilde{L} \subset \tilde{X}$ as follows:

$Setup (1^{λ})$ : on input $1^{λ}$ , run $HPS . Setup (1^{λ})$ to generate ${pp}_{1}$ for an universal₁ HPS instance (Λ, $\tilde{PK}$ , $\tilde{SK}$ , $\tilde{X}$ , $\tilde{L}$ , $\tilde{W}$ , Π, α), then apply the KPSY-transform [51] to obtain an universal₂ ${HPS}^{H}$ , where $H$ is a family of 4-wise independent hash functions from Π to $Π^{H}$ ; then build public parameters $pp = (F, PK, SK, X, L, W, Y)$ for PEPRFs from ${pp}_{1}$ and $H$ as follows, where $X = \tilde{X} \times Π^{H}$ , $Y = Π \cup ⊥$ , $PK = \tilde{PK} \times \tilde{PK} \times H$ , $SK = \tilde{SK} \times \tilde{SK} \times H$ , $W = \tilde{W}$ , $F$ will be defined later. The algorithm $HPS . PubEval$ defines a collection of languages $L = {L_{pk}}_{pk \in PK}$ over $X = \tilde{X} \times Π^{H}$ where each $L_{pk} = {x = (\tilde{x}, π^{h}) : \tilde{x} \in \tilde{L} \land π^{h} = h (HPS . PubEval ({\tilde{pk}}_{2}, \tilde{x}, \tilde{w}))}$ . It is easy to see that a witness $\tilde{w}$ for $\tilde{x} \in \tilde{L}$ is also a witness for $x = (\tilde{x}, π^{h}) \in L_{pk}$ . The corresponding sampling algorithm on input $pk = ({\tilde{pk}}_{1}, {\tilde{pk}}_{2}, h)$ and random coins r, samples $(\tilde{x}, \tilde{w}) \leftarrow \tilde{L} . SampRel (r)$ , computes $π^{h} \leftarrow h (HPS . PubEval ({\tilde{pk}}_{2}, \tilde{x}, \tilde{w}))$ , sets $x = (\tilde{x}, π^{h})$ and $w = \tilde{w}$ , outputs $(x, w)$ .

$KeyGen (pp)$ : on input $pp = ({pp}_{1}, H)$ , run $HPS . KeyGen ({pp}_{1})$ twice independently to get $({\tilde{pk}}_{1}, {\tilde{sk}}_{1})$ and $({\tilde{pk}}_{2}, {\tilde{sk}}_{2})$ , pick $h \overset{R}{\leftarrow} H$ , set $pk = ({\tilde{pk}}_{1}, {\tilde{pk}}_{2}, h)$ , $sk = ({\tilde{sk}}_{1}, {\tilde{sk}}_{2}, h)$ , output $(pk, sk)$ .

$PrivEval (sk, x)$ : on input $sk = ({\tilde{sk}}_{1}, {\tilde{sk}}_{2}, h)$ and $x = (\tilde{x}, π^{h})$ , output $y \leftarrow HPS . PrivEval ({\tilde{sk}}_{1}, \tilde{x})$ if $π^{h} = h (HPS . PrivEval ({\tilde{sk}}_{2}, \tilde{x}))$ and ⊥ otherwise. This algorithm defines $F : SK \times X \to Y \cup ⊥$ .

$PubEval (pk, x, w)$ : on input $pk = ({\tilde{pk}}_{1}, {\tilde{pk}}_{2}, h)$ and an element $x = (\tilde{x}, π^{h}) \in L_{pk}$ together with a witness w, output $y \leftarrow HPS . PubEval ({\tilde{pk}}_{1}, \tilde{x}, w)$ .

In the above construction, we implicitly build ${HPS}^{H}$ , which is universal₂ according to Theorem 6.1. The security of the above construction is assessed in the following theorem. Its proof is similar as the one of Theorem 6.2. We refer the reader to [17] for the full proof.

Theorem 6.3.
If the underlying subset membership problem is hard, then the PEPRFs from the universal ₁ HPSs are adaptive weak pseudorandom.
Remark 6.2.
While Construction 6.1 is straightforward, Construction 6.2 and Construction 6.3 are more technically involved. The basic idea underlying the latter two constructions are similar as the CCA-secure PKE from smooth plus universal₂ HPSs [27]. That is, using a “weak” HPS to generate a random DEM key, while using a “strong” HPS to eliminate “dangerous” decapsulation queries. As we analyzed above, the minimum requirement for the weak HPS is smoothness, while the minimum requirement for the strong HPS is being universal₂. The advantage of Construction 6.2 is that both HPSs exactly satisfy the respective minimum requirements, while the disadvantage is that we have to assume that there exists a strong HPS sharing the same X and L as that of the weak HPS. On the contrary, the advantage of Construction 6.3 is that we can start from a single weak HPS and then build a strong HPS from it, while the disadvantage is that the weak HPS has to be universal₁, which is strictly stronger than smooth. It seems to us that the KPSY transform cannot convert a smooth HPS into an universal₂ one.

7. Connection to extractable hash proof systems

Extractable hash proof systems (EHPS) were introduced by Wee [66] as a paradigm of constructing PKE from search problems associated with hard relations. In the following, we recall the notion of EHPS and then show how to construct PEPRF from them.

Definition 7.1 (Extractable hash proof system).

An EHPS consists of a tuple of algorithms ( $Setup$ , $KeyGen$ , ${KeyGen}^{'}$ , $PubEval$ , $PrivEval$ , $Ext$ ) as below:

$Setup (1^{λ})$ : on input $1^{λ}$ , output public parameters $pp$ which include an EHPS instance $(H, PK, SK, L, W, Π)$ , where $H : PK \times L \to Π$ can be viewed as a keyed function indexed by $PK$ . Let $R_{L}$ be a corresponding hard relation for L, and $hc : W \to Y$ be a hardcore function for $R_{L}$ .

$KeyGen (pp)$ : on input public parameters $pp$ , output a key pair $(pk, sk)$ .

${KeyGen}^{'} (pp)$ : on input public parameters $pp$ , output a key pair $(pk, {sk}^{'})$ .

$PubEval (pk, x, r)$ : on input $pk$ , x and r, output $π = H_{pk} (x)$ where $x \leftarrow SampLan (r)$ .

$PrivEval ({sk}^{'}, x)$ : on input ${sk}^{'}$ and $x \in X$ , output $π \leftarrow H_{pk} (x)$ .

$Ext (sk, x, π)$ : on input $sk$ , $x \in X$ , and $π \in Π$ , output $w \in W$ such that $(x, w) \in R_{L}$ if $π = H_{pk} (x)$ and $w = ⊥$ if not.

In an EHPS, ${KeyGen}^{'}$ and $PrivEval$ work in the hashing mode, which are only used to establish security. An EHPS satisfies the following property:

Indistinguishable.
The first outputs (namely $pk$ ) of $KeyGen$ and ${KeyGen}^{'}$ are statistically indistinguishable.
Definition 7.2 (All-but-one extractable hash proof system).

An all-but-one (ABO) EHPS is a richer abstraction of EHPS, besides algorithms ( $Setup$ , $KeyGen$ , ${KeyGen}^{'}$ , $PubEval$ , $PrivEval$ , $Ext$ ), it has an additional algorithm ${Ext}^{'}$ .

${KeyGen}^{'} (pp, x^{*})$ : on input public parameters $pp$ and an arbitrary $x^{*} \in X$ , output a key pair $(pk, {sk}^{'})$ .

$PrivEval ({sk}^{'}, x^{*})$ : on input ${sk}^{'}$ and $x^{*}$ , output $π^{*} = H_{pk} (x^{*})$ .

${Ext}^{'} ({sk}^{'}, x, π)$ : on input ${sk}^{'}$ , $x \in X$ such that $x \neq x^{*}$ , and $π \in Π$ , output $w \in W$ such that $(x, w) \in R_{L}$ if $π = H_{pk} (x)$ and $w = ⊥$ otherwise.

In ABO EHPS, ${KeyGen}^{'}$ , $PrivEval$ , and ${Ext}^{'}$ work in the ABO hashing mode, which are only used to establish security. All-but-one EHPS satisfies the following property:

Indistinguishable.
For any $x^{*} \in X$ , the first output (namely $pk$ ) of $KeyGen$ and ${KeyGen}^{'}$ are statistically indistinguishable.
Construction 7.1 (Construction from (ABO) EHPS).

We show how to construct PEPRFs from an (ABO) EHPS as follows:

$Setup (1^{λ})$ : run $EHPS . Setup (1^{λ})$ to generate an EHPS instance $pp = (H, PK, SK, \tilde{L}, \tilde{W}, Π)$ , and let $hc : \tilde{W} \to Y$ be a hardcore function for $R_{\tilde{L}}$ ; build public parameters $pp = (F, PK, SK, X, L, W, Y)$ for PEPRFs as follows: sets $X = \tilde{X} \times Π$ , $Y = Y$ , $W = R$ , and $F$ will be defined later. The algorithm $EHPS . PubEval$ induces a collection of languages $L = {L_{pk}}_{pk \in PK}$ over $X = \tilde{X} \times Π$ where each $L_{pk} = {x = (\tilde{x}, π) : \exists w \in W s.t. \tilde{x} = SampLan (w) \land π = EHPS . PubEval (pk, \tilde{x}, w)}$ . The corresponding sampling algorithm $SampRel$ on input r, computes $\tilde{x} \leftarrow SampLan (r)$ and $π \leftarrow EHPS . PubEval (pk, \tilde{x}, r)$ , outputs $x = (\tilde{x}, π)$ and $w = r$ . We assume the public parameters $pp$ of PEPRF and EHPS essentially contains the same information.

$KeyGen (pp)$ : on input $pp$ , output $(pk, sk) \leftarrow EHPS . KeyGen (pp)$ .

$PrivEval (sk, x)$ : on input $sk$ and x, parse x as $(\tilde{x}, π)$ , compute $\tilde{w} \leftarrow EHPS . Ext (sk, \tilde{x}, π)$ , output $y \leftarrow hc (\tilde{w})$ . This algorithm defines $F_{sk} (x)$ as $hc (EHPS . Ext (sk, x))$ .

$PubEval (pk, x, w)$ : on input $pk$ and $x \in L$ together with a witness $w \in W$ for x, compute $\tilde{w} \leftarrow SampWit (w)$ , output $y \leftarrow hc (\tilde{w})$ .

The security of the above construction is assessed in the following theorem. Its proof is similar as the ones in [66]. We refer the reader to [17] for the full proof.

Theorem 7.1.
If the underlying binary relation $R_{\tilde{L}}$ is one-way, then the PEPRFs from the EHPSs (resp. ABO EHPSs) are weak pseudorandom (adaptive weak pseudorandom).

8. Connection to puncturable PRFs

Puncturable PRFs (PPRFs) are a special type of constrained PRFs, where the constrained key is associated with a single point $x^{*} \in X$ . Such constrained key allows evaluation at all points $x \neq x^{*}$ . As noted by [12,15,48], the GGM tree-based construction of PRFs from one-way functions (OWFs) [37] can be modified to construct PPRFs.

Sahai and Waters [65] showed how to construct PKE/KEM from indistinguishability obfuscator ( $i O$ ), pseudorandom generator (PRG), and PPRFs. We refer to [65] for the definitions of $i O$ and PPRFs. We observe that a slight modification of their construction essentially gives us a way to compile PPRFs to PEPRFs via $i O$ .

Construction 8.1 (Construction from PPRFs and $i O$ ).

We show how to construct PEPRFs from PPRFs and $i O$ as follows:

$Setup (1^{λ})$ : on input $1^{λ}$ , generate an $i O$ for circuit class $C_{λ}$ , a length-doubling pseudorandom generator $PRG : {0, 1}^{λ} \to {0, 1}^{2 λ}$ , and a puncturable PRF $PPRF : K \times {0, 1}^{2 λ} \to Y$ ; then build public parameters $pp = (F, PK, SK, X, L, W, Y)$ for PEPRFs, where $PK = i O (C_{λ})$ , $SK = K$ , $X = {0, 1}^{2 λ}$ , $F = PPRF$ , $W = {0, 1}^{λ}$ , and $L = {x : \exists w \in W s.t. x = PRG (w)}$ . The corresponding sampling algorithm $SampRel$ on input $r \in {0, 1}^{λ}$ , outputs $x \leftarrow PRG (r)$ and $w = r$ .

$KeyGen (pp)$ : on input $pp$ , pick a puncturable PRF key $k \in K$ as the secret key $sk$ , create an obfuscation of the program of Fig. 2 (the size of the program is padded to be the maximum of itself and of Fig. 3) as the public key $pk$ .

$PrivEval (sk, x)$ : on input $sk$ and x, output $y \leftarrow PPRF (sk, x)$ .

$PubEval (pk, x, w)$ : on input $pk$ , an element $x \in L$ together with its witness w, output $y \leftarrow pk (x, w)$ .

Fig. 2.

Program public evaluation.

Fig. 3.

Program public evaluation^*.

The security of the above construction is assessed in the following theorem. Its proof is similar as the one in [65]. We refer the reader to [17] for the full proof.

Theorem 8.1.

If the $i O$ is indistinguishably secure, $PRG$ is a secure pseudorandom generator, and $PPRF$ is selective pseudorandom, then the PEPRFs are adaptive weak pseudorandom.

9. Publicly sampleable PRFs

In this section, we consider a relaxation of the functionality for PEPRFs, that is, instead of requiring $F_{sk} (x)$ is publicly evaluable on L, we only require that the distribution $(x, F_{sk} (x))$ is efficiently sampleable over $L \times Y$ . More precisely, we require there exist a PPT algorithm $PubSamp$ that on input fresh random coins r, outputs $(x, y) \in L \times Y$ such that $y = F_{sk} (x)$ . We refer to this relaxed notion as publicly sampleable PRFs (PSPRFs). Clearly, PEPRFs imply PSPRFs. The (adaptive) weak pseudorandomness for PSPRFs can be defined analogously. It is easy to verify that PSPRFs and KEM imply each other by viewing $PSPRF . PubSamp$ (resp. $PSPRF . PrivEval$ ) as $KEM . Encaps$ (resp. $KEM . Decaps$ ).10

¹⁰
Without loss of generality, we assume $KEM . Decaps$ is deterministic. We note that there do exist randomized decapsulation algorithms, e.g. those that implement “implicit rejection” strategy [52]. In that case, we can view $KEM . Decaps$ as randomized PSPRFs.

In light of this observation, we view PSPRF as a high level interpretation of KEM, which allows significantly simpler and modular proof of security. In what follows, we revisit the notion of trapdoor one-way relations, and explore its relation to PSPRFs.

9.1. Trapdoor relations

Wee [66] introduced the notion of trapdoor relations (TDRs) as a functionality relaxation of injective TDFs, in which the “easy to compute” property is weakened to “easy to sample”. Wee also showed how to construct such TDRs from EHPSs.

Definition 9.1 (Trapdoor relations).

A family of trapdoor relations consists of four polynomial-time algorithms as below.

$Setup (1^{λ})$ : on input $1^{λ}$ , output public parameters $pp = (R, U, S, PK, SK)$ (these sets are parameterized by λ), and a collection of binary relations $R : U \times S$ indexed by $PK$ . We say $R$ is one-to-one if for any $pk \in PK$ , we have: (1) for any $s \in S$ there exists one and only one $u \in U$ such that $(u, s) \in R_{pk}$ ; (2) for any $u \in U$ there exists at most one $s \in S$ such that $(u, s) \in R_{pk}$ .

$KeyGen (pp)$ : on input $pp$ , output a public key $pk$ (serve as a key to sample a relation) and a secrey key $sk$ (serve as a trapdoor to find a match).

$TdInv (td, u)$ : on input $td$ and $u \in U$ , output $s \in S$ or a distinguished symbol ⊥ indicating u does not have a match under $R_{pk}$ .

$SampRel (pk; r)$ : on input $pk$ and random coins r, output a tuple $(u, s) \in R_{pk}$ .

Correctness.
For any $λ \in N$ , any $pp \leftarrow Setup (1^{λ})$ , any $(pk, sk) \leftarrow KeyGen (pp)$ , and any $(u, s) \leftarrow SampRel (pk)$ , we have $(u, TdInv (td, u)) \in R_{pk}$ .
(Adaptive) One-wayness.
Let $A$ be an inverter against TDRs and define its advantage as: $\begin{matrix} {Adv}_{A} (λ) = Pr [(u^{}, s) \in R_{pk} : \begin{matrix} pp \leftarrow Setup (λ); \\ (pk, sk) \leftarrow KeyGen (pp); \\ (u^{}, s^{}) \leftarrow SampRel (pk); \\ s \leftarrow A^{O_{inv} (\cdot)} (pp, pk, u^{}) \end{matrix}], \end{matrix}$ where $O_{inv} (u) = TdInv (sk, u)$ , and $A$ is not allowed to query $O_{inv} (\cdot)$ for the challenge $u^{*}$ . We say TDRs are adaptive one-way (or simply adaptive) if for any PPT inverter its advantage is negligible in λ. The standard one-wayness can be defined similarly as above except that the adversary is not given access to the inversion oracle.

Construction 9.1 (PSPRFs from TDRs).

We show how construct PSPRFs from one-to-one TDRs as follows:

$Setup (1^{λ})$ : run $TDR . Setup (1^{λ})$ to generate $pp = (R, U, S, PK, SK)$ , and let $hc : S \to Y$ be a hardcore function for $R$ ; build public parameters $pp = (F, PK, SK, X, L, W, Y)$ for PSPRFs as follows: set $PK$ and $SK$ the same as that of TDRs, set $X = U$ , $W = S$ , $Y = Y$ , and $F$ will be defined later. $R = {R_{pk}}_{pk \in PK}$ induces a collection of languages $L = {L_{pk}}_{pk \in PK}$ over $X = U$ where each $L_{pk} = {x : \exists w \in W s.t. (x, w) \in R_{pk}}$ . The corresponding sampling algorithm is the same as that of TDRs. We assume the public parameters $pp$ of TDRs and PEPRFs essentially contains same information.

$KeyGen (pp)$ : on input $pp$ , output $(pk, sk) \leftarrow TDR . KeyGen (pp)$ .

$PrivEval (sk, x)$ : on input $sk$ and x, output $y \leftarrow hc (TDR . TdInv (sk, x))$ . This algorithm defines $F_{sk} : X \to Y \cup ⊥$ .

$PubSamp (pk; r)$ : on input $pk$ and random coins r, compute $(x, w) \leftarrow SampRel (pk; r)$ , output $(x, hc (w))$ .

The correctness of the above construction is easy to verify. The security of the above construction is assessed by the following theorem.

Theorem 9.1.
The resulting PSPRFs are (adaptive) weak pseudorandom if the underlying TDRs are (adaptive) one-way.

We omit the proof for its straightforwardness. The above result indicates that adaptive PSPRFs are implied by adaptive TDFs. By the separation result due to Gertner, Malkin, and Reingold [36] that it is impossible of basing TDFs on trapdoor predicates, as well as the equivalence among trapdoor predicates, CPA-secure PKEs and PSPRFs, we conclude that PSPRFs are strictly weaker than TDFs in a black-box sense. We conjecture a similar separation result also exists between adaptive PSPRFs and ATDFs. Besides, whether adaptive PSPRFs are strictly weaker than general ATDRs is also unclear to us. We left this as an open problem.
10. Publicly evaluable constrained PRFs

In this section, we introduce the notion of publicly evaluable constrained PRFs (PECPRFs), which is an extension of recent constrained PRFs [12,15,48] analogous to PEPRFs of PRFs. We begin with a formal definition, and then proceed to explore possible applications.

Definition 10.1 (Publicly evaluable constrained PRFs).

Publicly evaluable constrained PRFs consists of six polynomial-time algorithms as follows:

$Setup (1^{λ})$ : on input $1^{λ}$ , output public parameters $pp$ which include finite sets $MPK$ , $MSK$ , I, X, Y, a class of circuits $F = {f : I \to {0, 1}}$ , a collection of languages $L = {L_{ind}}_{ind \in I}$ defined over X, a witness set W, as well as a PRF family $F = {F_{msk} : I \times X \to Y}_{msk \in MSK}$ . Unlike the syntax of CPRFs [12,15,48], here we explicitly define the domain as a Cartesian product of I and X. We also assume that for any $ind \in I$ one can efficiently find a circuit $f \in F$ satisfying $f (ind) = 1$ .

$KeyGen (pp)$ : on input $pp$ , output master public key $mpk$ and master secret key $msk$ .

$Constrain (msk, f)$ : on input $msk$ and a circuit $f \in F$ , output a secret key ${sk}_{f}$ .

$SampRel (ind, r)$ : on input $ind \in I$ and fresh random coins r, output a random tuple $(x, w) \in R_{L_{ind}}$ .

$PubEval (ind, x, w)$ : on input $ind \in I$ and $x \in L_{ind}$ together with a witness $w \in W$ for x, output $y \in Y$ .

$PrivEval ({sk}_{f}, x)$ : on input secret key ${sk}_{f}$ and $x \in X$ , output $y \in Y$ .

Correctness.
For any $λ \in N$ , any $pp \leftarrow Setup (1^{λ})$ , any $(mpk, msk) \leftarrow KeyGen (pp)$ , any $ind \in I$ , and any $x \in L_{ind}$ , it holds that: $\begin{array}{rcl} \forall {sk}_{f} \leftarrow Constrain (msk, f) such that f (ind) = 1 : F_{msk} (ind, x) = PrivEval ({sk}_{f}, x), \\ a witness w \in W for x \in L_{ind} : F_{msk} (ind, x) = PubEval (ind, x, w) . \end{array}$
Pseudorandomness.
Let $A = (A_{1}, A_{2})$ be an adversary against publicly evaluable constrained PRFs and defines its advantage as: $\begin{matrix} {Adv}_{A} (λ) = Pr [b = b^{'} : \begin{matrix} pp \leftarrow Setup (1^{λ}); \\ (mpk, msk) \leftarrow KeyGen (pp); \\ (state, {ind}^{}) \leftarrow A_{1}^{O_{eval} (\cdot, \cdot), O_{constrain} (\cdot)} (pp, mpk); \\ r^{} \overset{R}{\leftarrow} R, (x^{}, w^{}) \leftarrow SampRel ({ind}^{}, r^{}); \\ y_{0}^{} \leftarrow F_{msk} ({ind}^{}, x^{}), y_{1}^{} \overset{R}{\leftarrow} Y; \\ b \overset{R}{\leftarrow} {0, 1}; \\ b^{'} \leftarrow A_{2}^{O_{eval} (\cdot, \cdot), O_{constrain} (\cdot)} (state, x^{}, y_{b}^{}) \end{matrix}] - \frac{1}{2}, \end{matrix}$ where $O_{eval} (ind, x) = F_{msk} (ind, x)$ , $O_{constrain} (f) = Constrain (msk, f)$ . The adversary $A$ is restricted from querying $O_{constrain} (\cdot)$ with f such that $f ({ind}^{}) = 1$ , and the $A_{2}$ is restricted from querying $O_{eval} (\cdot, \cdot)$ with $({ind}^{}, x^{*})$ . PECPRFs are said to be adaptive weak pseudorandom if for any PPT adversary $A$ its advantage function ${Adv}_{A}$ is negligible in λ.

We can define a weaker security notion by considering adversaries who only adaptively query oracle $O_{constrain} (\cdot)$ but never query oracle $O_{eval} (\cdot, \cdot)$ . We refer to the corresponding security notion as semi-adaptive weak pseudorandomness.

It is furthermore possible and straightforward to give an analogous relaxation of publicly evaluable constrained PRFs, namely requiring that $F_{msk} (ind, \cdot)$ is publicly sampleable instead of publicly evaluable.
10.1. Attribute-based KEM from publicly evaluable constrained PRFs

Sahai and Waters [64] introduced the notion of attribute-based encryption (ABE), which admits one to implement fine-grained yet flexible access control over sensitive data. As in the public-key setting and identity-based setting, there are numerous practical reasons to prefer an attribute-based key encapsulation mechanism (AB-KEM) over an ABE. Combining a data encapsulation mechanism (DEM) with appropriate security properties with an AB-KEM yields a fully functional ABE. For IBE this was formally proven in [8]. The proof can easily be adapted to the ABE setting. We refer the readers to Appendix A.2 for the formal definition of AB-KEM.

The construction of AB-KEM from PECPRFs is almost immediate, by simply using the PRF value as a DEM key. In particular, given a PECPRF with range Y, we can construct an AB-KEM with the same index set I and the DEM key set $K = Y$ . The algorithms $Setup$ and $KeyGen$ are the same as that of the PECPRF, and the algorithm $Extract$ is the same as the algorithm $Constrain$ of PECPRF. The algorithms $Encaps$ and $Decaps$ are defined by:

$Encaps (mpk, ind)$ : on input $mpk$ and $ind \in I$ , run $PECPRF . SampRel (ind, r)$ with fresh random coins r to sample a random $x \in L_{ind}$ with a witness w for x, compute $y \leftarrow PECPRF . PubEval (ind, x, w)$ , set $c = x$ , $k = y$ and output $(c, k)$ .

$Decaps ({sk}_{f}, c)$ : on input ${sk}_{f}$ and c, output $k \leftarrow PECPRF . PrivEval ({sk}_{f}, c)$ .

Correctness of this construction follows directly from that of PECPRF. The security of the above construction is assessed in the following theorem. We omit the proof here its triviality.

Theorem 10.1.
The AB-KEM is CPA-secure (resp. CCA-secure) if the underlying PECPRFs are semi-adaptive weak pseudorandom (adaptive weak pseudorandom).
Remark 10.1.
Considering PECPRFs that supports a special class of circuits $F$ (point circuits) where each f is indexed by I and $f_{ind}$ is defined as $f_{ind} ({ind}^{'})$ iff $ind = {ind}^{'}$ . It is easy to see that such PECPRFs immediately implies an identity-based key encapsulation mechanism (IB-KEM), while itself can be generically constructed from either an identity-based hash proof system (IB-HPS) [1,18] or an identity-based extractable hash proof system (IB-EHPS) [19].

10.2. Instantiations of PECPRFs

Next we provide an instantiation of PECPRFs for general circuits from multilinear maps based on the attribute-based encryption scheme [35]. We use the same notation for circuits as in [35], which is included in Appendix A.3 for completeness. We refer the readers to Appendix A.4 for the definition of multilinear maps and the related hardness assumption.

$Setup (1^{λ}, ℓ)$ : on input $1^{λ}$ and the maximum depth ℓ of a circuit, run $MLGroupGen (1^{λ}, k = ℓ + 1)$ to generate multilinear groups $(p, {G_{i}}_{i \in [k]}, {e_{i, j}}_{i, j ⩾ 1, i + j ⩽ k})$ with canonical generators $g_{1}, \dots, g_{k}$ as public parameters $pp$ .

$KeyGen (pp)$ : on input public parameters $pp$ , choose $α \overset{R}{\leftarrow} Z_{p}$ and $h_{1}, \dots, h_{n} \overset{R}{\leftarrow} G_{1}$ , output $mpk = (g_{k}^{α}, h_{1}, \dots, h_{n})$ and $msk = {(g_{k - 1})}^{α}$ . We let $I = {0, 1}^{n}$ , $X = G_{1}^{n}$ . For any $ind \in {0, 1}^{n}$ , let $S_{ind}$ be the set of subscript indices i such that ${ind}_{i} = 1$ . We define a collection of languages $L_{ind} = {(g_{1}^{r}, {h_{i}^{r}}_{i \in S_{ind}})}_{ind \in I}$ indexed by I, where $r \in Z_{p}$ serves as the witness.

$Constrain (msk, f)$ : on input $msk = {(g_{k - 1})}^{α}$ and a circuit f, choose $s_{1}, \dots, s_{n + q} \overset{R}{\leftarrow} Z_{p}$ (where random coins $s_{w}$ is associated with wire w), first produce a “header” component ${sk}_{h} = {(g_{k - 1})}^{α - s_{n + q}}$ , then produce key components for every wire w. The structure of the key components depends upon if w is an input wire, an AND gate, or an OR gate. We describe each case as below:

Input wire. By our convention if $w \in [1, n]$ then it corresponds to the wth input. Pick $t_{w} \overset{R}{\leftarrow} Z_{p}$ , and create key component ${sk}_{w} = ({sk}_{w, 1}, {sk}_{w, 2})$ , where $\begin{matrix} {sk}_{w, 1} = g_{1}^{s_{w}} h_{w}^{t_{w}}, {sk}_{w, 2} = g_{1}^{- t_{w}} . \end{matrix}$

OR gate. Suppose that wire $w \in Gates$ and $GateType (w) = OR$ . In addition, let $j = depth (w)$ be the depth of wire w. Pick $a_{w}, b_{w} \overset{R}{\leftarrow} Z_{p}$ , and create key component ${sk}_{w} = ({sk}_{w, 1}, {sk}_{w, 2}, {sk}_{w, 3}, {sk}_{w, 4})$ , where $\begin{matrix} {sk}_{w, 1} = g_{1}^{a_{w}}, {sk}_{w, 2} = g_{1}^{b_{w}}, {sk}_{w, 3} = g_{j}^{s_{w} - a_{w} \cdot s_{A (w)}}, {sk}_{w, 4} = g_{j}^{s_{w} - b_{w} \cdot s_{B (w)}} . \end{matrix}$

AND gate. Suppose that wire $w \in Gates$ and that $GateType (w) = AND$ . In addition, let $j = depth (w)$ be the depth of wire w. Pick $a_{w}, b_{w} \leftarrow Z_{p}$ , and create key component ${sk}_{w} = ({sk}_{w, 1}, {sk}_{w, 2}, {sk}_{w, 3})$ , where $\begin{matrix} {sk}_{w, 1} = g_{1}^{a_{w}}, {sk}_{w, 2} = g_{1}^{b_{w}}, {sk}_{w, 3} = g_{j}^{s_{w} - a_{w} \cdot s_{A (w)} - b_{w} \cdot s_{B (w)}} . \end{matrix}$

$SampRel (ind, r)$ : on input $ind \in {0, 1}^{n}$ and random coins $r \in Z_{p}$ , set $x_{0} = g_{1}^{r}$ , $x_{i} = h_{i}^{r}$ for $i \in S_{ind}$ , and output $x = (x_{0}, {x_{i}}_{i \in S_{ind}}) \in L_{ind}$ and witness $w = r$ .

$PubEval (ind, x, r)$ : on input $ind \in {0, 1}^{n}$ , $x \in L_{ind}$ , and a witness $r \in Z_{p}$ , output $y = {(g_{k}^{α})}^{r}$ .

$PrivEval ({sk}_{f}, x)$ : on input a secret key ${sk}_{f}$ for a circuit $f = (n, q, A, B, GateType)$ and x (the associated $ind$ can be simply recovered from x), first compute $y^{'} = e ({sk}_{h}, g_{1}^{r}) = e (g_{k - 1}^{α - s_{n + q}}, g_{1}^{r}) = g_{k}^{α r} g_{k}^{- s_{n + q} \cdot r}$ , then evaluate the circuit from the bottom up: consider wire w at depth j, if $f_{w} (ind) = 1$ then computes $y_{w} = {(g_{j + 1})}^{s_{w} \cdot r}$ , else nothing needs to be computed for this wire. The evaluation proceeds iteratively starting from $y_{1}$ to finally $y_{n + q}$ , with the purpose of the computation on a depth $j - 1$ wire (that evaluates to 1) will be defined before computing for a depth j wire. We show how to compute $y_{w}$ for all w where $f_{w} (ind) = 1$ , again according to whether the wire is an input, AND or OR gate.

Input wire. By our convention if $w \in [1, n]$ then it corresponds to the wth input. Suppose that $f_{w} (ind) = 1$ . The algorithm computes: $\begin{matrix} y_{w} = e ({sk}_{w, 1}, g_{1}^{r}) \cdot e ({sk}_{w, 2}, x_{w}) = e (g_{1}^{s_{w}} h_{w}^{t_{w}}, g_{1}^{r}) \cdot e (g_{1}^{- t_{w}}, h_{w}^{r}) = g_{2}^{{rs}_{w}} . \end{matrix}$

OR gate. Suppose that wire $w \in Gates$ and that $GateType (w) = OR$ . In addition, let $j = depth (w)$ be the depth of wire w. Suppose that $f_{w} (ind) = 1$ . If $f_{A (w)} (ind) = 1$ (the first input evaluated to 1), then we compute: $\begin{matrix} y_{w} = e (y_{A (w)}, {sk}_{w, 1}) \cdot e ({sk}_{w, 3}, g_{1}^{r}) = e (g_{j}^{{rs}_{A} (w)}, g_{1}^{a_{w}}) \cdot e (g_{j}^{s_{w} - a_{w} \cdot s_{A (w)}}, g_{1}^{r}) = {(g_{j + 1})}^{{rs}_{w}} . \end{matrix}$ Alternatively, if $f_{A (w)} (ind) = 0$ , but $f_{B (w)} (ind) = 1$ , then we compute: $\begin{matrix} y_{w} = e (y_{B (w)}, {sk}_{w, 2}) \cdot e ({sk}_{w, 4}, g_{1}^{r}) = e (g_{j}^{{rs}_{B} (w)}, g_{1}^{b_{w}}) \cdot e (g_{j}^{s_{w} - b_{w} \cdot s_{B (w)}}, g_{1}^{r}) = {(g_{j + 1})}^{{rs}_{w}} . \end{matrix}$

AND gate. Suppose that wire $w \in Gates$ and that $GateType (w) = AND$ . In addition, let $j = depth (w)$ be the depth of wire w. Suppose that $f_{w} (ind) = 1$ . Then $f_{A (w)} (ind) = f_{B (w)} (ind) = 1$ and we compute: $\begin{array}{rcl} y_{w} & = & e (y_{A (w)}, {sk}_{w, 1}) \cdot e (y_{B} (w), {sk}_{w, 2}) \cdot e ({sk}_{w, 3}, g_{1}^{r}) \\ = & e (g_{j}^{{rs}_{A (w)}}, g_{1}^{a_{w}}) \cdot e (g_{j}^{{rs}_{B (w)}}, g_{1}^{b_{w}}) \cdot e (g_{j}^{s_{w} - a_{w} \cdot s_{A (w)} - b_{w} \cdot s_{B} (w)}, g_{1}^{r}) = {(g_{j + 1})}^{{rs}_{w}} . \end{array}$

Finally, output

y^{'} \cdot y_{n + q}

. The correctness is easy to verify by observing that if

f (ind) = f_{n + q} (ind) = 1

, then

y_{n + q} = g_{k}^{r \cdot s_{n + q}}

and the final output is

g_{k}^{α r}

The security of the above construction is based on the MDDH assumption, which follows immediately from the analysis of attribute-based encryption [35]. Applying the generic construction presented in Section 10.1 to the above PECPRF, we recover exactly the ABE scheme [35].

11. Publicly evaluable and verifiable functions

In this section, we introduce a twist on PEPRFs, which we call publicly evaluable and verifiable functions (PEVFs). Compared to PEPRFs, PEVFs have an additional property named public verifiability, while the best possible security degrades from weak pseudorandomness to unpredictability. In addition, in PEVFs $L = X$ while in PEPRFs $L \subseteq X$ .

Definition 11.1 (Publicly evaluable and verifiable functions).

A family of PEVFs consist of the following polynomial-time algorithms:

$Setup (1^{λ})$ : on input $1^{λ}$ , output public parameters $pp = (F, SK, PK, L, W, Y)$ , where $F : SK \times L \to Y$ can be viewed as a keyed function indexed by $SK$ .

$KeyGen (pp)$ : on input $pp$ , output a secret key $sk$ and an associated public key $pk$ .

$PrivEval (sk, x)$ : on input $sk$ and $x \in L$ , output $y = F_{sk} (x)$ .

$PubEval (pk, x, w)$ : on input $pk$ and $x \in L$ together with a witness $w \in W$ for x, output $y = F_{sk} (x)$ .

$PubVefy (pk, x, y)$ : on input $pk$ , x and y, output true if $y = F_{sk} (x)$ and false if not.

Security.
Let $A$ be an adversary against PEVFs and define its advantage as: $\begin{matrix} {Adv}_{A} (λ) = Pr [PubVefy (pk, x^{}, y) = 1 : \begin{matrix} pp \leftarrow Setup (1^{λ}); \\ (pk, sk) \leftarrow KeyGen (pp); \\ r^{} \overset{R}{\leftarrow} R, (x^{}, w^{}) \leftarrow SampRel (r^{}); \\ y \leftarrow A (pp, pk, x^{}) \end{matrix}] . \end{matrix}$ We say that PEVFs are unpredictable if for any PPT adversary $A$ its advantage function ${Adv}_{A} (λ)$ is negligible in λ.
Remark 11.1.
Analogous to the generalization on PEPRFs, we can also generalize PEVFs by considering public-key dependent languages ${L_{pk}}_{pk \in PK}$ rather than a fixed language L. Correspondingly, the sampling algorithm $SampRel$ takes $pk$ as an extra input to sample a random tuple $(x, w) \in R_{L_{pk}}$ . The instantiation based on the RSA assumption presented in Section 11.2 exemplifies the usefulness of such generalization.

11.1. Application of PEVFs

Construction 11.1 (Signature from PEVFs).

Now we show a simple and intuitive construction of “hash-and-sign” signature from PEVFs.

$Setup (1^{λ})$ : on input $1^{λ}$ , run $PEVF . Setup (1^{λ})$ to generate public parameters $pp$ . Let M be the message space, $H : M \to L$ be a hash function.

$KeyGen (pp)$ : run $PEVF . KeyGen (pp)$ to generate $(pk, sk)$ , output $vk = (pk, H)$ as the verification key and $sk$ as the signing key.

$Sign (sk, m)$ : on input the signing key $sk$ and a message m, compute signature $σ \leftarrow F_{sk} (H (m))$ via $PEVF . PrivEval (sk, H (m))$ .

$Verify (vk, m, σ)$ : on input $vk = (pk, H)$ , m and σ, output $PEVF . PubVefy (pk, H (m), σ)$ .

Note that the algorithm $PEVF . PubEval$ is not used in the above construction, but will prove useful in security argument.

Theorem 11.1.
The above signature is strongly unforgeable under adaptive chosen-message attack in the random oracle model if the underlying PEVFs are hard to compute on average. Suppose $H$ is a random oracle, for any adversary $A$ breaking the signature with advantage ${Adv}_{A} (λ)$ that makes at most $Q_{h}$ random oracle queries to $H$ , there is an algorithm $B$ that breaks the security of PEVFs with advantage at least ${Adv}_{A} (λ) / Q_{h}$ .
Proof.
We prove this theorem by showing how to transform an adversary $A$ against the signature into an algorithm $B$ breaking the security of the underlying PEVFs. Without loss of generality, we assume $A$ : (1) always queries the random oracle $H$ with distinct messages; (2) first queries $H (m)$ before querying the signing oracle with a message m; (3) first queries $H (m)$ before outputting a forgery $(m, σ)$ . Given $pk$ and the challenged point $x^{}$ , $B$ interacts with $A$ as follows, with the aim to compute $F_{sk} (x^{})$ .
Setup: $B$ sends $vk = (pk, H)$ to $A$ . $B$ randomly picks $j \in {1, \dots, Q_{h}}$ .

Random oracle queries: To process random oracle queries, $B$ maintains a list H which is initially empty. Each entry in H is of the form $(m, x, w)$ , where $m \in M$ , $x \in L$ and $w \in W$ . When ith random query on message $m_{i}$ comes, $B$ responds as follows:

If $i \neq j$ , $B$ picks $r_{i} \overset{R}{\leftarrow} R$ , runs $PEVF . SampRel (r_{i})$ to obtain $(x_{i}, w_{i})$ , adds the entry $(m_{i}, x_{i}, w_{i})$ to the H list, returns $x_{i}$ to $A$ .

If $i = j$ , $B$ adds the entry $(m_{j}, x^{}, ⊥)$ to the H list, returns $x^{}$ to $A$ .

Signing queries: Upon receiving the singing query on message $m_{i}$ , $B$ responds as follows:

If $i \neq j$ , $B$ responds with $σ_{i} \leftarrow PEVF . PubEval (pk, x_{i}, w_{i})$ .

If $i = j$ , $B$ aborts.

Forgery: Finally, $A$ outputs a forgery $(m_{i}, σ_{i})$ . If $i = j$ , $B$ forwards $σ_{i}$ to its own challenger. Else, $B$ aborts.
It is not difficult to verify that, unless $B$ aborts, the simulation provided for $A$ is perfect and $B$ correctly computes the PEVF value at point $x^{}$ if $A$ outputs a valid signature for $m^{}$ . It is easy to show the probability that $B$ does not abort is $1 / Q_{h}$ . The theorem immediately follows. □

Looking ahead, when applying the above generic construction to PEVFs based on the RSA assumption and the CDH assumption in bilinear groups presented in Section 11.2, yields precisely the Bellare–Rogaway signature [6] and the Boneh–Lynn–Shacham (BLS) signature [11]. We also note that the “full domain hash” (FDH) framework cannot encompass the BLS signature accurately, because there is no corresponding efficiently computable trapdoor function/permutation.

Replacing random oracle. Hohenberger, Sahai, and Waters [46] utilized $i O$ to give a way to instantiate the random oracle with a concrete hash function in FDH applications. We extend their techniques to replace the random oracle in the above construction. In what follows, we sketch how to instantiate $H$ and establish the security. Let $PPRF : K \times M \to R$ be a puncturable PRF. To build a concrete hash function for $H$ , the user first picks a master key k for $PPRF$ , then sets the hash function as an obfuscation of the program described in Fig. 4.

Fig. 4.
Hash $H$ .

The security proof will proceed via a sequence of games. Let Game 0 be the standard selective security game with hash function instantiated as described above. In Game 1, we replace the original program with an obfuscation of a “puncturable program” as described in Fig. 5, where $m^{}$ is the message that $A$ commits to attack before seeing the $vk$ , and $x^{} = SampLan (PPRF (k, m^{}))$ .

Fig. 5.
Hash $H^{}$ .

Since the input/output behaviors of the two programs are identical, Game 0 and Game 1 are computationally indistinguishable by the security of $i O$ . In Game 2, we replace $x^{} = SampLan (PPRF (k, m^{}))$ with a random element chosen from L in the program of $H^{}$ . Due to the selective pseudorandomness of $PPRF$ , Game 1 and Game 2 are computationally indistinguishable. At this moment, we can build an algorithm $B$ that breaks the security of PEVFs by invoking $A$ in Game 2. After $B$ receiving PEVF challenge $(pk, x^{})$ and $A$ ’s target message $m^{}$ , $B$ creates $k ({m^{}})$ , then uses it together with the information of $x^{}$ and $m^{}$ to build the program $H^{}$ , then sends $vk = (pk, i O (H^{}))$ to $A$ . During Game 2, $B$ is able handle signing queries for any $m \neq m^{}$ without knowing $sk$ as follows: (1) compute $r \leftarrow PPRF (k ({m^{}}), m)$ ; (2) compute $(x, w) \leftarrow SampRel (r)$ ; (3) output $σ \leftarrow PEVF . PubEval (pk, x, w)$ . Finally, $B$ simply forwards the signature $σ^{}$ on $m^{}$ as the solution of $F_{sk} (x^{})$ . We note that one could use the usual complexity leveraging arguments to claim adaptive security.
Remark 11.2.
We remark that our security proofs are both in the random oracle model and the standard model share some of the spirit of the general RO security proof for FDH signatures, where the reduction programs the challenge at one point and it is able to produce valid signatures at all others points. A distinguished aspect is that the reduction creates the signature σ for message m via different methods. In the general RO security proof for FDH signatures, the reduction first picks σ randomly from domain, then programs $H (m)$ to its trapdoor permutation $TDP (σ)$ . In contrast, in our security proofs for PEVF signatures, the reductions first programs $H (m)$ to a random element x with extra information – its witness w, then computes its signature σ as $F_{sk} (H (m))$ using the publicly evaluable property.

Randomized PEVFs.* We can further generalize the notion of PEVFs to randomized publicly evaluable and verifiable functions (RPEVFs). Briefly, RPEVFs are PEVFs whose evaluation is randomized, and the random coins is added to the image. We believe RPEVFs are suitable for admitting more applications, such as probabilistic “hash-and-sign” signatures.
11.2. Instantiations of PEVFs

Here we construct PEVFs based on the RSA assumption (cf. definition in Appendix A.5) and the CDH assumption in bilinear groups, respectively.

Construction 11.2 (PEVFs based on the RSA assumption).

Next, we show how to instantiate PEVFs from the RSA assumption.

$Setup (1^{λ})$ : run $GenModulus (1^{λ}) \to (N, p, q)$ , set $W = Y = Z_{N}^{*}$ , set $PK = SK = Z_{ϕ (N)}^{*}$ , set $L = {L_{pk}}_{pk \in PK}$ , where $L_{pk} = {x : \exists w \in W s.t. w^{pk} \equiv x mod N}$ . The corresponding sampling algorithm $SampRel$ on input $pk$ and random coins r, picks $w \overset{R}{\leftarrow} Z_{N}^{*}$ and computes $x \leftarrow w^{pk} mod N$ , then outputs $(x, w) \in R_{L}$ .

$KeyGen (pp)$ : pick $sk \overset{R}{\leftarrow} SK$ , compute $pk \leftarrow {sk}^{- 1} mod ϕ (N)$ .

$PrivEval (sk, x)$ : on input $sk$ and x, output $x^{sk} mod N$ . This algorithm defines $F_{sk}$ .

$PubEval (pk, x, w)$ : on input $pk$ , x and w, output w.

$PubVefy (pk, x, y)$ : on input $pk$ , x and y, output true if $x \equiv y^{p k} mod N$ and false if not.

Construction 11.3 (PEVFs based on the CDH assumption).

Next, we show how to instantiate PEVFs from the CDH assumption in bilinear groups.

$Setup (1^{λ})$ : run bilinear group generator $BLGroupGen (1^{λ})$ to generate $(e, g, p, G, G_{T})$ , set $L = Y = PK = G$ , set $SK = W = Z_{p}$ , set $L = {x : \exists w \in W s.t. g^{w} = x}$ . The corresponding sampling algorithm $SampRel$ on input random coins r, picks $w \overset{R}{\leftarrow} Z_{p}$ and computes $x \leftarrow g^{w}$ , then outputs $(x, w) \in R_{L}$ .

$KeyGen (pp)$ : pick $sk \overset{R}{\leftarrow} Z_{p}$ , compute $pk = g^{sk}$ .

$PrivEval (sk, x)$ : on input $sk$ and x, output $y = x^{sk}$ .

$PubEval (pk, x, w)$ : on input $pk$ , x and w, output $y = {pk}^{w}$ .

$PubVefy (pk, x, y)$ : on input $pk$ , x and y, output true if $e (pk, x) = e (g, y)$ and false if not.

Footnotes

Acknowledgments

We are grateful to Yi Deng, Qiong Huang, and Dennis Hofheinz for insightful discussions and advice. We thank the reviewers of Journal of Computer Security for many helpful comments.

Yu Chen is supported by the National Natural Science Foundation of China (Grant No. 61303257, No. 61379141), the IIE’s Cryptography Research Project (Grant No. Y4Z0061B02), the Strategic Priority Research Program of CAS (Grant No. XDA06010701), and the State Key Laboratory of Cryptology’s Open Project (Grant No. MMKFKT201511). Zongyang Zhang is an International Research Fellow of JSPS and supported by the National Natural Science Foundation of China (Grant No. 61303201).

Review of standard definitions and assumptions

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.

Publicly evaluable pseudorandom functions and their applications

Abstract

Keywords

1. Introduction

1.1. Motivation

1 According to [47], Minicrypt refers to the world where one-way functions exist, but public-key cryptography does not; while Cryptomania refers to the world where public-key cryptography is possible.

2. Preliminaries

2.1. Basic notations

2.2. Languages and relations

4 When the context is clear, we usually omit pp from the input of SampRel .

5 Without loss of generality, we assume SampYes and SampLan induce identical distribution over L.

Definition 2.2 (PRFs [37]).

Definition 3.1 (Publicly evaluable PRFs).

Construction 3.1 (PEPRFs based on the QR assumption).

Construction 3.2 (PEPRFs based on the DDH assumption).

4. KEM from publicly evaluable PRFs

Construction 4.1 (KEM from PEPRFs).

Theorem 4.1. The KEM is CPA-secure (resp. CCA-secure) if the underlying PEPRFs are weak pseudorandom (resp. adaptive weak pseudorandom). 5. Connection to trapdoor functions

Definition 5.1 (Trapdoor functions).

Corollary 1. Let F be a family of efficiently computable injective functions. F is one-way if and only if F has a hardcore function hc . Construction 5.1 (Construction from TDFs).

Theorem 5.1. PEPRFs are weak pseudorandom (resp. adaptive weak pseudorandom) if the underlying TDFs are one-way (resp. adaptive one-way). 6. Connection to hash proof systems

Definition 6.1 (Hash proof system).

Construction 6.1 (Construction from smooth HPS).

Construction 6.2 (Construction from smooth and universal2 HPSs).

Definition 7.1 (Extractable hash proof system).

Indistinguishable. The first outputs (namely pk ) of KeyGen and KeyGen ′ are statistically indistinguishable. Definition 7.2 (All-but-one extractable hash proof system).

Indistinguishable. For any x ∗ ∈ X , the first output (namely pk ) of KeyGen and KeyGen ′ are statistically indistinguishable. Construction 7.1 (Construction from (ABO) EHPS).

Theorem 7.1. If the underlying binary relation R L ˜ is one-way, then the PEPRFs from the EHPSs (resp. ABO EHPSs) are weak pseudorandom (adaptive weak pseudorandom). 8. Connection to puncturable PRFs

Construction 8.1 (Construction from PPRFs and i O ).

10 Without loss of generality, we assume KEM . Decaps is deterministic. We note that there do exist randomized decapsulation algorithms, e.g. those that implement “implicit rejection” strategy [52]. In that case, we can view KEM . Decaps as randomized PSPRFs.

Definition 9.1 (Trapdoor relations).

Definition 10.1 (Publicly evaluable constrained PRFs).

11. Publicly evaluable and verifiable functions

Definition 11.1 (Publicly evaluable and verifiable functions).

Construction 11.1 (Signature from PEVFs).

Construction 11.2 (PEVFs based on the RSA assumption).

Construction 11.3 (PEVFs based on the CDH assumption).

Footnotes

Acknowledgments

Review of standard definitions and assumptions

References

¹
According to [47], $Minicrypt$ refers to the world where one-way functions exist, but public-key cryptography does not; while $Cryptomania$ refers to the world where public-key cryptography is possible.

⁴
When the context is clear, we usually omit $pp$ from the input of $SampRel$ .

⁵
Without loss of generality, we assume $SampYes$ and $SampLan$ induce identical distribution over L.

Theorem 4.1.
The KEM is CPA-secure (resp. CCA-secure) if the underlying PEPRFs are weak pseudorandom (resp. adaptive weak pseudorandom).

5. Connection to trapdoor functions

Corollary 1.
Let $F$ be a family of efficiently computable injective functions. $F$ is one-way if and only if $F$ has a hardcore function $hc$ .
Construction 5.1 (Construction from TDFs).

Theorem 5.1.
PEPRFs are weak pseudorandom (resp. adaptive weak pseudorandom) if the underlying TDFs are one-way (resp. adaptive one-way).

6. Connection to hash proof systems

Construction 6.2 (Construction from smooth and universal₂ HPSs).

Indistinguishable.
The first outputs (namely $pk$ ) of $KeyGen$ and ${KeyGen}^{'}$ are statistically indistinguishable.
Definition 7.2 (All-but-one extractable hash proof system).

Indistinguishable.
For any $x^{*} \in X$ , the first output (namely $pk$ ) of $KeyGen$ and ${KeyGen}^{'}$ are statistically indistinguishable.
Construction 7.1 (Construction from (ABO) EHPS).

Theorem 7.1.
If the underlying binary relation $R_{\tilde{L}}$ is one-way, then the PEPRFs from the EHPSs (resp. ABO EHPSs) are weak pseudorandom (adaptive weak pseudorandom).

8. Connection to puncturable PRFs

Construction 8.1 (Construction from PPRFs and $i O$ ).

¹⁰
Without loss of generality, we assume $KEM . Decaps$ is deterministic. We note that there do exist randomized decapsulation algorithms, e.g. those that implement “implicit rejection” strategy [52]. In that case, we can view $KEM . Decaps$ as randomized PSPRFs.