3
$\begingroup$

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?

|improve this question
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – poncho Jul 27 '15 at 17:59
  • $\begingroup$ @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. $\endgroup$ – user13676 Jul 27 '15 at 18:05
  • $\begingroup$ @poncho My question is: How do we permute a small sized set in practice? $\endgroup$ – user13676 Jul 27 '15 at 18:13
  • 2
    $\begingroup$ 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? $\endgroup$ – fgrieu Jul 27 '15 at 18:29
4
$\begingroup$

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])
|improve this answer
$\endgroup$
  • $\begingroup$ Can I ask you what the "secret key" is in this scheme? $\endgroup$ – user13676 Jul 27 '15 at 18:43
  • 2
    $\begingroup$ @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. $\endgroup$ – mikeazo Jul 27 '15 at 18:47
  • 2
    $\begingroup$ 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. $\endgroup$ – fgrieu Jul 27 '15 at 20:55
  • $\begingroup$ @fgrieu What can I use to get such property? $\endgroup$ – user13676 Jul 28 '15 at 12:15
  • $\begingroup$ @user13676 There are a lot of posts on this kind of stuff online. Most programming languages have methods to help with this. $\endgroup$ – mikeazo Jul 28 '15 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.