What is the difference between implausibility vs impossibility in the context of Crypto? I came to know that differing input indistinguishability Obfuscation (diO) implausibile but not impossible. Can I know the difference between the two terminologies?
$\begingroup$
$\endgroup$
6
-
1$\begingroup$ This seems like a question regarding English language, rather than crypto. Nevertheless, an example might suffice to resolve. It is impossible that TRUE AND FALSE. It is implausible that P = NP. $\endgroup$– user2768Commented Apr 19, 2017 at 16:58
-
3$\begingroup$ "Implausible" looks like an informal, not technical term, but there are technical cryptographic concepts that the word may stand for, like negligible probabilities. $\endgroup$– Luis CasillasCommented Apr 19, 2017 at 19:18
-
$\begingroup$ @user2768 does that mean implausibile is same as "impossible based on some unproved assumptions"? $\endgroup$– user38956Commented Apr 20, 2017 at 18:40
-
2$\begingroup$ @DheerajMPai, I would say "unlikely based on what is known." $\endgroup$– user2768Commented Apr 21, 2017 at 11:51
-
1$\begingroup$ X is implausible = "we have strong evidences (reasons) to believe that X is false". (But not that we may be wrong, so X is not impossible). $\endgroup$– Hilder Vitor Lima PereiraCommented Apr 24, 2017 at 10:42
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
3
This is a fairly clear cut mathematical distinction and not really phraseology nor semantics, especially in the sciences.
Implausible ~= Unlikely
Go back 10 years and consider the SHA-1 hash function. Reversing this function is (was) hard and therefore very unlikely. Today this has been kinda achieved in being able to generate collisions, but at great computational expense. This has started us on a path where perhaps tomorrow Google might improve on the technique and allow SHA-1 reversal on mobile phone level computational power. Or to only need the computational power of the iPhone10 when it starts selling. This fate befell MD5.
Similarly, Ivan Verykleverkov might be working in his Moscow University dorm room today at improving Shor's Algorithm. If the Verykleverkov Algorithm allows easy factorisation of primes on non quantum machines, RSA encryption and Blum Blum Shub random number generators become useless cryptographically overnight.
The theme here is something that is unlikely now does not preclude it (on a logical or mathematical basis) from becoming likely tomorrow.
Impossible = Impossible
Decrypting a properly applied One Time Pad (OTP) encryption is impossible. If the pad was generated using true entropy, there is no mathematical solution to reversal. The only solution is brute force attack leading to many possible alternative solutions. Contextual and semiotic analysis may ween some out (as implausible) but you'll still be left with many plain texts each of equal validity. This perfect secrecy is the OTP's draw and reason for all the related questions on this forum.
So in summary, one means the cryptography is currently secure but might be broken with future scientific advances whilst the other is mathematically proven to be secure for all time.
answered Apr 24, 2017 at 12:40
-
2$\begingroup$ On a side note, there was some work done by Peter Shor and another individual that seemed to have broken lattice cryptography. Oded Regev pointed out that the method was entirely classical, and there had been a mistake in one of the mathematical terms. So while I think your use of the name Ivan Verykleverkov is a fictional example, there are real world people working on this exact concept. $\endgroup$ Commented Apr 24, 2017 at 13:18
-
$\begingroup$ @floorcat Ivan attended my wedding. What is your estimate of the rate of progress of Shor development? Is there a tangible threat to prime factorisation cryptography yet? $\endgroup$ Commented Apr 24, 2017 at 13:44
-
1$\begingroup$ My apologies! I didn't find anything on him through google. Progress on their end is hard to gauge. They retracted the paper after Regev pointed out an error, and I haven't heard much since. My own personal estimates though, see a potential break of lattice crypto as likely. That said, if it doesn't happen in the next five years my confidence that it could be broken will drop significantly. Lattice crypto is the prime candidate for PQC, and the NIST reviews will start in about seven months. $\endgroup$ Commented Apr 24, 2017 at 17:44