# Questions tagged [permutation]

A way, esp. one of several possible variations, in which a set or number of things can be ordered or arranged.

145 questions
Filter by
Sorted by
Tagged with
283 views

### Permutation for which an inverse is a hard problem

Is it possible to construct (even if we don't know how) a permutation for which an inverse must exist but is difficult to find (brute force required)? The one way permutation contains no hidden ...
697 views

### What is the time complexity of the basic components of a symmetric cipher?

I have a very basic knowledge on time complexity and even less on programming, so please bear with me. I am interested to know the time complexity in big-O notation of some of the basic operations in ...
316 views

### Operation Table for Permutation Group

I cannot seem to figure out how the operation table for this permutation is formed. Is it multiplying each index and doing modulus? I can't seem to figure out. This is a Table 4.2 found in "...
62 views

### permutation cipher definition unclear

I have an assignment to decode a permutation cipher based on a key. But on the internet I found only ONE website talking about it. Things are not very clear. I understand that I have to reorder the ...
264 views

### Why do block ciphers use key schedules instead of round constants? (Even-Mansour)

Let's take AES as an example. What would be wrong with just having a 256 bit key that you XOR into your input and then XOR into your output? No key expansion at all. I believe it's even known as the ...
99 views

### Can both substitution and transposition ciphers be thought of as permutations?

I came across this problem to 'explain why both substitution and transposition ciphers can be thought of as permutations' and I cannot come up with an explanation to how substitution ciphers can be ...
46 views

### Can you rely on the permutation of a ciphertext for secrecy?

Say you have a message and you run it through an all-or-nothing transform. A transform that requires every single block in the correct order in order to recover any data. Each block is ...
180 views

### Composition of weak one way function is not a strong one way function

Given $f(x)$, a weak one-way permutation, how to prove that $f^T(x)$ is not a strong one-way function? Here $f^T$ denotes $T$ times self composition of $f$ and $T$ is a polynomial in input length.
802 views

### DES: how does Richard Outerbridge's Initial Permutation operate?

I know how initial permutation works, but I've never heard of this part. People say it's Richard Outerbridge's initial permutation and that it's faster than usual IP (initial permutation) and simple. ...
213 views

### Using multiple permutations to strengthen the security of a cipher

In one book it says a set of permutations with the composition operation is a group. This implies that using two permutations one after another cannot strengthen the security of a cipher, ...
118 views

### Is it possible to permute a binary vector obliviously?

Lets say A has a binary vector of length n, B has a permutation matrix of size n. Is there a way for B to permute A's vector so that A only learns about the result of permutation and B does not learn ...
131 views

### A strange phenomenon of the composition of permutations of order 2

Suppose that $f,g,h:X\rightarrow X$ are permutations such that $f^{2}=g^{2}=\textrm{Id}_{X}$ (i.e. $f,g$ have order 2). Let $F=f\circ g$. Let $D_{f,g}$ be the distribution that takes the value $n$ ...
416 views

### What are the subsequent inputs to the DES key schedule after round 1?

I've just been studying the DES crypto algorithm as presented by Christof Paar in his book entitled, Understanding Cryptography as well as his lecture. There is a diagram on page 68 of the text where ...
871 views

### How does Permutation and Substitution work?

I'm a little confused on how permutation and substitution works, I've been reading about S-DES and how it goes through P-Boxes and S-Boxes but what goes on inside P or S in the algorithm? Are these p ...
136 views

1k views

212 views

### Inverse single element permutations

Let's say we have a set of ordered elements $D=[x_1,x_2,x_3,x_4,x_5]$. We apply a random permutation on them with a $PRP=P_k: P_k(D)=D'=[x_3,x_2,x_5,x_1,x_4]$ My question is: can the owner of the key ...
699 views

### Can we exchange the permutation of a sponge construction?

Part of a sponge construction (like SHA3 uses) is a fixed permutation $p$; which is clearly not one-way. Could we, theoretically, exchange the permutation $p$ with any other permutation? What basic ...
173 views

### Using a round function intended for an SP network in a Feistel network?

If I use the round function from a secure SP network (such as AES) and use it in a Feistel netwok, is this a good starting point for the second cipher? My thought is "yes" because: it already has ...
723 views

### How does Feistel cipher create diffusion between blocks?

From what I've read about Feistel ciphers, I can understand that within each block, there is both confusion and diffusion. But it is unclear to me how a Feistel cipher permutates among blocks of data. ...
762 views

### Differences between OWP and OWF and their IND-CPA security

I am learning about one way permutations and one way functions and am not sure of the differences if there are any. Also in the random oracle model are they both IND-CPA secure?
4k views

### Why is the permutation in AES (and other ciphers) not random or key-dependent?

If the permutation in AES (or other ciphers) were randomly generated or dependent on the key, would it not be stronger against differential attacks? If this is so, then might we need fewer rounds for ...
133 views

### Permuted Hash Table

Suppose we have a hash table, $HT$, consisting of $100$ bins.The hash table uses a hash function $H$ that is public. We all know that given value $a$ we can compute the address in the hash by $H(a)=j$...
863 views

### How do substution-permutation networks work?

I understand what's going on in higher level. But i don't understand what's really going on in page 3 and 4 of this slide. Specifically, How S0 and S1 is used? What goes in what goes out? How ...
56 views

### When we use permutation and random long sting to hide a message

This question is modified version of this: Can we use merely permutation to hide a message? I have an English name $m=m_1 || m_2 ||..||m_{30}$. I pick a random string $d=d_1 ||..||d_{70}$ I mix ...
113 views

### Can we use merely permutation to hide a message?

This question is related to this: When all shares of a secret are given to adversary as a permuted matrix I think the below question is a simplified version of that. Assume we have a 40-bit ...
215 views

### When all shares of a secret are given to adversary as a permuted matrix

Suppose we have a secret $\sigma$. The secret comes from a universe in which the elements are not necessarily distributed uniformly. We split $\sigma$ into $n$ shares $[\sigma_1,...,\sigma_n]$ (...
Is there any notion of a periodic OWF? I.e. an OWF $f$ that on every input $x$ in its domain it holds that $f(f(f\ldots f(x))\ldots )=x$ when $f$ applied many times, each time on the previous output....
I am working on the following exercise question: Consider the following construction of a “keyed” hash function from Katz & Lindell (ex. 7.22 (1st ed.)/ 8.21(2nd ed.)). Gen : On input $1^n$ , ...