基于格的抗量子密码.pdf

《基于格的抗量子密码.pdf》由会员分享，可在线阅读，更多相关《基于格的抗量子密码.pdf（6页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1基于格的抗量子密码1张 江（ 密 码 科 学 技 术 国 家 重 点 实 验 室 ， 北 京 5159 信 箱 100878）摘要：近 年 来 ， 量 子 计 算 的 快 速 发 展 给 现 代 密 码 技 术 带 来 了 前 所 未 有 的 挑 战 和 威 胁 ， 量 子 时 代 也 常 被误 认 为 是 现 代 密 码 技 术 的 “终 结 者 ”。 首 先 ， 本 文 从 密 码 技 术 的 发 展 历 史 出 发 ， 介 绍 了 量 子 计 算 对 现 代密 码 技 术 的 影 响 和 抗 量 子 密 码 研 究 的 必 要 性 ； 其 次 ， 本 文 回 顾 了 格 上 抗 量 子

2、 密 码 的 研 究 现 状 ， 并 简 短介 绍 了 我 们 在 格 上 密 码 研 究 的 部 分 工 作 ； 最 后 ， 本 文 给 出 了 简 短 的 总 结 。关键词：密 码 学 ； 量 子 计 算 ； 基 于 格 的 抗 量 子 密 码 ； 量 子 密 码Lattice-based CryptographyJiang ZHANG(State Key Laboratory of Cryptology, P.O.Box 5159, Beijing 100878, China)Abstract: In recent years, quantum computation has gaine

3、d great development, which bringsgreat challenges and threats to modern cryptology, and makes many people mistakenly believethat the quantum era would be the end of the modern cryptology. In this paper, we first beganwith the development history of cryptology, and investigated the actual impact of q

4、uantumcomputation on the modern cryptology and the importance of post-quantum cryptographicresearch. Then, we briefly reviewed the state of lattice-based cryptography, and introduced ourseveral works in this area. Finally, we gave a short conclusion.Keywords: Cryptology, quantum computation, lattice

5、-based cryptography, quantumcryptography1 引 言密 码 学 的 英 文 是 Cryptology， 源 自 希 腊 文 “kryptos”及 “logos”两 词 ， 即 为 “隐 藏 ”及 “讯 息 ”之 意 。 人 类 早 在 古 埃 及 时 代 就 开 始 使 用 密 码 技 术 ， 但 当 时 主 要 用 于 军 事 目 的 ， 保 护 军 事 秘 密不 被 敌 人 窃 取 。 此 后 ， 密 码 技 术 一 直 伴 着 人 类 历 史 的 前 进 而 发 展 ， 只 是 在 不 同 的 历 史 阶 段 ，不 同 的 信 息 技 术 水 平 具

6、 有 不 同 的 表 现 形 式 。 密 码 学 家 通 常 将 密 码 技 术 的 发 展 历 史 分 为 三 个 时期 ， 即 古 典 密 码 、 近 代 密 码 和 现 代 密 码 时 期 。 古 典 密 码 是 指 20 世 纪 40 年 代 之 前 的 密 码 技 术的 统 称 ， 其 代 表 有 古 罗 马 时 代 的 凯 撒 （ Caesar） 密 码 ， 以 及 二 战 中 德 国 使 用 的 ENIGMA 密 码机 等 。 古 典 密 码 以 现 代 计 算 机 的 鼻 祖 “图 灵 机 ”的 出 现 而 逐 渐 退 出 历 史 舞 台 。 信 息 技 术 的 进步 虽 然

7、给 密 码 技 术 带 来 新 的 危 机 和 挑 战 ， 却 也 促 使 密 码 技 术 不 断 向 前 发 展 ， 使 得 其 从 最 初 军作者简介：张 江 ， 男 ， 博 士 ， 密 码 科 学 技 术 国 家 重 点 实 验 室 助 理 研 究 员 ， 主 要 研 究 领 域 为 可 证 明 安 全 的 公 钥 密 码 协议 ， 中 国 密 码 学 会 CACR-P-1201172， 电 话 ： 010 82789199， E-mail： .万方数据2队 和 政 府 专 属 技 术 走 向 为 普 通 民 众 服 务 的 公 共 信 息 技 术 。 1949 年 仙 农 （ Shan

