Weak-Keys in Public Key Cryptosystems Based on Discrete Logarithms

The discrete logarithm method is the foundation of many public key algorithms. However, one type of key, defined as a weak-key, reduces the security of public key cryptosystems based on the discrete logarithm method. The weak-key occurs if the public key is a factor or multiple of the primitive element, in which case the user＇s private key is not needed but can be obtained based on the character of the public key. An algorithm is presented that can easily test whether there is a weak-key in the cryptosystem. An example is given to show that an attack can be completed for the Elgamal digital signature if a weak-key exists, therefore validating the danger of weak-keys. Methods are given to prevent the generation of these weak-keys.

Security Analysis of Discrete Logarithm Based Cryptosystems

Discrete logarithm based cryptosysterns have subtle problems that make the schemes vulnerable. This paper gives a comprehensive listing of security issues in the systems and analyzes three classes of attacks which are based on mathematical structure of the group which is used in the schemes, the disclosed information of the subgroup and implementation details respectively. The analysis will, in turn, allow us to motivate protocol design and implementation decisions.

Threshold Signature Scheme Based on Discrete Logarithm and Quadratic Residue

Digital signature scheme is a very important research field in computer security and modern cryptography. A (k, n) threshold digital signature scheme is proposed by integrating digital signature scheme with Shamir secret sharing scheme. It can realize group-oriented digital signature, and its security is based on the difficulty in computing discrete logarithm and quadratic residue on some special conditions. In this scheme, effective digital signature can not be generated by anyk?1 or fewer legal users, or only by signature executive. In addition, this scheme can identify any legal user who presents incorrect partial digital signature to disrupt correct signature, or any illegal user who forges digital signature. A method of extending this scheme to an Abelian group such as elliptical curve group is also discussed. The extended scheme can provide rapider computing speed and stronger security in the case of using shorter key. Key words threshold scheme - digital signature - discrete logarithm - quadratic residuc - threshold digital signature CLC number TP 309. 7 Foundation item: Supported the National Nature Science Foundation of China, Hubei Province (90104005, 2002 AB0039)Biography: FEI Ru-chun (1964-), male, Ph. D candidate, Associated professor, research direction: information security and cryptography.

Constructing Representative Collective Signature Protocols Using The GOST R34.10-1994 Standard

The representative collective digital signature,which was suggested by us,is built based on combining the advantages of group digital signature and collective digital signature.This collective digital signature schema helps to create a unique digital signature that deputizes a collective of people representing different groups of signers and may also include personal signers.The advantage of the proposed collective signature is that it can be built based on most of the well-known difficult problems such as the factor analysis,the discrete logarithm and finding modulo roots of large prime numbers and the current digital signature standards of the United States and Russian Federation.In this paper,we use the discrete logarithmic problem on prime finite fields,which has been implemented in the GOST R34.10-1994 digital signature standard,to build the proposed collective signature protocols.These protocols help to create collective signatures:Guaranteed internal integrity and fixed size,independent of the number of members involved in forming the signature.The signature built in this study,consisting of 3 components(U,R,S),stores the information of all relevant signers in the U components,thus tracking the signer and against the“disclaim of liability”of the signer later is possible.The idea of hiding the signer’s public key is also applied in the proposed protocols.This makes it easy for the signing group representative to specify which members are authorized to participate in the signature creation process.

A Proxy Blind Signature Scheme Based on DLP

A proxy signature scheme allows an original signer to delegate his signing capability to a proxy signer who can sign on behalf of the original signer. A blind signature is the concept with a salient feature that the signer can not make a linkage between the blind signature and the identity of the requester. Proxy signature and blind signature are used widely in electronic commerce. With satisfying the security properties of both two signatures, a new proxy blind signature scheme based on discrete logarithm problem is proposed.

Enhancing the Security of He-Kiesler Signature Schemes

Although the He Kiesler signature is said to be proposed based on the discrete logarithm problem and the factorization problem, it has been proved that the signature is not as secure as it was stated to be. A new signature scheme is here proposed based on the discrete logarithm problem and the factorization problem to enhance the security of the He Kiesler signature.

AN EFFICIENT AND SECURE (t, n) THRESHOLD SECRET SHARING SCHEME

