Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
36 views

Definition of Random Permutation and random

When we attack a block cipher by using the differential cryptanalysis and linear cryptanalysis, we distinguish random permutation and cipher text. In this case, I want to know what is definition of ...
2
votes
1answer
54 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 ...
1
vote
0answers
75 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 ...
2
votes
1answer
62 views

Is it possible to make use of a pseudo-random permutation to construct a one-way compression function?

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 $...
1
vote
0answers
56 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 ...
0
votes
2answers
64 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 ...
1
vote
1answer
58 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 ...
3
votes
1answer
83 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 ...
0
votes
1answer
60 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. ...
4
votes
1answer
101 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 ...
2
votes
1answer
104 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 ...
0
votes
0answers
49 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 ...
1
vote
1answer
143 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?
1
vote
1answer
92 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 ...
1
vote
1answer
91 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$ ...
1
vote
0answers
88 views

Luby-Rackoff theorem for Generalized Feistel

I was reading about Luby-Rackoff theorem from various sources: [1], [2], [3], 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....
1
vote
0answers
55 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 ...
3
votes
1answer
87 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-...
4
votes
2answers
171 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 ...
3
votes
1answer
90 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) ...
0
votes
0answers
112 views

Collision resistant Davies-meyer compression function

We suppose $(E,D)$ is a secure $PRP$ , defined on $$(\{0, 1\}^n,\{0, 1\}^n,\{0, 1\}^n) $$ i was asked to find a collision for this compression function : $$ h(H, m) = E(H, m) ⊕ H $$ knowing that ...
1
vote
0answers
109 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= ...
1
vote
1answer
137 views

A Construction of a Cipher from a Single Pseudorandom Permutation

A paper from 1997 A construction of a cipher from a single pseudorandom permutation proposes a cipher in which The message block is XORed with K1 before applying F [a single random permutation], and ...
1
vote
0answers
94 views

CCA-Security Proof of a particular scheme

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 $\...
0
votes
1answer
90 views

What are the properties of a function based on multiple iterations of a pseudo-random permutation?

Let $F(S) = \text{Keccak-}f[1600](S)$. Assuming that the length of $S$ is equal to $1600 \times k$ and if $k$ is greater than $1$, we define a function $F_{k}(S)$ as follows. We note that $S$ is ...
1
vote
0answers
51 views

Security implications of plaintext-padding in an AEAD-scheme

Let's say I have a secure AEAD-scheme like ChaCha20/HMAC and my encrypted blobs need to match a fixed size: Is it OK to apply some padding to my plaintext to match the block-size? Can I use any ...
3
votes
0answers
92 views

What is the expected number of different sequences of bits in the collection that contains $2^{800}$ elements?

Let $F$ denote a function that returns the first $800$ bits of the input. Let $G(N)$ denote a function that returns the last $800$ bits of the binary encoding of the given number $N$. For example, ...
1
vote
0answers
17 views

Can we protect PRESENT from the Statistical Saturation Attack if we change the permutation layer to a random permutation layer?

This is continuation-question based on: If PRESENT had different permutations s would that protect it against Statistical Saturation Attack? Can we protect PRESENT from Statistical Saturation Attacks ...
4
votes
2answers
196 views

Creating single-cycle permutations

There was this one time I came up with a small permutation that had a block size of 16 bits. This was small enough to compute every mapping. I then iterated the mapping starting with zero to see how ...
3
votes
2answers
184 views

(Impossibility of?) Associative Pseudorandom Permutation

I'm not sure whether this had been a long-standing open problem in cryptography. Definition An associative pseudorandom permutation $f(k,m)$ is a permutation such that: $f(k_1, f(k_2, m)) = f(f(...
4
votes
1answer
386 views

How to build disk encryption system using forward permutations like Gimli?

First of all, this is purely a thought experiment. The width of Gimli isn't even a power of two (384 bits), and secondary storage bus speeds aren't even worth using a high performance permutation like ...
0
votes
1answer
135 views

How to pick up random number within range using pseudo-random number sequence