8、non） 发 表 了 著 名的 保 密 系 统 的 通 信 理 论 1， 建 立 了 近 代 密 码 学 的 理 论 基 础 。 20 世 纪 70 年 代 美 国 发 布 数 据加 密 标 准 （ DES） 2， 以 及 图 灵 奖 获 得 者 Diffie 和 Hellman 发 表 密 码 学 的 新 方 向 3则 标 志着 现 代 密 码 学 开 始 。如 图 1 所 示 ， 现 代 密 码 技 术 分 为 私 钥 （ 对 称 ） 密 码 技 术 和 公 钥 （ 非 对 称 ） 密 码 技 术 ， 其中 私 钥 密 码 技 术 主 要 研 究 对 象 为 私 钥 加 密 算 法 、 杂

9、 凑 函 数 和 消 息 认 证 码 等 ， 而 公 钥 密 码 技 术的 主 要 研 究 对 象 则 为 公 钥 加 密 算 法 、 数 字 签 名 算 法 和 密 钥 建 立 协 议 等 。 虽 然 私 钥 密 码 技 术 中的 私 钥 加 密 算 法 和 公 钥 密 码 技 术 中 的 公 钥 加 密 算 法 都 能 够 用 于 信 息 加 密 并 保 护 信 息 的 机 密性 ， 然 而 现 代 密 码 技 术 则 已 经 远 远 超 出 了 保 护 信 息 机 密 性 的 范 畴 。 在 理 论 上 现 代 密 码 学 依 赖于 计 算 复 杂 性 理 论 （ 即 求 解 某 些 计

10、 算 问 题 是 困 难 的 ） ， 但 在 技 术 上 私 钥 密 码 通 常 依 赖 于 现 有 的设 计 原 则 和 分 析 方 法 以 达 到 破 解 密 码 对 于 攻 击 者 在 计 算 上 是 不 可 行 的 ； 而 公 钥 密 码 则 依 赖 于具 体 的 数 学 困 难 问 题 并 通 过 安 全 归 约 将 对 于 公 钥 密 码 的 有 效 攻 击 变 成 求 解 相 应 的 数 学 困 难 问题 。 由 于 公 钥 密 码 利 用 的 数 学 困 难 问 题 往 往 具 有 非 常 丰 富 的 代 数 结 构 ， 这 使 得 对 公 钥 密 码 技术 的 攻 击 与 对

11、 私 钥 密 码 技 术 的 攻 击 有 着 巨 大 的 差 异 。 某 些 现 实 系 统 中 使 用 的 公 钥 密 码 系 统 （ 如RSA 和 ElGamal 公 钥 加 密 系 统 ） 是 建 立 在 大 整 数 分 解 问 题 和 求 解 离 散 对 数 问 题 的 困 难 性 之 上 ，虽 然 目 前 研 究 学 者 没 有 在 图 灵 机 模 型 下 找 到 求 解 这 两 类 问 题 的 高 效 算 法 （ 即 面 对 使 用 传 统 计算 机 的 攻 击 者 是 安 全 的 ） ， 但 在 1995 年 美 国 科 学 家 Peter Shor 却 给 出 了 能 在 多

12、项 式 时 间 内 高 效分 解 大 整 数 和 求 解 离 散 对 数 的 量 子 算 法 4。 换 句 话 说 ， 在 量 子 计 算 机 出 现 以 后 ， RSA 和 ElGamal公 钥 加 密 系 统 将 变 得 不 再 安 全 。图1现代密码技术上 述 密 码 系 统 在 面 对 经 典 计 算 机 和 量 子 计 算 机 时 的 安 全 性 差 异 源 自 于 量 子 计 算 机 与 经 典计 算 机 在 计 算 方 式 上 有 本 质 的 不 同 5。 例 如 ， 经 典 计 算 机 对 某 个 函 数 ()f 的 一 次 计 算 通 常 只 能获 得 ()f 在 某 个 特