Based on Shamir’s threshold secret sharing scheme and the discrete logarithm problem, a new (t, n) threshold secret sharing scheme is proposed in this paper. In this scheme, each participant’s secret shadow is selected by the participant himself, and even the secret dealer cannot gain anything about his secret shadow. All the shadows are as short as the shared secret. Each participant can share many secrets with other partici- pants by holding only one shadow. Without extra equations and information designed for verification, each participant is able to check whether another participant provides the true information or not in the recovery phase. Unlike most of the existing schemes, it is unnecessary to maintain a secure channel between each par- ticipant and the dealer. Therefore, this scheme is very attractive, especially under the circumstances that there is no secure channel between the dealer and each participant at all. The security of this scheme is based on that of Shamir’s threshold scheme and the difficulty in solving the discrete logarithm problem. Analyses show that this scheme is a computationally secure and efficient scheme.

Threshold Decryption Scheme withMultiple Policies

Based on the difficulty in computing discrete logarilhm and square 1001 onsome special conditions, we propose a basic threshold seeret sharing scheme for multiple secretswith multiple policies, which allows a group of users to share multiple secrttkeys and only onesecret shadow to be ktpt by each user. An efficient threshold decryption scheme with multiplepolicies is designed on the basis of the basic threshold scheme. This decryption scheme allowsmultiple secret keys to he shared among a groupof users, and each user to ketp only one secretshadow. Different public keys can be used to encrypt documents. If and only if the number ofcooperated users who koop the secret shadows is greater than or c-qual to the threshold value of thecorresponding secret key, they can cooperate to decrypt the documents. It is proved that theproposed scheme has very strong security, unless the attackers can solve the discrete logarithmproblem and the square root problem.

A Provably Secure and Efficient Remote Password Authentication Scheme Using Smart Cards

Communication technology has advanced dramatically amid the 21st century,increasing the security risk in safeguarding sensitive information.The remote password authentication(RPA)scheme is the simplest cryptosystem that serves as the first line of defence against unauthorised entity attacks.Although the literature contains numerous RPA schemes,to the best of the authors’knowledge,only few schemes based on the integer factorisation problem(IFP)and the discrete logarithm problem(DLP)that provided a provision for session key agreement to ensure proper mutual authentication.Furthermore,none of the previous schemes provided formal security proof using the random oracle model.Therefore,this study proposed an improved RPA scheme with session key establishment between user and server.The design of the proposed RPA scheme is based on the widely established Dolev-Yao adversary model.Moreover,as the main contribution,a novel formal security analysis based on formal definitions of IFP and DLP under the random oracle model was presented.The proposed scheme’s performance was compared to that of other similar competitive schemes in terms of the transmission/computational cost and time complexity.The findings revealed that the proposed scheme required higher memory storage costs in smart cards.Nonetheless,the proposed scheme is more efficient regarding the transmission cost of login and response messages and the total time complexity compared to other scheme of similar security attributes.Overall,the proposed scheme outperformed the other RPA schemes based on IFP and DLP.Finally,the potential application of converting the RPA scheme to a user identification(UI)scheme is considered for future work.Since RPA and UI schemes are similar,the proposed approach can be expanded to develop a provably secure and efficientUI scheme based on IFP and DLP.

A New Digital Multilevel Proxy Signature Scheme Based on Elliptic Curve Cryptography

Based on the analysis of elliptic curve digital signature algorithm（ECDSA）,aiming at multilevel proxy signature in which the original signer delegates the digital signature authority to several proxies and its security demands, a new multilevel proxy signature scheme based on elliptic curve discrete logarithm problem （ECDLP） is presented and its security are proved.

Solving the Multi-discrete Logarithm Problems over a Group of Elliptic Curves with Prime Order

In this paper, we discuss the expected number of steps in solving multi-discrete logarithm problems over a group of elliptic curves with prime order by using Pollard＇s rho method and parallel collision search algorithm. We prove that when using these algorithms to compute discrete logarithms, the knowledge gained through computing many logarithms does not make it easier for finding other logarithms. Hence in an elliptic cryptosystem, it is safe for many users to share the same curve, with different private keys.

Construction of k-ary Pseudorandom Elliptic Curve Sequences

We present a method for constructing k-ary sequences over elliptic curves. Using the multiplicative character of order k of finite fields, we construct a family of k-ary pseudorandom elliptic curve sequences. The pseudorandom measures, such as the well-distribution measure, the correlation measure of order e, and the linear complexity are estimated by using certain character sums. Such sequences share the same order of magnitude on the well-distribution measure, the correlation measure of order e as the ＇truly＇ random sequences. The method indicates that it is possible to construct ＇good＇ pseudorandom sequences over elliptic curves widely used in public key cryptography.

An Improved Sanitizable Signature Scheme

A new sanitizable signature scheme is proposed, in which the security flaw of Miyazaki＇s sanitizable signature scheme SUMI-4 is improved. The new scheme overcomes the shortcomings of the original scheme SUM1-4 by using sanitizable authorization certificates. The new scheme enables the primitive signer to limit the sanitizer＇s power and still satisfies the security request of sanitizable signature.

