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.

Filter by
Sorted by
Tagged with
4 votes
0 answers
53 views

Repeated tweak in tweakable block cipher

I am reading the proof for the Tweakable Authenticated Encryption in the paper Tweakable Block Ciphers. They stated that if the tweak is not repeated, the output of each tweakable random permutation ...
gan's user avatar
  • 41
1 vote
1 answer
59 views

Can the last n bitcoin blocks (including transactions) be reliable enough to be used as a seed for a PRNG or an input to a crypto hash-function?

Suggested by u/HolgerBier on reddit Is it unpredictable enough or too difficult to manipulate (as in more than a few hundred million USD) to have a sequence of blocks?
TheReal_Skywalker's user avatar
1 vote
0 answers
49 views

What are some ways to produce a pre-determined sequence of a large number of dice rolls? [closed]

What are some ways to produce a pre-determined sequence of a large number of dice rolls (on the order of 100-1000 times) using biased dice or a biased human roller given the constraints that multiple ...
TheReal_Skywalker's user avatar
2 votes
1 answer
63 views

Conceal time-based GUIDs with an affine-cipher?

I'd like to create a custom type of sortable GUID by concatenating an 8-byte nanosecond timestamp, 6 random bytes, a 1-byte node number, and a 1-byte counter. But, such a precise timestamp can be used ...
aiootp's user avatar
  • 53
1 vote
0 answers
52 views

Effcient collision attack for the Davies-Meyer compression function [closed]

We have a block cipher $E:\{0,1\}^{128}\times\{0,1\}^{128}\rightarrow\{0,1\}^{128}$. We know that the PRP advantage of E is Adv$_E^{PRP}=t/2^{128}$ where $t$ is the time needed by the algorithm to get ...
RudeusGreyrat's user avatar
3 votes
1 answer
731 views

Is there a 32 bit block cipher that is also a permutation over all 4bn elements?

Purpose: I'd like to shuffle a file system's blocks without loosing space so I thought if I formatted the disk to have exactly 2^32=4bn sectors, then a secure cipher with 32 bit wide data blocks could ...
yacrc's user avatar
  • 33
1 vote
0 answers
51 views

DES next round key

I don't understand which DES key is used in the next round of Feistel construction. As you can see below, we use our original key that has been inserted in permuted choice 1, where we got 56 bits, ...
joxavy's user avatar
  • 11
1 vote
1 answer
105 views

Derive independent values using block cipher

Suppose having an arbitrary $GF(2^n)$ element $x$. Its distribution is unknown. The task is to derive two $GF(2^n)$ elements $y$ and $z$, that have uniform distribution and are independent from each ...
Georgy Firsov's user avatar
0 votes
2 answers
127 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 ...
Finlay Weber's user avatar
1 vote
1 answer
62 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 ...
Eccentric3523's user avatar
0 votes
1 answer
131 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 ...
Andrew Tomazos's user avatar
1 vote
1 answer
96 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 ...
cryptobeginner's user avatar
1 vote
0 answers
48 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: ...
cookiecipher's user avatar
2 votes
2 answers
259 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 ...
Tim's user avatar
  • 151
0 votes
0 answers
75 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 ...
pepsilon's user avatar
2 votes
1 answer
80 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: ...
J. Doe's user avatar
  • 557
4 votes
1 answer
337 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 ...
Max1z's user avatar
  • 125
2 votes
1 answer
123 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 ...
BlackHat18's user avatar
2 votes
1 answer
976 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. ...
phantomcraft's user avatar
5 votes
1 answer
203 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 ...
Inkling's user avatar
  • 161
