Fact-checked by Grok 2 weeks ago

Pseudorandom function family

A pseudorandom function family (PRF) is an indexed collection of efficiently computable deterministic functions, each mapping from a fixed input domain to a fixed output range, such that when the index (secret key) is chosen uniformly at random, no probabilistic polynomial-time algorithm can distinguish the output of a function from the family from the output of a truly random function mapping between the same domains, except with negligible probability.^[1]^[2] The concept was formalized by Oded Goldreich, Shafi Goldwasser, and Silvio Micali in 1986, who demonstrated a construction of such families from any pseudorandom generator capable of expanding its input length, using a tree-based approach to evaluate functions on inputs represented as paths in a full binary tree.^[2] This construction implies that pseudorandom function families exist if and only if one-way functions exist, establishing their foundational role in computational cryptography.^[3] Pseudorandom function families serve as a core building block in symmetric-key cryptography, enabling secure constructions for message authentication codes (MACs), stream ciphers, and pseudorandom permutations used in block cipher modes of operation.^[4] For instance, they underpin efficient authentication schemes where a shared key indexes the function to verify message integrity without revealing the key, and they facilitate key derivation functions in protocols requiring multiple pseudorandom outputs from a single secret.^[2] More advanced applications include oblivious RAM simulations to hide access patterns and resettable zero-knowledge proofs for secure multi-party computation.^[3]

Background and Motivations

Random functions

A random function in cryptography is defined as a function chosen uniformly at random from the set of all possible functions mapping a finite domain to a finite codomain, exhibiting no inherent structure or predictability.^[2] This ideal primitive can be conceptualized as a lookup table where each input-output pair is independently selected, ensuring complete randomness in the mapping. The defining properties of a random function include the independence and uniform distribution of outputs for any set of distinct inputs, with each output drawn uniformly from the codomain.^[5] It operates deterministically, returning the same value for repeated queries to the same input, while providing fresh random responses for unseen inputs, akin to an oracle that maintains consistency across evaluations.^[5] These characteristics make random functions a cornerstone for idealized models in cryptographic proofs. Despite their theoretical appeal, random functions are highly impractical for real-world implementation due to exponential resource demands. Specifying a single random function over a domain of size $2^m and codomain of size n requires \log_2(n^{2^m}) = 2^m \cdot \log_2 n bits of storage, rendering it infeasible even for small m, such as m=20.^[2] Moreover, efficient evaluation necessitates instant access to this vast table, which is impossible without prohibitive computation and memory costs for large domains.^[2] In cryptographic analyses, random functions are frequently employed to model ideal primitives, such as hash functions treated as random oracles that map arbitrary inputs to fixed-length random outputs.^[6] While direct realization is unattainable, this idealization facilitates proofs of security under perfect randomness assumptions.

Motivations for pseudorandom functions

In cryptographic protocols, ideal random functions serve as powerful abstractions for achieving security, but they are computationally infeasible to implement directly, as they would require storing and looking up enormous tables of independent random values for every possible input.^[7] Pseudorandom function (PRF) families address this limitation by providing efficient, deterministic algorithms that compute function values on demand using a short secret key, mimicking the behavior of random functions for all practical purposes under computational constraints.^[8] This efficiency is essential for real-world systems, where protocols must run quickly on limited hardware without relying on infeasible storage or randomness generation.^[2] The concept of PRFs was introduced in 1986 by Oded Goldreich, Shafi Goldwasser, and Silvio Micali to extend the utility of pseudorandom generators (PRGs) beyond producing single long pseudorandom strings, enabling broader applications in cryptography where function-like oracles are needed.^[2] Their work was motivated by the desire to construct objects that exhibit "random-like" properties—such as unpredictability on distinct inputs—while being efficiently computable and keyed, thus bridging theoretical ideals with practical designs under the assumption of one-way functions.^[2] This historical development marked a key step in establishing computational pseudorandomness as a foundation for symmetric cryptography.^[8] PRFs play a crucial role in reductionist security proofs, where the security of a cryptographic scheme against a PRF adversary implies its security in an ideal model using truly random functions, facilitating the analysis and design of practical primitives like encryption and authentication.^[8] Unlike PRGs, which stretch a short seed into a fixed-length output that can only be queried once effectively, PRFs support multiple adaptive queries to the same keyed function, providing oracle-like access that better models the repeated evaluations required in most protocols.^[9] This extension allows PRFs to serve as versatile building blocks for achieving provable security in diverse applications.^[7]