Digital Multi-Signature Scheme Based on the Elliptic Curve Cryptosystem

In the study, the digital multi-signature scheme, constructed by theintegration of one-way hash function and identification scheme, are proposed based on the ellipticcurve cryptosystem (ECC). To the efficiency in performance, the ECC has been generally regarded aspositive; and the security caused by the Elliptic Curve Discrete Logarithm Problem (ECDLP) is highlyalso taken highly important. The main characteristic of the proposed scheme is that the length ofthe multi-signature is fixed rather than changeable and it will not increase with the number ofgroup members.

Effective generalized equations of secure hyperelliptic curve digital signature algorithms

A hyperelliptic curve digital signature algorithm （HECDSA） can be viewed as the hyperelliptic curve analogue of the standard digital signature algorithm （DSA）. This article discusses divisor evaluations, the basic HECDSA, variants, two HECDSA equations and a 4-tuple HECDSA scheme, and puts forward a generalized equation for HECDSA. From this generalized equation, seven general HECDSA types are derived based on the efficiency requirements. Meanwhile, the securities of these general HECDSA types are analyzed in detail.

Targeted Fully Homomorphic Encryption Based on a Double Decryption Algorithm for Polynomials

Several public-key encryption schemes used to solve the problem of ciphertext data processing on the fly are discussed. A new targeted fully homomorphic encryption scheme based on the discrete logarithm problem is presented. Public-key encryption cryptosystems are classified to examine homomorphic encryption. Without employing techniques proposed by Gentry such as somewhat homomorphic and bootstrapping techniques, or relinearization technique proposed by Brakerski et al., a new method called ＂Double Decryption Algorithm＂ is employed in our cryptography to satisfy a fully or targeted fully homomorphic property. Inspired by EIGamal and BGN cryptography, we obtain the desired fully homomorphic property by selecting a new group and adding an extra component to the ciphertext. Proof of semantic security is also demonstrated.

Homomorphic MAC-Based Scheme against Pollution Attacks in Network Coding

Network coding can improve network throughput in large, but it is vulnerable to the data pollution attacks. In this paper, we propose an efficient homomorphic message authentication code （MAC） scheme with discrete logarithm to detect and locate the malicious nodes. We also prove the security property of the scheme theoretically. Its effectiveness is demonstrated, and overhead is analyzed through extensive experiments.

Pseudo-Randomness of Certain Sequences of k Symbols with Length pq

The theory of finite pseudo-random binary sequences was built by C. Mauduit and A. Sarkozy and later extended to sequences of k symbols （or k-ary sequences）. Certain constructions of pseudo-random sequences of k symbols were presented over finite fields in the literature. In this paper, two families of sequences of k symbols are constructed by using the integers modulo pq for distinct odd primes p and q. The upper bounds on the well-distribution measure and the correlation measure of the families sequences are presented in terms of certain character sums over modulo pq residue class rings. And low bounds on the linear complexity profile are also estimated.

Attack on an Efficient Certificateless Aggregate Signature without Pairing

A Certificateless Aggregate Signature(CLAS) scheme was proposed by Qu and Mu recently, which was published in "Int J. Electronic Security and Digital Forensics, 2018, 10(2)". They used discrete logarithm to ensure the scheme's security. However,we show by formulating an attack that their CLAS scheme cannot defend against Type I adversary. Furthermore, we point out an error that exists in the signature simulation of their security proof.After that we give a correct signature simulation for the security proof. Finally, to resist the Type I attack, we present two methods for improving Qu et al's CLAS scheme. Moreover, the second improving method can elevate the trust level of Qu et al's CLAS scheme to the highest trust level: Level 3.

Generalized Goldwasser and Micali’s Type Cryptosystem

In 1982,Goldwasser and Micali proposed the first probabilistic public key cryptosystem with indistinguishability under chosen plaintext attack security based on the quadratic residuosity assumption.Ciphertext expansion of Goldwasser's scheme is quite large,thereby the scheme is inefficient.A lot of schemes have been proposed to reduce the ciphertext expansion.Some schemes use the same encryption algorithm as Goldwasser's scheme with different parameters and keys,which we call them Goldwasser and Micali's type(GM-type)schemes.GM-type schemes can be divided into two categories according to different parameters and decryption algorithms.In this paper,we propose the first generalized GM-type scheme combining these two categories.All GM-type schemes are special cases of our generalized GM-type scheme.The ciphertext expansion of our scheme is smaller than that of any other GM-type schemes.