基于ElGamal体制的门限秘密共享方案

基于ECC的存在特权集的门限群签名方案董玉蓉【摘要】通过对一种EIGamal类型存在特权集的门限群签名方案的分析研究,提出了一种基于ECC的存在特权集的门限群签名方案.该方案能有效防止KDC的欺诈,且只有在同时满足(t,n)ch,(t1,n1)门限签名时才能生成消息的有效签名,从而实现了门限特性,并具有门限群签名应有的性质.【期刊名称】《微型机与应用》【年(卷),期】2011(030)002【总页数】4页(P89-92)【关键词】特权集;秘密共享;门限群签名;ECC【作者】董玉蓉【作者单位】贵州大学计算机科学与信息学院,贵州贵阳520025【正文语种】中文【中图分类】TP309群签名方案首次由Chanm和VanHeyst于1991年提出。

在群签名方案中，允许每个成员都可以代表整个群体进行签名。

在群签名方案中引入秘密共享，解决密钥安全与有效保管问题的同时也形成了一类新的群签名方案——门限群签名方案，即群体中的某些给定子集可以代表整个群体签名。

在门限群签名方案中，门限群签名是由参加签名的各个成员所签署的部分数字签名按照某种方式结合后产生。

2003年，BELLARE M等人提出了群签名的简化形式定义[1]。

在这之后，不少学者提出的门限群签名方案均采用形式化的方法证明方案的安全性。

参考文献[2]提出良好的门限群签名应该具备以下一些性质：群签名特性、门限特性、不可伪造性、验证简单性、匿名性、可追查性、强壮性。

参考文献[3]中，Chen Feng等人基于Shamir秘密共享体制并结合“存在特权集的门限群签名方案”的思想[4]，构造了一类基于离散对数问题的ElGamal类型的存在特权集的门限群签名方案。

本文利用椭圆曲线密码体制的特点对Chen Feng的方案进行改进。

新的方案与原方案的共同点在于都使用双重秘密共享技术和单签名构造群签名的技术[3]，不同之处在于新方案实现了群成员的加入和撤销，提高了方案的通用性。

椭圆曲线上的向量空间秘密共享方案才宇飞;姜伟;刘焕平【摘要】In this paper, a vector space secret sharing scheme based on elliptic curve is proposed. The scheme expands the secret from the finite field to the elliptic curve. The sub - secret is encrypted by the elliptic curve E1Gamal cryptography to enhance the security. Its security is based on the security of the elliptic curve EIGamal cryptosystem and the intractability of the elliptic curve discrete logarithm problem. Compared with congener schemes, this one does not need security channel to send secret and spends less communication cost with high reliability and small amount of calculation.%基于椭圆曲线提出一个向量空间秘密共享方案．方案中将共享的秘密由有限域拓展到椭圆曲线上．利用椭圆曲线上的ElGamal密码体制加密子秘密，使得秘密具有更高的安全性．其安全性是基于椭圆曲线上的ElGamal密码体制的安全性及椭圆曲线离散对数问题难解性．与同类方案相比，该方案不需要安全信道发送秘密，且花费较小的通信代价，安全性高，计算量小．【期刊名称】《哈尔滨师范大学自然科学学报》【年(卷),期】2012(028)003【总页数】3页(P38-40)【关键词】秘密共享;椭圆曲线;ElGamal密码体制【作者】才宇飞;姜伟;刘焕平【作者单位】哈尔滨师范大学;天津市渤海石油第一中学;哈尔滨师范大学【正文语种】中文【中图分类】TP3090 引言在保密通信中，秘密共享是信息安全和数据保密的重要手段，针对密钥管理中密钥的泄漏问题和遗失问题，Blakley［1］和 Shamir［2］于 1979 年分别独立提出了门限秘密共享体制，由于门限秘密共享体制简单有效和易于实现，因此得到了很多学者的关注并对其进行了大量的研究.Asmuth和Bloom［3］提出了基于中国剩余定理的秘密共享方案，相对于Shamir［2］的方案降低了秘密重构阶段的计算复杂性，同时安全性也降低了.Angsuman Das 和 Avishek Adhikari［4］提出一般接入结构上的秘密共享方案，使其具有更加广泛的应用空间.1989 年，Brickell［5］提出了向量空间秘密共享方案，并且指出Shamir门限方案是向量空间秘密共享方案的特殊情况.2002年，许春香［6］等人提出一个密钥空间为有限域的安全矢量空间秘密共享方案，并对安全性和信息率做了定量分析.由于现代密码分析技术的不断发展，攻击者的计算能力增强，基于有限域的密码体制已经不能满足安全性的需要，越来越多的学者投入到安全性更好的椭圆曲线密码体制的研究，由于椭圆曲线公钥密码体制具有密钥短，加密强度高，存储空间小的优点，学者构造了许多的椭圆曲线秘密共享方案［7-9］.1 预备知识1.1 向量空间访问结构及向量空间秘密共享方案设 P={p1，p2，…，pn}是n个分享者集合，K=GF(q)是一个有限域，分发者D∉P，Kr是K上的r维向量空间.Γ是P上的一个单调访问结构，且r不小于所有最小授权子集的最大基数.称Γ是一个向量空间访问结构，如果存在函数φ:P∪D→Kr，满足性质φ(D)=(1，0，…，0)∈〈φ(pi):pi∈B〉⇔B∈Γ.向量空间秘密共享方案［10］构造如下:首先D向全体参与者公布函数φ，对要共享的秘密S∈K，D定义v1=S，并随机地选取vi∈K，i=2，3，…，r.K 中的一个向量 v=(S，v2，…，vr)，使得S=v·φ(D).其中φ(D)=(1，0，…，0)，把si=v·φ(pi)的值作为子秘密份额秘密发送给每个参与者pi，如果B={p1，p2，…，pl}是一个授权子集，则存在K中的一个向量λ =(λ1，λ2，…，λl)，满足，其中“·”表示向量的数量积(内积)，则有从而对于B中的参与者来说，秘密S由他们所共享的子秘密si的线性组合来恢复.1.2 模素数的椭圆曲线定义1 有限域Zp上的椭圆曲线E(Zp)是定义在仿射平面上的三次方程y2≡(x3+ax+b)modp的所有解(x，y)∈Zp×Zp与无穷远点O构成的并集，记为其中:p为素数，p ＞ 3，a，b∈Zp，且4a3+27b2≠0.E上的点数记为#E，它满足不等式E上的加法运算定义如下:假设P=(x1，y1)，Q=(x2，y2)是 E 上的点.如果 x1=x2且y2=-y1，则 P+Q=O;否则 P+Q=(x3，y3)，其中且可以证明，椭圆曲线上的点关于点的加法构成阿贝尔群.如果P=(x，y)，k是一个整数，那么点P的阶是满足nP=O的最小的正整数，记为l.定义2 给定一个有限域Zp上的椭圆曲线E(Zp)，P∈E(Zp)，点P的阶为大素数l，对于给定点R ∈〈P〉，计算整数n∈［1，l］，满足 nP=R.称为椭圆曲线离散对数问题(ECDLP).2 椭圆曲线上的向量空间秘密共享方案假设 P={p1，p2，…，pn}是n个参与者的集合，E(Zp)是有限域Zp上的椭圆曲线，G是一个l(l是一个大素数)阶的E(Zp)上的基点，且〈G〉上的椭圆曲线离散对数问题是难解的.所要共享的秘密S∈E(Zp)，Γ是P的一个向量空间访问结构，φ:P∪ D→是相应的函数，公开参数φ(pi)=(ai1，ai2，…，air)，φ(D)={1，0，…，0}.首先每个参与者pi选取ai∈［1，l］，计算βi=aiG，ai作为私钥，βi公开.其次分发者D选取a∈［1，l］，计算β =aG，a作为私钥，β 作为公钥，分发者要保证βi≠ βj(i≠ j)，β ≠ βi，i，j=1，2，…n.2.1 秘密份额的分发(1)分发者D任意选取数x2，…，xr∈，令v=(S，x2G，…，xrG)∈ (Zp× Zp)r，所共享的秘密S=v·φ(D).(2)分发者计算si=v·φ(pi)=ai1S+ai2x2G+ … +airxrG，i=1，2，…，n，si为参与者pi的子秘密共享.(3)分发者选取k∈，对于每个 si=(six，siy)，计算公开 C1，C2i，i=1，2，…，n.2.2 秘密的恢复为了恢复秘密S，不妨假设B={p1，p2，…，pl}是授权子集，则存在Zp上的向量使得又因为C2i-aiC1=si(见后文可行性分析)，所以授权子集中的成员用自己的私钥ai 即可求得si，再由B中的所有参与者提供的子秘密si就可恢复秘密S，3 方案分析(1)可行性分析.令 xiG=(mi，ni)，i=2，…，r则向量参与者共享的秘密恢复秘密时，设授权子集 B={p1，p2，…，pl}∈Γ，则，其中λ =(λ1，λ2，…，λl)，由于所以授权子集中的成员用自己的私钥ai即可求得 si，秘密(2)本方案的安全性是基于椭圆曲线离散对数问题难解性及椭圆曲线上的Elgamal 密码体制的安全性.采用椭圆曲线上的Elgamal密码体制对子秘密si进行加密，提高了安全性能，计算简单.已知C1，试图从C1=kG中得到整数k是不可能的，同样，已知 C2i，试图从C2i=si+kβi中得到si是不可能的，因为k是未知的. (3)当要保存新的秘密S'时，只需分发者D重新选择xi∈R(Zp)*，i=2，…，r再计算参与者的子秘密si'，按照以上的步骤进行，公开C1'，C2i'.而不需要改变分发者和参与者的公钥和私钥.4 结论基于椭圆曲线提出了一个更具安全性，实用性的向量空间秘密共享方案.无需安全信道传输，也减少了通信代价.椭圆曲线密码体制使秘密共享建立在椭圆曲线离散对数难题上，提高了安全性能.再接下来的研究中，会考虑无可信中心的秘密共享方案.参考文献［1］ Blakley G R.Safeguarding Cryptographic Keys［A］.Proc.AFIPS 1979 National Computer Conference，1979:313-317.［2］ Shamir A.How to Share a Secret［J］.Communications of the ACM，1979，22(11):612-613.［3］ Asmuth C.，Bloom J.A Modular Approach to Key Safeguarding ［J］.IEEE Transactions on Information Theory，1983，29:208-210.［4］ Das A.，Adhikari A.An Efficient Mult-use Multi-secret Sharing Scheme Based on Hash Function［J］.Applied Mathematics Letters，2010，23:993-996.［5］ Brickell E F.，Some Ideal Secret Sharing Schemes［J］.Journal of Combinatorial Mathematics and Combinatorial Computing，1989，9:105-113.［6］许春香，陈凯，肖国振.安全的矢量空间秘密共享方案［J］.电子学报，2002，30(5):715-718.［7］殷春梅，汪彩梅.一种基于椭圆曲线的多密钥共享方案［J］.合肥工业大学学报，2006，29(4):392-394.［9］肖立国，钟诚，陈国良.基于椭圆曲线密码体制的动态秘密共享方案［J］.微电子学与算机，2002(1):30-31.［10］Stinson D R.密码学原理与实践［M］.冯登国等译，3版.北京:电子工业出版社，2010.。

