半群作用问题在密码学中的应用
|
摘要
各种半群作用问题,如离散对数问题和共轭问题,在现代密码学中有着广泛应用。源于离散对数问题困难性的计算Diffie-Hellman假设和判定Diffie-Hellman假设是众多现代密码体制安全性的基石。近几年,许多学者基于某些非交换群上共轭问题及其相关问题的困难性也设计了较为简单的公钥密码体制。然而,DDH假设在双线性群上并不成立,大多数基于共轭问题的的密码体制也并不安全。寻找其他合适的半群作用问题是一个重要的研究方向。本文对几类半群作用问题做了探索性研究。研究了离散对数问题、矩阵半群作用问题及其相关问题、Clifford半群上的多重共轭搜索问题及其相关的问题,得到如下主要结果:
(1)研究了半群作用的抽象代数理论。定义并研究了可分整Dubreil-Jacotin半群,利用序群对序幺半群的作用刻画了一类可分整Dubreil-Jacotin半群的结构。
(2)基于一类关于矩阵半群作用的有限域上向量空间,提出了广义计算Diffie-Hellman( n -ECDH)问题和广义判定Diffie-Hellman( n -EDDH)问题。分析了n -ECDH问题和n -EDDH问题与离散对数问题、CDH问题和DDH问题之间的关系。证明了n -EDDH问题满足随机自归约性,DDH问题可多项式时间归约为n -EDDH问题。在一般群模型下,双线性群上2-EDDH假设要弱于DDH假设。
(3)构造了新的广义ElGamal公钥加密方案,它是单向的当且仅当ECDH假设成立,它是语义安全的当且仅当EDDH假设成立。
(4)构造了几个新的广义Cramer-Shoup公钥加密方案,在EDDH假设下,它们是标准模型下IND-CCA2安全的。
(5)构造了两类新的伪随机函数。在EDDH假设和GECDH假设下,分别证明了它们的安全性。
(6)提出基于Clifford半群上的多重共轭搜索问题和多重幂等元搜索问题的密钥建立协议代数模型。利用某些有限表达的Clifford半群有可能实现这种协议并能抵抗长度攻击。
(7)对von zur Gathen和Shparlinski提出的乘法噪音多项式插值算法进行了分析,提出了改进算法。分别降低了原算法中有限域阶的下界和乘法近似黑盒的询问初值。
All kinds of semigroup action problems such as discrete logarithm problem and conjugacy problem play very significant role in modern cryptography. The decisional Diffie-Hellman assumption from discrete logarithm is the base of security of many modern cryptosystems. Recently, many scholars have designed some simple cryptosystems based on conjugacy problem on several non-abelian groups. However, DDH assumption does not hold in bilinear groups and most cryptosystems based on conjuacy problem are not secure. So it is a very important research direction to find other appropriate semigroup action problem. This paper dissertation investigates the several semigroup action problems exploringly and analyzes logarithm problem, matrix semigroup action problem, multiple conjugacy search problem on Clifford semigroup and their related problems. The main results are as follows:
(1) The algebraic theory of semigroup action is discussed. Split integral Dubreil-Jacotin semigroup is defined and studied and the structure of a class of split Dubreil-Jacotin semigroup is described by some ordered group action on ordered monoid.
(2) An extended computational Diffie-Hellman problem and an extended decisional Diffie-Hellman problem based on a class of vector space of finite field with respect to matrix semigroup action are proposed. The relationship of n -ECDH assumption, n -EDDH assumption, DL assumption, CDH assumption and DDH assumption is analyzed. It is proved that the n -EDDH problem satisfies the random self-reducibility property and 2-EDDH assumption is weaker than the classic DDH assumption in the generic bilinear groups in the generic group model.
(3) A new extended ElGamal public key encryption scheme is proposed. The new encryption scheme is one-way if and only if ECDH assumption holds and it is semantically secure in the standard model if and only if the EDDH assumption holds.
(4) Several new extended Cramer-Shoup public key encryption schemes is proposed and analyzed. These schemes are proved secure against adaptive chosen ciphertext attack under EDDH assumption.
(5) Two new constructions of pseudo-random functions are presented. The proof of security on them is proposed under the EDDH assumption and GECDH assumption.
(6) Two algebraic key establishment protocol models are presented. The new key establishment protocol models are based on the multiple conjugacy (idempotent) search problem on Clifford semigroup. Some finite presented Clifford semigroup maybe implement these protocol models and resist the length attack.
(7) Two amended multiplicative noisy polynomial interpolation algorithms presented by von zur Gathen and Shparlinski are proposed and analyzed. The amended algorithms reduce respectively the lower bound of the order of finite field and the initial query value inputted to multiplicatively approximate multiplicative black box.
(1)研究了半群作用的抽象代数理论。定义并研究了可分整Dubreil-Jacotin半群,利用序群对序幺半群的作用刻画了一类可分整Dubreil-Jacotin半群的结构。
(2)基于一类关于矩阵半群作用的有限域上向量空间,提出了广义计算Diffie-Hellman( n -ECDH)问题和广义判定Diffie-Hellman( n -EDDH)问题。分析了n -ECDH问题和n -EDDH问题与离散对数问题、CDH问题和DDH问题之间的关系。证明了n -EDDH问题满足随机自归约性,DDH问题可多项式时间归约为n -EDDH问题。在一般群模型下,双线性群上2-EDDH假设要弱于DDH假设。
(3)构造了新的广义ElGamal公钥加密方案,它是单向的当且仅当ECDH假设成立,它是语义安全的当且仅当EDDH假设成立。
(4)构造了几个新的广义Cramer-Shoup公钥加密方案,在EDDH假设下,它们是标准模型下IND-CCA2安全的。
(5)构造了两类新的伪随机函数。在EDDH假设和GECDH假设下,分别证明了它们的安全性。
(6)提出基于Clifford半群上的多重共轭搜索问题和多重幂等元搜索问题的密钥建立协议代数模型。利用某些有限表达的Clifford半群有可能实现这种协议并能抵抗长度攻击。
(7)对von zur Gathen和Shparlinski提出的乘法噪音多项式插值算法进行了分析,提出了改进算法。分别降低了原算法中有限域阶的下界和乘法近似黑盒的询问初值。
All kinds of semigroup action problems such as discrete logarithm problem and conjugacy problem play very significant role in modern cryptography. The decisional Diffie-Hellman assumption from discrete logarithm is the base of security of many modern cryptosystems. Recently, many scholars have designed some simple cryptosystems based on conjugacy problem on several non-abelian groups. However, DDH assumption does not hold in bilinear groups and most cryptosystems based on conjuacy problem are not secure. So it is a very important research direction to find other appropriate semigroup action problem. This paper dissertation investigates the several semigroup action problems exploringly and analyzes logarithm problem, matrix semigroup action problem, multiple conjugacy search problem on Clifford semigroup and their related problems. The main results are as follows:
(1) The algebraic theory of semigroup action is discussed. Split integral Dubreil-Jacotin semigroup is defined and studied and the structure of a class of split Dubreil-Jacotin semigroup is described by some ordered group action on ordered monoid.
(2) An extended computational Diffie-Hellman problem and an extended decisional Diffie-Hellman problem based on a class of vector space of finite field with respect to matrix semigroup action are proposed. The relationship of n -ECDH assumption, n -EDDH assumption, DL assumption, CDH assumption and DDH assumption is analyzed. It is proved that the n -EDDH problem satisfies the random self-reducibility property and 2-EDDH assumption is weaker than the classic DDH assumption in the generic bilinear groups in the generic group model.
(3) A new extended ElGamal public key encryption scheme is proposed. The new encryption scheme is one-way if and only if ECDH assumption holds and it is semantically secure in the standard model if and only if the EDDH assumption holds.
(4) Several new extended Cramer-Shoup public key encryption schemes is proposed and analyzed. These schemes are proved secure against adaptive chosen ciphertext attack under EDDH assumption.
(5) Two new constructions of pseudo-random functions are presented. The proof of security on them is proposed under the EDDH assumption and GECDH assumption.
(6) Two algebraic key establishment protocol models are presented. The new key establishment protocol models are based on the multiple conjugacy (idempotent) search problem on Clifford semigroup. Some finite presented Clifford semigroup maybe implement these protocol models and resist the length attack.
(7) Two amended multiplicative noisy polynomial interpolation algorithms presented by von zur Gathen and Shparlinski are proposed and analyzed. The amended algorithms reduce respectively the lower bound of the order of finite field and the initial query value inputted to multiplicatively approximate multiplicative black box.
引文
[1] Abdalla M, Bellare M, Rogaway P. DHIES: An encryption scheme based on the Diffie-Hellman problem. CT-RSA’01, LNCS 2020, Berlin: Springer-Verlag, 2001, pp. 143-158.
[2] Adleman L M. A subexponential algorithm for the discrete logarithm problem with applications to cryptography. Proceedings of the IEEE 20th Annual Symposium on Foundations of Computer Science, 1979, 55-60.
[3] Adleman L M. The function field sieve. Algorithmic Number Theory, LNCS 877, Berlin: Springer-Verlag, 1994, pp. 108-121.
[4] Adleman L M and Demarrais J. A subexponential algorithm for discrete logarithms over all finite fields. Mathematics of Computation, 1993, 61, pp. 1-15.
[5] Adleman L M, DeMarrais J and Huang M D. A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields. Algorithmic Number Theory, LNCS 877, Berlin: Springer-Verlag, 1994, pp. 28-40.
[6] Ajtai M, Kumar R and Sivakumar D. A sieve algorithm for the shortest lattice vector problem. Proc. 33rd ACM Symp. on Theory of Comput., New York, ACM Press, 2001, pp. 601–610.
[7] Anshel I, Anshel M and Goldfeld D. An algebraic method for public key cryptography. Mathematical Research Letters, 1999, 6(3), pp. 287–291.
[8] Babai L. On Lovasz’lattice reduction and the nearest lattice point problem. Combinatorica, 1986, 6(1), pp. 1-13.
[9] Bao F, Deng R and Zhu H. Variations of Diffie-Hellman problem. ICICS'2003, LNCS 2836, Berlin: Springer-Verlag, 2003, pp. 301–312.
[10] Beame P W, Cook S A and Hoover H J. Log depth circuits for division and related problems. SIAM J. Comput. 1986, 15, pp. 994-1003.
[11] Bellare M, Boldyreva A, and Micali S. Public-key encryption in a multi-user setting: security proofs and improvements. In Advances in Cryptology–Eurocrypt 2000, LNCS 1807, Berlin: Springer-Verlag pages, 2000, pp.259-274.
[12] Bellare M, Desai A, Pointcheval D, et al. Relations among notions of security for public-key encryption schemes. Advances in Cryptology–Crypto’98, LNCS 1462, Berlin: Springer-Verlag pages, 1998, pp. 26–45.
[13] Bellare M and Goldwasser S. New paradigm for digital signatures and message authentication based on non-interactive zero knowledge proofs. Advancesin Cryptology–CRYPTO’89, LNCS 435, Berlin: Springer-Verlag, 1990, pp. 194–211.
[14] Bellare M and Rogaway P. Minimizing the use of random oracles in authenticated encryption schemes. Information and communications security, LNCS 1334, Berlin: Springer-Verlag, 1997, pp. 1-16.
[15] Bellare M and Rogaway P. Optimal asymmetric encryption. In Advances in Cryptology-Eurocrypt’94, LNCS 950, Berlin: Springer-Verlag pages, 1994, pp.92-111.
[16] Birgit P and Ahmadeza S. Anonymous fingerprinting with direct non-repudiation. Advances in Cryptology–Asiacrypt'2000, LNCS 1976, Berlin: Springer-Verlag, 2000, pp. 401-414.
[17] Birman J, Ko K and Lee S. The infimum, supremum, and geodesic length of a braid conjugacy class. Adv. in Math, 2001, 164(1), pp. 41–56.
[18] Blackburn S R and Galbraith S D. Cryptanalysis of two cryptosystems based on group actions. Advances in Cryptology-Asiacrypt’99, LNCS 1716, Berlin: Springer-Verlag, 1999, pp. 52-61.
[19] Blum M and Micali S. How to generate cryptographically strong sequence of pseudo-random bits. SIAM J. Comput. 1984, 13, pp. 850-864.
[20] Blyth T S. Dubreil-Jacotin inverse semigroups. Proc. Roy. Soc. Edinburgh. Sect., 1973, A71, pp. 345–360.
[21] Blyth T S. The structure of certain ordered regular semigroups. Proc. Roy. Soc. Edinburgh. Sect., 1976, A75, pp. 235–257.
[22] Blyth T S and Emilia G. Perfect elements in Dubreil-Jacotin regularsemigroups. Semigroup Forum, 1992, 45, pp. 55–62.
[23] Blyth T S and Janowitz M F. Residuation Theory. Pergamon Press, 1972.
[24] Boneh D. The decision Diffie-Hellman problem. Algorithmic Number Theory, Third International Symposium, ANTS-III, LNCS 839, Berlin: Springer-Verlag, 1998, pp. 48-63.
[25] Boneh D and Boyen X. Short signatures without random oracles. Advances in Cryptology-Eurocrypt’04, LNCS 3027, Berlin: Springer-Verlag, 2004, pp. 56-73.
[26] Boneh D and Boyen X. Secure identity based encryption without random oracles. Advances in Cryptology-Crypto'04, LNCS 3152, Berlin: Springer-Verlag, 2004, pp. 443-459.
[27] Boneh D and Boyen X. Efficient selective-ID secure identity-based encryption without random oracles. Advances in Cryptology-Eurocrypt’04, LNCS 3027, Berlin: Springer-Verlag, 2004, pp. 223-238.
[28] Boneh D, Boyen X and Shacham H. Short group signatures. Advances in Cryptology-Crypto'04, LNCS 3152, Berlin: Springer-Verlag, 2004, pp. 41-55.
[29] Boneh D and Franklin M. Identity based encryption from the Weil pairing. SIAM J. of Computing, 2003, 32(3), pp. 586-615.
[30] Boneh D and Lipton R J. Algorithms for black-box fields and their application to cryptography. Advances in Cryptology-Crypto’96, LNCS 1109, Berlin: Springer-Verlag, 1996, pp. 283-297.
[31] Boneh D, Lynn B, and Shacham H. Short signatures from the Weil pairing. Advances in Cryptology-Asiacrypt’01, LNCS 2248, Berlin: Springer-Verlag, 2001,pp. 514-532.
[32] Boneh D, Shen E, and Waters B. Strongly unforgeable signatures based on computational Diffie-Hellman. International Workshop on Practice and Theory in Public Key Cryptography 2006-PKC '06, LNCS 3958, Berlin: Springer-Verlag, 2006, pp. 229-240.
[33] Boneh D and Venkatesan R. Hardness of computing the most significant bits of secret keys in Diffie–Hellman and related schemes. Advances in Cryptology- CRYPTO'96, LNCS 1109. Berlin: Springer-Verlag, 1996, pp. 129-142.
[34] Boneh D and Venkatesan R. Rounding in lattices and its cryptographic applications. Proc. 8th Annual ACM-SIAM Symp. on Discr. Algorithms, New York, ACM Press, 1997, pp. 675-- 681.
[35] Brands S. An efficient off-line electronic cash system based on the representation problem, CWI Technical Report, CS-R9323, 1993.
[36] Bresson E, Chevassut O, and Pointcheval D. The group Diffie-Hellman problems. Workshop on selected areas in cryptography-SAC’02, LNCS 2595, Berlin: Springer-Verlag, 2002, pp. 325-338.
[37] Bresson E et al. A Generalization of DDH with Applications to Protocol Analysis and Computational Soundness. Advances in Cryptology-Crypto'2007, LNCS 4622, Berlin: Springer-Verlag, 2007, pp. 482-499.
[38] Burmester M, Desmedt Y, and Seberry J. Equitable key escrow with limited time span (or, how to enforce time expiration cryptographically). Advances in Cryptology–Asiacrypt'98, LNCS 1514, Berlin: Springer-Verlag, 1998, pp. 380–391.
[39] Canetti R. Universally composable security: a new paradigm for cryptographic protocols. Cryptology ePrint Archive, Report 2000/067, 2000. Available from: http://eprint.iacr.org.
[40] Canetti R, Friedlander J and Shaparlinski I E. On certain exponential sums and the distribution of Diffie-Hellman triples. J. London Math. Soc., 1999, 59, pp. 799-812.
[41] Cheon J and Jun B. A polynomial time algorithm for the braid Diffie-Hellman conjugacy problem. Advances in Cryptology -Crypto’03, LNCS 2729. Berlin: Springer-Veralg, 2003, pp. 212–225.
[42] Chor B, Fiat A and Naor M. Tracing traitors. Advances in Cryptology -CRYPTO’94, LNCS 839, Berlin: Springer-Verlag, 1994, pp. 257–270.
[43] Coppersmith D, Odlzyko A M and Schroeppel R. Discrete logarithms in GF(p). Algorithmica, 1986, 1, pp. 1-15.
[44] Cramer R and Shoup V. Design and analysis of practical publickey encryption schemes secure against sdaptive chosen ciphertext attack. SIAM Journal of Computing, 2003, 33(1), pp. 167-226.
[45] Cramer R and Shoup V. A practical public key cryptosystem provably secureagainst adaptive chosen ciphertext attack. Advances in Cryptology-Crypto’98, LNCS 1462. Berlin: Springer-Veralg, 1998, pp. 13-25.
[46] Cramer R and Shoup V. Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public key encryption. Advances in Cryptology -Eurocypt’02, LNCS 2332. Berlin: Springer-Veralg, 2002, pp. 45-64.
[47] Diffie W and Hellman M E. New directions in cryptography. IEEE Trans. Inform. Theory, 1976, 22(6): 644-654.
[48] Dolev D, Dwork C, and Naor M. Non-malleable cryptography. In 23rd Annual ACM Symposium on Theory of Computing, 1991, pp. 542–552.
[49] Dolev D, Dwork C, and Naor M. Non-malleable cryptography. SIAM J. Comput., 2000, 30(2), pp. 391–437.
[50] ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inform. Theory, 1985, 31(4), pp. 469-472.
[51] El Mahassni E, Nguyen P Q and Shparlinski I E. The insecurity of Nyberg-Rueppel and other DSA-like signature schemes with partially known nonces. Proceedings of Cryptography and Lattices Conference, Berlin Heidelberg: Springer, 2001, pp. 97-109.
[52] Frey G and Rück H G. A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Mathematics of Computation, 1994, 62, pp. 865-874.
[53] Franco N and Gonzales-Meneses J. Conjugacy problem for braid groups and Garside groups. J. Algebra, 2003, 266(1), pp. 112–132.
[54] Fujisaki E and Okamoto T. How to enhance the security of public-key encryption at minimum cost. International Workshop on Practice and Theory in Public Key Cryptography 99-PKC’99. LNCS 1560, Berlin: Springer-Verlag pages, 1999, pp. 53–68.
[55] Goldreich O. Foundations of cryptography: Basic Tools. Cambridge: Cambridge University Press, 2001.
[56] Goldreich O. Foundations of cryptography Volume 2: Basic Applications. Cambridge: Cambridge University Press, 2004.
[57] Goldreich O, Goldwasser S and Micali S. How to construct random functions]. Journal of ACM, 1986. 33, pp. 792–807.
[58] Goldreich O and Ostrovsky R. Software protection and simulation on oblivious RAMs. Journal of ACM, 1996. 43(3), pp. 431–473.
[59] Goldreich O and Levin L. A hard-core predicate for all one-way functions. Proc. 21st Ann. ACM Symp. On Theory of Computing, 1989, pp. 25-32.
[60] Goldwasser S and Micali S. Probabilistic encryption. Journal of Computer and System Sciences, 1984, 28, pp. 270–299.
[61] Gonzalez-Meneses J. Improving an algorithm to solve Multiple Simultaneous Conjugacy Problems in braid groups. Available fromhttp://xxx.lanl.gov/abs/math.GT/0212150.
[62] González Vasco M I and Shparlinski I E. On the security of Diffie–Hellman bits. Proc. Workshop on Cryptography and Computational Number Theory, Singapore 1999, Birkh?user, 2001, pp. 257–268.
[63] González Vasco M I and Shparlinski I E. Security of the most signi.cant bits of the shamir message passing scheme. Math. Comp., 2002, 71, pp. 333–342.
[64] Heiman R. A note on discrete logarithms with special structure. Advances in Cryptology-Eurocrypt’92, LNCS 658, Berlin: Springer-Verlag, 1993, pp. 454-457.
[65] Hellman M E and Reyneri J M. Fast computation of discrete logarithms in GF(q). Advances in Cryptology-Crypto 82, LNCS 658, Berlin: Springer-Verlag, 1982, pp. 3-13.
[66] Howie J M. An introduction to semigroup theory. London: Academic Press, 1976.
[67] Huang H W. Some contributions to ordered semigroup. Master’s thesis, Jiangxi Normal Unverisity, 2004.
[68] Hughes J. A linear algebraic attack on the AAFG1 braid group cryptosystem. ACISP 2002, LNCS 2384, Berlin: Springer-Veralg, 2002, pp. 212–225.
[69] Hughes J and Tannenbaum A. Length-based attacks for certain group based encryption rewriting systems. Workshop SECI02 Security of Communications on the Internet, Tunis, Tunisa, 2002, pp. 5-12.
[70] Joux A. A one round protocol for tripartite Diffie-Hellman. Proceedings of ANTS IV, LNCS 1838, Berlin: Springer-Verlag, 2000, pp. 385-394.
[71] Joux A and Nguyen K. Separating decision Diffie-Hellman from Diffie-Hellman in cryptographic groups. Journal of Cryptology, 2003, 16 (4), pp. 239-247.
[72] Knuth D E. The art of computer programming-sorting and searching, volume 3, Addison-Wesley, Reading, Massachusetts, 1973.
[73] Ko K H, Lee S J, Cheon J H, et al. New public-key cryptosystem using braid groups. Advances in Cryptology-Crypto 2000, LNCS 1880, Berlin: Springer-Verlag, 2000, pp. 166-183.
[74] Koblitz N. Algebraic aspects of cryptography. Berlin: Springer-Veralg, 1998.
[75] Lee I S, Kim W H, Kwon D, et al. On the security of MOR public key cryptosystem. Advances in Cryptology–Asiacrypt’04, LNCS 3329, Berlin: Springer-Verlag, 2004, pp. 387-400.
[76] Lenstra A K, Lenstra H W, and Lovasz L. Factoring polynomials with rational coefficients. Mathematische Annalen, 1982, 261(4),pp. 515–534.
[77] Lidl R and Niederreiter H. Introduction to finite fields and their applications. Cambridge : Cambridge University Press, 1986.
[78] Luby M and Rackoff C. How to construct pseudorandom permutations and pseudorandom functions. SIAM Journal of Computing, 1988. 17, pp. 373–386.
[79] Mahlburg K. An overview of braid group cryptography. Available fromhttp://www.math.wisc.edu/~boston/mahlburg.pdf.
[80] Mao Wenbo. Modern Cryptography: Theory and Practice. Beijing: Publishing House of Electronics Industry, 2004.
[81] Maurer U M. Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms, Advances in Cryptology-Crypto’94, LNCS 839, Berlin: Springer-Verlag, 1994, pp. 271-281.
[82] Maurer U M and Wolf S. Diffie-Hellman oracles. Advances in Cryptology-Crypto’96, LNCS 1109, Berlin: Springer-Verlag, 1996, pp. 268-282.
[83] Maurer U M and Wolf S. Lower bounds on generic algorithms in groups. Advances in Cryptology-Eurocrypt '98, LNCS 1403, Berlin: Springer-Verlag, 1998, pp. 72-84.
[84] Maurer U M and Wolf S. The relationship between breaking the Diffie–Hellman protocol and computing discrete logarithms. SIAM J. Comput., 1999, 28(5), pp. 1689–1721.
[85] Maurer U M and Wolf S. The Diffie-Hellman protocol. Designs, Codes, and Cryptography, 2000, 19, pp. 147-171.
[86] Maurer U M and Wolf S. Diffie-Hellman, Decision Diffie-Hellman, and discrete logarithms. In IEEE Symposium on Information Theory, Cambridge, USA, 1998, pp. 327.
[87] Maze G. Algebraic methods for constructing one-way trapdoor functions. PhD thesis, University of Notre Dame, May 2003.
[88] Maze G, Monico C and Rosenthal J. A public key cryptosystem based on actions by semigroups. In Proceedings of the 2002 IEEE International Symposium on Information Theory. Lausanne, Switzerland: Institute of Electrical and Electronics Engineers Inc 2002, pp. 266.
[89] Maze G, Monico C and Rosenthal J. Public key cryptography based on simple modules over simple rings. In Proceedings of the 2002 Mathematical Theory of Networks and System, Notre Dame: University of Notre Dame. 2002.
[90] Maze G, Monico C and Rosenthal J. Public key cryptography based on semigroup actions. http://www.math.unizh.ch/user/gmaze/Articles/CryptoArxiv.pdf. 2005, to appear in Advances of Mathematics of Communications. To appear in Advances of Mathematics of Communications.
[91] McCurley K S. Cryptographic key distribution and computation in class groups. Mollin R A, editor, Number Theory and Applications, Kluwer Academic Publishers, 1989, pp. 459-479.
[92] McCurley K S. The discrete logarithm problem. Pomerance C, editor, Cryptology and Computational Number Theory, volume 42 of Proceedings of Symposia in Applied Mathematics, American Mathematical Society, 1990, pp. 49-74.
[93] McFadden R and O’Carroll L. F-inverse semigroups. Proc. London. Math. Soc., 1971, 22 (3), pp. 652–666.
[94] Menezes A, Okamoto T and Vanstone S. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Transactions on Information Theory, 1993, 39, pp. 1639-1646.
[95] Menezes A, van Oorschot P and Vanstone S. Handbook of Applied Cryptography. Boca Raton, FL: CRC Press Series on Discrete Mathematics and its Applications, CRC Press, 1997.
[96] Monico C. Semirings and semigroup actions in public-key cryptography. Dissertation for the Doctoral Degree, Notre Dame: University of Notre Dame. 2002.
[97] Naor M and Reingold O. Number-theoretic constructions of efficient pseudo-random functions. Journal of ACM, 2004, 51(2), pp. 231-262.
[98] Naor M and Yung M. Public-key cryptosystems provably secure against chosen ciphertext attacks. In 22nd Annual ACM Symposium on Theory of Computing, 1990, pp. 427–437.
[99] Naor M and Reingold O. Synthesizers and their application to the parallel construction of pseudo-randomfunctions. Journal of Computer and System Sciences, 1999, 58(2), pp. 336-375.
[100] Nguyen P Q and Shparlinski I E. The insecurity of the digital signature algorithm with partially known nonces. J. Cryptology, 2002, 15(3), pp. 151–176.
[101] Nguyen P Q and Shparlinski I E. The insecurity of the elliptic curve digital signature algorithm with partially known nonces. Designs, Codes and Cryptography, 2003, 30(2), pp. 201–217.
[102] Okamoto T and Pointcheval D. The gap-problems: a new class of problems for the security of cryptographic schemes. International Workshop on Practice and Theory in Public Key Cryptography 2001-PKC’01, LNCS 1992, Berlin: Springer-Verlag, 2001, pp. 104-118.
[103] Otto F and Staller-Klein. Some remarks on finitely presented monoids with automatic structure. Available from http://citeseer.ist.psu.edu/34256.html.
[104] Paeng S H and Ha K C. New public key cryptosystem using finite non abelian groups. Advances in Cryptology-Crypto’01, LNCS 2139, Berlin: Springer-Verlag, 2001, pp. 470-485.
[105] Petrich M. Inverse Semigroups. New York : Wiley-Interscience, 1984.
[106] Pohlig S C and Hellman M E. An improved algorithm for computing logarithms over GF(p) nd its cryptographic significance. IEEE Transactions on Information Theory, 1978, 24, pp. 106-110.
[107] Pollard J M. Monte Carlo methods for index computation (mod p). Mathematics of Computation, 1978, 32, pp. 918-924.
[108] Rackoff C and Simon D. Noninteractive zero-knowledge proof of knowledge and chosen ciphertext attack. Advances in Cryptology–Crypto’91, LNCS 576, Berlin: Springer-Verlag, 1991, pp. 433-444.
[109] Reif J. On threshold circuits and polynomial computation. Proc. Of the 2nd Conference on Structure in Complexity Theory, 1987, pp. 118-123.
[110] Reif J and Tate S. On threshold circuits and polynomial computation. SIAM J. Comput., 1992, 5, pp. 896-908.
[111] Rose J S. A course on group theory. Cambridge: Cambridge University Press, 1978.
[112] Schacham H. A Cramer-Shoup encryption scheme from the linear assumption and from progressively weaker linear variants. http://eprint.iacr.org/2007/074.pdf.
[113] Shor P W. Algorithms for quantum computation: discrete logarithms and factoring. Proceedings of the IEEE 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124-134.
[114] Shoup V. Lower bounds for discrete logarithms and related problems. Advances in Cryptology-Eurocrypt’97 , LNCS 1233. Berlin: Springer-Verlag, 1997, pp. 256-266.
[115] Shparlinski I E. Sparse polynomial approximation in finite fields. Proc. 33rd ACM Symp. on Theory of Comput. New York: ACM Press, 2001, pp. 209–215.
[116] Shparlinski I E. Hidden number problem and its applications. Proc. 7th Spanish Meeting on Cryptology and Information Security, Vol.1. Oviedo: Univ. of Oviedo, 2002, pp. 49–72.
[117] Shparlinski I E. Noisy interpolation of sparse polynomials in finite fields. Applicable Algebra in Engineering, Communication and Computing, 2005, 16(5), pp. 307-317.
[118] Shparlinski I E. Playing“Hide-and-Seek”in finite fields: Hidden number problem and its applications. Proc. 7th Spanish Meeting on Cryptology and Information Security, Vol.1, Univ. of Oviedo, 2002, pp. 49–72.
[119] Shpilrain V and Ushakov A. Thompson’s group and public key cryptography. Applied Cryptography and Network Security 2005, LNCS 3531, Berlin: Springer-Verlag, 2005, pp. 151-163.
[120] Siu K Y, Bruck J, Kailath T, et al. Depth efficient neural network for division and related problems, IEEE Trans. Inform. Theory, 1993, 39, pp. 946-956.
[121] Siu K Y and Roychowdhury. On optimal depth threshold circuits for multiplication and related problems. SIAM J. Disc. Math., 1994, 7(2), pp. 284-292.
[122] Smart N P. The discrete logarithm problem on elliptic curves of trace one. Journal of Cryptology, 1999, 12, pp. 193-196.
[123] Stadler M. Publicly verifiable secret sharing. Advances in Cryptology–Eurocrypt'96, LNCS 1070, Berlin: Springer-Verlag, 1996, pp. 190-199.
[124] Steiner M, Tsudik G and Waidner M. Diffie-Hellman key distribution extended to group communication. In Proc. of ACM CCS '96. New York: ACM Press,1996, pp. 31--37.
[125] Thiong Ly J A. A serial version of the Pohlig-Hellman algorithm for computing discrete logarithms. Applicable Algebra in Engineering, Communication and Computing, 1993, 4, pp. 77-80.
[126] Tsiounis Y and Yung M. On the security of ElGamal based encryption. Public Key Cryptography-PKC’98, LNCS 1431, Berlin: Springer-Verlag, 1998, pp. 117-134.
[127] Tobias C. Security analysis of the MOR cryptosystem. International Workshop on Practice and Theory in Public Key Cryptography 2003-PKC’03, LNCS 2567, Berlin: Springer-Verlag, 2003, pp. 175-186.
[128] Van Oorschot P, Parallel collision search with applications to hash functions and discrete logarithms. 2nd ACM Conference on Computer and Communications Security, ACM Press, 1994, pp. 210-218.
[129] von zur Gathen J and Shparlinski I E. Polynomial Interpolation from Multiples. Proc.15th ACM-SIAM Symposium on Discrete Algorithms. Philadelphia: SIAM, 2004, pp. 1125-1130.
[130] Wagner N R and Magyarik M R. A public key cryptosystem based on the word problem. Advances in Cryptology- Crypto’84, LNCS 196, Berlin: Springer-Verlag, 1985, pp. 19-36.
[131] Xie X Y. An introduction to ordered semigroup theory. Beijing: Science Press in China, 2001.
[132] Yamamura A. Public-key cryptosystems using the modular group. International Workshop on Practice and Theory in Public Key Cryptography 1998-PKC’98, LNCS 1431, Berlin: Springer-Verlag, 1998, pp. 203-216.
[133]肖国镇,卿斯汉.编码理论.北京:国防工业出版社,1993.
[134]赖溪松,韩亮,张真诚(张玉清,肖国镇改编).计算机密码学及其应用.北京:国防工业出版社,2001.
[135]胡予濮,肖国镇.对称密码学.北京:机械工业出版社,2002 .
[136]王育民,刘建伟.通信网的安全-理论与技术.西安:西安电子科技大学出版社,1999.
[137]王新梅,肖国镇.纠错码-原理与方法(修订版).西安:西安电子科技大学出版社,2001
[138]裴定一祝跃飞.算法数论.北京:科学出版社, 2002.
[139]冯登国,裴定一.密码学导引.北京:科学出版社,1999.
[140] (芬兰)Arto Salomaa. (丁存生单炜娟译).公钥密码学.北京:国防工业出版社,1998.
[141](以色列)Oded Goldreich. (温巧燕,杨义先等译).密码学基础(第一卷).北京:人民邮电出版社,2003.
[142] (以色列)Oded Goldreich. (温巧燕,杨义先等译).密码学基础(第二卷).北京:人民邮电出版社,2005.
[143]张福泰,李继国,王晓明等.密码学教程.武汉:武汉大学出版社,2006.
[144]章照止.现代密码学基础.北京:北京邮电大学出版社,2004.
[145]陈鲁生沈世镒.现代密码学.北京:科学出版社,2002.
[146]卢开澄.计算机密码学-计算机网络中的数据保密与安全(第三版).北京:清华大学出版社,2003
[147]陈恭亮.信息安全数学基础.北京:清华大学出版社,2004.
[148]宋光天.交换代数导引.合肥:中国科学技术大学出版社,2002.
[149](加)Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. (胡磊王鹏等译).应用密码学手册.电子工业出版社,2005.
[150](英)Wenbo Mao(王继林伍前红等译).现代密码学理论与实践.北京:电子工业出版社,2004.
[151]杨波.现代密码学.北京:清华大学出版社,2003.
[152]陈原.公钥加密与混合加密的可证明安全性研究[D].西安:西安电子科技大学,2006.
[2] Adleman L M. A subexponential algorithm for the discrete logarithm problem with applications to cryptography. Proceedings of the IEEE 20th Annual Symposium on Foundations of Computer Science, 1979, 55-60.
[3] Adleman L M. The function field sieve. Algorithmic Number Theory, LNCS 877, Berlin: Springer-Verlag, 1994, pp. 108-121.
[4] Adleman L M and Demarrais J. A subexponential algorithm for discrete logarithms over all finite fields. Mathematics of Computation, 1993, 61, pp. 1-15.
[5] Adleman L M, DeMarrais J and Huang M D. A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields. Algorithmic Number Theory, LNCS 877, Berlin: Springer-Verlag, 1994, pp. 28-40.
[6] Ajtai M, Kumar R and Sivakumar D. A sieve algorithm for the shortest lattice vector problem. Proc. 33rd ACM Symp. on Theory of Comput., New York, ACM Press, 2001, pp. 601–610.
[7] Anshel I, Anshel M and Goldfeld D. An algebraic method for public key cryptography. Mathematical Research Letters, 1999, 6(3), pp. 287–291.
[8] Babai L. On Lovasz’lattice reduction and the nearest lattice point problem. Combinatorica, 1986, 6(1), pp. 1-13.
[9] Bao F, Deng R and Zhu H. Variations of Diffie-Hellman problem. ICICS'2003, LNCS 2836, Berlin: Springer-Verlag, 2003, pp. 301–312.
[10] Beame P W, Cook S A and Hoover H J. Log depth circuits for division and related problems. SIAM J. Comput. 1986, 15, pp. 994-1003.
[11] Bellare M, Boldyreva A, and Micali S. Public-key encryption in a multi-user setting: security proofs and improvements. In Advances in Cryptology–Eurocrypt 2000, LNCS 1807, Berlin: Springer-Verlag pages, 2000, pp.259-274.
[12] Bellare M, Desai A, Pointcheval D, et al. Relations among notions of security for public-key encryption schemes. Advances in Cryptology–Crypto’98, LNCS 1462, Berlin: Springer-Verlag pages, 1998, pp. 26–45.
[13] Bellare M and Goldwasser S. New paradigm for digital signatures and message authentication based on non-interactive zero knowledge proofs. Advancesin Cryptology–CRYPTO’89, LNCS 435, Berlin: Springer-Verlag, 1990, pp. 194–211.
[14] Bellare M and Rogaway P. Minimizing the use of random oracles in authenticated encryption schemes. Information and communications security, LNCS 1334, Berlin: Springer-Verlag, 1997, pp. 1-16.
[15] Bellare M and Rogaway P. Optimal asymmetric encryption. In Advances in Cryptology-Eurocrypt’94, LNCS 950, Berlin: Springer-Verlag pages, 1994, pp.92-111.
[16] Birgit P and Ahmadeza S. Anonymous fingerprinting with direct non-repudiation. Advances in Cryptology–Asiacrypt'2000, LNCS 1976, Berlin: Springer-Verlag, 2000, pp. 401-414.
[17] Birman J, Ko K and Lee S. The infimum, supremum, and geodesic length of a braid conjugacy class. Adv. in Math, 2001, 164(1), pp. 41–56.
[18] Blackburn S R and Galbraith S D. Cryptanalysis of two cryptosystems based on group actions. Advances in Cryptology-Asiacrypt’99, LNCS 1716, Berlin: Springer-Verlag, 1999, pp. 52-61.
[19] Blum M and Micali S. How to generate cryptographically strong sequence of pseudo-random bits. SIAM J. Comput. 1984, 13, pp. 850-864.
[20] Blyth T S. Dubreil-Jacotin inverse semigroups. Proc. Roy. Soc. Edinburgh. Sect., 1973, A71, pp. 345–360.
[21] Blyth T S. The structure of certain ordered regular semigroups. Proc. Roy. Soc. Edinburgh. Sect., 1976, A75, pp. 235–257.
[22] Blyth T S and Emilia G. Perfect elements in Dubreil-Jacotin regularsemigroups. Semigroup Forum, 1992, 45, pp. 55–62.
[23] Blyth T S and Janowitz M F. Residuation Theory. Pergamon Press, 1972.
[24] Boneh D. The decision Diffie-Hellman problem. Algorithmic Number Theory, Third International Symposium, ANTS-III, LNCS 839, Berlin: Springer-Verlag, 1998, pp. 48-63.
[25] Boneh D and Boyen X. Short signatures without random oracles. Advances in Cryptology-Eurocrypt’04, LNCS 3027, Berlin: Springer-Verlag, 2004, pp. 56-73.
[26] Boneh D and Boyen X. Secure identity based encryption without random oracles. Advances in Cryptology-Crypto'04, LNCS 3152, Berlin: Springer-Verlag, 2004, pp. 443-459.
[27] Boneh D and Boyen X. Efficient selective-ID secure identity-based encryption without random oracles. Advances in Cryptology-Eurocrypt’04, LNCS 3027, Berlin: Springer-Verlag, 2004, pp. 223-238.
[28] Boneh D, Boyen X and Shacham H. Short group signatures. Advances in Cryptology-Crypto'04, LNCS 3152, Berlin: Springer-Verlag, 2004, pp. 41-55.
[29] Boneh D and Franklin M. Identity based encryption from the Weil pairing. SIAM J. of Computing, 2003, 32(3), pp. 586-615.
[30] Boneh D and Lipton R J. Algorithms for black-box fields and their application to cryptography. Advances in Cryptology-Crypto’96, LNCS 1109, Berlin: Springer-Verlag, 1996, pp. 283-297.
[31] Boneh D, Lynn B, and Shacham H. Short signatures from the Weil pairing. Advances in Cryptology-Asiacrypt’01, LNCS 2248, Berlin: Springer-Verlag, 2001,pp. 514-532.
[32] Boneh D, Shen E, and Waters B. Strongly unforgeable signatures based on computational Diffie-Hellman. International Workshop on Practice and Theory in Public Key Cryptography 2006-PKC '06, LNCS 3958, Berlin: Springer-Verlag, 2006, pp. 229-240.
[33] Boneh D and Venkatesan R. Hardness of computing the most significant bits of secret keys in Diffie–Hellman and related schemes. Advances in Cryptology- CRYPTO'96, LNCS 1109. Berlin: Springer-Verlag, 1996, pp. 129-142.
[34] Boneh D and Venkatesan R. Rounding in lattices and its cryptographic applications. Proc. 8th Annual ACM-SIAM Symp. on Discr. Algorithms, New York, ACM Press, 1997, pp. 675-- 681.
[35] Brands S. An efficient off-line electronic cash system based on the representation problem, CWI Technical Report, CS-R9323, 1993.
[36] Bresson E, Chevassut O, and Pointcheval D. The group Diffie-Hellman problems. Workshop on selected areas in cryptography-SAC’02, LNCS 2595, Berlin: Springer-Verlag, 2002, pp. 325-338.
[37] Bresson E et al. A Generalization of DDH with Applications to Protocol Analysis and Computational Soundness. Advances in Cryptology-Crypto'2007, LNCS 4622, Berlin: Springer-Verlag, 2007, pp. 482-499.
[38] Burmester M, Desmedt Y, and Seberry J. Equitable key escrow with limited time span (or, how to enforce time expiration cryptographically). Advances in Cryptology–Asiacrypt'98, LNCS 1514, Berlin: Springer-Verlag, 1998, pp. 380–391.
[39] Canetti R. Universally composable security: a new paradigm for cryptographic protocols. Cryptology ePrint Archive, Report 2000/067, 2000. Available from: http://eprint.iacr.org.
[40] Canetti R, Friedlander J and Shaparlinski I E. On certain exponential sums and the distribution of Diffie-Hellman triples. J. London Math. Soc., 1999, 59, pp. 799-812.
[41] Cheon J and Jun B. A polynomial time algorithm for the braid Diffie-Hellman conjugacy problem. Advances in Cryptology -Crypto’03, LNCS 2729. Berlin: Springer-Veralg, 2003, pp. 212–225.
[42] Chor B, Fiat A and Naor M. Tracing traitors. Advances in Cryptology -CRYPTO’94, LNCS 839, Berlin: Springer-Verlag, 1994, pp. 257–270.
[43] Coppersmith D, Odlzyko A M and Schroeppel R. Discrete logarithms in GF(p). Algorithmica, 1986, 1, pp. 1-15.
[44] Cramer R and Shoup V. Design and analysis of practical publickey encryption schemes secure against sdaptive chosen ciphertext attack. SIAM Journal of Computing, 2003, 33(1), pp. 167-226.
[45] Cramer R and Shoup V. A practical public key cryptosystem provably secureagainst adaptive chosen ciphertext attack. Advances in Cryptology-Crypto’98, LNCS 1462. Berlin: Springer-Veralg, 1998, pp. 13-25.
[46] Cramer R and Shoup V. Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public key encryption. Advances in Cryptology -Eurocypt’02, LNCS 2332. Berlin: Springer-Veralg, 2002, pp. 45-64.
[47] Diffie W and Hellman M E. New directions in cryptography. IEEE Trans. Inform. Theory, 1976, 22(6): 644-654.
[48] Dolev D, Dwork C, and Naor M. Non-malleable cryptography. In 23rd Annual ACM Symposium on Theory of Computing, 1991, pp. 542–552.
[49] Dolev D, Dwork C, and Naor M. Non-malleable cryptography. SIAM J. Comput., 2000, 30(2), pp. 391–437.
[50] ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inform. Theory, 1985, 31(4), pp. 469-472.
[51] El Mahassni E, Nguyen P Q and Shparlinski I E. The insecurity of Nyberg-Rueppel and other DSA-like signature schemes with partially known nonces. Proceedings of Cryptography and Lattices Conference, Berlin Heidelberg: Springer, 2001, pp. 97-109.
[52] Frey G and Rück H G. A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Mathematics of Computation, 1994, 62, pp. 865-874.
[53] Franco N and Gonzales-Meneses J. Conjugacy problem for braid groups and Garside groups. J. Algebra, 2003, 266(1), pp. 112–132.
[54] Fujisaki E and Okamoto T. How to enhance the security of public-key encryption at minimum cost. International Workshop on Practice and Theory in Public Key Cryptography 99-PKC’99. LNCS 1560, Berlin: Springer-Verlag pages, 1999, pp. 53–68.
[55] Goldreich O. Foundations of cryptography: Basic Tools. Cambridge: Cambridge University Press, 2001.
[56] Goldreich O. Foundations of cryptography Volume 2: Basic Applications. Cambridge: Cambridge University Press, 2004.
[57] Goldreich O, Goldwasser S and Micali S. How to construct random functions]. Journal of ACM, 1986. 33, pp. 792–807.
[58] Goldreich O and Ostrovsky R. Software protection and simulation on oblivious RAMs. Journal of ACM, 1996. 43(3), pp. 431–473.
[59] Goldreich O and Levin L. A hard-core predicate for all one-way functions. Proc. 21st Ann. ACM Symp. On Theory of Computing, 1989, pp. 25-32.
[60] Goldwasser S and Micali S. Probabilistic encryption. Journal of Computer and System Sciences, 1984, 28, pp. 270–299.
[61] Gonzalez-Meneses J. Improving an algorithm to solve Multiple Simultaneous Conjugacy Problems in braid groups. Available fromhttp://xxx.lanl.gov/abs/math.GT/0212150.
[62] González Vasco M I and Shparlinski I E. On the security of Diffie–Hellman bits. Proc. Workshop on Cryptography and Computational Number Theory, Singapore 1999, Birkh?user, 2001, pp. 257–268.
[63] González Vasco M I and Shparlinski I E. Security of the most signi.cant bits of the shamir message passing scheme. Math. Comp., 2002, 71, pp. 333–342.
[64] Heiman R. A note on discrete logarithms with special structure. Advances in Cryptology-Eurocrypt’92, LNCS 658, Berlin: Springer-Verlag, 1993, pp. 454-457.
[65] Hellman M E and Reyneri J M. Fast computation of discrete logarithms in GF(q). Advances in Cryptology-Crypto 82, LNCS 658, Berlin: Springer-Verlag, 1982, pp. 3-13.
[66] Howie J M. An introduction to semigroup theory. London: Academic Press, 1976.
[67] Huang H W. Some contributions to ordered semigroup. Master’s thesis, Jiangxi Normal Unverisity, 2004.
[68] Hughes J. A linear algebraic attack on the AAFG1 braid group cryptosystem. ACISP 2002, LNCS 2384, Berlin: Springer-Veralg, 2002, pp. 212–225.
[69] Hughes J and Tannenbaum A. Length-based attacks for certain group based encryption rewriting systems. Workshop SECI02 Security of Communications on the Internet, Tunis, Tunisa, 2002, pp. 5-12.
[70] Joux A. A one round protocol for tripartite Diffie-Hellman. Proceedings of ANTS IV, LNCS 1838, Berlin: Springer-Verlag, 2000, pp. 385-394.
[71] Joux A and Nguyen K. Separating decision Diffie-Hellman from Diffie-Hellman in cryptographic groups. Journal of Cryptology, 2003, 16 (4), pp. 239-247.
[72] Knuth D E. The art of computer programming-sorting and searching, volume 3, Addison-Wesley, Reading, Massachusetts, 1973.
[73] Ko K H, Lee S J, Cheon J H, et al. New public-key cryptosystem using braid groups. Advances in Cryptology-Crypto 2000, LNCS 1880, Berlin: Springer-Verlag, 2000, pp. 166-183.
[74] Koblitz N. Algebraic aspects of cryptography. Berlin: Springer-Veralg, 1998.
[75] Lee I S, Kim W H, Kwon D, et al. On the security of MOR public key cryptosystem. Advances in Cryptology–Asiacrypt’04, LNCS 3329, Berlin: Springer-Verlag, 2004, pp. 387-400.
[76] Lenstra A K, Lenstra H W, and Lovasz L. Factoring polynomials with rational coefficients. Mathematische Annalen, 1982, 261(4),pp. 515–534.
[77] Lidl R and Niederreiter H. Introduction to finite fields and their applications. Cambridge : Cambridge University Press, 1986.
[78] Luby M and Rackoff C. How to construct pseudorandom permutations and pseudorandom functions. SIAM Journal of Computing, 1988. 17, pp. 373–386.
[79] Mahlburg K. An overview of braid group cryptography. Available fromhttp://www.math.wisc.edu/~boston/mahlburg.pdf.
[80] Mao Wenbo. Modern Cryptography: Theory and Practice. Beijing: Publishing House of Electronics Industry, 2004.
[81] Maurer U M. Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms, Advances in Cryptology-Crypto’94, LNCS 839, Berlin: Springer-Verlag, 1994, pp. 271-281.
[82] Maurer U M and Wolf S. Diffie-Hellman oracles. Advances in Cryptology-Crypto’96, LNCS 1109, Berlin: Springer-Verlag, 1996, pp. 268-282.
[83] Maurer U M and Wolf S. Lower bounds on generic algorithms in groups. Advances in Cryptology-Eurocrypt '98, LNCS 1403, Berlin: Springer-Verlag, 1998, pp. 72-84.
[84] Maurer U M and Wolf S. The relationship between breaking the Diffie–Hellman protocol and computing discrete logarithms. SIAM J. Comput., 1999, 28(5), pp. 1689–1721.
[85] Maurer U M and Wolf S. The Diffie-Hellman protocol. Designs, Codes, and Cryptography, 2000, 19, pp. 147-171.
[86] Maurer U M and Wolf S. Diffie-Hellman, Decision Diffie-Hellman, and discrete logarithms. In IEEE Symposium on Information Theory, Cambridge, USA, 1998, pp. 327.
[87] Maze G. Algebraic methods for constructing one-way trapdoor functions. PhD thesis, University of Notre Dame, May 2003.
[88] Maze G, Monico C and Rosenthal J. A public key cryptosystem based on actions by semigroups. In Proceedings of the 2002 IEEE International Symposium on Information Theory. Lausanne, Switzerland: Institute of Electrical and Electronics Engineers Inc 2002, pp. 266.
[89] Maze G, Monico C and Rosenthal J. Public key cryptography based on simple modules over simple rings. In Proceedings of the 2002 Mathematical Theory of Networks and System, Notre Dame: University of Notre Dame. 2002.
[90] Maze G, Monico C and Rosenthal J. Public key cryptography based on semigroup actions. http://www.math.unizh.ch/user/gmaze/Articles/CryptoArxiv.pdf. 2005, to appear in Advances of Mathematics of Communications. To appear in Advances of Mathematics of Communications.
[91] McCurley K S. Cryptographic key distribution and computation in class groups. Mollin R A, editor, Number Theory and Applications, Kluwer Academic Publishers, 1989, pp. 459-479.
[92] McCurley K S. The discrete logarithm problem. Pomerance C, editor, Cryptology and Computational Number Theory, volume 42 of Proceedings of Symposia in Applied Mathematics, American Mathematical Society, 1990, pp. 49-74.
[93] McFadden R and O’Carroll L. F-inverse semigroups. Proc. London. Math. Soc., 1971, 22 (3), pp. 652–666.
[94] Menezes A, Okamoto T and Vanstone S. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Transactions on Information Theory, 1993, 39, pp. 1639-1646.
[95] Menezes A, van Oorschot P and Vanstone S. Handbook of Applied Cryptography. Boca Raton, FL: CRC Press Series on Discrete Mathematics and its Applications, CRC Press, 1997.
[96] Monico C. Semirings and semigroup actions in public-key cryptography. Dissertation for the Doctoral Degree, Notre Dame: University of Notre Dame. 2002.
[97] Naor M and Reingold O. Number-theoretic constructions of efficient pseudo-random functions. Journal of ACM, 2004, 51(2), pp. 231-262.
[98] Naor M and Yung M. Public-key cryptosystems provably secure against chosen ciphertext attacks. In 22nd Annual ACM Symposium on Theory of Computing, 1990, pp. 427–437.
[99] Naor M and Reingold O. Synthesizers and their application to the parallel construction of pseudo-randomfunctions. Journal of Computer and System Sciences, 1999, 58(2), pp. 336-375.
[100] Nguyen P Q and Shparlinski I E. The insecurity of the digital signature algorithm with partially known nonces. J. Cryptology, 2002, 15(3), pp. 151–176.
[101] Nguyen P Q and Shparlinski I E. The insecurity of the elliptic curve digital signature algorithm with partially known nonces. Designs, Codes and Cryptography, 2003, 30(2), pp. 201–217.
[102] Okamoto T and Pointcheval D. The gap-problems: a new class of problems for the security of cryptographic schemes. International Workshop on Practice and Theory in Public Key Cryptography 2001-PKC’01, LNCS 1992, Berlin: Springer-Verlag, 2001, pp. 104-118.
[103] Otto F and Staller-Klein. Some remarks on finitely presented monoids with automatic structure. Available from http://citeseer.ist.psu.edu/34256.html.
[104] Paeng S H and Ha K C. New public key cryptosystem using finite non abelian groups. Advances in Cryptology-Crypto’01, LNCS 2139, Berlin: Springer-Verlag, 2001, pp. 470-485.
[105] Petrich M. Inverse Semigroups. New York : Wiley-Interscience, 1984.
[106] Pohlig S C and Hellman M E. An improved algorithm for computing logarithms over GF(p) nd its cryptographic significance. IEEE Transactions on Information Theory, 1978, 24, pp. 106-110.
[107] Pollard J M. Monte Carlo methods for index computation (mod p). Mathematics of Computation, 1978, 32, pp. 918-924.
[108] Rackoff C and Simon D. Noninteractive zero-knowledge proof of knowledge and chosen ciphertext attack. Advances in Cryptology–Crypto’91, LNCS 576, Berlin: Springer-Verlag, 1991, pp. 433-444.
[109] Reif J. On threshold circuits and polynomial computation. Proc. Of the 2nd Conference on Structure in Complexity Theory, 1987, pp. 118-123.
[110] Reif J and Tate S. On threshold circuits and polynomial computation. SIAM J. Comput., 1992, 5, pp. 896-908.
[111] Rose J S. A course on group theory. Cambridge: Cambridge University Press, 1978.
[112] Schacham H. A Cramer-Shoup encryption scheme from the linear assumption and from progressively weaker linear variants. http://eprint.iacr.org/2007/074.pdf.
[113] Shor P W. Algorithms for quantum computation: discrete logarithms and factoring. Proceedings of the IEEE 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124-134.
[114] Shoup V. Lower bounds for discrete logarithms and related problems. Advances in Cryptology-Eurocrypt’97 , LNCS 1233. Berlin: Springer-Verlag, 1997, pp. 256-266.
[115] Shparlinski I E. Sparse polynomial approximation in finite fields. Proc. 33rd ACM Symp. on Theory of Comput. New York: ACM Press, 2001, pp. 209–215.
[116] Shparlinski I E. Hidden number problem and its applications. Proc. 7th Spanish Meeting on Cryptology and Information Security, Vol.1. Oviedo: Univ. of Oviedo, 2002, pp. 49–72.
[117] Shparlinski I E. Noisy interpolation of sparse polynomials in finite fields. Applicable Algebra in Engineering, Communication and Computing, 2005, 16(5), pp. 307-317.
[118] Shparlinski I E. Playing“Hide-and-Seek”in finite fields: Hidden number problem and its applications. Proc. 7th Spanish Meeting on Cryptology and Information Security, Vol.1, Univ. of Oviedo, 2002, pp. 49–72.
[119] Shpilrain V and Ushakov A. Thompson’s group and public key cryptography. Applied Cryptography and Network Security 2005, LNCS 3531, Berlin: Springer-Verlag, 2005, pp. 151-163.
[120] Siu K Y, Bruck J, Kailath T, et al. Depth efficient neural network for division and related problems, IEEE Trans. Inform. Theory, 1993, 39, pp. 946-956.
[121] Siu K Y and Roychowdhury. On optimal depth threshold circuits for multiplication and related problems. SIAM J. Disc. Math., 1994, 7(2), pp. 284-292.
[122] Smart N P. The discrete logarithm problem on elliptic curves of trace one. Journal of Cryptology, 1999, 12, pp. 193-196.
[123] Stadler M. Publicly verifiable secret sharing. Advances in Cryptology–Eurocrypt'96, LNCS 1070, Berlin: Springer-Verlag, 1996, pp. 190-199.
[124] Steiner M, Tsudik G and Waidner M. Diffie-Hellman key distribution extended to group communication. In Proc. of ACM CCS '96. New York: ACM Press,1996, pp. 31--37.
[125] Thiong Ly J A. A serial version of the Pohlig-Hellman algorithm for computing discrete logarithms. Applicable Algebra in Engineering, Communication and Computing, 1993, 4, pp. 77-80.
[126] Tsiounis Y and Yung M. On the security of ElGamal based encryption. Public Key Cryptography-PKC’98, LNCS 1431, Berlin: Springer-Verlag, 1998, pp. 117-134.
[127] Tobias C. Security analysis of the MOR cryptosystem. International Workshop on Practice and Theory in Public Key Cryptography 2003-PKC’03, LNCS 2567, Berlin: Springer-Verlag, 2003, pp. 175-186.
[128] Van Oorschot P, Parallel collision search with applications to hash functions and discrete logarithms. 2nd ACM Conference on Computer and Communications Security, ACM Press, 1994, pp. 210-218.
[129] von zur Gathen J and Shparlinski I E. Polynomial Interpolation from Multiples. Proc.15th ACM-SIAM Symposium on Discrete Algorithms. Philadelphia: SIAM, 2004, pp. 1125-1130.
[130] Wagner N R and Magyarik M R. A public key cryptosystem based on the word problem. Advances in Cryptology- Crypto’84, LNCS 196, Berlin: Springer-Verlag, 1985, pp. 19-36.
[131] Xie X Y. An introduction to ordered semigroup theory. Beijing: Science Press in China, 2001.
[132] Yamamura A. Public-key cryptosystems using the modular group. International Workshop on Practice and Theory in Public Key Cryptography 1998-PKC’98, LNCS 1431, Berlin: Springer-Verlag, 1998, pp. 203-216.
[133]肖国镇,卿斯汉.编码理论.北京:国防工业出版社,1993.
[134]赖溪松,韩亮,张真诚(张玉清,肖国镇改编).计算机密码学及其应用.北京:国防工业出版社,2001.
[135]胡予濮,肖国镇.对称密码学.北京:机械工业出版社,2002 .
[136]王育民,刘建伟.通信网的安全-理论与技术.西安:西安电子科技大学出版社,1999.
[137]王新梅,肖国镇.纠错码-原理与方法(修订版).西安:西安电子科技大学出版社,2001
[138]裴定一祝跃飞.算法数论.北京:科学出版社, 2002.
[139]冯登国,裴定一.密码学导引.北京:科学出版社,1999.
[140] (芬兰)Arto Salomaa. (丁存生单炜娟译).公钥密码学.北京:国防工业出版社,1998.
[141](以色列)Oded Goldreich. (温巧燕,杨义先等译).密码学基础(第一卷).北京:人民邮电出版社,2003.
[142] (以色列)Oded Goldreich. (温巧燕,杨义先等译).密码学基础(第二卷).北京:人民邮电出版社,2005.
[143]张福泰,李继国,王晓明等.密码学教程.武汉:武汉大学出版社,2006.
[144]章照止.现代密码学基础.北京:北京邮电大学出版社,2004.
[145]陈鲁生沈世镒.现代密码学.北京:科学出版社,2002.
[146]卢开澄.计算机密码学-计算机网络中的数据保密与安全(第三版).北京:清华大学出版社,2003
[147]陈恭亮.信息安全数学基础.北京:清华大学出版社,2004.
[148]宋光天.交换代数导引.合肥:中国科学技术大学出版社,2002.
[149](加)Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. (胡磊王鹏等译).应用密码学手册.电子工业出版社,2005.
[150](英)Wenbo Mao(王继林伍前红等译).现代密码学理论与实践.北京:电子工业出版社,2004.
[151]杨波.现代密码学.北京:清华大学出版社,2003.
[152]陈原.公钥加密与混合加密的可证明安全性研究[D].西安:西安电子科技大学,2006.