Formal Definition

Definition of a PRF family

A pseudorandom function family (PRF family) is formally defined as an efficient collection of functions indexed by secret keys, enabling the emulation of random functions in computational models. Specifically, it consists of a keyed function F: \{0,1\}^\kappa \times \mathcal{D} \to \mathcal{R}, where \kappa is the security parameter representing the key length, \mathcal{D} is the input domain (often \{0,1\}^n for n = O(\kappa)), and \mathcal{R} is the output range (typically \{0,1\}^m with m \leq n). This syntax allows the family to map key-input pairs to outputs deterministically and efficiently.^[2] The structure of the PRF family is given by the set \{F_k\}_{k \in K}, where K = \{0,1\}^\kappa is the key space with |K| = 2^\kappa, and each F_k: \mathcal{D} \to \mathcal{R} is defined by F_k(x) = F(k, x) for x \in \mathcal{D}. This indexing ensures that, with a secret key k chosen uniformly at random from K, the selected function F_k appears as an arbitrary member of the family of all possible functions from \mathcal{D} to \mathcal{R}. The large key space size $2^\kappa is chosen to make brute-force enumeration of keys computationally infeasible for polynomial-time adversaries.^[2] Efficiency requirements are central to the definition: keys are generated by sampling uniformly from \{0,1\}^\kappa, a process that runs in negligible time. The evaluation of F(k, x) must be performed by a deterministic algorithm that runs in time polynomial in \kappa and |x|, where |x| is the bit length of the input x \in \mathcal{D}. This polynomial-time computability distinguishes PRF families from ideal random functions, which are intractable to evaluate directly.^[7]

Security model

The security of a pseudorandom function (PRF) family F = \{F_k : \{0,1\}^n \to \{0,1\}^m \}_{k \in \{0,1\}^\lambda} is defined via an indistinguishability experiment that pits a probabilistic polynomial-time (PPT) adversary A against two worlds: the real world, where the adversary interacts with an oracle implementing F_k for a randomly chosen key k, and the ideal world, where the oracle implements a truly random function \rho that maps inputs consistently to uniformly random outputs. In the experiment, a random bit b \in \{0,1\} is chosen; if b = 0, the oracle O(x) = F_k(x) for k \leftarrow \{0,1\}^\lambda; if b = 1, the oracle O(x) = \rho(x), where \rho is drawn from the set of all functions from \{0,1\}^n to \{0,1\}^m. The adversary A receives input $1^\lambda (the security parameter) and makes adaptive queries to O, receiving responses O(x_i) for chosen inputs x_i, before outputting a guess b' \in \{0,1\} for b. The family F is secure if no PPT adversary can distinguish the worlds with non-negligible advantage.^[10]^[11] The formal advantage of adversary A against F is given by

\mathrm{Adv}^{\mathrm{PRF}}_{F,A}(\lambda) = \left| \Pr\left[A^{F_k}(1^\lambda) = 1 \mid k \leftarrow \{0,1\}^\lambda \right] - \Pr\left[A^\rho(1^\lambda) = 1 \mid \rho \leftarrow \mathrm{Rand}(\{0,1\}^n, \{0,1\}^m) \right] \right|,

