More Efficient Public-Key Cryptography with Leakage and Tamper Resilience

更高效的抗泄露抗篡改公钥密码系统

Shuai Han, Shengli Liu*, Dawu Gu

研究目标

设计高效的数字签名和公钥加密方案，并使其同时具备抗泄露与抗篡改能力，在敌手能够非黑盒访问密码设备，部分泄露私钥信息，并能够篡改密码设备运行时输入的私钥的条件下，仍然能够达成数字签名的强存在不可伪造安全性，以及公钥加密的CCA安全性。

关键问题

在密码方案安全分析中，通常假设敌手只具有黑盒访问运行密码方案的设备的能力，这忽略了现实中的敌手对密码设备进行非黑盒访问所带来的威胁。这包括利用侧信道攻击等技术手段泄露私钥的部分信息，以及利用故障注入、内存篡改等技术手段使密码设备工作在与预设私钥不同，但与之有关的密钥上。如何从密码方案设计的层面防御现实中的这两类攻击成为一大问题。

现有的针对抗泄露或抗篡改的公钥加密与数字签名成熟方案主要分别考虑这两种攻击，构造能够抵抗二者之一的公钥加密与数字签名方案。而针对同时抗泄露与抗篡改的方案研究，仍然比较初步。尽管存在多种针对同时抗泄露抗篡改的安全模型，如CTL、BTL、sLTR等模型，分别对应具有不同种类泄露与篡改能力的敌手，具有不同安全强度。其中CTL模型下的方案具有最强的安全性，但这也给它带来极高的效率损失；但即使是在安全性保障更弱的BTL、sLTR等模型下，现有的公钥加密与数字签名方案的效率也十分低下，多数方案需要依赖真模拟可提取的非交互式零知识证明（tSE-NIZK）作为底层组件进行构建，使得密文或签名长度过长。

如何设计足够高效的公钥加密与数字签名，使之能够充分权衡抗泄露抗篡改安全性和运行效率上，以尽可能高的效率达成充分的抗泄露抗篡改安全性，是我们工作研究的关键问题。

研究内容

  1. 我们形式化了数字签名的强抗泄露抗篡改安全模型，定义了数字签名在面对选择消息攻击时的抗泄露抗篡改的强存在不可伪造性 (sLTR-CMA)。该模型下，敌手可以泄露的有界的一部分设备内部信息，还可以发起无限次篡改攻击，但篡改方式必须局限在事先声明的函数集合中。

  2. 我们直接构造了在sLTR模型下安全的数字签名方案，以及具有sLTR模型下CCA安全性的高效公钥加密方案。两种方案在抗篡改上均能抵抗基于仿射函数族的篡改攻击。在抗泄露上，数字签名方案可以抵抗1/4-o(1)的泄露率，公钥加密方案可以抵抗1/3-o(1)的泄露率。两种方案的效率均相比此前方案有显著提升。

技术路线

  1. 我们基于非对称双线性配对群上的MDDH假设并利用抗碰撞哈希函数直接设计sLTR模型下安全的数字签名与公钥加密方案，而不使用tSE-NIZK等复杂的密码原语作为底层组件。

  2. 我们在方案中非黑盒地使用一种特殊的基于MDDH假设与抗碰撞哈希函数OTSS-NIZK，其能够引导具有特殊形式的随机性。

  3. 我们的数字签名的构造基于一个使用MDDH假设构造的公开可验证函数，使得取得公钥的参与方都可以验证函数的输出值，并且不得知函数输入值的其他相关信息。我们在此之上，非黑盒地利用前述的特殊OTSS-NIZK隐藏这一公开可验证函数的信息，实现了sLTR-CMA安全的高效数字签名。

  4. 我们的高效公钥加密方案基于一种基于MDDH的仅具有CPA安全的变种Cramer-Shoup公钥加密方案。我们在此之上，非黑盒地利用前述的特殊OTSS-NIZK，将CPA安全提升至CCA安全并达成了方案的抗泄露与抗篡改性质，高效地实现了sLTR-CCA安全性。

11. 抗泄露抗篡改公钥密码系统

研究意义

  1. 我们提出的数字签名与公钥加密具有效率高的优点。其中，我们提出的数字签名方案所产生的签名包含仅4个群元素，以往抗泄露抗篡改方案的签名长度是我们的5~8倍；提出的公钥加密方案密文仅包含6个群元素，以往抗泄露抗篡改方案的密文长度是我们的1.3~3.3倍。

  2. 我们首次针对数字签名形式化地定义了sLTR-CMA安全性，为进一步研究数字签名抗泄露抗篡改安全性与效率之间的权衡，以及设计高效抗泄露抗篡改签名方案奠定了基础。

  3. 我们提出的签名方案是首个在sLTR模型下实现强存在性不可伪造性的方案。这一构造为在抗泄露抗篡改场景下构造高效的认证密钥交换（AKE）等高级密码原语提供了强有力的基础组件。