Abstract
本文指出在DH密钥交换协议中，从公钥计算密钥是困难的。通过隐藏数问题的研究证明：
给定一个预言，输入
计算 的个最高有效位（most significant bit）
找到
该方案可以证明MSB在其他方案中的难度，例如EIGamal公钥系统、Shamir信息传递方案、Okamoto的会议密钥共享方案。作者由此结果提出了新的DH密钥交换变体，证明了MSB是计算困难的。
1 Introduction
中相对基于的离散对数问题（DPL）是给定 求。假设这个问题很难，DH提出了这个公钥系统。A、B分别拥有私钥 。对应计算 并将结果发送给对方。然后它们计算出密钥很多人认为在函数是和DLP一样是计算困难的。
在进行密钥协商之后，可以通过分组密码对会话内容进行加密。一种自然的方法来推导密文的密钥是使用从的一个比特块。例如，如果是一个1024位的素数，则可以使用中的64个最高有效位。攻击者可能无法计算整个，但也可能成功地计算这部分比特并破解会话。
因此，重要的是要知道的最高有效位（MSB）是否安全，包括。 以本篇文章的发表时间，DH密钥的MSB安全性尚未被证明。
提出的一些加密方案与DH函数有关，或基于该函数。这些方案依赖于的“隐藏”性质。
在本文，作者研究了Diffie-Hellman密钥交换方案的以及上面提到的相关方案的MSB安全性。作者证明DH的秘密在 或更多的MSB与整个秘密一样都是计算困难的。对于一个1024位的素数，作者的结果意味着32个或更多的MSB是计算困难的。结果是基于LLL在格上的取整，结合Babai和Schnoor的结果改进到：任意固定的 ，有。