where A^G(1^\lambda) = 1 denotes the event that A outputs 1 after interacting with oracle G, and \mathrm{Rand}(\{0,1\}^n, \{0,1\}^m) is the distribution over all $2^{m \cdot 2^n} possible functions. The PRF family F is secure if, for every PPT adversary A, \mathrm{Adv}^{\mathrm{PRF}}_{F,A}(\lambda) is negligible in \lambda, meaning it is smaller than any inverse polynomial $1/p(\lambda) for sufficiently large \lambda. This notion was introduced by Goldreich, Goldwasser, and Micali as a computational analogue to truly random functions, ensuring that even after polynomially many queries, the outputs appear random to efficient observers.^[12]^[10] Adversaries in this model operate in the adaptive query setting, where they may choose each query x_i based on previous responses, up to a polynomial number q(\lambda) of queries, with q depending on the running time of A. The random function \rho in the ideal world is typically implemented as a lookup table that assigns a fresh random output to each unseen input and returns consistent values for repeated inputs, preserving the functional consistency required for indistinguishability. Security holds against all such PPT adversaries, capturing the computational hardness assumption that no efficient algorithm can exploit the structure of F to predict or distinguish outputs beyond random guessing.^[11]^[10] Proofs of PRF security often rely on hybrid arguments to bridge the real and ideal worlds; for instance, one common structure uses a sequence of hybrids H_1 (fully using the PRF oracle) to H_0 (fully random oracle), where each consecutive hybrid differs in a single query's response, allowing the advantage to be bounded by the sum of distinguishing advantages between adjacent hybrids, typically shown negligible via reductions to underlying primitives. This approach provides a modular way to establish security for constructions of PRFs.^[11]^[12]

Properties and Extensions

Indistinguishability criteria

The indistinguishability criteria for a pseudorandom function (PRF) family \mathcal{F} center on computational indistinguishability from a family of truly random functions. Specifically, no probabilistic polynomial-time (PPT) distinguisher \mathcal{A} can distinguish outputs from \mathcal{F} (when a key is chosen uniformly at random) from outputs of a random function with non-negligible advantage, where the advantage is defined as the absolute difference between the probabilities that \mathcal{A} outputs 1 in the two cases. This notion was formalized by Goldreich, Goldwasser, and Micali, who showed that such families exist if pseudorandom generators (PRGs) exist, thereby linking PRF security to the existence of one-way functions via the Håstad-Impagliazzo-Levin-Luby (HILL) construction.^[13] The distinguisher is modeled as a uniform PPT algorithm, meaning it is described by a fixed Turing machine that runs in time polynomial in the security parameter n, without access to non-uniform advice strings that grow with n.^[14] A key aspect of PRF indistinguishability is its resilience to multiple adaptive queries. Unlike PRGs, which provide security only for a single stretched output, PRF security holds even if the distinguisher makes up to q(n) queries, where q is any polynomial in n, and each query can depend on previous responses.^[7] In the standard security game, the distinguisher interacts with an oracle that is either the PRF under a random key or a truly random function, and adaptivity ensures that the queries simulate realistic adversarial access patterns. This multi-query model strengthens the primitive, as breaking indistinguishability requires exploiting correlations across evaluations, which is computationally infeasible under the negligible advantage bound—typically less than $1/n^c for any constant c and sufficiently large n.^[15] PRF security typically assumes the existence of one-way functions, with PRGs serving as an intermediate primitive in constructions like the Goldreich-Goldwasser-Micali (GGM) tree-based approach. For instance, the GGM construction yields a PRF secure against PPT distinguishers if the underlying PRG stretches seeds by a super-logarithmic factor. While non-uniform adversaries (equipped with polynomial-length advice) offer a stricter model capturing preprocessing attacks, the standard PRF definition focuses on uniform PPT adversaries to align with practical computational limits.^[16] Under these criteria, PRFs enable pseudorandom permutations (PRPs) via the Luby-Rackoff construction, which builds a secure PRP from a PRF using a four-round Feistel network, ensuring indistinguishability against adaptive chosen-plaintext queries.

Oblivious pseudorandom functions