1 vote
2 answers
133 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 ...
eddydee123's user avatar
9 votes
3 answers
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 ...
eddydee123's user avatar
2 votes
0 answers
70 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 (...
Mohammad Al-Turkistany's user avatar
2 votes
3 answers
484 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?...
Finlay Weber's user avatar
0 votes
0 answers
73 views

Are there any block ciphers (like AES) which are (or can be) commutative under composition for different keys?

Let $BC$ be a block cipher with similar security as AES (in ECB mode). This $BC$ is applied to a message $m$ of same bit size. The result is a cipher $c$. e.g.; $$BC(key_A,m) = c_A$$ $$BC(key_B,m) = ...
J. Doe's user avatar
  • 557
1 vote
1 answer
119 views

How to generate a random string in Python for a mission-critical application

I'm trying to figure something out, but it is difficult for me. I need to generate a fully random string in Python. My current function is attached below. I just want to know whether this is secure ...
LimesBytefend's user avatar
1 vote
0 answers
106 views

Formal security arguments for 3 round feistal network using PRF

There is a proof sketch in Introduction to modern cryptography that a three-round feistel network using pseudorandom round functions is a secure pseudorandom permutation PRP Πk against probabilistic ...
Chulbuli's user avatar
1 vote
0 answers
146 views

Four round Feistel network using pseudo random round function [closed]

I am solving a four-round Feistel network using pseudo-random round function is a strong pseudo-random function for security against adversaries, but I don't understand that how to solve I know 3 ...
Mary's user avatar
  • 11
0 votes
1 answer
177 views

How does this generate a permutation?

In the process of trying to answer this question, I ended up getting stuck. I found a paper which seems to solve their issue: its authors define a process which yields a pseudorandom permutation ...
JamesTheAwesomeDude's user avatar
8 votes
4 answers
225 views

Why are $\lceil 1/\operatorname{entropy-per-bit} \rceil$ number of bits not sufficient to generate an unbiased bit?

Consider a biased RNG badrand() generating 1 with probability $0.9$ and 0 with probability $...
Ritesh Singh's user avatar
1 vote
1 answer
148 views

Test the randomness of a random permutations, that was generated without Fisher-Yates?

Overview of the problem Before this gets immediately flagged as duplicate, I'm not interested in testing the Fisher-Yates shuffle for randomness, since this can simply be done by testing the ...
camel-cdr's user avatar
  • 113
5 votes
3 answers
334 views

How to combine $n$ 'less random' bits to generate one 'more random' bit?

Suppose we have a random number generator badrand() generating 1 with probability $0.9$ and 0...
Ritesh Singh's user avatar
5 votes
1 answer
204 views

Can a block cipher with fixed point permutations be a good PRP?

Let $E:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$ be a good PRP and consider blockcipher $\widetilde{E}$ defined as follows $$\widetilde{E}(K,X) = \begin{cases}K & \text{if } X=K \\ E(K,K ) & \...
Yunus Karakaya's user avatar
0 votes
1 answer
65 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 ...
jimmytann's user avatar
  • 177
2 votes
0 answers
89 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%...
Skary's user avatar
  • 361
13 votes
1 answer
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 ...
extremeaxe5's user avatar
3 votes
2 answers
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 ...
KMG's user avatar
  • 403
3 votes
2 answers
732 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 ...
SAI Peregrinus's user avatar
1 vote
0 answers
110 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 ...
Peiffap's user avatar
  • 111
3 votes
1 answer
3k 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 ...
Alex's user avatar
  • 321
1 vote
0 answers
83 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 ...
Keshav Srinivasan's user avatar
1 vote
1 answer
238 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. ...
fgrieu's user avatar
  • 134k
3 votes
1 answer
108 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 ...
DasArchive's user avatar
0 votes
1 answer
86 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 ...
Daniel B's user avatar
  • 337
1 vote
2 answers
529 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 ...
Jonathan Hutton's user avatar
4 votes
2 answers
456 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 ...
Cyker's user avatar
  • 699
0 votes
0 answers
107 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 ...
Lorenzo's user avatar
  • 139
7 votes
2 answers
508 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 ...
Arthur B's user avatar
  • 245
3 votes
0 answers
104 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 ...
Bob Semple's user avatar
1 vote
0 answers
91 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 ...
user574362's user avatar