LiftedElGamal门限加密算法

本文详细学习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\)，其中\(g^s=h\)。
（3）加密：选择一个随机数\(r\in Z_p\)，计算\(Enc_{PK}(m,r)=<g^r,h^r*g^m>\)；解密：密文\(c=<\alpha,\beta>\)，计算\(g^m=\beta*\alpha^{-s}\)，最后得到\(m\)【\(m\)只能是小数据，如果太大则根据离散对数问题\(m\)是难解的】

原论文中给出的公钥加密方案是：

参考：ElGamal算法

Lifted ElGamal 门限加密算法

（1）源自【A public key cryptosystem and a signature scheme based on discrete logarithms】
（2）这里将明文放在了指数上，恢复明文，就需要计算离散对数，所以\(\rho\)选取要很小，不然很难恢复明文。
（3）通过查表（离散对数表）来获取结果，这里对应上面的exhaustive search
（4）密钥生成，加密，解密和原ElGamal类似。

开源库

github：https://github.com/aistcrypt/Lifted-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 workcd workgit clone git://github.com/aistcrypt/Lifted-ElGamal.gitgit clone git://github.com/herumi/xbyak.gitgit clone git://github.com/herumi/mie.gitgit clone git://github.com/herumi/cybozulib.gitgit 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）有限域\(F_p\)上进行测试

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 initmode=initmake privateKey=vote_prv.txt, publicKey=vote_pub.txtPamdeMacBook-Air:bin pam$ ./vote_toold.exe vote -l 101010011mode=votevoters=101010011shuffleeach voter votesmake vote_5.txtmake vote_1.txtmake vote_6.txtmake vote_4.txtmake vote_7.txtmake vote_8.txtmake vote_0.txtmake vote_2.txtmake vote_3.txtPamdeMacBook-Air:bin pam$ ./vote_toold.exe countmode=countaggregate votesadd vote_0.txtadd vote_1.txtadd vote_2.txtadd vote_3.txtadd vote_4.txtadd vote_5.txtadd vote_6.txtadd vote_7.txtadd vote_8.txtcreate result file : vote_ret.txtPamdeMacBook-Air:bin pam$ ./vote_toold.exe openmode=openresult of vote count 5

源码

参考

1、集合交集问题的安全计算
2、Simple, Fast Malicious Multiparty Private Set Intersection