New Public Key Cryptosystems from Combinatorial Group Theory

External direct product of some low layer groups such as braid groups and general Artin groups, with a kind of special group action on it, provides a secure cryptographic computation platform, which can keep secure in the quantum computing epoch. Three hard problems on this new platform, Subgroup Root Problem, Multi-variant Subgroup Root Problem and Subgroup Action Problem are presented and well analyzed, which all have no relations with conjugacy. New secure public key encryption system and key agreement protocol are designed based on these hard problems. The new cryptosystems can be implemented in a general group environment other than in braid or Artin groups.

An Efficient and Practical Public Key Cryptosystem with CCA-Security on Standard Model

Chosen Ciphertext Attack （CCA） security on the standard model is widely accepted as the standard security notion for the public key cryptosystem. The existing CCA-secure public key cryptosystems on the standard model are expensive in terms of efficiency and practicality. In this paper, an efficient and practical public key cryptosystem is presented over the group of signed quadratic residues. It is provably secure against CCA on the standard model. Furthermore, public verifiability for this scheme is also realized in the way that projects the verification privacy key into public key on trapdoor pretending. It will be useful to devise efficient CCA-secure threshold and proxy re-encryption schemes on the standard model.

Practical Cryptanalysis of a Public Key Cryptosystem Based on the Morphism of Polynomials Problem

Multivariate Public Key Cryptography （MPKC） has intensively and rapidly developed during the past three decades. MPKC is a promising candidate for post-quantum cryptography. However, designing it is universally regarded as a difficult task to design a secure MPKC foundation scheme, such as an encryption scheme and key exchange scheme. In this work, we investigate the security of a new public key cryptosystem that is based on the Morphism of Polynomials （MP）. The public key cryptosystem proposed by Wang et al. （Wuhan University, China） comprises a key exchange scheme and encryption scheme. Its security can be provably reduced to the hardness of solving a new difficult problem, namely, the Decisional Multivariate Diffie Hellman （DMDH） problem. This problem Js a variant of the MP problem, which is difficult to solve by random systems. We present a proposition that reduces the DMDH problem to an easy example of the MP problem. Then, we propose an efficient algorithm for the Key Recover Attack （KRA） on the schemes of the public key cryptosystem. In practice, we are able to entirely break the cryptosystem＇s claimed parameter of 96 security levels in less than 17.252 s. Furthermore, we show that finding parameters that yield a secure and practical scheme is impossible.

Batch Private Keys Generation for RSA in Security Communication Systems

RSA public key cryptosystem is extensively used in information security systems. However, key generation for RSA cryptosystem requires multiplicative inversion over finite field, which has higher computational complexity, compared with either multiplication in common sense or modular multiplication over finite field. In order to improve the performance of key generation, we propose a batch private keys generation method in this paper. The method derives efficiency from cutting down multiplicative inversions over finite field. Theoretical analysis shows that the speed of batch private keys generation for s users is faster than that of s times solo private key generation. It is suitable for applications in those systems with large amount of users.

New Weak Keys in RSA

The security of the RSA system with the prime pairs of some special form is investigated. A new special-purpose algorithm for factoring RSA numbers is proposed. The basic idea of the method is to factor RSA numbers by factoring a well-chosen quadratic polynomial with integral coefficients. When viewed as a general-purpose algorithm, the new algorithm has a high computational complexity. It is shown thai the RSA number n = pq can be easily factored if p and q have the special form of p = as＋b, q=cs＋d, where a, b, c, d are relatively small numbers. Such prime pairs （p, q） are the weak keys of RSA, so when we generate RSA modulus, we should avoid using such prime pairs （p, q）.

FAPKC3: A New Finite Automaton PublicKey Cryptosystem

This paper deals with finite automaton public key cryptosystem and digital signatures. A new system FAPKC3 is proposed which can be used for encryption and implementing digital signatures as well. Some performances of a software implementation of FAPKC3 are presented and its security is discussed.

New Public-Key Cryptosystem Based on the Morphism of Polynomials Problem

During the last two decades, there has been intensive and fast development in Multivariate Public Key Cryptography （MPKC）, which is considered to be an important candidate for post-quantum cryptography. However, it is universally regarded as a difficult task, as in the Knapsack cryptosystems, to design a secure MPKC scheme （especially an encryption scheme） employing the existing trapdoor construction. In this paper, we propose a new key-exchange scheme and an MPKC scheme based on the Morphism of Polynomials （MP） problem. The security of the proposed schemes is provably reducible to the conjectured intractability of a new difficult problem, namely the Decisional Multivariate Diffie-Hellman （DMDH） problem derived from the MP problem. The proposed key agreement is one of several non-number-theory-based protocols, and is a candidate for use in the post-quantum era. More importantly, by slightly modifying the protocol, we offer an original approach to designing a secure MPKC scheme. Furthermore, the proposed encryption scheme achieves a good tradeoff between security and efficiency, and seems competitive with traditional MPKC schemes.

基于纠错编码的多变量公钥加密方案(英文)

Advances in quantum computers pose potential threats to the currently used public-key cryptographic algorithms such as RSA and ECC.As a promising candidate against attackers equipped with quantum computational power,Multivariate Public-Key Cryptosystems(MPKCs)has attracted increasing attention in recently years.Unfortunately,the existing MPKCs can only be used as multivariate signature schemes,and the way to construct an efficient MPKC enabling secure encryption remains unknown.By employing the basic MQ-trapdoors,this paper proposes a novel multivariate encryption scheme by combining MPKCs and code-based public-key encryption schemes.Our new construction gives a positive response to the challenges in multivariate public key cryptography.Thorough analysis shows that our scheme is secure and efficient,and its private key size is about 10 times smaller than that of McEliece-type cryptosystems.

