Leakage-Resilient Lattice-Based Partially Blind Signatures.

Dimitrios Papachristoudis, Dimitrios Hristu‐Varsakelis, Foteini Baldimtsi, George Stephanides

Published Jan 1, 2019• 1 citation

Abstract

Blind signature schemes (BSS) play a pivotal role in privacy-oriented cryptography. However, with BSS, the signed message remains unintelligible to the signer, giving them no guarantee that the blinded message he signed actually contained valid information. Partially BSS (PBSS) were introduced to address precisely this problem. In this study, the authors present the first leakage-resilient, lattice-based PBSS in the literature. The proposed construction is provably secure in the random oracle model and offers quasi-linear complexity w.r.t. key/signature sizes and signing speed. In addition, it offers statistical partial blindness and its unforgeability is based on the computational hardness of worst-case ideal lattice problems for approximation factors in O ~ ( n 4 ) in dimension n. The proposed scheme benefits from the subexponential hardness of ideal lattice problems and remains secure even if a ( 1 − o ( 1 ) ) fraction of the signer's secret key leaks to an adversary via arbitrary side-channels. Several extensions of the security model, such as honest-user unforgeability and selective failure blindness, are also considered and concrete parameters for instantiation are proposed.

Related papers

Leakage‐resilient lattice‐based partially blind signatures

Dimitrios Papachristoudis, Dimitrios Hristu‐Varsakelis, Foteini Baldimtsi +1 more

Blind signature schemes (BSS) play a pivotal role in privacy‐oriented cryptography. However, with BSS, the signed message remains unintelligible to the signer, giving them no guarantee that the blinded message he signed actually contained valid information. Partially BSS (PBSS) were introduced to address precisely this problem. In this study, the authors present the first leakage‐resilient, lattice‐based PBSS in the literature. The proposed construction is provably secure in the random oracle model and offers quasi‐linear complexity w.r.t. key/signature sizes and signing speed. In addition, it offers statistical partial blindness and its unforgeability is based on the computational hardness of worst‐case ideal lattice problems for approximation factors in in dimension n . The proposed scheme benefits from the subexponential hardness of ideal lattice problems and remains secure even if a fraction of the signer's secret key leaks to an adversary via arbitrary side‐channels. Several extensions of the security model, such as honest‐user unforgeability and selective failure blindness, are also considered and concrete parameters for instantiation are proposed.

IET Information SecurityJul 29, 201918 citations

Identity-based blind signature from lattices

Wen Gao, Yupu Hu, Baocang Wang +2 more

Blind signature allows a user to get a signature of a signer on an arbitrary message, and the verifier can convince that the signature is indeed signed by the signer without leaking any information about the message. This property is necessary when the user’s privacy needs protection, such as a bank bill, a trade secret, etc. As an alternative of public key infrastructure, the identity-based system can simplify the key management procedures in certificate-based public key systems. Inspired by the requirement of identity-based blind signature in the post quantum world, we research on identity-based blind signature based on hard lattice problems under the random Oracle model. We propose a construction built upon the blind signature by Rückert, and it is proved to be one-more unforgeable against selective identity and chosen message attacks (sID-CMA) and unconditionally blind. The proposed scheme has 2 moves, and its security can be reduced to the small integer solution (SIS) problem.

Wuhan University Journal of Natural SciencesJul 14, 20177 citations

Lattice-based Blind Signatures

Markus Rückert

Motivated by the need to have secure blind signatures even in the presence of quantum computers, we present two efficient blind signature schemes based on hard worst-case lattice problems. Both schemes are provably secure in the random oracle model and unconditionally blind. The first scheme is based on preimage samplable functions that were introduced at STOC 2008 by Gentry, Peikert, and Vaikuntanathan. The scheme is stateful and runs in 3 moves. The second scheme builds upon the PKC 2008 identification scheme of Lyubashevsky. It is stateless, has 4 moves, and its security is based on the hardness of worst-case problems in ideal lattices.

Dagstuhl Seminar ProceedingsJan 1, 20091 citation

Efficient Identity-Based Proxy Blind Signature Scheme over Lattices

Yi Yan, Mingming Jiang, Yanyan Kong +1 more

In response to the issues of low security and computational efficiency in current lattice-based proxy blind signature systems, a novel identity-based proxy blind signature scheme utilizing lattices is proposed. This scheme integrates the user's identity information through matrix accumulation operations to serve as the verification public key, simplifying the identity validation process and strengthening both security and privacy measures. The user's private key as well as the proxy signing key are produced through the extended algorithm of the left sampling algorithm, while the rejection sampling algorithm is employed to produce the proxy blind signature. These enhance the space utilisation of keys and signatures. Moreover, the scheme's security is reducible to solving the small integer solution problem, thereby attaining resilience against one-more unforgeability under the adaptive chosen-message attacks within the random oracle model. Compared to other schemes, our scheme features smaller key and signature sizes, resulting in greater efficiency.

International Conference on Computer, Vision and Intelligent Technology (ICCVIT)Nov 24, 20241 citation

Lattice-based Blind Signatures | Preliminary Version |

Markus Rückert

Motivated by the need to have secure blind signatures even in the presence of quantum computers, we present two ecient blind signa- ture schemes based on hard worst-case lattice problems. Both schemes are provably secure in the random oracle model and unconditionally blind. The rst scheme is based on preimage samplable functions that were introduced at STOC 2008 by Gentry, Peikert, and Vaikuntanathan. The scheme is stateful and runs in 3 moves. The second scheme builds upon the PKC 2008 identication scheme of Lyubashevsky. It is state- less, has 4 moves, and its security is based on the hardness of worst-case problems in ideal lattices.

Jan 1, 20093 citations

Revisiting Lattice-based Non-interactive Blind Signature

Anindya Ganguly, Angshuman Karmakar, Suparna Kundu +2 more

Blind signatures (BS) allow a signer to produce a valid signature on a message without learning the message itself.They have niche applications in privacy-preserving protocols such as digital cash and electronic voting.Non-interactive blind signatures (NIBS) remove the need for interaction between the signer and the user.In the post-quantum era, lattice-based NIBS schemes are studied as candidates for long-term security.In Asiacrypt 2024, Baldimtsi et al. proposed the first lattice-based NIBS construction, whose security relies on the random one-more inhomogeneous short integer solution (rOM-ISIS) assumption.This rOM-ISIS is considered to be a non-standard assumption.Later, Zhang et al. introduced another lattice-based construction in ProvSec 2024, and proved its security under the standard module short integer solution (MSIS) assumption.We analyse the security of the latter scheme.In the random oracle model, we show that it fails to achieve both nonce blindness and receiver blindness.We present explicit attacks where an adversary breaks both properties with probability 1.Our attack is based on a crucial observation that uncovers a flaw in the design.Specifically, this flaw allows an attacker to link a message-signature pair with its presignature-nonce pair.In addition, we also identify a flaw in the unforgeability proof.Finally, we suggest a modification to address the issue, which is similar to Baldimtsi et al. construction, and its security relies again on the non-standard rOM-ISIS assumption.This work again raises the question of the feasibility of achieving NIBS from standard assumptions.

Oct 8, 20250 citations