参数选择.令n 为系统的安全参数,m=8n log q其中q =poly(n).α=1/poly(n)为一个错误分布的参数.s 是一个高斯抽样的参数.Let k 为一次强不可伪造签名方案的验证密钥的长度.令Ssign表示一个强存在性不可伪造的一次签名方案,vk ∈{0,1}k 是Ssign的验证密钥.我们假设vk 的汉明重量l 的大小为k/2或k/2+1,即vk ∈{0,1}k 是0,1均衡的.

密钥生成.运行陷门抽样算法,输出矩阵A 以及格Λ⊥q(A)的陷门基T.随机选择矩阵其中i=1,2,··· ,k.则,(A,Ai)为公钥,T 为密钥.

加密.执行以下运算来完成对消息的加密:

Step 1.随机的选择Ssign方案的签名密钥sk 和验证密钥vk.令vk =(vk[1],vk[2],··· ,vk[k])其中vk[i]∈{0,1},并设vk 的汉明重量为l.

Step 2.按照如下原则选取公开矩阵Ai 参与加密运算：如果vk[i] = 1,选择相应的矩阵Ai,如果vk[i] = 0,则不选择任何矩阵.不妨设vk[ji] = 1 其中i = 1,2,··· ,l,并令

Step 3.随机的选择一个矩阵以及一个错误矩阵 计算

Step 4.将sk,vk,C 输入Ssign方案的签名算法,输出一个一次签名σ.(www.daowen.com)

于是,(C,vk,σ)作为消息M 对应的密文.

解密.为了完成对(C,vk,σ)的解密,解密算法如下操作:

Step 1.验证一次签名σ 的正确性,若验证失败则终止,否则继续Step 2.

Step 3.以为输入,运行盆景树算法,输出格的一组陷门基.

Step 4.计算E=Tt1C(modq),M=T-t1 E(mod2).