Information Technology Reference
In-Depth Information
2 A Multisignature Scheme Based on SDLP and IFP
We propose a new multisignature scheme whereby each member of a given group,
G
, signs a document making use of his private key. The verifier of the signature
checks whether the signature corresponds to the multisignature of the group, by
using the public key that all the members of the group share [19].
We suppose that
G
=
is the
Trusted Third Party which computes its own private key, the unique public key
associated to all private keys, as well as helps the members of
G
to generate
their private key.
{
U
1
,U
2
,...,U
t
}
is the group of signer and
T
2.1 Key Generation
First of all,
T
generates its own private key:
1.
T
chooses two large primes
p
and
q
such that
p
=
u
1
·
r
·
p
1
+1
,
q
=
u
2
·
r
·
q
1
+1
,
with
r, p
1
,q
1
primes,
u
1
,u
2
∈
Z
,withgcd(
u
1
,u
2
)=2,
i.e.
,
u
1
=2
v
1
,
v
2
=2
v
2
, and gcd(
v
1
,v
2
) = 1. To guarantee the security of the scheme,
the bitlength of
r
is chosen so that the Discrete Logarithm Problem in a
Subgroup of
Z
n
,oforder
r
, be computationally infeasible. Although the fac-
tors of
n
are of a particular form, they can be eciently generated and to our
knowledge there is no known ecient algorithm to factorize
n
([20], [21]).
2.
T
computes
n
=
p
·
q,
r
2
φ
(
n
)=(
p
−
1)(
q
−
1) =
u
1
·
u
2
·
·
p
1
·
q
1
,
φ
(
n
)
λ
(
n
)=lcm(
p
−
1
,q
−
1) =
1)
=2
v
1
·
v
2
·
r
·
p
1
·
q
1
,
gcd(
p
−
1
,q
−
where
φ
(
n
) is the Euler function and
λ
(
n
) is the Carmichael function.
3. Next,
∈
Z
n
T
selects an element
α
of order
r
modulo
n
,verifying
r
2
gcd(
α, φ
(
n
)) = gcd(
α, u
1
·
u
2
·
·
p
1
·
q
1
)=1
.
The element
α
can be eciently computed due to the fact that
knows
the factorization of
n
,
φ
(
n
), and
λ
(
n
) [21, Lemma 3.1]. We denote by
S
r
the
multiplicative subgroup of
T
Z
n
generated by
α
.
T
generates a secret random number
s
∈
Z
r
4.
and computes
α
s
β
≡
(mod
n
)
.
(1)
5. The values (
α, r, β, n
) are made public; whereas
T
keeps secret (
p, q, s
).
Remark that breaking the key generation protocol amounts to solving the Inte-
ger factorization Problem (IFP). Moreover, to determine
s
from
β
in the expres-
sion (1) the Subgroup Discrete Logarithm Problem (SDLP) must be solved.
Search WWH ::
Custom Search