A Leakage-Resilient Pairing-Based Variant of the Schnorr Signature Scheme

Leakage-resilient cryptography aims at capturing side-channel attacks within the provable security framework. Currently there exists a plethora of schemes with provably secure guarantees against a variety of side-channel attacks. However, meeting the strongest security levels (resilience against continual leakage attacks) under the weakest assumptions leads currently to costly schemes. Additionally, recent results show the impossibility to achieve the strongest leakage-resilient security levels for cryptosystems whose secret key is uniquely determined by its public key.

The above justifies the use of stronger assumptions to achieve simpler, more efficient schemes, since most deployed and practical cryptosystems satisfy the above-mentioned uniqueness of the secret key property. In particular, the Schnorr-based leakage-resilient digital signature schemes proposed up to now are built by gluing together ℓ-copies of the basic signature scheme, resulting in a public key that admits exponentially-many secret keys. Furthermore, the space needed to store the secret key material is proportional to the leakage tolerated by these schemes.

We aim at designing a leakage-resilient variant of the Schnorr signature scheme whose secret key’s storage space is constant, independently of the amount of leakage that it can tolerate. We assume that at any given time only the parts of the memory in use leak (split-state/only computation leaks information model); we ease the problem of exhibiting a security reduction by relying on generic groups (generic bilinear group model). We proceed by first proposing a pairing analogue of the Schnorr signature scheme, that we next transform to include split signing key updates. We give a leakage-resilience lower bound in generic bilinear groups against continual leakage attacks for the new scheme.