On Multi-User Security of Lattice-Based Signature Under Adaptive Corruptions and Key Leakages
摘要
We consider the multi-user security under the adaptive corruptions and key leakages ( \( \textrm{MU}^{\textrm{c} \& \textrm{l}}\) security) for lattice-based signatures. Although there exists an \( \textrm{MU}^{\textrm{c} \& \textrm{l}}\) secure signature based on a number-theoretic assumption, or a leakage-resilient lattice-based signature in the single-user setting, \( \textrm{MU}^{\textrm{c} \& \textrm{l}}\) secure lattice-based signature is not known. We examine the existing lattice-based signature schemes from the viewpoint of \( \textrm{MU}^{\textrm{c} \& \textrm{l}}\) security, and find that the security of the Lyubashevsky’s signature, which is proven to have the ordinary single-user security only, can be extended to the multi-user security even if we take the adaptive corruptions and the key leakages into account. Our security proof in the multi-user setting makes use of the feature of the SIS problem so that a SIS instance is set to the public parameter and a reduction algorithm can set a public key with a secret key in order to answer a corruption query. We also show that the entropy of the secret key is kept under the bounded leakage with a high probability and then the leakage resilience of signature holds.