# Questions tagged [pseudo-random-permutation]

A Pseudo-Random Permutation (PRP) is a function that cannot be distinguished (with practical effort) from a permutation selected at random with uniform probability from the family of all permutations on the function's domain.

118 questions
Filter by
Sorted by
Tagged with
177 views

### Is there a method to encrypt relations in between values of a cyclic value set and generate values out of this set with pseudo RNG? (all at user PC)

Is there a pseudo RNG and function $f$ with 1.) The RNG produces a value $v_0$ out of $N$ different values (set $S$). 2.) Independent of the RNG the function $f$ generates $v_{i+1}=f(v_i)$ ...
95 views

### Sponge with PRF instead of PRP

In most uses of Sponge mode of operations such as SHA3 and many of the round-2 candidates in the NIST lightweight cryptography project, the underlaying primitive is a cryptographic permutation - that ...
57 views

### memory-hard KDF that's just a giant permutation?

Why aren't there memory-hard KDF functions that simply build a 1GB permutation and permute it? Then hash the 1GB result. For example, use a hash function (unfixed output mode) on the key+salt and use ...
62 views

72 views

### Dependence of a Pseudorandom Function's Security on its Input/Output Spaces

Let $n$ be a security parameter and $F:\{0,1\}^{\ell_{key}(n)} \times \{0,1\}^{\ell_{in}(n)} \rightarrow \{0,1\}^{\ell_{out}(n)}$ be a keyed function which forms a family of Pseudorandom Functions (...
152 views

### PRP vs PRF for the F-function of a Feistel network

A Feistel network is generally defined with a PRF for its F-function, but PRPs have been used as well. What are the theoretical cryptographic implications of using a PRP instead of a PRF? Does it ...
96 views

### Aside from Keccak, are there any keyed/unkeyed permutations where the choice of all rotation constants is not based on heuristic methods?

I am interested to see examples of cryptographic algorithms (namely, keyed or unkeyed permutations that transform an $n$-bit input to an $n$-bit output) where the choice of all rotation values is not ...
46 views

### PRP, PRF change at next selection?

This is probably a silly question, and similar question was asked before; but I can not figure out what actually is PRP/PRF. For example, it is commented that: A Pseudo Random Function is a ...
105 views

### A well known hash function?

Name a well-known and standardized function $F : \{0,1\}^{256} × \{0,1\}^{128} → \{0,1\}^{128}$ that is believed to be a pseudorandom permutation. I was thinking SHA256, but I am not sure. Can ...
33 views

169 views

### Can we use a PRF as a PRP?

Leaving aside the problem of how to compute the inverse of a PRF F, may we use it also as a PRP? The reciprocal of this statement is true, see for instance Katz and Lindell, Proposition 3.27, when ...
147 views

### Is it possible to apply a pseudo-random permutation (a keyed permutation) to construct a sponge function?

The description of the sponge function on Crypto.Stackexchange contains the following text (source): The cryptographic sponge is a construction scheme for hash functions (and other symmetric ...
120 views

Let $f_k(B)$ denote the underlying function (a pseudo-random permutation) of a block cipher: it uses an $x$-bit key $k$ to encrypt an $y$-bit block $B$. The question: is it possible to make use of $... 0answers 73 views ### Is this a PRP? How can I create a distinguisher to show it isn't? Consider the keyed permutation$F_k : \{0,1\}^2 \to \{0,1\}^2$with two-bit keys defined as$F_k(x) = k\oplus x$. Is this F a PRP? How can I create a distinguisher D and calculate the difference ... 2answers 123 views ### Does encryption using PRP mean indistinguishable encryption against an eavesdropper? I am a student studying cryptography by reading "Introduction to Modern Cryptography". I have some confusion about encryption using PRP (e.g., AES). Briefly speaking, a keyed deterministic ... 1answer 169 views ### How to prove the PRF,$F(k,x) = (k \wedge x ) \oplus k$is PRP? I am trying to understand PRF's and PRP's. I have got a question where I have to decide whether$F(k,x) = (k \wedge x ) \oplus k$(where$k$and$x$are simple$1$bits (1 or 0)) is PRP or not. I am ... 1answer 148 views ### Permutation for which an inverse is a hard problem Is it possible to construct (even if we don't know how) a permutation for which an inverse must exist but is difficult to find (brute force required)? The one way permutation contains no hidden ... 1answer 330 views ### How is a PRP different from PRF? Both can be inverted to get the same input PRP is said to be a bijective function which means that there is a one-to-one mapping with the output. And hence the output can be inverted using the decryption algorithm to get the same input. ... 1answer 128 views ### Using a PRP$\pi: \{0,1\}^{16} \to \{0,1\}^{16}$to construct an ideal cipher Say we have an ideal 16-bit PRP. Since it appears that a permutation with a small domain can be used to turn it into a PRF, which can then be used in a Feistel network. On the surface, it makes it ... 1answer 186 views ### Reproducable pseudorandom permutation I there a way to calculate two similar pseudorandom periodic sequences by exchanging some sort of initial value and generator polynomial? Like a linear-feedback shift register but with a finite ... 0answers 71 views ### why isnt E a secure block cipher Let$\pi : \{0,1\}^n \rightarrow \{0,1\}^n$be a permutation. Let$E(k, x) = \pi(x \oplus k)$where$x,k \in \{0,1\}^n$. Why isn't$E$a secure block cipher? My idea: Suppose$E$is a secure block ... 1answer 263 views ### Why do we use (pseudo) random permutations and not (pseudo) random functions for en- and decryption? Why do we use pseudo random permutations and not pseudo random functions for encryption an decryption? 1answer 149 views ### Security of OFB mode if PRP is used instead of PRF In the cryptography lecture at my university, we had the theorem that (randomized) OFB mode is IND-CPA secure if the used pseudorandom function (PRF) is IND-PRF secure. Afterwards, we investigated ... 1answer 108 views ### A strange phenomenon of the composition of permutations of order 2 Suppose that$f,g,h:X\rightarrow X$are permutations such that$f^{2}=g^{2}=\textrm{Id}_{X}$(i.e.$f,g$have order 2). Let$F=f\circ g$. Let$D_{f,g}$be the distribution that takes the value$n$... 1answer 166 views ### Luby-Rackoff theorem for Generalized Feistel I was reading about Luby-Rackoff theorem from various sources: , , , which says you need at least 3 rounds of a$2$-branch Feistel network to get a PRP if the underlying$f$function is a PRF.... 0answers 82 views ### Are there any pseudo-random permutation algorithms for any number of words in the input independently of the word size (as in MD6 core function)? I am interested in fixed pseudo-random permutation algorithms that are defined for any number of words in the input (but there might be some minimal number of words, e.g. 8), where the word size may ... 1answer 200 views ### How to show that the following function is not a OWF? Given F, which is a Pseudo Random Permutation, I need to prove that the following function f is not a OWF: f(x, y) = Fx(y) My first thought would be to create an adversary which tries and compute Fx-... 2answers 206 views ### Can we always find a key to map a given plaintext block to a given ciphertext block in AES? I am revising for my exams and I have come across this question in a past paper and I am not confident about it at all. Assuming that only the smallest permissible key and block sizes can be used I ... 1answer 126 views ### Security properties of an encryption scheme built from a PRP and a PRG Note: This was my in-class problem last week and potentially will be on the exam tomorrow. Thus, I want to reconfirm my thoughts so that I'll be ready to face this type of question (if appear) ... 0answers 185 views ### Pseudo-random function where the output is inverted using XOR I'm looking to know whether or not this PRF is secure : $$F'(k, x) = F(k, x) ⊕ 1^n$$ knowing that$F$is already a secure PRF for $$\{0, 1\}^n × \{0, 1\}^n → \{0, 1\}^n$$ with, for example,$n= ...
Suppose to have a scheme that works so: $\mathcal{P}_k =:\{P_k\colon \{0,1\}^{2n} \to \{0,1\}^{2n} \}$ is a strong PRP family. Encryption: $\operatorname{Enc}(k,m)=P_k(m\mathbin\Vert r)$, where \$\...