Tighter Reductions of LWE Problems with Semi-uniform Seeds
Author:
Affiliation:

Clc Number:

TP301

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    In certain designs and applications of practical lattice-based cryptography, the use of a specialized variant of LWE problems, where the public matrix is sampled from a non-uniform distribution, is required to establish the securities of corresponding cryptographic schemes. Recently, the formal definition of LWE problems with semi-uniform seeds was introduced in some work, in which the hardness of Euclidean, ideal, and module lattice-based LWE problems with semi-uniform seeds was proved through reduction roadmaps similar to those employed in the hardness proofs of entropic LWE problems. However, known reduction introduces significant losses in the Gaussian parameters of errors and dimensions. Moreover, additional non-standard assumptions are required to demonstrate the hardness of LWE problems with semi-uniform seeds over rings. In this study, a tighter reduction is proposed for LWE problems with semi-uniform seeds by incorporating modified techniques from the hardness proofs of Hint-LWE problems. The proposed reduction is largely unaffected by the algebraic structures of the underlying problems and can be uniformly applied to Euclidean, ideal, and module lattice-based LWE problems with semi-uniform seeds. The hardness of these LWE problems can be established based on standard LWE assumptions without the need for any additional non-standard assumptions. Furthermore, the dimension of the corresponding LWE problems remains unchanged, and the reduction introduces only minimal losses in Gaussian parameters of errors.

    Reference
    Related
    Cited by
Get Citation

王洋,王明强.半均匀LWE问题的紧致归约.软件学报,2025,36(10):4405-4416

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:June 25,2024
  • Revised:September 05,2024
  • Adopted:
  • Online: January 20,2025
  • Published: October 06,2025
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063