基于ElGamal体制的门限密钥托管方案
曹珍富;李继国
【期刊名称】《计算机学报》
【年(卷),期】2002(025)004
【摘要】该文基于ElGamal密码体制提出了一个门限密钥托管方案.这个方案不仅有效地解决了"一次监听,永久监听"问题,而且每个托管代理能够验证他所托管的子密钥的正确性,并且在监听阶段,监听机构能够确切地知道门限密钥托管方案中哪些托管代理伪造或篡改子密钥.由于该方案是门限密钥托管方案,所以在各托管代理中有一个或几个托管代理不愿合作或无法合作时,监听机构仍能很容易地重构出会话密钥.此外,还具有抵抗LEAF反馈攻击的特性.
【总页数】5页(P346-350)
【作者】曹珍富;李继国
【作者单位】上海交通大学计算机科学与工程系,上海,200030;哈尔滨工业大学计算机科学与工程系,哈尔滨,150001
【正文语种】中文
【中图分类】TP309
【相关文献】
1.基于ElGamal公钥体制的动态密钥托管方案 [J], 房伟;闫鸿滨
2.基于ELGamal密码体制的安全密钥托管方案 [J], 张文娟;张锦华
3.基于ElGamal公钥体制的动态(k,n)门限密钥托管方案 [J], 谢丽丽;张龙;刘绍武;
柯品惠
4.基于椭圆曲线密码体制的动态(k,n)门限密钥托管方案 [J], 谢丽丽;张龙;刘绍武
5.基于椭圆曲线密码体制的门限密钥托管方案 [J], 何业锋;张建中
因版权原因，仅展示原文概要，查看原文内容请购买。

elgamal公钥密码体制
摘要：
I.简介
- 公钥密码体制的定义
- ElGamal 公钥密码体制的提出背景
II.ElGamal 公钥密码体制的基本原理
- 加密和解密过程
- 数字签名和验证过程
III.ElGamal 公钥密码体制的安全性
- 密钥生成和分发
- 攻击模型的分析
IV.ElGamal 公钥密码体制的应用
- 电子商务领域的应用
- 安全通信领域的应用
正文：
ElGamal 公钥密码体制是一种非对称加密算法，由Taher ElGamal 于1985 年提出。

该体制基于离散对数问题的困难性，相较于RSA 密码体制，ElGamal 密码体制在相同安全级别下具有更小的密钥长度。

ElGamal 公钥密码体制的基本原理包括加密和解密过程、数字签名和验证过程。

在加密过程中，发送方使用接收方的公钥对明文进行加密；在解密过程中，接收方使用自己的私钥对密文进行解密。

数字签名过程类似于加密过程，
发送方使用接收方的公钥对自己发送的消息进行签名，接收方则使用发送方的私钥对签名进行验证。

ElGamal 公钥密码体制的安全性主要依赖于密钥生成和分发。

密钥生成过程中，用户需要选择一个大于1 的素数p，并在模p 意义下找到一个随机数x，通过计算得到公钥和私钥。

密钥分发过程中，发送方需要将公钥发送给接收方，而私钥则需要妥善保管，以防止泄露。

尽管ElGamal 公钥密码体制在电子商务领域和安全通信领域有着广泛的应用，但由于其密钥长度相对较小，容易受到暴力破解攻击。

因此，研究者们针对该体制提出了许多改进方案，以提高其安全性和抵抗攻击的能力。

shamir 原理简单介绍
Shamir的门限方案是一种基于拉格朗日插值多项式的密码学方案，用于实现秘密共享。

其基本原理是将一个秘密密钥切分成多个部分，并分发给不同的参与方。

当满足指定的门限条件时，参与方才能合作将密钥还原出来。

这样做的好处是即使有部分参与方失效或者被攻击，仍然可以保证密钥的安全性。

Shamir门限方案的核心原理是将秘密密钥作为常数项，构造一个t-1次多项式，其中t是门限值。

然后选择一个有限域和t-1个随机数作为插值多项式的系数，在每个参与方上计算对应的多项式值，并将其作为该参与方的私密分享。

通过任意t个参与方的合作运算，可以通过插值多项式重建密钥。

Shamir门限方案具有很高的安全性，因为即使少于t个参与方联合也不能得到共享秘密的任何信息。

此外，Shamir门限方案还具有灵活性和可扩展性，可以根据实际需求调整门限值和参与方数量。

基于iOS终端的SM2移动密码系统邓高宇;龙毅宏【摘要】本文提出并实现了一种基于iOS移动终端的SM2移动密码系统方案,在iOS移动终端提供基于秘密共享的SM2签名功能.此系统针对SM2私钥进行秘密共享,将SM2私钥秘密份额分别存储在移动终端和密码服务器上.在应用程序需要使用SM2私钥进行数字签名时,移动终端和密码服务器分别使用SM2私钥秘密份额进行密码运算,最后将密码运算的结果组合实现SM2数字签名.本文提出的针对SM2私钥的秘密共享方案,使用户能够基于iOS移动终端安全地使用SM2私钥.【期刊名称】《软件》【年(卷),期】2018(039)002【总页数】4页(P28-31)【关键词】SM2;移动终端;秘密共享【作者】邓高宇;龙毅宏【作者单位】武汉理工大学信息工程学院,湖北武汉 430070;武汉理工大学信息工程学院,湖北武汉 430070【正文语种】中文【中图分类】TN918.910 引言SM2椭圆曲线公钥密码算法于 2010年首次公开发布，2012年成为中国商用密码标准，2016年成为中国国家密码标准。

迄今为止与SM2算法相关研究表明，SM2算法的可证安全性达到了公钥密码算法的最高安全级别[1]，其实现效率相当于或略优于一些国际标准的同类椭圆曲线密码算法[2-5]。

2013年，孙荣燕，蔡昌曙，周洲[6]等人对SM2数字签名算法与 ECDSA算法进行了对比与分析研究，对ECDSA-SM2算法的数字模型进行了正确性证明。

2016年，陈泽凯[7]实现了一个基于身份的SM2椭圆曲线数字签名方案SM2-IBS，具有效率高、签名长度短、不依赖PKI等特点。

随着4G、WLAN、传感器等无线网络的普及，使用移动终端逐渐成为用户访问网络处理业务（包括网络通信、电子支付、网上银行等）的重要手段[8]。

而在移动终端上使用公钥密码私钥如SM2私钥时，最重要的一点就是保障用户私钥存储、使用的安全。

目前在移动终端对用户私钥进行有效保护的手段主要有两种：一种是采用USB密码钥匙（USB key）作为客户端装置来存储私钥[9]，此种方式给用户带来了使用成本，而且使用也不方便；另一种方式是使用移动终端内置密码芯片来存储私钥并进行密码运算，然而内置密码芯片的移动终端应用不广，市面上绝大部分手机都不自带密码芯片，且目前不存在支持SM2密码运算的手机密码芯片。

Computer Science and Application 计算机科学与应用, 2019, 9(5), 941-946Published Online May 2019 in Hans. /journal/csahttps:///10.12677/csa.2019.95107Design of Privacy Protection ElectronicVoting Scheme Based on ElGamalHomomorphic EncryptionJing LiuSchool of Information and Security Engineering, Zhongnan University of Economics and Law, Wuhan HubeiReceived: May 7th, 2019; accepted: May 20th, 2019; published: May 27th, 2019AbstractRealizing the true anonymity is a research hot spot in the field of electronic voting. This paper proposes an electronic voting framework based on ElGamal homomorphic encryption. It counts ciphertext votes and then the statistical data is decrypted to obtain the voting result. This scheme greatly improves the anonymity of voting and data security at the time of counting. Further, expe-riments based on real-world scenario show that execution time and operational efficiency of the framework, and the feasibility of the framework is verified.KeywordsElectronic Voting, Homomorphic Encryption, Anonymity, Privacy Preserving基于ElGamal同态加密的隐私保护电子投票方案设计刘静中南财经政法大学信息与安全工程学院，湖北武汉收稿日期：2019年5月7日；录用日期：2019年5月20日；发布日期：2019年5月27日摘要实现电子投票真正地匿名性是电子投票领域的一个研究热点。

