Improvement of a Lattice-based Signature Scheme

Yan Xu, Miaomiao Tian, Liusheng Huang, Wei YangJ. Inf. Hiding Multim. Signal Process 2014 · OpenReview

Abstract

Lattice-based cryptography is a leading candidate for post-quantum security due to its resistance against quantum computing attacks. This paper identifies a security flaw in a prominent lattice-based digital signature scheme proposed by Xavier Boyen in 2010. Specifically, the scheme fails to achieve "strong unforgeability" (SUF), allowing an attacker to generate new valid signatures for previously signed messages. We propose an improved scheme that achieves SUF by transitioning from a homogeneous to an inhomogeneous verification equation. Our analysis demonstrates that this fix provides the necessary security guarantees without sacrificing efficiency or quantum resistance.

Introduction

Digital signatures are fundamental to secure online communication, providing authentication and integrity. As quantum computing advances, traditional signature schemes based on integer factorization or discrete logarithms become vulnerable. Lattice-based cryptography, relying on problems like the Small Integer Solution (SIS), offers a robust alternative.

A critical property for advanced cryptographic applications is Strong Unforgeability (SUF). While standard unforgeability prevents an attacker from signing a new message, SUF ensures an attacker cannot even produce a different signature for a message that has already been signed. Boyen’s 2010 scheme fails this requirement; because it utilizes a homogeneous equation ($As = 0 \pmod q$), an adversary can simply negate a valid signature $s$ to $-s$ to create a new valid signature.

Proposed Methodology

To address the linearity trap in Boyen's scheme, we utilize the "GPV" framework (Gentry, Peikert, and Vaikuntanathan) and basis delegation techniques. The core innovation lies in modifying the verification condition.

In the original scheme, a signature $s$ must satisfy: $$As = 0 \pmod q$$ Our improved scheme requires the signature to satisfy an inhomogeneous equation: $$As = y \pmod q$$ where $y$ is a random non-zero vector. By introducing this non-zero target, we break the linear relationship that allowed for simple forgeries like sign-flipping. This change ensures that the scheme is secure in the "Standard Model," avoiding the idealized assumptions of the Random Oracle Model.

Results and Comparative Analysis

The proposed scheme successfully mitigates the identified vulnerability while maintaining competitive performance. We compared our scheme's parameters against Boyen's original work [8] and the scheme by Cash et al. [13].

Comparison of key and signature sizes across different lattice-based schemes.

As shown in the comparison table above, our improved scheme maintains the same signature size ($2m$) and secret key size ($m^2$) as the most efficient prior works. The verification key size increases only by a negligible amount—specifically, the addition of a single vector $n$. This demonstrates that strong unforgeability can be achieved with minimal overhead. Furthermore, we provide a formal reduction proof showing that breaking the SUF of our scheme is as difficult as solving the SIS problem—a task widely considered impossible for modern and quantum computers.

Conclusion and Future Work

We have demonstrated a practical improvement to lattice-based signatures that achieves strong unforgeability with nearly zero efficiency loss. While this work establishes a strong theoretical foundation, future research should focus on selecting specific numerical parameters for standardized security levels (e.g., 128-bit security) and conducting hardware-based implementation benchmarks. Additionally, exploring "ideal lattices" (Ring-SIS) could further reduce the relatively large key sizes characteristic of current lattice-based methods.

Summary updated

BibTeX
@article{xu2014improvement,
  author = {Yan Xu and Miaomiao Tian and Liusheng Huang and Wei Yang},
  title = {{Improvement of a Lattice-based Signature Scheme}},
  journal = {J. Inf. Hiding Multim. Signal Process.},
  year = {2014},
  url = {https://openreview.net/forum?id=8JEqT-Pj9Pa},
}
Figure