Oblivious pseudorandom functions (OPRFs) extend standard pseudorandom functions to a two-party setting, enabling a client with input x and a server with key k to jointly compute the evaluation F_k(x) such that the client receives the output while the server gains no information about x. The protocol ensures that the computation privately realizes this functionality, where the server outputs nothing, and the overall interaction hides the client's input from the server. This primitive was first formalized by Freedman, Ishai, Pinkas, and Reingold in their work on privacy-preserving keyword search.^[17] OPRF security encompasses two core properties: pseudorandomness and obliviousness. Pseudorandomness guarantees that, in the presence of a malicious server, the client's view of the output is computationally indistinguishable from the evaluation of a truly random function, provided the client does not know the key k. Obliviousness ensures that, even against a malicious client, the server's view of the protocol transcript reveals no information about the input x, simulating independence from x. These properties build on the indistinguishability criteria of standard PRFs but adapt them to the multi-party oblivious evaluation paradigm.^[18] The formal security model for OPRFs employs a simulation-based approach, distinguishing between the real world (protocol execution) and the ideal world (interaction with a trusted functionality). Security holds if, for any probabilistic polynomial-time adversary, there exists a simulator that generates views indistinguishable between the two worlds, even under malicious corruption of one or both parties. Specifically, when the server is corrupted, the simulator ensures the client's output remains pseudorandom; when the client is corrupted, it hides x from the server's view while maintaining correctness. This model, often framed in the Universal Composability framework, provides composable security guarantees for OPRFs.^[18] In 2024, the IETF standardized OPRFs, verifiable OPRFs (VOPRFs), and partially oblivious OPRFs (POPRFs) using prime-order groups, including elliptic curves, in RFC 9497, facilitating broader adoption in protocols like Privacy Pass.^[19] Recent advances as of 2025 include post-quantum constructions based on lattices, enhancing resistance to quantum attacks.^[20] OPRFs find use in privacy-preserving computations, such as enabling secure outsourcing of function evaluations without input disclosure.^[18]

Constructions

From pseudorandom generators

One foundational construction of a pseudorandom function (PRF) family from a pseudorandom generator (PRG) is the Goldreich-Goldwasser-Micali (GGM) method, which leverages a tree-based structure to simulate a random function over a large domain.^[21] This construction assumes the existence of a secure length-doubling PRG G: \{0,1\}^n \to \{0,1\}^{2n}, where G(s) = G^0(s) \Vert G^1(s) and each G^b(s) (for b \in \{0,1\}) outputs n bits, indistinguishable from uniform randomness by any efficient distinguisher.^[21] The PRF family \{F_k: \{0,1\}^n \to \{0,1\}^n \mid k \in \{0,1\}^n \} is then defined using a full binary tree of depth n, with the root labeled by the key k. Each internal node labeled by a seed s expands to two children via G^0(s) (left, for bit 0) and G^1(s) (right, for bit 1). For an input x = x_1 x_2 \dots x_n \in \{0,1\}^n, F_k(x) is computed as the label of the leaf reached by starting at the root and following the path dictated by the bits of x: iteratively set s_0 = k, s_i = G^{x_i}(s_{i-1}) for i = 1 to n, and output s_n. This requires n sequential applications of G.^[21] The security of this PRF relies on a hybrid argument that reduces distinguishability from the PRG's security. Consider a distinguisher D making q adaptive queries to either the real PRF or an ideal random function. For each query path (corresponding to an input x), define n+1 hybrids H_0, H_1, \dots, H_n, where H_0 uses truly random labels along the path (ideal), H_n uses the full GGM tree (real), and H_i uses random labels for the first i edges of the path but pseudorandom thereafter. The difference between consecutive hybrids H_i and H_{i+1} involves replacing one PRG output with uniform randomness, so if D distinguishes H_i from H_{i+1} with non-negligible advantage, it contradicts the PRG's security. Over all q queries and n levels per query, the total distinguishing advantage for the PRF is at most q n \epsilon, where \epsilon is the PRG's distinguishing advantage.^[21] Formally, if G is a (t, \epsilon)-secure PRG, then the GGM PRF F is a (t' , q n \epsilon)-secure PRF, where t' = t - O(n q) accounts for the additional time to simulate the hybrids.^[21] This establishes that secure PRGs imply secure PRFs under standard computational assumptions.^[21] A limitation of the basic GGM construction is that the output length is fixed to n bits, matching the seed size. Extensions for variable-length outputs can be achieved by composing the leaf value with an additional PRG to expand it as needed, preserving security via a similar hybrid argument.^[21]

Direct constructions and variants

