An Improved Lattice-Based Ring Signature With Unclaimable Anonymity in the Standard Model

Mingxing Hu, Weijiong Zhang, Zhen Liu

TL;DR

This paper introduces a new lattice-based ring signature scheme that offers "unclaimable anonymity" while being secure against attackers who can introduce their own keys into the signature ring. Crucially, it achieves this with a signature size that grows linearly with the number of participants, a significant improvement over previous quadratic-sized signatures.

What Problem Does This Paper Address?

Ring signatures are a cryptographic tool that allows a user to sign a message on behalf of a group (a "ring") of potential signers, without revealing which specific member actually generated the signature. This "signer anonymity" is highly desirable for privacy. However, existing schemes often fall short in two key areas:

  1. Security against "adversarially-chosen-key attacks": Some schemes are vulnerable if an attacker can inject their own public keys into the ring. An honest user might then unknowingly use these malicious keys, compromising the signature's integrity.
  2. Efficiency (Signature Size): Previous lattice-based ring signatures with strong anonymity guarantees often produced signatures whose size grew quadratically with the size of the ring and the message. This is impractical for large rings, such as those found in cryptocurrencies.

The paper builds upon prior work (Park and Sealfon, CRYPTO'19) that introduced "signer-unclaimability" (a stronger form of anonymity) and a lattice-based scheme. However, that scheme still suffered from the aforementioned security and efficiency issues.

Methods

The authors propose a novel lattice-based ring signature scheme that addresses the limitations of prior work. Their approach leverages several advanced cryptographic techniques:

  • Lattice-based Cryptography: The scheme is built upon the hardness of problems in mathematical lattices, which are believed to be resistant to quantum computers. Specifically, they rely on the Small Integer Solution (SIS) and Learning With Errors (LWE) assumptions.
  • Key-Homomorphic Evaluation: They adapt an algorithm for evaluating pseudorandom functions (PRFs) in a "key-homomorphic" way. This allows them to construct a signature that is "unforgeable" even when the ring contains keys chosen by an adversary. The core idea is to use a PRF to generate a secret component of the signature that is unpredictable to an attacker.
  • Standard Model Proofs: Unlike many cryptographic schemes that rely on the "random oracle model" (a theoretical idealization), this work provides proofs of security in the "standard model," meaning they rely only on the assumed hardness of the underlying lattice problems.

The key innovation lies in how they use the PRF evaluation to construct a signature component that is tied to the signer's secret key and the message, but is difficult for an adversary to forge even if they control some public keys in the ring. This also allows them to decouple the signature size from the message length, leading to a linear growth in signature size with respect to the ring size.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unforgeability against Adversarial Keys is Crucial: The paper highlights that for practical applications like cryptocurrencies, security against attackers injecting keys into rings is not just a theoretical concern but a practical necessity.
  • Linear Signature Size is Achievable: The work demonstrates that achieving strong anonymity (signer-unclaimability) and security against adversarial keys doesn't have to come with a quadratic signature size penalty. This is a significant efficiency breakthrough.
  • PRFs as Building Blocks for Anonymity: The clever use of pseudorandom functions, evaluated in a key-homomorphic manner, is central to achieving both unforgeability and unclaimable anonymity simultaneously.

Key Results

  • New Lattice-Based Ring Signature Scheme: The paper presents a novel scheme with unclaimable anonymity.
  • Unforgeable w.r.t. Adversarially-Chosen-Key Attack: The proposed scheme is proven secure against attackers who can introduce their own keys into the ring.
  • Linear Signature Size: The signature size grows linearly with the size of the ring, a significant improvement over previous quadratic-sized schemes.
  • Standard Model Security: The security proofs are conducted in the standard model, relying on standard lattice assumptions.

Limitations and Future Work

The authors acknowledge that while their signature size is linear, further improvements to logarithmic size would be ideal for extremely large rings. They suggest that future work could focus on achieving this logarithmic size while still relying on standard lattice assumptions and operating in the standard model.

Summary updated

Abstract

Abstract Ring signatures enable a user to sign messages on behalf of an arbitrary set of users, called the ring, without revealing exactly which member of that ring actually generated the signature. The signer-anonymity property makes ring signatures have been an active research topic. Recently, Park and Sealfon (PS; CRYPTO’19) presented an important anonymity notion named signer-unclaimability and constructed a lattice-based ring signature scheme with unclaimable anonymity in the standard model; however, it did not consider the unforgeable w.r.t. adversarially chosen-key attack (the public key ring of a signature may contain keys created by an adversary) and the signature size grows quadratically in the size of ring and message. In this work, we propose a new lattice-based ring signature scheme with unclaimable anonymity in the standard model. In particular, our work improves the security and efficiency of PS work, which is unforgeable w.r.t. adversarially chosen-key attack, and the ring signature size grows linearly in the ring size.
BibTeX
@article{hu2022improved,
  author = {Mingxing Hu and Weijiong Zhang and Zhen Liu},
  title = {{An Improved Lattice-Based Ring Signature With Unclaimable Anonymity in the Standard Model}},
  journal = {The Computer Journal},
  year = {2022},
  doi = {10.1093/comjnl/bxac104},
}
Figure