环-密钥生成.

n 为安全参数,其他参数均是n 的函数:

设Ui 表示环组成员且环组有l个成员,则每位环成员Ui 利用陷门抽样算法,抽取格矩阵以及格Λ⊥q(Ai) 的陷门基 环中心随机、独立地生成2k 个矩阵,j = 1,2,··· ,k,b = 0 或者1.环中心将所有环成员的公钥级联为一个新的矩阵,不失一般性,假设A = A1||A2||···||Al.设hash函数h(·) : {0,1}* →{0,1}k 为一个安全的hash函数.于是环公钥(,A),j =1,2,··· ,k,b=0 或者1.Ti 为用户Ui 的签名密钥.

环-签名.

设用户Ui 要生成签名消息M 的签名,消息的hash值为μ = h(M).Ui 首先利用μ 的各个分量选择公开参数矩阵 具体的,若μ 的第一个分量为0则选择参数矩阵,以此类推.级联所有用户的公钥矩阵与选定的参数矩阵得到矩阵于是利用盆景树的扩展控制算法和原像抽样函数生成消息的签名如下：(www.daowen.com)

环-验证.

验证者得到消息M 的签名v 后,首先计算hash函数值μ = h(M),利用μ 的各个分量值选取环参数矩阵并与环公钥A级联得到矩阵Aμ,然后验证：

通过以上验证则接受签名,否则拒绝签名.