13、 定 输 入 点 x 的 函 数 值 ( )f x ， 而 量 子 计 算 机 却 能 以 数 据 的 量 子 叠 加 态(Superposition State) x x 作 为 输 入 并 通 过 一 次 计 算 得 到 函 数 值 的 量 子 叠 加 态( )x f x 。 这 种 特 性 使 得 量 子 算 法 相 对 于 经 典 算 法 能 提 供 一 定 的 加 速 ， 但 具 体 的 加 速 性 能却 与 被 计 算 函 数 的 代 数 性 质 有 着 密 切 的 关 系 。 例 如 ， 对 于 大 整 数 分 解 问 题 和 求 解 离 散 对 数 问题 ， 量 子 算 法 相

14、 对 于 经 典 算 法 具 有 指 数 的 加 速4， 但 对 某 些 其 他 问 题 ， 量 子 算 法 却 只 能 提 供 多项 式 的 加 速 6。 特 别 地 ， 目 前 针 对 私 钥 密 码 最 高 效 的 Grover 量 子 算 法 7， 也 只 是 将 密 钥 的 有 效长 度 减 少 为 原 来 的 一 半 。 换 句 话 说 ， 只 要 将 目 前 私 钥 加 密 算 法 的 密 钥 长 度 扩 张 一 倍 就 能 够 有效 地 抵 抗 量 子 计 算 机 的 攻 击 。 此 外 ， 对 于 某 些 困 难 问 题 （ 如 NP 完 全 问 题 、 基 于 格 、 基

15、于 编 码和 基 于 多 变 量 方 程 的 数 学 问 题 ） ， 量 子 算 法 相 对 于 传 统 算 法 也 并 没 有 明 显 的 优 势 8,9。 实 际 上 ，万方数据3紧 跟 着 Shor 量 子 算 法 之 后 ， 国 内 外 密 码 学 家 已 开 始 利 用 基 于 格 、 基 于 编 码 和 基 于 多 变 量 方 程等 数 学 困 难 问 题 来 设 计 公 钥 密 码 系 统 ， 并 统 称 这 些 研 究 为 抗 量 子 密 码 学 9。由 于 公 钥 密 码 技 术 被 广 泛 应 用 于 实 际 信 息 系 统 ， 并 起 着 不 可 替 代 的 作 用 （

16、例 如 ， 私 钥 密码 技 术 不 能 完 全 替 代 数 字 签 名 算 法 的 作 用 ） ， 因 此 研 究 抗 量 子 密 码 具 有 极 大 的 必 要 性 和 紧 迫性 。 此 外 ， 随 着 量 子 计 算 技 术 的 发 展 ， 量 子 密 码 也 作 为 一 种 新 的 密 码 技 术 进 入 人 们 的 视 野 。严 格 来 说 ， 目 前 的 量 子 密 码 主 要 是 指 量 子 密 钥 传 输 协 议 （ QKD） 10,11， 其 完 成 的 主 要 是 公 钥密 码 技 术 中 部 分 密 钥 建 立 协 议 的 功 能 。 进 一 步 ， 由 于 公 钥 加

17、密 和 数 字 签 名 算 法 在 本 质 上 蕴 含着 从 “公 钥 不 能 计 算 出 私 钥 ”的 困 难 问 题 ， 因 此 在 理 论 上 不 可 能 利 用 量 子 技 术 实 现 “无 条 件 安 全的 公 钥 加 密 和 数 字 签 名 算 法 ”。 注 意 到 现 实 生 活 中 使 用 的 密 钥 建 立 协 议 （ 如 TLS/SSL 协 议 ） 往往 都 需 要 认 证 用 户 的 身 份 （ 即 需 要 签 名 算 法 ） ， 可 以 预 见 量 子 密 码 要 借 助 其 他 公 钥 密 码 技 术 才能 真 正 用 于 实 际 生 活 中 大 多 数 信 息 系

18、统 。 因 此 ， 研 究 基 于 抗 量 子 困 难 问 题 的 公 钥 密 码 技 术 抗 量 子 密 码 对 于 量 子 密 码 的 应 用 也 具 有 重 要 的 意 义 。2 基 于 格 的 抗 量 子 密 码经 过 多 年 的 研 究 ， 密 码 学 家 已 筛 选 出 了 几 大 类 极 有 希 望 能 够 抵 抗 量 子 计 算 机 攻 击 的 困 难问 题 ， 并 基 于 这 些 问 题 设 计 了 抗 量 子 攻 击 的 密 码 ， 包 括 基 于 格 的 密 码 、 基 于 编 码 的 密 码 、 基于 多 变 量 的 密 码 和 基 于 杂 凑 函 数 的 密 码 9。

