Cryptography Reference
In-Depth Information
11.4 Sampling from algebraic groups
A natural problem, given an algebraic group G over a finite field
F q , is to generate a
“random” element of G . By “random” we usually mean uniformly at random from G (
F q ),
although sometimes it may be appropriate to weaken this condition. The first problem is to
generate a random integer in [0 ,p
1]. Examples 11.4.1 and 11.4.2 give two
simple approaches. Chapter 7 of Sidorenko [ 503 ] is a convenient survey.
1] or [1 ,p
Example 11.4.1 One way to generate a random integer in [0 ,p
1] is to generate random
binary strings x of length k (where 2 k 1 <p
2 k ) and only output those satisfying 0
x
p
1.
Example 11.4.2 Another method is to generate a binary string that is longer than p and
then return this value reduced modulo p . We refer to Section 7.4 of Shoup [ 497 ]fora
detailed analysis of this method (briefly, if 2 k 1 <p
l bit
string then the statistical difference of the output from uniform is 1 / 2 l ). Section 7.5 of [ 497 ]
discusses how to generate a random k -bit prime and Section 7.7 of [ 497 ] discusses how to
generate a random integer of known factorisation.
2 k and one generates a k
+
Exercise 11.4.3 Show that the expected number of trials of the algorithm in Example 11.4.1
is less than 2.
F p n uniformly at random,
Exercise 11.4.4 Give an algorithm to generate an element of
assuming that generating random integers modulo p is easy.
Appendix B.2.4 of Katz and Lindell [ 300 ] gives a thorough discussion of sampling
randomly in (
F p .
Algorithm 5 shows how to compute a generator for
) and
Z
/N
Z
F p , when the factorisation of p
1
F p n , when the factorisation of p n
is known. Generalising this algorithm to
1 is known,
⊆ F q of prime order r .
To sample uniformly from G , one can generate a uniform element in
is straightforward. In practice, one often works in a subgroup G
F q and then raise to
the power ( q
1) /r . This exponentiation can be accelerated using any of the techniques
discussed earlier in this chapter.
Exercise 11.4.5 Let q be a prime power such that the factorisation of q
1 is known. Give
an algorithm to determine the order of an element g
∈ F q .
F q such that the factori-
sation of the order of G is known. Give an algorithm to compute a generator of G .
Exercise 11.4.6 Let q be a prime power. Let G be a subgroup of
An alternative approach to the sampling problem for a finite Abelian group G is given
in Exercise 11.4.7 (these ideas will also be used in Exercise 15.5.2 ). However, this method
is often not secure for applications in discrete logarithm cryptography. The reason is that
one usually wants to sample group elements at random such that no information about their
discrete logarithm is known, whereas the construction in Exercise 11.4.7 (especially when
used to define a hash function) may give an attacker a way to break the cryptosystem.
Search WWH ::




Custom Search