XiaoMi-AI文件搜索系统
World File Search SystemSIVP
在晶格上，学习错误，随机线性代码和加密图
我们的主要结果是从最坏的晶格问题（例如G AP SVP和SIVP）降低到某个学习问题。这个学习问题是“从奇偶校验和误差问题学习到更高模量的自然扩展。也可以将其视为从随机线性代码解码的问题。这很大程度上表明这些问题很困难。但是，我们的还原是量子。因此，对学习问题的有效解决方案意味着G AP SVP和SIVP的量子算法。一个主要的开放问题是，是否可以使这种减少的经典（即非量化）。我们还提出了一个（经典的）公钥密码系统，其安全性是基于学习问题的硬度。从主要结果来看，其安全性也基于G AP SVP和SIVP的最差量子量子硬度。新的加密系统比以前基于晶格的Cryposystems：公共密钥的大小〜O（n 2）和加密消息的大小增加了〜O（n）的倍数（在先前的密码系统中，这些值分别为〜O（n 4）和〜o（N 2））。实际上，在所有各方共享一个随机长度〜o（n 2）的假设下，公共密钥的大小可以降低到〜o（n）。
格问题的量子算法
我们给出了一个多项式时间量子算法，用于求解具有确定多项式模噪比的带错学习问题 (LWE)。结合 Regev [J.ACM 2009] 所示的从格问题到 LWE 的简化，我们得到了多项式时间量子算法，用于求解所有 n 维格在 ˜ Ω(n4.5) 近似因子内的决策最短向量问题 (GapSVP) 和最短独立向量问题 (SIVP)。此前，还没有多项式甚至亚指数时间量子算法可以求解任何多项式近似因子内所有格的 GapSVP 或 SIVP。为了开发一种求解 LWE 的量子算法，我们主要介绍了两种新技术。首先，我们在量子算法设计中引入具有复方差的高斯函数。特别地，我们利用了复高斯函数离散傅里叶变换中喀斯特波的特征。其次，我们使用带复高斯窗口的窗口量子傅里叶变换，这使我们能够结合时域和频域的信息。使用这些技术，我们首先将 LWE 实例转换为具有纯虚高斯振幅的量子态，然后将纯虚高斯态转换为 LWE 秘密和误差项上的经典线性方程，最后使用高斯消元法求解线性方程组。这给出了用于求解 LWE 的多项式时间量子算法。