群签名、环签名、盲签名

群签名

定义

群签名方案是算法组

Π

G

S

=

(

G

e

n

,

S

i

g

n

,

V

e

r

,

O

p

e

n

)

Pi_{GS}=(Gen, Sign, Ver, Open)

ΠGS=(Gen,Sign,Ver,Open)

  1. G

    e

    n

    (

    1

    λ

    ,

    n

    )

    Gen(1^lambda,n)

    Gen(1λ,n):密钥生成算法,

    n

    n

    n 为群成员数,输出

    • g

      v

      k

      gvk

      gvk:群公钥,用于验签

    • g

      m

      s

      k

      gmsk

      gmsk:主私钥,由管理员持有,用于追踪成员身份

    • g

      s

      k

      =

      (

      g

      s

      k

      [

      1

      ]

      ,


      ,

      g

      s

      k

      [

      n

      ]

      )

      gsk=(gsk[1],cdots,gsk[n])

      gsk=(gsk[1],,gsk[n]):成员私钥,用于签名

  2. S

    i

    g

    n

    (

    g

    s

    k

    [

    i

    ]

    ,

    m

    )

    Sign(gsk[i],m)

    Sign(gsk[i],m):签名算法,任意成员可以独立签署消息

    m

    m

    m,输出签名

    σ

    sigma

    σ

  3. V

    e

    r

    (

    g

    v

    k

    ,

    m

    ,

    σ

    )

    Ver(gvk,m,sigma)

    Ver(gvk,m,σ):验签算法,根据验签通过与否,输出

    0

    /

    1

    0/1

    0/1

  4. O

    p

    e

    n

    (

    g

    m

    s

    k

    ,

    m

    ,

    σ

    )

    Open(gmsk,m,sigma)

    Open(gmsk,m,σ):公开算法,如果签名正确,则输出签名者身份

    i

    i

    i,否则输出

    perp

我们说

σ

sigma

σ

m

m

m 的正确签名,如果存在

i

[

1

,

n

]

i in [1,n]

i[1,n] 以及随机带

r

r

r,使得

σ

=

S

i

g

n

(

g

s

k

[

i

]

,

m

;

r

)

sigma=Sign(gsk[i],m;r)

σ=Sign(gsk[i],m;r) 成立。

安全性

群签名的安全性只需两条:完全匿名性、完全可追踪性。其他奇奇怪怪的安全性要求都可以由这两条推出。

  • 匿名性实验

在这里插入图片描述

定义敌手的优势为:

A

d

v

Π

,

A

a

n

o

n

(

λ

,

n

)

=

2

P

r

[

E

x

p

t

Π

,

A

a

n

o

n

(

1

λ

,

n

,

U

1

)

=

1

]

1

2

=

P

r

[

E

x

p

t

Π

,

A

a

n

o

n

(

1

λ

,

n

,

1

)

=

1

]

P

r

[

E

x

p

t

Π

,

A

a

n

o

n

(

1

λ

,

n

,

0

)

=

0

]

begin{aligned} Adv_{Pi,A}^{anon}(lambda,n) &= 2left| Prleft[Expt_{Pi,A}^{anon}(1^lambda,n,U_1)=1right] - frac{1}{2} right|\ &= left| Prleft[Expt_{Pi,A}^{anon}(1^lambda,n,1)=1right] - Prleft[Expt_{Pi,A}^{anon}(1^lambda,n,0)=0right] right| end{aligned}

AdvΠ,Aanon(λ,n)=2Pr[ExptΠ,Aanon(1λ,n,U1)=1]21=Pr[ExptΠ,Aanon(1λ,n,1)=1]Pr[ExptΠ,Aanon(1λ,n,0)=0]

我们说

Π

G

S

Pi_{GS}

ΠGS完全匿名的,如果对于任意 PPT 敌手

A

A

A,优势

A

d

v

Π

,

A

a

n

o

n

(

λ

,

n

)

Adv_{Pi,A}^{anon}(lambda,n)

AdvΠ,Aanon(λ,n) 是可忽略的。

  • 可追踪性实验

在这里插入图片描述

定义敌手的优势为:

A

d

v

Π

,

A

t

r

a

c

e

