Symmetric Primitives with Structured Secrets

Abstract

Securely managing encrypted data on an untrusted party is a challenging problem that has motivated the study of a wide variety of cryptographic primitives. A special class of such primitives allows an untrusted party to transform a ciphertext encrypted under one key to a ciphertext under another key, using some auxiliary information that does not leak the underlying data. Prominent examples of such primitives in the symmetric setting are key-homomorphic (weak) PRFs, updatable encryption, and proxy re-encryption. Although these primitives differ significantly in terms of their constructions and security requirements, they share two important properties: (a) they have secrets with structure or extra functionality, and (b) all known constructions of these primitives satisfying reasonably strong definitions of security are based on concrete public-key assumptions, e.g., DDH and LWE.

This raises the question of whether these objects inherently belong to the world of public-key primitives, or they can potentially be built from simple symmetric-key objects such as pseudorandom functions. In this work, we show that the latter possibility is unlikely. More specifically, we show that:

• Any (bounded) key-homomorphic weak PRF with an abelian output group implies a (bounded) input-homomorphic weak PRF, which has recently been shown to imply not only public-key encryption  but also a variety of primitives such as PIR, lossy TDFs, and even IBE.

• Any ciphertext-independent updatable encryption scheme that is forward and post-compromise secure implies PKE. Moreover, any symmetric-key proxy re-encryption scheme with reasonably strong security guarantees implies a forward and post-compromise secure ciphertext-independent updatable encryption, and hence PKE.

In addition, we show that unbounded (or exact) key-homomorphic weak PRFs over abelian groups are impossible in the quantum world. In other words, over abelian groups, bounded key-homomorphism is the best that we can hope for in terms of post-quantum security. Our attack also works over other structured primitives with abelian groups and exact homomorphisms, including homomorphic one-way functions and input-homomorphic weak PRFs.

1 Introduction

Examining the practicality and security of cryptographic primitives has always been one of the most important aspects of cryptographic research. When a new cryptographic protocol is developed, it is often somewhat inefficient and relies on a relatively strong assumption. We might ask a question that captures the essence of “lower bounds” for cryptographic algorithms: is it possible to improve this cryptosystem, or is the proposed scheme close to optimal?

A plausible approach for understanding the gap between known constructions and “reasonable” lower bounds is to determine the power of a cryptographic primitive, i.e., what other cryptographic objects can be built from it in a generic way. For instance, if a certain primitive is known to imply public-key encryption (PKE), then it does not seem likely that this primitive can be built in a generic manner from one-way functions (OWFs) [IR89, GHMM18]. However, for certain classes of primitives, this gap might be substantial.

One such class of primitives that has been studied considerably is what we will term symmetric primitives with structured secrets. Perhaps the most iconic member of this (informal) class, and one we will use to illustrate our points here, is the key-homomorphic PRF. Recall that, informally, a key-homomorphic PRF is a function $F: \mathcal {K} \times \mathcal {X} \rightarrow \mathcal {Y}$ with key space $\mathcal {K}$ and output space $\mathcal {Y}$ endowed with group operations $\oplus$ and $\otimes$, respectively, that meets all of the requirements of a pseudorandom function with the following extra property:¹

$$\begin{aligned} F \left( k_{1}, x \right) \otimes F \left( k_{2}, x \right) = F \left( k_{1} \oplus k_{2}, x \right) . \end{aligned}$$

Key-homomorphic PRFs (KHPRFs) were first implicitly shown in [NPR99] in the random oracle model and then formally defined and constructed in the standard model in [BLMR13]. There are a number of interesting applications of KHPRFs, including primitives like distributed PRFs [NPR99, BLMR13, LST18], updatable encryption [EPRS17, LT18], and PRFs that are secure against related key attacks [LMR14].

Since [BLMR13], there have been a number of works constructing improved variants of KHPRFs [BP14, BV15, BFP+15]. However, despite this quantity of research, the known constructions of KHPRFs still require powerful assumptions. For instance, we only know how to build exact key-homomorphic PRFs in the standard model from multilinear maps or related assumptions [BLMR13]. If we relax these requirements to almost KHPRFs in the standard model, all known constructions still require an LWE assumption with superpolynomial modulus. Even constructions in the random oracle model require public-key assumptions like DDH [NPR99].

All of these assumptions and constructions are seemingly very heavyweight for an ostensibly symmetric-key primitive that is typically targeted for applications in the symmetric-key setting. This leads us to a natural question: can we construct more efficient key-homomorphic PRFs, or is there some fundamental lower bound limiting their efficiency? Boneh et. al state, optimistically, “Another interesting area of research is to construct key-homomorphic PRFs whose performance is comparable to real-world block ciphers such as AES,” [BLMR13] but so far there are no known realizations of such a construction.

However, key-homomorphic PRFs are far from the only symmetric primitive with structured secrets for which the gap between known constructions and lower bounds appears to be relatively large. There are a number of other seemingly symmetric-key primitives that are only known to be implementable from concrete public-key assumptions.

Updatable Encryption. Suppose that Alice wants to perform key rotation on encrypted data in the cloud, but does not trust the cloud with her secret key. Updatable encryption, first defined in [BLMR13] as an application of key-homomorphic PRFs, allows third parties to periodically rotate encryption keys by moving ciphertexts from an old key to a new one, without actually learning the contents of the ciphertexts.

Boneh et al. [BLMR13] proposed the first formal definitions and concrete realizations of updatable encryption, which were subsequently refined by Everspaugh et al. in [EPRS17]. In a more recent work, Lehmann and Tackmann [LT18] introduced stronger security notions for updatable encryption that are desirable for real-world applications, and also pointed out that none of the existing constructions satisfy these notions. They addressed this issue by presenting a new, non-KHPRF updatable encryption protocol called RISE that achieves these stronger security requirements.

However, all of the constructions from the stronger security assumptions in [LT18] are either built from key-homomorphic PRFs or from concrete public-key assumptions. Yet again, the question remains: can we build similar schemes using simple symmetric-key primitives? Lehmann and Tackmann [LT18] are pessimistic, “secure updatable encryption schemes seem to inherently require techniques from the public-key world” but no formal bounds were given.

Proxy Re-Encryption. A proxy re-encryption scheme is a cryptosystem where, given a special update token, a third party can transform a ciphertext encrypted under Alice’s public key to a ciphertext encrypted under Bob’s public key, while learning nothing about the underlying message. Proxy re-encryption was initially developed in [BBS98] and then formalized in [AFGH05, AFGH06]. A number of subsequent works proposed improved schemes, including CCA-secure proxy re-encryption [CH07], identity-based proxy re-encryption [GA07], and CCA-secure unidirectional proxy re-encryption [LV08].

Proxy re-encryption has also been studied extensively in the symmetric-key setting [SNS11]. In particular, many of the proposed definitions and security notions associated with proxy re-encryption [nBL17, DKL+18, FKKP19] can be adopted to the symmetric-key setting. Interestingly, while some of the simpler definitions of security may be realized from known symmetric primitives, the stronger definitions only have known realizations from public-key assumptions like DDH and LWE [ABPW13, CCL+14]. This leads to the following question: are these stronger definitions of symmetric-key proxy re-encryption achievable from symmetric-key encryption?

Downside of Structure. A common property underlying each of the cryptographic primitives discussed so far is that they have structured secrets. While the presence of structure potentially allows building rich cryptosystems from simple primitives, it may also make these primitives vulnerable to potential attacks [Bar17]. This motivates us to pose the following question: can the structure inherent in KHwPRFs (and related primitives) lead to attacks?

1.1 Our Contributions

We show that the answer to many of these questions is negative. Our results can be summarized as follows:

Key-Homomorphic Weak PRFs. We show that any key-homomorphic weak PRF (KHwPRF) $F: \mathcal {K} \times \mathcal {X} \rightarrow \mathcal {Y}$ with an abelian output group $\mathcal {Y}$ implies PKE. In fact, we show that KHwPRFs with abelian output groups imply a much stronger primitive called input-homomorphic weak PRF (IHwPRF) which, by the recent work of [AMPR19], implies a large number of public-key primitives, including identity-based encryption [Sha84], private information retrieval [KO97], and lossy trapdoor functions [PW08]. In essence, our results indicate that it is seemingly unlikely that KHwPRFs, and hence KHPRFs, with abelian output groups are implied by symmetric-key primitives [IR89, GHMM18]. Our results also hold for bounded KHwPRFs with abelian output groups (encompassing nearly all applications of almost KHPRFs from lattice-based assumptions). To our knowledge, all existing constructions of KHwPRFs (and almost KHwPRFs) have abelian output groups.

Interestingly, our constructions of PKE and IHwPRF only use the output group $\mathcal {Y}$ of the KHwPRF. We use the security of the KHwPRF to argue security of our constructions. It may be possible that this seemingly novel construction technique has other applications.

These results on KHwPRFs lend evidence to support the idea that many “symmetric-key” cryptosystems that are currently only known from KHPRFs, do, in fact, belong to the world of public-key primitives. We note that some primitives (such as distributed PRFs) have KHPRF-based constructions that require abelian key and output groups, further strengthening the argument that these constructions are unlikely to be built from symmetric-key primitives.

Finally, we show how to construct a Naor-Reingold style PRF [NR97] from any key-homomorphic weak PRF. As we explain in Sect. 3.4, this allows us to construct highly parallel and potentially efficient PRFs from any KHwPRF. To the best of our knowledge, prior to this work, it was not known how to construct a Naor-Reingold style PRF from a generic primitive.

Updatable Encryption. We show that any ciphertext-independent updatable encryption scheme that satisfies the adaptive notions of forward and post-compromise security proposed in [LT18] implies PKE. As pointed out in [LT18], forward and post-compromise security are desirable for real-world applications, since they guarantee that message confidentiality is preserved even in the presence of temporary key compromise. Our result confirms the pessimism expressed in [LT18] that updatable encryption schemes with desirable security properties inherently belong to the class of asymmetric primitives.

Proxy Re-Encryption. We show that any symmetric-key proxy re-encryption scheme that satisfies the adaptive notion of indistinguishability-based security formalized in [FKKP19] implies updatable encryption with forward and post-compromise security, and hence PKE. We remark that the definition presented in [FKKP19] captures the desirable properties of proxy re-encryption, namely unidirectionality and adaptive security, and unifies the security notions achieved by a large number of existing constructions [AFGH05, AFGH06, ABH09, CCL+14].

Quantum Attacks on Primitives with Structure. We show that any exact (not bounded) homomorphic one-way function (HOWF) with abelian input and output groups can be broken in polynomial time using a quantum computer. This immediately rules out the existence of abelian, exact KHwPRFs (and hence KHPRFs) in the quantum setting. In other words, over abelian groups, KHwPRFs (and KHPRFs) with bounded homomorphism are the best that we can hope for in the quantum world.

