Underlying group order, and member representation size.
From: Peter Fairbrother (zenadsl6186_at_zen.co.uk)
Date: Tue, 17 Feb 2004 22:11:45 +0000
(no, it's got nothing to do with !)
It is often necessary (for eg ia semantic security reasons) to use an
underlying subgroup of prime order of the representational group in PK
situations. For instance, in DH or El Gamal in a representational Z_p of
size 1024 bits it is usual to use a subgroup of prime order q of size 160
Operations are carried out within the 160-bit group, and if for example we
could number the members, and convert the numbers to the member (and
vice-versa) we could get away with only using 160 bits to store and transfer
keys etc. There would be no need to transmit 1024 bits to denote the member.
Put another way, there are only 2^160 possible values of interest, but it
takes 1024 bits to specify a value. There are "impossible values", by which
I mean values that are representable but which are not members of the
underlying operative group.
You could convert the 1024-bit representation of a member of a 160-bit group
to a 160-bit number, and transmit those 160 bits instead of 1024 bits - but
it's hard to convert back.
You can also do it the other way round, ie 160->1024 is easy but 1024->160
is hard. I don't know how to do it so that translation is easy both ways.
DH/El Gamal can be implemented in many groups other than a subgroup of prime
order of Z_p, but are there any such where the order of the underlying group
is equal to the size of the space used to specify a member? With no
"impossible values"? A group that has p members, and each can be defined as
a number <= p?
If so, is it a group in which eg DLP is hard, and that does not have
problems like eg anomalous groups in ECC? Tom mentioned something about such
in another thread recently.
-- Peter Fairbrother
The new moon is shining the angels are washing their windows
Above the years whose jumble sale goes spinning on below