I want to generate PRP using Fisher–Yates shuffle for array [1,2,3,4,5,6,7,8,9,10,11,12]. I implemented NLFSR_25bit with specific seed for PRNG. (for picking up pseudo-random number in every ...
0
votes
1answer
94 views

Arbitrary width pseudorandom permutation

An arbitrary width pseudorandom permutation seems like a very versatile secret-key cryptographic building block. It allows for trivial (nonce-misuse-resistant!) authenticated encryption, among other ...
1
vote
3answers
222 views

Does there exist a deterministic, invertible function $\{0,1\}^n \rightarrow \{0,1\}^n$ that is not a bijection?

One of the requirements for a function to be a PRP is For any $K \in \{0,1\}^s$, $F$ is a bijection from $\{0,1\}^n \rightarrow \{0,1\}^n$. Taken from Wikipedia Does this have to be ...
5
votes
0answers
200 views

A novel encryption method using only a (huge) lookup table. Is this remotely secure? [closed]

So I've come up with an (admittedly impractical) encryption method using a lookup table. The table is a shuffled list of all unsigned 32-bit integers, effectively making it a 32-bit unkeyed PRP. I ...
1
vote
0answers
116 views

Cross, Benes and Butterfly permutation. How make it?

I'm not a math professional and researching an algorithm to provide a good permutation, I found references for Butterfly, Benes and Cross permutations. But all papers I found are in fact discussing ...
1
vote
1answer
323 views

Pseudo-random permutation of a range

I have this set: {0,1,2,3,...,15}. I would like to create a pseudo-random permutation from elements of this set, for example ...
6
votes
2answers
120 views

OWF by encrypting a constant?

This question is a generalization of this old, unanswered question. Suppose we're given a strong PRP $E:\mathcal K\times\mathcal M\to\mathcal C,(K,M)\mapsto C=E(K,M)$. Suppose further we pick a ...
0
votes
2answers
271 views

Pseudorandom Permutation equals to PRF?

I stuck on the same problem in a cryptography, as stated in this question I found following statement in famous textbook by J. Katz (main wiki PRP article refers to this textbook) PROPOSITION 3.27 ...
4
votes
1answer
924 views

Is 3 rounds Feistel enough for making PRP

I know that one round of Feistel is not enough for making a PRP (Pseudo Random Permutation) even I know that two round is not enough how about three round of Feistel ? I read a lot but not usefull. ...
1
vote
1answer
147 views

What is the prp-advantage of a $2^{80}$-time adversary attacking AES-256?

I am somewhat confused with something I read in Dan Boneh's slides discussing the advantage of a $2^{80}$-time adversary attacking AES-256; according to Boneh, the assumption is that this advantage is ...
3
votes
2answers
163 views

How to contruct a pseudorandom with a specific property

How to construct a pseudorandom function $PRF$ with the following property: Probability that $PRF(k_1,i)=PRF(k_2,i)$ is negligible, for all keys $k_1,k_2$ such that $k_1\neq k_2$ Does the PRF with ...
1
vote
1answer
167 views

Probability of collision in PRF

My question is related to this: Collision-resistant Pseudorandom function Assume we have a pseudorandom function as follows: $PRF: \{0,1\}^{l}\times\{0,1\}^{t}\rightarrow\{0,1\}^{m}$, where $l$ is ...
15
votes
3answers
494 views

Expected entropy in $P(x)\oplus x$ for random $x$, where $P$ is a random permutation

Let $P$ be a random permutation of $n>1$ bits. Let $F$ be the function on the same domain $\{0,1\}^n$, defined by $F(x)=P(x)\oplus x$. When $P$ is a block cipher with key a message block, that's ...
4
votes
0answers
99 views

How can we formally define a Pseudo-Random Shuffle function?

My question is related to: When we turn Random shuffle to Pseudorandom Shuffle The idea is to permute the elements in vector $\mathbf{v}$ pseudorandomly, where $|\mathbf{v}|=n$; I am aware that we ...
1
vote
1answer
560 views

Indistinguishable encryptions in the presence of an eavesdropper

I'm trying to understand how the messages $m_0$ and $m_1$ can be distinguished here. I understand the adversary game, so in short: Adv chooses $m_0$ and $m_1$, one them is encrypted and Adv is able to ...
1
vote
2answers
153 views

Can I construct a PRP by sorting results of a PRF?

I am using HMAC-SHA256 as a pseudorandom function family (PRF). I read somewhere that a pseudorandom permutation family (PRP) can be implemented by applying a PRF and sorting the output. For example,...
1
vote
1answer
90 views

Number of possible functions for a PRP

In the Coursera crypto course, Dan Boneh states that if $F: K \times X \to Y$ is a PRF, if the size of the input space $X$ is $2^{128}$, and the size of the output space $Y$ is also $2^{128}$, then ...
5
votes
4answers
258 views

Why are stream ciphers not PRPs?

In a stream cipher like RC4, a message is xored with a random stream of bits, hence a n bits message will result in a n bits random-like ciphertext. So it's a bijection, it's invertible, the output ...
6
votes
1answer
224 views

Computationaly efficient distinguisher for a PRP generator

Let $n$ be an integer (the motivating context had $n\approx2^{27}$). All other lowercase variables are non-negative integers less than $n$ (elements of $\mathbb Z_n$). All uppercase variables are ...