Anamorphic Authenticated Key Exchange: Double Key Distribution under Surveillance

变形认证密钥交换：监管下的双重密钥分发

Weihao Wang, Shuai Han*, Shengli Liu*

研究目标

本论文致力于研究受迫环境下的高效隐蔽密钥协商方案（即变形认证性密钥协商协议，AM-AKE），用以对抗一些比传统密码学所赋予能力更强的敌手，为各类受迫环境下依赖于隐蔽密钥安全性进行隐蔽通信的密码学原语（如变形加密、变形签名等）提供重要的安全保障。对于受迫环境下的认证性密钥协商协议（AKE）而言，敌手可以强迫所有用户交出自己的长期私钥，还能查看每次AKE会话的中间状态及双方协商出的会话密钥，甚至实施主动攻击。我们的目标是合理刻画出AM-AKE的安全模型，并构建高效的AM-AKE协议，使得通信双方在不提前共享信息的前提下，不仅能协商出一个会话密钥，还能秘密地协商出一个敌手不知道的隐蔽密钥，进而为变形密码的真正落地创造必要条件。

关键问题

  1. 如何定义AM-AKE的安全模型？该问题主要有三个方面需要考虑：（1）对受迫环境下敌手能力的刻画，即敌手能够获得AKE协议中的哪些信息，并如何体现主动攻击；（2）体现AM-AKE的隐蔽性，即敌手不能区分出正常AKE协议和AM-AKE协议；（3）体现隐蔽密钥的隐蔽性，即敌手无法获得隐蔽密钥的任何信息。

  2. 如何在AM-AKE中建立起用户相对于敌手的优势？长期私钥是AKE协议中用户优势的全部来源，而受迫环境下的敌手可以强制所有用户交出自己的长期私钥并实施主动攻击，从而可以完美假冒任何用户进行正常的AKE通信。因此，受迫环境下的用户必须额外拥有一些敌人无法从长期私钥中获取到的信息，并以此信息作为协商出隐蔽密钥的基本条件。

  3. 如何处理较难建立优势的AM-AKE？对于一些AKE协议，我们很难设找出关于用户长期私钥的秘密信息并以此协商隐蔽密钥，由此设计出的AM-AKE方案（称作平凡AM-AKE）较难实现受迫环境下的安全性。我们从两个方面解决该问题：（1）证明平凡AM-AKE关于安全性的一些不可能结果；（2）适当降低安全模型设计中对安全性的要求，使得平凡AM-AKE方案在模型放松后可被证明为安全。

研究内容

本论文主要研究AM-AKE的安全模型设计及方案构造，并在所设计的安全模型下证明方案的安全性。具体而言，分为以下几个方面进行研究。

  1. AM-AKE的语义、正确性、鲁棒性定义及安全模型设计。其中，安全模型分别从AM-AKE工作模式的不可区分性及隐蔽密钥的伪随机性为出发点进行设计。

  2. 证明平凡AM-AKE关于鲁棒性、安全性的不可能结果。

  3. 设计平凡AM-AKE的通用构造并证明其安全性，同时给出实例化方案。

  4. 设计AM-AKE的通用构造并证明其强安全性，同时给出实例化方案。

技术路线

为了设计AM-AKE方案，我们先归纳、提炼出底层AKE所需满足的性质，利用与这些性质相契合的合适的密码学工具设计出对隐蔽密钥的协商策略，进而证明其鲁棒性、安全性等。具体而言，分为以下几个步骤。

  1. 探究AM-AKE方案对底层AKE的要求。其中，我们要求AKE的长期密钥产生算法具有秘密可提取性，使得用户可以调用一个与之等价的算法并额外获得关于私钥的陷门，通信双方可以用自己的私钥陷门与对方的公钥共享一个敌手不可知的秘密信息；除此之外，我们还要求AKE的会话密钥导出算法具有可分性，保证每次会话交互信息（transcript）的新鲜性，用以实现鲁棒性和安全性。

  2. 利用伪随机函数实现隐蔽密钥的协商。由于通信双方已经共享了一个敌手不可知的秘密信息，因此可以用该秘密信息作为伪随机函数的种子，用AKE会话的transcript作为函数输入，然后计算得到隐蔽密钥。

  3. 通过底层AKE的性质证明方案的鲁棒性及安全性。例如，通过长期密钥产生算法的秘密可提取性证明隐蔽密钥的伪随机性；通过会话密钥导出算法的可分性，用不同分片之间的联系证明工作模式不可区分性及鲁棒性等。

8. 变形AKE

研究意义

我们首先给出了AM-AKE语义、正确性及鲁棒性的具体定义，并刻画了两种安全模型，包括工作模式不可区分性（IND-WM）及隐蔽密钥的伪随机性（PR-DK）。我们还刻画了AM-AKE的强安全模型，让敌手额外获得AKE算法中使用的随机数。对于平凡AM-AKE，我们证明了一些关于鲁棒性、安全性的不可能结果，并利用具备随机数可恢复性质算法的AKE给出了其通用构造，实现了鲁棒性和放松后的安全性；对于非平凡AM-AKE，我们利用满足秘密可提取性和算法可分性的AKE并配合伪随机函数给出了其通用构造，实现了鲁棒性和强安全性。除此之外，我们还基于目前流行的两种流行的 AKE范式（SIG+KEM范式及3KEM范式）给出了两种平凡AM-AKE和两种非平凡AM-AKE的具体构造。

我们所设计的AM-AKE通用构造可以广泛通过具体的AKE进行实例化，可以安全而高效地分配隐蔽密钥，使得依赖于隐蔽密钥安全性的变形密码（包含基于接收方的变形加密和变形签名）具备了基本的安全保障并得以真正落地，在变形密码面临的受迫环境下具有很高的研究意义与实用价值。