We can also extend this attack to essentially all exact input-homomorphic weak unpredictable functions (IHwUFs) and IHwPRFs over abelian groups using the results from [AMPR19], which in turn yields quantum attacks on essentially all exact (group-)homomorphic encryption schemes over abelian groups. We note that a similar result with respect to homomorphic encryption was achieved in [AGKP14], albeit using different techniques.

1.2 Related Works

We have already discussed a number of papers related to key-homomorphic PRFs, updatable encryption, and proxy re-encryption. However, we want to note the construction [DKPW12] of Dodis et al. which showed how to build efficient MACs from key-homomorphic weak PRFs, even predating [BLMR13].

Previous works have studied the relationship between cryptographic primitives and structure. Recently, [AMPR19] examined simple primitives with structured inputs. In a work on a similar topic, Pietrzak and Sjödin [PS08] showed that weak PRFs with a certain input property imply PKE. In a different line of works that show PKE from other primitives, Berman et al. showed that laconic zero-knowledge protocols imply PKE [BDRV18], Fischlin and Harasser [FH18] showed that PKE is implied by invisible sanitizable signatures, and Rothblum [Rot11] demonstrated (homomorphic) PKE from a secret-key encryption scheme with some form of weak homomorphism. For a comprehensive treatment of PRFs and related primitives, see [BR17].

1.3 Technical Overview

In this section, we explain at a high level the techniques behind our constructions and proofs.

Key-Homomorphic Weak PRFs. Informally, a key-homomorphic weak PRF is a function $F: \mathcal {K} \times \mathcal {X} \rightarrow \mathcal {Y}$ with keyspace $\mathcal {K}$ and output space $\mathcal {Y}$ endowed with group operations $\oplus$ and $\otimes$, respectively, that meets the definition of a weak pseudorandom function² with the following extra property:

$$\begin{aligned} F \left( k_{1}, x \right) \otimes F \left( k_{2}, x \right) = F \left( k_{1} \oplus k_{2}, x \right) . \end{aligned}$$

As a warm-up, we first show that a KHwPRF with an abelian output group $\mathcal {Y}$ implies PKE. To illustrate how this works, we will show how our construction works with a simple DDH-based KHwPRF from [NPR99]³ in parallel with a generic construction. First, we use the following notation for two weak PRFs:

Now consider many instances of the same KHwPRF in parallel, with different keys. By a hybrid argument, we know that such a set of KHwPRF outputs is still indistinguishable from random. One can visualize this as follows:

Now suppose we take a random “subset sum”⁴ of the columns of these many instances of KHwPRFs in parallel. If is a random vector denoting our subset sum choice, we get new “columns” as follows:

If $\ell > 3\log |\mathcal {K}|$, then the distribution of $k^{*} = \oplus _{j = 1}^{\ell } s_{j} k_{j}$ will be statistically close to uniform over $\mathcal {K}$. This can be shown by a relatively simple application of the leftover hash lemma [IZ89]. It now follows by the pseudorandomness of the KHwPRFs F and $F_{DDH}$ that these new columns are computationally indistinguishable from random, even given the outputs of the other columns.

We now present the critical step of our argument: if such subset sums of KHwPRF outputs are indistinguishable from random even if the randomness for the subset sum is reused, then, by a series of hybrid arguments, it follows that similar subset sums of randomly chosen elements of the output group $\mathcal {Y}$ are indistinguishable from random: otherwise, we would have a distinguisher for the original KHwPRF. In other words, the following must hold:

Note that for a matrix of group elements $\mathbf {Y}\in \mathcal {Y}^{m\times \ell }$ and a vector , we denote by $\mathbf {Y}\mathbf {s}\in \mathcal {Y}^{m}$ the vector of group elements

$$\begin{aligned} \bigg (\bigotimes _{j = 1}^{\ell } s_{j} \cdot y_{1,j},\ldots ,\bigotimes _{j = 1}^{\ell } s_{j} \cdot y_{m,j}\bigg ). \end{aligned}$$

Given this hard problem, which is based on the weak pseudorandomness of F, it is simple to construct a two-party noninteractive key exchange protocol (which is sufficient for PKE), as visualized in the following figure (note that the public parameter $\textsf {pp}$ consists of an $m\times m$ matrix of uniformly chosen group elements for a fixed ).

It turns out that the technique described above is actually versatile enough to construct a number of stronger cryptographic primitives. More specifically, we show how to build an input-homomorphic weak PRF (IHwPRF), which by [AMPR19] implies a variety of public-key primitives.

Informally, an IHwPRF is a function $F': \mathcal {K} \times \mathcal {X} \rightarrow \mathcal {Y}$ with input space $\mathcal {X}$ and output space $\mathcal {Y}$ endowed with group operations $\oplus$ and $\otimes$, respectively, that also meets the definition of a weak pseudorandom function. However, the homomorphism is over the input space rather than the key space:

$$\begin{aligned} F' \left( k, x_{1} \right) \otimes F' \left( k, x_{2} \right) = F' \left( k, x_{1} \oplus x_{2} \right) . \end{aligned}$$

First, note that the DDH-based KHwPRF is already input homomorphic. But the DDH assumption is very special in this regard, and we cannot guarantee that other constructions of KHwPRFs are also implicitly IHwPRFs. In general, for a KHwPRF $F:\mathcal {K}\times \mathcal {X}\rightarrow \mathcal {Y}$, the input space $\mathcal {X}$ might not even be a group.

We now illustrate the construction of an IHwPRF from any KHwPRF with an abelian output group $\mathcal {Y}$ (where $\ell >3\log |\mathcal {K}|$):

First, note that the input homomorphism of $F'$ and $F'_{\text {DDH}}$ follows from that fact that the underlying groups $\mathcal {Y}$ and $\mathbb {G}$ are abelian, respectively. If $\mathcal {Y}$ is not abelian, then $F'$ would still be pseudorandom, but not input homomorphic. It is an interesting open problem to remove this restriction on $\mathcal {Y}$ while retaining input-homomorphism.

Notice that in the actual constructions of PKE and IHwPRF, we do not explicitly use the key space or the input space of the underlying KHwPRF; we essentially use the pseudorandomness of the KHwPRF to argue their security. In Sect. 3, we present the detailed constructions and proofs, and extend our techniques to work for almost KHwPRFs.

On the negative side, we rule out the existence of exact KHwPRFs with output groups over which a system of linear equations (with binary variables) can be solved efficiently, because such an algorithm can be used to break the hard problem instance described above, and hence to break the pseudorandomness of the underlying exact KHwPRF.⁵

Updatable Encryption. We show that any ciphertext-independent updatable encryption (UE) scheme that meets the notion of “adaptive indistinguishability of updates” formalized by Lehmann and Tackmann in [LT18] implies a PKE scheme. Recall that a UE scheme allows publishing an update token $\varDelta _{0,1}$ that can be used by a third party to transform a ciphertext encrypted under a key $\textsf {sk} _0$ to a ciphertext encrypted under another key $\textsf {sk} _1$, without knowing the underlying message.

In our PKE construction from UE, the public key consists of a pair of UE ciphertexts encrypting 0 and 1 respectively under a key $\textsf {sk} _0$, and an update token $\varDelta _{0,1}$. Depending on the plaintext bit b, the encryption algorithm updates one of the two ciphertexts, and the decryption algorithm in turn decrypts using the updated key $\textsf {sk} _1$. To prove CPA security, we show a reduction in which the challenge ciphertext for the UE game is transformed into the public key for the PKE game, which then allows us to switch between knowledge of secrets and knowledge of update tokens. The detailed construction and proof of security are presented in Sect. 4.1.

As a side note, our construction of PKE assumes that the update algorithm of the underlying UE scheme is randomized. We point out that all existing UE schemes satisfying the notion of update indistinguishability (notably, the RISE scheme in [LT18]) have randomized update algorithms.

Proxy Re-Encryption. We show that any symmetric-key proxy re-encryption scheme that satisfies the indistinguishability-based security notions formalized in [FKKP19] implies a ciphertext-independent UE scheme with indistinguishability of updates. By the result mentioned above, it thus implies a PKE scheme.

Our construction of UE from a symmetric-key PRE essentially maps PRE secret keys associated with different identifiers to UE secret keys associated with different epochs. To prove security, we show a reduction where any valid oracle query from the adversary in the UE game can be mapped into a corresponding valid oracle query to the challenger in the PRE game.

We remark that while existing PRE schemes typically support multi-hop updates [AFGH05, FKKP19], UE schemes as formalized in [LT18] support a more sequential flavor of updates. It is unlikely that such UE schemes would imply PRE schemes with desirable security properties, unless the definitions for UE are further strengthened to encompass functionalities similar to multi-hop-updates.

Quantum Attacks on Generic Primitives. In the body of the paper, we show that there exist quantum attacks on a number of generic exact primitives over abelian groups. However, since all of these attacks essentially follow from our attack on an exact homomorphic one-way function (HOWF) over an abelian group, we will focus our attention here on this attack. Informally, an HOWF is a function $f: \mathcal {X}\rightarrow \mathcal {Y}$ with input group $(\mathcal {X},\oplus )$ and output group $(\mathcal {Y},\otimes )$ (where both group operations are efficiently computable), that meets the definition of a one-way function with the following extra property:

$$\begin{aligned} f \left( x_1)\otimes f(x_2\right) = f \left( x_{1} \oplus x_{2}\right) . \end{aligned}$$

Our attack relies on the fact that there exists a quantum algorithm such that given black-box access to an abelian group $\mathcal {G}$ with certain properties, it outputs an explicit representation of the group; in other words, it outputs an isomorphism $\psi :\mathcal {G}\rightarrow \mathbb {Z}_{q_1}\oplus \cdots \oplus \mathbb {Z}_{q_m}$ such that both $\psi$ and $\psi ^{-1}$ are efficiently computable (see [CM01] and Section 6.2 of [Chi17] for more details).

At a high level, our attack works as follows: given an exact HOWF $f: \mathcal {X}\rightarrow \mathcal {Y}$ such that $\mathcal {X}$ and $\mathcal {Y}$ are both abelian groups, we use their explicit representations to construct linear systems of modular equations, and efficiently solve them to find a preimage for any given HOWF output. The detailed description of the attack is presented in Sect. 5.

2 Preliminaries

2.1 Notation

For any positive integer n, we use [n] to denote the set $\{1, \ldots , n\}$. We use $\lambda$ for the security parameter. We use the symbols $\oplus$ and $\otimes$ as group operations defined in the context. For a finite set S, we use $s \leftarrow S$ to sample uniformly from the set S.

Let $(\mathcal {Y},\otimes )$ be an efficiently samplable group, such that the group operation is efficiently computable. Let $\mathbf {Y}\in \mathcal {Y}^{m\times \ell }$ be an $m\times \ell$ matrix of group elements sampled from $\mathcal {Y}$. Also, let be an arbitrary binary vector. We denote by $\mathbf {Y}\mathbf {s}\in \mathcal {Y}^{m}$ the vector of group elements