(

λ

,

n

)

=

P

r

[

E

x

p

t

Π

,

A

t

r

a

c

e

(

1

λ

,

n

)

=

1

]

Adv_{Pi,A}^{trace}(lambda,n) = Prleft[Expt_{Pi,A}^{trace}(1^lambda,n)=1right]

AdvΠ,Atrace(λ,n)=Pr[ExptΠ,Atrace(1λ,n)=1]

我们说

Π

G

S

Pi_{GS}

ΠGS完全可追踪的,如果对于任意 PPT 敌手

A

A

A,优势

A

d

v

Π

,

A

t

r

a

c

e

(

λ

,

n

)

Adv_{Pi,A}^{trace}(lambda,n)

AdvΠ,Atrace(λ,n) 是可忽略的。

构造

密码学部件:

  • 一般签名算法

    Π

    s

    =

    (

    G

    e

    n

    s

    ,

    S

    i

    g

    n

    ,

    V

    e

    r

    )

    Pi_s = (Gen_s, Sign, Ver)

    Πs=(Gens,Sign,Ver)

  • 公钥加密方案

    Π

    e

    =

    (

    G

    e

    n

    e

    ,

    E

    n

    c

    ,

    D

    e

    c

    )

    Pi_e = (Gen_e, Enc, Dec)

    Πe=(Gene,Enc,Dec)

  • 非交互零知识证明

    (

    P

    ,

    V

    )

    (P,V)

    (P,V)

在这里插入图片描述

  1. P

    0

    P_0

    P0 是组管理员。为了让组内的每个成员都可以签名并验证,可以简单地执行

    n

    n

    n

    G

    e

    n

    s

    Gen_s

    Gens,为各个成员生成私钥公钥,将

    {

    v

    k

    i

    }

    i

    I

    {vk_i}_{i in I}

    {vki}iI 作为群公钥。但是这会泄露成员身份。

  2. 我们不再公开公钥,而是在签名时附加上一个证明

    π

    pi

    π,使得验签者相信确实存在一个群成员

    i

    i

    i 签署了消息。但这有个问题,就是没有证明

    v

    k

    i

    vk_i

    vki 是属于这个组的。

  3. P

    0

    P_0

    P0 再为每个成员的公钥添加上证书

    c

    e

    r

    t

    i

    cert_i

    certi,同时要证明

    v

    k

    i

    vk_i

    vki 确实是组成员的公钥。但是这必须公布

    c

    e

    r

    t

    i

    cert_i

    certi,又把成员身份泄露了。

  4. 因此我们把证书加密后再发布,签名者对于

    m

    m

    m 输出

    (

    C

    ,

    π

    )

    (C,pi)

    (C,π),验签者验证

    π

    pi

    π 确实是对

    m

    ,

    C

    m,C

    m,C 之间关系的证明。

环签名

定义

环签名方案是算法组

Π

R

S

=

(

G

e

n

,

S

i

g

n

,

V

e

r

)

Pi_{RS}=(Gen, Sign, Ver)

ΠRS=(Gen,Sign,Ver)

  1. G

    e

    n

    (

    1

    λ

    )

    Gen(1^lambda)

    Gen(1λ):密钥生成算法,输出

    (

    s

    k

    ,

    v

    k

    )

    (sk,vk)

    (sk,vk)

  2. S

    i

    g

    n

    (

    s

    k

    ,

    R

    ,

    m

    )

    Sign(sk,R,m)

    Sign(sk,R,m):签名算法,验签密钥集合

    R

    =

    (

    v

    k

    i

    ,


    ,

    v

    k

    n

    )

    R=(vk_i,cdots,vk_n)

    R=(vki,,vkn)(环),任何人可以独立签署消息

    m

    m

    m,输出签名

    σ

    sigma

    σ

  3. V

    e

    r

    (

    R

    ,

    m

    ,

    σ

    )

    Ver(R,m,sigma)

    Ver(R,m,σ):验签算法,根据验签通过与否,输出

    0

    /

    1

    0/1

    0/1

若验签通过,那么说明签名是由

R

R

R 中的某个

v

k

i

vk_i

vki 对应的

s

k

i

sk_i