19、 由 于 具 有 渐 进 的 计 算 效 率 、 基 于 最 坏 情 况 的 困 难 假设 、 极 大 的 多 样 性 等 优 点 ， 基 于 格 的 密 码 吸 引 了 国 内 外 密 码 学 家 的 广 泛 关 注 。 当 前 ， 为 已 有基 于 经 典 假 设 的 密 码 系 统 寻 找 基 于 格 上 困 难 问 题 的 替 代 密 码 系 统 已 经 变 成 一 个 重 要 的 研 究 方向 。2.1 研 究 现 状从 18 世 纪 开 始 ， 拉 格 朗 日 （ Lagrange） 和 高 斯 （ Gauss） 等 世 界 著 名 数 学 家 已 经 开 始 研 究格 上 的 困

20、 难 问 题 。 令 m 是 m 维 欧 几 里 得 空 间 。 令 1( , , ) m nn B b b 是 m 中 n 个 线 性 无关 列 向 量 构 成 的 矩 阵 。 一 个 由 矩 阵 B 生 成 的 格 ( )BL 是 一 个 由 其 列 向 量 1, , mn b b 的 所 有整 系 数 线 性 组 合 构 成 的 集 合 ， 即 ( ) : :n i i ii x x B Bx x b L 。 整 数 m 和 n 分 别称 为 格 ( )BL 的 维 数 和 秩 。 矩 阵 B 称 为 格 ( )BL 的 基 ， 一 个 格 通 常 有 许 多 不 同 的 基 。 格 中

21、 两 个最 重 要 的 困 难 问 题 是 最 短 向 量 问 题 （ SVP） 和 最 近 向 量 问 题 （ CVP） 。 令 1( ) 是 格 中 最 短向 量 的 长 度 。 给 定 m 中 秩 为 n 的 格 m 和 向 量 t m ， 定 义 向 量 t 到 格 的 距 离 为v( ,t) mindist v t 。定 义 1（ 近 似 最 短 向 量 问 题 ） 给 定 秩 为 n 的 格 ( ) BL 的 一 组 基 m nB 和 实 数 ( ) 1n ，近 似 最 短 向 量 问 题 SVP 的 目 标 是 寻 找 非 零 格 向 量 v使 得 1v ( ) 。定 义 2（

22、近 似 最 近 向 量 问 题 ） 给 定 秩 为 n 的 格 ( ) BL 的 一 组 基 m nB 和 目 标 向 量万方数据4t m ， 以 ( ) 1n 为 近 似 因 子 的 近 似 最 近 向 量 问 题 CVP 的 目 标 是 寻 找 格 向 量 v使 得v-t dist( ,t) 。当 近 似 因 子 ( ) 1n 时 ， 上 述 两 个 定 义 给 出 的 是 格 上 的 标 准 问 题 ， 并 被 证 明 了 是 NP 困 难的 12。 但 随 着 ( )n 的 变 大 ， 这 类 问 题 会 变 得 越 来 越 容 易 求 解 。 特 别 地 ， 当 loglog /lo

23、g( ) 2n n nn 时 ，相 关 近 似 问 题 就 已 存 在 多 项 式 时 间 的 求 解 算 法 13,14 。 虽 然 ， 对 于 多 项 式 近 似 因 子poly( ) ( )n n ， SVP 和 CVP 问 题 已 经 不 再 是 NP 困 难 的15,16， 但 求 解 这 两 类 问 题 却 仍 然 需要 指 数 的 计 算 时 间 和 空 间 17。 事 实 上 ， 即 使 对 于 ( ) 2kn 的 近 似 因 子 ， 目 前 最 好 的 算 法 也 需要 ( / )2O n k 的 计 算 时 间 。 此 外 ， Shor 提 出 的 用 于 大 整 数 分

