3
$\begingroup$

Assuming we are in the information theoretical setting, whereby there is no bound on the computational power of an adversary. Does this mean that the standard definitions for DDH, RSA or QR do no hold in that setting, because the definitions assume some bounds on the computational power of the adversary?

$\endgroup$
  • 1
    $\begingroup$ Well, given that all of these can be reduced to factoring or DLog, which you can trivially brute-force when given unlimited computational power, all the assumption require the computational bound. $\endgroup$ – SEJPM Sep 5 '17 at 14:16
8
$\begingroup$

Does this mean that the standard definitions for DDH, RSA or QR do no hold in that setting, because the definitions assume some bounds on the computational power of the adversary?

That is correct; a computationally unbounded adversary could trivially solve any of these problems. For example, to solve the DDH problem ("given, $g, g^x, g^y, g^z$, does $g^{xy} = g^z$?) a computationally unbounded adversary could go through all possible values $x, y, z$ (between $0$ and $p-1$), and check if they match the $g^x, g^y, g^z$ values they were given, and if so, does $g^{xy} = g^z$. This sort of solution works for all the other problems you mentioned.

Note: there are computationally far easier ways to solve this problem; this is just the generic strategy that works against any computationally bounded problem.

$\endgroup$
  • $\begingroup$ Is that true for any LWE problems and their variations? $\endgroup$ – curious Sep 5 '17 at 14:38
  • $\begingroup$ @curious: it is most certainly true; a computationally unbounded attacker could just try all possible private values, and see which ones worked. As tylo mentioned below, about the only things that are informationally secure are OTP (and authentication equivalents), secret sharing, half of a commitment scheme, and perhaps one or two other things... $\endgroup$ – poncho Sep 5 '17 at 14:41
  • $\begingroup$ so in some sense, Quantum computing brings the Adversary more to the information theoretical setting even LWE is OK in that world. $\endgroup$ – curious Sep 5 '17 at 14:45
  • 5
    $\begingroup$ @curious: I would disagree with that way of putting it. It does allow the attacker to efficiently solve some problems that (as far as we know) can't be solved efficiently without a QC; however there are plenty of problems (e.g. break AES-256) which appear to be intractable with a QC. $\endgroup$ – poncho Sep 5 '17 at 14:54
6
$\begingroup$

Yes, it does.

Any cryptosystem relying on factoring being hard (RSA, Paillier, Rabin, etc.) is immediately broken by an unbounded adversary, because he can just try out all smaller prime factors to factorize a given modulus.

For DDH (or similar methods in finite groups) it's basically the same, he can just try all possible exponents when there are finitely many.

Information theoretic security is not that common. For encryption you have OTP, for secret sharing there are a few (most notably Shamir's), and there are unconditionally hiding or binding commitment schemes (but you can't have both at the same time). On the theoretical level, information theoretic security is closely related to those protocols which would still work even if P = NP.

$\endgroup$

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.