# Tagged Questions

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.

29 views

### Proving CCA security for scheme constructed from secure PRP

We have a $PRP : \{0,1\}^{3n} \rightarrow \{0,1\}^{3n}$ and encryption scheme constructed from this $PRP$. $E_k(x\|r\|0^n)$, where $r$ is randomly chosen from $\{0,1\}^n$ and $0^n$ is a block of ...
57 views

117 views

### Example of a PRP that is not a strong PRP

The exact definition of security for a pseudorandom permutation is straightforward - for some encryption scheme $E\,\colon\,\mathcal{K}\times\mathcal{D}\rightarrow\mathcal{D}$, it must be the case ...
61 views

### Is there any more asymetric-time permutation than x^3 (mod p)?

I've been using "asymetric-time bijective functions (or permutations)" for several practical uses. I've applied them to solve problems in software-attestation and proof of unique blockchain storage. ...
63 views

### Unkeyed, fast, one-way PRP

Are there any fast, secure, one-way, unkeyed almost-pseudorandom permutations? I am looking for something that can hide a MAC, without requiring a secret key and while being much faster than public ...
151 views

### help with cryptanalysis of a sponge permutation

I have been studying and researching hash functions. So far my research has led me to the sponge construction. It appears that the permutation used in the sponge to stir the state is more or less ...
53 views

### Generating a 30-32-bit PRP

I want to generate a small 30 or 32 bit PRP. I am going to use that PRP in an open web service and anyone will be able to get any number of plaintext-cyphertext pairs. I've found an algorithm called ...
52 views

### Probability of $D_k(a*k+b) =p$ for a PRP

I'm wondering what the probability of a PRP having numerous keys (say 3 or more) with the same simple idempotent, or near identity, function. For example, does there exist values of $p, a, b, x_1,$ ...
85 views

### Indistinguishability game hop

I am trying to prove that changing an input in a security game from a randomly permuted set to a set that is permuted using a pseudorandom permutation (PRP) results in a negligible distinguishing ...
76 views

### Permuting Small Sized Set in Practice

Imagine we have a set $S$ of $m$ elements and we wants to permutes the set elements. Thus the original position of each element should be unknown after permuting. If we define a permutation function ...
116 views

### CPA-security of a pseudorandom permutation encryption scheme

Let $F$ be a pseudorandom permutation, and define a fixed-length encryption scheme $(Gen, Enc, Dec)$ as follows: on input $m \in$ $\{0,1\}^{n/2}$ and key $k \in \{0,1\}^n$, algorithm Enc chooses a ...
65 views

### Pseudorandom functions: how are functions stored?

I am wondering about the setup for testing if a function family is pseudorandom. We step into a room, and query the black box with $x$, which yields $f(x)$, etc... We don't know if $f$ is a random ...
76 views

### Is algorithm with more than $2^{word size}$ words secure? [closed]

Let's say we have a feistel cipher or feistel pseudo-random permutation with 8-bit function (S-box) similar to Treyfer, but with much bigger block size like 16MB. Here is example of such pseudo-random ...
65 views

### Determine if encryption is safe against CPA

The following encryption scheme encrypts each block of length $n$ of the plaintext separately: $c_i = k_1 \oplus F(k_2 \oplus p_i)$ Where $F$ is a strong pseudo-random permutation (i.e. it is easy ...
103 views

### Are pseudorandom permutation really permutation in mathematical sense?

In security, and specifically Block Cipher (AES, DES, etc), when we talk about pseudo random permutations, is the term "permutation" refer to the same meaning as in discrete mathematics. That is, the ...
152 views

### Permuted vectors

Consider we have two vectors $v_1, v_2$ of size $n$, and each vector contains $n$ elements. We permute the vectors as: $\pi (k_1,v_1), \pi (k_2,v_2)$. Where $\pi (k_i,v)$ denotes a permutation of a ...
122 views

119 views

### Random Permutation polynomial

I need to know, please: (1) Is there anyway to pick uniformly at random permutation polynomial in a field of prime order? (2) Are there many permutation polynomials in a field? (3) In a finite ...
598 views

### What is the most computationally efficient way of generating pseudo-random permutations?

I have an application in which I need to create up to J randomly shuffled-copies of an array of length N. Then I will have millions or even billions of iterations such that, in each iteration, I will ...
146 views

### Is AES's parity key-dependent?

Is the parity of the permutation of the set $\{0,1\}^{128}$, defined by AES encryption for a certain fixed key, dependent on this key? DES, and any pure Feistel cipher, has even parity for any key. ...
70 views

### Forward pseudorandom permutation [closed]

Please consider the following scenario: The user A and B use their keys, K1 and K2 respectively. Each client have a vector of elements. Each client separately permutes his vector using his key and ...
102 views

### How do you create a large PRP from a small one?

How can you efficiently create a pseudorandom permutation with a large domain given a PRP with a small domain? Meaning: given an $n$-bit PRP, how can I create an $n k$-bit PRP? I'm only interested in ...
94 views

### Statistical tests for pseudorandom permutations

I'm implementing a format-preserving encryption scheme similar to those described in the literature. I want to sanity test my PRP using some statistical tests like TestU01. However, I'm not sure how ...
196 views

### CBC-MAC based on PRF

Why is the block cipher in the CBC-MAC taken to be a pseudo random permutation (PRP) and not a pseudo random function (PRF)? We don't need the bijective property of the PRP. So why go with it?
2k views

### Luby-Rackoff theorem confusion

The Luby-Rackoff theorem states that if a round function is a secure pseudorandom function (PRF) then 3 rounds are sufficient to make the block cipher a pseudorandom permutation (PRP). PRPs are ...
118 views

### Turning PRPs in PRGs with a counter

I am following the Coursera Cryptography I course and I have the following question, I am a bit perplexed by the statement, in week 2 lecture "What are block cyphers?" that a counter-mode PRF is a ...
183 views