第３１卷第２期北京电子科技学院学报２０２３年６月Ｖｏｌ．３１Ｎｏ．２ＪｏｕｒｎａｌｏｆＢｅｉｊｉｎｇＥｌｅｃｔｒｏｎｉｃＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙＩｎｓｔｉｔｕｔｅＪｕｎ．２０２３基于编码的ＥｌＧａｍａｌ型公钥密码体制研究概述∗刘㊀冰㊀吴旭聃㊀冯雨薇北京电子科技学院，北京市㊀１０００７０摘㊀要：基于编码的公钥密码算法具有安全性高㊁加解密速度快㊁易于实现的优点，但也普遍存在公钥规模大的缺点㊂常用的基于编码的加密方式有ＭｃＥｌｉｅｃｅ型㊁Ｎｉｅｄｅｒｒｅｉｔｅｒ型和ＥｌＧａｍａｌ型三种㊂作为新出现的加密模式，ＥｌＧａｍａｌ型体制中涉及两类不同功能的编码，存在译码失败概率问题，采用了独特的临时密钥方法，提高了其安全性能㊂本文重点对ＥｌＧａｍａｌ型加密方式进行介绍，对其结构㊁所基于的困难问题和译码失败概率等进行了研究，从而可以对该结构有更深入的认识，并据此为以后的设计和分析工作奠定基础㊂关键词：编码；ＥｌＧａｍａｌ型；临时密钥；译码失败概率中图分类号：ＴＰ３０９㊀㊀㊀文献标识码：Ａ文章编号：１６７２－４６４Ｘ（２０２３）２－０１－０９∗㊀基金项目：北京电子科技学院一流学科建设项目（项目编号：１２０１０１１）∗∗㊀作者简介：刘冰（１９７６－），男，博士，副教授，研究方向：密码学；吴旭聃（１９９６－），男，硕士研究生，研究方向：密码学；冯雨薇（１９９８－），女，硕士研究生，研究方向：密码学㊂引言㊀㊀随着时代的发展，量子计算机能将许多传统的公钥密码算法轻易破解，所以须寻求安全性更高的公钥密码算法，这就有了后量子密码算法［１，２］的出现㊂后量子密码算法能够有效抵御量子计算机的攻击，它们大致有以下几种：基于格的㊁基于编码的㊁基于多变量的㊁基于同源的㊁基于哈希函数的等㊂目前，越来越多的学者开始对后量子密码学进行研究㊂ＮＩＳＴ发布公告，呼吁制定新标准用于后量子密码系统，ＣＡＣＲ也举办了包括后量子密码在内的算法竞赛，来鼓励更多的人加入此项研究㊂美国国家标准技术研究所（ＮＩＳＴ）在２０１２年启动了后量子密码的研究工作，并于２０１６年２月启动了全球范围内的后量子密码标准征集㊂ＮＩＳＴ主要聚焦于以下３类后量子密码算法的征集：公钥加密㊁密钥交换㊁数字签名㊂有８２个提案提交给ＮＩＳＴ，其中６９个方案进入第一轮，基于编码的方案有２０个㊂有２６个提案进入第二轮，有７个基于编码的方案［３］㊂有１５个提案进入第三轮，基于编码的有３个㊂ＮＩＳＴ于２０２２年７月发布了进入第四轮的候选算法，其中基于编码的有３个，分别是ＢＩＫＥ［４］㊁ＣｌａｓｓｉｃＭｃＥｌｉｅｃｅ［５］㊁ＨＱＣ［６］㊂ＣＡＣＲ的公钥密码竞赛中，也有进入到第二轮的基于编码的算法Ｐｉｇｌｅｔ－１㊂基于编码的困难问题是公认的ＮＰ完全问题，在安全性方面能够得到保障，因而基于编码的密码算法有望成为后量子密码算法的主要选择㊂基于编码的公钥加密算法一直有着公钥规模大的缺点，但减小公钥规模可能会对其安全性北京电子科技学院学报２０２３年造成影响，有关方面的专家一直在这两者之间寻找一个平衡㊂基于编码的公钥密码系统，最早由ＭｃＥｌｉｅｃｅ［７］于１９７８年提出，称为ＭｃＥｌｉｅｃｅ方案，该方案基于Ｇｏｐｐａ码构造㊂Ｎｉｅｄｅｒｒｅｉｔｅｒ在１９８６年提出了安全性等价的Ｎｉｅｄｅｒｒｅｉｔｅｒ型方案㊂这两个体制的区别在于前者加密使用的是生成矩阵，而后者使用的是校验矩阵㊂近些年，受到格的加密算法的启发，编码的加密方案也开始使用ＥｌＧａｍａｌ型加密方式［６］㊂本文对ＮＩＳＴ中的一些基于编码的方案，根据它们的加密方式㊁所用的码㊁所基于的困难问题进行分类，如表１所示㊂表１㊀基于编码的ＮＩＳＴ方案汇总类别结构码困难问题遴选结果ＣｌａｓｓｉｃＭｃＥｌｉｅｃｅＮｉｅｄｅｒｒｅｉｔｅｒ型Ｇｏｐｐａ码ＳＤ问题第四轮ＢＩＫＥＮｉｅｄｅｒｒｅｉｔｅｒ型ＱＣ⁃ＭＤＰＣ码ＱＣＳＤ问题第四轮ＨＱＣＥｌＧａｍａｌ型ＱＣ⁃ＭＤＰＣ码ＱＣＳＤ问题第四轮ＲＱＣＥｌＧａｍａｌ型ＱＣ⁃ＬＲＰＣ码ＲＱＣＳＤ问题第二轮ＲＯＬＬＯＥｌＧａｍａｌ型ＱＣ⁃ＬＲＰＣ码ＲＱＣＳＤ问题第二轮ＬＥＤＡｃｒｙｐｔＭｃＥｌｉｅｃｅ型ＱＣ⁃ＭＤＰＣ码ＱＣＳＤ问题第二轮ＢＩＧＱＵＡＫＥＮｉｅｄｅｒｒｅｉｔｅｒ型Ｇｏｐｐａ码ＱＣＳＤ问题第一轮ＲＬＣＥ⁃ＫＥＭＭｃＥｌｉｅｃｅ型广义Ｒｅｅｄ⁃Ｓｏｌｏｍｏｎ码ＳＤ问题第一轮ＤＡＧＳＭｃＥｌｉｅｃｅ型ＤｙａｄｉｃＧｅｎｅｒａｌｉｚｅｄＳｒｉｖａｓｔａｖａ码ＳＤ问题第一轮１㊀相关定义㊀㊀定义１汉明距离和线性码㊂令Ｆｑ是一个有限域，则Ｆｎｑ上两个字ｘ和ｙ之间的汉明距离［８］定义为ｘ和ｙ在对应位上不相同的位数㊂字ｘ的汉明重量ｗｔ（ｘ）定义为ｘ中非零的位数㊂一个码是汉明空间Ｆｎｑ的一个非空子集合㊂一个Ｆｎｑ的ｋ维子空间被称为是Ｆｑ上的一个（ｎ，ｋ）线性码㊂定义２生成矩阵和校验矩阵㊂设Ｃ是Ｆｑ上的（ｎ，ｋ）线性码㊂码Ｃ的生成矩阵［９］Ｇ是一个Ｆｑ上的矩阵，且使得Ｃ＝＜Ｇ＞，＜Ｇ＞表示码Ｃ的向量子空间由Ｇ的行向量所张成㊂通常，Ｇ的行向量是相互独立的，且Ｇ是ｋˑｎ阶矩阵㊂如果Ｇ矩阵的前ｋ列构成ｋ阶单位阵，则称Ｇ为系统形式的生成矩阵㊂码Ｃ的对偶码Ｃʅ是在Ｆｑ上的标量乘意义下与Ｃ正交的码㊂它是Ｆｑ上的一个（ｎ，ｎ－ｋ）码㊂码Ｃ的校验矩阵［９］Ｈ就是其对偶码Ｃʅ的生成矩阵㊂定义３最小距离和最小重量㊂设Ｃ是Ｆｑ上的（ｎ，ｋ）线性码㊂码Ｃ的最小距离ｄ＝ｄｍｉｎ（Ｃ）是码的任意两个不同码字之间汉明距离的最小值㊂码Ｃ的最小重量是码的任意非零码字重量的最小值㊂线性码的最小距离等于其最小重量㊂设码的最小距离为ｄ，则将（ｎ，ｋ）线性码称为（ｎ，ｋ，ｄ）码㊂定义４秩距离㊂在有限域Ｆｑｍ上（Ｆｑｍ可视为Ｆｑ的ｍ维空间），设ｕ＝（ｕ１，ｕ２，．．．，ｕｎ）ɪＦｎｑｍ，β１， ，βｍ是Ｆｑ上的一组基向量，每个ｕｉ可以由基表示为ｕｉ＝ðｍｊ＝１ｘｊｉβｊ，则矩阵Ｕ＝（ｘｊｉ）１ɤｊɤｍ，１ɤｉɤｎ，的秩称为ｕ的秩重量，记为ｗＲ（．）㊂∀ｕ，ｖɪＦｎｑｍ，ｕ和ｖ的秩距离［１０］ｄ（ｕ，ｖ）＝ｗＲ（ｕ－ｖ）㊂定义５循环矩阵㊂令ｘ＝（ｘ１， ，ｘｎ）ɪＦｎ㊂则循环矩阵定义如下：ｒｏｔ（ｘ）＝ｘ１ｘｎ ｘ２ｘ２ｘ１ ｘ３︙︙⋱︙ｘｎｘｎ－１ ｘ１éëêêêêêêùûúúúúúúɪＦｎˑｎ定义６准循环码（Ｑｕａｓｉ⁃ＣｙｃｌｉｃＣｏｄｅｓ）［１１］㊂将Ｆｓｎ２的向量ｘ＝（ｘ１， ，ｘｓ）视为ｓ个连续块（ｎ元组）㊂对于任意ｃ＝（ｃ１， ，ｃｓ）ɪＣ，每个块ｃ１， ，ｃｓ同时进行循环变换后获得的向量仍是㊃２㊃第３１卷基于编码的ＥｌＧａｍａｌ型公钥密码体制研究概述㊀一个是码字，则称一个［ｓｎ，ｋ，ｄ］线性码Ｃ是ｓ阶的准循环（ＱＣ）㊂定义７ＭＤＰＣ码［１２］：即中密度奇偶校验码㊂一个（ｎ，ｒ，ｗ）－ＭＤＰＣ码是指长度为ｎ，其奇偶校验矩阵行重量为ｗ，余维数为ｒ的线性码㊂ＭＤＰＣ码与ＬＤＰＣ码（低密度奇偶校验码）的区别在于它们行重量的大小，ＭＤＰＣ码行重量约为Ｏ（ｎｌｏｇｎ）数量级㊂定义８ＱＣ⁃ＭＤＰＣ码［１２］㊂（ｎ，ｒ，ｗ）－ＭＤＰＣ码为准循环结构时，即准循环中密度奇偶校验码（ＱＣ⁃ＭＤＰＣ码）㊂ＱＣ⁃ＭＤＰＣ码的定义是关于该码的校验矩阵Ｈ㊂（ｎ，ｋ，ｗ，ｔ）－ＱＣ⁃ＭＤＰＣ码中ｎ是码长，也是Ｈ的列数；ｋ为码的维度，ｒ＝ｎ－ｋ表示码的校验维度，也是Ｈ的行数；ｗ表示校验矩阵Ｈ的固定行汉明重量；ｔ表示码的纠错能力㊂ＱＣ⁃ＭＤＰＣ码的准循环结构奇偶校验矩阵ＨＱＣ为ＨＱＣ＝Ｈ１１ Ｈ１ｊ︙⋱︙Ｈｉ１Ｈｉｊéëêêêêùûúúúú定义９Ｐｏｌａｒ码㊂极化码（Ｐｏｌａｒｃｏｄｅ）［１３］是一种信道编码方法，最早由土耳其Ａｒｉｋａｎ［１４］于２００９年提出，其在理论上具有无限接近于香农限的独特性质㊂Ｐｏｌａｒ码的原理是信道极化［１５］㊂在信道极化中，有两个重要参数信道容量Ｉ（Ｗ）和巴氏参数Ｚ（Ｗ）㊂给定一个Ｂ⁃ＤＭＣ信道，如Ｗ：ＸңＹ，Ｘ和Ｙ为输入和输出㊂令Ｗ（Ｙ｜Ｘ）为信道转移概率，其中Ｘɪ｛０，１｝㊂对信道Ｗ，信道的参数为信道容量Ｉ（Ｗ）和巴氏参数Ｚ（Ｗ），则Ｉ（Ｗ）≜ðｙɪＹðｘɪＸ１２Ｗ（ｙ｜ｘ）ｌｏｇＷｙｘ()１２Ｗｙ０()＋１２Ｗｙ１()Ｚ（Ｗ）≜ðｙɪＹＷｙ０()Ｗｙ１()２㊀编码中的困难问题㊀㊀基于编码的困难问题［１６］是一类量子计算机无法有效求解的ＮＰ完全问题㊂大多数编码的困难问题是源于ＳｙｎｄｒｏｍｅＤｅｃｏｄｉｎｇ（ＳＤ）问题，它已经被证明是ＮＰ完全问题㊂本节将介绍３种常见的编码困难问题，分别是校验子译码（ＳＤ）困难问题㊁准循环码的校验子译码（ＱＣＳＤ）困难问题和准循环秩码的校验子译码（ＲＱＣＳＤ）困难问题㊂ＮＩＳＴ中的大部分参数方案都是基于以上的三个问题㊂２ １㊀ＳＤ困难问题Ｈ是有限域Ｆ上的随机线性码Ｃ的（ｎ－ｋ）ˑｎ的校验矩阵，ｓɪＦｎ－ｋ，找一个重量小于ｄ的字ｘɪＦｎ使得ＨｘＴ＝ｓ㊂２ ２㊀ＱＣＳＤ困难问题Ｈ是有限域Ｆ上的准循环码Ｃ的（ｎ－ｋ）ˑｎ的准循环校验矩阵，ｓɪＦｎ－ｋ，找一个汉明重量小于ｄ的字ｘɪＦｎ使得ＨｘＴ＝ｓ㊂ＱＣＳＤ问题的困难性虽未得到严格证明，但对于准循环（ＱＣ）码的矩阵，ＳＤ问题仍然适用，目前也没有对其有效的攻击算法㊂２ ３㊀ＲＱＣＳＤ困难问题Ｈ是有限域Ｆｑ上的准循环码Ｃ的（ｎ－ｋ）ˑｎ的准循环校验矩阵，ｓɪＦｎ－ｋｑ，找一个秩重量小于ｄ的字ｘɪＦｎｑ使得ＨｘＴ＝ｓ㊂ＲＱＣＳＤ问题与上一问题的区别在于这里是在秩距离下，而上者是汉明距离㊂３㊀ＭｃＥｌｉｅｃｅ和Ｎｉｅｄｅｒｒｅｉｔｅｒ加密方式㊀㊀在基于编码的公钥密码算法中，包括三种常见的构造模式㊂其中ＭｃＥｌｉｅｃｅ型和Ｎｉｅｄｅｒｒｅｉｔｅｒ型出现较早，对其讨论也比较充分㊂这两种算法设计思路比较明确，但它们是直接通过隐藏码的结构来保证方案的安全性，这就对码的结构要求㊃３㊃北京电子科技学院学报２０２３年十分严格，并且存在破解的可能㊂目前这两种方式又可以分为原始方案与现代方案，主要区别在于现代方案使用的码字为系统码，其生成矩阵和校验矩阵具有Ｇ＝（Ｉｋ Ｘ）和Ｈ＝（－ＸＴＩｎ－ｋ）的形式，因此可以减少部分密钥量㊂３ １㊀ＭｃＥｌｉｅｃｅ型加密方案３ １ １㊀原始方案密钥生成：生成一个能纠ｔ个错的［ｎ，ｋ］线性码ς的生成矩阵Ｇ；私钥ｓｋ，（Ｓ，Ｇ，Ｐ），其中Ｓ是一个混淆可逆矩阵，Ｐ是一个置换矩阵；公钥ｐｋ：Ｇ ＝Ｓ㊃Ｇ㊃Ｐ㊂加密：给定一个明文ｍ和一个重量ｗ（ｅ）ɤｔ的噪声向量ｅ，密文为ｃѳｍＧ ＋ｅ㊂解密：令ΦＧ是能纠ｔ个错误的译码算法，则明文可通过如下过程解密得到ｍѳΦＧ（ｃＰ－１）Ｓ－１㊂３ １ ２㊀现代方案密钥生成：给定一个能纠ｔ个错的［ｎ，ｋ］线性码ς的生成矩阵Ｇ；私钥ｓｋ，Ｇ；公钥ｐｋ，Ｇᶄ＝（ＩＱ）为Ｇ的标准型㊂加密：给定要加密的明文ｍ，一个重量ｗ（ｅ）ɤｔ的噪声向量ｅ，密文通过如下过程获得ｃѳｍＧᶄ＋ｅ㊂解密：令ΦＧ是能纠ｔ个错误的译码算法，则明文可通过如下过程解密得到ｍѳΦＧ（ｃ）㊂３ ２㊀Ｎｉｅｄｅｒｒｅｉｔｅｒ型加密方案３ ２ １㊀原始方案密钥生成：给定一个能纠ｔ个错的［ｎ，ｋ］线性码ς的校验矩阵Ｈ；私钥ｓｋ，（Ｓ，Ｈ，Ｐ），其中Ｓ是混淆可逆矩阵，Ｐ是一个置换矩阵；公钥ｐｋ，Ｈ＝Ｓ㊃Ｈ㊃Ｐ㊂加密：重量ｗｔ（ｅ）ɤｔ的噪声向量ｅ，被用来表示明文信息ｍ，密文为ｓѳＨᶄｅＴ㊂解密：令ΦＨ是能纠ｔ个错误的译码算法，则明文可通过如下过程解密得到ｅѳＰ－１ΦＨ（Ｓ－１ｓ）㊂３ ２ ２㊀现代方案密钥生成：给定一个能纠ｔ个错的［ｎ，ｋ］线性码ς的校验矩阵Ｈ；私钥ｓｋ，Ｈ；公钥ｐｋ，Ｈᶄ＝［Ｑ｜Ｉｎ－ｋ］ѳＨ㊂加密：重量ｗ（ｅ）ɤｔ的噪声向量ｅ，被用来表示明文信息ｍ，密文ｓ通过如下过程获得ｓѳＨᶄｅＴ㊂解密：令ΦＨ是能纠ｔ个错误的译码算法，则明文可通过如下过程解密得到ｅѳΦＨ（ｓ）㊂４㊀ＥｌＧａｍａｌ型加密方式㊀㊀２０１７年，ＣａｒｌｏｓＡｇｕｉｌａｒ等人提出了第一个安全性依赖于随机准循环码译码的高效密码系统［１７］，即ＥｌＧａｍａｌ型密码系统，随之又出现了ＥｌＧａｍａｌ型的ＨＱＣ和ＲＱＣ［１８］算法㊂Ｂａｒｒｅｔｏ［１９］等人提出了ＥｌＧａｍａｌ型的ＣＡＫＥ算法，Ｊｅａｎ⁃ＣｈｒｉｓｔｏｐｈｅＤｅｎｅｕｖｉｌｌｅ提出了ＥｌＧａｍａｌ型的Ｏｕ⁃ｒｏｂｏｒｏｓ［２０］算法，ＮｉｃｏｌａｓＡｒａｇｏｎ等人提出的ＢＩＫＥ算法，其中第二轮中ＢＩＫＥ３是以Ｏｕｒｏｂｏｒｏｓ算法为基础进行改进的ＥｌＧａｍａｌ型算法㊂２０１９年，王丽萍等人提出了秩距离下的ＥｌＧａｍａｌ型Ｐｉｇｌｅｔ－１算法㊂ＥｌＧａｍａｌ型加密方式与另外两种加密方式不同之处在于采用了两个独立的码㊂其中随机拟循环码不需要解密，保证了方案的安全性；而公开码Ｃ（或ＱＣ⁃ＭＤＰＣ码）保证了算法的正确性，对效率有很大影响㊂它让使用难以隐藏但译码效率很高的公开码成为可能㊂与之相比，ＭｃＥｌｉｅｃｅ型和Ｎｉｅｄｅｒｒｅｉｔｅｒ型方案的编译码方法是固定的㊂同时ＥｌＧａｍａｌ型采用的公私钥是临时密钥，每次密钥交换时都会生成一个新的密钥对，这意味着ＥｌＧａｍａｌ型方式在信息传输时的密钥是不断更新的，这样可有效抵御ＧＪＳ攻击㊂４ １㊀ＥｌＧａｍａｌ型加密方式概况ＥｌＧａｍａｌ型方案又可以分两类㊂㊃４㊃第３１卷基于编码的ＥｌＧａｍａｌ型公钥密码体制研究概述㊀４ １ １㊀版本一（以ＨＱＣ㊁Ｐｉｇｌｅｔ－１等为代表）密钥生成：随机取样ｈƔѳＲ＝Ｆ２［Ｘ］／（Ｘｎ－１），ＧɪＦｋˑｎ２是具有快速译码算法的编码Ｃ在Ｒ上的生成矩阵；私钥ｓｋ，（ｘ，ｙ）ƔѳＲ２且ω（ｘ）＝ω（ｙ）＝ｗ；公钥ｐｋ，（ｈ，ｓ＝ｙ＋ｈ㊃ｘ），得到（ｐｋ，ｓｋ）㊂加密：生成噪声向量ｅƔѳＲ㊁（ｒ１，ｒ２）ƔѳＲ２使得ω（ｅ）＝ｗｅ，ω（ｒ１）＝ω（ｒ２）＝ｗｒ，密文（ｃ１，ｃ２），ｃ１＝ｒ１＋ｈ㊃ｒ２，ｃ２＝ｍＧ＋ｓ㊃ｒ２＋ｅ，得到ｃ＝（ｃ１，ｃ２）㊂解密：令ＤＧ是码Ｃ的能纠δ个错误的译码算法，解密如下ｍѳＤＧ（ｃ２－ｃ１㊃ｘ）＝ＤＧ（ｍＧ＋ｙｒ２－ｒ１ｘ＋ｅ），返回ＤＧ（ｃ２－ｃ１㊃ｘ）㊂４ １ ２㊀版本二（以Ｏｕｒｏｂｏｒｏｓ，ＢＩＫＥ第二轮算法３为代表）密钥生成：随机取样ｈƔѳＲ＝Ｆ２［Ｘ］／（Ｘｎ－１），；私钥ｓｋ，（ｘ，ｙ）ƔѳＲ２且ω（ｘ）＝ω（ｙ）＝ｗ；公钥ｐｋ，（ｈ，ｓ＝ｙ＋ｈ㊃ｘ），得到（ｐｋ，ｓｋ）㊂加密：生成噪声向量ｅƔѳＲ㊁（ｒ１，ｒ２）ƔѳＲ２使得ω（ｅ）＝ｗｅ，ω（ｒ１）＝ω（ｒ２）＝ｗｒ，密文（ｃ１，ｃ２），ｃ１＝ｒ１＋ｈ㊃ｒ２，ｃ２＝ｓ㊃ｒ２＋ｅ，得到ｃ＝（ｃ１，ｃ２）㊂解密：对（ｃ２－ｃ１㊃ｙ）进行译码，得到ｅ和（ｒ１，ｒ２）㊂４ ２㊀正确性验证以版本一为例，版本二类似㊂假设合法的接收者可以使用ｓｋ从消息的噪声编码ｃ２中去除足够多的错误，系统的正确性可以得到保证㊂此方案的正确性显然依赖于码Ｃ的译码能力㊂特别的，假定码Ｃ正确译码ｃ２－ｃ１㊃ｙ，则有Ｄｅｃｒｙｐｔ（ｓｋ，Ｅｎｃｒｙｐｔ（ｐｋ，ｍ））＝ｍ㊂要使码Ｃ正确译码ｃ２－ｃ１㊃ｙ，还需满足以下条件：ω（ｓ㊃ｒ２－ｍ㊃ｙ＋ｅ）ɤδ，即ω（ｘ㊃ｒ２－ｒ１㊃ｙ＋ｅ）ɤδ，此条件将通过译码失败概率分析（以足够大的概率）得到保证㊂４ ３㊀设计特点与传统的ＭｃＥｌｉｅｃｅ和Ｎｉｅｄｅｒｒｅｉｔｅｒ型方案相比，ＥｌＧａｍａｌ型方案具有一些新的设计特点，从而进一步提高了方案的安全性㊂其中临时密钥的采用和不需隐藏码的结构是其中两个主要特点㊂使用临时密钥在安全性方面的提升主要体现在可以抵御ＧＪＳ攻击［２１］㊂ＧＪＳ攻击全称为密钥恢复攻击，是指Ａ采用公钥加密消息并将密文发给Ｂ，在这一过程中如果产生译码上的错误，Ｂ会给Ａ反馈㊂如果攻击者Ｃ假扮成Ａ向Ｂ发密文，并从Ｂ的反馈中收集译码错误信息，通过收集大量译码错误信息，攻击者Ｃ便能恢复出方案的私钥㊂ＭｃＥｌｉｅｃｅ和Ｎｉｅｄｅｒｒｅｉｔｅｒ型方案不能抵御ＧＪＳ攻击，原因是其在传输过程中的密钥是固定的㊂而ＥｌＧａｍａｌ型采用了传输时不断更新的临时密钥，ＧＪＳ的攻击者最多只有一次观察解密的机会，因此无法创建关于不同错误模式的统计信息，ＧＪＳ攻击本质上是失效的㊂在ＭｃＥｌｉｅｃｅ和Ｎｉｅｄｅｒｒｅｉｔｅｒ型方案加密框架中，是通过直接隐藏码的结构（通过给码的生成矩阵或校验矩阵进行变换）来保证安全性，这使得算法安全性依赖于隐藏码的结构，解密算法由译不可更改的隐藏码组成㊂这种方式使其面临攻击，存在安全隐患㊂而ＥｌＧａｍａｌ型框架中，安全性寄托在不需译码的随机ＱＣ码上，而需要进行编译码的码Ｃ是公开参数，不需要进行保密，这就进一步提高了其安全性㊂４ ４㊀信息位编码方式版本一的信息位为ｍ，版本二的有效信息为ｅ和（ｒ１，ｒ２）㊂如果用于混合加密中的对称密钥生成，信息位可如以上算法所示随机产生㊂如果用于信息传输在版本二中会涉及到等重编码［２２］的问题㊂等重码是将信息编码为具有规定重量的码字的方法㊂令ｑ为整数，Ｃ集合如果是ｗ＝（ｗ１，ｗ２， ，ｗｎ）ɪ｛０，１｝ｎ{：ðｎｉ＝１ｗｉ＝ｑ}的子集，则称Ｃ为长度为ｎ，重量为ｑ的等重码其㊃５㊃北京电子科技学院学报２０２３年构造方法可参考文献［２２］等㊂在版本二中，因为错误向量ｅ和（ｒ１，ｒ２）都有重量要求，所以必须先将信息编码为具有特定重量的码字才能使用版本二传输特定信息㊂４ ５㊀ＥｌＧａｍａｌ体制中涉及的编译码在版本一中包含了两类码㊂一个是［ｎ，ｋ］码Ｃ，它需要进行编码和译码，为此需要具有高效译码算法ＤＧ㊂码Ｃ和它的生成矩阵是公开的，对安全性没有影响㊂第二种码是随机ＱＣ码㊂从公钥求解私钥，以及在只有公钥情况下从密文破解明文可以视为随机拟循环码的译码问题，无法进行有效译码㊂总体思路是通过拟循环码生成噪声，生成的噪声可被码Ｃ译码㊂对算法进行优化的一个思路是选择具有更优纠错能力和快速算法的公开码Ｃ，比如Ｐｏｌａｒ码㊂Ｐｏｌａｒ码具有达到香农极限的编码效率，有利于进一步压缩密钥量，同时保持快速的编译码㊂Ｐｏｌａｒ码的译码可采用ＳＣ译码［２３］算法㊂在版本二同样存在两类编码㊂与安全相关的随机拟循环码与上面类似㊂版本二中不需要构造公开码Ｃ，但需要对（ｙｒ２－ｒ１ｘ＋ｅ）进行译码，在私钥（ｘ，ｙ）已知的情况下恢复ｅ和（ｒ１，ｒ２）为ＱＣ⁃ＭＤＰＣ码译码问题，即带噪声的校验子译码㊂准循环性不会改变译码算法，但因为存在额外的噪声ｅ，此为带噪声的校验子译码㊂噪声校验子译码是校验子译码的一种变体，在给定Ｈ和ｓ的情况下，需寻找ｅɪＦｎ２，使ｓ－ｅＨＴ和ｅ都具有较小的重量㊂比特翻转算法在进行修改后同样适用于噪声校验子译码［４］㊂４ ６㊀安全归约一个编码方案的安全性要归结到它的困难问题㊂ＥｌＧａｍａｌ型密码体制在进行加解密时所使用的是随机拟循环（ＱＣ）码，所以其困难问题可以归结到ＱＣＳＤ问题或者ＲＱＣＳＤ问题㊂选择明文攻击下的不可区分性（ＩＮＤ⁃ＣＰＡ）通常通过以下的游戏来证明：攻击者Ａ选择两个明文μ０和μ１，并将它们发送给的挑战者，挑战者随机决定ｂɪ｛０，１｝的值，将μｂ加密为密文ｃ，并将ｃ返回给Ａ㊂如果Ａ在决定密文ｃ加密哪个明文时具有可以忽略的优势，则认为该加密方案是ＩＮＤ⁃ＣＰＡ安全的㊂汉明距离下的Ｅｌ⁃Ｇａｍａｌ型方案在ＱＣＳＤ假设下的ＩＮＤ⁃ＣＰＡ㊂在ＥｌＧａｍａｌ型体制中，已知公钥（ｈ，ｓ＝ｙ＋ｈ㊃ｘ），求解私钥（ｘ，ｙ），即为已知随机ＱＣ码的校验矩阵（１，ｈ）和伴随式ｓ，求解满足重量要求的向量（ｘ，ｙ）㊂而已知公钥和密文（ｃ１，ｃ２）＝（ｒ１＋ｈ㊃ｒ２，ｍＧ＋ｓ㊃ｒ２＋ｅ）求解明文的过程，可以归结为在校验矩阵（１０ｈ０１ｓ）和伴随式（ｃ１，ｃ２－ｍＧ）已知下求解满足重量要求的向量（ｒ１，ｅ，ｒ２）．很明显，以上均为ＱＣＳＤ问题㊂以上为对汉明距离下的方案的分析，秩距离下可以类比完成㊂４ ７㊀译码失败概率由算法可知，要想正确译码，需要满足ω（ｘ㊃ｒ２－ｒ１㊃ｙ＋ｅ）ɤδ㊂与ＭｃＥｌｉｅｃｅ型和Ｎｉｅｄｅｒｒｅ⁃ｉｔｅｒ型相比，ＥｌＧａｍａｌ型体制必然存在着译码失败概率（ＤＦＲ），需要将其限定在２－λ以下，其中λ为算法的设计安全强度㊂对译码失败概率进行分析，目前的主要方法包括理论分析和实验分析两种㊂在理论分析中，首先假设误差向量ｅᶄ的每个固定坐标ｅᶄｋ的概率分布为伯努利分布，参数ｐ∗＝Ｐ［ｅᶄｋ＝１］，利用参数ｐ∗的二项分布来估算ｅᶄ的重量分布㊂而在实验中，由于译码失败概率通常较小，直接进行标准参数下的实验测量所需数据量过大以至无法实现㊂通常的方法是首先进行短码下的测试，然后利用外推法来估算长码的情况，总体来看所得结果较实际情况保守㊂由于译码失败概率估计的复杂性，目前两种方法都无法得到精准的结果，这也在一定程度上限定了密钥尺寸的进一步压缩㊂因此对此问题进行研究也成为了ＥｌＧａｍａｌ型方案应用研究的重要方面㊂㊃６㊃第３１卷基于编码的ＥｌＧａｍａｌ型公钥密码体制研究概述㊀４ ８㊀参数选取码长等参数的选择会影响密钥尺寸和编译码复杂度，从而对安全性和效率都有较大影响㊂一方面，出于结构性原因，实际攻击的复杂性会随着码长的增加而迅速增长㊂特别是拟循环码有其特殊的结构，面对特定的结构攻击会有很大的危险，需要保持一定的安全冗余㊂另一方面，计算量会随着系统规模的增加而增加，所以它可以表示成系统规模的函数，常用规模的幂方数来度量计算量的大小㊂所以，参数选择是基于编码的公钥密码设计的重要部分㊂对参数的选取要考虑的内容有安全性㊁解码效率㊁占用空间等㊂最终的参数要综合考虑有高解码效率，不易被攻破又尽可能小的占据密钥空间㊂在设定参数时，最重要的要素是考虑方案针对现有攻击的抵抗强度，同时考虑满足译码失败概率的要求㊂信息集译码［２４］（ＩＳＤ）是目前对于编码最有效的攻击方法㊂基本思想是将校验矩阵变为系统形式，再进行信息位匹配和校验位匹配㊂最简单的ＩＳＤ形式是１９６２年Ｐｒａｎｇｅ提出的，它试图猜测码中设置的无错误信息㊂根据定义，信息集是确定整个码字的位置集㊂如果该集合避免了密文中的所有错误位置，则该集合是无错误的；那么这些位置上的密文就是这些位置上的码字㊂攻击者通过线性运算确定码字的其余部分，并通过检查错误权值是否为ｔ来判断攻击是否成功㊂对于ｋ／ｎ＝１／２的算法，通用的信息集译码算法的复杂度为ＷＦＡ（ｎ，ｋ，ｔ）＝２ｃｔ（１＋ｏ（１））ｃ取决于算法，编码率Ｒ＝ｋ／ｎ和错误率ｔ／ｎ㊂对于次线性（ｔʈｎ）的情况，可取Ｃ＝ｌｏｇ２１１－Ｒ而针对ＥｌＧａｍａｌ型算法中所采用的ＱＣ码，需要考虑针对其循环结构的特殊译码算法㊂ＤｅｃｏｄｉｎｇＯｎｅＯｕｔｏｆＭａｎｙ（ＤＯＯＭ）［２５］算法就针对准循环结构，对产生循环结构的多项式进行攻击，ＱＣ码比起随机码的信息集译码方式快ｒ倍，尤其当多项式有多个低次因子更有效㊂因此准循环码在选取参数时需使（Ｘｒ－１）／（Ｘ－１）ɪＦ２［Ｘ］不可约，防止使用ＤＯＯＭ算法快速破解准循环结构㊂在能够抵抗以上攻击方法的前提下，同时考虑译码失败概率满足安全强度要求，可以反推参数选择范围㊂如在安全参数λ的要求下，ＥｌＧａｍａｌ类型码长为Ｏ（λ２），对应公钥长度为Ｏ（λ２），与之相比，基于Ｇｏｐｐａ码的ＭｃＥｌｉｅｃｅ类型分别为Ｏ（λｌｏｇλ）和Ｏ（λ２（ｌｏｇλ）２）㊂需要指出的是，目前典型的ＥｌＧａｍａｌ型算法的安全性均建立在拟循环码译码的基础上，因此其参数选择范围相近㊂如在２１２８强度下，ＨＱＣ的（ｎ，ｗ）参数为（１７６６９，６６），ＢＩＫＥ－３为（２４５３８，６７），其中ｎ为码长，ｗ为错误向量ｘ和ｙ重量㊂与之相比，其设计灵活性更加体现在公开码Ｃ的选择等方面㊂５㊀结语㊀㊀基于编码的公钥密码算法能有效抵抗量子算法的攻击，目前已有许多高效且安全的基于编码的公钥加密算法，是后量子密码算法的主流方向之一㊂本文先介绍了基于编码的公钥密码算法的背景，然后对加密方式㊁编码困难问题做了简要回顾㊂目前对ＭｃＥｌｉｅｃｅ型和Ｎｉｅｄｅｒｒｅｉｔｅｒ型研究地较为充分，相比较，对ＥｌＧａｍａｌ型加密方式的相关工作较少，ＥＩＧａｍａｌ型加密使用临时密钥，并且不需要在公开的矩阵中隐藏码结构，具有一定的优势，本文以ＥｌＧａｍａｌ型公钥加密方式为重点，对其正确性㊁安全性及译码失败概率等方面进行了总结㊂并给出后续设计和分析中需要注意的问题，主要包括：（１）译码失败概率对算法性能有重要影响，需要从理论和实验方面给出更为精确的结果；（２）利用编码理论发展的最新结果，选择更为高效的码字Ｃ，对提高算法的㊃７㊃北京电子科技学院学报２０２３年实现效率有重要帮助；（３）通过等重码等方式对错误向量进行编码，有可能进一步提高传输效率，等等㊂通过本文，希望可以为基于编码的Ｅｌ⁃Ｇａｍａｌ型方案的设计与分析打下基础㊂参考文献［１］㊀ＣＨＥＮＬ，ＪＯＲＤＡＮＳ，ｅｔａｌ．ＲｅｐｏｒｔｏｎＰｏｓｔ⁃ＱｕａｎｔｕｍＣｒｙｐｔｏｇｒａｐｈｙ［Ｍ］．Ｗａｓｈｉｎｇｔｏｎ：ＵＳＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｍｅｒｃｅ，ＮａｔｉｏｎａｌＩｎｓｔｉｔｕｔｅｏｆＳｔａｎｄａｒｄｓａｎｄＴｅｃｈｎｏｌｏｇｙ，２０１６．［２］㊀ＡＬＡＧＩＣＧ，ＡＬＰＥＲＩＮＪ，ｅｔａｌ．ＳｔａｔｕｓＲｅｐｏｒｔｏｎｔｈｅＦｉｒｓｔＲｏｕｎｄｏｆｔｈｅＮＩＳＴＰｏｓｔ⁃ＱｕａｎｔｕｍＣｒｙｐｔｏｇｒａｐｈｙＳｔａｎｄａｒｄｉｚａｔｉｏｎＰｒｏｃｅｓｓ［Ｍ］．Ｗａｓｈｉｎｇｔｏｎ：ＵＳＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｍｅｒｃｅ，ＮａｔｉｏｎａｌＩｎｓｔｉｔｕｔｅｏｆＳｔａｎｄａｒｄｓａｎｄＴｅｃｈｎｏｌｏｇｙ，２０１９．［３］㊀王丽萍，戚艳红．基于编码的后量子公钥密码研究进展［Ｊ］．信息安全学报，２０１９，４（２）．［４］㊀ＡｒａｇｏｎＮ，ＢａｒｒｅｔｏＰ，ＢｅｔｔａｉｅｂＳ，ｅｔａｌ．ＢＩＫＥ：ｂｉｔｆｌｉｐｐｉｎｇｋｅｙｅｎｃａｐｓｕｌａｔｉｏｎ［Ｊ／ＯＬ］．（２０１７－１２－２２）［２０２１－３－１０］．ｈｔｔｐｓ：／／ｈａｌ．ａｒｃｈｉｖｅｓ⁃ｏｕｖｅｒｔｅｓ．ｆｒ／ｈａｌ－０１６７１９０３．［５］㊀ＣｈｏｕＴ，ＣｉｄＣ，ＵｉｂＳ，ｅｔａｌ．ＣｌａｓｓｉｃＭｃＥ⁃ｌｉｅｃｅ：ｃｏｎｓｅｒｖａｔｉｖｅｃｏｄｅ⁃ｂａｓｅｄｃｒｙｐｔｏｇｒａｐｈｙ［Ｊ／ＯＬ］．（２０２０－１０－１０）［２０２１－３－１０］．ｈｔ⁃ｔｐｓ：／／ｃｌａｓｓｉｃ．ｍｃｅｌｉｅｃｅ．ｏｒｇ／ｎｉｓｔ／ｍｃｅｌｉｅｃｅ－２０２０１０１０．ｐｄｆ．［６］㊀ＭｅｌｃｈｏｒＣＡ，ＡｒａｇｏｎＮ，ＢｅｔｔａｉｅｂＳ，ｅｔａｌ．Ｈａｍｍｉｎｇｑｕａｓｉ⁃ｃｙｃｌｉｃ（ＨＱＣ）［Ｊ］．ＮＩＳＴＰＱＣＲｏｕｎｄ，２０１８，２：４－１３．［７］㊀ＭｃＥｌｉｅｃｅＲＪ．ＡＰｕｂｌｉｃ⁃ＫｅｙＣｒｙｐｔｏｓｙｓｔｅｍｂａｓｅｄｏｎＡｌｇｅｂｒａｉｃＣｏｄｉｎｇＴｈｅｏｒｙ［Ｊ］．ＤｅｅｐＳｐａｃｅＮｅｔｗｏｒｋＰｒｏｇｒｅｓｓＲｅｐｏｒｔ，１９７８，４４：１１４－１１６．［８］㊀ＭｃＥｌｉｅｃｅＲＪ．Ｔｈｅｔｈｅｏｒｙｏｆｉｎｆｏｒｍａｔｉｏｎａｎｄｃｏｄｉｎｇ［Ｍ］．Ｃａｍｂｒｉｄｇｅ，ＵＫ：ＣａｍｂｒｉｄｇｅＵｎｉ⁃ｖｅｒｓｉｔｙＰｒｅｓｓ，２００２：１３９－２２８．［９］㊀ＲｏｂｉｎｓｏｎＤＪＳ．Ａｎｉｎｔｒｏｄｕｃｔｉｏｎｔｏａｂｓｔｒａｃｔａｌｇｅｂｒａ［Ｍ］．Ｂｅｒｌｉｎ：ＷａｌｔｅｒｄｅＧｒｕｙｔｅｒ，２００８：２５５－２６６．［１０］㊀ＧＡＢＯＲＩＴＰ，ＨＡＵＴＥＶＩＬＬＥＡ，ＰＨＡＮＤＨ，ｅｔａｌ．Ｉｄｅｎｔｉｔｙ⁃ｂａｓｅｄｅｎｃｒｙｐｔｉｏｎｆｒｏｍｃｏｄｅｓｗｉｔｈｒａｎｋｍｅｔｒｉｃ［Ｃ］／／Ｔｈｅ３７ｔｈＡｎｎｕａｌＩｎｔｅｒ⁃ｎａｔｉｏｎａｌＣｒｙｐｔｏｌｏｇｙＣｏｎｆｅｒｅｎｃｅ（ＣＲＹＰＴＯ）．２０１７：１９４－２２４．［１１］㊀ＭｉｓｏｃｚｊｉＲ，ＴｉｌｌｉｃｈＪＰ，ＳｅｎｄｒｉｅｒＮ，ｅｔａｌ．ＭＤ⁃ＰＣ⁃ＭｃＥｌｉｅｃｅ：ＮｅｗＭｃＥｌｉｅｃｅｖａｒｉａｎｔｓｆｒｏｍｍｏｄｅｒａｔｅｄｅｎｓｉｔｙｐａｒｉｔｙ⁃ｃｈｅｃｋｃｏｄｅｓ［Ｃ］／／２０１３ＩＥＥＥｉｎｔｅｒｎａｔｉｏｎａｌｓｙｍｐｏｓｉｕｍｏｎｉｎｆｏｒ⁃ｍａｔｉｏｎｔｈｅｏｒｙ．Ｉｓｔａｎｂｕｌ：ＩＥＥＥ，２０１３：２０６９－２０７３．［１２］㊀ＧａｌｌａｇｅｒＲ．Ｌｏｗ⁃ｄｅｎｓｉｔｙｐａｒｉｔｙ⁃ｃｈｅｃｋｃｏｄｅｓ［Ｊ］．ＩＲＥＴｒａｎｓａｃｔｉｏｎｓｏｎｉｎｆｏｒｍａｔｉｏｎｔｈｅｏｒｙ，１９６２，８（１）：２１－２８．［１３］㊀ＨＯＯＳＨＭＡＮＤＲ，ＡＲＥＦＭＲ．ＥｆｆｉｃｉｅｎｔＰｏｌａｒＣｏｄｅ⁃ＢａｓｅｄＰｈｙｓｉｃａｌＬａｙｅｒＥｎｃｒｙｐｔｉｏｎＳｃｈｅｍｅ［Ｊ］．ＩＥＥＥＷｉｒｅｌｅｓｓＣｏｍｍｕｎｉｃａｔｉｏｎｓＬｅｔｔｅｒｓ，２０１７，６（６）：７１０－７１３．［１４］㊀ＡＲＩＫＡＮＥ．ＣｈａｎｎｅｌＰｏｌａｒｉｚａｔｉｏｎ：ＡＭｅｔｈｏｄｆｏｒＣｏｎｓｔｒｕｃｔｉｎｇＣａｐａｃｉｔｙＡｃｈｉｅｖｉｎｇＣｏｄｅｓｆｏｒＳｙｍｍｅｔｒｉｃＢｉｎａｒｙ⁃ＩｎｐｕｔＭｅｍｏｒｙｌｅｓｓＣｈａｎｎｅｌｓ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｆｏｒｍａｔｉｏｎＴｈｅｏｒｙ，２００９，５５（７）：３０５１－３０７３．［１５］㊀ＨｏｏｓｈｍａｎｄＲ，ＡｒｅｆＭＲ．Ｐｏｌａｒｃｏｄｅ⁃ｂａｓｅｄｓｅｃｕｒｅｃｈａｎｎｅｌｃｏｄｉｎｇｓｃｈｅｍｅｗｉｔｈｓｍａｌｌｋｅｙｓｉｚｅ［Ｊ］．ＩＥＴＣｏｍｍｕｎｉｃａｔｉｏｎｓ，２０１７，１１（１５）：２３５７－２３６１．［１６］㊀ＳＥＮＤＲＩＥＲＮ．Ｃｏｄｅ⁃ｂａｓｅｄｃｒｙｐｔｏｇｒａｐｈｙ：ｓｔａｔｅｏｆｔｈｅａｒｔａｎｄｐｅｒｓｐｅｃｔｉｖｅｓ［Ｊ］．ＩＥＥＥＳｅ⁃ｃｕｒｉｔｙ＆Ｐｒｉｖａｃｙ，２０１７，１５（４）：４４－５０．［１７］㊀ＣａｒｌｏｓＡｇｕｉｌａｒ⁃Ｍｅｌｃｈｏｒ，ＯｌｉｖｉｅｒＢｌａｚｙ，Ｊｅａｎ⁃ＣｈｒｉｓｔｏｐｈｅＤｅｎｅｕｖｉｌｌｅ，ＰｈｉｌｉｐｐｅＧａｂｏｒｉｔ，ａｎｄＧｉｌｌｅｓＺ ｍｏｒ．Ｅｆｆｉｃｉｅｎｔｅｎｃｒｙｐｔｉｏｎｆｒｏｍｒａｎｄｏｍｑｕａｓｉ⁃ｃｙｃｌｉｃｃｏｄｅｓ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｆｏｒｍａｔｉｏｎＴｈｅｏｒｙ，６４（５）：３９２７－３９４３，２０１８．㊃８㊃第３１卷基于编码的ＥｌＧａｍａｌ型公钥密码体制研究概述㊀［１８］㊀Ａｇｕｉｌａｒ⁃ＭｅｌｃｈｏｒＣ，ＢｌａｚｙＯ，ＤｅｎｅｕｖｉｌｌｅＪＣ，ｅｔａｌ．Ｅｆｆｉｃｉｅｎｔｅｎｃｒｙｐｔｉｏｎｆｒｏｍｒａｎｄｏｍｑｕａｓｉ⁃ｃｙｃｌｉｃｃｏｄｅｓ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｆｏｒ⁃ｍａｔｉｏｎＴｈｅｏｒｙ，２０１８，６４（５）：３９２７－３９４３．［１９］㊀ＢａｒｒｅｔｏＰＳＬＭ，ＧｕｅｒｏｎＳ，ＧｕｎｅｙｓｕＴ，ｅｔａｌ．Ｃａｋｅ：Ｃｏｄｅ⁃ｂａｓｅｄａｌｇｏｒｉｔｈｍｆｏｒｋｅｙｅｎｃａｐｓｕｌａ⁃ｔｉｏｎ［Ｃ］／／ＩＭＡＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＣｒｙｐｔｏｇｒａｐｈｙａｎｄＣｏｄｉｎｇ．Ｃｈａｍ：Ｓｐｒｉｎｇｅｒ，２０１７：２０７－２２６．［２０］㊀ＤｅｎｅｕｖｉｌｌｅＪＣ，ＧａｂｏｒｉｔＰ，Ｚ ｍｏｒＧ．Ｏｕｒｏｂｏ⁃ｒｏｓ：Ａｓｉｍｐｌｅ，ｓｅｃｕｒｅａｎｄｅｆｆｉｃｉｅｎｔｋｅｙｅｘ⁃ｃｈａｎｇｅｐｒｏｔｏｃｏｌｂａｓｅｄｏｎｃｏｄｉｎｇｔｈｅｏｒｙ［Ｃ］／／Ｐｏｓｔ⁃ＱｕａｎｔｕｍＣｒｙｐｔｏｇｒａｐｈｙ：８ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＷｏｒｋｓｈｏｐ，ＰＱＣｒｙｐｔｏ２０１７，Ｕｔｒｅｃｈｔ，ＴｈｅＮｅｔｈｅｒｌａｎｄｓ，Ｊｕｎｅ２６－２８，２０１７，Ｐｒｏｃｅｅｄｉｎｇｓ８．ＳｐｒｉｎｇｅｒＩｎｔｅｒｎａｔｉｏｎａｌＰｕｂｌｉｓｈｉｎｇ，２０１７：１８－３４．［２１］㊀ＧｕｏＱｉａｎ，ＪｏｈａｎｓｓｏｎＴ，ＳｔａｎｋｏｖｓｋｉＰ．ＡｋｅｙｒｅｃｏｖｅｒｙａｔｔａｃｋｏｎＭＤＰＣｗｉｔｈＣＣＡｓｅｃｕｒｉｔｙｕｓｉｎｇｄｅｃｏｄｉｎｇｅｒｒｏｒｓ［Ｃ］／／ＰｒｏｃｏｆＩｎｔｅｒｎａ⁃ｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎｔｈｅＴｈｅｏｒｙａｎｄＡｐｐｌｉｃａｔｉｏｎｏｆＣｒｙｐｔｏｌｏｇｙａｎｄＩｎｆｏｒｍａｔｉｏｎＳｅ⁃ｃｕｒｉｔｙ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，２０１６：７８９－８１５．［２２］㊀ＴｉａｎＣ，ＶａｉｓｈａｍｐａｙａｎＶＡ，ＳｌｏａｎｅＮＪＡ．Ａｃｏｄｉｎｇａｌｇｏｒｉｔｈｍｆｏｒｃｏｎｓｔａｎｔｗｅｉｇｈｔｖｅｃｔｏｒｓ：Ａｇｅｏｍｅｔｒｉｃａｐｐｒｏａｃｈｂａｓｅｄｏｎｄｉｓｓｅｃｔｉｏｎｓ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｆｏｒｍａｔｉｏｎＴｈｅｏｒｙ，２００９，５５（３）：１０５１－１０６０．［２３］㊀杨超，肖东亮，顾珍珍，等．基于Ｐｏｌａｒ码的Ｎｉｅｄｅｒｒｅｉｔｅｒ公钥密码体制［Ｊ］．密码学报，２０１８，５（６）：６２３－６３０．［２４］㊀ＰｒａｎｇｅＥ．Ｔｈｅｕｓｅｏｆｉｎｆｏｒｍａｔｉｏｎｓｅｔｓｉｎｄｅｃｏ⁃ｄｉｎｇｃｙｃｌｉｃｃｏｄｅｓ［Ｊ］．ＩＲＥＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎ⁃ｆｏｒｍａｔｉｏｎＴｈｅｏｒｙ，１９６２，８（５）：５－９．［２５］㊀ＳｅｎｄｒｉｅｒＮ．Ｄｅｃｏｄｉｎｇｏｎｅｏｕｔｏｆｍａｎｙ［Ｃ］／／Ｐｏｓｔ⁃ＱｕａｎｔｕｍＣｒｙｐｔｏｇｒａｐｈｙ：４ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＷｏｒｋｓｈｏｐ，ＰＱＣｒｙｐｔｏ２０１１，Ｔａｉｐｅｉ，Ｔａｉｗａｎ，Ｎｏｖｅｍｂｅｒ２９－Ｄｅｃｅｍｂｅｒ２，２０１１．Ｐｒｏｃｅｅｄｉｎｇｓ４．ＳｐｒｉｎｇｅｒＢｅｒｌｉｎＨｅｉｄｅｌｂｅｒｇ，２０１１：５１－６７．ＡＲｅｓｅａｒｃｈＳｕｍｍａｒｙｏｆＣｏｄｉｎｇ⁃ｂａｓｅｄＥｌＧａｍａｌＴｙｐｅＰｕｂｌｉｃＫｅｙＣｒｙｐｔｏｓｙｓｔｅｍ∗ＬＩＵＢｉｎｇ㊀ＷＵＸｕｄａｎ㊀ＦＥＮＧＹｕｗｅｉＢｅｉｊｉｎｇＥｌｅｃｔｒｏｎｉｃＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙＩｎｓｔｉｔｕｔｅ，Ｂｅｉｊｉｎｇ１０００７０，Ｐ．Ｒ．ＣｈｉｎａＡｂｓｔｒａｃｔ：Ｃｏｄｉｎｇ⁃ｂａｓｅｄｐｕｂｌｉｃｋｅｙｃｒｙｐｔｏｇｒａｐｈｙａｌｇｏｒｉｔｈｍｈａｓｔｈｅａｄｖａｎｔａｇｅｓｏｆｈｉｇｈｓｅｃｕｒｉｔｙ，ｆａｓｔｅｎ⁃ｃｒｙｐｔｉｏｎａｎｄｄｅｃｒｙｐｔｉｏｎｓｐｅｅｄａｎｄｅａｓｙｉｍｐｌｅｍｅｎｔａｔｉｏｎ，ｂｕｔｉｔａｌｓｏｈａｓｔｈｅｄｉｓａｄｖａｎｔａｇｅｓｏｆｌａｒｇｅｐｕｂｌｉｃｋｅｙｓｃａｌｅ．ＴｈｅＭｃＥｌｉｅｃｅ，ｔｈｅＮｉｅｄｅｒｒｅｉｔｅｒａｎｄｔｈｅＥｌＧａｍａｌａｒｅｔｈｒｅｅｔｙｐｅｓｏｆｃｏｍｍｏｎｌｙｕｓｅｄｃｏｄｉｎｇ⁃ｂａｓｅｄｅｎｃｒｙｐｔｉｏｎｍｅｔｈｏｄｓ．Ａｓａｎｅｗｅｎｃｒｙｐｔｉｏｎｍｏｄｅ，ｔｈｅＥｌＧａｍａｌｓｙｓｔｅｍｉｎｖｏｌｖｅｓｔｗｏｃｏｄｉｎｇｔｙｐｅｓｗｉｔｈｄｉｆｆｅｒｅｎｔｆｕｎｃｔｉｏｎｓ，ｆａｃｉｎｇｔｈｅｐｒｏｂｌｅｍｏｆｄｅｃｏｄｉｎｇｆａｉｌｕｒｅｐｒｏｂａｂｉｌｉｔｙ．Ａｕｎｉｑｕｅｔｅｍｐｏｒａｒｙｋｅｙｍｅｔｈｏｄｉｓｕｔｉｌｉｚｅｄｔｏｉｍｐｒｏｖｅｔｈｅｓｅｃｕｒｉｔｙｐｅｒｆｏｒｍａｎｃｅ．ＴｈｉｓｐａｐｅｒｆｏｃｕｓｅｓｏｎｉｎｔｒｏｄｕｃｉｎｇｔｈｅＥｌＧａｍａｌｅｎｃｒｙｐｔｉｏｎ，ａｎｄｔｈｅｓｔｒｕｃｔｕｒｅ，ｄｉｆｆｉｃｕｌｔｐｒｏｂｌｅｍｓａｎｄｄｅｃｏｄｉｎｇｆａｉｌｕｒｅｐｒｏｂａｂｉｌｉｔｙａｒｅｓｔｕｄｉｅｄ，ｔｏａｃｈｉｅｖｅａｄｅｅｐｅｒｕｎｄｅｒｓｔａｎｄｉｎｇｏｆｔｈｅｓｔｒｕｃｔｕｒｅａｎｄｔｏｏｂｔａｉｎｅｌｅｍｅｎｔａｒｙｆｏｒｆｕｔｕｒｅｄｅｓｉｇｎａｎｄａｎａｌｙｓｉｓ．Ｋｅｙｗｏｒｄｓ：ｃｏｄｉｎｇ；ＥｌＧａｍａｌｔｙｐｅ；ｔｅｍｐｏｒａｒｙｋｅｙ；ｄｅｃｏｄｉｎｇｆａｉｌｕｒｅｐｒｏｂａｂｉｌｉｔｙ（责任编辑：张卷美）㊃９㊃。

