Post-quantum signatures from identification schemes

Lukáš Belza

This work addresses the threat that quantum computers pose to conventional digital signatures. It focuses on remote signing scenarios, specifically in the context of national identification systems such as ID Austria. We propose a new blind signature scheme that is secure against quantum attacks, preserves user privacy, and supports remote signing. The construction uses a commitment scheme and a post-quantum digital signature. We formally define the security model and prove that the scheme satisfies the IND-CMA and EUF-CMA properties. We discuss a specific instance using the Dilithium algorithm and other PQ algorithms. The result is a practically deployable scheme suitable for electronic identification and digital services. A novelty is the combination of blind signatures with post-quantum signatures in a remote signing model and the proof of its security.

Kwangjo Kim

Tian‐Yin Wang, Jianfeng Ma, Xiao‐Qiu Cai

André Chailloux

Applying the Fiat-Shamir transform on identification schemes is one of the main ways of constructing signature schemes. While the classical security of this transformation is well understood, it is only very recently that generic results for the quantum case have been proposed [DFMS19,LZ19]. These results are asymptotic and therefore can't be used to derive the concrete security of these signature schemes without a significant loss in parameters. In this paper, we show that if we start from a commit-and-open identification scheme, where the prover first commits to several strings and then as a second message opens a subset of them depending on the verifier's message, then there is a tight quantum reduction for the the Fiat-Shamir transform to special soundness notions. Our work applies to most 3 round schemes of this form and can be used immediately to derive quantum concrete security of signature schemes. We apply our techniques to several identification schemes that lead to signature schemes such as Stern's identification scheme based on coding problems, the [KTX08] identification scheme based on lattice problems, the [SSH11] identification schemes based on multivariate problems, closely related to the NIST candidate MQDSS, and the PICNIC scheme based on multiparty computing problems, which is also a NIST candidate.

Chanyoung Ko, Youngkyung Lee, Kwangsu Lee +1 more

Sedat Akleylek, Meryem Soysaldı

In this paper, we present a new TRSS (threshold ring signature scheme) which depends on the worst-case hardness of a lattice problem. We apply Fiat-Shamir transform to a lattice-based identification scheme to obtain the proposed scheme. The hardness of the identification scheme which is the hybrid combination of two different designs is based on inhomogeneous short integer solution (ISIS) problem. We give security proof for the proposed TRSS. Comparing the proposed TRSS and the others which are quantum secure, the size of key pairs and the length of the signature are nearly same. Therefore, the proposed scheme is an alternative to the threshold ring signature schemes in post-quantum area.