基于格的抗量子密码.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 构 造 了 第 一 个 基 于 格 上 困 难 问 题 的 单
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 量子 密码
限制150内