One-more reductions
first made 10 July 2025, last modified 26 August 2025
Abstract
"One-more" reductions are a refined form of classical security assumptions, designed to capture situations where an adversary is given multiple challenges and must succeed slightly more times than expected. We will follow their historical development and prove the security of Chaum's blind signature scheme under a variation of OM-RSA.
Notes
The target is an advanced audience with some interest in the foundations of theoretical cryptography.
This presentation was part of the 2025 edition of the self-study PhD course Cryptographic Proof Techniques by Prof. Elena Pagnin (Chalmers University of Technology, Sweden). I thank her for the valuable comments and invaluable patience.
The handout includes theoretical details from cited literature and the formalisation of some personal remarks and doubts. The ones I managed to solve, of course. The current version was updated on 2025-07-11 with the great feedback received during the presentation, which improved it a lot.