$$\begin{aligned} \bigg (\bigotimes _{{j:s_j = 1}} y_{1,j},\ldots ,\bigotimes _{{j:s_j = 1}} y_{m,j}\bigg ). \end{aligned}$$

Similarly, let be an arbitrary binary matrix. We denote by $\mathbf {Y}\mathbf {S}\in \mathcal {Y}^{m\times \ell '}$ the matrix of group elements

$$\begin{aligned} \begin{bmatrix} \bigotimes \nolimits _{{j:s_{j,1} = 1}} y_{1,j}&\ldots&\bigotimes \nolimits _{{j:s_{j,\ell '} = 1}} y_{1,j}\\ \vdots&\ddots&\vdots \\ \bigotimes \nolimits _{{j:s_{j,1} = 1}} y_{m,j}&\ldots&\bigotimes \nolimits _{{j:s_{j,\ell '} = 1}} y_{m,j} \end{bmatrix}. \end{aligned}$$

2.2 Cryptographic Primitives

Pseudorandom Functions. Informally, an efficiently computable function is called pseudorandom if there exists no PPT adversary that can distinguish it from a truly random function. More formally, a PRF family is an efficiently computable function family $\{F(k,\cdot ): \mathcal {X}\rightarrow \mathcal {Y}\}_{k \in \mathcal {K}}$ (where K, $\mathcal {X}$ and $\mathcal {Y}$ are indexed by the security parameter $\lambda$) such that for all PPT adversaries $\mathcal {A}$ we have

where $k \leftarrow \mathcal {K}$ and $f: \mathcal {X} \rightarrow \mathcal {Y}$ is a (truly) random function.

Weak Pseudorandom Functions. Let $F^\$(k, \cdot )$ be a randomized oracle that responds to queries by sampling $x \leftarrow \mathcal {X}$ and outputting (x, F(k, x)). A weak pseudorandom function (wPRF) family is an efficiently computable function family $\{F(k,\cdot ): \mathcal {X}\rightarrow \mathcal {Y}\}_{k \in \mathcal {K}}$ (where K, $\mathcal {X}$ and $\mathcal {Y}$ are indexed by the security parameter $\lambda$) such that for all PPT adversaries $\mathcal {A}$ we have

where $k \leftarrow \mathcal {K}$ and $f: \mathcal {X} \rightarrow \mathcal {Y}$ is a (truly) random function.

Definition 1

(Homomorphic One-Way Function.) A homomorphic one-way function (HOWF) is a function $f: \mathcal {X}\rightarrow \mathcal {Y}$ with input group $(\mathcal {X},\oplus )$ and output group $(\mathcal {Y},\otimes )$ (where both group operations are efficiently computable), that meets the definition of a one-way function with the following extra property:

$$\begin{aligned} f \left( x_1)\otimes f(x_2\right) = f \left( x_{1} \oplus x_{2}\right) . \end{aligned}$$

Definition 2

(Key-Homomorphic Functions.) A function family $\{F(k, \cdot ) : \mathcal {X} \rightarrow \mathcal {Y}\}_{k \in \mathcal {K}}$ is key-homomorphic if the following conditions hold:

• $(\mathcal {K}, \oplus )$ and $(\mathcal {Y}, \otimes )$ are efficiently samplable groups, and the group operations and the inverse operation in each group are efficiently computable.

• For any pair of keys $k_1,k_2\in \mathcal {K}$ and any input $x\in \mathcal {X}$, we have

  $$\begin{aligned} F \left( k_{1}, x \right) \otimes F \left( k_{2}, x \right) = F \left( k_{1} \oplus k_{2}, x \right) . \end{aligned}$$

A key-homomorphic weak PRF (KHwPRF) family is a weak PRF family that is also key homomorphic. Similarly, a key-homomorphic PRF (KHPRF) family is a PRF family that is also key homomorphic.

Definition 3

(Input-Homomorphic Weak PRF.) A weak pseudorandom function family $\{F'(k, \cdot ) : \mathcal {X} \rightarrow \mathcal {Y}\}_{k \in \mathcal {K}}$ is an IHwPRF family if the following conditions are satisfied:

• $(\mathcal {X}, \oplus )$ and $(\mathcal {Y}, \otimes )$ are efficiently samplable groups, and the group operations and the inverse operation in each group are efficiently computable.

• For any pair of inputs $x_1,x_2\in \mathcal {X}$ and any key $k\in \mathcal {K}$, we have

  $$\begin{aligned} F' \left( k, x_{1} \right) \otimes F' \left( k, x_{2} \right) = F' \left( k, x_{1} \oplus x_{2} \right) . \end{aligned}$$

Definition 4

($\gamma$-Bounded IHwPRF.) A weak pseudorandom function family $\{F(k, \cdot ) : \mathcal {X} \rightarrow \mathcal {Y}\}_{k \in \mathcal {K}}$ is a $\gamma$-bounded IHwPRF family if there is an (efficiently computable) universal mapping $\mathcal {R}: \mathcal {Y} \rightarrow \mathcal {Z}$ such that

• $(\mathcal {K}, \oplus )$ and $(\mathcal {Y}, \otimes )$ are efficiently samplable groups, and the group operations and the inverse operation in each group are efficiently computable.

• For a randomly chosen input vector $(x_1, \ldots , x_{L}) \leftarrow \mathcal {X}^{L}$ such that $L \le \gamma$, and a randomly chosen key $k \leftarrow \mathcal {K}$, the following holds with overwhelming probability:

  $$\begin{aligned} \mathcal {R}\Big ( F\Big (k,\bigoplus _{j \in {[L]}} x_j \Big ) \Big ) = \mathcal {R} \Big ( \bigotimes _{j \in [L]} F(k, x_j) \Big ). \end{aligned}$$

3 Key-Homomorphic Weak PRFs and Implications

In this section we show how to construct PKE and input-homomorphic weak PRF (IHwPRF) from a key-homomorphic weak PRF (KHwPRF). First, we introduce a hardness assumption over the output group of a KHwPRF. This hardness assumption has the advantage that it does not directly involve the input set $\mathcal {X}$ of the KHwPRF, which may be algebraically unstructured. Here (and in the following two subsections), we assume that the KHwPRF has unbounded (or exact) homomorphism. Later in this section, we show how to extend our results to “almost” KHwPRFs. Finally, we provide a construction of Naor-Reingold style PRF from KHwPRFs.

Theorem 1

Let $F: \mathcal {K} \times \mathcal {X} \rightarrow \mathcal {Y}$ be a KHwPRF, and let be an (arbitrary) positive integer. Assume that be a positive integer such that . Let $\mathbf {Y}\in \mathcal {Y}^{m \times d}$ be a matrix of group elements such that each entry $y_{i,j }$ (for $i \in [m], j \in [d]$) is drawn uniformly and independently from $\mathcal {Y}$. If , then for any PPT adversary we have

$$\begin{aligned} (\mathbf {Y}, \mathbf {Y}\mathbf {s}) {\mathop {\approx }\limits ^{c}}(\mathbf {Y}, \mathbf {u}), \end{aligned}$$

where $\mathbf {u}\leftarrow \mathcal {Y}^m$ is a a vector of m uniformly chosen elements from $\mathcal {Y}$.

Proof

Let $\mathbf {F}\in \mathcal {Y}^{m \times d}$ be a matrix formed in the following way: first sample m uniform elements from $\mathcal {X}$ as $\{x_i \leftarrow \mathcal {X} \}_{i \in [m]}$, and generate d uniform elements from $\mathcal {K}$ as $\{k_j \leftarrow \mathcal {K} \}_{j \in [d]}$. Now we set $\mathbf {F}_{i,j} = F(k_j, x_i)$, i.e., each row (respectively, column) has the same input (respectively, key).

In the first part we prove that $\mathbf {F}{\mathop {\approx }\limits ^{c}}\mathbf {Y}$. We define the hybrids $\mathcal {H}_j$ over the columns as follows: let $\mathcal {H}_j$ be the hybrid that the first j columns are generated using the weak PRF and the remaining columns are generated using uniform and independent values. By construction, we have $\mathcal {H}_0 \equiv \mathbf {Y}$ and $\mathcal {H}_d \equiv \mathbf {F}$. It is enough to show that $\mathcal {H}_{j - 1} {\mathop {\approx }\limits ^{c}}\mathcal {H}_{j}$ for each $j \in [d]$. Given access to an oracle $\mathcal {O}$ which is either F or a truly random function, the reduction invokes its oracle m times and receives $\{x_{i'}, \mathcal {O}(x_{i'})\}_{i' \in [m]}$. It then samples $j - 1$ keys as $\{k_{j'} \leftarrow \mathcal {K}\}_{j' \in [j - 1]}$ and forms the matrix $\mathbf {M}\in \mathcal {Y}^{m \times d}$ as follows:

• If $j' < j$, set $\mathbf {M}_{i', j'} = F(k_{j'}, x_{i'})$.

• If $j' = j$, set $\mathbf {M}_{i', j'} = \mathcal {O}(x_{i'})$.

• If $j' > j$, for each $i' \in [m]$ and $j' \in \{j + 1, \ldots , d \}$ sample a fresh $y \leftarrow \mathcal {Y}$ and set $\mathbf {M}_{i', j'} = y$.

Observe that $\mathbf {M}\equiv \mathcal {H}_{j - 1}$ if $\mathcal {O}$ corresponds to a truly random function, and $\mathbf {M}\equiv \mathcal {H}_{j}$ if $\mathcal {O}$ corresponds to the pseudorandom function F. It follows that $\mathcal {H}_{j - 1} {\mathop {\approx }\limits ^{c}}\mathcal {H}_{j}$.

In the second part of the proof, we show that $(\mathbf {F}, \mathbf {F}\mathbf {s}) {\mathop {\approx }\limits ^{c}}(\mathbf {F}, \mathbf {u})$. Given an attacker $\mathcal {A}$ that distinguishes $(\mathbf {F}, \mathbf {F}\mathbf {s})$ from $(\mathbf {F}, \mathbf {u})$, we describe an attacker $\mathcal {B}$ against the weak pseudorandomness of F. Given access to an oracle $\mathcal {O}$ which is either F or a truly random function, $\mathcal {B}$ invokes its oracle m times and receives $\{x_{i}, \mathcal {O}(x_{i})\}_{i \in [m]}$. The reduction then samples d keys as $\{k_{j} \leftarrow \mathcal {K}\}_{j \in [d]}$ and forms the matrix $\mathbf {F}$ as $\mathbf {F}_{i,j} = F(k_{j}, x_i)$. Define the vectors $\mathbf {y}^* \in \mathcal {Y}^m$ and $\mathbf {k}\in \mathcal {K}^d$ as

