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
1
vote
1answer
55 views

Test the randomness of a random permutations, that was generated without Fisher-Yates?

Overview of the problem Before this gets immediately flagged as duplicate, I'm not interested in testing the Fisher-Yates shuffle for randomness, since this can simply be done by testing the ...
1
vote
0answers
86 views

How can I determine the number of times I have to reapply the Scytale until the original plaintext comes back?

Given "①②③④⑤⑥⑦⑧⑨⑩⑪⑫" as plain text and a 4 rows Scytale inscription with 3 as the length of the longest row, the original plaintext is back after 5 runs: ①④⑦⑩②⑤⑧⑪③⑥⑨⑫ ①⑩⑧⑥④②⑪⑨⑦⑤③⑫ ①⑥⑪⑤⑩④⑨③⑧②⑦...
0
votes
0answers
16 views

calculating the branch number/ active bundles of a cipher

I have read the papers Wide Trail Strategy and Wide Trail Design Strategy for Binary MixColumns. These papers describe the need for a good linear transformation in a cipher, a provable mechanism to ...
0
votes
1answer
71 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
74 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
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 ...
4
votes
1answer
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 ...
1
vote
1answer
125 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
46 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
50 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
244 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
61 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
108 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
55 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
72 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
131 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
56 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
56 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
81 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
72 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
164 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
81 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
93 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
192 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
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 ...
0
votes
0answers
76 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
62 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
285 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
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 ...
4
votes
1answer
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 ...
1
vote
2answers
103 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
137 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
446 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
157 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
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 ...
3
votes
0answers
59 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 ...
2
votes
2answers
91 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$.
7
votes
0answers
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 ...
1
vote
1answer
107 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
76 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
2k 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
179 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
42 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
285 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
86 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 ...