格上不经意传输协议的分析与设计

摘要

密码学作为信息安全领域的重要理论基础与关键技术，在互联网技术快速发展的今天，为网络中的数据加密、消息认证、访问控制等实际应用提供可靠技术保障。然而，随着量子计算技术的发展，传统公钥密码体制受到了极大挑战，使得基于经典数论问题的密码系统在量子环境下不再安全。面对来自量子计算技术的威胁，后量子密码（post-quantum cryptography）引起了密码研究者、各国标准机构以及政府机要部门的广泛关注。作为后量子密码的一个研究分支，格公钥密码（lattice-based cryptography）相较于其他后量子密码体制具有显著优势，在密码学发展进程中占据重要地位。 目前，基于格公钥密码的方案构造多是对加密、签名等密码原语的研究，在协议构造方面的研究工作甚少。此外，不经意传输（oblivious transfer，OT）因其具有简洁的密码功能，被广泛应用于安全多方计算等高层应用协议中。然而，目前大多数OT协议都依赖于大数分解或离散对数困难假设而构建，基于后量子密码体制的OT协议研究并不深入。因此，研究基于格公钥密码体制的OT协议具有积极的意义。本文将以此动机，围绕格上OT协议（lattice-based OT protocols）进行分析与设计，并取得如下主要成果： 1.针对后量子密码方案往往缺乏量子安全性证明的问题，在量子环境下对一个高效的格上OT协议进行量子安全性分析。由于大多数后量子密码体制只在传统敌手存在的情况下给出安全证明，并没有考虑协议在量子环境下的安全性。通过使用量子平移定理等相关定理，在量子敌手存在的环境下，对一个格上OT协议进行量子安全性分析，一定程度上缓解了后量子密码体制缺乏量子安全证明这一问题现状。 2.针对通用可组合性（universal composability，UC）安全模型因其高度广义的模型形式化，难以在实际中具体分析协议这一问题，使用一个更加简洁合理的分析模型研究格上UC安全OT协议的实际可组合性。UC模型的高度通用性使得难以在实际中明确表述协议以及分析协议的组合特性，等式安全模型（equational security framework）提供了具体的通信数学模型，并以数学等式形式的简洁语法规则描述密码协议，从一定程度上解决了UC模型难以实际应用这一问题。因此，在等式安全模型下，我们将对一个格上UC安全的OT协议进行安全性分析。我们最初的目的是想要证明该协议可在等式安全模型中获得其声称的UC安全性，从而说明该协议在实际中可获得完全异步的可组合性。然而，在证明过程中我们发现了一个时间漏洞。虽然对使用的OT理想函数进行了两次改进，但是仍然无法在等式安全模型下获得该协议所声称的安全性。 3.针对构造基于后量子密码体制且满足UC安全性OT协议的困难性，提出了几个格上UC安全的OT协议。首先，基于环上带差错学习（ring learning with errors，RLWE）问题，提出一个UC安全的2-选-1OT协议，并将其自然地扩展为一个UC安全的N-选-1OT协议。此外，基于同样的协议结构，分别使用一个改进的基于RLWE问题以及一个基于带差错学习（learning with errors，LWE）问题的格上密钥交换协议作为协议组件，从而获得一个改进的基于RLWE问题的OT协议，以及一个基于LWE问题的OT协议。最后，我们给出效率比对表，以证明所提出的格上UC安全OT协议是高效的。 4.鉴于发展格上其他密码构造这一迫切性要求，提出一个改进的格上哈希证明系统（hash proof system，HPS）。首先，对一个基于LWE问题的密钥交换协议进行扩展，使其对任意模数可用。进而，可利用扩展协议背后的调和机制（reconciliation mechanism），改进一个高效的格上HPS方案，使其可输出多个封装比特，并在计算和存储开销方面优于其他方案。此外，应用扩展后的调和机制，可直接改进这个格上HPS原始方案中的两个应用扩展，即基于身份的哈希证明系统（identity-based hash proof system，IB-HPS）和可更新的哈希证明系统（updatable hash proof system，UHPS），从而优化这两个应用扩展方案的性能。

目录

第一个书签之前

摘要

ABSTRACT

插图索引

表格索引

符号对照表

缩略语对照表

第一章 绪论

1.1研究背景及意义

1.2国内外研究现状

1.3研究成果及内容安排

第二章 预备知识

2.2格理论知识

2.2.1格理论基础知识

2.2.2格上困难问题

2.2.3LWE 问题

2.2.4RLWE 问题

2.3高斯分布

2.3.1取整高斯分布

2.3.2离散高斯分布

2.3.3格上高斯分布

2.3.4光滑参数

2.4不经意传输

2.5UC 安全模型

2.5.1UC 模型

2.5.2OT 理想函数

2.5.3攻陷场景

2.6本章小结

第三章 格上不经意传输协议的量子安全性分析

3.2量子 UC 模型

3.2.1量子计算基础知识

3.2.2机器模型

3.2.3量子 UC 安全性

3.3基于 LWE 问题的不经意传输协议

3.3.1基于 LWE 问题的双模密码系统

3.3.2基于 LWE 问题的 OT 协议

3.3.3仿真器构造

3.4量子安全性分析

3.4.1量子平移定理

3.4.2量子安全证明

3.5本章小结

第四章 格上 UC 安全不经意传输协议的等式安全性分析

4.2等式安全模型

4.3协议 dmmode 的等式描述

4.4协议 dmmode 的等式安全性分析

4.4.1关于 FOT 的等式安全性

4.4.2关于 F'OT 的等式安全性

4.4.3关于 F''OT 的等式安全性

4.5本章小结

第五章 格上 UC 安全的不经意传输协议构造

5.2符号说明及协议基本组件

5.2.1符号说明

5.2.2基于 RLWE 问题的密钥交换协议

5.2.3哈希函数

5.2.4对称加密算法

5.3协议 1：基于 RLWE 问题的 UC 安全 OT 协议

5.3.1随机 OT

5.3.2标准 OT

5.3.3协议 2：UC 安全的 N-选-1 OT 协议

5.4协议 1 的改进版本

5.4.1协议 3：（改进的）基于 RLWE 问题的 UC 安全 OT 协议

5.4.2协议 Newhope 的调和机制

5.4.3证明概要

5.5.1协议 4 ：基于 LWE 问题的 UC 安全 OT 协议

5.5.2协议 Frodo 的调和机制

5.5.3证明概要

5.6效率比对

5.7本章小结

第六章 改进的格上哈希证明系统

6.2哈希证明系统及相关引理介绍

6.2.1哈希证明系统

6.2.2相关定理及引理

6.3扩展的基于 LWE 问题的密钥交换协议

6.3.1对任意模数可用的密钥交换协议

6.3.2协议的安全性

6.3.3协议的正确性

6.4改进的基于 LWE 问题的哈希证明系统

6.5改进的两个应用扩展：IB-HPS 和 UHPS

6.5.1IB-HPS

6.5.2UHPS

6.6本章小结

第七章 总结与展望

7.2研究展望

参考文献

致谢

作者简介