一个基于ECC的ElGamal型（t,n）门限数字签名方案一个基于ECC的ElGamal型(t,n)门限数字签名方案张险峰;秦志光;刘锦德【期刊名称】《计算机科学》【年(卷),期】2003(030)005【摘要】This paper comprehensively introduces and analyzes Shamir Secret Sharing, Pedersen's Verifiable SecretSharing based on ECC, verifiable secret sharing without a trusted center based on ECC and an ElGamal digital signa-ture scheme based on ECC. Based on the theoretical introduction, an ElGamal_type(t, n) threshold digital signaturescheme Based on ECC is designed. The performance of the scheme is analyzed. And an application based on thescheme is described. In the scheme, a trusted center to deal with the sharing secret is eliminated. No secret communi-cation is required in the signature issuing phase. The scheme is characterized by excellent security as well as high effi-ciency.【总页数】4页(157-160)【关键词】Network security;Elliptic curve cryptography (ECC);ElGamal;Threshold digital signature;SecretSharing 【作者】张险峰;秦志光;刘锦德【作者单位】电子科技大学计算机学院IBM技术中心,成都,610054;电子科技大学计算机学院IBM技术中心,成都,610054;电子科技大学计算机学院IBM技术中心,成都,610054。

基于ElGamal体制的视频内容保密比较方案于鹏;王永滨;柯雅明;刘文【摘要】针对视频内容比较过程中内容易泄露和通信开销大的问题，提出一种基于ElGamal体制的视频内容保密比较方案。