Direct constructions of pseudorandom functions (PRFs) often leverage pseudorandom permutations (PRPs) or hash functions as building blocks, providing efficient alternatives to PRG-based methods. A key result is that any secure PRP can serve directly as a PRF in the standard model, with the distinguishing advantage differing by at most q^2 / 2^{n+1}, where q is the number of queries and n is the block length; this negligible loss follows from the fact that collisions in a PRF can be used to distinguish a PRP from a random permutation.^[22] For example, the Advanced Encryption Standard (AES), modeled as a secure PRP, functions as a PRF when used in modes like counter mode, enabling its widespread adoption in cryptographic protocols.^[23] The Luby-Rackoff construction provides a structured way to build PRPs from PRFs using Feistel networks, but the converse implication allows PRPs like AES to yield PRFs without additional overhead beyond the permutation itself.^[24] This reduction ensures that the security of the PRP transfers to the PRF with only a minor degradation, preserving computational indistinguishability against polynomial-time adversaries.^[22] Hash-based constructions offer another direct avenue for PRFs, particularly through keyed hash functions. The Hash-based Message Authentication Code (HMAC), which nests a cryptographic hash function within itself using a secret key, is proven to be a secure PRF assuming the underlying compression function is itself a PRF; this holds without requiring collision resistance of the hash.^[25] Modern variants extend these constructions for specialized applications, such as authenticated encryption with associated data (AEAD). In Galois/Counter Mode (GCM), the block cipher (e.g., AES) acts as a PRF to generate the keystream via counter mode, combined with a polynomial-based MAC for authentication; this tweak-like use of the counter input ensures nonce-based security up to $2^{32} blocks under the PRP assumption.^[26] For post-quantum security, lattice-based PRFs derived from the Learning With Errors (LWE) problem provide quantum-resistant alternatives; for instance, key-homomorphic PRFs from LWE enable efficient evaluation with small modulus sizes while maintaining security under the standard LWE assumption in the standard model.^[27] These constructions achieve PRF security with polynomial-time reductions to LWE hardness, supporting applications like key derivation in quantum-safe protocols.^[28]

Applications

In symmetric cryptography

In symmetric cryptography, pseudorandom function (PRF) families serve as foundational building blocks for constructing secure message authentication codes (MACs) and encryption modes, leveraging their indistinguishability from random functions to ensure confidentiality and integrity. A direct application is using a PRF to generate authentication tags, where the tag for a message m is computed as F_k(m) with secret key k. This construction achieves unforgeability under chosen-message attacks (UF-CMA), as any forgery would imply distinguishing the PRF from a truly random function through oracle access, with security reducing directly to the PRF's advantage via hybrid arguments.^[29] For fixed-length messages, this provides a simple and efficient MAC, though extensions like pairwise-independent hashing may be needed for variable-length inputs to achieve stronger security models such as UF-CMVA, with error bounds scaling as O(Q_V \epsilon + Q_V Q_T / 2^\mu), where Q_V and Q_T are verification and tagging queries, and \mu is the tag length.^[29] PRFs also underpin various encryption modes by generating pseudorandom keystreams or intermediate values. In counter (CTR) mode, the PRF produces a keystream for XORing with the plaintext: for a nonce r and blocks m_1, \dots, m_\ell, the ciphertext is (r, F_k(r) \oplus m_1, \dots, F_k(r + \ell - 1) \oplus m_\ell), often implemented with F_k as a block cipher in counter configuration, such as E_k(\text{IV} \| i). This yields chosen-plaintext attack (CPA) security with advantage at most $2 \cdot \text{PRF-Adv} + 2T^2 \ell / 2^n, where T is the number of queries and n the block size, assuming negligible PRF distinguishability and birthday-bound compliance.^[30] For authentication, the cipher block chaining (CBC) MAC constructs a tag by iteratively applying the PRF: t_0 = 0, t_i = F_k(t_{i-1} \| m_i) for message blocks m_i, with the final t_\ell as the tag (padded for variable lengths). Security against forgery is bounded by O(q \sigma / 2^n), where q is the number of queries and \sigma the total blocks processed, reducing to the underlying PRF's security via collision analysis in output chains.^[31] Authenticated encryption with associated data (AEAD) schemes further integrate PRFs for simultaneous encryption and authentication, handling nonces to prevent replays. In Galois/Counter Mode (GCM), a PRF (typically a block cipher like AES in CTR mode) generates the keystream, while authentication derives from a universal hash over the ciphertext and associated data, combined with a PRF-derived value for the tag; nonce misuse resistance relies on the PRF's randomness for unique session keys. Similarly, Offset Codebook (OCB) mode employs a PRF to offset message blocks before encryption and computes tags via PRF evaluations on the output, ensuring privacy and authenticity with nonce-based freshness; security proofs bound the advantage to the PRF's under multi-user settings, with overhead linear in message length. These modes balance efficiency and security by avoiding full permutation requirements, unlike raw PRPs. A prominent example is Poly1305, a PRF-based MAC that computes tags via polynomial evaluation over a prime field: for message blocks c_i, the tag is ( \sum c_i r^{16-i} \mod (2^{130}-5) + AES_k(n) ) \mod 2^{128}, where r is a one-time key derived from a nonce n using a PRF like AES, and constrained bits ensure field properties. This yields forgery probability at most $14 D \lceil L/16 \rceil / 2^{106} for L-byte messages and D forgeries, assuming PRF security. Compared to PRP-based MACs like CBC-MAC, Poly1305 offers advantages in speed (under 3.1 cycles per byte on modern CPUs), parallelizability, and key agility without precomputation tables, as it avoids invertibility constraints that complicate nonce handling in permutations.^[32]

