# 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
17k views

### What are the benefits of the two permutation tables in DES?

Why do we use a permutation table in the first step of DES algorithm and one at the end of the algorithm?
7k views

### Shannon confusion and diffusion concept

I read the document(not the whole document) from Shannon where he speaks about the concepts of confusion and diffusion. I read in many places(not in the document but around the internet) that ...
17k views

### Why is AES not a Feistel cipher?

I am studying for an exam right now. And I wanted to make sure I got this point correct. AES is not a Feistel cipher because the operations in AES are not invertible. Is the above statement correct?...
2k views

### Replacing the Rijndael S-Box?

The Rijndael S-Box design generates a permutation cycle of type $2+27+59+81+87$. What effect would replacing that permutation with a cycle of type $256$ have on the security of AES?
2k views

### How to check whether the permutation is random or not

Imagine that my friend gives me the permutation $\pi$. He pretends that the permutation was generated completely random. I'm suspicious and worried, because the permutation (for instance) looks like: ...
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 ...
2k views

### Is the inverse of a secure PRP, also a secure PRP?

If a block cipher is a secure PRP, is it's inverse a secure PRP as well? My intuition says yes but I'm not exactly sure. On a related note, if a block cipher is a secure sPRP, is it's inverse a ...
1k views

### Block cipher and parity of permutation

Can anyone explain the following text passage to me? Most real-world block ciphers build even permutations, because it's hard to build odd ones using small operations (32 bit) on larger (128 ...
471 views

### Santa Claus' secret permutation

This December, $N$ friends play secret santa: they select a random permutation $\sigma$ of $N$ (without fixed point). For Santa Claus, everyone has to bring a gift to the next person in the ...
1k views

### Shared secret: Generating Random Permutation

-- or: How to Play Poker Without a Dealer I know this question is long but it's a really interesting theoretical problem about shared secrets and multi-party computation. General Problem: "Shared ...
5k views

### What is the difference between a hash and a permutation?

As defined by Wikipedia a hash function is [...] any algorithm or subroutine that maps large data sets of variable length to smaller data sets of a fixed length. For example, a person's name, ...
1k views

### Permutations of pseudorandom data

Assuming a bit string is deemed cryptographically secure, e.g. PRNG using AES in counter mode, can we equally assume any permutation of said bit string is also cryptographically secure? In a more ...
884 views

### Proving RSA is a permutation

I am trying to prove that RSA is a permutation. All I can find is places where it is stated that it is a permutation because the function is bijective. I know that it is, but would like to see a ...
219 views

### Does there exist trapdoor permutation from lattices?

It seems that the lattice functions are either surjective (SIS) or injective (LWE), due to the error that is basically intended to destroy the structure and provide security. I was wondering whether ...
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 ...
165 views

### Are any block ciphers provably free of equivalent keys?

There are $2^n!$ possible permutations of an $n$-bit block cipher $E_k:\{0,1\}^n \rightarrow \{0,1\}^n$, and any given key $k$ selects one of these permutations at random. Define equivalent keys as a ...
432 views

### Relationship between existence of OWFs and OWPs

OWPs are bijective OWFs, so every OWP is a OWF, but not the other way around. However, I'm wondering what the relationship between the existence of both types of functions is. Obviously if one ...
177 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 ...
650 views

17k views

### How to solve Columnar Transposition Cipher without a key

I have been given a 77 character message for decryption, but no matter where I look all the Columnar Transposition scripts out there are all requiring of a key. I believe the number of columns to be 7,...
876 views

### Is it possible to generate a secure permutation F over 32-bit integers even if F(0) … F(n) is public knowledge?

I'm currently interested in the problem of generating random-looking URLs from sequential database IDs, like how they do it in link shorteners. One way to do this is to encrypt the sequential database ...
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 ...
336 views

### Parity attack on block cipher

My misunderstanding is all about the parity attack mentioned in "Cryptography Engineering by Ferguson, Schneier and Kohno". Most modern block ciphers have a 128-bit block size, but they ...
534 views

### How strong is XooDoo vs AES?

What is Gimli, and how does XooDoo compare to symmetric ciphers such as AES or ChaCha? I am looking at this library, called charm. Interesting paper here. I also ...
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]$ (...
103 views

### Does there exist a universal one-way permutation?

Leonid Levin constructed a universal one-way function, i.e. a function which is one-way as long as there exists at least one one-way function. But my question is, does there exist a universal one-way ...
5k views

### DES: How to find the Inverse of the Initial Permutation?

I am doing a DES problem by hand and I want to know how you calculate the inverse of the initial permutation. I know what the permutation is, but how do you find it based off the given initial ...
127 views

### What does it mean that $BW_N$ is a permutation over the squares mod N?

Let $BW_N$ be a function such that $BW_N:\mathbb{QR}_{N} \mapsto \mathbb{QR}_{N}$ and let if be defined as follow: $BW_N(x) = x^2 \pmod N$ where $N=pq$ and p and q are primes and $p=q=3 \pmod 4$. I am ...
876 views

### Is SHA-256 a one way permutation when restricting the domain to {0,1}^256? [duplicate]

Suppose we consider the space of $\lbrace 0,1 \rbrace^{256}$ as the domain and SHA-256 as our hash function. Does SHA-256 become a one way permutation? Has anyone tried to prove this? Or can it be ...
635 views

### How secure is bit level permutation?

Could anyone explain how secure is bit level permutation? What is the most serious threat against the security of this kind of cipher?
336 views

### NP complete problems related to permutations of binary vectors or block ciphers

Recently, T.Gowers wrote a blog entry called "How not to prove that P is not equal to NP" about the Razborov/Rudich Natural Proofs paper. He has a construction where he talks about compositions of 3-...
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, ...
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 ...
441 views

### If PRESENT had different permutations s would that protect it against Statistical Saturation Attack?

The block cipher PRESENT is vulnerable to the Statistical Saturation Attack for up to 15 rounds (PDF) and a simple example is here. So my questions are, if some (or all) of the permutations were ...
331 views

### Is there a theoretical maximum useful keysize given the block-size?

Consider a block-cipher $F$ with a $N$-bit block-size and a $M$-bit key-size. That is, if $k$ is a $M$-bit key, $p$ is a $N$-bit block of plain-text and $c$ is a $N$-bit block of cipher-text, then: ...
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 ...
234 views

### modified substitution permutation networks

I have a model of substitution permutation networks, modified as follows: instead of iterating $n$ times a round(each of which is composed of the key mixing phase, substitution S-BOX) and ...
378 views

### Periodic One Way Function

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....
699 views

### Simple proof that shows AES is not a uniform permutation on any n-bit string?

Is there a simple proof that shows AES is not a uniform permutation on any $n$-bit string? Since I'm just starting with crypto, I'd like to see a simple yet elegant proof for the said property. ...
648 views

### Revealing random bit permutation

I am new in cryptography. I want to determine the complexity of revealing a random bit permutation which is used as block cipher for plaintexts (bitstrings of length n). An adversary catches different ...
473 views

### Construct a random permutation from a random function?

How can we construct a (pseudo) random permutation from a (pseudo) random function ? I've seen a method from Luby-Rackoff which allows to construct a PRP of length $2N$ from a PRF of input/output ...
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. ...