0
$\begingroup$

In an one-time pad scheme, $s \oplus m$ is uniformly random for any $m \in \{ 0,1 \}^\ell$ if $s$ is uniform in $\{ 0,1 \}^\ell$. By the security of PRF, it seems to be secure to replace the truly uniform string $s$ with the output $F_k(r)$ of a PRF $F: \{ 0,1 \}^\kappa \times \{ 0,1 \}^\ell \rightarrow \{ 0,1 \}^\ell$. Let us consider a case where $r$ can only be chosen from a small range with limited entropy (e.g., $\{ 0...00,0...01 \}$ with $\ell - 1$ leading zeros). Is it possible for an adversary who has no idea about $k$ to distinguish between the one-time pad $F_k(r) \oplus m$ and a truly random string? If possible, how does the entropy of $r$ influence the advantage of such an adversary?

Many thanks for any help.

Improve this question
$\endgroup$
  • $\begingroup$ Keep in mind that, when you saying it seems to be secure, actually, you are switching from perfect secrecy to computationally bounded adversary model, in which, we want the adversaries gain is negligible. $\endgroup$ – kelalaka Oct 18 '20 at 7:27
  • $\begingroup$ @kelalaka, thanks for your comment. Indeed, in this case, I am interested in the computational indistinguishability between $F_k(r) \oplus m$ and a truly random string. $\endgroup$ – X.G. Oct 18 '20 at 7:42
  • 1
    $\begingroup$ Hint: what happens if $r$ repeats in several experiments using the same $k$? $\endgroup$ – fgrieu♦ Oct 18 '20 at 10:07
  • $\begingroup$ How many samples does the adversary get to see? $\endgroup$ – Maeher Nov 2 '20 at 11:16

Your Answer

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

Browse other questions tagged or ask your own question.