0
$\begingroup$

Assume all the values and operations defined over $\mathbb{F}_p$. For the sake of simplicity assume all the values are non-zero. Let $(-r)$ denote additive inverse of value $r$.

We have one fixed value $a$. we compute $v_1=a+r_1$ and $v_2=(-r_1)+r_2$, where $r_i$ are picked uniformly at random from the field.

We give $v_1$ and $v_2$ to a semi-honest adversary and ask him to do:

$v_1+v_2=a+r_2$

Question: Given $v_1$ and $v_2$ can the adversary learn anything about $a$ in above scenario (when it performs modular addition operation)?

|improve this question
$\endgroup$
  • $\begingroup$ well, you have three unknowns in two linear equations, chances are an attacker can uniquely identify all three variables' values. $\endgroup$ – SEJPM♦ Aug 12 '16 at 11:06
  • 1
    $\begingroup$ 3 unknown values in two equations can still be information theoretically secure. If you consider the rule of thumb "every equation reduces the degrees of freedome by one" for linear equations, this is similar to two unknowns in one equation, which is the case for OTP. $\endgroup$ – tylo Aug 12 '16 at 14:04
3
$\begingroup$

This is just a blown up version of the OTP.

$v_1$ is basically just the normal OTP: To decrypt, it is enough to know $r_1$

And then you give the adversary just another random value: If $r_2$ is drawn uniformly and $r_1$ is fixed, $v_2$ has the very same distribution as $r_2$ itself. Essentially, you are using another OTP to encrypt the key of the first OTP (the minus sign does not change anything)

So in the end, if you transmit both $v_1$ and $v_2$, you just doubled the size of the message. And you have doubled the key size, and key management is the major drawback of OTP. Decryption is possible with knowledge of either $r_1$ (directly) or $r_2$ (indirectly, getting $r_1$ from $v_2$).

This construction can easily be turned into an attacker on OTP and vice versa, so the security is basically the same. But this is only true if you actually use OTP with true random keys. In a stream cipher construction (which people wrongfully call OTP sometimes), the situation might be entirely different, and from intuition I would say it would weaken the security.

|improve this answer
$\endgroup$
  • $\begingroup$ Thank you for the answer. Thus, it is secure? $\endgroup$ – user153465 Aug 12 '16 at 11:34
  • $\begingroup$ It is as secure and unusable as OTP. But it is larger, and I fail to see a reason why someone would want to double the message and keysize (okay, you actually only need to store / transmit one of the keys) without any security gain. $\endgroup$ – tylo Aug 12 '16 at 11:39
  • $\begingroup$ But why the attack mentioned in the comment does not hold? Why are ignoring $-r_1$. See if the attacker computes $v_1+v_2=a+r_2$, then $r_2$ is used twice, both in the result and in $v_2$. Thank you in advance. $\endgroup$ – user153465 Aug 12 '16 at 11:49
  • $\begingroup$ I don't understand what you mean with "ask the attacker to compute $v_1 + v_2$. The equation follows from the definitions. But it basically has no meaning at all. In the end: If you know either $r_1$ or $r_2$ you can compute $a$. Otherwise, you can't. Another way to look at this: This is exactly the same as doing OTP twice with different keys on the same message. Nothing more. $\endgroup$ – tylo Aug 12 '16 at 13:56

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.