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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 12:58

1 Answer 1


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 and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.