综合利用视频编码、篡改和人眼视觉特征，提取视频帧中每个条带的最后一个宏块亮度分量作为特征数据，对特征数据进行分组，并计算哈希值。

设计改进的ElGamal算法，在交互双方间共享一个大素数，使其满足可交换性，并利用该算法，在不泄露视频内容的前提下，对双方视频的分组哈希值进行保密比较，从而判断视频是否被篡改，并定位篡改发生的区域。

实验结果表明，该方案计算复杂度低、通信量小，且具有较好的安全性和公平性。

%Video has the problem of content leak and high communication cost in the process of comparison, so this paper proposes a kind of video content confidential comparison scheme based on ElGamal system. Combined with video encoding, tampering and human visual features, the last macroblock’s luminance component of video frame slice is extracted as the feature data. The feature data is grouped and calculated hash value. It designs the improved ElGamal algorithm, which makes a large prime number be shared between the two parties to satisfy the interchangeability. Using the interchangeable ElGamal algorithm, on the premise of not leaked video content, it makes confidential comparison on the grouped hash values of two parties judge whether the video is tampered and locate the tampered area. Experimental results show thatthis scheme has low computing complexity and small communication amount, and it also has good security, fairness.【期刊名称】《计算机工程》【年(卷),期】2014(000)007【总页数】4页(P117-120)【关键词】ElGamal体制;保密比较;视频编码;篡改;特征数据;可交换性【作者】于鹏;王永滨;柯雅明;刘文【作者单位】中国传媒大学计算机学院，北京100024;中国传媒大学计算机学院，北京100024;中国传媒大学计算机学院，北京100024;中国传媒大学计算机学院，北京 100024【正文语种】中文【中图分类】TP3091 概述随着计算机和通信技术的发展，以及“三网融合”的推进，视频内容已经成为人们工作、学习、娱乐生活中不可或缺的组成部分，人们在享受信息时代方便快捷服务的同时，同样也面临着视频内容带来的安全问题。

