通过双循环矩阵改进的基于纠错码的身份认证方案
|
摘要
目前所有的公钥密码方案都基于大整数分解或离散对数难题,这些困难问题在量子计算机中都可以在多项式时间内求解,因此所有的公钥方案都将面临危险,而基于纠错码的密码方案可以抵抗量子计算机的攻击,所以很有必要研究基于纠错码的身份认证方案。Stern身份认证方案总体来说很不错,但其公钥太大,达到150 Kbit;Veron提出一种改进的方案,目的也在于减少Stern方案中的公钥,在Veron方案中,Veron用生成矩阵来替代校验矩阵,使得所构造的公钥大大减小,但是其基于的安全性GSD问题没有得到很好地证明。现采用双循环矩阵来解决Stern方案中的密钥太大的问题,就是通过双循环矩阵把私钥嵌入到公钥中。这样做的好处有两点:1所基于的安全性是已被证明为安全的循环码;2改进以后,公钥只有347bit,而私钥大小也只有694 bit。并且分析所构造方案的安全性,将其归结到双循环线性条件下的SD问题。因为使用循环结构,使得实现起来比较容易并且效率很高。这些特点使得方案在轻量级结构的场合具有广阔的应用前景,比如手持终端,云存储环境下的数字签名等场合。
At present,all public key cryptography schemes are based on hard problems such as large integer factorization,discrete logarithm. All these hard problems can be solved by a quantum computer in polynomial time,therefore,all public key cryptography schemes will be insecure. Identification schemes based on error-correcting codes can resist the attacks by quantum computers,so it is necessary to design identification schemes based on error-correcting codes. Stern identification scheme is very good in general,but it has too large public key,about 150 Kbits. Veron proposed an improved identification scheme based on Stern'scheme,whose aim is to reduce the size of public key. In Veron's improved scheme,he worked with the generator matrix of the code rather than with on its dual matrix,which makes public key much smaller,but the coding theory problem on which security of this public key is somewhat unclear. Our improved scheme uses double circulant matrix to solve the problem of large public key in Stern's scheme. The construction is embedding directly the secret key in the public key,which has the two following advantages: 1 the security relies on a problem which is related to well known and well studied codes,namely the double circulant codes; 2 the size of the public key is very low,only 347 bits in a typical set-up,the private key is also relatively small,typically 694 bits. At last,the security of the improved scheme was analyzed,its security can be reduced to a certain hard problem. These features make our variant highly attractive for lightweight implementations,especially in handheld terminal or in cloud storage environment.
At present,all public key cryptography schemes are based on hard problems such as large integer factorization,discrete logarithm. All these hard problems can be solved by a quantum computer in polynomial time,therefore,all public key cryptography schemes will be insecure. Identification schemes based on error-correcting codes can resist the attacks by quantum computers,so it is necessary to design identification schemes based on error-correcting codes. Stern identification scheme is very good in general,but it has too large public key,about 150 Kbits. Veron proposed an improved identification scheme based on Stern'scheme,whose aim is to reduce the size of public key. In Veron's improved scheme,he worked with the generator matrix of the code rather than with on its dual matrix,which makes public key much smaller,but the coding theory problem on which security of this public key is somewhat unclear. Our improved scheme uses double circulant matrix to solve the problem of large public key in Stern's scheme. The construction is embedding directly the secret key in the public key,which has the two following advantages: 1 the security relies on a problem which is related to well known and well studied codes,namely the double circulant codes; 2 the size of the public key is very low,only 347 bits in a typical set-up,the private key is also relatively small,typically 694 bits. At last,the security of the improved scheme was analyzed,its security can be reduced to a certain hard problem. These features make our variant highly attractive for lightweight implementations,especially in handheld terminal or in cloud storage environment.
引文
1 Shor P W.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.Siam J Sci Statist Comput,1997;26:124-134
2 McE liece R.A public key cryptosystem based on algebraic coding theory.DSN Progress Report,1978;(42-44):114-116
3 Ding J,Yang B Y.Multivariate Public Key Cryptography.PostQuantum Cryptography.Springer Berlin Heidelberg,2009:193-241
4 Gaborit P.Shorter keys for code based cryptography.Proceedings of WCC,2005:1-13
5 Stern J.A new identification scheme based on syndrome decoding.Crypto'93,1993:13-21
6 Fiat A,Shamir A.How to prove yourself:practical solutions to identification and signature problems.Odlyzko A M(ed)Advances in Cryptology-CRYPTO'86.LNCS,Berlin:Springer,1987;263:186-194
7杨波.现代密码学.清华大学出版社,2015Yang Bo.Modern cryptography.Beijing:Tsinghua University Press,2015
8 Veron P.Improved identification schemes based on error-correcting codes.Applicable Algebra in Engineering,Communication and Computing.,1997;8(1):57-69
9张颖.基于编码理论的密码技术分析与设计.大连:大连海事大学,2010Zhang Ying.Analysis and Design for CryP tographic Technique Based on Error Correcting Codes.Dalian:Dalian Maritime University,2010
10 Berlekamp E,McE liece R,van Tilborg H.On the inherent intractability of certain coding problems.IEEE Transactions on Information Theory,1978;24(3):384-386
11 Prange E.The use of information sets in decoding cyclic codes.IRETransactions on Information Theory,1962:5-9
12 Lee P,Brickell E.An observation on the security of McE liece's public key cryptosystem.Advances in Cryptology-Eurocrypt'88,1989;330:275-280
13 Canteaut A,Chabaud F.A new algorithm for finding minimum weight words in a linear code:application to primitive narrow-sense BCH codes of length-511.IEEE Transactions on Information Theory,1998;44:367-378
14 Sendrier N.On the security of the McE liece public-key cryptosystem.Blaum M,Farrell P G,van Tilborg H,Editors,Information,Coding and Mathematics,2002:141-163
15 MacW illiams F J,Sloane N J A.The theory of error correcting codes.North-Holland Press:1977
16 Pierce J N.Limit distributions of the minimum distance of random linear codes.IEEE Trans Inf Theory,1967:13;595-599
17 Chen C,Peterson W,Weldon E.Some results on quasi-cyclic codes.Information and Control,1969;15:407-423
18 Gaborit P,Zemor G.Asymptotic improvement of the Gilbert Varshamov bound for linear codes.Proceedings of ISIT 2006,Seattle,USA,2006:287-291
19 Hoffstein J,Pipher J,Silverman J H.NTRU:a ring-based public key cryptosystem,1998:267-288
2 McE liece R.A public key cryptosystem based on algebraic coding theory.DSN Progress Report,1978;(42-44):114-116
3 Ding J,Yang B Y.Multivariate Public Key Cryptography.PostQuantum Cryptography.Springer Berlin Heidelberg,2009:193-241
4 Gaborit P.Shorter keys for code based cryptography.Proceedings of WCC,2005:1-13
5 Stern J.A new identification scheme based on syndrome decoding.Crypto'93,1993:13-21
6 Fiat A,Shamir A.How to prove yourself:practical solutions to identification and signature problems.Odlyzko A M(ed)Advances in Cryptology-CRYPTO'86.LNCS,Berlin:Springer,1987;263:186-194
7杨波.现代密码学.清华大学出版社,2015Yang Bo.Modern cryptography.Beijing:Tsinghua University Press,2015
8 Veron P.Improved identification schemes based on error-correcting codes.Applicable Algebra in Engineering,Communication and Computing.,1997;8(1):57-69
9张颖.基于编码理论的密码技术分析与设计.大连:大连海事大学,2010Zhang Ying.Analysis and Design for CryP tographic Technique Based on Error Correcting Codes.Dalian:Dalian Maritime University,2010
10 Berlekamp E,McE liece R,van Tilborg H.On the inherent intractability of certain coding problems.IEEE Transactions on Information Theory,1978;24(3):384-386
11 Prange E.The use of information sets in decoding cyclic codes.IRETransactions on Information Theory,1962:5-9
12 Lee P,Brickell E.An observation on the security of McE liece's public key cryptosystem.Advances in Cryptology-Eurocrypt'88,1989;330:275-280
13 Canteaut A,Chabaud F.A new algorithm for finding minimum weight words in a linear code:application to primitive narrow-sense BCH codes of length-511.IEEE Transactions on Information Theory,1998;44:367-378
14 Sendrier N.On the security of the McE liece public-key cryptosystem.Blaum M,Farrell P G,van Tilborg H,Editors,Information,Coding and Mathematics,2002:141-163
15 MacW illiams F J,Sloane N J A.The theory of error correcting codes.North-Holland Press:1977
16 Pierce J N.Limit distributions of the minimum distance of random linear codes.IEEE Trans Inf Theory,1967:13;595-599
17 Chen C,Peterson W,Weldon E.Some results on quasi-cyclic codes.Information and Control,1969;15:407-423
18 Gaborit P,Zemor G.Asymptotic improvement of the Gilbert Varshamov bound for linear codes.Proceedings of ISIT 2006,Seattle,USA,2006:287-291
19 Hoffstein J,Pipher J,Silverman J H.NTRU:a ring-based public key cryptosystem,1998:267-288