首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

若通过验证可颠覆美国后量子密码设计,清华陈一镭预印论文破解格密码

量子计算机是否有望能破解 Lattice Problems 以及 LWE?虽然这一问题长期以来受到关注,但鲜有实质性进展。...具体而言,这篇论文展示了一种多项式时间量子算法,用于求解具有特定多项式模数 - 噪声比的有误学习问题(LWE)。...利用这些技术,陈一镭将 LWE 实例转换为具有纯虚高斯振幅的量子态,然后将纯虚高斯态转换为 LWE 秘密和误差项的经典线性方程,最后利用高斯消元法求解线性方程组。...求解 LWE 的量子算法 论文第三章主要专注于定理的证明: 3.1 节展示了具有几个已知秘密坐标的 LWE 和标准 LWE 一样难; 3.2 介绍了将 LWE 转换成具有唯一最短向量的特殊 q-ary...下面三种缩减都是对现有经典多项式时间缩减的微小修改,从标准 LWE 到它们的变体。 1. 有 k 个无误差坐标的 LWE。 2. 有 k 个选择误差项的 LWE。 3.LWE,秘密遵循误差分布。

9810
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    密码体制如何应对“量子霸权”?

    表3:抗量子密码分类 分类 数学困难问题 用途 举例 基于格的密码 基于格上的困难问题,主要有LWE(Learning with Errors)、Ring-LWE、SIS等 加密/签名/密钥交换等 NTRU...格是一种与群、环、域并列的代数结构,LWE(带错误的学习)是格上的困难问题。...2005年,Regev提出LWE问题并通过量子算法将LWE归约到格上的最短向量困难问题(SVP),并给出了基于LWE的公钥密码方案。与之前出现的格上困难问题比较,LWE在构建密码系统时更方便。...Ring-LWE(环上带错误的学习)是LWE的变体。在基于Ring-LWE的密码中,密钥由若干个多项式表示,而不是LWE中的矩阵,因而减小了密钥大小,同时提高了加解密速度。...表4:各类抗量子密码特点 基于格的密码 多变量密码 基于Hash的密码 基于编码的密码 以NTRU为早期代表,已在欧洲成为标准;目前新算法多基于LWE或Ring-LWE 以Rainbow等为代表 以Merkle

    2.5K20

    深度|加密技术如何对付量子计算机

    格的前景自1997年以后变得明朗起来,IBM的研究人员提出第一种较好的加密方案,这种加密方案名为Learning With Errors(LWE),意即伴随误差学习,由于要找到最近的通用格要很长时间,因而可以抵抗来自量子计算机的攻击...什么是LWE方案 在2005年,Oded Regev基于LWE问题提出了一种加密方案,他证实这个方案解决起来很难,因而比较安全。...鱼和熊掌不可兼得,LWE方案虽然更加通用并且安全性更高,但它的效率较低。研究人员在这个方向上,还在不断探索,之后提出了一些其他方案。...除了Soliloquy以外,他们的发现还表明,其他基于理想格的方案,构造单独短向量的方法也可以被攻破,而基于一般格的方案,如Ring-LWE和NTRU则不受影响。

    824100

    【八年苦读】伯克利研究生解决量子计算验证问题

    2017年,Mahadev通过一种名为“Learning With Errors”(LWE)的加密技术,找到了如何在secret-state方法的核心构建trapdoor函数的方法。...Mahadev的验证协议——以及随机数生成器和盲加密方法——取决于量子计算机不能破解LWE的假设。...目前,LWE被广泛认为是后量子密码学的主要候选,可能很快就会被国家标准和技术研究所采用作为其新的加密标准,以取代量子计算机可能破解的标准。...Vidick写道,无论如何,该协议对LWE的依赖使得Mahadev的工作带来了双赢。量子计算机欺骗协议的唯一方法是量子计算世界中有人找到了破解LWE的方法,这本身就是一项了不起的成就。

    60270

    理论计算机顶会FOCS 2021奖项揭晓!姚期智获时间检验奖,MIT毛啸获最佳学生论文奖

    7.Zvika Brakerski, Vinod Vaikuntanathan: 《Efficient Fully Homomorphic Encryption from (Standard) LWE》...FOCS 2011 论文链接:https://eprint.iacr.org/2011/344.pdf 论文介绍: 该论文提出了一个完全同态的加密方案——完全基于(标准)有错误学习(LWE)假设。...在 LWE 上应用已知结果,本论文方案的安全性基于任意格上“短向量问题”的最坏情况硬度。...研究人员的构造在两个方面改进了以前的工作: 1)展示了“近似同态”的加密可以基于 LWE,使用一种新的重新线性化技术。相比之下,之前的所有方案都依赖于与各种环中的理想相关的复杂性假设。...这篇论文的方案具有非常短的密文,因此研究者们使用它来构建渐近高效的基于 LWE 的单服务器私有信息检索 (PIR) 协议。

    90440

    同态加密:实现数据的“可算不可见”

    ② 第二代全同态加密方案——BGV/BFV方案 Gentry方案之后的第二代全同态加密方案通常基于LWE/RLWE假设,其安全性基于代数格上的困难问题,典型方案包括BGV方案和BFV方案等。...BFV(Brakerski/Fan-Vercauteren)方案是与BGV方案类似的另一种第二代全同态加密方案,同样可基于LWE和RLWE构造。...该方案基于LWE并可推广至RLWE,但其的性能不如BGV方案等其他基于RLWE的方案。...2020年5月,IBM在GitHub上开源了基于HElib开发的面向macOS和iOS操作系统的全同态加密工具包,提供了基于Xcode的全同态加密SDK,近期还将发布面向Linux和Android操作系统的工具包...SEAL支持Windows、Linux、macOS、FreeBSD、Android等操作系统平台,同时支持.NET开发。

    2.7K31

    Linux - Linux内存管理

    为了解决内存紧缺的问题,Linux引入了虚拟内存的概念。为了解决快速存取,引入了缓存机制、交换机制等。...要深入了解Linux内存运行机制,需要知道下面提到的几个方面。 首先,Linux系统会不时地进行页面交换操作,以保持尽可能多的空闲物理内存。...其次,Linux进行页面交换是有条件的,不是所有页面在不用时都交换到虚拟内存中,Linux内核根据“最近最经常使用”算法,仅仅将一些不经常使用的页面文件交换到虚拟内存中。...Linux虽然可以在一段时间内自行恢复,但是恢复后的系统已经基本不可用了。...Linux下可以使用文件系统中的一个常规文件或者一个独立分区作为交换空间。同时Linux允许使用多个交换分区或者交换文件。

    52.3K41
    领券