Constrained Keys for Invertible Pseudorandom Functions
A constrained pseudorandom function (PRF) is a secure PRF for which one can generate constrained keys that can only be used to evaluate the PRF on a subset of the domain. Constrained PRFs are used widely, most notably in applications of indistinguishabili
- PDF / 520,669 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 22 Downloads / 263 Views
Abstract. A constrained pseudorandom function (PRF) is a secure PRF for which one can generate constrained keys that can only be used to evaluate the PRF on a subset of the domain. Constrained PRFs are used widely, most notably in applications of indistinguishability obfuscation (iO). In this paper we show how to constrain an invertible PRF (IPF), which is significantly harder. An IPF is a secure injective PRF accompanied by an inversion algorithm. A constrained key for an IPF can only be used to evaluate the IPF on a subset S of the domain, and to invert the IPF on the image of S. We first define the notion of a constrained IPF and then give two main constructions: one for puncturing an IPF and the other for (single-key) circuit constraints. Both constructions rely on recent work on private constrained PRFs. We also show that constrained pseudorandom permutations for many classes of constraints are impossible under our definition.
1
Introduction
Pseudorandom functions (PRFs) [34] and pseudorandom permutations (PRPs) [41] have found numerous applications in cryptography, such as encryption, data integrity, user authentication, key derivation, and others. Invertible PRFs are a natural extension that borrows features from both concepts. An invertible PRF (IPF) is an efficiently-computable injective function F : K × X → Y equipped with an efficient inversion algorithm F−1 : K × Y → X ∪ {⊥}. The inversion algorithm is required to satisfy the following two properties for all k ∈ K: – (1) F−1 k, F(k, x) = x for all x ∈ X . – (2) F−1 (k, y) = ⊥ whenever y is not in the image of f (x) := F(k, x). We say that an IPF F is secure if no poly-bounded adversary can distinguish the following two experiments. In one experiment the adversary is given oracles for the function f (x) := F(k, x) and its inverse f −1 (x) := F−1 (k, x), where k is randomly chosen in K. In the other experiment, the adversary is given oracles for a random injective function g : X → Y and its inverse g −1 : Y → X ∪ {⊥}. These two experiments should be indistinguishable. We define this in detail in The full version of this paper is available at https://eprint.iacr.org/2017/477.pdf. c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part I, LNCS 10677, pp. 237–263, 2017. https://doi.org/10.1007/978-3-319-70500-2_9
238
D. Boneh et al.
Sect. 3. Note that when X = Y, an IPF is the same as a strong pseudorandom permutation [41]. IPFs come up naturally in the context of deterministic authenticated encryption (DAE) [50], as discussed below. A closely related concept called a pseudorandom injection (PRI) [50] is similar to an IPF except for some syntactic differences (an IPF is a pseudorandom injection without additional length constraints and with an empty header). Constrained PRFs. In this paper we define and construct constrained IPFs. It is helpful to first review constrained PRFs [19,21,40]. Recall that a PRF F : K × X → Y is said to be a constrained PRF if one can derive constrained keys from the master PRF key
Data Loading...
