This question is modified version of this: Can we use merely permutation to hide a message?

I have an English name $m=m_1 || m_2 ||..||m_{30}$.

I pick a random string $d=d_1 ||..||d_{70}$

I mix the values $m_i$ and $d_i$ together and permute them (using pseudorandom permutation) to get a value $v$. So $v$ will be a string of length 100 containing both $m_i$ and $d_i$ values.

We assume that the adversary knows the message's length.

We know that in order for the adversary to find the right name it needs to do $\frac{100!}{30!\cdot 70!}=29372339821610944823963760$ try.

Question: Given the value $v$ can the adversary learn the English name with a non-negligible probability? Is there any way for it to by pass that much try?

  • $\begingroup$ I may gravely err, but I surmise that your question might not be "well-formed". For (in any case) the random string could have a subset of size 30 that forms a valid English name also of size 30. Now, which one is the "right" name to be found? I suggest that you illustrate your idea through highly reducing the sizes, giving a concrete example with a short English name and a corresponding short random string such that your question could be clearly understood. $\endgroup$ Commented Jan 29, 2016 at 14:38
  • $\begingroup$ @Mok-KongShen Thank you for your suggestion. By giving example of English name, I wanted to say the adversary knows the message distribution, however in reality $m$ is not necessarily a name and it could be a set element. But if I talk about the set and elements it would be a bit more difficult to visualize the problem. If I reduce the message length, I think the problem can be solved easily. $\endgroup$
    – user153465
    Commented Jan 29, 2016 at 14:43
  • 1
    $\begingroup$ But you could give a concrete trivial (may be no good for your intended purposes) example such that one clearly knows your underlying thought. Say, the English name is "Eve", the random string is ........(your choice), assuming that case is ignored. $\endgroup$ Commented Jan 29, 2016 at 15:01


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.