typically have running times of the form

ence, vol. 1592, ed. J. Stern. Springer-Verlag, Berlin,

123“139.

e(γ +o(1))(log x) (log log x) ,

t 1’t

for x ’ ∞,

for some constants γ > 0 and 0 < t < 1, where x is

the order of the ¬nite ¬eld in which discrete loga-

STRUCTURAL

rithms are being computed, or the modulus to be

CRYPTANALYSIS factored. The size of the input to these algorithms

is proportional to the length in bits of x, so the run-

Structural Cryptanalysis is a branch of Crypt- ning time, being subexponential in log x, is subex-

analysis which studies the security of cryptosys- ponential in the input size as well (see L-notation).

tems described by generic block diagrams. It For further discussion, see exponential time and

analyses the syntactic interaction between the polynomial time.

various blocks, but ignores their semantic def-

inition as particular functions. Typical exam- Burt Kaliski

ples include meet-in-the-middle attacks on mul-

tiple encryptions, the study of various chaining

structures used in modes of operation, and the

SUBGROUP

properties of Feistel structures or substitution“

permutation networks with a small number of

A subset of elements of a group that is itself a

rounds.

group, i.e., that follows the group axioms (clo-

Structural attacks are often weaker than actual

sure, associativity, identity, inverse). For example,

attacks on given cryptosystems, since they cannot

if G = (S, —) is a group, then for any g ∈ S, the set

exploit particular weaknesses (such as bad differ-

of elements

ential cryptanalysis properties or weak avalanche

effect) of concrete functions. The positive side of g, g2 , g3 , . . .

this is that they are applicable to large classes of

(together with the multiplication operation) is a

cryptosystems, including those in which some of

subgroup of G. The order of any subgroup of a

the internal functions are unknown or key depen-

group G divides the order of the group G itself;

dent. Structural attacks often lead to deeper the-

this is known as Lagrange™s theorem.

oretical understanding of fundamental construc-

tions, and thus they are very useful in establishing

Burt Kaliski

general design rules for strong cryptosystems.

Alex Biryukov

SUBGROUP

CRYPTOSYSTEMS

SUBEXPONENTIAL TIME

In cryptographic applications it is often advan-

A subexponential-time algorithm is one whose run- tageous to replace a generator of the multiplica-

tive group F— t of a ¬nite ¬eld F pt of character-

ning time as a function of the size k of its input p

istic p by a generator g of a subgroup of F— t , as

grows more slowly than b x for every base b > 1. p

That is, for every constant base b > 1, the running originally suggested by Schnorr [2]. The subgroup

Substitutions and permutations 599

g generated by g must be chosen in such a way representation applies in principle to any element

that solving the discrete logarithm problem in g of F pt . When applied to the order- t ( p) subgroup

G of F— t with t as above, however, the trace repre-

is not easier than computing discrete logarithms p

in F— t . sentation has other important advantages: given

p

Tr (w) ∈ F pt/ f for any w ∈ G, it determines w and

Because of the Pohlig“Hellman algorithm (see

discrete logarithm problem), the order of g must its conjugates uniquely and the trace of any power

be chosen in such a way that it contains a suf¬- of w can be computed very ef¬ciently. Since g was

chosen in such a way that g ‚ G, this fast ˜ex-

ciently large prime factor. Usually, g is chosen in

such a way that its order q is prime. Because q ponentiation™ applies to the subgroup g as well.

divides the order p t ’ 1 of F— t and because p t ’ LUC with t = 2 and XTR with t = 6 allow very

p

1 = s dividing t s ( p), where s (X) is the tth cyclo- ef¬cient methods to ¬nd proper p and q of cryp-

tomic polynomial (as de¬ned in the generalization tographically relevant sizes. For large choices of

of Pollard™s p ’ 1 method”see integer factoring), t parameter selection becomes more cumbersome.

the prime order q of g divides s ( p) for one of For details of the exponentiation and parameter