ski 所签署的。与群签名相比,环签名是去中心化的,并且参与者的加入退出很容易。缺点是没法追踪恶意的签名者。

安全性

  • 无内部攻击的不可伪造性实验

在这里插入图片描述

  • 内部攻击的不可伪造性实验

在这里插入图片描述

定义敌手的优势为:

A

d

v

Π

,

F

E

U

F

C

M

A

(

λ

)

=

P

r

[

E

x

p

t

Π

,

F

e

u

f

c

o

r

r

u

p

t

c

m

a

(

1

λ

)

=

1

]

Adv_{Pi,F}^{EUF-CMA}(lambda) = Prleft[ Expt_{Pi,F}^{euf-corrupt-cma}(1^lambda)=1 right]

AdvΠ,FEUFCMA(λ)=Pr[ExptΠ,Feufcorruptcma(1λ)=1]

我们说

Π

R

S

Pi_{RS}

ΠRS 是**(内部攻击下)不可伪造的**,如果对于任意 PPT 敌手

F

F

F,优势

A

d

v

Π

,

F

E

U

F

C

M

A

(

λ

)

Adv_{Pi,F}^{EUF-CMA}(lambda)

AdvΠ,FEUFCMA(λ) 是可忽略的。

  • 基本匿名性实验

在这里插入图片描述

定义敌手的优势为:

A

d

v

Π

,

A

a

n

o

n

(

λ

)

=

2

P

r

[

E

x

p

t

Π

,

A

a

n

o

n

(

1

λ

,

U

1

)

=

1

]

1

2

=

P

r

[

E

x

p

t

Π

,

A

a

n

o

n

(

1

λ

,

1

)

=

1

]

P

r

[

E

x

p

t

Π

,

A

a

n

o

n

(

1

λ

,

0

)

=

0

]

begin{aligned} Adv_{Pi,A}^{anon}(lambda) &= 2left| Prleft[Expt_{Pi,A}^{anon}(1^lambda,U_1)=1right] - frac{1}{2} right|\ &= left| Prleft[Expt_{Pi,A}^{anon}(1^lambda,1)=1right] - Prleft[Expt_{Pi,A}^{anon}(1^lambda,0)=0right] right| end{aligned}

AdvΠ,Aanon(λ)=2Pr[ExptΠ,Aanon(1λ,U1)=1]21=Pr[ExptΠ,Aanon(1λ,1)=1]Pr[ExptΠ,Aanon(1λ,0)=0]

我们说

Π

G

S

Pi_{GS}

ΠGS基本匿名的,如果对于任意 PPT 敌手

A

A

A,优势

A

d

v

Π

,

A

a

n

o

n

(

λ

)

Adv_{Pi,A}^{anon}(lambda)

AdvΠ,Aanon(λ) 是可忽略的。

  • (有内部攻击的)匿名性实验

在这里插入图片描述

定义敌手的优势为:

A

d

v

Π

,

A

a

n

o

n

c

o

r

r

u

p

t

(

λ

)

=

2

P

r

[

E

x

p

t

Π

,

A

a

n

o

n

c

o

r

r

u

p

t

(

1

λ

,

U

1

)

=

1

]

1

2

=

P

r

[

E

x

p

t

Π

,

A

a

n

o

n

c

o

r

r

u

p

t

(

1

λ

,

1

)

=

1

]

P

r

[

E

x

p

t

Π

,

A

a

n

o

n

c

o

r

r

u

p

t

(

1

λ

,

0

)

=

0

]

begin{aligned} Adv_{Pi,A}^{anon-corrupt}(lambda) &= 2left| Prleft[Expt_{Pi,A}^{anon-corrupt}(1^lambda,U_1)=1right] - frac{1}{2} right|\ &= left| Prleft[Expt_{Pi,A}^{anon-corrupt}(1^lambda,1)=1right] - Prleft[Expt_{Pi,A}^{anon-corrupt}(1^lambda,0)=0right] right| end{aligned}

AdvΠ,Aanoncorrupt(λ)=2Pr[ExptΠ,Aanoncorrupt(1λ,U1)=1]21=Pr[ExptΠ,Aanoncorrupt(1λ,1)=1]Pr[ExptΠ,Aanoncorrupt(1λ,0)=0]