24、解 和 离 散 对 数 的 量 子 算 法 4对 求 解 格 上的 困 难 问 题 也 没 有 明 显 的 优 势 。 特 别 地 ， 即 使 是 对 于 格 上 相 对 比 较 容 易 的 唯 一 最 短 向 量 问 题(Unique SVP)， 已 知 的 量 子 算 法 也 需 要 亚 指 数 的 计 算 时 间 9,18。 正 因 为 如 此 ， 多 项 式 近 似 因 子的 SVP 和 CVP 问 题 在 格 密 码 学 中 被 广 泛 地 用 做 抗 量 子 攻 击 的 困 难 假 设 。1999 年 ， Ajtai 构 造 了 第 一 个 基 于 格 上 困 难 问 题 的 单

25、向 函 数 族19， 并 证 明 了 如 果 多 项 式 近似 因 子 的 SVP 问 题 在 最 坏 情 况 下 是 困 难 的 ， 那 么 求 解 该 函 数 族 中 函 数 的 逆 在 平 均 意 义 下 也 是困 难 的 。 值 得 注 意 的 是 ， 这 种 “平 均 困 难 性 最 坏 困 难 性 的 联 系 ”是 其 他 密 码 构 造 都 不 曾 具 有 的优 良 性 质 。 此 外 ， Ajtai 的 工 作 19还 间 接 地 提 出 了 格 上 密 码 学 常 用 的 两 个 困 难 假 设 之 一 的 最 小整 数 解 问 题 （ SIS） 。 2005 年 ， Reg

26、ev 提 出 了 格 密 码 常 用 另 一 个 困 难 假 设 带 错 误 的 学 习 问 题（ LWE） 20， 并 同 样 证 明 了 该 问 题 的 平 均 困 难 性 与 多 项 式 近 似 因 子 的 SVP 问 题 最 坏 困 难 性 在量 子 归 约 下 是 等 价 的 。 由 于 大 多 格 上 密 码 都 是 基 于 SIS 问 题 和 LWE 问 题 构 造 的 ， 因 此 这 些 基于 格 的 密 码 天 然 的 拥 有 相 应 格 上 问 题 的 最 坏 困 难 性 保 证 。 经 过 20 多 年 的 研 究 ， 基 于 格 的 密 码在 公 钥 加 密 算 法20

27、、 数 字 签 名 算 法 21,22、 密 钥 交 换 协 议 23,24、 基 于 身 份 加 密 算 法 22,25， 甚 至 还包 括 全 同 态 加 密 算 法 26和 函 数 加 密 算 法 27等 都 取 得 了 丰 硕 的 成 果 。 此 外 ， 大 多 数 基 于 格 的 密码 计 算 效 率 也 比 较 高 ， 且 支 持 高 度 并 行 ， 但 基 于 格 的 密 码 也 有 如 下 两 个 缺 点 ： 1） 密 钥 长 度 和通 信 代 价 比 较 大 ， 即 使 是 基 于 理 想 格 的 密 码 构 造 也 需 要 数 千 字 节 23， 比 基 于 大 整 数 分

28、 解 问 题等 传 统 公 钥 密 码 还 要 大 几 十 倍 ； 2） 基 于 格 的 密 码 涉 及 与 安 全 强 度 相 关 的 参 数 较 多 ， 选 取 特 定安 全 强 度 的 参 数 和 评 估 给 定 参 数 的 具 体 安 全 强 度 的 困 难 性 较 高 。2.2 我 们 的 部 分 工 作近 年 来 ， 我 们 一 直 在 从 事 抗 量 子 密 码 的 研 究 工 作 ， 并 取 得 了 一 些 阶 段 性 的 研 究 成 果 。 特别 地 ， 在 抗 量 子 公 钥 加 密 算 法 研 究 方 面 ， 我 们 设 计 了 格 上 第 一 个 基 于 属 性 的 加

