3 ms·

I didn't know the algorithm: https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing

• schoen 6y ago
  A fun fact is that this is one of only two algorithms in https://en.wikipedia.org/wiki/Category:Information-theoretically_secure_algorithms https://en.wikipedia.org/wiki/Category:Information-theoretic... The idea is that there is no amount of computational capacity or mathematical insight that could permit an attacker to break this algorithm, even in principle. That contrasts with other primitives which are often insecure given an efficient P=NP solution (guess the right answer and check that it was correct). With the one-time pad and Shamir's Secret Sharing, the attacker has no meaningful way to check whether the guessed answer was correct or not. (Both algorithms have a requirement for random input, and the information-theoretic security argument assumes that the attacker could never predict any information about your randomness source, which might not always be true if you're running on real hardware. If you're driving the algorithm with the output of a CSPRNG, the information-theoretic security may reduce to the security of your CSPRNG, which is not information-theoretically secure, for example because an attacker who could somehow guess the CSPRNG seed and offset could potentially confirm that this guess was right.) Another way of thinking about this is the a brute force attack on a security system requires a way to detect when your current guess is right. This is why, for example, the RSA encryption challenges would always have a plaintext starting with "The unknown message is:". This assumption isn't necessarily that unrealistic if you know that the plaintext of an encrypted message is a particular file format. Apparently a huge amount of military cryptanalysis, once governments started building special-purpose hardware for brute-force-like attacks, consisted in trying to find and refine ways to usefully detect when the attack had succeeded, given relatively great uncertainty about the nature of the plaintext. It also appears that many of those plaintext-recognition ideas are still classified (!). In an information-theoretically secure algorithm, there is no way to detect a successful break of the algorithm because all plaintexts are equally possible and equally likely given only the evidence of the ciphertext. That means that the ciphertext itself doesn't contribute any new information about the plaintext, so there's in some sense nothing to worry about from sharing the ciphertext with an adversary.
  • deleted 6y ago
    [deleted]
  • peterwwillis 6y ago
    Haha, and I was thinking "Wait, is one-time pad the other one?" before clicking! Too bad, since one-time pad is only theoretically secure. Too many ways to break it in practice.
    • p4bl0 6y ago
      Well, if used correctly, it is practically secure, and otherwise it's not really a one-time pad.