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
2 votes
1 answer
407 views

Why not use a random permutation as a block cipher?

The purpose of a block cipher is to act like a random permutation, and indeed a common security definition is one in which the block cipher is taken to be indistinguishable from a random permutation (...
user avatar
  • 454
0 votes
0 answers
11 views

Example of enhanced trapdoor perrmutation (Enhanced TDP)

I am currently reading about Trapdoor Permutations (TDP). While I can totally understand and think of examples of TDP. I cannot think of any examples of Enhanced TDP. The definition of both TDP and ...
user avatar
  • 282
1 vote
1 answer
51 views

Even-Mansour Cipher: Efficient algorithms for sampling a random permutation

My understanding of the Even-Mansour cipher is the following: We draw a random permutation $P$ from the set of all permutation $P: \{0,1\}^n \rightarrow \{0,1\}^n$. This permutation is public. We ...
user avatar
0 votes
1 answer
50 views

How to know if a power is a permutation of an inverse group

Consider the group $$ℤ^*_{55}$$ Is exponentiating to the 3rd power a permutation of: $$ℤ^*_{55}$$ And exponentiation to the 5th power? I'm trying to solve this problem related to groups, but I don't ...
user avatar
1 vote
0 answers
14 views

Connecting, joining or merging Substitution Permutation layer

I am trying to identify how the SP Network is constructed. I am looking for plausible solutions that help to connect these layers together and what are the ways that exist in literature other than Kam ...
user avatar
2 votes
1 answer
40 views

How difficult is finding $i$ for sequence $s_{i} = g^{s_{i-1}} \mod P$ with $s_0 = g$ for given value $v\in [1,P-1]$

Assuming we found a constant $g$ and a prime $P$ which is able to produce all values from $1$ to $P-1$ with it's sequence $$s_{i} = g^{s_{i-1}} \mod P$$ $$s_0 = g$$ How many steps are needed to ...
user avatar
  • 879
2 votes
1 answer
66 views

How difficult is finding $i$ in tetration $^{i}g = g\uparrow \uparrow i = \underbrace{g^{g^{\cdot\cdot\cdot^{g}}}}_i\equiv v \mod P$ for $v\in[1,P-1]$

EDIT: I messed up something (see comments at answer). This question contains some false statements EditEnd. For tetration modulo prime $P$ $$^{i}g = g\uparrow \uparrow i = \underbrace{g^{g^{\cdot\cdot\...
user avatar
  • 879
0 votes
1 answer
29 views

Could we use permutation polynomials for Shamir's secret sharing scheme?

Could we use permutation polynomials for secret sharing scheme like Shamir's? The say that they induce a bijection over $\mathbb{Z}_p$ what does this mean and how does it helps?
user avatar
0 votes
1 answer
81 views

Substitution-Permutation Network (SPN) Example

I came in contact with an algorithm that deals with SPN in an example, first I'd like to give a definition of what it is: Let $l, m, $ and $N$ be positive integers, let $\pi_s: \{0,1\}^l \to \{0,1\}^...
user avatar
2 votes
1 answer
133 views

Can anybody explain the proof of Rabin and Ben-or of secure multiparty computation?

Can anybody explain the proof of Rabin and Ben-or of secure multiparty computation? The idea is that every player $i$, of $N<+\infty$ players, holds a secret say $s_i$. All of them want to share ...
user avatar
0 votes
0 answers
24 views

Rational secure multiparty computation with permuatation secret sharing scheme?

Taking a look in this economic paper they use cryptographic tools to implement correletaed equilibria in the case of two plaeyrs. They use permutations for the exchange of information between the ...
user avatar
0 votes
1 answer
64 views

Number of Involuntory Keys in Permutation Cipher

I've came with the following problem from the Theory and Practice book by Stinson-Paterson. It states the following: 2.17 (a) Prove that a permutation $\pi$ in the Permutation Cipher is an ...
user avatar
0 votes
1 answer
88 views

What's the difference between permutation and transposition?

I am trying to understand the difference between permutation and transposition. I have seen a similar question in the forum but I would like to ask you for proper definitions and examples of each. I'm ...
user avatar
0 votes
0 answers
23 views

Securely and Deterministically select a combination of objects from hash (cryptographic seed)

I am working on a project that is using a bit-commitment concept to authenticate information. I need to select a combination of objects securely from a secure hash, then distribute that hash later. ...
user avatar
  • 1
0 votes
1 answer
59 views

Structure of composition of permutations

If $P_1, P_2$ are finite permutations, what can we say about $P_3 = P_1 \cdot P_2$? That is, what properties of the composition of permutations can be inferred from the properties of the permutations ...
user avatar
0 votes
0 answers
23 views

How to find k evenly-distributed elements from the set of all n! permutations over n alternatives?

Let $C=\{ c_1, c_2, \cdots,c_n \}$ be a set of $n$ alternatives and $T$ be the set of all strict complete orderings on $C$. For any two $t_1$ and $t2$ in $T$, their (Kendal-tau) distance $d(t_1, t_2)$ ...
user avatar
  • 111
0 votes
1 answer
66 views

Why is a fixed permutation not oneway?

This may not be a good question, but I am just start to learn cryptography. I would like to ask why a fix permutation is not one way. An adversary is given y=f(x) and try to invert y, x and y are n ...
user avatar
  • 99
4 votes
1 answer
198 views

Can modular exponentiation with a public index be considered a secure permutation?

Secure permutation can be used in Sponge and Duplex constructions to build hash functions and encryption. To potentially use them in public-key cryptography, some arithmetic properties is desired. Can ...
user avatar
  • 6,551
0 votes
3 answers
423 views

How to generate keys from a 56 bit using DES

First I just want to apologize for my lack of knowledge in this system. The professor kind of gave us an exercise to solve before even going through the lessons. I tired to look at videos online but ...
user avatar
1 vote
0 answers
60 views

How to cryptanalyze the message using permution cipher

The message is: ACAUI MMGRC AILEE HKREG EAISW OSTHDS With a grid size of 6 x 6. The forbidden cells are in different rows and different columns, so there are no two forbidden cells in the same line.
user avatar
  • 11
1 vote
2 answers
84 views

Permutation polynomial

I want to find a linearized polynomial as my permutation polynomial in GF(2^n). I know that the only root should be 0. So, is there any way to find such polynomial instead of choosing a random one and ...
user avatar
  • 53
0 votes
1 answer
98 views

How does this generate a permutation?

In the process of trying to answer this question, I ended up getting stuck. I found a paper which seems to solve their issue: its authors define a process which yields a pseudorandom permutation ...
user avatar
1 vote
0 answers
20 views

Assistance with Permutation Cipher (Columnar Transposition) [closed]

I was wondering if someone could provide some assistance with understanding a permutation cipher. I have both the cipher text as well as the plaintext but am having some difficulties trying to find ...
user avatar
  • 11
1 vote
1 answer
94 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 ...
user avatar
1 vote
0 answers
101 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: ①④⑦⑩②⑤⑧⑪③⑥⑨⑫ ①⑩⑧⑥④②⑪⑨⑦⑤③⑫ ①⑥⑪⑤⑩④⑨③⑧②⑦...
user avatar
0 votes
1 answer
127 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 ...
user avatar
  • 157
3 votes
2 answers
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 ...
user avatar
  • 373
1 vote
1 answer
100 views

What's a random involution?

What are the properties of random involution? What is the difference between random involution and random permutation?
user avatar
  • 19
5 votes
1 answer
119 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 ...
user avatar
4 votes
1 answer
393 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 ...
user avatar
1 vote
1 answer
275 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 ...
user avatar
0 votes
1 answer
56 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 ...
user avatar
  • 85
2 votes
2 answers
275 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} $$ ...
user avatar
  • 35
3 votes
1 answer
139 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 ...
user avatar
3 votes
3 answers
175 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=...
user avatar
0 votes
1 answer
67 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 ...
user avatar
  • 327
0 votes
1 answer
92 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.
user avatar
1 vote
1 answer
163 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 ...
user avatar
0 votes
0 answers
69 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 ...
user avatar
  • 67
0 votes
0 answers
68 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)
user avatar
-1 votes
1 answer
125 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 ...
user avatar
  • 1
3 votes
0 answers
92 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 ...
user avatar
1 vote
4 answers
188 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?
user avatar
1 vote
1 answer
74 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 ...
user avatar
  • 201
0 votes
1 answer
85 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 ...
user avatar
1 vote
1 answer
143 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 ...
user avatar
  • 675
0 votes
1 answer
203 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)$ ...
user avatar
  • 879
6 votes
1 answer
240 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 ...
user avatar
  • 6,551
0 votes
0 answers
91 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 ...
user avatar
17 votes
2 answers
3k 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: ...
user avatar