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$
4
  • 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, 2015 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, 2015 at 18:05
  • $\begingroup$ @poncho My question is: How do we permute a small sized set in practice? $\endgroup$
    – user13676
    Jul 27, 2015 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, 2015 at 18:29

1 Answer 1

Reset to default
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$
6
  • $\begingroup$ Can I ask you what the "secret key" is in this scheme? $\endgroup$
    – user13676
    Jul 27, 2015 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, 2015 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, 2015 at 20:55
  • $\begingroup$ @fgrieu What can I use to get such property? $\endgroup$
    – user13676
    Jul 28, 2015 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, 2015 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.