ICP(Internet Computer Protocol)由多个子网(subnet)构成, 每个子网上是一个区块链网络。为了实现ICP子网节点动态管理以及子网与子网之间消息认证,Jens Groth提出一种基于BLS签名的非交互分布式密钥生成及密钥重分享协议,主要实现以下功能:
- 采用BLS签名,公钥加密和零知识证明技术,实现公开可验证的秘密分享协议;
- 能够在保证子网公钥不变的情况下,实现密钥的再分享,可以有效解决子网中节点动态加入或退出的密钥管理问题。
Shair 密钥分享
密钥分享主要是将 秘密 创建多个份额: , 其中任w意 个可以构建 秘密 , 而 不会泄露任何 的信息。
Shamir 秘密分享: 随机选取 次多项式 , 其中 , . 任意 个点可以构造多项式 , 得到 。
可以采用Lagrange 插值描述Shamir 秘密分享: 给定索引集合 , 对于 , 定义Lagrange多项式:
所有的Lagrange多项式次数都是 , 并满足 和 . 因此对于 上的点, 可以得到:
对于秘密分享 , 可以构建 为:
因此 密钥分享方案为:
: 给定 , 设定 , 选择 , 定义, 得到:
: 给定 中的索引 和分享 , 返回:
为了验证分享的正确性,Feldman提出了可验证的秘密分享(VSS), 需要公开参数: , 对于每个分享 , 可以验证其正确性:
但是这种情况下只有接收者可以验证,需要一个交互过程。可以构造公开可验证的秘密分享(PVSS)方案, 使任何人都可以开公验证。
Resharing
对于密钥为 的 Shamir秘密分享方案可以转化为 的Shamir 秘密分享方案, 保持不变。对于分享, 过程如下:
: 返回 .
: 返回
上式成立的条件在于Lagrange插值的线性性质,即对于 和 , 可以计算下式:
BLS 签名
: 选择双线性对, Hash函数: .
:选择 , 设置 , 返回
: 计算签名
: 若, 验证:
BLS签名满足惟一性。
门限签名
门限签名主要指对于参与者人数大于或等于 时,可以构建一个有效的签名。分布式门限签名方案主要包括几个算法:
: 确定性算法,用于验证阈值 , 验证密钥, 验证密钥share: 是否有效。
: 确定性算法,用以验证私钥share 和验证公钥share 是否有效。
: 确定性或随机的算法,利用私钥share 对 消息 产生签名share:
: 确定性算法,对于验证公钥share 对 和 签名share 进行验证。
: 确定性算法,对于 个签名share: , 将其组合成一个签名:
: 确定性算法,给定验证公钥, 消息 和 签名 , 验证签名是否有效。
BLS门限签名
: 设置 阶为 的群 , 双线性对函数 , 分别为的生成元,Hash函数:
: 验证 , . 设定 , , 对于,验证:
若验证通过,返回 , 否则返回 .
: 若 , 则返回 , 否则返回
: 计算
: 若, 验证:
: 解析 为多个索引 ,, 得到聚合签名:
: 验证, 验证:
前向安全的公钥加密方案
本节将介绍CCA安全的多接收者的公钥加密方案,基于双线性对构造,具有前向安全性。
二叉树加密
设二叉树高度为 , 每个叶子节为一个加密的密文,每个节点都有一个对应的私钥,拥有根节点 私钥可以解密所有的密文,拥有中间节点可以解密其对应子树的密文。
BTE(Binary Tree Encryption) 加密方案主要有以下几个算法:
: 参数包括消息空间 , 二叉树高度 , 节点的路径为:, 其中 . 即根节点为空路径: , 叶子节点
: 随机的密钥生成算法,生成二叉树根节点的公钥和私钥。
: 确定性算法,以验证公钥的有效性。
: 随机的更新算法,给定节点的解密密钥和 , 得到节点 的解密密钥,其中
: 随机的加密算法,给定公钥,加密的消息,和叶子节点,返回加密的密文。
: 确定性的算法,
方案构造
: 对于阶为 的双线性对群: , 消息空间, 消息空间足够小,可通过穷举攻击获取,群元素 , 树的高度为
: 选择 , 计算 . 选择 , 则 , 返回:
: 若 , 返加, 否则返回
: 给定
, 选择 , 返回:
: 给定 , 选择 , 返回:
: 解析
对于 , 判定
计算:
搜索 , 使得
多接收者二叉树加密
发送者有多个密文给多个接收者,可以直接用单接收者的二叉树加密方案,但是效率比较低,通过复用随机数,可以使加密方案更加高效,多接收者的二叉树加密方案主要有以下算法:
: 指消息密文空间 , 高度为 的二叉树有 个叶子节点,节点的路径为, 对于叶子节点
: 随机的密钥生成算法,生成根节点公钥和私钥;
: 确定性算法,验证公钥的有效性;
: 随机的更新算法, 给定节点 的解密私钥, 得到节点 的解密私钥。
: 随机的加密方案,给定公钥和消息,得到相应节点的密文。
: 确定性解密算法,给定密文,索引 , 和解密密钥,得到
方案构造
构造基本上和单接收者二叉树加密方案类似,但使用相同的随机数.
: 对于阶为 的双线性对群: , 消息空间, 消息空间足够小,可通过穷举攻击获取,群元素 , 树的高度为
: 选择 , 计算 . 生成关于 的离散对数零知识证明 , 令. 选择 , 则 , 得到:
: 若 , 返加, 否则返回
: 给定
, 选择 , 返回:
: 给定 , 选择 , 返回:
: 解析
对于 , 判定
对于 , 计算:
搜索 , 使得
扩展明文空间
对于 , 难以计算其离散对数 . 可以采用chunked encryption
实现,即将 写作 , 其中 , 限定 足够小,可以穷举搜索出来。对于消息空间为的多接收者二叉树加密方案描述如下:
: 设定正整数 , , 使得 , 其中
: 得到
: 返回
: 得到
: 给定 , 分别将其分成小块 , 因此 . 对于 , 设定 , 返回
: 解析 , 对于 , 计算 , 最终得到
注: 采用 Baby-step Giant-ste算法可以加快搜索速度。
方案造构
: 选择 , 计算 和 , 其中:
-
: 首先解析 为 , . 然后将 分成小块, , 其中 .
返回值为:, 其中:
: 对于, 返回 , 其中:
返回值为:
: 解析 , , . 对于, 验证:
对于, 解析 。
对于 , 计算:
搜索 , 使得. 最终得到 消息
前向安全的CCA公钥加密方案
: 给定消息空间 和 最大周期数 .
: 随机的密钥生成算法, 生成一个公钥和周期为 的私钥。
: 确定性算法,验证 的准确性。
: 随机的密钥更新算法,给定 周期 的 解密密钥,返回周期为 的解密密钥。若 , 返回 .
: 随机的加密算法,给定 个公钥,相应的消息及周期,返回一个密文。
: 确定性解密算法,给定解密密钥 , 索引为 , 周期为 , 返回明文 . 若
方案构造
本部分将构造一个多接收者的CCA安全的加密方案,明文空间为 ,
: 明文消息空间为 , 最大周期数为, hash函数:
初始设置包括群元素, 其中 .
: 选择 , 计算 , 生成证明 , 设定公钥为, 选择随机数 , , 令 , 返回
: 解析公钥为 , 若 , 且 验证通过,返回 , 否则
: 若 . 解析 , , 其中 是涵盖 所有叶子节点的最小子集, 是涵盖 所有叶子节点的最小子集,对于所有的 得到子密钥 ,得到:
: 分析 的二进制形式,选择 , 计算:
计算
返回加密的密文:
: 解析 , , 计算, 假定, 得到 , 返回
非交互式零知识证明
离散对数证明
: 设定群, 素数阶为 , 生成元为 . Oracle 采用Hash函数 实现。
:
: 证明 的离散对数
: , 使得
:
选择 , 计算 ;
计算
计算
生成的证明为:
:
验证 , 域元素
计算
若 验证通过,则返回 , 否则
密钥分享证明
: 设定群, 阶为, 双线性对: , 生成元为:. 群元素 . Oracle 采用 Hash函数 .
: ,
$R=g_1^r, C_1 = y_1^rg_1^{s_1},\cdots, C_n = y_n^r\cdot g_1^{s_n}$
: 实例中离散对数满足: 满足下述关系:
: 对于 满足 , 其中
:
计算
生成随机数: , 计算:
计算
-
计算:
$z_r = rx' + \rho\ mod\ p$ , $z_a = x'\sum_{i=1}^n s_i x^i + \alpha\ mod\ p $
生成的证明为:
:
验证 , 域元素
计算
验证:
和
若验证通过返回 , 否则返回
Chunking 零知识证明
: 指定参数为 阶为, 生成元 的群, 参数包括 安全参数 , 正整数 , 使得
: 中的群元素有:
: 实例的离散对数满足 , 使得 , 使得:
: 离散对数 满足约束
:
选择
计算
查询 , 解析输出为:
计算:
检查其在 范围内。
计算:
查询 , 得到
计算
生成的证明为:
:
验证实例属于 , 解析
验证
计算 , 查询 得到
-
验证:
和
前向安全的分布式密钥生成和密钥重分享协议
: 参数索引范围为 , 最大周期数为:
: 随机化的密钥生成算法,得到一个公钥,和一个私钥, 初始周期为
: 确定性算法,验证公钥的有效性。
: 对于周期为 的解密密钥,升级到周期 .
: 随机的 dealing
算法, 给定门限值,和多个公钥 , 生成给定周期的 dealing
. 私钥sk
为可选的输入。
: 确定性 dealing
验证算法,若dealing
有效,则返回, 否则返回 , 为可选的验证公钥。
: 确定性算法,给定索引 , 不同的索 , 返回验证公钥, 秘密分享的验证公钥
: 确定性算法,给定门限 和 验证密钥,若有效,则返加
: 确定性算法, 给定解密密钥, 大小于 的集合 , 周期 的 : , 返回 的私钥。
: 确定性算法, 验证 分享密钥的有效性。
本具体方案构造可参考论文。