Questions tagged [permutation]
A way, esp. one of several possible variations, in which a set or number of things can be ordered or arranged.
127
questions
2
votes
0answers
39 views
Provably secure way of expanding permutations
Gimli is a 384-bit permutation which makes use of an internal 96-bit permutation which works on columns. Every 4 rounds starting from the 1st a "small swap" is performed and every 4 rounds starting ...
1
vote
4answers
135 views
If you iterate a cryptographic permutation long enough will you map the input to itself?
Given a cryptographic permutation $\{0,1\}^n \rightarrow \{0,1\}^n$ does it follow that after some number of iterations you must eventually map the input to itself?
1
vote
1answer
55 views
Permutation of first $k$ prime powers as a one-way function?
Let $a_1$ through $a_k$ be some permutation of the first $k$ primes. Let $n \in [1,k!]$ be a parameter specifying the exact ordering by taking the $n$th permutation in a sorted list or by some other ...
0
votes
1answer
73 views
Is there an efficient algorithm that allows to obtain a uniform distribution of all possible $4$-bit permutations from a single keyless $4$-bit S-Box?
Let $S$ denote a keyless permutation that operates on $4$-bit inputs and returns $4$-bit outputs (that is, $S$ is a $4$-bit S-Box).
In this question, $x_0$ denotes an arbitrary bitstring that ends ...
1
vote
1answer
63 views
Iterated AES encryption under a fixed key
Is it right that repeated AES encryption under the same key will eventually lead back to the original plaintext?
The reasoning is that AES acts like a reversible permutation of the blocks, the ...
0
votes
1answer
179 views
Is there a method to encrypt relations in between values of a cyclic value set and generate values out of this set with pseudo RNG? (all at user PC)
Is there a pseudo RNG and function $f$ with
1.) The RNG produces a value $v_0$ out of $N$ different values (set $S$).
2.) Independent of the RNG the function $f$ generates $v_{i+1}=f(v_i)$
...
6
votes
1answer
117 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 ...
0
votes
0answers
57 views
memory-hard KDF that's just a giant permutation?
Why aren't there memory-hard KDF functions that simply build a 1GB permutation and permute it? Then hash the 1GB result. For example, use a hash function (unfixed output mode) on the key+salt and use ...
14
votes
2answers
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: ...
0
votes
0answers
25 views
Is there a 'chain-function' which allows computing the value for the index which is next, previous, +/- some constants but has no shortcut for other?
Looking for an algorithm which has a cyclic 'chain'-function which only allows the computation of next, previous element and in addition to that also a shift by a small amount of constants.
Example 1 ...
-1
votes
1answer
56 views
Question about the definition of Associative Pseudorandom Permutation [closed]
In question about associative pseudo-random permutation the definition uses:
$f(k_1, f(k_2, m)) = f(f(k_1, k_2), m)$
What is defined by that? No luck with google so far.
As far as I know a ...
3
votes
0answers
102 views
What is the intuition behind the strength of unstructured symmetric cryptography?
Consider a single round of a cryptographic permutation, what is so special about it that lacking some bits of information that either get mixed into it as a subkey or omitted at the end (sponge ...
2
votes
1answer
164 views
How are the four 8-bit permutation tables of Present cipher calculated?
the fast implementation of present cipher for 8-bit register uses four 8-bit lookups tables for permutation. Table 3 & 2 are :
...
5
votes
1answer
123 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 ...
3
votes
1answer
264 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 ...
1
vote
2answers
99 views
From the product of two permutation matrices raised to the same power, is it easy to find the power?
Let $A$ and $B$ be two public permutation matrices.
If $r$ is a secret power of large number, can we easily find $r$ from $A^rB^r$?
0
votes
1answer
127 views
Is Permutation conjugate problem hard?
Let $x$,$y$,$z$ be permutations. Then public key is $z=xyx^{ā1}$ and $y$. Is permutation conjugate search problem easy? if yes, how to find $x$ from $z$ and $y$?
Let be a is Alice's secret key as ...
0
votes
0answers
43 views
Examples of extended trapdoor permutations
I am interested in Extended Trapdoor Permutations (ETP). An Extended Trapdoor Permutation (ETP) is a collection of permutations $\{f_{\alpha}\}_{\alpha}$ along with four algorithms $I$ (index), $S$ (...
2
votes
4answers
371 views
Randomness Testing
Let say I have three sequences:
S1 = {1,2,3,4,5,6,7,8,9,10}
S2 = {3,7,1,9,4,10,5,8,6,2}
S3 = {8,3,10,2,6,7,1,5,9,4}
i.e. S2 and S3 are just the permutations of S1. Is there any method to check how ...
3
votes
1answer
135 views
What can be said about the self-power map on groups based on DLP?
Introduction
I've been playing with group representation theory some time, concretely representing groups as permutation groups (Cayley's theorem), where the group $G$ has an embedding into the ...
3
votes
2answers
127 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 ...
3
votes
0answers
54 views
AES: Why ShiftRows() before MixColumns()? [duplicate]
In above picture you can see a AES state array over 2 rounds through the S- and P-Boxes of AES. It's taken from here and intends to show how 2 rounds of transformation are necessary to achieve full ...
1
vote
2answers
80 views
Is a random permutation “hiding”?
Let's say I tell you $G: \mathbb{F} \rightarrow \mathbb{F}$ is a random permutation (some finite field). Does that mean:
$G$ is one-way, so that if I give you $G(x)$, it is infeasible to determine ...
1
vote
0answers
44 views
Proving at most one affine permutation mapping $x$ to $u$ and $y$ to $v$ with $x,y \in \mathbb{Z}_n$ and $\gcd(xāy,n) = 1$
Suppose that $x,y \in \mathbb{Z}_n$ with $\gcd(xāy,n) = 1$. Prove that for any $u,v \in \mathbb{Z}_n$ there is at most one affine permutation mapping $x$ to $u$ and $y$ to $v$.
5
votes
0answers
138 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 ...
1
vote
1answer
95 views
Key, plaintext block and ciphertext block permutations question
Question: If a cipherās key size is $k$ bits and its block size is $b$ bits, how many possible keys are there, how many possible plaintext blocks are there, and how many possible ciphertext blocks are ...
1
vote
0answers
69 views
Locally computable random permutation
Let $A$ be a set of size $n$. Given a random seed $s$, I am looking to build a pseudo-random random permutation $\pi_s: A \rightarrow A$ such that $\pi_s(a)$ is fast to compute for every $a \in A$. By ...
0
votes
3answers
938 views
What's the difference between confusion/diffusion and mode of operation?
I understand the concepts of confusion (substitution) and diffusion (permutation).
My understanding of what a mode is that it's an algorithm that lets us encrypt arbitrary message size. i.e. AES is ...
1
vote
1answer
89 views
Permutation and modes of operation
I'm reading the book "Serious Cryptography A Practical Introduction to Modern Encryption" from Jean-Philippe Aumasson, and in the first chapter, it is written this :
We can try to abstract out the ...
3
votes
1answer
39 views
For a hash over a finite space without size reduction, is a public permutation sufficient?
Suppose the application is a Lamport signature scheme.
Is the following a secure hash $\{0,1\}^n \rightarrow \{0,1\}^n$?
$$
H(x) = x \oplus P(x)
$$
where $P$ is a public permutation that permutes an ...
6
votes
3answers
204 views
Mixing x into permutation through XOR vs. modular addition
Block ciphers mix key material into the permutation through XOR. Also do pre and post whitening this way.
Chacha/Salsa finishes by 32-bit modular adding key and iv material (among other bits but ...
1
vote
0answers
75 views
Is this a PRP? How can I create a distinguisher to show it isn't?
Consider the keyed permutation $F_k : \{0,1\}^2 \to \{0,1\}^2$ with two-bit keys defined as $F_k(x) = k\oplus x$.
Is this F a PRP? How can I create a distinguisher D and calculate the difference ...
3
votes
1answer
161 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
413 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
165 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
59 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
205 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
71 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 ...
1
vote
0answers
37 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
141 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
643 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
168 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
107 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
114 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
389 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
672 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
103 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
112 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 ...
4
votes
1answer
555 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
184 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 ...
