# Permuting Small Sized Set in Practice

Imagine we have a set $S$ of $m$ elements and we wants to permutes the set elements. Thus the original position of each element should be unknown after permuting. If we define a permutation function as $\pi: \{0,1\}^n \rightarrow \{0,1\}^n$, then the set elements are permuted securely if $n\le|S|$ where $n$ is the security parameter. So to permute $S$ we do $\pi (i)=r_i$, where $i$ is the original index of an element in the set, and $r_i$ is its new index.

However, if the set size is small ($|S|< n$) it seems the only way to securely permute it is to pad it first and then permute it, that increases storage cost.

Question: Is there any better and more cost effective way of permuting a set than the above scheme?

• I believe you need to rethink what security means in this context. It doesn't mean that the attacker can't take a guess at the permutation (and have a $1/|S|!$ chance of getting it correct). Instead, it's that the attacker doesn't get any additional information about the permutation. That is, even if $|S|=2$, the attacker knows that either the two elements remain where they are, or that they are swapped; but he doesn't know which it is. Jul 27, 2015 at 17:59
• @poncho Thank you for the answer. If we use a block cipher, as a permutation function, then given an input $i$ it outputs $r_i$ that is in the block ciphers range. Since the range of block cipher is usually large (e.g. 64-bit) $r_i$ can be any element in this range. Please correct me if I'm wrong. Jul 27, 2015 at 18:05
• @poncho My question is: How do we permute a small sized set in practice? Jul 27, 2015 at 18:13
• What's wrong with the Fisher–Yates shuffle, which is the archetypal way to randomly make a permutation of a set small enough that we can store the index of each element? Or/and (especially, for wider sets) enciphering the index using one of the many techniques of Format-Preserving Encryption and a fixed key?
– fgrieu
Jul 27, 2015 at 18:29

If you can generate uniform random numbers, you can use a variant of Fisher-Yates.

//given an array s with the elements to be permuted
for i from n-1 to 1:
t = rand(0, i) # inclusive
swap(s[i], s[t])

• Can I ask you what the "secret key" is in this scheme? Jul 27, 2015 at 18:43
• @user13676 The state of the random number generator. If you need it to be "keyed" so you can reproduce the permutation, then seed the random number generator. Jul 27, 2015 at 18:47
• In this pseudocode, t = rand(0, i) must generate a random integer uniformly distributed among the i+1 integers in range [0,i] inclusive; otherwise the permutation is distinguishable from random, especially for small sets.
– fgrieu
Jul 27, 2015 at 20:55
• @fgrieu What can I use to get such property? Jul 28, 2015 at 12:15
• @user13676 There are a lot of posts on this kind of stuff online. Most programming languages have methods to help with this. Jul 28, 2015 at 12:19