$$\begin{aligned} \mathbf {k}= (k_1, \ldots , k_d),\quad \quad \quad \mathbf {y}^* := \left( \mathcal {O}(x_1), \ldots , \mathcal {O}(x_m)\right) . \end{aligned}$$

Finally, $\mathcal {B}$ runs $\mathcal {A}$ on the input $(\mathbf {F}, \mathbf {y}^*)$ and $\mathcal {B}$ outputs whatever $\mathcal {A}$ outputs. It is easy to see that if $\mathcal {O}$ is a truly random function we have $(\mathbf {F}, \mathbf {y}^*) \equiv (\mathbf {F}, \mathbf {u})$. Observe that by the leftover hash lemma, we have $(\mathbf {k}, \bigoplus _{\mathbf {s}} \mathbf {k}) {\mathop {\approx }\limits ^{s}}(\mathbf {k}, k^*)$ where $k^*$ is uniform over $\mathcal {K}$. If $\mathbf {y}^*$ corresponds to the weak PRF outputs ($\mathcal {O}$ is the weak PRF), by key homomorphism of F we have

$$\begin{aligned} \mathbf {F}\mathbf {s}&= \begin{pmatrix} F\left( \bigoplus _{\mathbf {s}} \mathbf {k}, x_1\right) \\ F\left( \bigoplus _{\mathbf {s}} \mathbf {k}, x_2\right) \\ \vdots \\ F\left( \bigoplus _{\mathbf {s}} \mathbf {k}, x_m\right) \end{pmatrix} {\mathop {\approx }\limits ^{s}}\begin{pmatrix} F\left( k^*, x_1\right) \\ F\left( k^*, x_2\right) \\ \vdots \\ F\left( k^*, x_m\right) \\ \end{pmatrix} \equiv \mathbf {y}^*. \end{aligned}$$

Therefore, the advantage of $\mathcal {B}$ (in the weak PRF game) is negligibly different from the advantage of $\mathcal {A}$. It follows that $(\mathbf {F}, \mathbf {F}\mathbf {s}) {\mathop {\approx }\limits ^{c}}(\mathbf {F}, \mathbf {u})$, as required.

Using the first part of the proof by a straightforward reduction we have $(\mathbf {Y}, \mathbf {Y}\mathbf {s}) {\mathop {\approx }\limits ^{c}}(\mathbf {F}, \mathbf {F}\mathbf {s})$ and $(\mathbf {F}, \mathbf {u}) {\mathop {\approx }\limits ^{c}}(\mathbf {Y}, \mathbf {u})$. Using the second part, it follows that

$$\begin{aligned} (\mathbf {Y}, \mathbf {Y}\mathbf {s}) {\mathop {\approx }\limits ^{c}}(\mathbf {F}, \mathbf {F}\mathbf {s}) {\mathop {\approx }\limits ^{c}}(\mathbf {F}, \mathbf {u}) {\mathop {\approx }\limits ^{c}}(\mathbf {Y}, \mathbf {u}), \end{aligned}$$

and hence we get $(\mathbf {Y}, \mathbf {Y}\mathbf {s}) {\mathop {\approx }\limits ^{c}}(\mathbf {Y}, \mathbf {u})$.

3.1 Public-Key Encryption

Now we describe a non-interactive key exchange protocol (which is sufficient to realize PKE) based on any KHwPRF. Later, we explain construction of an IHwPRF from any KHwPRF, which in turn implies a variety of cryptographic primitives. We first start with an inefficient protocol, and then we show how to improve its efficiency.

Given a KHwPRF $F: \mathcal {K} \times \mathcal {X} \rightarrow \mathcal {Y}$ such that $\mathcal {Y}$ is an abelian group, fix some integer and let $\mathbf {Y}\in \mathcal {Y}^{m \times m }$ be a matrix of uniformly chosen group elements from $\mathcal {Y}$. Alice (respectively, Bob) chooses binary vector (respectively, ), and sends $\mathbf {r}^{t}\mathbf {Y}$ (respectively, $\mathbf {Y}\mathbf {s}$) to Bob (respectively, Alice). The final secret will be $\mathbf {r}^t(\mathbf {Y}\mathbf {s}) = (\mathbf {r}^{t}\mathbf {Y})\mathbf {s}\in \mathcal {Y}$. The following figure is a simple visualization of the key exchange protocol.

We sketch the security proof for the mentioned protocol. It is enough to show

$$\begin{aligned} (\mathbf {Y}, \mathbf {r}^t\mathbf {Y}, \mathbf {Y}\mathbf {s}, \mathbf {r}^t\mathbf {Y}\mathbf {s}) {\mathop {\approx }\limits ^{c}}(\mathbf {Y}, \mathbf {y}_1, \mathbf {y}_2, y), \end{aligned}$$

where .

Observe that by Theorem 1 and a simple hybrid argument we can replace $\mathbf {r}^t\mathbf {Y}$ with a random vector $\mathbf {u}\leftarrow \mathcal {Y}^{m}$ and so

$$\begin{aligned} (\mathbf {Y}, \mathbf {u}, \mathbf {Y}\mathbf {s}, \mathbf {u}\mathbf {s}) {\mathop {\approx }\limits ^{c}}(\mathbf {Y}, \mathbf {y}_1, \mathbf {y}_2, y). \end{aligned}$$

Now let $\hat{\mathbf {Y}} \in \mathcal {Y}^{(m + 1) \times m}$ be the matrix that has $\mathbf {Y}$ as its top submatrix and $\mathbf {u}$ as its last row. By applying Theorem 1 again, it follows that

$$\begin{aligned} (\hat{\mathbf {Y}}, \hat{\mathbf {Y}}\mathbf {s}) {\mathop {\approx }\limits ^{c}}(\hat{\mathbf {Y}}, y), \end{aligned}$$

as required.

The reader may notice that the aforementioned key exchange protocol is too expensive in terms of communication complexity, i.e, to agree on some group element the parties need to exchange $2m^2$ group elements. Using the following lemma, we immediately get a key exchange protocol for which the whole cost of communication is twice the size of the final secret (like DDH).

Lemma 1

Let $F: \mathcal {K} \times \mathcal {X} \rightarrow \mathcal {Y}$ be a KHwPRF, and let be a positive integer. For any PPT adversary we have

$$\begin{aligned} (\mathbf {Y}, \mathbf {R}\mathbf {Y}, \mathbf {Y}\mathbf {S}, \mathbf {R}\mathbf {Y}\mathbf {S}) {\mathop {\approx }\limits ^{c}}(\mathbf {Y}, \mathbf {Y}', \mathbf {Y}'', \mathbf {Y}'''), \end{aligned}$$

where $\mathbf {Y}, \mathbf {Y}', \mathbf {Y}'', \mathbf {Y}'''$ are matrices of uniform group elements in $\mathcal {Y}^{m \times m }$, and $\mathbf {S}$, $\mathbf {R}$ are uniform binary matrices, i.e., and .⁶

Proof

The lemma follows from Theorem 1, and a standard hybrid argument.

3.2 Input-Homomorphic Weak PRF

Here we show a simple construction of an IHwPRF from any KHwPRF. We remark that although an IHwPRF implies a variety of cryptographic primitives, the constructions will not be necessarily efficient. More efficient constructions can be obtained by directly building the primitive using the assumption in Lemma 1.

Lemma 2

Let $F: \mathcal {K} \times \mathcal {X} \rightarrow \mathcal {Y}$ be a KHwPRF. If be a positive integer and $\mathcal {Y}$ is an abelian group, the function defined as

$$\begin{aligned} \tilde{F}\big ( \mathbf {s}= (s_1, \ldots , s_d) , \mathbf {y}= (y_1, \ldots , y_d)\big ) = \bigotimes _{\mathbf {s}} \mathbf {y}= \bigotimes _{j : s_j = 1} y_j \end{aligned}$$

is an IHwPRF.

Proof

First, observe that $\tilde{F}$ is input homomorphic since for any $\mathbf {y},\mathbf {y}' \in \mathcal {Y}^d$ and we have

$$\begin{aligned} \tilde{F}(\mathbf {s}, \mathbf {y}) \otimes \tilde{F}(\mathbf {s}, \mathbf {y}')&= \bigg (\bigotimes _{\mathbf {s}} \mathbf {y}\bigg ) \otimes \bigg (\bigotimes _{\mathbf {s}} \mathbf {y}'\bigg ) \\&= \bigg (\bigotimes _{j : s_j = 1} y_j \bigg ) \otimes \bigg (\bigotimes _{j : s_j = 1} y'_j\bigg ) \\&= \bigotimes _{j : s_j = 1} (y_j \otimes y'_j) \\&= \bigotimes _{\mathbf {s}} \; (\mathbf {y}\otimes \mathbf {y}') = \tilde{F}(\mathbf {s}, \mathbf {y}\otimes \mathbf {y}'). \end{aligned}$$

Given m (where ) samples of the form $(\mathbf {y}_i, \mathcal {O}(\mathbf {y}_i))$, form the matrix $\mathbf {Y}\in \mathcal {Y}^{m \times d}$ such that the i’th row of $\mathbf {Y}$ is $\mathbf {y}_i$. In addition, define $\mathbf {y}^*$ as $\mathbf {y}^* := (\mathcal {O}(\mathbf {y}_1), \ldots , \mathcal {O}(\mathbf {y}_m))$. Observe that if $\mathcal {O}$ is a truly random function then $\mathbf {y}^*$ is uniformly distributed in $\mathcal {Y}^m$. On the other hand, if $\mathcal {O}$ is the weak PRF, we have $\mathbf {y}^* = \mathbf {Y}\mathbf {s}$ for some uniform . By applying Theorem 1 and observing the fact that , it follows that F is a weak PRF.

Implications. By plugging in the results of [AMPR19], and using the Lemma 2 it follows that KHwPRFs imply noninteractive key exchange, private information retrieval [KO97], lossy trapdoor functions [PW08], identity-based encryption (in a non-blackbox manner) [DG17b, DG17a, BLSV18], and hinting PRGs [KW19].

We remark that KHwPRFs trivially imply homomorphic one-way functions (HOWFs) and hence using the results of [AMPR19], KHwPRFs imply collision-resistant hash functions, Schnorr signatures, and chameleon hash functions.

3.3 Asymmetric Primitives from Bounded KHwPRFs

In this part, we show that the “approximate” (some papers called it “almost”) version of key-homomorphic weak PRFs with certain properties imply a variety of asymmetric primitives, such as public-key encryption (PKE). Approximate KHwPRFs have the property that $F_{k \oplus k'}(x)$ is close to $F_{k}(x) \otimes F_{k'}(x)$ where closeness is measured with respect to some distance function.

An Algebraic Definition. Formalizing a general definition for “approximate” homomorphism requires a somewhat involved geometric definition that needs a distance function, which also does not nicely fit into the recent (algebraic) framework of [AMPR19]. In this work, we provide a natural algebraic definition for bounded Key-Homomorphic weak PRFs, which is similar to the definition of bounded IHwPRFs of [AMPR19].

