Exponential quantum speedup for $\mathbb{F}_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
该论文研究 F_3^n 上的向量子集和问题：给定 m 个取自 F_3^n 的随机向量，要求找出一个非空子集使其向量和为零；m 越小，问题越难。该问题与后量子密码（尤其是基于 LWE 的构造）以及组合优化密切相关，也是量子优势研究中的经典试验
#LWE
共收录 9 条相关情报。
← 返回所有主题Classical Verification of Quantum Computation with Quasilinear Resources, from Compiled Nonlocal Games
该论文研究的是「量子计算的经典验证」这一核心问题：如何让一个只能进行经典计算的验证者，去核实一台不受信任的量子证明者是否正确地执行了量子电路。作者 Holler 与 Natarajan 基于「计算自测试」(computational sel
Verifiable quantum advantage in extremely low depth
该论文提出一个可在极低深度量子电路中求解、但在标准格基假设下对经典多项式时间算法困难、且可由经典计算机高效验证的采样问题。作者给出了两种量子实现：一种使用对数对数深度（log-log-depth）的量子电路（QNC^0[log log]），
A New Algebraic Algorithm for LWE
本文提出一种求解搜索型LWE问题（Search-LWE）的新代数算法。LWE问题由Regev于2005年引入，是现代密码学与后量子安全的核心假设。目前求解Search-LWE的算法大致分为代数类、组合类和格基类。该工作属于代数方法：其高层思
From Perfect to Approximate Hints: Efficient LWE Secret Recovery Leveraging Low Hamming Weight.
本文研究学习带误差问题（LWE）中秘密向量的恢复问题，特别关注秘密具有低汉明重量的情况。LWE是后量子密码学的基础假设，其安全性依赖于给定样本恢复秘密的困难性。传统方法通常假设秘密均匀分布，但在许多实际场景（如FrodoKEM、Kyber等
Portable Acceleration of Learning With Errors KEMs for Post-Quantum Cryptography
本文针对后量子密码（PQC）迁移中基于Learning With Errors（LWE）的密钥封装机制（KEM）计算开销大的问题，提出一种可移植的GPU加速方案。作者利用OpenMP Target offloading技术，在单一源码基础上
A Note on Banaszczyk's Inequality
该论文是对Banaszczyk不等式的进一步改进。Banaszczyk不等式是格密码学中一个经典的概率不等式，用于估计格上离散高斯分布的尾部概率，在格基密码系统的安全性分析中具有重要地位。此前，Tian、Liu和Xu已对该不等式给出了一个改
SalsaPicante: A Machine Learning Attack on LWE with Binary Secrets.
本文提出一种基于机器学习的攻击方法 SalsaPicante，针对带有稀疏二进制秘密的学习与错误（LWE）问题。LWE 是后量子密码（PQC）系统的基础难题，NIST 标准化的密钥交换机制（KEM）基于模 LWE，而现有同态加密（HE）库多
Ringtail: Practical Two-Round Threshold Signatures from Learning with Errors.
本文提出了一种名为Ringtail的基于格的后量子阈值签名方案。阈值签名允许将签名密钥分发给ℓ个参与方，其中任意t个参与方可以联合生成签名。现有方案要么需要三轮签名协议（Eurocrypt'24），要么依赖非标准假设（Crypto'24）。