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
1 vote
0 answers
68 views

When using AES-NI as a high-speed permutation, does AESDEC offer better diffusion?

If I was to use AES-NI as a high performance 128-bit permutation/PRF would AESDEC offer faster/better diffusion than AESENC? The reason I ask is because both instructions have the same cost, but the ...
Chris_F's user avatar
  • 197
0 votes
1 answer
49 views

Can f(S) also be replaced by PRP(S) in a Sponge consruction?

I have difficulties understanding the PRP in the absorb phase of a sponge construction: a block is XORed to the r part of the state memory,and then the entire state sent through a blockcipher-like ...
Even darker than dark's user avatar
5 votes
1 answer
227 views

Is F(k,k) $\oplus$ F(k,x) a pseudorandom permutation?

Suppose that $F: \{0,1\}^n\times \{0,1\}^n\rightarrow \{0,1\}^n$ is a strongly pseudorandom permutation. Let $\hat{F}(k,x):=F(k,k)\oplus F(k,x)$. I know that $\hat{F}$ can't be a strongly ...
YirongHu's user avatar
1 vote
1 answer
128 views

My new PRNG (PaulssonSponge) with dieharder tests

I run an open source project implementing some RipeMD and SHA hashes, one day I got nerdy and threw together my own Sponge function. I have now tested it with the dieharder 3.31.1 test suite. Is it ...
Kristoffer Paulsson's user avatar
1 vote
2 answers
92 views

How to construct a permutation (shuffle) oblivious pseudorandom function?

We know that OPRF is a two-party protocol, where Alice inputs $X = {x_1, ..., x_n}$, Bob has no input, and after executing the OPRF protocol, Alice gets $F_k(x_i)$, and Bob receives a pseudorandom key ...
song's user avatar
  • 11
3 votes
3 answers
1k views

Why is SHA-2 considered an ARX construction when it also uses non-ARX operations?

SHA-2 makes use of non-ARX non-linear operators such as the Choice and Majority functions: \begin{align} \mathsf{Ch}(E,F,G) &= (E \wedge F) \oplus (\neg E \wedge G)\\ \mathsf{Ma}(A, B, C) &= (...
LightTunnelEnd's user avatar
0 votes
0 answers
79 views

Full-Block Cipher Feedback Mode as a complete AEAD with a free MAC?

Full-State Keyed Sponge (aka Donkey Sponge) appears to cross over into block cipher mode territory such as Full Block Cipher Feedback Mode: Full State Keyed Sponge (FKS) construction: FKS has been ...
LightTunnelEnd's user avatar
1 vote
0 answers
138 views

Can a Full-State Keyed Sponge be used as AEAD by using XEX?

Full-State Keyed Sponge (aka Donkey Sponge) is when a message is absorbed into the full state of the sponge. Such an approach to MAC construction is considered secure. 1 However for an AEAD or a ...
LightTunnelEnd's user avatar
3 votes
2 answers
323 views

Are sponges inherently inefficient when compared to other constructions?

A sponge has by definition 'wasted' operations (the part of the state which always remains private but goes through all the ops of the permutation). In return for that waste you get a MAC at the end - ...
LightTunnelEnd's user avatar
4 votes
1 answer
138 views

How is the Full-State Keyed duplex useful?

In the Full-State Keyed duplex (sponge construction AEAD), plaintext is absorbed into the entire state of the sponge permutation but only a portion of the output can be used else the scheme breaks (...
LightTunnelEnd's user avatar
1 vote
2 answers
83 views

Given $i$ keyed-$PRP$ labels $\ell_{i,x}$ from a $2^{256} \times 2^{256}$ Sudoku (Latin-square), how difficult is it for an adversary to solve?

There's a keyed-permutation I'm playing with, $\ell_{i,x} = \pi_i(x_i)$, which is a bijection $X \leftrightarrow X$, where $|X| = 2^{256}$, and whose evaluations on plaintext inputs $x_i$ perfectly ...
aiootp's user avatar
  • 773
0 votes
1 answer
74 views

Regarding: Pseudorandomness, Pseudorandomgenerators and Padding

Hey there guys and gals, so I am right now studying topics regarding pseudorandomness. I was wondering why, for example with CBC-MAC oder a regular CBC blockcipher, we use padding instead of a PRG. ...
LePetit's user avatar
  • 15
1 vote
0 answers
109 views

Can a one-way permutation be used to stretch a pseudorandom generator?

Consider a secure PRG $G:\{0,1\}^\lambda \to \{0,1\}^n$ and a one-way permutation $f:\{0,1\}^{n-\lambda} \to \{0,1\}^{n-\lambda}$. I'm wondering if the following construction $G': \{0,1\}^\lambda \to \...
Vishnu Iyer's user avatar
1 vote
1 answer
75 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
51 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
71 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
  • 773
1 vote
0 answers
60 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
831 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
64 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
117 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
169 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
75 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
138 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
173 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
57 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
379 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
110 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
86 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
  • 453
4 votes
1 answer
554 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
  • 145
3 votes
1 answer
153 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
978 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
346 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
155 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
77 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
1k 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
1 vote
1 answer
150 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
132 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
160 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
222 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
279 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
2 votes
1 answer
203 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
  • 123
5 votes
3 answers
378 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
220 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
74 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
97 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
  • 371
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
1k 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
124 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