International Association
for Cryptologic Research

Almost cryptographic protocols are presented with security arguments. None of them, however, did explain why a protocol should like this, not like that. The reason is that there are short of any principles for designing and analyzing cryptographic protocols. In this paper, we put forth such a principle beyond security, called Less Parameters, which says that the involved parameters should be reduced as less as possible. Actually, the principle ensures a protocol better cost. In different scenarios, the principle is not easy to grasp. Intuitively, we advise to introduce public parameters as less as possible. In the light of the principle, we investigate some signatures. We believe the techniques developed in this paper will be helpful to better some cryptographic protocols.

In 2006, Boyen and Waters proposed an anonymous ID-based encryption. It is impressive that in the scheme the system secret key is a tuple of five numbers. The user's secret key is also a tuple of five elements. The authors did not explain why it should introduce so many parameters. In this paper, we simulate a general attempt to attack the scheme. It shows us which parameters are essential to the scheme and which parameters can be reasonably discarded. Based on the analysis we present a simplified version and an efficient version of the Boyen-Waters scheme. The analyzing technique developed in this paper is helpful to better other cryptographic protocols.

In 2001, Gottesman and Chuang proposed a quantum signature scheme. Unlike classical signature schemes, the public keys in the scheme can only be used once. The authors claim that the scheme is somewhat cumbersome but it serves as a good model and suggests novel research directions for the field of quantum cryptography. In this note, we remark that the Gottesman-Chuang quantum signature scheme is so commonplace and cumbersome that it can not suggest the potential for quantum public key cryptography. The authors ignore an ultimate fact, namely, the cost to grantee the authenticity of a user's public key is expensive in the scenario of Public Key Infrastructure. It entails that a user's public key should be repeatedly usable in the life duration.

In 2008, Libert and Vergnaud put forth a proxy re-encryption scheme (LV08 for short). Unlike some earlier PRE schemes, the LV08 scheme specifies a validity-checking process to guarantee that the received ciphertext is well-formed. In this paper, we clarify an ultimate fact that the received message is well-formed is the premise to decryption in all encryption schemes. The underlying mechanism to keep the communicated message well-formed in encryption schemes is another topic. The authors ignored the fact and proposed a cumbersome presentation. We will simplify the LV08 scheme and show its security level is the same as that of the scheme proposed by Ateniese et al in 2005. Therefore, the LV08 scheme can not ensure chosen-ciphertext security as claimed.

We present a birthday attack against DES. It is entirely based on the relationship $L_{i+1}=R_{i}$ and the simple key schedule in DES. It requires about $2^{16}$ ciphertexts of the same $R_{16}$, encrypted by the same key $K$. We conjecture it has a computational complexity of $2^{48}$. Since the requirement for the birthday attack is more accessible than that for Differential cryptanalysis, Linear cryptanalysis or Davies' attack, it is of more practical significance.

We introduce a message attack against DSA and show that the security of DSA is indeed reduced to the following problem, i.e., find $\theta\in \mathbb{Z}_q^*$ such that\\ \centerline{$z=(\hat g^{\theta} \,\mbox{mod}\, p)\, \mbox{mod}\, q $}\\ where $\mbox{Ord}_p(\hat g)=q$ and $z\in \mathbb{Z}_q^*$ is randomly chosen by the adversary. Compared with the common key-only attack, i.e., find $x\in \mathbb{Z}_q^*$ such that\\ \centerline{$ y= g^x \,\mbox{mod}\, p$}\\ the message attack is more effective because of the big gap between $|p|$ (1024-bit) and $|q|$ (160-bit).

Whether a recipient \textit{can prove} a signature to others is of great importance. The function is just one reason that we call a signature ``signature" rather than others. In this paper, we point out that one popular signcryption signature convinces \textit{only} the designated document's recipient that the signer deliberately signed the document. The \textit{designated recipient} can \textit{check} the validity of a given signcryptext but \textit{cannot prove} it to others. We also improve it using the efficient technique developed in Schnorr's signature instead of a zero-knowledge proof such that the receiver can \textit{check} the validity of a given signcryptext and \textit{can prove} it to a third party.