We remark that all existing constructions of approximate KHwPRFs with an appropriate choice of parameters can be viewed as bounded KHwPRFs.

Definition 5

A weak pseudorandom function family $\{F(k, \cdot ) : \mathcal {X} \rightarrow \mathcal {Y}\}_{k \in \mathcal {K}}$ is a $\gamma$-bounded KHwPRF family if there exists (efficiently computable) universal mappings $\mathcal {R}_{\mathsf {in}}: \mathcal {Y} \rightarrow \mathcal {Z}_{\mathsf {in}}$ and $\mathcal {R}_{\mathsf {out}}: \mathcal {Z}_{\mathsf {in}} \rightarrow \mathcal {Z}_{\mathsf {out}}$ such that

• $(\mathcal {K}, \oplus )$, $(\mathcal {Y}, \otimes )$, and $(\mathcal {Z}_{\mathsf {in}}, \odot )$ are efficiently samplable groups, and the group operations and the inverse operation in each group are efficiently computable.

• For a randomly chosen key vector $(k_1, \ldots , k_{L}) \leftarrow \mathcal {K}^{L}$ such that $L \le \gamma$, and a randomly chosen input $x \leftarrow \mathcal {X}$, the following holds with overwhelming probability:

  $$\begin{aligned} \mathcal {R}_{\mathsf {in}}\Big ( F\Big (\bigoplus _{j \in {[L]}} k_j, x \Big ) \Big ) = \mathcal {R}_{\mathsf {in}} \Big ( \bigotimes _{j \in [L]} F(k_j, x) \Big ), \end{aligned}$$
  $$\begin{aligned} \mathcal {R}_{\mathsf {out}}\Big ( \bigodot _{j \in [L]} \mathcal {R}_{\mathsf {in}}\Big ( F( k_j, x) \Big ) \Big ) = \mathcal {R}_{\mathsf {out}}\Big ( \mathcal {R}_{\mathsf {in}} \Big ( \bigotimes _{j \in [L]} F(k_j, x) \Big ) \Big ). \end{aligned}$$

Bounded KHwPRFs and LWR. All of the currently known instantiations of “approximate” key-homomorphic (weak) PRFs use Learning With Rounding (LWR) [BPR12] as their underlying assumption. It is easy to see that if the output group of some LWR-based KHwPRF is $\mathbb {Z}_p^n$ for some superpolynomial modulus p and some dimension n, we can define the mapping $\mathcal {R}_{\mathsf {in}}$ (respectively, $\mathcal {R}_{\mathsf {out}}$) to be rounding with respect to some modulus $p_{\mathsf {in}}$ (respectively, $p_{\mathsf {out}}$) such that $p/p_{\mathsf {in}}$ and $p_{\mathsf {in}}/p_{\mathsf {out}}$ are both superpolynomial.

This immediately yields bounded KHwPRFs from approximate KHwPRFs that have the mentioned property. We remark that this property seems to be necessary for most of the applications of KH-PRFs in [BLMR13] (and in some cases to get an efficient construction). The reader may note that the resulting construction of bounded KHwPRFs from LWR has a triple rounding, one that is embedded in the (weak) PRF F and one for each mapping $\mathcal {R}_{\mathsf {out}}$ and $\mathcal {R}_{\mathsf {in}}$ defined above. Although this property is inherent for the LWR-based construction, in general there may not be any similarity between F and $\mathcal {R}_{\mathsf {in}}$ or $\mathcal {R}_{\mathsf {out}}$ for a bounded KHwPRF.

PKE Construction from Bounded KHwPRF. Using the definition above, we now construct a public-key encryption scheme from a bounded KHwPRF. The construction is almost identical to the case of unbounded KHwPRFs, with the difference being applying the mappings $\mathcal {R}_{\mathsf {in}}$ and $\mathcal {R}_{\mathsf {out}}$ of the bounded KHwPRF. The argument for the security is also very similar to the exact/unbounded case, and we omit the details.

Given a $\gamma$-bounded KHwPRF $F: \mathcal {K} \times \mathcal {X} \rightarrow \mathcal {Y}$ (with mappings $\mathcal {R}_{\mathsf {in}}$ and $\mathcal {R}_{\mathsf {out}}$ defined as above) such that $\mathcal {Y}$ and $\mathcal {Z}_{\mathsf {in}}$ are abelian groups and , fix some integer and let $\mathbf {Y}\in \mathcal {Y}^{m \times m }$ be a matrix of uniformly chosen group elements from $\mathcal {Y}$. Alice (respectively, Bob) chooses binary vector (respectively, ), and sends $\mathcal {R}_{\mathsf {in}}(\mathbf {r}^{t}\mathbf {Y})$ (respectively, $\mathcal {R}_{\mathsf {in}}(\mathbf {Y}\mathbf {s})$) to Bob (respectively, Alice). The final secret will be

$$\begin{aligned} \mathcal {R}_{\mathsf {out}} \big ( \mathbf {r}^t\mathcal {R}_{\mathsf {in}}(\mathbf {Y}\mathbf {s}) \big ) = \mathcal {R}_{\mathsf {out}} \big (\mathcal {R}_{\mathsf {in}}(\mathbf {r}^{t}\mathbf {Y})\mathbf {s}\big ) \in \mathcal {Z}_{\mathsf {out}}. \end{aligned}$$

Bounded IHwPRF from Bounded KHwPRF. Using the definition above, we now construct a bounded IHwPRF from a bounded KHwPRF. The construction is almost identical to the case of unbounded KHwPRFs, with the difference being applying the mappings $\mathcal {R}_{\mathsf {in}}$ and $\mathcal {R}_{\mathsf {out}}$ of the bounded KHwPRF.

Given a $\gamma$-bounded KHwPRF $F: \mathcal {K} \times \mathcal {X} \rightarrow \mathcal {Y}$ (with mappings $\mathcal {R}_{\mathsf {in}}$ and $\mathcal {R}_{\mathsf {out}}$ defined as above) such that $\mathcal {Y}$ and $\mathcal {Z}_{\mathsf {in}}$ are abelian groups and , fix some integer d such that we define a bounded IHwPRF with its associated mapping $\tilde{\mathcal {R}} : \mathcal {Z}_{\mathsf {in}} \rightarrow \mathcal {Z}_{\mathsf {out}}$ as

$$\begin{aligned} \tilde{F}\big ( \mathbf {s}= (s_1, \ldots , s_d) , \mathbf {y}= (y_1, \ldots , y_d)\big ) = \mathcal {R}_{\mathsf {in}} \big ( \bigotimes _{\mathbf {s}} \mathbf {y}\big ) = \mathcal {R}_{\mathsf {in}}\big (\bigotimes _{j : s_j = 1} y_j \big ), \end{aligned}$$

where $\tilde{\mathcal {R}}$ (the associated mapping with $\tilde{F}$) is identical to $\mathcal {R}_{\mathsf {out}}$. The security proof is very similar to the exact/unbounded case, and hence we omit the details.

3.4 Naor-Reingold PRF

Here we show a construction of Naor-Reingold style PRF from any KHwPRF. Before we do so, however, we will provide some background on the Naor-Reingold PRF and explain why PRFs in this style are important. We start by recalling the original Naor-Reingold PRF [NR97]:

Let $\mathbb {G}$ be a group of order p, and let $F_{NR} :(\mathbb {Z}_{p}^{(\ell +1)} \times \mathbb {G}) \times \{0,1\}^{\ell } \rightarrow \mathbb {G}$ be the function defined by

where the values $\alpha _{0}, \alpha _{1},\ldots , \alpha _{\ell }$ form the key and is the input. Informally, a Naor-Reingold style PRF requires a constant number of computations (for instance, the exponentiation in $F_{NR}$) on which the assumption related to its hardness depends, while all of the operations that scale with the length of the input (for instance, the integer multiplications in the exponent of $F_{NR}$) are less expensive. This feature allows Naor-Reingold style PRFs to be potentially efficient. In particular, assuming that the underlying operations have reasonably low circuit depth, such PRFs typically have polylogarithmic evaluation circuits.

We now show a simple construction of Naor-Reingold style PRF from any exact KHwPRF with abelian output group. Our construction involves a subset product of binary matrices and one “multiplication” of a group matrix and an integer matrix. The depth of the PRF evaluation circuit is polylogarithmic provided that the group operation can be done efficiently.

Theorem 2

Let $\tilde{F}: \mathcal {K} \times \mathcal {X} \rightarrow \mathcal {Y}$ be a KHwPRF, and fix some . Let $\mathbf {Y}\in \mathcal {Y}^{m \times m}$ be a (public) matrix of group elements such that each entry $y_{i,j }$ (for $i \in [m], j \in [m]$) is drawn uniformly and independently from $\mathcal {Y}$. The function defined as

$$\begin{aligned} F\bigg ((\mathbf {S}_0, \mathbf {S}_1, \ldots , \mathbf {S}_{\ell }), \mathbf {x}= (x_1, \ldots , x_{\ell }) \bigg ) = \mathbf {Y}\mathbf {S}_0 \prod _{i = 1}^{\ell } \mathbf {S}_i^{x_i} \end{aligned}$$

is a pseudorandom function where for $i \in \{0, \ldots , \ell \}$.

Proof

To prove this theorem, we use the following lemma.

Lemma 3

Let $\mathbf {Y}_1,\ldots ,\mathbf {Y}_Q \in \mathcal {Y}^{m \times m}$ be matrices with uniformly and independently sampled entries from $\mathcal {Y}$ for some , and let be a uniformly sampled binary matrix. Then for any PPT adversary we have

$$\begin{aligned} \{(\mathbf {Y}_q, \mathbf {Y}_q\mathbf {S})\}_{q\in [Q]} {\mathop {\approx }\limits ^{c}}\{(\mathbf {Y}_q, \mathbf {U}_q)\}_{q\in [Q]}. \end{aligned}$$

where for each $q\in [Q]$, $\mathbf {U}_q \leftarrow \mathcal {Y}^{m \times m}$ is a matrix of uniformly chosen elements from $\mathcal {Y}$.

This lemma follows directly from Theorem 1, and a standard hybrid argument over the columns of $\mathbf {S}$. The proof of pseudorandomness now proceeds via a series of $(\ell +1)$ hybrid games, where for each $j\in [0,\ell ]$, the $j^{\text {th}}$ game is as described below.

• 1. The challenger samples $(\ell -j)$ uniform binary matrices as for $i \in [j+1,\ell ]$. It also maintains a list $\mathcal {L}$ of $m\times m$ matrices over the group $\mathcal {Y}$. Initially, this list is empty. The challenger also creates and stores an $m\times m$ matrix $\mathbf {Y}_0$ consisting of uniformly and independently sampled entries from $\mathcal {Y}$.