In protocol design

Pseudorandom function (PRF) families play a crucial role in key derivation within cryptographic protocols, enabling the expansion of short or low-entropy inputs into multiple cryptographically secure subkeys. The HMAC-based key derivation function (HKDF), specified in RFC 5869, leverages a PRF such as HMAC to perform extraction and expansion steps, first deriving a pseudorandom key from input material and then expanding it into multiple outputs.^[33] This approach ensures that even weakly random keys yield unpredictable subkeys, mitigating risks from poor entropy sources. In the Transport Layer Security (TLS) protocol version 1.3, HKDF is integral to the key schedule, deriving traffic keys, application keys, and other material from the shared secret established during the handshake, thereby supporting secure session establishment across diverse network environments. For password-based key generation, PRFs are employed to stretch low-entropy passwords into robust keys resistant to brute-force attacks. The Password-Based Key Derivation Function 2 (PBKDF2), defined in RFC 2898 and updated in RFC 8018, iterates a PRF (typically HMAC with a hash like SHA-256) thousands of times on the password combined with a salt, amplifying computational cost and producing a fixed-length key suitable for encryption or authentication.^[34] This iteration model balances security against offline attacks with practical usability, making PBKDF2 a standard in protocols requiring user-derived keys, such as secure storage and VPN authentication. In multi-party privacy-preserving protocols, oblivious pseudorandom functions (OPRFs)—an extension of PRFs—enable computations where one party evaluates the function on private inputs without revealing them to the evaluator. OPRFs facilitate private set intersection (PSI) protocols, allowing two parties to identify common elements in their datasets without disclosing full sets, as demonstrated in efficient batched OPRF constructions based on standard assumptions.^[35] Similarly, OPRFs underpin oblivious authentication in messaging systems; for instance, WhatsApp's end-to-end encrypted backup protocol incorporates OPRF-based mechanisms via the OPAQUE protocol for password-protected backups, ensuring the server learns nothing about the user's backup password.^[36] These applications enhance privacy in scenarios like contact discovery and secure data sharing. PRFs also support zero-knowledge proofs by simulating random oracles in the Fiat-Shamir heuristic, transforming interactive proofs into non-interactive ones. In this paradigm, a PRF (often instantiated via a keyed hash) replaces the oracle to generate challenges deterministically from public commitments, preserving soundness and zero-knowledge properties under the random oracle model. This technique is foundational in non-interactive zero-knowledge (NIZK) systems, enabling efficient verification in bandwidth-constrained settings like blockchain transactions. In modern distributed systems, PRFs enable secure key management in blockchains and multi-party computation (MPC). Ethereum's wallet standards and staking protocols, such as those outlined in EIP-2333 and EIP-2334, utilize PRF-based derivation (e.g., via PBKDF2 or HKDF-like expansions) to generate hierarchical keys from mnemonic seeds, ensuring deterministic yet secure key trees for validator operations and withdrawals. In secure MPC, PRFs generate pseudorandom correlations or shares among parties, facilitating efficient joint computations on private inputs without trusted setups, as seen in protocols for bilinear correlations and threshold schemes.^[37] These uses underscore PRFs' versatility in scaling privacy and security across decentralized environments.

