Multisignature Scheme Based on the Generalized Conic Curve

Abstract

We propose a multisignature scheme based on the generalized conic curve. This scheme makes use of the difficulties in factorizing large integer and computing discrete logarithm on the Abelian group, is convenient to, plaintext. Furthermore, the numeric Simulation of the multisignature is designed.

1. Generalized Conic Curve

The generalized conic curve R_n (a,b,c) is the solution set of the congruence equation y² ≡ ax² − bx − cxy(mod n), where n = pq, and (a,n) = (b,n) = 1. Assume that A ∊ R_n (a,b,c), we call the smallest positive integer k, which establishes the equation kA = O, as the order of A. We denote the order of A as o(A). If (x² + cx − a) is irreducible both in F_p and F_q, then exists a point G in R_n (a,b,c), its order is N_n = 2rs. The point G satisfied these conditions is the base point.

2. Multisignature Scheme Based on R_n (a,b,c)

2.1. Setup

(1) Choose Rn(a,b,c), where modulus n = pq, and p + 1 = 2r, q + 1 = 2s, r and s are two large primes. (2) Let G = (x_G, y_G) be the base point of Rn(a,b,c), the order is N_n = 2rs. (3) Each signer has private key d_i and public key Q_i, where Q_i = d_i G(mod n). (4) Publish n,Q_i, but keep corresponding d_i privately.

2.2. Sign

(1) Assume that having k signers. Each signer selects a random integer k_i ∊ Z∗ _Nn : (2) Computes C_i = k_iG = (x_i, y_i), and publishes C_i. (3) Calculates $\sum _{i=1}^k{C}_i=(x,y)$ , the addition here is the addition of group ⊕. (4) Calculates δ _i = k_i − d_iH(m)γ(modN_n), if δ _i = 0, then goes back to the step (2-1). Thus, (γ _i , δ _i ) is his signature on message, and sends (γ _i , δ _i ) to the collector.

2.3. Collect

(1) The collector receives all (C_i, δ _i ). (2) Computes $\sum _{i=1}^k{C}_i=(x,y)$ , denoted as C. (3) Computes $\delta =\sum _{i=1}^k{\delta }_i$ . (4) Sends (C, δ) to the verifier.

2.4. Verify

(1) The verifier computes $Q\equiv \sum _{i=1}^k{Q}_i(modn)$ . (2) Chooses u₁ = δ u₂ = γH(m), computes u₁G ⊕ u₂Q = (xʹ, yʹ), denoted as Cʹ. (3) Accepts the message if C equals to Cʹ.

3. Conclusion

This paper proposes a multisignature scheme based on the generalized conic curve. The standard binary notation system also can be used to simplify computing techniques, which can improve almost 1/4 of computational efficiency.