I've been studying cryptography for a little while. I understand fairly well the nuts and bolts of security proofs, but I'm having trouble reconciling the formal statements of security in these proofs with their practical "meaning" for a real system. Is there an intuitive way to reason about the "real-world" security of some cryptosystem based only on a formal proof of security against a constructed adversary?

  • $\begingroup$ Can you give some examples? $\endgroup$ – mikeazo Sep 30 '14 at 0:08
  • $\begingroup$ I guess a salient example of this is encryption that preserves some functionality of the plaintext in the ciphertexts. Most good schemes in this area provide a proof of security based on a constructed model of the ideal functionality. How do we reason about the relevance of that model to a real deployed implementation of the scheme? $\endgroup$ – pg1989 Sep 30 '14 at 0:14
  • 1
    $\begingroup$ I think that in its current form, this question might be too broad and subjective. This rabbit hole is deep. The range of possible issues includes appropriateness of the attack model (most models assume no timing side-channels exist), the interpretation of what "secure" means (when is it safe to leak plaintext length? Are even the strongest possible order-preserving encryption security definitions "secure enough"?), the assumptions (AES? Good. LWE? Hmm... ROM? Uh...). To say nothing of concrete vs. asymptotic security, a can of worms on its own! Not to mention implementation issues. $\endgroup$ – Seth Sep 30 '14 at 21:15
  • $\begingroup$ Hmm... you might be right. I wouldn't be offended if people voted to close; this was just on my mind and I wanted to solicit input from the community. $\endgroup$ – pg1989 Sep 30 '14 at 22:09
  • $\begingroup$ If there was an answer to this question, it would probably fill hundreds of journals, I guess. And even then, scientists would not be able to agree on common assumptions, I guess. $\endgroup$ – tylo Oct 1 '14 at 12:58

As suggested in the comments, this question does seem broad and an answer would probably fill hundreds of journals. Nonetheless, the introduction to Katz & Lindell's Introduction to Modern Cryptography provides a nice starting point from a (largely) accepted perspective. Starting from a similar perspective, I'd say a provable security proof of some statement -- e.g., scheme S satisfies property P -- asserts nothing about the real-word beyond what is derivable about the real-world from the statement. This is incredibly limiting when you dig deeper, because many provable security proofs assert nothing about the real-world. That said, at least we can agree that the proven statement holds, rather than nothing at all.


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.