密钥协商算法主要用于在TLS/SSL等安全协议中协商会话密钥。丁式密钥协商（Ding Key Exchange）是由丁津泰教授在美国辛辛那提大学就职时提出的，该算法是第一个完整的基于错误学习问题（LWE/RLWE）的类Diffie-Hellman协议。
Diffie-Hellman（DH）密钥协商的过程如图1所示，g是公共的因子，红色的Alice和蓝色的Bob分别生成a和b，Alice和Bob如图执行交互，这样可以获得相同的数据，即
(gb)a=(ga)b
该值即可作为会话密钥。DH密钥协商的安全性可以归约到离散对数困难问题， DH密钥协商的原型易受中间人攻击，因此实际应用中会采用其增强方案，这一点在本文中不再赘述。
图1 Diffie-Hellman密钥协商
图2是Ding密钥协商的基本流程，可以看出该协议的宏观过程与DH密钥协商是一致的，因此该协议可以比较容易地置换现在广泛使用的DH密钥协商。
图2 Ding密钥协商交互
与DH密钥协商不同的是，Ding密钥协商的结果kA，kB不是严格相等的，好在a是在Zq中均匀采样的，而e是值很小，因此kA和kB的差异仅在低有效的比特位。因此需要一种协调机制（Reconciliation）使双方规避误差，最终得到相同的会话密钥，这需要用到图2中红色问号部分，这个值需要称为 “信号（Signal）”。
图3 Ding密钥协商具体流程
图3中的Round和Recover函数是用于减少通信开销的一对函数。Sig函数用于生成Signal，Mod2函数用于错误协调。我们观察到，kA（ki）和kB（kj）若没有模约减的情况，则它们的奇偶性是一致的，原因在于加性误差是2的倍数，这也就是说可以用mod2的结果达成1bit的共识。但由于模数往往是奇素数，如果约减次数不同，那么最终kA（ki）和kB（kj）的奇偶性会有差异，因此在Mod2函数中实际需要确保kA（ki）和kB（kj）不能恰好“跨越”一个模数。
图4 Mod2函数中的区域翻转
如图4所示，[-q/2,q/2] 分为两个部分，[-q/4,q/4]为inner region，其他为outer region。
为了避免“跨越”一个模数，Ding的方案是将kA（ki）和kB（kj）都转换到inner region，对kA（ki）来说，如果kB（kj）发来的signal（即wj）是1，那么就执行转换，否则不执行转换。Ding的方案的容错能力是(q/4)-2。
作者：陈朝晖
参考：
[1]Ding, J.: A simple provably secure key exchange scheme based on the learning with errors problem. IACR Cryptology ePrint Archive 2012/688 (2012)
