Questions tagged [permutation]

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

Filter by
Sorted by
Tagged with
5
votes
2answers
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 ...
1
vote
3answers
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 ...
0
votes
1answer
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 "...
1
vote
0answers
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 ...
5
votes
1answer
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 ...
1
vote
0answers
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 ...
2
votes
0answers
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 ...
1
vote
3answers
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.
3
votes
1answer
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. ...
4
votes
1answer
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, ...
2
votes
1answer
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 ...
1
vote
1answer
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$ ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
136 views

Problem with a reduction using Hybrid Argument

I have an issue with this proof. We define two games: $$H'(\lambda):$$ 1) Pick $R \in \mathcal{R}(n,l)$ (the space of truly random functions from $\{0,1\}^n$ to $\{0,1\}^l$ 2) we define $\mathit{Enc}...
3
votes
1answer
117 views

Practical OWP of the set of $k$-bit bitstrings for low $k$

Down to what $k$ and how can we devise a practical, public, efficiently computable One Way Permutation $P$ of the set $\{0,1\}^k$ of $k$-bit bitstrings, if possible without involving a trusted party ...
7
votes
1answer
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 ...
1
vote
1answer
218 views

A Construction of a Cipher from a Single Pseudorandom Permutation

A paper from 1997 A construction of a cipher from a single pseudorandom permutation proposes a cipher in which The message block is XORed with K1 before applying F [a single random permutation], and ...
2
votes
1answer
160 views

Method for creating any involutive permutation

The Fisher-Yates shuffle can produce any permutation of a set of $n$ elements. Is there anything that can do the same for creating an involutive permutation of $n$ elements where $n$ is an even number?...
5
votes
2answers
352 views

Creating single-cycle permutations

There was this one time I came up with a small permutation that had a block size of 16 bits. This was small enough to compute every mapping. I then iterated the mapping starting with zero to see how ...
4
votes
1answer
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 ...
2
votes
2answers
249 views

What affect does the permutation layer have on the avalanche effect?

If the permutation is not well thought out, how will this effect the cipher's avalanche effect. For example, if the permutation in PRESENT was in some way different (just made up without any thought) ...
2
votes
1answer
92 views

What does it mean when 1 bit goes into an s-box but two (or more) come out?

I am trying to understand how bits are spread in the PRESENT cipher. The bits that enter the permutation of PRESENT return to their original position after only three rounds. But I am told that in ...
1
vote
1answer
180 views

How does the PRESENT cipher's permutation affect all rounds when it repeats after every three rounds?

I heard that the permutation in PRESENT affects all bits after only a few rounds. However, when I looked at it the bits return to their original position after only three rounds. For example, in round-...
6
votes
1answer
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 ...
1
vote
0answers
118 views

Is there a public key encryption for permutations which is homomorphic under permutation composition?

I'm brainstorming an idea for extending our Latin square autotopism secret sharing scheme (proposed here [open access]) to a repairable scheme. I seek a cryptographic method, which may or may not ...
1
vote
2answers
166 views

Total password count, given length and pool size

First, if my password is exactly 8 characters long, derived from a pool of 95 characters, then is the total amount of passwords I can create simply $95^8$ ...
3
votes
1answer
869 views

Pseudo-random permutation of a range

I have this set: {0,1,2,3,...,15}. I would like to create a pseudo-random permutation from elements of this set, for example ...
0
votes
1answer
122 views

Can a random permutation be restored / decrypted?

Say you have a 1,000,000 random bytes file and you split it into 1000 x (1000 bytes) pieces. You then pick two random pieces and swap them writing down the position of the pieces (eg. swapped piece ...
3
votes
1answer
219 views

How to generate a permutation of n numbers using secret sharing scheme?

Consider $n$ parties having their private inputs $s_1,\cdots,s_n$. How can they compute a public function $f(s_1,\cdots,s_n)= \pi$, where $\pi$ is a permutation of numbers between $1,\cdots,n$, using ...
5
votes
1answer
164 views

Mathematical structure for Sbox

Recently, when I studied the permutation cipher, I saw a matrices structure which is same as permutation cipher. This method was so simple and interesting for me. Let $m$ be $n$-bit plain text and $P=...
2
votes
2answers
1k views

Apply a permutation cipher by hand

I did the following problem from the book "Cryptography Theory and Practice" as I am doing some self-study. Problem: a) Suppose that $\pi$ is the following permutations of the set $\lbrace 1,\dots,8 ...
2
votes
1answer
329 views

What is the importance of $f_k$ in a feistel network being a permutation

I was doing some cryptography exercises, one of which was an example of a feistel network. It said that the function $f_k$ was a permutation for all k but didn't explain why that makes a difference. ...
1
vote
1answer
844 views

substitution-permutation network construction

I want to understand more about substitution-permutation network, if we modify it instead of carrying out the key-mixing, substitution, and permutation steps in alternating order for r rounds, the ...
3
votes
1answer
806 views

Number of combinations required to brute force

I am trying to encrypt a password in a program. Here is the process: Let us assume that I have a string $p$ ($n$ characters long) which contains the password. Now the program reverse the string and ...
5
votes
2answers
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,...
1
vote
1answer
120 views

Permutations coming from RSA

The RSA algorithm can be used to generate a permutation. Given two prime numbers $p$ and $q$, the key length is $n=pq$. If $a$ is the private key, then $b$ is the public key, where $ab \equiv 1 \...
2
votes
1answer
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 ...
6
votes
2answers
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 ...
4
votes
1answer
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 ...
3
votes
1answer
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. ...
2
votes
1answer
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?
13
votes
4answers
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 ...
0
votes
0answers
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$...
3
votes
1answer
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 ...
0
votes
0answers
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 ...
-1
votes
1answer
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 ...
4
votes
1answer
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]$ (...
3
votes
1answer
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....
2
votes
1answer
347 views

Provable security of cryptographic hash functions

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$ , ...