论文阅读---Coconut: Threshold Issuance Selective Disclosure Credentials with Applications to Distributed
Coconut: Threshold-based Issuance, Selective Disclosure of Credentials, with Potential Applications in Distributed Systems.
https://arxiv.org/pdf/1802.07344.pdf
Introduction
基于属性体系（Attribute-Based Credentials, ABC）的一种实现方式也被称为匿名认证方案、选择性透露认证机制或最小披露令牌技术是一种保障隐私信息安全的访问控制方法。该方案的核心要素是生成一个由认证机构V\mathcal{V}对用户属性aa进行digitally signed签名生成的凭证σ\sigma。通过一个标准化的身份认证流程U\mathcal{U}将从V\mathcal{V}处获得该凭证σ\sigma认证机构V\mathcal{V}将验证U\mathcal{U}确实拥有相应的属性aa
在ABC方案中提供盲颁发协议时, 该协议不仅允许U在aa上获得签名σ, 并且未将aa透露给V. 此外, 在显示(Show)协议阶段, U凭借其凭证向服务提供者P验证其属性符合访问策略φ.
ABC方案引入了一种无法建立关联性的机制：当用户展示凭证σ时（即该凭证σ无法被用于关联到其自身或其他任何形式的授权），尽管可能存在权威机构\mathcal{V}与服务提供方\mathcal{P}之间的勾结行为（其中仅能存在一次针对权威机构\mathcal{V}的授权授予该服务提供方\mathcal{P}）
通常采用 ABC 方案基于一个单一 authority V\mathcal{V} 的设计理念。该方案负责确保用户的属性信任问题。Coconut 方案则考虑了多个authority (V1,...,Vn)(\mathcal{V}_1,...,\mathcal{V}_n) 的协作机制。在发布协议中，用户 U\mathcal{U} 必须获取来自至少 tt 个 authorities 的部分凭证。这些凭证将被用于通过 show 协议验证用户所拥有的属性 aa 的凭证 σ\sigma。
采用 ABC 在区块链系统中实现访问控制时，则可考虑采用阈值颁发协议（Threshold issuance）。基于此，在不诚实的参与者数量低于设定门槛的情况下（即参与者中有少于阈值数量的人试图欺诈性行为），区块链系统能够确保其自身的完整性和安全性。
PS Signature Scheme
KeyGen(k=κ,q=Q). 通过调用setup函数生成参数集θ= (p,G,G,Gt,e,g,g)，其中p是一个安全参数κ对应的质数域参数集合；G和G分别是两个循环群；Gt是目标群；e为配对映射函数；g为生成元；g为另一个生成元。随后从Z_p^{q+1}中选取随机数对(x,y₁,…,y_q)，其中x为私钥的一部分；其余yi(i=1,…,q)为其他私钥组成部分。最终得到私钥sk= (θ,x,y₁,…,y_q)，并计算公钥pk= (θ,α,β₁,…,β_q)，其中α=g^x mod p；β_i=g^{yi} mod p（i=1,…,q）。
Sign(sk,m₁,…,mₚ) 转换 sk 为形式 (θ,x,y₁,…,yₚ)，其中 θ 表示参数集 {x} ∪ {yᵢ | i=0,…,p-2} ∪ {z}. 随机选取 r∈Zp，并令 h=gr. 计算 s = hx + Σ(yᵢ mᵢ)，并输出签名 σ = (h,s).
VfSig( pk , σ , m₁ , … , mₚ ) 是一个函数符号表示法。该算法通过以下步骤实现：首先将公钥转化为 θ ， α ， β₁ 到 βₚ 的集合；然后生成签名 h 和 s；最后通过计算方程 e(h , α ∏_{j=1}^p β_j^{m_j}) = e(s , \tilde{g}) 来验证其正确性。
PS 签名方案可实现盲化（即随机化），选取随机数 r' ← Z_p 并随后计算 σ' = (h^{r'}, s^{r'})。
The Conconut Scheme
Initialization. Initialization(1λ, q)\mathrm{Initialization}(1^\lambda, q) 必须在一个可信实体内执行。其中, 1λ是一个安全参数, 表示系统的信任级别; q 是参与签名的消息数量, 决定了系统的安全性水平.
- 参数初始化：给定参数 k 和安全参数 λ，
- 首先从椭圆曲线群 𝔾 中随机选取点 P，
- 然后从扩展的椭圆曲线群 𝔾~ 中随机选取点 Q，
- 接着从子群 𝔾_t 中随机选取点 R，
- 并从乘法群 𝔾_m 中随机选取标量 s，
- 最后从质数子群 𝔽_p 中随机选取标量 t。
KeyGen. 该算法TTPKeyGen(params, t, n, q)\mathrm{TTPKeyGen}(params,t,n,q)由可信赖实体构成。其中params由Setup模块生成；tt被定义为门限阈值；nn代表了参与者总数；qq表示待签名消息的数量。
- 选取一个 (q+1)(q+1) 次多项式 f(v,w_1,\dots,w_q)\in\mathbb{Z}_p^{q+}[x] ，其中多项式的阶为 t-2 ，且所有系数均来自 \mathbb{Z}_p 域。
- 设定初始值向量 y=(y_1,\dots,y_q)\in\mathbb{Z}_p^q 和 x=v(0)\in\mathbb{Z}_p。
- 对于每个权威 V_i（其中 i=1,\dots,n），执行以下操作：
- 赋值其私钥 s_{k_i} = (x_i,y_{i, \dots,y_{i,q}}) ，其中每一项均来源于对应的域。
- 确保每个私钥参数满足协议的安全性要求。
- 对于每个权威 V_i（其中 i= ,\dots,n），计算其验证密钥：
- 即通过指定生成元 \tilde{g} 的幂次运算来构造完整的验证密钥集合。
- 计算全局验证密钥：
- 将所有权威的验证密钥按特定顺序组合形成完整的系统验证密钥集合。
- 输出结果：
- 包含公共参数集 (pk,\ sk_{ },pk_{ },\dots,\ sk_n,pk_n) 的元组。
Protocol for Issuing a Signature.
-
生成一个 Elgamal 密钥对 (d,γ)(d,\gamma)。选择 d←Zpd\leftarrow Z_p 并计算 γ←gd\gamma\leftarrow g^d
-
选择随机数 o←Zpo\leftarrow Z_p 并计算承诺 cm←go∏j=1qhjmjc_m\leftarrow go\prod_{j=1}{q}h_j^{m_j}
-
计算 h←H(cm)h\leftarrow H(c_m)，hh 是用于计算签名的生成元
-
计算每个消息的 Elgmal 加密。对于 j=1,...,qj=1,...,q，选择随机数 kj←Zpk_j\leftarrow Z_p 并设置 cj=(aj,bj)=(gkj,γkjhmj)c_j=(a_j,b_j)=(g{k_j},\gamma{k_j}h^{m_j})
-
计算通过 Fiat-Shamir 启发式的 πs\pi_s 的 ZK 参数
πs=NIZK{(d,m1,...,mq,o,k1,...,kq):γ=gd∧cm=go∏j=1qhjmj∧{aj=gkj∧bj=γkjhmj}∀j∈[1,...,q]∧ϕ(m1,...,mq)=1}\pi_s=NIZK{(d,m_1,...,m_q,o,k_1,...,k_q):\gamma=g^d\wedge c_m=go\prod_{j=1}{q}h_j{m_j}\wedge{a_j=g{k_j}\wedge b_j=\gamma{k_j}h{m_j}}_{\forall j\in[1,...,q]}\wedge \phi(m_1,...,m_q)=1} -
输出 (d,Λ=(γ,cm,c1,...,cq,h,πs),ϕ)(d,\Lambda=(\gamma,c_m,c_1,...,c_q,h,\pi_s),\phi)
用户通过网络传输 Λ 和 ϕ 至 tt 个 authorities。每个 authority Vi 调用盲签名算法 BlindSign(params, ski, Λ, ϕ)，其中 params 是 Setup 程序生成的关键参数集合；Λ 是 PrepareBlindSign 函数输出的第二个参数；ϕ 则是用于验证消息陈述性的签名值。
- 将 Λ 转换为目标变量组 (γ, cm, c₁,…, cq, h, πs)
- 计算 h' ← H(cm)
- 通过使用参数 ϕ 和目标变量组 (γ, cm, c₁,…, cq, h) 来验证 πs
- 对于每个 j 属于 1 到 q 的范围（j = 1,…, q），将变量 cj 转换为目标变量组中的对应分量 (aj,bj)
- 计算生成元的乘积及其指数形式：∏(aⱼ^{yⱼ}, h^x ∏(bⱼ^{yⱼ}))
- 输出最终的盲签名份额 σ̃i 等于计算得到的两个部分组成的有序对 (h', ∏(aⱼ^{yⱼ}, h^x ∏(bⱼ^{yⱼ}) ))
每个权威ViV_i向用户发送σi\tilde{\sigma}_i。当接收到所有签名份额时，用户将通过调用UnBlind(params,d,Λ,σi,pki,m1,…,mq)\mathrm{Unblind}(params,d,\Lambda,\tilde{\sigma}_i,pk_i,m_1,…,m_q)}来解密这些签名片段。其中dd是采用Elgamal算法生成的私钥，并且σ~i\tilde{\sigma}_i是通过BlindSign算法产生的签名片段。这些消息内容包括(m_1,…, m_q)。
将 Λ 转化为由 γ、c_m、c_1 至 c_q、h 和 π_s 组成。
σ~i 被重构成 (h,\tilde{c}) 和 c~\tilde{c} 组成的两个部分。
计算 σi 时使用公式 σ_i = (h, s_i) ← (h, \tilde{b}(\tilde{a})^{-d}).
pkpk_i 被重新定义为由 α_i 和 β_{i,j} 组成的部分，并对签名份额进行验证。
输出最终的签名份额 σ_i。
e(h, g\xi g_yi ¹ᵐ¹ ··· · · · · · · · · g_yi qmq ) = e( hˣ ∏{j=1到q}{( (gd_k j h_m j ) y j ( k j y j )^{-d } ), \tilde{g}}
)
= e( hˣ ∏{j=1到q}{( (gd_k j h_m j ) y j ( k j y j )^{-d } ), \tilde{g}}
)
令 S∈[1,n] 是 TTP 负责分配的一组 authorities 索引集合。通过 Aggregation-Credential 函数 \mathrm{AggCred}(params,<\sigma_i>_{i\in \mathbb{S}},pk,m_1,...,m_q)，用户能够生成多个盲签名 shares。其中 <σi>i∈S 是这些 blind signature shares 的集合（共若干份），pk 是 TTPKeyGen 输出的结果包含一个验证密钥，并且 (m1,...,mq) 是需要被签名的一组待签名的消息集。
-
给定任意的元素 i 属于集合 S，则将 σ_i 转换为有序对 (h, s_i)。
-
求取在点 0 处的拉格朗日插值多项式的值；其中 li 等于第一个乘积除以第二个乘积再取模 p。
其中，
li = [∏{ j ∈ SS, j ≠ s } ( - j ) ] / [ ∏{ j ∈ SS, j ≠ i } ( i - j ) ]^{-1} mod p -
通过计算得到签名 σ = (h, s) ← (h, ∏i∈S s_i^l_i)
-
将 pkpk 转换为 (α, β₁,…, β_q)(\alpha,\beta_1,…,\beta_q) 并对所得到的结果进行验证，则满足 e(h, α∏j=1^q β_j^m_j) = e(s,g~)
-
输出结果为 σ
Protocol for Proving Signature Possession.
-
转化 σ\sigma 为 (h,s)(h,s)
-
转化 pkpk 为 (α,β1,...,βq)(\alpha,\beta_1,...,\beta_q)
-
选择随机数 r←Zq和r′←Zpr\leftarrow \mathbb{Z}_q 和 r'\leftarrow \mathbb{Z}_p
-
计算 h′←hr′h'\leftarrow h^{r'} 和 s′←sr′s'\leftarrow s^{r'}
-
计算 κ←α∏j=1qβjmjg~r\kappa\leftarrow \alpha \prod_{j=1}^q \beta_j{m_j}\tilde{g}r
-
计算 v←(h′)rv\leftarrow (h')^r
-
计算 πv\pi_v 的 ZK 参数
πv=NIZK{(m1,...,mq,r):κ=α∏j=1qβjmjg~r∧v=(h′)r∧ϕ′(m1,...,mq)=1}\pi_v=NIZK{(m_1,...,m_q,r):\kappa=\alpha\prod_{j=1}q\beta_j{m_j}\tilde{g}^r\wedge v=(h')^r\wedge \phi'(m_1,...,m_q)=1} -
设置 Θ=(κ,v,h′,s′,πv)\Theta=(\kappa,v,h',s',\pi_v)
-
输出 (Θ,ϕ′)(\Theta,\phi')
客户端向Provider发送包含参数(Θ,ϕ′)的信息包。Provider执行VerifyCred算法（即\mathrm{VerifyCred}）并接收参数包括params、pk、以及θ和φ'。
- 表示 Θ 为 (\kappa,v,h',s',\pi_v)
- 基于 ϕ', params,pk,h',s' 和 κ 的基础上，并结合参数 v 的存在性进行验证 \pi_v
- 若 h'=1，则返回 false
- 当且仅当 e(h', κ) 等于 e(s'v,\tilde{g}) 时，则认为验证成功