A Certificateless Threshold Public Key Encryption Scheme

The decryption participant＇s private key share for decryption is delegated by key generation center in the threshold IBE scheme.However,a key generation center which is absolutely trustworthy does not exist.So the author presents a certificateless threshold public key encryption scheme.Collaborating with an administrator,the decryption participant generates his whole private key share for decryption in the scheme.The administrator does not know the decryption participant＇s private key share for decryption.Making use of q-SDH assumption,the author constructs a certificateless threshold public key encryption scheme.The security of the scheme is eventually reduced to the solving of Decisional Bilinear Diffie-Hellman problem.Moreover,the scheme is secure under the chosen ciphertext attack in the standard model.

A PRACTICAL PARALLEL ALGORITHM FOR COMPUTING a^b mod c

In this paper,we propose a. practical parallel algorithm for computing ab mod c. The algorithm is based on RES representations of integers. In particular, a technique is introduced for avoiding overflow.The algorithm is easy to be implemented on hardware and achieves linear speedup.

Cryptographic Protocols Based on Nielsen Transformations

We introduce in this paper cryptographic protocols which use combinatorial group theory. Based on a combinatorial distribution of shares we present secret sharing schemes and cryptosystems using Nielsen transformations. Nielsen transformations are a linear technique to study free groups and general infinite groups. In addition the group of all automorphisms of a free group F, denoted by AUT (F), is generated by a regular Nielsen transformation between two basis of F, and each regular Nielsen transformation between two basis of F defines an automorphism of F.

New designing of cryptosystems based on quadratic fields

This paper proposes a method to construct new kind of non-maximal imaginary quadratic order （NIQO＊） by combining the technique of Diophantine equation and the characters of non-maximal imaginary quadratic order. It is proved that in the class group of this new kind of NIQO＊, it is very easy to design provable secure cryptosystems based on quadratic field （QF）. With the purpose to prove that this new kind of QF-based cryptosystems are easy to implement, two concrete schemes are presented, i.e., a Schnorr-like signature and an EIGamel-like encryption, by using the proposed NIQO＊. In the random oracle model, it is proved that： （1） under the assumption that the discrete logarithm problem over class groups （CL-DLP） of this new kind of NIQO＊ is intractable, the proposed signature scheme is secure against adaptive chosen-message attacks, i.e., achieving UF-CMA security; （2） under the assumption that the decisional Diffie-Hellman problem over class groups （CL-DDH） of this new kind of NIQO＊ is intractable, the enhanced encryption in this paper is secure against adaptive chosen-ciphertext attacks, i.e., reaching IND-CCA2 security.

Protecting Web Application Code and Sensitive Data with Symmetric and Identity-Based Cryptosystems

How to protect the security of web application code and sensitive data has become one of the primary concerns in web services.In this paper,symmetric cryptosystem combined with identity-based public key cryptosystem is proposed to protect web application programs and sensitive data.The key generation center generates the private and public key pairs for the web server and users,which are used to implement identity authentication and data integrity.Whenweb application code and sensitive data are transmitted between the web server and the user’s browser,a random session key is generated for encrypting the web application code and sensitive data.Meanwhile,a digital signature is generated and added to the encrypted program code and sensitive data.The security analysis shows that the proposed security scheme can ensure the confidentiality,integrity and authentication of web application code and sensitive data.

Constructing Finite Automata with Invertibility bytransformation Method

Ra, Rb transformations were successfully applied to establish invertibility theory for linear and quasi-linear finite automata over finite fields. In aprevious paper, the authors generalized R., Rb transformations to deal with nonlinear memory finite automata, and gave sufficient conditions for weak inverse andfor weakly invertible memory finite automata and inversion processes concerned;methods by transformation to generate a kind of nonlinear memory finite automatasatisfying one of these sufficient conditions were also given. This paper extends theconcepts, methods and results to general finite automata, in which states consist offinite input history, finite output history and finite 'inner state' history.

Probability method for cryptanalysis of general multivariate modular linear equation

Finding the solution to a general multivariate modular linear equation plays an important role in cryptanalysis field. Earlier results show that obtaining a relatively short solution is possible in polynomial time. However, one problem arises here that if the equation has a short solution in given bounded range, the results outputted by earlier algorithms are often not the ones we are interested in. In this paper, we present a probability method based on lattice basis reduction to solve the problem. For a general multivariate modular linear equation with short solution in the given bounded range, the new method outputs this short solution in polynomial time, with a high probability. When the number of unknowns is not too large （smaller than 68）, the probability is approximating 1. Experimental results show that Knapsack systems and Lu-Lee type systems are easily broken in polynomial time with this new method.

Fast VLSI Implementation of Modular Inversion in Galois Field GF(p)

Modular inversion is one of the key arithmetic operations in public key cryptosystems, so low-cost, high-speed hardware implementation is absolutely necessary. This paper presents an algorithm for prime fields for hardware implementation. The algorithm involves only ordinary addition/subtraction and does not need any modular operations, multiplications or divisions. All of the arithmetic operations in the algorithm can be accomplished by only one adder, so it is very suitable for fast very large scale integration (VLSI) implementation. The VLSI implementation of the algorithm is also given with good performance and low silicon penalty.