# 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. – poncho Jul 27 '15 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. – user13676 Jul 27 '15 at 18:05
• @poncho My question is: How do we permute a small sized set in practice? – user13676 Jul 27 '15 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 '15 at 18:29

//given an array s with the elements to be permuted

• 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 '15 at 20:55