# 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 ...
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: ...
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 ...
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: ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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?...
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 ...
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%...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)$ ...
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 ... ### 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 ...