Checking whether a committed integer lies in a specific interval has many cryptographic applications. In Eurocrypt'98, Chan et al. proposed an instantiation (CFT for short). Based on CFT, Boudot presented an efficient range-bounded commitment scheme in Eurocrypt'2000. Both CFT proof and Boudot proof are based on the encryption $E(x, r)=g^xh^r\ \mbox{mod}\ n$, where $n$ is an RSA modulus whose factorization is \textit{unknown} by the prover. They did not use a single base as usual. Thus an increase in cost occurs. In this paper we show that it suffices to adopt a single base. The cost of the improved Boudot proof is about half of that of the original scheme. Moreover, the key restriction in the original scheme, i.e., both the discrete logarithm of $g$ in base $h$ and the discrete logarithm of $h$ in base $g$ are unknown by the prover, which is a potential menace to the Boudot proof, is definitely removed.

We introduce a set of criterions for classifying signature-only signature models. By the criterions, we classify signature models into 5 basic types and 69 general classes. Theoretically, 21140 kinds of signature models can be deduced by appropriately combining different general classes. The result comprises almost existing signature models. We also contribute a lot of new signature models. Moreover, we find the three signature models, i.e., group-nominee signature, multi-nominee signature and threshold-nominee signature, are of great importance in light of our classification.

A group signature scheme allows a group member of a given group to sign messages on behalf of the group in an anonymous and unlinkable fashion. In case of a dispute, however, a designated group manager can reveal the signer of a valid group signature. Many applications of group signatures require that the group manager can be split into a membership manager and a revocation manager. Such a group signature scheme with strong separability was proposed in paper [1]. Unfortunately, the scheme is insecure which has been shown in [2][3][4]. In this paper we show that the scheme is untraceable by a simple and direct attack. Besides, we show its universal forgeability by a general attack which only needs to choose five random numbers. We minutely explain the technique to shun the challenge in the scheme.

It's well known that Shor[1] proposed a polynomial time algorithm for prime factorization by using quantum computers. For a given number $n$, he gave an algorithm for finding the order $r$ of an element $x$ (mod $n$) instead of giving an algorithm for factoring $n$ directly. The indirect algorithm is feasible because factorization can be reduced to finding the order of an element by using randomization[2]. But a point should be stressed that the order of the number must be even. Actually, the restriction can be removed in a particular case. In this paper, we show that factoring RSA modulus (a product of two primes) only needs to find the order of $2$, whether it is even or not.

A group signature scheme allows a group member of a given group to sign messages on behalf of the group in an anonymous fashion. In case of a dispute, however, a designated group manager can reveal the signer of a valid group signature. In the paper, we show the untraceability of two group signatures in [1, 5] by new and very simple attacks. Although those flaws, such as, forgeability, untraceability and linkability have been shown in [2, 7, 8, 9], we should point out that our attacks are more simple.

One fair e-cash system was proposed in [1]. In this paper, we show that the system is insecure. Besides, we point out that there are two drawbacks. One is that those integer intervals for $s_i (i=1, \cdots, 9)$ are unappropriate. The other is that the datum $s_3$ in signature data is redundant. Moreover, we give a minute description of the technique to shun the challenge in the scheme. We think the method is a little interesting.

Duc et al. proposed a forward-secure blind signature scheme in [1]. They claimed that the scheme is constructed from the provably secure Okamoto-Guilou-Quisquater blind signature scheme. But we recently found that their scheme is insecure. In the paper, we show the scheme is universally forgeable by a simple and direct attack.

Wang et al. recently proposed an improved edition based on Tseng-Jan group signature scheme${}^{[1]}$. In the paper, we show that the scheme is untraceable by a simple attack.

Park and Lee have proposed a digital nominative proxy signature scheme for mobile communication in [1]. They claimed that neither Origin signer nor Proxy agent can generate a valid signature solely. In this paper we show that Origin signer can generate a valid signature without the cooperation of the agent. In fact, the flaw comes from that Verifier dose not use the public key of Proxy agent in verifying phase. It's a serious designing error.

Deng and Zhao recently proposed a group signature scheme. We find that the scheme cannot satisfy all of the requirements of a secure group signature.

Wang et al. recently proposed a new perfect and strong key-insulated signature scheme in [1]. We find that the scheme is universally forgeable. In the paper we present a simple and direct attack on it.

In the paper, we analyze two signature schemes. The first is a $(t_j, t, n) $ threshold group signature scheme proposed by Shi and Feng in [1]. The second is a fair blind signature scheme proposed by Feng in [2]. Our results show that both schemes are forgeable. Besides, we introduce a concept, i.e., suspended factor, to describe the common error in designing signature scheme, which means that some signature data lie at neither base position nor exponent position in verifying equation, instead lie at factor position solely .

Qiu et al. proposed a variant group signature scheme in [1]. We find that the group manager can successfully forge signature because he has absolute predominance in Join Phase.