基于ElGamal体制的可验证的门限秘密共享方案
王慧蓉;吕学琴;刘焕平
【期刊名称】《哈尔滨师范大学自然科学学报》
【年(卷),期】2003(019)006
【摘要】本文将ElGamal体制与Shamir秘密分享方案相结合提出了一种可验证的门限秘密共享方案,其安全性是基于ElGamal体制中在有限域求解离散对数问题的难解性.在该方案中提出了如何防止恶意参与者进行恶意攻击以及如何检验合法参与者是否提供了假的秘密份额,同时也给出了检验由假冒Dealer的参与者以及检验Dealer是否分发了非法的秘密份额的一些有效措施.
【总页数】3页(P36-38)
【作者】王慧蓉;吕学琴;刘焕平
【作者单位】哈尔滨师范大学;哈尔滨师范大学;哈尔滨师范大学
【正文语种】中文
【中图分类】TP3
【相关文献】
1.基于特征值的可验证特殊门限秘密共享方案 [J], 张艳硕;李文敬;陈雷;毕伟;杨涛
2.基于ElGamal密码体制的可验证秘密共享方案 [J], 柳毅;郝彦军;庞辽军
3.一种基于大数分解和求解离散对数的可验证(k,n)门限秘密共享方案 [J], 马春波;何大可
4.基于双线性对的可验证门限秘密共享方案 [J], 王天成
5.基于ElGamal体制的门限秘密共享方案 [J], 王天成;张建中
因版权原因，仅展示原文概要，查看原文内容请购买。