A provably secure ring signature scheme with bounded leakage resilience

Conventionally, the unforgeability of ring signature schemes is defined in an ideal environment where the attackers cannot access any information about the secret keys of the signers. This assumption is too strong to be satisfied in the real world since the cryptographic operations involves the secret key information leakage in various ways due to power/time consumption difference in operations on the 0/1 bits of the secret key. An attacker can obtain this information both passively by collecting power consumption information or actively by injecting faults during the signing operations. Thus, provably secure ring signature in the conventional security definition may be insecure in the real world due to the key information leakage. To address this problem, we formalize the first bounded leakage resilience definition for ring signature. A leakage resilient ring signature scheme remains secure even if arbitrary, but bounded, information about the secret key is leaked to an adversary. A bound on the leaked information is necessary because a ring signature cannot be secure if some signer's secret key is fully leaked. Then we propose the first ring signature scheme with bounded leakage resilience. Following the enhanced security definition with leakage resilience, the proposed scheme is provably secure based on the difficulty of the second l-representation problem in finite field.