References

[1]
Pseudorandom function family - Glossary | CSRC
Definitions: An indexed family of (efficiently computable) functions, each defined for the same particular pair of input and output spaces.Missing: primary | Show results with:primary
[2]
How to construct random functions | Journal of the ACM
A constructive theory of randomness for functions, based on computational complexity, is developed, and a pseudorandom function generator is presented.Missing: original | Show results with:original
[3]
[PDF] Pseudorandom Functions: Three Decades Later
In 1984, Goldreich, Goldwasser and Micali formalized the concept of pseudorandom functions and proposed a construction based on any length-doubling ...
[4]
[PDF] Pseudorandom Functions Revisited: The Cascade Construction and ...
Oct 31, 2005 · Pseudorandom function families are a powerful cryptographic primitive, yielding, in partic- ular, simple solutions for the main problems in ...Missing: primary sources
[5]
[PDF] Lecture 15 1 Pseudorandom Functions and Permutations
The analogous property we would like from F is that it should "look like a random function" when a random key is chosen. ... bits does it take to represent a ...Missing: limitations | Show results with:limitations
[6]
[PDF] Random Oracles are Practical: A Paradigm for Designing Efficient ...
Mihir Bellare. ∗. Phillip Rogaway. †. August 2, 2021. Abstract. We argue that the random oracle model —where all parties have access to a public random oracle ...
[7]
Pseudo-Random Functions - Applied Cryptography Group
Suppose Alice wishes to authenticate herself to Bob, by proving she knows a secret that they share. With PRNG's they could proceed as follows.Missing: primary sources
[8]
[PDF] Chapter 3 Pseudorandom Functions
A pseudorandom function is a family of functions with the property that the input- output behavior of a random instance of the family is “computationally ...Missing: sources | Show results with:sources
[9]
[PDF] Pseudo-Random Generators (PRGs) and Pseudo-Random ...
Sep 6, 2019 · [1] O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. 1986. 4-8.<|control11|><|separator|>
[10]
[PDF] 6 Pseudorandom Functions & Block Ciphers
A pseudorandom function (PRF) is a tool that allows Alice & Bob to achieve the effect of such an exponentially large table of shared randomness in practice. In ...Missing: limitations | Show results with:limitations
[11]
Pseudorandom functions - An intensive introduction to cryptography
The key to understanding schemes using pseudorandom functions is to imagine what would happen if f s f_s fs was be an actual random function instead of a ...Missing: primary sources<|control11|><|separator|>
[12]
None
Error: Could not load webpage.<|control11|><|separator|>
[13]
[PDF] A PSEUDORANDOM GENERATOR FROM ANY ONE-WAY ...
Pseudorandom generators are fundamental to many theoretical and applied aspects of computing. We show how to construct a pseudorandom generator from any one-way ...
[14]
[PDF] 1 Introduction 2 Concrete formalization
Our definition. of PPT refers to a uniform algorithm, with a fixed program size independent of n. (However, in many treatments of cryptography, it is common to ...
[15]
[PDF] From Non-Adaptive to Adaptive Pseudorandom Functions
A pseudorandom function family (PRF), introduced by Goldreich, Goldwasser, and Micali [11], cannot be distinguished from a family of truly random functions.
[16]
[PDF] Weak Pseudorandom Functions in Minicrypt
So in Minicrypt, i.e. under the assumption that one-way functions exist but public-key cryptography does not, the notion of public- and secret-coin weak PRFs ...
[17]
[PDF] Keyword Search and Oblivious Pseudorandom Functions
Abstract. We study the problem of privacy-preserving access to a database. Particularly, we consider the problem of privacy-preserving keyword search.
[18]
[PDF] SoK: Oblivious Pseudorandom Functions - Cryptology ePrint Archive
Mar 4, 2022 · We explain which OPRF constructions can. (or cannot) achieve which properties. Section 4 explains in which models one can formulate OPRF ...
[19]
[PDF] How to Construct Random Functions
GOLDREICH, O., GOLDWasser, S., and MICALI, S. How to construct random functions. Tech. Memo 244, Laboratory for Computer Science, MIT, Cambridge, Mass., Nov ...
[20]
[PDF] PRPs and PRFs - Stanford University
Any secure PRP is also a secure PRF. • Lemma: Let E be a PRP over (K,X). Then for any q-query adversary A: | PRF Adv[A,E] - PRP Adv[A,E] | < q2 / 2|X|.
[21]
[PDF] PRPs and PRFs - Stanford University
Chal. Any secure PRP is also a secure PRF. Goal: build “secure” encryption from a PRP.
[22]
How to Construct Pseudorandom Permutations from Pseudorandom ...
We show how to efficiently construct a pseudorandom invertible permutation generator from a pseudorandom function generator.
[23]
[PDF] New Proofs for NMAC and HMAC: Security without Collision ...
This paper proves that HMAC is a PRF under the sole assumption that the compression function is a PRF. This recovers a proof based guarantee since no known ...
[24]
[PDF] Encrypted Davies-Meyer and Its Dual: Towards Optimal Security ...
The dashed line represents the necessary addition to yield EWCDM. where h is an almost xor universal hash function, p1,p2 are two permutations, and where ν ...
[25]
[PDF] The Security and Performance of the Galois/Counter Mode (GCM) of ...
GCM uses E as a pseudorandom function (PRF). In our analysis, we make use of the well-known result on the use of a PRP as a PRF [4]. Our defini ...
[26]
Key-Homomorphic Pseudorandom Functions from LWE with a Small ...
Feb 24, 2020 · In this work, we provide two new PRF constructions from the LWE problem that each focuses on either minimizing the depth of its evaluation circuit or providing ...
[27]
[PDF] Key Homomorphic PRFs and Their Applications
Feb 2, 2014 · Abstract. A pseudorandom function F : K×X →Y is said to be key homomorphic if given F(k1,x) and F(k2,x) there is an efficient algorithm to ...<|control11|><|separator|>
[28]
[PDF] Symmetric Key Authentication, revisited - Cryptology ePrint Archive
Oct 28, 2012 · Abstract. Traditionally, symmetric-key message authentication codes (MACs) are easily built from pseu- dorandom functions (PRFs).
[29]
[PDF] Symmetric Encryption: PRFs, Counter mode, and ChaCha20 - MIT
Feb 10, 2025 · Encrypting with a pseudorandom function: Counter mode. Last time, Yael demonstrated how to encrypt messages using a pseu- dorandom function.
[30]
[PDF] On The Exact Security of MACs Using PRFs
However, the CBC mode of operation can also be used to construct a MAC when the underlying primitive is a domain preserving pseudo random function (PRF) or a ...
[31]
[PDF] The Poly1305-AES message-authentication code
Mar 29, 2005 · Polynomial-evaluation MACs over prime fields can exploit the multipliers built into many current CPUs, achieving substantially better ...
[32]
RFC 5869 - HMAC-based Extract-and-Expand Key Derivation ...
This document specifies a simple Hashed Message Authentication Code (HMAC)-based key derivation function (HKDF), which can be used as a building block in ...Missing: family | Show results with:family
[33]
RFC 8018 - PKCS #5: Password-Based Cryptography Specification ...
RFC 8018 PKCS #5 v2.1 January 2017 B.1. Pseudorandom Functions Examples of pseudorandom function for PBKDF2 (Section 5.2) include HMAC with SHA-1, SHA-224 ...
[34]
[PDF] Efficient Batched Oblivious PRF with Applications to Private Set ...
ABSTRACT. We describe a lightweight protocol for oblivious evaluation of a pseudorandom function (OPRF) in the presence of semi- honest adversaries.
[35]
[2112.10020] Cryptography from Pseudorandom Quantum States
Dec 18, 2021 · A consequence of (a) is that pseudorandom states are sufficient to construct maliciously secure multiparty computation protocols in the ...