Universal Exponentiation Algorithm A First Step towards Provable SPA-Resistance

Very few countermeasures are known to protect an exponentiation against simple side-channel analyses. Moreover, all of them are heuristic.This paper presents a universal exponentiation algorithm. By tying the exponent to a corresponding addition chain, our algorithm can virtually execute any exponentiation method.Our aim is to transfer the security of the exponentiation method being implemented to the exponent itself. As a result, we hopefully tend to reconcile the provable security notions of modern cryptography with real-world implementations of exponentiation-based cryptosystems.