the s dividing t. However, if q divides s ( p) for selection methods, see [3] for LUC and [1] and [4]

some s < t, then g can effectively be embedded for XTR.

in the proper sub¬eld F ps of F pt . This has the un- The fact that the distinction between subgroup

elements and their pt/ f-th powers (i.e., their con-

desirable consequence that the discrete logarithm

problem in g can be solved in the multiplicative jugates over F pt/ f ) is lost, has been shown (see [1])

group F— s of the substantially smaller ¬eld F ps , to have no negative impact on the security of LUC

p

which is easier than solving it in F— t . Thus, in or- and XTR. A potential disadvantage of the trace-

p

der not to affect the hardness of the discrete loga- based systems is that they complicate ordinary

rithm problem in g , the order q of g must be cho- multiplication of subgroup elements (represented

sen as a suf¬ciently large prime divisor of t ( p). by their traces).

Given q, a proper g can be found as g = h( p ’1)/q

t

Arjen K. Lenstra

for any h ∈ F— t such that g = 1.

p

If t = 1, this implies that p must be chosen so

that 1 ( p) = p ’ 1 has a large enough prime factor References

q. If t = 2, however, q must be a large prime factor

of 2 ( p) = p + 1 and if t = 6 of 6 ( p) = p2 ’ p + 1. [1] Lenstra, A.K. and E. Verheul (2000). “The XTR pub-

The case t = 1 corresponds to the traditional and lic key system.” Advances in Cryptology”CRYPTO

2000, Lecture Notes in Computer Science, vol. 1880,

conceptually easiest choice of using the prime

ed. M. Bellare. Springer-Verlag, Berlin, 1“19.

¬eld F pt = F p: for 1024-bit security, representa-

[2] Schnorr, C.P. (1991). “Ef¬cient signature genera-

tion of elements of the subgroup g requires about

tion by smart cards.” Journal of Cryptology, 4, 161“

1024 bits. The latter two cases, t = 2 and t = 6

174.

(or, more generally, t divisible by 2 or 6, respec- [3] Smith, P. and C. Skinner (1995). “A public-

tively) are of interest because they allow a more key cryptosystem and a digital signature system

ef¬cient representation of the subgroup elements based on the Lucas function analogues to discrete

when LUC or XTR are used (where LUC [3] refers logarithms.” Proceedings ASIACRYPT™94, Lecture

to ˜Lucas™ because of LUC™s use of Lucas sequences, Notes in Computer Science, vol. 917, eds. J. Pieprzyk

and R. Safari-Naini. Springer-Verlag, Berlin, 357“

and XTR [1] is an abbreviation of ECSTR which

364.

stands for ef¬cient compact subgroup trace repre-

[4] Stam, M. and A.K. Lenstra (2001). “Speeding

sentation). For 1024-bit security 1024/2 = 512 bits

up XTR.” Proceedings ASIACRYPT 2001, Lecture

suf¬ce for even t when using LUC and 1024/3 ≈

Notes in Computer Science, vol. 2248, ed. C. Boyd.

342 bits suf¬ce for t divisible by 6 when using XTR.

Springer-Verlag, Berlin, 125“143.

Let f be the factor indicating the improvement in

representation size: f = 2 for LUC and f = 3 for

XTR.

For any ¬nite ¬eld Fu , extension ¬eld Fuv , and

SUBSTITUTIONS AND

w ∈ Fuv the trace Tr (w) of w over Fu is de¬ned

PERMUTATIONS

as the sum of the v conjugates of w over Fu :

i

Tr (w) = 0¤i<v w u ∈ Fu (the inclusion in Fu be-

cause Tr (w)u = Tr (w)). LUC and XTR work by A substitution cipher is usually described by a

representing elements of g by their trace over sequence or list of single substitutions, each of

the sub¬eld F pt/ f . The resulting representation ad- which is commonly denoted by an arrow, like

p ’’ π.

vantage of a factor f compared to the traditional

600 Substitutions and permutations