Full Text Views
94
Multisignatures enable multiple users to sign a message interactively. Many instantiations are proposed for multisignatures, however, most of them are quantum-insecure, because these are based on the integer factoring assumption or the discrete logarithm assumption. Although there exist some constructions based on the lattice problems, which are believed to be quantum-secure, their security reductions are loose. In this paper, we aim to improve the security reduction of lattice-based multisignature schemes concerning tightness. Our basic strategy is combining the multisignature scheme proposed by El Bansarkhani and Sturm with the lattice-based signature scheme by Abdalla, Fouque, Lyubashevsky, and Tibouchi which has a tight security reduction from the Ring-LWE (Ring Learning with Errors) assumption. Our result shows that proof techniques for standard signature schemes can be applied to multisignature schemes, then we can improve the polynomial loss factor concerning the Ring-LWE assumption. Our second result is to address the problem of security proofs of existing lattice-based multisignature schemes pointed out by Damgård, Orlandi, Takahashi, and Tibouchi. We employ a new cryptographic assumption called the Rejected-Ring-LWE assumption, to complete the security proof.
Masayuki FUKUMITSU
Hokkaido Information University
Shingo HASEGAWA
Tohoku University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Masayuki FUKUMITSU, Shingo HASEGAWA, "Tighter Reduction for Lattice-Based Multisignature" in IEICE TRANSACTIONS on Fundamentals,
vol. E104-A, no. 12, pp. 1685-1697, December 2021, doi: 10.1587/transfun.2020EAP1131.
Abstract: Multisignatures enable multiple users to sign a message interactively. Many instantiations are proposed for multisignatures, however, most of them are quantum-insecure, because these are based on the integer factoring assumption or the discrete logarithm assumption. Although there exist some constructions based on the lattice problems, which are believed to be quantum-secure, their security reductions are loose. In this paper, we aim to improve the security reduction of lattice-based multisignature schemes concerning tightness. Our basic strategy is combining the multisignature scheme proposed by El Bansarkhani and Sturm with the lattice-based signature scheme by Abdalla, Fouque, Lyubashevsky, and Tibouchi which has a tight security reduction from the Ring-LWE (Ring Learning with Errors) assumption. Our result shows that proof techniques for standard signature schemes can be applied to multisignature schemes, then we can improve the polynomial loss factor concerning the Ring-LWE assumption. Our second result is to address the problem of security proofs of existing lattice-based multisignature schemes pointed out by Damgård, Orlandi, Takahashi, and Tibouchi. We employ a new cryptographic assumption called the Rejected-Ring-LWE assumption, to complete the security proof.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2020EAP1131/_p
Copy
@ARTICLE{e104-a_12_1685,
author={Masayuki FUKUMITSU, Shingo HASEGAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Tighter Reduction for Lattice-Based Multisignature},
year={2021},
volume={E104-A},
number={12},
pages={1685-1697},
abstract={Multisignatures enable multiple users to sign a message interactively. Many instantiations are proposed for multisignatures, however, most of them are quantum-insecure, because these are based on the integer factoring assumption or the discrete logarithm assumption. Although there exist some constructions based on the lattice problems, which are believed to be quantum-secure, their security reductions are loose. In this paper, we aim to improve the security reduction of lattice-based multisignature schemes concerning tightness. Our basic strategy is combining the multisignature scheme proposed by El Bansarkhani and Sturm with the lattice-based signature scheme by Abdalla, Fouque, Lyubashevsky, and Tibouchi which has a tight security reduction from the Ring-LWE (Ring Learning with Errors) assumption. Our result shows that proof techniques for standard signature schemes can be applied to multisignature schemes, then we can improve the polynomial loss factor concerning the Ring-LWE assumption. Our second result is to address the problem of security proofs of existing lattice-based multisignature schemes pointed out by Damgård, Orlandi, Takahashi, and Tibouchi. We employ a new cryptographic assumption called the Rejected-Ring-LWE assumption, to complete the security proof.},
keywords={},
doi={10.1587/transfun.2020EAP1131},
ISSN={1745-1337},
month={December},}
Copy
TY - JOUR
TI - Tighter Reduction for Lattice-Based Multisignature
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1685
EP - 1697
AU - Masayuki FUKUMITSU
AU - Shingo HASEGAWA
PY - 2021
DO - 10.1587/transfun.2020EAP1131
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E104-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2021
AB - Multisignatures enable multiple users to sign a message interactively. Many instantiations are proposed for multisignatures, however, most of them are quantum-insecure, because these are based on the integer factoring assumption or the discrete logarithm assumption. Although there exist some constructions based on the lattice problems, which are believed to be quantum-secure, their security reductions are loose. In this paper, we aim to improve the security reduction of lattice-based multisignature schemes concerning tightness. Our basic strategy is combining the multisignature scheme proposed by El Bansarkhani and Sturm with the lattice-based signature scheme by Abdalla, Fouque, Lyubashevsky, and Tibouchi which has a tight security reduction from the Ring-LWE (Ring Learning with Errors) assumption. Our result shows that proof techniques for standard signature schemes can be applied to multisignature schemes, then we can improve the polynomial loss factor concerning the Ring-LWE assumption. Our second result is to address the problem of security proofs of existing lattice-based multisignature schemes pointed out by Damgård, Orlandi, Takahashi, and Tibouchi. We employ a new cryptographic assumption called the Rejected-Ring-LWE assumption, to complete the security proof.
ER -