我们说

Π

G

S

Pi_{GS}

ΠGS匿名的,如果对于任意 PPT 敌手

A

A

A,优势

A

d

v

Π

,

A

a

n

o

n

c

o

r

r

u

p

t

(

λ

)

Adv_{Pi,A}^{anon-corrupt}(lambda)

AdvΠ,Aanoncorrupt(λ) 是可忽略的。

构造

方法一:类似群签名,使用 NIZKP 将一般签名方案转化为环签名方案。

方法二:真的构成一个环 [RST01],使用 trapdoor OWP 群成员可以在环的某个位置上打开环,然后再关闭环。

{

H

s

}

{H_s}

{Hs} 是 CRHF,

{

F

k

,

F

k

1

}

{F_k,F_k^{-1}}

{Fk,Fk1} 是 trapdoor OWP,对应的公私钥为

(

p

k

,

s

k

)

(pk,sk)

(pk,sk)

Π

=

(

G

e

n

,

E

n

c

,

D

e

c

)

Pi=(Gen, Enc, Dec)

Π=(Gen,Enc,Dec) 是对称加密算法,签名算法如下:

  1. 选取

    R

    =

    (

    p

    k

    1

    ,


    ,

    p

    k

    n

    )

    R = (pk_1,cdots,pk_n)

    R=(pk1,,pkn),包含自己的公钥

    p

    k

    j

    pk_j

    pkj

  2. 计算

    r

    =

    H

    s

    (

    m

    )

    r=H_s(m)

    r=Hs(m),生成

    k

    G

    e

    n

    (

    1

    λ

    ;

    r

    )

    k leftarrow Gen(1^lambda;r)

    kGen(1λ;r)

  3. 随机选取

    x

    1

    ,


    ,

    x

    j

    1

    ,

    x

    j

    +

    1

    ,


    ,

    x

    n

    x_1,cdots,x_{j-1},x_{j+1},cdots,x_n

    x1,,xj1,xj+1,,xn,计算

    y

    i

    =

    F

    (

    p

    k

    i

    ,

    x

    i

    )

    ,

    j

    i

    y_i = F(pk_i, x_i), j neq i

    yi=F(pki,xi),j=i

  4. 随机选取

    t

    j

    =

    v

    t_j'=v

    tj=v,计算

    t

    j

    +

    1

    =

    E

    n

    c

    (

    k

    ,

    t

    j

    )

    t_{j+1}=Enc(k,t_j')

    tj+1=Enc(k,tj),然后依次计算

    t

    i

    +

    1

    =

    E

    n

    c

    (

    k

    ,

    t

    i

    y

    i

    )

    ,

    i

    =

    j

    +

    1

    ,


    ,

    n

    ,

    1

    ,


    ,

    j

    1

    t_{i+1} = Enc(k, t_i oplus y_i), i=j+1,cdots,n,1,cdots,j-1

    ti+1=Enc(k,tiyi),i=j+1,,n,1,,j1(令

    n

    +

    1

    1

    n+1 equiv 1

    n+11)得到

    t

    j

    t_j

    tj,接着求逆

    x

    j

    =

    F

    1

    (

    s

    k

    j

    ,

    t

    j

    t

    j

    )

    x_j = F^{-1}(sk_j, t_j oplus t_j')

    xj=F1(skj,tjtj)

  5. 输出

    (

    R

    ,

    t

    n

    ,

    x

    1

    ,


    ,

    x

    n

    )

    (R, t_n, x_1, cdots, x_n)

    (R,tn,x1,,xn) 作为消息

    m

    m

    m 的签名。

盲签名

定义

盲签名方案是算法组

Π

B

S

=

(

G

e

n

,

<

S

,

U

>

,

V

e

r

)

Pi_{BS}=(Gen, <S,U>, Ver)

ΠBS=(Gen,<S,U>,Ver),其中

<

S

,

U

>

<S,U>

<S,U> 是签名者和用户之间的交互协议,

  1. G

    e

    n

    (

    1

    λ

    )

    Gen(1^lambda)

    Gen(1λ):密钥生成算法,输出

    (

    s

    k

    ,

    v

    k

    )

    (sk,vk)

    (sk,vk)

  2. <

    S

    (

    s

    k

    )

    ,

    U

    (

    v

    k

    ,

    m

    )

    >

    <S(sk),U(vk,m)>

    <S(sk),U(vk,m)>:签名交互协议,签名者输出

    O

    u

    t

    =

    O

    K

    /

    F

    a

    i

    l

    Out=OK/Fail

    Out=OK/Fail(签名是否成功),用户输出

    m

    m

    m 的签名值

    σ

    sigma

    σ

  3. V

    e

    r

    (

    v

    k

    ,

    m

    ,

    σ

    )

    Ver(vk,m,sigma)

    Ver(vk,m,σ):验签算法,根据验签通过与否,输出

    0

    /

    1

    0/1

    0/1

安全性

  • 不可伪造性实验:因为挑战者

    C

    h

    Ch

    Ch 看不到

    m

    m

    m,因此不能像一般签名算法那样设置一个签名历史记录

    Q

    s

    Q_s

    Qs 使得

    m

    ∉

    Q

    s

    m^* notin Q_s

    mQs,而是需要敌手

    F

    F

    F 询问

    k

    k

    k 次签名后,应当输出至少

    k

    +

    1

    k+1

    k+1 个不同消息的合法签名。

在这里插入图片描述

定义敌手的优势为:

A

d

v

Π

,

F

E

U

F

C

M

A

(

λ

)

=

P

r

[

E

x

p

t

Π

,

F

e

u

f

c

m

a

(

1

λ

)

=

1

]

Adv_{Pi,F}^{EUF-CMA}(lambda) = Prleft[ Expt_{Pi,F}^{euf-cma}(1^lambda)=1 right]

AdvΠ,FEUFCMA(λ)=Pr[ExptΠ,Feufcma(1λ)=1]

我们说

Π

B

S

Pi_{BS}

ΠBS 是**(内部攻击下)不可伪造的**,如果对于任意 PPT 敌手

F

F

F,优势

A

d

v

Π

,

F

E

U

F

C

M

A

(

λ

)

Adv_{Pi,F}^{EUF-CMA}(lambda)

AdvΠ,FEUFCMA(λ) 是可忽略的。

  • 盲签实验

在这里插入图片描述

定义敌手的优势为:

A

d

v

Π

,

A

b

l

i

n

d

(

λ

)

=

2

P

r

[

E

x

p

t

Π

,

A

b

l

i

n

d

(

1

λ

,

U

1

)

=

1

]

1

2

=

P

r

[

E

x

p

t

Π

,

A

b

l

i

n

d

(

1

λ

,

1

)

=

1

]

P

r

[

E

x

p

t

Π

,

A

b

l

i

n

d

(

1

λ

,

0

)

=

0

]

begin{aligned} Adv_{Pi,A}^{blind}(lambda) &= 2left| Prleft[Expt_{Pi,A}^{blind}(1^lambda,U_1)=1right] - frac{1}{2} right|\ &= left| Prleft[Expt_{Pi,A}^{blind}(1^lambda,1)=1right] - Prleft[Expt_{Pi,A}^{blind}(1^lambda,0)=0right] right| end{aligned}

AdvΠ,Ablind(λ)=2Pr[ExptΠ,Ablind(1λ,U1)=1]21=Pr[ExptΠ,Ablind(1λ,1)=1]Pr[ExptΠ,Ablind(1λ,0)=0]

我们说

Π

B

S

Pi_{BS}

ΠBS盲的,如果对于任意 PPT 敌手

A

A

A,优势

A

d

v

Π

,

A

b

l

i

n

d

(

λ

)

Adv_{Pi,A}^{blind}(lambda)

AdvΠ,Ablind(λ) 是可忽略的。

构造

密码学部件:

  • 一般签名算法

    Π

    s

    =

    (

    G

    e

    n

    s

    ,

    S

    i

    g

    n

    ,

    V

    e

    r

    )

    Pi_s = (Gen_s, Sign, Ver)

    Πs=(Gens,Sign,Ver)

  • 公钥加密方案

    Π

    e

    =

    (

    G

    e

    n

    e

    ,

    E

    n

    c

    ,

    D

    e

    c

    )

    Pi_e = (Gen_e, Enc, Dec)

    Πe=(Gene,Enc,Dec)

  • 非交互零知识证明

    (

    P

    ,

    V

    )

    (P,V)

    (P,V)

  • 非交互承诺方案

    Π

    c

    =

    (

    C

    o

    m

    ,

    O

    p

    e

    n

    )

    Pi_c = (Com,Open)

    Πc=(Com,Open)

盲签名的密钥生成算法

G

e

n

(

1

λ

)

Gen(1^lambda)

Gen(1λ) 为:

  1. 获得公共随机串

    C

    R

    S

    Z

    K

    CRS_{ZK}

    CRSZK

    C

    R

    S

    C

    o

    m

    CRS_{Com}

    CRSCom

  2. 执行

    (

    p

    k

    s

    ,

    s

    k

    e

    )

    G

    e

    n

    e

    (

    1

    λ

    )

    (pk_s,sk_e) leftarrow Gen_e(1^lambda)

    (pks,ske)Gene(1λ)

    (

    s

    k

    ,

    v

    k

    )

    =

    G

    e

    n

    s

    (

    1

    λ

    )

    (sk,vk) = Gen_s(1^lambda)

    (sk,vk)=Gens(1λ)

  3. 输出公钥

    v

    k

    B

    S

    =

    (

    C

    R

    S

    Z

    K

    ,

    C

    R

    S

    C

    o

    m

    ,

    p

    k

    e

    ,

    v

    k

    )

    vk_{BS} = (CRS_{ZK},CRS_{Com},pk_e,vk)

    vkBS=(CRSZK,CRSCom,pke,vk),私钥

    s

    k

    B

    S

    =

    (

    C

    R

    S

    Z

    K

    ,

    C

    R

    S

    C

    o

    m

    ,

    s

    k

    e

    ,

    s

    k

    )

    sk_{BS} =(CRS_{ZK},CRS_{Com},sk_e,sk)

    skBS=(CRSZK,CRSCom,ske,sk)

盲签协议(Blind-signing protocol)

<

S

,

U

>

<S,U>

<S,U> 构造如下:

在这里插入图片描述

验签算法

V

e

r

(

v

k

B

S

,

m

,

(

C

σ

,

π

)

)

Ver(vk_{BS},m,(C_sigma,pi))

Ver(vkBS,m,(Cσ,π)) 为:

  1. 设置

    x

    =

    (

    C

    σ

    ,

    p

    k

    e

    ,

    C

    R

    S

    C

    o

    m

    ,

    v

    k

    ,

    m

    )

    x = (C_sigma,pk_e,CRS_{Com},vk,m)

    x=(Cσ,pke,CRSCom,vk,m)

  2. 输出

    V

    (

    C

    R

    S

    Z

    K

    ,

    x

    ,

    π

    )

    V(CRS_{ZK},x,pi)

    V(CRSZK,x,π)

其中,NIZKP

<

P

,

V

>

<P,V>

<P,V> 所证明的关系为:

R

L

(

x

,

w

)

=

1
  


  

x

=

(

C

σ

,

p

k

e

,

C

R

S

C

o

m

,

v

k

,

m

)

w

=

(

u

,

v

,

σ

,

C

)

1)

 

C

=

C

o

m

(

C

R

S

C

o

m

,

m

;

u

)

2)

 

1

=

V

e

r

(

v

k

,

C

,

σ

)

3)

 

C

σ

=

E

n

c

(

p

k

e

,

C

σ

;

v

)

R_L(x,w)=1 iff begin{aligned} &x = (C_sigma,pk_e,CRS_{Com},vk,m)\ &w = (u,v,sigma,C)\ &textbf{1) }C = Com(CRS_{Com},m;u)\ &textbf{2) }1 = Ver(vk,C,sigma)\ &textbf{3) }C_sigma = Enc(pk_e,C|sigma;v)\ end{aligned}

RL(x,w)=1x=(Cσ,pke,CRSCom,vk,m)w=(u,v,σ,C)1) C=Com(CRSCom,m;u)2) 1=Ver(vk,C,σ)3) Cσ=Enc(pke,Cσ;v)

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>