# 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.

165 questions
Filter by
Sorted by
Tagged with
71 views

### Are Block Ciphers Pseudorandom functions? [duplicate]

I am reading this page on wikipedia on Key derivation function here where it states: In cryptography, a key derivation function (KDF) is a cryptographic algorithm that derives one or more secret keys ...
• 444
1 vote
53 views

### An unconditional proof of a PRP by restricting adversary run time

I am a Ph.D. student studying CS theory, I made this account for this question. Recently, I seem to have obtained a proof of existence of a PRP (which is unconditional in the sense that it does not ...
101 views

### Is this pseudo random function any good and/or original? [closed]

I designed this pseudo-random function algorithm that takes a uint64 and returns a uint64. I'd like to know if it is any good ...
1 vote
56 views

### Even-Mansour Cipher: Efficient algorithms for sampling a random permutation

My understanding of the Even-Mansour cipher is the following: We draw a random permutation $P$ from the set of all permutation $P: \{0,1\}^n \rightarrow \{0,1\}^n$. This permutation is public. We ...
1 vote
27 views

### Generalizing randomized permutation functions

The paper on the "SNEIKEN and SNEIKHA" AE and HASH sponge-based algorithms, respectively, presents a 512-bit permutation function "SNEIK512" that, unlike other permutations (ie: ...
• 123
132 views

### Are pseudorandom generators, pseudorandom permutations and hash functions all keyless?

In Katz's Introduction to Modern Cryptography, Chapter 7 Practical Constructions of Symmetric-Key Primitives In previous chapters we have demonstrated how secure encryption schemes and message ...
• 151
56 views

### Pseudorandom permutations

So I am trying to solve some exercises about pseudorandom permutations. Assume that keyed-permuation $E_k(x)$ is a pseudorandom permutation, where $|x|=|k|=n$. Using $E_k(x)$, we construct an ...
76 views

### Any way to find $g,P$ for max cycle size in Blum–Micali with $x_{i+1} = g^{x_i} \mod P$ and $x_0 = g$?

For some $g$ and prime $P$ the sequence $$x_{i+1} = g^{x_i} \mod P$$ $$x_0 = g$$ can contain all numbers from $1$ to $P-1$ and with this it is a pseudo-random permutation of those numbers (EDIT: ...
• 475
169 views

### The different bounds of PRP/PRF switching lemma

The PRP/PRF switching lemma is usually denoted as follows: I understand the proof of this version of the bound $\frac{q(q-1)}{2^{n+1}}$ and the game-playing technique behind it. However, I came ...
• 115
101 views

### Questions regarding the pseudorandom function construction of Banerjee, Peikert, and Rosen

I am trying to understand the following pseudorandom function constructed by Banerjee, Peikert, and Rosen in this paper, assuming the hardness of LWE. Consider the following LWE/LWR based pseudorandom ...
• 285
955 views

### Nexor, an encryption algorithm that promises unlimited key sizes: Is it safe?

My intention is not to make spam here, but I came across this project in Github: https://github.com/andrewhodel/nexor It's an algorithm called Nexor, it promises encryption with unlimited key sizes. ...
• 523
24 views

### Rational secure multiparty computation with permuatation secret sharing scheme?

Taking a look in this economic paper they use cryptographic tools to implement correletaed equilibria in the case of two plaeyrs. They use permutations for the exchange of information between the ...
• 271
121 views

### What is the best way to pseudonymise IP addresses while retaining the ability to identify those that share a subnet?

Background: I'm developing an app that is based around registered users voting on stuff, and I want to create a heuristic that involves IP addresses as one way to flag accounts for further ...
• 161
1 vote
118 views

### Is there any fundamental difference between the block cipher operations encryption and decryption?

Is there any fundamental reason to designate one direction of a block cipher as "encryption" and the other "decryption"? Or are these arbitrary choices? Or perhaps practical ...
• 147
1k views

### Any advantage to a block cipher which is not efficiently invertible?

The classic definition of a PRP includes efficient invertibility. Given that many modern cipher modes (CTR-based e.g. GCM) use only the forward direction of the block cipher, it seems that the ...
• 147
50 views

### Examples of one-way pseudo-random permutation?

One-way functions have many candidates such as integer factorization. I am interested in combinatorial one way permutations. Specifically, I am interested in known one-way pseudo-random permutations (...
1 vote
152 views

### How are the keys used in cryptography generated?

It seems there are keys everywhere in cryptography. From things like HMAC to encryption (both asymmetric and symmetric). The bit I do not totally understand now is how are cryptographic keys generated?...
• 444
105 views

### Why is a two-round Feistel Network not a PRF? [duplicate]

I am a student studying PRP and PRF in school, my prof gave us a thinking question: "Why is a two-round Feistel network not a PRF, even while the component function is a PRF?" I've seen that ...
65 views

47 views

### Generator of one-way functions

Please pardon my question if it seems silly, but I am very keen on knowing: in applied cryptography, there is such a thing as a one-way function, which given an input would generate an output that is ...
• 155
68 views

### Fisher Yates on "faulted" random number generator cryptanalysis

For the sake of curiosity and fun, i have implemented a C# program that operate as deck dealer on 40 cards deck (following the Fisher Yates shuffeling algorithm https://en.wikipedia.org/wiki/Fisher%E2%...
• 351
2k views

### Formally, what is AES?

AES is supposed to be a symmetric key block cipher. The theoretical counterpart to this is a pseudorandom permutation. I'd like to say that AES is a PRP (well, supposedly at least), but that doesn't ...
• 239
2k views

### Why I can't permutate an email and get away with it?

I can understand why a simple substitution cipher can be broken easily using English letter frequencies, and even English digrams like th can be used. Also a ...
• 373
364 views

### What is the difference between a permutation and a shuffle (transposition cipher)

A non-cryptographic definition of a permutation is "2a: the act or process of changing the lineal order of an ordered set of objects. 2b: an ordered arrangement of a set of objects The Wikipedia ...
• 4,989
1 vote
106 views

### Impossibility of recovering the key of a keyed pseudorandom permutation

I'm currently working on some cryptography homework, but I'm stuck on this particular question. Let $F$ be a pseudorandom permutation with identical key length and block length (both equal to the ...
• 111
2k views

### Two Round Feistel network

While reading on block ciphers and DES I read that two-round Feistel network is not a secure PRP? Is there any easy to understand proof to explain the intuition behind this statement. I did search ...
• 321
1 vote
65 views

### Is there a universal construction for Davies-Meyer hash functions?

My understanding is that there exists no strong pseudorandom permutation for which the Davies-Meyer construction is known to yield a provably collision-resistant hash function. Were I mean provably ...
1 vote
155 views

### Security of block cipher PRP(k⊕m)⊕k

Let $\mathcal S=\{0,1\}^n$ be the set of bitstrinsg of $n$ bits (for security parameter $n$). Let $P$ be a public Pseudo-Random Permutation of $\mathcal S$, efficiently computable in both directions. ...
• 124k
89 views

### Is there any block cipher which is also a pseudo-random-permutation over the key

As block ciphers are defined as a pseudo-random-permutation over the data (keyed with the key), I was wondering, if there are also constructions for which key and data can be switched and the cipher ...
69 views

### Shuffling: Purpose and formal definition

To my understanding, shuffling means simply to permute the elements in vector $\mathbf{v}$ pseudorandomly, using a PRP $\pi (\mathrm{seed},\mathbf{v})$. A secure PRP should yield a permutation ...
• 337
1 vote
464 views

### Is there a Pseudo Random Permutation Generator that can output all values of the length of N

Is there a pseudo random permutation generator that produces all permutation of any bit length of the plaintext (this may not be clear, please let me know and I will explain). It must be fast, and ...
354 views

### What makes AES look like an ideal cipher?

There are 2128! permutations on 128-bit inputs. AES supports a maximum key length of 256 bits, therefore offers at most 2256 permutations. The total number of 128-bit permutations is much larger than ...
• 657
71 views

### Is it possible to compute permutations of a sequence of bytes by using exactly one pseudo-random number?

Suppose I have a certain sequence of bytes, for example 0102F4829hex, and I can pick from a pseudo-random number generator exactly one number. Is it possible, by using exactly one pseudo-random number ...
• 67
370 views

### How random are permutations generated from Feistel networks with a small number of rounds?

I wrote a toy pseudo-random permutation out of a Feistel network using blake2b. However, looking at the distribution of permutations for small n = 6, it's clearly not uniform unless many rounds are ...
• 245
94 views

### Provably secure way of expanding permutations

Gimli is a 384-bit permutation that makes use of an internal 96-bit permutation which works on columns. Every 4 rounds starting from the 1st a "small swap" is performed and every 4 rounds ...
• 133
1 vote
76 views

### Implementing MAC with PRF family $f$, why do we need $f_k$ to be invertible?

As per the title, say we have $\text{MAC}(k,m) = (m,f_k(m))$ where $f$ is a PRF family and every function $f_k$ is PRP, where $f_k(m)$ and $f_k^{-1}(m)$ are efficiently computable. I proved that this ...
218 views

### Regarding XEX mode

Wikipedia claims that given an unkeyed permutation $p$ (presumably of the same size as the key) this is safe: $p(m \oplus k) \oplus k$ Why isn't this construction used instead of XEX? Surely unkeyed ...
• 133
223 views

### Why is the internal chacha20 permutation vulnerable to attacks if used in a sponge construction?

The user Forest in here claims that the internal chacha20 permutation is "vulnerable to attacks if it were used in a sponge construction". My question is as follows: What are these attacks? Would ...
• 113
207 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)$ ...
• 475
246 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 ...
• 6,621
### Is there a cyclic RNG without an explicit form for $i$'th element which is guaranteed to have a sum of zero (subset of elements, $\mod P$ possible)
Let $X$ be a sequence element list of (pseudo) random values generated by a RNG and $x_i \in X$ a member of it. The period length is $k = |X|$ and it is a cyclic generator. For $i>k$ the value \$x_i ...