-2
$\begingroup$

Let $G$ be a pseudorandom generator.

Is the scheme with encryption

$$\text{Enc}_k(m) = s \| \left( m\oplus G(k) \oplus s \right),\quad s\in\{0,1\}^n \text{ uniformly sampled},$$

and decryption

$$\text{Dec}_k(s,c) = c \oplus s \oplus G(k)$$

multi-message indistinguishable?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ @SEJPM no, that would be fine, because the distinguisher for a PRF can generally not use key dependant messages. The bigger problem is that $F(k,r_1)\oplus F(k,r_2) =G(r_1)\oplus G(r_2)$, which is trivial to check. $\endgroup$
    – Maeher
    Commented Sep 21, 2017 at 15:10
  • $\begingroup$ I modified the question @Maeher $\endgroup$
    – CRYPTONEWBIE
    Commented Sep 21, 2017 at 16:43
  • 2
    $\begingroup$ Note that because $G$ and $s$ are public, they don't add anything to the scheme and thus terms like $G(s)$ or $s$ can simply be stripped out of the XOR. $\endgroup$
    – SEJPM
    Commented Sep 21, 2017 at 17:17
  • $\begingroup$ I would assume that the answer would depend on $G$. Have you read through this? $\endgroup$
    – mikeazo
    Commented Sep 21, 2017 at 18:18
  • 2
    $\begingroup$ -1 I am tired of these questions where someone comes up with a design and dumps it here so others can do the analysis work they are too lazy to do themselves. For that matter, voting to close as off-topic under "request to analyse cryptographic design". $\endgroup$
    – fkraiem
    Commented Sep 22, 2017 at 1:04

2 Answers 2

Reset to default
3
$\begingroup$

It is not entirely clear what you mean by "multi-message indistinguishable". I'm going to assume the weakest possible interpretation I can think of.

So consider the scenario where the adversary is trying to distinguish between the encryptions of two random pairs of messages without knowledge of any additional ciphertexts. I.e. your adversary gets as input two pairs of random messages $(m_0^0,m_0^1),(m_1^0,m_1^1)$ as well as $((s_0,c_0) =Enc_k(m_b^0),(s_1,c_1)=Enc_k(m_b^1))$ for a uniformly chosen bit $b$ and is supposed to guess $b$.

As observed by SEJPM, xoring with $s$ in your construction does not serve any purpose because $s$ is public and can therefore simply be removed. And once you've done that, the encryption is deterministic and you can completely cancel out the key and reveal the xor of the two messages.

So what our adversary does is simly check for which $a\in\{0,1\}$ it holds that $$m_a^0\oplus m_a^1 = c_0\oplus s_0 \oplus c_1 \oplus s_1$$ and output $a$.

This will be correct with overwhelming probability, because we have that $$c_0\oplus s_0 \oplus c_1 \oplus s_1\\ =m_b^0\oplus G(k) \oplus s_0 \oplus s_0 \oplus m_b^1 \oplus G(k) \oplus s_1 \oplus s_1\\ =m_b^0\oplus m_b^1.$$

The only ambiguity left would be if it so happens that $m_0^0\oplus m_0^1 = m_1^0\oplus m_1^1$ but that happens only with probability $2^{-n}$. So our adversary is successful with probability at least $1-2^{-n}$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you, that makes sense. Can you suggest another encryption scheme (using $G$) which would be multi-message indistinguishable in your sense? @Maeher $\endgroup$
    – CRYPTONEWBIE
    Commented Sep 21, 2017 at 18:49
  • $\begingroup$ @CRYPTONEWBIE Use the GGM construction to build a PRF $F$ from your PRG and use $Enc_k(m) = (r,m\oplus F_k(r))$. $\endgroup$
    – Maeher
    Commented Sep 21, 2017 at 18:54
  • $\begingroup$ What if we limit the number of pairs of messages that each adversary gets to some fixed number $q$? Is there a simpler encryption scheme then? @Maeher $\endgroup$
    – CRYPTONEWBIE
    Commented Sep 21, 2017 at 19:28
0
$\begingroup$

No. First of all, you can strip out $s$ with regards to security properties. $s$ is part of the output, so the ciphertext $c$ may as well consist of $G(k) \oplus m$.

Now $G$ is only pseudo-random. Which means that it depends fully on the input parameters. And the only parameter given is the key $k$. Multi-message indistinguishable means that $k$ remains the same across multiple messages. This means that the output of $G$, lets call it the key stream value $g$ will have the same value as well.

So this scheme is identical to reusing a one-time pad (OTP), which in turn means that it is certainly not multi-message secure. Actually, it fails spectacularly with only 2 messages required to expose a lot of information on both of the messages.

Improve this answer
$\endgroup$

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