29、 密 算 法28， 第一 个 支 持 灵 活 门 限 访 问 结 构 的 属 性 加 密 算 法 29， 第 一 个 在 标 准 模 型 下 适 应 安 全 的 具 有 对 数 公钥 长 度 的 基 于 身 份 加 密 算 法 22， 以 及 第 一 个 支 持 常 数 噪 音 LPN 假 设 的 公 钥 加 密 算 法 30； 在 抗量 子 密 钥 交 换 协 议 研 究 方 面 ， 我 们 通 过 使 用 “噪 声 消 除 ”和 “拒 绝 采 样 ”等 技 术 基 于 格 上 困 难 问 题设 计 了 第 一 个 两 轮 隐 式 认 证 的 密 钥 交 换 协 议 24； 在 抗 量 子

30、数 字 签 名 算 法 研 究 方 面 ， 我 们 设 计了 第 一 个 参 数 几 乎 与 群 成 员 个 数 无 关 的 格 上 群 签 名 算 法 31和 第 一 个 标 准 模 型 下 对 数 公 钥 长 度万方数据5的 短 签 名 算 法 22。3 总 结 与 展 望量 子 计 算 虽 然 给 现 代 密 码 技 术 带 来 一 定 的 挑 战 ， 但 其 仅 仅 对 基 于 某 些 具 体 数 学 问 题 的 密码 方 案 有 颠 覆 性 的 威 胁 ， 并 没 有 动 摇 现 代 密 码 学 的 理 论 基 础 。 量 子 密 码 （ 量 子 密 钥 传 输 ） 虽然 能 够 替

31、 代 公 钥 密 码 技 术 中 部 分 密 钥 交 换 协 议 的 功 能 ， 但 其 却 不 能 替 代 现 代 密 码 技 术 特 别 是公 钥 密 码 技 术 在 实 际 应 用 中 的 作 用 ， 因 此 研 究 抗 量 子 的 新 型 公 钥 密 码 具 有 极 大 的 必 要 性 和 紧迫 性 。虽 然 当 前 量 子 计 算 机 还 处 于 非 常 原 型 的 阶 段2， 但 密 码 学 家 却 早 已 开 始 抗 量 子 密 码 的 研 究 。特 别 地 ， 美 国 国 家 标 准 研 究 所 （ NIST） 已 于 2016 年 开 始 抗 量 子 密 码 标 准 的 征

32、集 ， 并 计 划 将 于2023 年 左 右 推 出 抗 量 子 密 码 标 准 。 我 们 有 理 由 相 信 更 先 进 的 抗 量 子 密 码 必 将 先 于 量 子 计 算 机进 入 实 际 应 用 。参考文献1 Claude E. Shannon. Communication theory of secrecy systemsJ. Bell Labs Technical Journal,1949,28(4):656715.2 National Bureau of Standards, Data Encryption StandardS, U.S. Department of Com

33、merce, FIPS pub. 46,January 1977.3 Whitfield Diffie and Martin Hellman. New directions in cryptographyJ. IEEE transactions on InformationTheory, 1976, 22(6):644654.4 Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantumcomputerJ. SIAM Journal on Compu

34、ting, 1997, 26(5):14841509.5 Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum informationM. Cambridgeuniversity press, 2000.6 Robert Beals, Harry Buhrman, and Richard Cleve et al. Quantum lower bounds by polynomialsJ. Journal ofthe ACM, 2001, 48(4):778797.7 Lov K Grover. Quantum

35、 mechanics helps in searching for a needle in a haystackJ. Physical review letters,1997, 79(2):325328.8 Charles H. Bennett, Ethan Bernstein, and Gilles Brassard et al. Strengths and weaknesses of quantumcomputingJ. SIAM journal on Computing, 1997, 26(5):15101523.9 Daniel Bernstein, Johannes Buchmann

36、, and Erik Dahmen. Post-quantum cryptographyM. Springer Science &Bussiness Media, 2009:1-245.10 ChariesH. Bennett and Gilles Brassard. Quantum Cryptography: Public-Key Distribution and Coin TossingC.Proceedings of the International Conference on Computers, Systems and Signal Processing, Bangalore, I

37、ndia,1984:175-179.11 Gilles Brassard. Brief history of quantum cryptography: A personal perspectiveC/IEEE Information TheoryWorkshop on Theory and Practice in Information-Theoretic Security, IEEE, 2005:1923.12 Daniele Micciancio and Shafi Goldwasser. Complexity of lattice problems: a cryptographic p

