Another Look at Provable Security

Explore a critical examination of provable security in cryptography through this Eurocrypt 2012 conference talk by Alfred Menezes. Delve into the complexities of non-tight reductions, focusing on the classic Bellare-Rogaway proof for RSA-FDH in the random oracle model. Examine identity-based encryption schemes and investigate the importance of tightness in security proofs. Analyze MACs in multi-user settings, comparing single-user and multi-user scenarios. Evaluate Bellare's security theorem for NMAC and interpret its practical implications. Consider the PRF security model and its assumptions. Discuss the significance of non-uniform complexity models in cryptographic proofs. Reflect on the COPS (Cryptanalysis of Provable Security) approach and contemplate a radical proposal for the field. Gain valuable insights into the challenges and future directions of provable security in modern cryptography.

Intro
What this talk is about
Example of a non-tight reduction The classic Bellare-Rogaway proof for RSA-FDH in the random oracle model has a tightness gap of y, where is the number of hash function queries
Identity-based encryption schemes
Does tightness matter?
MACs in the multi-user setting
Security proof for MAC* The proof is a reduction from breaking MAC1 to breaking MAC
Provably secure, but insecure
MAC* in other protocols
Single-user vs. multi-user
Bellare's security theorem for NMAC
PRF security Security assumption: f is (t,c,q)-secure. That is, adversaries
PRF security in the non-uniform model
Interpreting Bellare's proof in practice
Is HMAC-MD5 provably secure?
Non-uniform complexity model
Significance of our work
COPS: Cryptanalysis of Provable Security
A radical proposal
In conclusion....