格上随机喻示模型下带关键字检索的公钥加密体制

近年来,基于格的密码体制受到越来越多的关注。这类密码具有诸多潜在优势:抗量子攻击、并行性好、概念简单、安全性所基于的困难问题的随机实例难解性等价于格上公认困难问题最坏情况等。带关键字检索的公钥加密(PEKS)体制是一种具有关键字检索功能的加密机制:用PEKS加密的关键字w的密文和加密消息存储在服务器上,用户向服务器发送一个秘密值Tw,服务器可以搜索出所有包含该关键词w的加密消息,但无法知晓w本身的任何内容。提出了一种基于格的带关键字检索的公钥加密体制,并在随机喻示模型下,基于格上带错误的学习(Learning With Errors)问题的困难性假设证明了新体制的安全性。

LWE问题实际安全性分析综述

LWE问题被广泛用于设计安全的格上密码方案。为了评估基于LWE的格密码方案在给定具体参数下的安全强度,我们需要研究目前求解LWE问题算法的复杂度。本文以Albrecht等人^([33])2015年的研究工作为基础,概述了求解LWE问题的主流算法及其复杂度,并给出了针对具体LWE实例的评估结果。

LWE问题的分析策略及格基约减算法综述

格公钥密码因其数学困难问题的平均/最坏复杂度等价性、代数结构的线性性和丰富的密码等功能而被普遍认为是最有发展前途的后量子密码。目前有大量格密码算法的安全性基于格上的错误学习(LWE)问题而设计。因此,研究LWE的求解算法对深刻理解格公钥密码算法的安全性至关重要。文章首先针对不同类型LWE问题的不同求解策略进行梳理和比较;其次,归纳整理了目前已有的格基约减算法的基本思想和技术原理;最后,对基于格归约的方法求解LWE问题的研究重点和趋势作了展望。