本文详细学习Lifted ElGamal 门限加密算法
门限加密体制#
（1）门限加密是可以抗合谋的
（2）表现在私钥分为n份，至少需要t份才能解密成功，叫做（t-n）门限。类似于“秘密分享”。
ElGamal算法#
（1）源自【A public key cryptosystem and a signature scheme based on discrete logarithms】给出了加法和乘法同态性的定义，其中加法同态只能用于小的明文域。
（2）G是阶为p的群，g是群G的生成元，基于DDH问题，公钥是PK=(G,p,g,h)，私钥是SK=s，其中gs=h。
（3）加密：选择一个随机数r∈Zp，计算EncPK(m,r)=<gr,hr∗gm>；解密：密文c=<α,β>，计算gm=β∗α−s，最后得到m【m只能是小数据，如果太大则根据离散对数问题m是难解的】
原论文中给出的公钥加密方案是：
参考：ElGamal算法
Lifted ElGamal 门限加密算法#
（1）源自【A public key cryptosystem and a signature scheme based on discrete logarithms】
（2）这里将明文放在了指数上，恢复明文，就需要计算离散对数，所以ρ选取要很小，不然很难恢复明文。
（3）通过查表（离散对数表）来获取结果，这里对应上面的exhaustive search
（4）密钥生成，加密，解密和原ElGamal类似。
开源库#
该库实现了具有加法同态性的Lifted-ElGamal算法【A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms】和实现了对受限明文空间的零知识证明【Methods for Restricting Message Space in Public-Key Encryption】。
基于Lifted-ElGamal算法给出了一个投票系统。
安装#
环境：MacOS
（1）依赖库
OpenSSL：安装参考
GMP(libgmp-dev)
（2）下载
mkdir work
cd work
git clone git://github.com/aistcrypt/Lifted-ElGamal.git
git clone git://github.com/herumi/xbyak.git
git clone git://github.com/herumi/mie.git
git clone git://github.com/herumi/cybozulib.git
git clone git://github.com/herumi/cybozulib_ext.git
#如果卡的话，换成 https://github.com/***.git
其中：
- cybozulib_ext是VC（Visual C++）中使用OpenSSL和GMP库所需的
- Xbyak在Intel系CPU中提升运算速度
- Linux通过apt-get等获取OpenSSL和libgmp-dev
测试#
（1）有限域Fp上进行测试
CYBOZU_TEST_AUTO(testFp)
{
typedef mie::FpT<mie::Gmp, TagFp> Zn;
typedef mie::ElgamalT<Fp, Zn> ElgamalFp;
/*
Zn = (Z/mZ) - {0}
*/
const int m = 65537;
{
std::ostringstream os;
os << m;
Fp::setModulo(os.str());
}
{
std::ostringstream os;
os << m - 1;
Zn::setModulo(os.str());
}
ElgamalFp::PrivateKey prv;
/*
3^(m-1) = 1
*/
const int f = 3;
{
Fp x(f);
Fp::power(x, x, m - 1);
CYBOZU_TEST_EQUAL(x, 1);
}
prv.init(f, 17, rg);
const ElgamalFp::PublicKey& pub = prv.getPublicKey();
const int m1 = 12345;
const int m2 = 17655;
ElgamalFp::CipherText c1, c2;
pub.enc(c1, m1, rg);
pub.enc(c2, m2, rg);
// BitVector
{
cybozu::BitVector bv;
c1.appendToBitVec(bv);
ElgamalFp::CipherText c3;
c3.fromBitVec(bv);//c3复制c1
CYBOZU_TEST_EQUAL(c1.c1, c3.c1);
CYBOZU_TEST_EQUAL(c1.c2, c3.c2);
}
Zn dec1, dec2;
prv.dec(dec1, c1);
prv.dec(dec2, c2);
// dec(enc) = id，判断是否解密成功
CYBOZU_TEST_EQUAL(dec1, m1);
CYBOZU_TEST_EQUAL(dec2, m2);
// iostream
{
ElgamalFp::PublicKey pub2;
ElgamalFp::PrivateKey prv2;
ElgamalFp::CipherText cc1, cc2;
{
std::stringstream ss;
ss << prv;
ss >> prv2;
}
Zn d;
prv2.dec(d, c1);
CYBOZU_TEST_EQUAL(d, m1);
{
std::stringstream ss;
ss << c1;
ss >> cc1;
}
d = 0;
prv2.dec(d, cc1);
CYBOZU_TEST_EQUAL(d, m1);
{
std::stringstream ss;
ss << pub;
ss >> pub2;
}
pub2.enc(cc2, m2, rg);
prv.dec(d, cc2);
CYBOZU_TEST_EQUAL(d, m2);
}
// enc(m1) enc(m2) = enc(m1 + m2)
c1.add(c2);
prv.dec(dec1, c1);
CYBOZU_TEST_EQUAL(dec1, m1 + m2);
// enc(m1) x = enc(m1 + x)
const int x = 555;
pub.add(c1, x);
prv.dec(dec1, c1);
CYBOZU_TEST_EQUAL(dec1, m1 + m2 + x);
// rerandomize
c1 = c2;
pub.rerandomize(c1, rg);
// verify c1 != c2
CYBOZU_TEST_ASSERT(c1.c1 != c2.c1);
CYBOZU_TEST_ASSERT(c1.c2 != c2.c2);
prv.dec(dec1, c1);
// dec(c1) = dec(c2)
CYBOZU_TEST_EQUAL(dec1, m2);
// check neg
{
ElgamalFp::CipherText c;
Zn m = 1234;
pub.enc(c, m, rg);
c.neg();
Zn dec;
prv.dec(dec, c);
CYBOZU_TEST_EQUAL(dec, -m);
}
// check mul
{
ElgamalFp::CipherText c;
Zn m = 1234;
int x = 111;
pub.enc(c, m, rg);
c.mul(x);
Zn dec;
prv.dec(dec, c);
m *= x;
CYBOZU_TEST_EQUAL(dec, m);
}
// check negative value
for (int i = -10; i < 10; i++) {
ElgamalFp::CipherText c;
const Zn mm = i;
pub.enc(c, mm, rg);
Zn dec;
prv.dec(dec, c, 1000);
CYBOZU_TEST_EQUAL(dec, mm);
}
// isZeroMessage
for (int m = 0; m < 10; m++) {
ElgamalFp::CipherText c0;
pub.enc(c0, m, rg);
if (m == 0) {
CYBOZU_TEST_ASSERT(prv.isZeroMessage(c0));
} else {
CYBOZU_TEST_ASSERT(!prv.isZeroMessage(c0));
}
}
// zkp
{
ElgamalFp::Zkp zkp;
ElgamalFp::CipherText c;
cybozu::crypto::Hash hash(cybozu::crypto::Hash::N_SHA256);
pub.encWithZkp(c, zkp, 0, hash, rg);
CYBOZU_TEST_ASSERT(pub.verify(c, zkp, hash));
zkp.s0 += 1;
CYBOZU_TEST_ASSERT(!pub.verify(c, zkp, hash));
pub.encWithZkp(c, zkp, 1, hash, rg);
CYBOZU_TEST_ASSERT(pub.verify(c, zkp, hash));
zkp.s0 += 1;
CYBOZU_TEST_ASSERT(!pub.verify(c, zkp, hash));
CYBOZU_TEST_EXCEPTION_MESSAGE(pub.encWithZkp(c, zkp, 2, hash, rg), cybozu::Exception, "encWithZkp");
}
}
（2）测试加解密和同态计算
CYBOZU_TEST_AUTO(testEc)
{
typedef mie::FpT<mie::Gmp, TagEc> Zn;
typedef mie::ElgamalT<Ec, Zn> ElgamalEc;
Fp::setModulo(para.p);
Zn::setModulo(para.n);
Ec::setParam(para.a, para.b);
const Fp x0(para.gx);
const Fp y0(para.gy);
const size_t bitLen = Zn(-1).getBitLen();
const Ec P(x0, y0);
/*
Zn = <P>
*/
ElgamalEc::PrivateKey prv;
prv.init(P, bitLen, rg);
prv.setCache(0, 60000);
const ElgamalEc::PublicKey& pub = prv.getPublicKey();
const int m1 = 12345;
const int m2 = 17655;
ElgamalEc::CipherText c1, c2;
pub.enc(c1, m1, rg);
pub.enc(c2, m2, rg);
// BitVector
{
cybozu::BitVector bv;
c1.appendToBitVec(bv);
ElgamalEc::CipherText c3;
c3.fromBitVec(bv);
CYBOZU_TEST_EQUAL(c1.c1, c3.c1);
CYBOZU_TEST_EQUAL(c1.c2, c3.c2);
}
Zn dec1, dec2;
prv.dec(dec1, c1);
prv.dec(dec2, c2);
// dec(enc) = id
CYBOZU_TEST_EQUAL(dec1, m1);
CYBOZU_TEST_EQUAL(dec2, m2);
// iostream
{
ElgamalEc::PublicKey pub2;
ElgamalEc::PrivateKey prv2;
ElgamalEc::CipherText cc1, cc2;
{
std::stringstream ss;
ss << prv;
ss >> prv2;
}
prv.setCache(-200, 60000);
Zn d;
prv2.dec(d, c1);
CYBOZU_TEST_EQUAL(d, m1);
{
std::stringstream ss;
ss << c1;
ss >> cc1;
}
d = 0;
prv2.dec(d, cc1);
CYBOZU_TEST_EQUAL(d, m1);
{
std::stringstream ss;
ss << pub;
ss >> pub2;
}
pub2.enc(cc2, m2, rg);
prv.dec(d, cc2);
CYBOZU_TEST_EQUAL(d, m2);
}
// enc(m1) enc(m2) = enc(m1 + m2)
c1.add(c2);
prv.dec(dec1, c1);
CYBOZU_TEST_EQUAL(dec1, m1 + m2);
// enc(m1) x = enc(m1 + x)
const int x = 555;
pub.add(c1, x);
prv.dec(dec1, c1);
CYBOZU_TEST_EQUAL(dec1, m1 + m2 + x);
// rerandomize
c1 = c2;
pub.rerandomize(c1, rg);
// verify c1 != c2
CYBOZU_TEST_ASSERT(c1.c1 != c2.c1);
CYBOZU_TEST_ASSERT(c1.c2 != c2.c2);
prv.dec(dec1, c1);
// dec(c1) = dec(c2)
CYBOZU_TEST_EQUAL(dec1, m2);
// check neg
{
ElgamalEc::CipherText c;
Zn m = 1234;
pub.enc(c, m, rg);
c.neg();
Zn dec;
prv.dec(dec, c);
CYBOZU_TEST_EQUAL(dec, -m);
}
// check mul
{
ElgamalEc::CipherText c;
Zn m = 123;
int x = 111;
pub.enc(c, m, rg);
Zn dec;
prv.dec(dec, c);
c.mul(x);
prv.dec(dec, c);
m *= x;
CYBOZU_TEST_EQUAL(dec, m);
}
// check negative value
for (int i = -10; i < 10; i++) {
ElgamalEc::CipherText c;
const Zn mm = i;
pub.enc(c, mm, rg);
Zn dec;
prv.dec(dec, c, 1000);
CYBOZU_TEST_EQUAL(dec, mm);
}
// isZeroMessage
for (int m = 0; m < 10; m++) {
ElgamalEc::CipherText c0;
pub.enc(c0, m, rg);
if (m == 0) {
CYBOZU_TEST_ASSERT(prv.isZeroMessage(c0));
} else {
CYBOZU_TEST_ASSERT(!prv.isZeroMessage(c0));
}
}
// zkp
{
ElgamalEc::Zkp zkp;
ElgamalEc::CipherText c;
// cybozu::Sha1 hash;
cybozu::crypto::Hash hash(cybozu::crypto::Hash::N_SHA256);
pub.encWithZkp(c, zkp, 0, hash, rg);
CYBOZU_TEST_ASSERT(pub.verify(c, zkp, hash));
zkp.s0 += 1;
CYBOZU_TEST_ASSERT(!pub.verify(c, zkp, hash));
pub.encWithZkp(c, zkp, 1, hash, rg);
CYBOZU_TEST_ASSERT(pub.verify(c, zkp, hash));
zkp.s0 += 1;
CYBOZU_TEST_ASSERT(!pub.verify(c, zkp, hash));
CYBOZU_TEST_EXCEPTION_MESSAGE(pub.encWithZkp(c, zkp, 2, hash, rg), cybozu::Exception, "encWithZkp");
}
// cache
{
const int m1 = 9876;
const int m2 = -3142;
ElgamalEc::CipherText c1, c2;
pub.enc(c1, m1, rg);
pub.enc(c2, m2, rg);
prv.setCache(-10000, 10000);
int dec1 = prv.dec(c1);
int dec2 = prv.dec(c2);
CYBOZU_TEST_EQUAL(m1, dec1);
CYBOZU_TEST_EQUAL(m2, dec2);
c1.add(c2);
bool b;
int dec = prv.dec(c1, &b);
CYBOZU_TEST_EQUAL(m1 + m2, dec);
CYBOZU_TEST_ASSERT(b);
prv.clearCache();
prv.dec(c1, &b);
CYBOZU_TEST_ASSERT(!b);
}
// benchmark
{
int m = 12345;
ElgamalEc::CipherText c;
CYBOZU_BENCH("enc", pub.enc, c, m, rg);
prv.setCache(0, 20000);
CYBOZU_BENCH("dec", prv.dec, c);
CYBOZU_BENCH("rand", pub.rerandomize, c, rg);
}
}
同态计算：
（1）enc(m1) enc(m2) = enc(m1 + m2)
（2）enc(m1) x = enc(m1 + x)
投票例子#
介绍#
每个投票者对“0”或“1”进行加密，并单独将其密文发送到服务器，服务器计算结果，而不知道每次投票或结果本身，示例代码模拟了该方案。
编译后得到文件：vote_tool.exe
运行#
运行命令：
vote_tool.exe [opt] mode mode: select any one of init/vote/count/open -l: input a bit vector
（1）初始化
vote_tool.exe init
初始化系统并生成公钥（vote\u pub.txt）和密钥（vote\u prv.txt）。secp192k1用作EC ElGamal加密的参数。
（2）投票
vote_tool.exe vote [-l a bit vector]
输入一个长度为n 位向量v[i]（1bit），表示第i个投票人的投票
使用公钥对v[i]加密，并打乱密文序列的顺序。然后将每个密文存储在vote_0.txt,...,vote_n.txt中的任何一个文件中。由于顺序被打乱了，服务器无法检测哪个文件包含谁的投票。此过程模拟每个投票者单独发送使用自己的公钥加密的密文。
（3）统计
vote_tool.exe count
该程序从文件中读取所有密文，并在不解密的情况下检查是否是“0”或“1”加密的。这是通过使用第三方库提供的非交互式零知识证明来实现的。该程序在不解密的情况下聚合密文并验证所有密文。
（4）打开
vote_tool.exe open
该程序解密密文写入的result.txt，并在控制台上显示结果。
结果：
PamdeMacBook-Air:bin pam$ ./vote_toold.exe init
mode=init
make privateKey=vote_prv.txt, publicKey=vote_pub.txt
PamdeMacBook-Air:bin pam$ ./vote_toold.exe vote -l 101010011mode=vote
voters=101010011
shuffle
each voter votes
make vote_5.txt
make vote_1.txt
make vote_6.txt
make vote_4.txt
make vote_7.txt
make vote_8.txt
make vote_0.txt
make vote_2.txt
make vote_3.txt
PamdeMacBook-Air:bin pam$ ./vote_toold.exe count
mode=count
aggregate votes
add vote_0.txt
add vote_1.txt
add vote_2.txt
add vote_3.txt
add vote_4.txt
add vote_5.txt
add vote_6.txt
add vote_7.txt
add vote_8.txt
create result file : vote_ret.txt
PamdeMacBook-Air:bin pam$ ./vote_toold.exe open
mode=open
result of vote count 5
源码#
参考#
1、集合交集问题的安全计算
2、Simple, Fast Malicious Multiparty Private Set Intersection