• 2. The adversary adaptively issues a maximum of PRF queries of the form $\mathbf {x}_1,\ldots ,\mathbf {x}_Q$, where for each $q\in [Q]$, we have $\mathbf {x}_q = (x_{1,q}, \ldots , x_{\ell ,q})$. For ease of representation, we divide each query string as $\mathbf {x}_q = (\mathbf {x}^{(0)}_q, \mathbf {x}^{(1)}_q)$, where

  $$\begin{aligned} \mathbf {x}^{(0)}_q = (x_{1,q}, \ldots , x_{j,q}), \quad \mathbf {x}^{(1)}_q = (x_{j+1,q}, \ldots , x_{\ell ,q}). \end{aligned}$$

• 3. Upon receipt of the $q^{\text {th}}$ query, the challenger proceeds as follows:

  • (a) If $j=0$, it sets $\mathbf {Y}_q = \mathbf {Y}_0$.

  • (b) Otherwise, it checks if there exists a $q' < q$ such that $\mathbf {x}^{(0)}_q = \mathbf {x}^{(0)}_{q'}$.

    • i. If yes, it sets $\mathbf {Y}_q = \mathbf {Y}_{q'}$.

    • ii. Otherwise, it sets $\mathbf {Y}_q$ to be an $m\times m$ matrix with uniformly and independently sampled entries from $\mathcal {Y}$.

  • (c) It updates the list $\mathcal {L}$ as $\mathcal {L} = \mathcal {L}\cup \{\mathbf {Y}_q\}$ and responds to the $q^{\text {th}}$ query as

    $$\begin{aligned} f_{j,q} = \mathbf {Y}_q\prod _{i = j+1}^{\ell } \mathbf {S}_i^{x_{i,q}}. \end{aligned}$$

Note that in the $\text {zero}^{\text {th}}$ hybrid, we replaced the component $\mathbf {Y}\mathbf {S}_0$ in the original PRF construction by an $m\times m$ matrix $\mathbf {Y}_0$ consisting of uniformly and independently sampled entries from $\mathcal {Y}$. It follows from Theorem 1 that this hybrid is indistinguishable from the real PRF experiment.

Now, for each $j\in [0,\ell ]$, let $\mathcal {F}_{j} = \{f_{j,q}\}_{q\in [Q]}$ be the set of responses generated by the challenger in the $j^{\text {th}}$ game. The proof of Theorem 2 now follows immediately from the following claim:

Claim

For each $j\in [0,\ell -1]$ and for any PPT adversary we have

$$\begin{aligned} \mathcal {F}_{j} {\mathop {\approx }\limits ^{c}}\mathcal {F}_{j+1}. \end{aligned}$$

Let $\mathcal {A}$ be a PPT adversary such that for some $j\in [\ell ]$, $\mathcal {A}$ efficiently distinguishes between $\mathcal {F}_{j}$ and $\mathcal {F}_{j+1}$. We construct an attacker $\mathcal {B}$ against the assumption in Lemma 3. $\mathcal {B}$ receives as input a tuple of the form $\{(\mathbf {Y}_q, \mathbf {Z}_q)\}_{q\in [Q']}$ for some $Q' > Q$, where either each $\mathbf {Z}_q$ is of the form $\mathbf {Y}_q\mathbf {S}_j$ for some uniformly random $m\times m$ binary matrix $\mathbf {S}_j$, or each $\mathbf {Z}_q$ is a uniformly random matrix over $\mathcal {Y}^{m\times m}$. It proceeds as follows:

• 1. $\mathcal {B}$ samples $(\ell -j-1)$ uniform binary matrices as for $i \in [j+2,\ell ]$. It also maintains a counter variable $\mathsf {cnt}$. Initially, $\mathsf {cnt} = 1$.

• 2. $\mathcal {A}$ adaptively issues a maximum of PRF queries of the form $\mathbf {x}_1,\ldots ,\mathbf {x}_Q$, where for each $q\in [Q]$, we have $\mathbf {x}_q = (x_{1,q}, \ldots , x_{\ell ,q})$. Again, for ease of representation, we divide each query string as $\mathbf {x}_q = (\mathbf {x}^{(0)}_q, \mathbf {x}^{(1)}_q)$, where

  $$\begin{aligned} \mathbf {x}^{(0)}_q = (x_{1,q}, \ldots , x_{j,q}), \quad \mathbf {x}^{(1)}_q = (x_{j+1,q}, \ldots , x_{\ell ,q}). \end{aligned}$$

• 3. Upon receipt of the $q^{\text {th}}$ query, $\mathcal {B}$ checks if there exists a $q' < q$ such that $\mathbf {x}^{(0)}_q = \mathbf {x}^{(0)}_{q'}$.

  • (a) If yes, it sets $\widetilde{\mathbf {Y}}_q = \widetilde{\mathbf {Y}}_{q'}$ and $\widetilde{\mathbf {Z}}_q = \widetilde{\mathbf {Z}}_{q'}$.

  • (b) Otherwise, it sets $\widetilde{\mathbf {Y}}_q = \mathbf {Y}_{\mathsf {cnt}}$ and $\widetilde{\mathbf {Z}}_q = \mathbf {Z}_{\mathsf {cnt}}$, and updates $\mathsf {cnt} = \mathsf {cnt}+1$.

• 4. $\mathcal {B}$ now responds to the $q^{\text {th}}$ query as

  $$ \tilde{f}_{j,q} = {\left\{ \begin{array}{ll} \widetilde{\mathbf {Y}}_q\prod \nolimits _{i = j+2}^{\ell } \mathbf {S}_i^{x_{i,q}} &{} \text {if } x_{j+1,q} = 0\\ \widetilde{\mathbf {Z}}_q\prod \nolimits _{i = j+2}^{\ell } \mathbf {S}_i^{x_{i,q}} &{} \text {if } x_{j+1,q} = 1. \end{array}\right. } $$

• 5. Eventually, the adversary $\mathcal {A}$ outputs a bit b. $\mathcal {B}$ outputs the same bit b.

Let $\widetilde{\mathcal {F}} = \{\tilde{f}_{j,q}\}_{q\in [Q]}$ be the set of responses generated by $\mathcal {B}$. It is easy to see the following:

• If each $\mathbf {Z}_q$ is of the form $\mathbf {Y}_q\mathbf {S}_j$ for some uniformly random $m\times m$ binary matrix $\mathbf {S}_j$, then the distribution of $\widetilde{\mathcal {F}}$ is identical to that of $\mathcal {F}_{j}$.

• On the other hand, if each $\mathbf {Z}_q$ is a uniformly random matrix over $\mathcal {Y}^{m\times m}$, then the distribution of $\widetilde{\mathcal {F}}$ is identical to that of $\mathcal {F}_{j+1}$.

It now follows that the advantage of $\mathcal {B}$ is identical to that of $\mathcal {A}$. This completes the proof of Claim 3.4. The proof of Theorem 2 follows immediately.

NR-style PRFs from Bounded KHwPRFs. Our definition of bounded KHwPRFs does not allow a direct construction of NR-style PRFs. However, there are known constructions of NR-style PRFs from lattice-based assumptions. A notable example is the lattice-based KHPRF from [BLMR13], which proves security by progressively rounding further at each hybrid argument to ensure that “exactness” holds at each step. However, while actually computing the PRF, this is simulated by rounding once to a specially chosen modulus. In practical scenarios, this construction seems substantially less efficient than related pseudorandom synthesizer constructions [NR95, Mon18].

Our algebraic definition of bounded KHwPRFs does not encompass multiple levels of “rounding” (or any other compressing operation), since it seemingly makes bounded KHwPRFs inherently inefficient for constructing NR-style PRFs. Thus, we omit constructing NR-style PRFs from bounded KHwPRFs.

4 Updatable Encryption and Symmetric PRE

In this section, we show that any ciphertext-independent updatable encryption scheme that satisfies the adaptive notions of forward and post-compromise security proposed in [LT18] implies PKE. We also show that any symmetric-key proxy re-encryption scheme that satisfies the adaptive notion of indistinguishability-based security formalized in [FKKP19] implies updatable encryption with forward and post-compromise security, and hence PKE.

4.1 PKE from Updatable Encryption

An updatable encryption scheme is, informally speaking, a symmetric key encryption scheme with the following extra property: a user with a secret key $k_{1}$ can provide an update token $\sigma _{1, 2}$ that maps ciphertexts encrypted under key $k_{1}$ to new ciphertexts encrypted under some other key $k_{2}$. The main application of updatable encryption is handling key rotation of data in the cloud where a data owner does not trust the cloud owner enough to provide them with a secret key in the clear.

Updatable encryption was first defined in [BLMR13] as an application of KHPRFs. The definitions proposed in [BLMR13] were subsequently refined by Everspaugh et al. in [EPRS17]. In a more recent work, Lehmann and Tackmann [LT18] introduced more rigorous security notions for updatable encryption that are desirable for real-world applications, and also pointed out that none of the existing constructions satisfy these notions. In this section, we show that updatable encryption with adaptive update indistinguishability (IND-UPD) as defined by Lehmann and Tackmann [LT18] implies public-key encryption. We start by defining the general functionality of any UE scheme. Note that all of the definitions we use here are from [LT18].

Definition 6

(Updatable Encryption). An updatable encryption scheme $\mathsf {UE}$ for a message space $\mathcal {M}$ is a tuple of five PPT algorithms $(\mathsf {Setup},\mathsf {Next},\mathsf {Enc},$ $\mathsf {Dec},\mathsf {Update})$ defined as follows:

• $\mathsf {Setup} (1^{\lambda })$: Given the security parameter $\lambda$, it generates a secret key $\textsf {sk} _0$.

• $\mathsf {Next} ( \textsf {sk} _e)$: On input a secret key $\textsf {sk} _e$ for epoch e, it generates a new secret key $\textsf {sk} _{e+1}$ and a new update token $\varDelta _{e,e+1}$ for epoch $(e+1)$.

• $\mathsf {Enc} ( \textsf {sk} _e, \textsf {m} )$: On input a secret key $\textsf {sk} _e$ for epoch e and a message $\textsf {m} \in \mathcal {M}$, it generates a ciphertext $\textsf {ct} _e$.

• $\mathsf {Dec} ( \textsf {sk} _e, \textsf {ct} _e)$: On input a secret key $\textsf {sk} _e$ and a ciphertext $\textsf {ct} _e$ for some epoch e, it either outputs a message $\textsf {m} '\in \mathcal {M}$ or $\bot$.

• $\mathsf {Update} (\varDelta _{e,e+1}, \textsf {ct} _e)$: On input an update token $\varDelta _{e,e+1}$ and a ciphertext $\textsf {ct} _e$ for some epoch e, it outputs an updated ciphertext $\textsf {ct} _{e+1}$ for epoch $(e+1)$.

Correctness. For any message $\textsf {m} \in \mathcal {M}$, for any $\textsf {sk} _0\leftarrow \mathsf {Setup} (1^{\lambda })$, and for any sequence of key/update token pairs $( \textsf {sk} _1,\varDelta _{0,1}),\ldots ,( \textsf {sk} _e,\varDelta _{e-1,e})$ obtained recursively as $( \textsf {sk} _j,\varDelta _{j-1,j})\leftarrow \mathsf {Next} ( \textsf {sk} _{j-1})$ for each $j\in [e]$, we have

$$\begin{aligned} \mathsf {Dec} ( \textsf {sk} _j, \textsf {ct} _j) = \textsf {m} , \end{aligned}$$

for any $j\in [e]$, where the sequence of ciphertexts $\textsf {ct} _0, \textsf {ct} _1,\ldots , \textsf {ct} _e$ is obtained as $\textsf {ct} _0 = \mathsf {Enc} ( \textsf {sk} _0, \textsf {m} )$ and $\textsf {ct} _j\leftarrow \mathsf {Update} (\varDelta _{j-1,j}, \textsf {ct} _{j-1})$ for each $j\in [e]$.

Security Notions for UE. In their paper [LT18], Lehmann and Tackmann define several notions of security for updatable encryption. Previous works had somewhat non-accurate notions of security, so we consider the definitions from [LT18] to be the only suitable ones currently known for UE. In this section, we focus on their IND-UPD security definition, which we explain below. In our opinion, this definition reflects the security needs of a user storing data and updating ciphertexts in an untrusted cloud. However, debating the definitions of UE is out of scope of this paper, and we refer to the sections 3 and 4 of [LT18] for a discussion of notions of UE security.

Forward and Post-Compromise Security. We adopt the definition of post-compromise security for $\mathsf {UE}$ schemes proposed and formalized by Lehmann and Tackmann in a recent work [LT18]. More specifically, we focus on the notion of adaptive update indistinguishability, or IND-UPD in short (also referred to as unlinkability), which ensures that an updated ciphertext obtained via the $\mathsf {Update}$ algorithm does not reveal any information about the previous ciphertext to a PPT adversary $\mathcal {A}$, even when $\mathcal {A}$ adaptively compromises polynomially many keys and tokens before and after the challenge epoch.

Adaptive Update Indistinguishability. We recall the formal definitions for adaptive update indistinguishability from [LT18]. We assume that the adversary has access to the following oracles (e is an epoch counter initialized to 0 and $\mathcal {L}$ is a list initialized to empty):

• 1. $\mathcal {O}_{\mathsf {Enc}}$: On input a message $\textsf {m}$, this oracle outputs $\textsf {ct} _e\leftarrow \mathsf {Enc} ( \textsf {sk} _e, \textsf {m} )$, where $\textsf {sk} _e$ is the secret key corresponding to the current epoch e, and adds the tuple $( \textsf {ct} _e,e)$ to the list $\mathcal {L}$.

• 2. $\mathcal {O}_{\mathsf {Next}}$: When queried, this oracle generates a new key/update token pair as $( \textsf {sk} _{e+1},\varDelta _{e,e+1})\leftarrow \mathsf {Next} ( \textsf {sk} _{e})$, updates the epoch counter to $(e+1)$ and adds $(e+1, \textsf {sk} _{e+1},\varDelta _{e,e+1})$ to the global state of the challenger. If issued post challenge-query phase, it also updates the challenge ciphertext to the new epoch as $\textsf {ct} ^{*}_e\leftarrow \mathsf {Update} (\varDelta _{e-1,e}, \textsf {ct} ^{*}_{e-1})$, and adds $( \textsf {ct} ^{*}_e,e)$ to the list $\mathcal {L}$.

• 3. $\mathcal {O}_{\mathsf {Update}}$: On input a ciphertext $\textsf {ct} _{e-1}$ such that $( \textsf {ct} _{e-1},e-1)\in \mathcal {L}$ (i.e., the input ciphertext is honestly generated during the previous epoch), this oracle outputs $\textsf {ct} _e\leftarrow \mathsf {Update} (\varDelta _{e-1,e}, \textsf {ct} _{e-1})$, and adds $( \textsf {ct} _e,e)$ to the list $\mathcal {L}$.

• 4. $\mathcal {O}_{\mathsf {corrupt}}$: This oracle takes as input an epoch $e'\le e$ (where e is the current epoch) and either $\mathsf {key}$ or $\mathsf {token}$. On input $(e',\mathsf {key})$, it outputs the key $\textsf {sk} _{e'}$. On input $(e',\mathsf {token})$, it outputs the token $\varDelta _{e'-1,e'}$.

• 5. $\mathcal {O}_{\mathsf {challenge}}$: This oracle returns the current challenge ciphertext $\textsf {ct} ^{*}_e$ from the list $\mathcal {L}$.

For each bit $b\in \left\{ 0,1 \right\}$, define the following experiment $\mathsf {Expt} ^{\text {ind-upd}}_b$ between a challenger and an adversary $\mathcal {A}$:

Definition 7

(IND-UPD secure Updatable Encryption). An updatable encryption scheme $\left( \mathsf {Setup},\mathsf {Next},\mathsf {Enc},\mathsf {Dec},\mathsf {Update} \right)$ is said to be $\textsf {IND-UPD}$-secure if for all PPT adversaries $\mathcal {A}$, the views of $\mathcal {A}$ in the experiments $\mathsf {Expt} ^{\text {ind-upd}}_0$ and $\mathsf {Expt} ^{\text {ind-upd}}_1$ are computationally indistinguishable. (Note that in the aforementioned definition, we implicitly assumed that the update algorithm of the underlying UE scheme is randomized.)

We now show that any updatable encryption scheme that satisfies adaptive update indistinguishability implies a PKE scheme. More formally, let $\mathsf {UE} = (\mathsf {Setup},\mathsf {Next},\mathsf {Enc},\mathsf {Dec},\mathsf {Update})$ be an IND-UPD secure scheme. We construct a PKE scheme as follows.

• Key Generation: The key generation algorithm receives as input the security parameter $\lambda$. It first generates a secret key for the UE scheme as $\textsf {sk} _0\leftarrow \mathsf {Setup} (1^{\lambda })$. It then recursively updates this secret key $(e+1)$ times for some arbitrarily chosen epoch e, as

  $$\begin{aligned} ( \textsf {sk} _j,\varDelta _{j-1,j})\leftarrow \mathsf {Next} ( \textsf {sk} _{j-1}) \text { for each } j\in [e+1]. \end{aligned}$$

  Finally, it chooses two messages $\textsf {m} _0, \textsf {m} _1\in \mathcal {M}$ such that $\textsf {m} _0\ne \textsf {m} _1$, sets

  $$\begin{aligned} \textsf {ct} ^{*}_0 = \mathsf {Enc} ( \textsf {sk} _{e}, \textsf {m} _0),\quad \textsf {ct} ^{*}_1 = \mathsf {Enc} ( \textsf {sk} _{e}, \textsf {m} _1), \end{aligned}$$

  and outputs the secret key/public key pair $( \textsf {sk} _{\text {PKE}}, \textsf {pk} _{\text {PKE}})$ as

  $$\begin{aligned} \textsf {sk} _{\text {PKE}} = \textsf {sk} _{e+1},\quad \textsf {pk} _{\text {PKE}} = \left( ( \textsf {m} _0, \textsf {ct} ^{*}_0),( \textsf {m} _1, \textsf {ct} ^{*}_1),\varDelta _{e,e+1}\right) . \end{aligned}$$

• Encryption: To encrypt a bit , the encryption algorithm outputs a randomized update of $\textsf {ct} ^{*}_b$ to the epoch $e+1$ using the publicly available update token $\varDelta _{e,e+1}$. More formally, on input a bit , the encryption algorithm outputs

  $$\begin{aligned} \textsf {ct} _{\text {PKE}} \leftarrow \mathsf {Update} (\varDelta _{e,e+1}, \textsf {ct} ^{*}_b). \end{aligned}$$

• Decryption: On input a ciphertext $\textsf {ct} _{\text {PKE}}$, the decryption algorithm computes

  $$\begin{aligned} \textsf {m} ' = \mathsf {Dec} ( \textsf {sk} _{\text {PKE}}, \textsf {ct} _{\text {PKE}}). \end{aligned}$$

  If $\textsf {m} ' = \textsf {m} _b$ for some , it outputs b. Otherwise, it outputs $\bot$.

Correctness is straightforward to verify. We now formally prove the following theorem.

Theorem 3

If $\mathsf {UE}$ is IND-UPD secure, then the aforementioned PKE scheme is IND-CPA secure.

Proof

Let $\mathcal {A}$ be an adversary that breaks the IND-CPA security of the PKE scheme with non-negligible advantage $\varepsilon$. We construct an algorithm $\mathcal {B}$ that breaks the IND-UPD security of $\mathsf {UE}$ with advantage $\varepsilon ' = \varepsilon /2$. $\mathcal {B}$ proceeds as follows:

• 1. $\mathcal {B}$ plays the IND-UPD security game with the challenger for $\mathsf {UE}$ till some epoch $e-1$ for some arbitrarily chosen challenge epoch e. At this point, $\mathcal {B}$ chooses a pair of arbitrary messages $\textsf {m} _0, \textsf {m} _1\in \mathcal {M}$ such that $\textsf {m} _0\ne \textsf {m} _1$, and queries the $\mathcal {O}_{\mathsf {Enc}}$ oracle to obtain $( \textsf {ct} _0, \textsf {ct} _1)$, where

  $$\begin{aligned} \textsf {ct} _0 = \mathsf {Enc} ( \textsf {sk} _{e-1}, \textsf {m} _0),\quad \textsf {ct} _1 = \mathsf {Enc} ( \textsf {sk} _{e-1}, \textsf {m} _1). \end{aligned}$$

• 2. $\mathcal {B}$ outputs $( \textsf {ct} _0, \textsf {ct} _1)$ as the pair of challenge ciphertexts, and receives the challenge ciphertext $\textsf {ct} ^{*}_{e}$, which is a randomized update of $\textsf {ct} _b$ to the epoch e for .

• 3. Next, $\mathcal {B}$ issues the following additional queries:

  • (a) It queries the $\mathcal {O}_{\mathsf {Update}}$ oracle to receive $\widetilde{ \textsf {ct} }^{*}_{e}$, which is a randomized update of $\textsf {ct} _1$ to the epoch e.

  • (b) It issues a query to the $\mathcal {O}_{\mathsf {Next}}$ oracle, followed by a token-query to the $\mathcal {O}_{\mathsf {corrupt}}$ oracle, to obtain an update token $\varDelta _{e,e+1}$.

  Note that none of the aforementioned queries violate any of the constraints described in the IND-UPD security experiment.

• 4. $\mathcal {B}$ now provides the adversary $\mathcal {A}$ with the public key $\textsf {pk} _{\text {PKE}}$, where

  $$\begin{aligned} \textsf {pk} _{\text {PKE}} = \left( ( \textsf {m} _0, \textsf {ct} ^{*}_e),( \textsf {m} _1,\widetilde{ \textsf {ct} }^{*}_{e}),\varDelta _{e,e+1}\right) . \end{aligned}$$

• 5. $\mathcal {B}$ uniformly samples and outputs the challenge ciphertext $\textsf {ct} ^{*}_{\text {PKE}}$, where

  $$ \textsf {ct} ^{*}_{\text {PKE}} = {\left\{ \begin{array}{ll} \mathsf {Update} (\varDelta _{e,e+1}, \textsf {ct} ^{*}_e) &{} \text {if}~b' = 0,\\ \mathsf {Update} (\varDelta _{e,e+1},\widetilde{ \textsf {ct} }^{*}_{e}) &{} \text {if}~b' = 1. \end{array}\right. } $$

• 6. $\mathcal {B}$ outputs whatever $\mathcal {A}$ outputs.

Observe that when $b=0$, the distribution of the public key $\textsf {pk} _{\text {PKE}}$ in the view of $\mathcal {A}$ is exactly as in the real IND-CPA experiment. On the other hand, if $b=1$, then $\textsf {ct} ^{*}_e$ and $\widetilde{ \textsf {ct} }^{*}_{e}$ are sampled from the same distribution. It follows that the advantage of $\mathcal {B}$ in the IND-UPD experiment is $\varepsilon ' = \varepsilon /2$. This completes the proof of Theorem 3.

5 Negative Results in Quantum Setting

In this section we show that any homomorphic one-way function (HOWF) with exact/unbounded homomorphism over abelian groups can be broken using a quantum algorithm. Since exact (or unbounded) KHwPRFs (and hence KHPRFs) over abelian groups trivially imply unbounded HOWFs, it follows that there is no secure construction of an unbounded KHPRF/KHwPRF in quantum world. As a result, a secure KHwPRF either needs to have an approximate homomorphism, or the homomorphism should hold over a non-abelian group.

At a high level, given any abelian group with certain conditions there are known quantum algorithms to determine the structure of the group. That is, given an abelian group $\mathcal {G}$, there is an efficient quantum algorithm to find (an efficiently computable) isomorphism $\psi : \mathcal {G} \rightarrow \mathbb {Z}_{q_1} \oplus \cdots \oplus \mathbb {Z}_{q_m}$. We apply this to both the input and output group of a candidate HOWF f. Then we show a simple classic algorithm that given these isomorphisms over the input and output group of f, one can simply break one-wayness of f.

Theorem 4

Let $f: \mathcal {X} \rightarrow \mathcal {Y}$ be a (classic) HOWF such that $\mathcal {X}$ and $\mathcal {Y}$ are abelian groups, and there exists an efficient algorithm to find a generating set for $\mathcal {Y}$. There exists a polynomial quantum algorithm that breaks the one-wayness of f with non-negligible advantage.⁷

First we recall the following fact from algebra. A proof can be found in any standard textbook.

Theorem 5

Any finite abelian group is isomorphic to a direct sum of cyclic groups, and each cyclic group has a prime power order.

We also rely on the following quantum algorithm (see [CM01] and Section 6.2 of [Chi17] for more details).

Theorem 6

Let $\mathcal {G}$ be a finite abelian group such that (1) each element of $\mathcal {G}$ has a unique decoding, (2) there is an efficient algorithm to do group operations on the elements of $\mathcal {G}$, and (3) there is an efficient algorithm to find a generating set for $\mathcal {G}$. There is a polynomial time quantum algorithm such that decomposes the group $\mathcal {G}$ as

$$\begin{aligned} \mathcal {G} = \langle g_1 \rangle \oplus \cdots \oplus \langle g_M \rangle , \end{aligned}$$

in terms of the generators $g_1, \ldots , g_M$, and for every $m, m' \in [M]$ such that $m \ne m'$ we have $\langle g_m \rangle \cap \langle g_{m'} \rangle = \{e\}$, where e is the identity element of $\mathcal {G}$. Moreover, the isomorphism

(in both ways) can be computed efficiently.

Now we are ready to proceed to the proof of Theorem 4. Let $f : \mathcal {X} \rightarrow \mathcal {Y}$ be an unbounded HOWF such that $\mathcal {X}$ and $\mathcal {Y}$ are abelian groups. Given a challenge $y^* \in \mathcal {Y}$ such that $y^* := f(x^*)$ for some uniform $x^* \leftarrow \mathcal {X}$, we want to find a preimage x such that $f(x) = y^*$. Let

$$\begin{aligned} \tilde{\mathcal {X}} := \mathbb {Z}_{p_1} \oplus \cdots \oplus \mathbb {Z}_{p_M}\quad ,\quad \tilde{\mathcal {Y}} := \mathbb {Z}_{q_1} \oplus \cdots \oplus \mathbb {Z}_{q_N} \end{aligned}$$

be the decomposition of groups $\mathcal {X}$ and $\mathcal {Y}$, respectively, where $p_i$ (respectively, $q_j$) is a prime power for $m \in [M]$ (respectively, $n \in [N]$). We fix some arbitrary order for the cyclic groups, and we call $\tilde{\mathcal {X}}$ an explicit representation of $\mathcal {X}$. Using Theorem 6, we can efficiently compute the isomorphisms $\psi _{\mathcal {X}}, \psi _{\mathcal {Y}}$ (and their inverses) for any element in the domain of the isomorphism where

$$\begin{aligned} \psi _{\mathcal {X}}: \mathcal {X} \rightarrow \tilde{\mathcal {X}}\quad ,\quad \psi _{\mathcal {Y}}: \mathcal {Y} \rightarrow \tilde{\mathcal {Y}}. \end{aligned}$$

We define $\tilde{f} : \tilde{\mathcal {X}} \rightarrow \tilde{\mathcal {Y}}$ as the analog of f over the explicit representations of $\mathcal {X}$ and $\mathcal {Y}$, i.e., define

$$\begin{aligned} \tilde{f}(\tilde{x}) = \psi _{\mathcal {Y}}(f(\psi _{\mathcal {X}}^{-1}(\tilde{x}))). \end{aligned}$$

It is not hard to see that $f(x) = y$ is equivalent to $\tilde{f}(\psi _{\mathcal {X}}(x)) = \psi _{\mathcal {Y}}(y)$. Because the isomorphisms $\psi _{\mathcal {X}}, \psi _{\mathcal {Y}}$ and their inverses are efficiently computable, it is enough to show an attack against one-wayness of $\tilde{f}$.

For each $n \in [N]$, we define $\mathbf {e}_n \in \mathbb {Z}_{p_1} \oplus \, \cdots \oplus \, \mathbb {Z}_{p_N}$ to be the (unit) vector whose nth component is 1, and all other components are 0.⁸ For an element $\tilde{y} \in \tilde{\mathcal {Y}}$, let $[\tilde{y}]_{m} \in \mathbb {Z}_{q_m}$ be the mth component of $\tilde{y}$. We compute the index set $I_m$ for each $m \in M$ as

$$\begin{aligned} I_m = \{n \in [N] \mid [\tilde{f}(\mathbf {e}_n)]_{m} \ne 0 \}. \end{aligned}$$

All index sets $\{I_m\}_{m \in [M]}$ can be computed efficiently since both N and M are polynomially bounded. Define a vector of variables $\mathbf {z}= (z_1, \ldots , z_N) \in \mathbb {Z}^N$, and for each $m \in [M]$, consider the following system of modular equations where $\{z_i\}_{i \in I_m}$ are the (unknown) variables:

$$\begin{aligned} S_m: \quad \sum _{i \in I_m} z_i [\tilde{f}(\mathbf {e}_i)]_m \equiv [\tilde{y}]_m \pmod {q_m} \end{aligned}$$

Consider the following observations:

• Without loss of generality we can assume that for two distinct $m, m' \in [M]$, we have $\text{ gcd }(q_m, q_m') = 1$. If $q_m = q_m'$, we can simply merge $S_m$ and $S_{m'}$. If $q_m < q_{m'}$ and $\text{ gcd }(q_m, q_m') > 1$, we can “lift” the equation in $S_{m'}$ simply by multiplying the both sides by $q^{m'}/q^m$ and adding the resulting equation to $S_{m'}$. We refer to this part as “merging step”.

• Observe that for any two integers $p> 1, q > 1$, if there is a non-trivial homomorphism from $\mathbb {Z}_p$ to $\mathbb {Z}_q$ then either $p \mid q$ or $q \mid p$. Therefore, if $z_n$ appears in $S_m$ (or equivalently $n \in I_m$), we either have $p_n \mid q_m$ or $q_m \mid p_n$.

Let $\overline{M} \subseteq M$ be the set of indices after the “merging step”. Using the previous observations, it follows that

• For any two distinct $\overline{m}_1, \overline{m}_2 \in \overline{M}$, we have $\text{ gcd }(q_{\overline{m}_1}, q_{\overline{m}_2}) = 1$.

• For any $n \in N$, there is at most one $\overline{m} \in \overline{M}$ such that the variable $z_n$ appears in $S_{\overline{m}}$.

Each system of equation(s) $S_{\overline{m}}$ can be seen as a system of linear equation(s) over the group $\mathbb {Z}_{q_{\overline{m}}}$, and it can solved using the known algorithms for solving linear equations over finite abelian groups, e.g., [GR02]. One can equivalently interpret each $S_{\overline{m}}$ as a system of equations over the finite ring $\mathbb {Z}_{q_{\overline{m}}}$ (since $q_{\overline{m}}$ is not necessarily prime).

By solving each system $S_{\overline{m}}$, we can determine the vector $\mathbf {z}\in \mathbb {Z}^N$. Finally, we output $\tilde{x}$ as the preimage of $\tilde{y}$ the attacker where

$$\begin{aligned} \tilde{x} = (z_1 \bmod p_1, \ldots , z_N \bmod p_n). \end{aligned}$$

By construction, we know that the vector $\mathbf {z}$ satisfies all system of equation(s) $\{S_m\}_{m \in M}$. It follows that $\tilde{f}(\tilde{x}) = \tilde{y}$, as required.

Building Quantum-Secure Primitives from Abelian Groups. Our results here may have some implications for the construction of quantum-secure primitives over abelian groups. For instance, in [AMPR19], the authors showed that many public-key cryptosystems can be built from generic primitives with exact homomorphism. Our results here give evidence that such constructions are not going to be quantum-secure when instantiated with new assumptions that rely on abelian groups. Lattice-based primitives do not support exact homomorphisms, which makes them immune to a wide class of quantum attacks. However, there do exist other assumptions relying on abelian groups, such as isogeny-based assumptions [JD11], for which similar notions of homomorphism are yet to be explored [dOPS18].