代理重加密：NuCypher Umbral介绍

　　NuCypher 是一个满久的项目了，最主要的目标是为隐私保护的应用提供基础设施，包含了Secret Management、Dynamic Access Control 与Secure Computation。其中会用到的代理重加密这个功能，这篇文章将介绍NuCypher使用的代理重加密方法，他们命名为Umbral，在西班牙文中这是Threshold 的意思。

　　简介代理重加密与Umbral

　　Umbral 是一个门槛式代理重加密方法，首先我们需要先了解重加密是什么。在现代生活中，云端硬盘大概是绝大多数人都会使用到的服务，也经常会拿来做文件分享等等。而若今天我们需要提供一个文件给朋友，我们通常会上传并建立一个连结，但更机密的资料我们可能就需要先加密再上传，以保证服务商无法窃取或流出这个资料。然而加密之后，如果想要提供给另外一个人但不同密码，我们就需要建立许多份副本。代理重加密则将这个过程交给云端服务商，我们将一份加密的档案上传后，这些服务商透过重加密来产生对不同人的加密副本，就可以使我们避免重复加密。

　　在上面的流程中，我们可以分成三个角色：

• 　　加密方（Delegator）

• 　　解密方（Delegatee）

• 　　服务方（Proxy）

　　加密方会提供一个重加密密钥 rk 给服务方，服务方可以拿着加密方产生的密文 ca 和这把 rk 去重新加密成给别人的密文cb，这套流程就称作代理重加密。

　　代理重加密上有三个属性：

• 　　Directionality：如果服务方只能利用 rk 将 ca 转换成 cb，称为unidirectional，如果可以反过来则称为bidirectional。在代理重加密上，我们会希望他是unidirectional的，以避免解密方在使用他的密钥产生密文后，被服务方与加密方共谋而泄漏其中的明文。

• 　　Number of Hops：如果服务方对于 ca，在具备不同 rk 下（例如给Bob和Charlie的）可以分别产生对应的 ca 则称为multi-hop/multi-use，否则称为single-hop/single-use。

• 　　Interactivity：如果解密方的密钥不需参与重加密密钥的产生流程，则称为non-interactive，否则为interactive。

　　对于这三个属性，Umbral 是unidirectional、multi-hop、non-interactive 的，此外，他也引入了非互动式零知识证明来提供重加密的可验证性。

　　而Umbral 的另一个特点，就是他是门槛式（Threshold）的，在前面的的简介中只有一个Proxy，一旦这个Proxy 故障，那加密方与解密方就无法完成传递，因此透过Threshold 的设计，例如可以建立一个t of N 的代理重加密会话，只要N 个Proxy 有t 个正常运作就可以确保传递顺畅。

• 　　KEM/DEM Approach

　　Umbral 参考了美国国家标准协会提出的ECIES-KEM，用到了称为KEM/DEM Approach 的方法。KEM/DEM Approach 是一种混合加密方式，透过混合非对称与对称加密，来提供足够的安全性与加解密效率（非对称的加解密通常较为耗能）。KEM Key Encapsulate Mechanism 会先产生一个对称加密的密钥，再透过DEM Data Encapsulate Mechanism 则将传递的资料加密。

• 　　Shamir's Secret Sharing

　　Umbral中的Threshold特性透过Shamir's Secret Sharing的方式来达成。

• 　　Implementation

• 　　Umbral 如何运作

　　这边的Alice 是上面的Delegator，Bob 是Delegatee。首先Alice 会透过Encapsulate 去产生对称密钥K 和Capsule，这个Capsule 包含了让Bob 拿到K 的资讯。接着Alice 会对Bob 产生N 个kFrag 并发送给Proxy 们，Proxy 拿着Capsule 和kFrag 就可以产生cFrag 并发送给Bob，Bob 拿到t 个cFrag 就可以用自己的密钥重组并解密出K。

• 　　产生公开参数

　　首先会先产生一组Parameter：

　　其中G是一个order为质数q的循环群，g和U则是在G上的两个Generator。H2 ,H3 ,H4 则是作为随机数产生器哈希函数。KDF是Key Derivation Function，将用这个来产生对称密钥。q和KDF的输出长度是这个协议的安全性参数。

• 　　KeyGen

　　Alice会产生自己的非对称密钥对，接着产生提供给Proxy的kFrag。产生kFrag的步骤如下：

• 　　Alice会选择一个暂时的非对称密钥对，这里可能是考虑Alice和Bob会需要建立不只一次协议

• 　　将这个密钥对和Bob 做非互动式Diffie-Hellman 密钥交换，计算

• 　　依照Shamir's Secret Sharing 的方式，产生一个t-1 次的多项式f，其中秘密 f_0 = a cdot d^{-1} mod qf0 =a⋅d−1modq

• 　　计算共有的

• 　　产生N个kFrag：

　　5.1选取随机数 5.2计算Shamir's Secret Sharing上的点 5.3计算Re-encrypt Key 5.4计算Commitment 5.5组合成kFrag

　　在产生kFrag中，论文有提到，z1 ,z2 这两个是作为验证用的，在官方实作上是让Alice对kFrag加上pkA, pkB做签名来提供验证功能，由于这两个没有参与后面的运算这边选择略过。

• 　　产生Capsule

　　Alice会选择两个随机数r, u并包装成。对称密钥则透过得出，任何人收到Capsule都可以透过去检验E, V的正确性。而Alice可以拿Capsule和Private Key a去取回。

• 　　重加密与解密

　　Proxy拿到Capsule和kFrag后，就可以产生cFrag：。同时还会产生NIZK证明：

　　这可能是基于NuCypher设计Stake机制，透过这个NIZK，网路可以透过计算验证这个Proxy有没有正确的计算而无需取得

　　Bob 搜集足够的cFrag 后，就可以来做解密，步骤如下：

• 　　计算（即KeyGen 4.于Bob方的运算）和d=（即KeyGen 2.于Bob方的运算）。

• 　　对每个cFrag计算对应的si与

• 　　计算与

• 　　计算

　　这边用我自己比较好理解的方式去写，所以可能有点Bug。其中如果把 E 展开，可以得到，这里做的就是前面KeyGen 5.透过Shamir's Secret Sharing的还原。套回4.后可以看出他与产生Capsule一节中最后的相同，从而使Alice与Bob共享这个Key。

• 　　传递密文

　　最后再使用KEM/DEM Approach的方式来传递密文就可以达成完整的Re-Encryption。原先产生Capsule时，会同时产生密文，并传递)C=(Capsule,encData)，当Bob拿到时先解出K再message = SymDecrypt(encData)即可。