Another look at tightness II: Practical issues in cryptography

Sanjit Chatterjee, Neal Koblitz, Alfred Menezes and Palash Sarkar
preprint, 2016.

Abstract: How to deal with large tightness gaps in security proofs is a vexing issue in cryptography. Even when analyzing protocols that are of practical importance, leading researchers often fail to treat this question with the seriousness that it deserves. We discuss nontightness in connection with complexity leveraging, HMAC, lattice-based cryptography, identity-based encryption, and hybrid encryption.

Eprint paper
Supplement: Concrete analysis of Regev's worst-case to average-case reduction