38、erspectiveM,Springer Science & Business Media, 2012:1-220.13 C.P Schnorr. A more efficient algorithm for lattice basis reductionJ. Journal of Algorithms, 1988, 9(1):47 62.2目 前 已 知 量 子 计 算 机 只 能 将 整 数 35 分 解 成 5 乘 7（ 即 分 解 小 于 6 比 特 位 的 整 数 ） ， 而 实 际 应 用 中 较 低 安 全 强 度 的RSA 密 码 系 统 使 用 的 却 是 1024 比 特

39、位 的 大 整 数 。万方数据614 A.K. Lenstra, Jr. Lenstra, H.W., and L. Lovsz. Factoring polynomials with rational coefficientsJ.Mathematische Annalen, 1982, 261(4):515534.15 Oded Goldreich and Shafi Goldwasser. On the limits of non-approximability of lattice problemsC/Proceedings of the Thirtieth Annual ACM Sym

40、posium on Theory of Computing, New York, ACM, 1998:19.16 Dorit Aharonov and Oded Regev. Lattice problems in NP CoNPC/Proceedings of the 45th Annual IEEESymposium on Foundations of Computer Science, 2004: 362371.17 Mikls Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice

41、vectorproblemC/Proceedings of the 33rd annual ACM symposium on Theory of computing, New York, ACM,2001:601610.18 Oded Regev. Quantum computation and lattice problemsJ. SIAM Journal on Computing, 2004,33(3):738760.19 Mikls Ajtai. Generating hard instances of lattice problems (extended abstract)C/Proc

42、eedings of the 28thannual ACM symposium on Theory of computing, New York, ACM, 1996:99108.20 Oded Regev. On lattices, learning with errors, random linear codes, and cryptographyC/Proceedings of the37th annual ACM symposium on Theory of computing, New York, ACM, 2005:8493.21 Vadim Lyubashevsky and Da

43、niele Micciancio. Asymptotically efficient lattice-based digitalsignaturesC/Theory of Cryptography, LNCS 4948, 2008:37-54.22 Jiang Zhang, Yu Chen, and Zhenfeng Zhang. Programmable Hash Functions from Lattices: Short Signaturesand IBEs with Small Key SizesC/Advances in Cryptology CRYPTO 2016. LNCS 98

44、16, 2016:303332.23 Erdem Alkim, Lo Ducas, and Thomas Pppelmann et al. Post-quantum key exchange a newhopeC/USENIX Security 2016, Austin, USENIX Association, 2016:327-343.24 Jiang Zhang, Zhenfeng Zhang, and Jintai Ding et al. Authenticated key exchange from ideallatticesC/Advances in Cryptology EUROC

45、RYPT 2015, LNCS 9057, 2015:719751.25 Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographicconstructionsC/Proceedings of the 40th annual ACM symposium on Theory of computing, New York, ACM,2008:197-206.26 Craig Gentry. Fully homomorphic encryption us

46、ing ideal latticesC/Proceedings of the 41st annual ACMsymposium on Theory of computing, New York, ACM, 2009:169178.27 Shweta Agrawal, David Mandell Freeman, and Vinod Vaikuntanathan. Functional Encryption for InnerProduct Predicates from Learning with ErrorsC/Advances in Cryptology - ASIACRYPT 2011,

47、 LNCS 7073,2011: 21-40.28 Jiang Zhang and Zhenfeng Zhang. A ciphertext policy attribute-based encryption scheme withoutpairingsC/Information Security and Cryptology INSCRYPT 2011, LNCS 7537, 2012:324340.29 Jiang Zhang, Zhenfeng Zhang, and Aijun Ge. Ciphertext policy attribute-based encryption fromla

48、tticesC/Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security,New York, ACM, 2012: 1625.30 Yu Yu and Jiang Zhang. Cryptography with Auxiliary Input and Trapdoor from ConstantNoiseLPNC/Advances in Cryptology CRYPTO 2016, LNCS 9814, 2016 :214243.31 Phong Q. Nguyen, Jiang Zhang, and Zhenfeng Zhang. Simpler efficient group signatures fromlatticesC/Public-Key Cryptography PKC 2015, LNCS, 2015, 9020:401426.万方数据