Efficient Online/Offline Signatures with Computational Leakage Resilience in Online Phase

摘要

An online/offline signature scheme allows separation of its signing algorithm into offline phase and online phase. There have been many constructions in the literature, and they are provably secure under chosen-message attacks. However, it has recently been shown that this security notion is insufficient due to side-channel attacks, where an adversary can exploit leakage of information from the implementation of the signing algorithm. Regarding the implementation of online/offline signatures, we found that the online phase is much more critical than the offline phase. In this paper, we propose two efficient online/offline signature schemes. Our online phase is secure with unbounded leakage resilience as long as the assumption that only computation leaks information holds. Our constructions offer a very short signature length and they are efficient in the online phase with modular additions only.