Ralph Merkle 于1974年提出 Merkle's Puzzles 公钥密码协议

在密码学中，Merkle's Puzzles 是一种早期的公钥密码系统构造，由 Ralph Merkle 于 1974 年设计、1978 年发表。它允许两方通过交换消息来协商一个共享秘密，即使他们事先没有任何共同的秘密。

假设 Alice 和 Bob 希望进行通信。Bob 可以按如下方式向 Alice 发送消息：首先他创建大量谜题，每个谜题的难度适中——必须让 Alice 能够以适中的计算量解开谜题。谜题的形式是一条用未知密钥加密的消息；密钥必须足够短，以便能够进行暴力破解。Bob 把所有谜题（即加密消息）发送给 Alice，Alice 随机选择一个并解开它。解密后的解中包含一个标识符以及一个会话密钥，因此 Alice 可以告诉 Bob 她解开了哪个谜题。现在双方都拥有一个共同的密钥：Alice 因为她解开了谜题，Bob 因为他发送了该谜题。任何窃听者（比如 Eve）面临的任务更困难——她不知道 Alice 解开的是哪个谜题。她最好的策略是解开所有谜题，但由于谜题数量太多，这对 Eve 来说计算代价比 Alice 更高。

请注意，窃听者 Eve 可以读取 Alice 发回给 Bob 的标识符 X（以明文形式），但如果不暴力破解大多数原始消息，她就无法将其映射到 Bob 和 Alice 现在用于持续通信的秘密密钥 Y，因为每条消息中的 X 值都是随机生成的。

可以调整谜题游戏的参数，使得窃听者破解代码的难度远高于各方通信的难度，但 Merkle's Puzzles 并未提供现代密码学所要求（并据以定义安全性）的那种巨大的定性难度差异。

假设 Bob 发送的谜题数量为 m，Bob 和 Alice 各需要 n 步计算来解开一个谜题。那么双方都能在 O(m+n) 的时间复杂度内推导出一个共同的会话密钥。相比之下，Eve 需要解开所有谜题，这需要花费她 O(mn) 的时间。如果 m ≈ n，Eve 的工作量大致是 Alice 和 Bob 的二次方复杂度，即她的计算时间大约是他们的平方量级。因此 n 应选择得足够大，使得计算对 Alice 和 Bob 仍然可行，同时超出 Eve 的能力。

对于实际现实世界的密码学应用而言，二次方复杂度通常不被认为足以抵御攻击者（或者走另一个极端，当 m、n 很大时，对参与者来说也不够方便）。然而，这个方案的独特之处在于它是公钥密码学的首批示例之一，并且启发了 Diffie-Hellman 密钥交换协议——后者具有高得多的复杂度，依赖于离散对数问题。

2008 年，Boaz Barak 和 Mohammad Mahmoody-Ghidary 证明了（“Merkle Puzzles Are Optimal”）这个二次方界无法被改进。