Questions tagged [permutation]
A way, esp. one of several possible variations, in which a set or number of things can be ordered or arranged.
143
questions
-1
votes
0answers
24 views
permutation,how that more than 60% of possible mappings will have at least one fixed point [closed]
Let $\pi(.)$ be a permutation over the integers $\{0,1,2,β¦,(2^π β 1)\}$. Fixing the key, DES is such a permutation for $n=64$. We say $\pi$ has a fixed point if $\pi(π) = π$ for some $m$. As you ...
0
votes
1answer
60 views
What Permutation Entropy really is?
I was wondering about what is permutation entropy(PE). Then, I came to know this paper which describes PE. Now, let's assume that we have a pseudorandom permutation that is generated using an entropy ...
3
votes
2answers
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 ...
1
vote
1answer
63 views
What's a random involution?
What are the properties of random involution? What is the difference between random involution and random permutation?
4
votes
1answer
91 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 ...
4
votes
1answer
295 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 ...
1
vote
1answer
54 views
Double permutation patterns for transposition ciphers, how to crack
I'm reading from Cornell , I know for a single permutation, I can find the ciphertext length (100), divide in some key lengths (10x10, 5x20), then try all permutation (10x9x8... 5x4x3x2x1). then find ...
0
votes
0answers
41 views
RSA trap door permutation does not hold for all text Xs? [duplicate]
The RSA trapdoor permutation as I understand goes like this,
choose $N$ such that $N= p*q$ where $p$ and $q$ are large random primes. Therefore $N$ is NOT prime
choose integers $e, d$ such that $e \...
0
votes
1answer
47 views
collision resistance with added permutation
Suppose we have an $n$ bit ciphertext $c$ protected by a $k$ bit $MAC$, with $k < n$.
Generally, we expect collisions after $O(2^{k/2})$ ciphertext/MAC pairs are seen.
Consider the following ...
2
votes
2answers
226 views
Is this permutation secure?
Let vector ${\bf d} \in \{ \pm 1 \}^n$ be the message we want to send. In my system, ${\bf d}$ is multiplied by an $n \times n$ Fourier matrix ${\bf F}$, as follows
$$ {\bf x} = {\bf F} {\bf d} $$
...
3
votes
1answer
52 views
Proving that RSA encryption function with non-square free modulus is not a permutation
Here is a backgroung for the question on hand. While studying RSA I came up to the question about what happens if $p$ and $q$ involved in modulus computation are not actually primes? There is already ...
2
votes
3answers
82 views
Some questions on building permutations from boolean functions
I've seen multiple examples of boolean functions being used as a permutation.
For example the Keccak Chi : 2.3.1 function:
from https://keccak.team/figures.html
Or as a formula: for $i=\{0..4\}$ $A_i=...
0
votes
1answer
49 views
Shuffling: Purpose and formal definition
To my understanding, shuffling means simply to permute the elements in vector $\mathbf{v}$ pseudorandomly, using a PRP $\pi (\mathrm{seed},\mathbf{v})$. A secure PRP should yield a permutation ...
0
votes
1answer
64 views
One way permutation and its inverse
Is the following statement correct?
Let $F$ be a OWP. Then the inverse $F^{-1}$ of $F$ is also a OWP.
1
vote
1answer
116 views
What is different between a hash function and permutations with repeats
Are secure hash function outputs different from permutation sets of the same length and value? If yes please explain how they appear differently.
For example, MD5 would produce
...
0
votes
0answers
44 views
Is it possible to compute permutations of a sequence of bytes by using exactly one pseudo-random number?
Suppose I have a certain sequence of bytes, for example 0102F4829hex, and I can pick from a pseudo-random number generator exactly one number.
Is it possible, by using exactly one pseudo-random number ...
0
votes
0answers
55 views
An insecure signature with message recovery, Dan Boneh
Someone can help me to resolve this questions from the book of Dan Boneh (University of Standford)
0
votes
1answer
61 views
How should I assign a letter at random to another?
For my first ever project in Python, I wanted to code a cipher to encrypt simple messages ( no spaces or lower case to avoid that extra hassle for now ).
My idea was to either:
Choose a letter of ...
3
votes
0answers
64 views
Provably secure way of expanding permutations
Gimli is a 384-bit permutation that 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 ...
1
vote
4answers
154 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
64 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
78 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
81 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
184 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
151 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
67 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 ...
15
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: ...
-1
votes
1answer
58 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
104 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
225 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 :
...
6
votes
1answer
144 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 ...
4
votes
1answer
384 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
102 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
131 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 ...
2
votes
4answers
406 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
153 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
160 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
57 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
84 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
45 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$.
6
votes
0answers
184 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
102 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
72 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
1k 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
150 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
250 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
82 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 ...
5
votes
2answers
244 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
562 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 ...
