We show polynomial-time quantum algorithms for the following problems: (*) Short integer solution (SIS) problem under the infinity norm, where the public matrix is very wide, the modulus is a polynomially large prime, and the bound of infinity norm is set to be half of the modulus minus a constant. (*) Learning with errors (LWE) problem given LWE-like quantum states with polynomially large moduli and certain error distributions, including bounded uniform distributions and Laplace distributions. (*) Extrapolated dihedral coset problem (EDCP) with certain parameters. The SIS, LWE, and EDCP problems in their standard forms are as hard as solving lattice problems in the worst case. However, the variants that we can solve are not in the parameter regimes known to be as hard as solving worst-case lattice problems. Still, no classical or quantum polynomial-time algorithms were known for the variants of SIS and LWE we consider. For EDCP, our quantum algorithm slightly extends the result of Ivanyos et al. (2018). Our algorithms for variants of SIS and EDCP use the existing quantum reductions from those problems to LWE, or more precisely, to the problem of solving LWE given LWE-like quantum states. Our main contribution is solving LWE given LWE-like quantum states with interesting parameters using a filtering technique.


翻译:我们为下列问题展示了多元时量算法:(*) 在无限规范下,短期整数(SIS)问题(SIS)问题,因为公共矩阵非常广泛,模数是多元型的大质质,而无限规范的界限定在模数减去常数的一半。 (*) 学习有误(LWE)问题,因为LWE类量子国家存在多模式性大和某些差错分布,包括约束性统一分布和拉普尔分布。 (*) 具有某些参数的外推异差异差共合(EDCP)问题。SIS、LWE和EDCP问题的标准形式与解决最坏情况下的拉特类问题一样困难。然而,我们所能解决的变异性在已知的参数体系中并不难于解决最坏情况的问题。然而,我们所考虑的SIS和LWE的变异性(EWE) 和LWE的变异性(LWE) 。

0
下载
关闭预览

相关内容

专知会员服务
84+阅读 · 2020年12月5日
【NeurIPS 2020】通过双向传播的可扩展图神经网络
专知会员服务
27+阅读 · 2020年11月3日
专知会员服务
123+阅读 · 2020年9月8日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
已删除
inpluslab
8+阅读 · 2019年10月29日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Arxiv
0+阅读 · 2021年11月26日
VIP会员
相关资讯
已删除
inpluslab
8+阅读 · 2019年10月29日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Top
微信扫码咨询专知VIP会员