<<

. 4
( 5)



>>

transferability is simply this: the legitimate use to revoke their anonymous credentials on demand.
of personal credentials (in contrast to consumable The price of this feature is an even higher compu-
credentials) can neither be detected nor prevented tational complexity of the showing of credentials.
by referring only to the digital activity of individ- It appears that detecting a cheating individ-
uals. There must be some mechanism that can ual who has lent his personal credentials to an-
distinguish whether the individual who shows a other individual, or who has borrowed a personal
personal credential is the same as the individ- credential from another individual is technically
ual to whom that credential has been issued be- possible, but is often unacceptable in practice.
fore. Since personal devices as well as personal Unauthorized access may lead to disastrous or
access information such as PINs and passwords hard-to-quantify damage, which cannot be com-
can easily be transferred from one individual to pensated after the access has been made regard-
another, there is no other way to make this dis- less how individuals are persecuted and what
tinction but by referring to hardly transferable measures of retaliation are applied.
characteristics of the individuals themselves, for The wisdom of more than 20 years of research
example, through some kind of (additional) bio- on credentials is that in of¬‚ine consumable creden-
metric identi¬cation (see biometrics) of individu- tials overspender detection can be achieved by dig-
als. Then, illegitimate showing can be recognized ital means alone while overspending prevention
during the attempt and thus can be prevented can only be achieved by relying on tamper resis-
effectively, however, at the price of assuming tant hardware. In online consumable credentials,
tamper resistant biometric veri¬cation hardware. both overspender detection and overspending pre-
Bleumer proposed to enhance the wallet-with- vention can be achieved without relying on tamper
observer architecture of Chaum and Pedersen [15] resistant hardware.
by a biometric recognition facility embedded into In personal credentials, one is interested in
the tamper resistant observer in order to achieve transfer prevention, which we have called non-
transfer prevention [1]. transferability. Considering a separate integrity
Camenisch and Lysyanskaya [5] have proposed requirement of transferer detection makes lit-
a personal credential scheme which enforces non- tle sense in most applications because the po-
transferability by deterring individuals who are tential damage caused by illegitimately trans-
willing to transfer, pool, or share their creden- ferring credentials is hard to compensate for.
112 Credentials


Nontransferability can be achieved in a strict Quisquater and J. Vandewalle. Springer-Verlag,
Berlin, 288“293.
sense only by relying on tamper resistant biomet-
[10] Chaum, David (1990). “Showing credentials with-
ric veri¬cation technology, regardless if it is an
out identi¬cation: Transferring signatures be-
online or of¬‚ine scheme. Nontransferability can
tween unconditionally unlinkable pseudonyms.”
be approximated by deterrence mechanisms inte-
Advances in Cryptology”AUSCRYPT™90, Sydney,
grated into the personal credential schemes, but it
Australia, January 1990, Lecture Notes in Com-
remains to be analyzed for each particular appli- puter Science, vol. 453. Springer-Verlag, Berlin,
cation how effective those deterrence mechanisms 246“264.
can be. [11] Chaum, David (1992). “Achieving electronic pri-
vacy.” Scienti¬c American 267 (2), 96“101.
Gerrit Bleumer [12] Chaum, David, Bert den Boer, Eugene van Heyst,
Stig Mjlsnes, and Adri Steenbeek (1990). “Ef¬cient
References of¬‚ine electronic checks.” Advances in Cryptology”
EUROCRYPT™89, Lecture Notes in Computer
Science, vol. 434, eds. J.-J. Quisquater and J.
[1] Bleumer, Gerrit (1998). “Biometric yet privacy pro-
Vandewalle. Springer-Verlag, Berlin, 294“301.
tecting person authentication.” Information Hid-
[13] Chaum, David and Jan-Hendrik Evertse (1987). “A
ing, Lecture Notes in Computer Science, vol.
secure and privacy-protecting protocol for trans-
1525, ed. D. Aucsmith. Springer-Verlag, Berlin, 99“
mitting personal information between organiza-
110.
tions.” Advances in Cryptology”CRYPTO™86, Lec-
[2] Brands, Stefan (1994). “Untraceable off-line
ture Notes in Computer Science, vol. 263, ed. A.
cash in wallet with observers.” Advances in
Odlyzko. Springer-Verlag, Berlin, 118“167.
Cryptology”CRYPTO™93, Lecture Notes in Com-
[14] Chaum, David, Amos Fiat, and Moni Naor
puter Science, vol. 773, ed. D.R. Stinson. Springer-
(1990). “Untraceable electronic cash.” Advances in
Verlag, Berlin, 302“318.
Cryptology”CRYPTO™88, Lecture Notes in Com-
[3] Brands, Stefan and David Chaum (1994).
puter Science, vol. 403, ed. S. Goldwasser. Springer-
“Distance-bounding protocols.” Advances in
Verlag, Berlin, 319“327.
Cryptology”EUROCRYPT™93, Lecture Notes in
[15] Chaum, David and Torben Pedersen (1993).
Computer Science, vol. 765, ed. T. Helleseth.
“Wallet databases with observers.” Advances in
Springer-Verlag, Berlin, 344“359.
Cryptology”CRYPTO™92, Lecture Notes in Com-
[4] Brickell, Ernie, Peter Gemmell, and David Kravitz
puter Science, vol. 740, ed. E.F. Brickell. Springer-
(1995). “Trustee-based tracing extensions to
Verlag, Berlin, 89“105.
anonymous cash and the making of anonymous
[16] Chen, Lidong (1996). “Access with pseudonyms.”
change.” 6th ACM-SIAM Symposium on Discrete
Cryptography: Policy and Algorithms, Lecture
Algorithms (SODA) 1995. ACM Press, New York,
Notes in Computer Science, vol. 1029, eds. E.
457“466.
Dawson and J. Golic. Springer-Verlag, Berlin, 232“
[5] Camenisch, Jan and Anna Lysyanskaya (2001).
243.
“Ef¬cient non-transferable anonymous multishow
[17] Cramer, Ronald and Torben Pedersen (1994).
credential system with optional anonymity revo-
“Improved privacy in wallets with observers
cation.” Advances in Cryptology”EUROCRYPT
(extended abstract).” Advances in Cryptology”
2001, Lecture Notes in Computer Science, vol.
EUROCRYPT™93, Lecture Notes in Computer Sci-
2045, ed. B. P¬tzmann. Springer-Verlag, Berlin,
ence, vol. 765, ed. T. Helleseth. Springer-Verlag,
93“118.
Berlin, 329“343.
[6] Camenisch, Jan and Anna Lysyanskaya (2002).
˚
[18] Damard, Ivan B. (1990). “Payment systems
“Dynamic accumulators and application to ef¬-
and credential mechanisms with provable secu-
cient revocation of anonymous credentials.” Ad-
rity against abuse by individuals.” Advances in
vances in Cryptology”CRYPTO 2002, Lecture
Cryptology”CRYPTO™88, Lecture Notes in Com-
Notes in Computer Science, vol. 2442, ed. M. Yung.
puter Science, vol. 403, ed. S. Goldwasser. Springer-
Springer-Verlag, Berlin, 61“76.
Verlag, Berlin, 328“335.
[7] Camenisch, Jan, Ueli Maurer and Markus Stadler
[19] Even, Shimon, Oded Goldreich, and Yacov
(1996). “Digital payment systems with passive
Yacobi (1984). “Electronic wallet.” Advances in
anonymity-revoking trustees.” ESORICS™96, Lec-
Cryptology”CRYPTO™83, Lecture Notes in Com-
ture Notes in Computer Science, vol. 1146, ed. V.
puter Science, ed. D. Chaum. Plenum Press, New
Lotz. Springer-Verlag, Berlin, 33“43.
York, 383“386.
[8] Chaum, David (1985). “Security without identi¬ca-
[20] Frankel, Yair, Yannis Tsiounis, and Moti Yung
tion: Transaction systems to make Big Brother ob-
(1996). “Indirect discourse proofs: Achiev-
solete.” Communications of the ACM 28 (10), 1030“
ing ef¬cient fair off-line e-cash.” Advances in
1044.
Cryptography”ASIACRYPT™96, Lecture Notes in
[9] Chaum, David (1990). “Online cash checks.” Ad-
Computer Science, vol. 1163, eds. K. Kim and T.
vances in Cryptology”EUROCRYPT™89, Lecture
Matsumoto. Springer-Verlag, Berlin, 286“300.
Notes in Computer Science, vol. 434, eds. J.-J.
Cryptanalysis 113


CRYPTANALYSIS
[21] Franklin, Matthew and Moti Yung (1993). “Se-
cure and ef¬cient off-line digital money.” 20th In-
ternational Colloquium on Automata, Languages
Cryptanalysis is the discipline of deciphering a ci-
and Programming (ICALP), Lecture Notes in
phertext without having access to the keytext (see
Computer Science, vol. 700, eds. A. Lingas, R.G.
cryptosystem), usually by recovering more or less
Karlsson, and S. Carlsson. Springer-Verlag, Berlin,
directly the plaintext or even the keytext used, in
265“276.
cases favorable for the attacker by reconstructing
[22] Lysyanskaya, Anna, Ron Rivest, A. Sahai, and
the whole cryptosystem used. This being the worst
Stefan Wolf (1999). “Pseudonym systems.” Selected
case possible for the attacked side, an acceptable
Areas in Cryptography, Lecture Notes in Computer
Science, vol. 1758, eds. H.M. Heys and C.M. Adams. level of security should rest completely in the key
Springer-Verlag, Berlin, 302“318. (see Kerckhoffs™ and Shannon™s maximes). “A sys-
[23] Naccache, David and Sebastiaan von Solms (1992). tematic and exact reconstruction of the encryp-
“On blind signatures and perfect crimes.” Comput- tion method and the key used” (Hans Rohrbach,
ers & Security, 11 (6), 581“583.
1946) is mandatory if correctness of a cryptana-
[24] Stadler, Markus, Jean-Marc Piveteau, and Jan Ca-
lytic break is a to be proved, e.g., when a cryptan-
menisch (1995). “Fair blind signatures.” Advances
alyst is a witness to the prosecution.
in Cryptology”EUROCRYPT™95, Lecture Notes in
Computer Science, vol. 921, eds. L.C. Guillou and
J.-J. Quisquater. Springer-Verlag, Berlin, 209“219.
TERMINOLOGY: Cryptanalysis can be passive,
which is the classical case of intercepting the mes-
sage without giving any hint that this was done,
CROSS-CORRELATION or active, which consists of altering the message
or retransmitting it at a later time, or even of in-
Let {at } and {bt } be two sequences of period n (so serting own messages (some of these actions may
at = at+n and bt = bt+n for all values of t) over an be detected by the recipient).
alphabet being the integers mod q (see modular A compromise is the loss (or partial loss) of se-
arithmetic). The cross-correlation between the se- crecy of the key by its exposure due to crypto-
quences {at } and {bt } at shift „ is de¬ned as graphic faults. We shall describe various kinds of
key compromises.
n’1
ωat+„ ’bt ,
C(„ ) = A plaintext-ciphertext compromise is caused by
a transmission of a message in ciphertext followed
t=0

where ω is a complex qth root of unity. Note that (e.g., because the transmission was garbled) by
in the special case of binary sequences, q = 2 and transmission of the same message in plaintext. If
ω = ’1. information on the encryption method is known
or can be guessed, this results in exposure of the
In the special case when the two sequences are
key. This attack may be successful for a plaintext
the same, the cross-correlation is the same as
of several hundred characters.
the auto-correlation. Many applications in stream
A plaintext-plaintext compromise is a transmis-
ciphers and communication systems require large
sion of two isologs, i.e., two different plaintexts,
families of cyclically distinct sequences with a low
encrypted with the same keytext. If the encryp-
maximum nontrivial value of the auto- and cross-
tion method is such that the encryption steps form
correlation between any two sequences in the
a group (see key group and pure crypto-system),
family.
then a “difference” p1 ’ p2 of two plaintexts p1 , p2
Tor Helleseth and a “difference” c1 ’ c2 of two plaintexts c1 , c2
may be de¬ned and the role of the keytext is can-
References celled out: c1 ’ c2 = p1 ’ p2 . Thus, under suitable
guesses on the plaintext language involved, e.g.,
[1] Golomb, S.W. (1982). Shift Register Sequences. on probable words and phrases, a “zig-zag” method
Aegean Park Press, Laguna Hills, CA. (see below), decomposing c1 ’ c2 , gives the plain-
[2] Helleseth, T. and P.V. Kumar (1999). “Pseudonoise
texts and then also the keytext. This compromise
sequences.” The Mobile Communications Hand-
is not uncommon in the case of a shortage of key-
book, ed. J.D. Gibson. CRC Press, Boca Raton, FL,
ing material. It is even systemic if a periodic key
Chapter 8.
is used.
[3] Helleseth, T. and P.V. Kumar (1998). “Sequences
A ciphertext-ciphertext compromise is a trans-
with low correlation.” Handbook of Coding Theory,
mission of two isomorphs, i.e., the same plain-
eds. V.S. Pless and W.C. Huffman. Elsevier, Amster-
text, encrypted with two different keytexts.
dam, Chapter 21.
114 Cryptanalysis


Exchanging the role of plaintext and keytext, this an example: the frequency pro¬le of the English
case is reduced to and can be treated as a plaintext- language looks like
plaintext compromise. This compromise is even
systematic in message sets, where the same mes-
sage is sent in different encryption to many
places, such as it is common in public key crypto-
systems.
One speaks of a brute force attack or exhaus-
tive key search if all possible keytexts are tried
out to decrypt a ciphertext (knowing or guessing abcde f gh i j k lmnop q r s t uvwxyz
the cryptosystem used). At present, with the still
growing speed of supercomputers, every 10 years If a ciphertext of 349 characters has the follow-
the number of trial and error steps that is feasible ing distribution:
is increased by a factor of roughly 25 .
Further commonly used terminology will be
given now. In a ciphertext-only attack, only one
or more ciphertexts under the same keytext
are known. In a known-plaintext attack one
knows one or more matching pairs of plaintext“
ciphertext. Frequently, this attack is carried out
with rather short fragments of the plaintext 1 0 5 36 9 10 9 54 9 10 2123 1 8 8 10 41 3 4 0 19 22 24 18 0 4
A B C D E F G H I J K L MN O P Q R S T U V W X Y Z
(e.g., probable words and phrases). In a chosen-
plaintext attack one can choose plaintexts and
it is easy to guess a C¦sar encryption that counts
obtain the corresponding ciphertexts. Sometimes
.
down three letters in the standard alphabet: a =
this can be done with the proviso that the plain-
. . .
D, b = E, c = F, . . . , z = C. More dif¬cult is the
texts may be chosen in a way that depends on
situation if a mixed alphabet is to be expected.
the previous encryption outcomes. How to foist the
Then the ¬rst step is to group the letters in cliques:
plaintext on the adversary is not a cryptographer™s
the most frequent ones, the very rare ones, and
problem, but is a problem of misleading the adver-
some in between
sary and is to be executed by the secret services.
Finally, in a chosen-ciphertext attack there is the
{etaoin} {srh} {ld} {cumfpgwyb} {vk} {xjqz},
possibility to choose different ciphertexts to be de-
crypted, with the cryptanalyst having access to the
decrypted plaintext. An example may be the inves- and to re¬ne the decryption within these cliques
tigation of a tamperproof decryption box, with the by trial and error.
hope of ¬nding the key. Depth is a notion used in connection with the
cryptanalysis of polyalphabetic encryptions. It
means the arrangement of a number of ciphertexts
STATISTICAL APPROACHES TO CLASSICAL
supposedly encrypted with the same keytext”for
CRYPTOSYSTEMS: We shall now discuss some
periodic polyalphabetic encryption broken down
statistical methods that can be used by the
according to the assumed period.
cryptanalist.
Example: a depth of ¬ve lines:


T CCVL ES KPT X MP VW HY MVG XB O RV C WA RF
V L L BV C K WF P E H ECF CGNZE KK K VI HD DI D
MY Y RD MJ WMC UI GLO KMX LR EWH X M T J HAS
B KQTZ B Z WK W Z X GZ O V T B AT KWMGM RJ KLP
MY Y VH B WJ D X CP CZO HV T S I VME BS O H R A U.


Frequency matching is a cryptanalytic method The lines of a depth are isologs: they are en-
for breaking monoalphabetic (C¦sar type) encryp- crypted with the same key text and represent a
tions. One determines the frequency of the char- plaintext“plaintext compromise.
acters in a ciphertext and compares them with the By forming differences of the elements in se-
frequency of the characters in a language known lected columns, a reduction of depth to a monoal-
or assumed to be used for the plaintext. To give phabetic (C¦sar type) encryption is accomplished.
Cryptanalysis 115


This makes it possible to derive the keytext belong. For suf¬ciently long texts, it is statistically
roughly equal to 1/15 = 6.67% for the English lan-
TRUTH ISSOP RECIO USTHA TITNE EDSAB guage and 1/12.5 = 8% for the French language
and the German language. Most importantly, it
which decrypts the depth (by means of the
remains invariant if the two texts are polyalpha-
Vigen` re table) to
e
betically encrypted with the same keytext. If, how-
al i c e wa sb e g i nni ng t og et ve r yt i re ever, they are encrypted with different keytexts
c ur i o u s er a ndc ur i o use rcri e dal i c
or with the same key sequence, but with differ-
t he yw e r ei n dee da q ue er l ooki ngpar
ent starting positions, the character coincidence
i t was t hewh i tera bbi tt r ot t i ngs l o
is rather random and the value of Kappa is sta-
t he c a t erp i l l ar a nda l i c el o o k e d a t.
tistically close to 1/N, where N is the size of the
vocabulary. The Kappa test applied to a ciphertext
Forming a depth is possible as soon as the value
C and cyclically shifted versions C (u) of the cipher-
of the period of the periodic polyalphabetic encryp-
text, where u denotes the number of shifts, yields
tion has been found, for instance by the Kasiski
the value κ(C, C (u) ). If the keytext is periodic with
method below. Forming a depth is not possible,
period d, then for u = d and for all multiples of d,
if the key is non-periodic. But even for periodic
a value signi¬cantly higher than 1/N will occur,
polyalphabetic encryptions, forming a depth of suf-
while in all other cases a value close to 1/N will be
¬ciently many elements (usually more than six) is
found. This is the use of the Kappa examination
not possible if the keytext is short enough.
for ¬nding the period; it turned out to be a more
When the alphabets used in a polyalphabetic
accurate instrument than the Kasiski method.
periodic substitution are a mixed alphabet and a
The Kappa test may also be used for adjust-
shifted version of it, symmetry of position is the
ing two ciphertexts C, C which are presumably
property that for any pair of letters their distance
encrypted with the same keytext, but with dif-
is the same in all rows of the encryption table.
ferent starting positions (called superimposition).
For a known period, it may allow, after forming a
By calculating κ(C (u) , C ), a shift d, determined
depth, the complete reconstruction of the substi-
as a value of u, for which κ(C (u) , C ) is high,
tution (Auguste Kerckhoffs, 1883).
brings the two ciphertexts C (d) and C “in phase”,
Kasiski™s method. If in a periodic polyalphabetic
i.e., produces two isologs. In this way, a depth of
encryption the same plaintext sequence of char-
n texts can be formed by superimposition from
acters happens to be encrypted with the same
a ciphertext“ciphertext compromise of n cipher-
sequence of key characters, the same ciphertext
texts.
sequence of characters will occur. Thus, in order
The De Viaris attack is a cryptanalytic method
to determine the period of a periodic polyalpha-
invented by Ga¨ tan Henri L´ on de Viaris in 1893
e e
betic encryption, the distance between two “par-
to defeat a polyalphabetic cryptosystem proposed
allels” in the ciphertext (pairs, triples, quadru-
´
by Etienne Bazeries, in which the alphabets did
ples etc. of characters) is to be determined; the
not form a Latin square. (A Latin square for a vo-
distance of genuine parallels will be a multiple
cabulary of N characters is an N — N matrix over
of the period. The greatest common divisor of
this alphabet such that each character occurs just
these distances is certainly a period”it may, how-
once in every line and in every column.)
ever, not be the smallest period. Moreover, the pe-
Pattern ¬nding is a cryptanalytic method that
riod analysis may be disturbed by faked parallels.
can be applied to monoalphabetic encryptions. It
Kasiski developed this fundamental test for key
makes use of patterns of repeated symbols. For ex-
periodicity in 1863 and shattered the widespread
ample, the pattern 1211234322 with “signature”
belief that periodic polyalphabetic encryption is
4 + 3 + 2 + 1 (four twos, three ones, two threes and
unbreakable.
one four) most likely allows in English nothing
The Kappa test is based on the relative fre-
quency κ(T, T ) of pairs of text segments T = but peppertree, the pattern 1213143152 with the
signature 4 + 2 + 2 + 1 + 1 nothing but initiation
(t1 , t2 , t3 , . . . , t M ), T = (t1 , t2 , t3 , . . . , t M ) of equal
length, M ≥ 1, with the same characters at the (Andree 1982, based on Merriam-Webster™s Dictio-
nary).
same positions (that is why this method is also
Noncoincidence exhaustion. Some cryptosys-
called the index of coincidence, often abbreviated
tems show peculiarities: genuine self-reciprocal
to I.C., William F. Friedman, 1925). The value
permutations never encrypt a letter by itself. Porta
of Kappa is rather typical for natural languages,
N
since the expected value of κ(T, T ) is 2
encryptions even always encrypt a letter from the
i=1 pi ,
¬rst half of the alphabet by a letter from the
where pi is the probability of occurrence of the
second half of the alphabet and vice versa. Such
ith character of the vocabulary to which T and T
116 Crypto machines


Reference
properties may serve to exclude many positions
of a probable word (a probable word is a word or
phrase that can be expected to be present in a mes- [1] Bauer, F.L. (1997). “Decrypted secrets.” Methods
sage according to the context; it may form the basis and Maxims of Cryptology. Springer-Verlag, Berlin.
for a known-plaintext attack).
Zig-zag exhaustion. For encryptions with a key
group (see key), the difference of two plaintexts
CRYPTO MACHINES
is invariant under encryption: it equals the dif-
ference of the corresponding ciphertexts. Thus in
These are machines for automatic encryption us-
case of a plaintext“plaintext compromise (with a
ing a composition of mixed alphabet substitutions
depth of 2), the difference of the ciphertexts can be
often performed by means of rotors. Examples
decomposed into two plaintexts by starting with
are: Enigma (Germany), Hebern Electric Code
probable words or phrases in one of the plaintexts
Machine (USA), Typex (Great Britain), SIGABA = ˆ
and determining the corresponding plaintext frag-
M-134-C (USA), and NEMA (Switzerland).
ment in the other plaintext, and vice versa. This
Rotor: wheel, sitting on an axle and having on
may lead in a zig-zag way (“cross-ruff ”) to complete
both sides a ring of contacts that are internally
decryption.
wired in such a way that they implement a per-
Theoretically, the decomposition is unique pro-
mutation.
vided the sum of the relative redundancies of the
The Enigma machine (Figures 1 and 2) was in-
two texts is at least 100%. For the English lan-
vented by the German Arthur Scherbius. In 1918,
guage, the redundancy (see information theory) is
he ¬led a patent application for an automatic,
about 3.5 [bit/char] or 74.5% of the value 4.7 ≈
keyboard-operated electric encryption machine
log2 26 [bit/char].
performing a composition of a ¬xed number of
Multiple anagramming is one of the very few
polyalphabetic substitution (see substitutions and
general methods for dealing with transposition ci-
permutations) steps (four in the early commercial
phers, requiring nothing more than two plaintexts
models) with shifted mixed alphabets performed
of the same length that have been encrypted with
by wired keying wheels (called rotors).
the same encryption step (so the encrypting trans-
The key sequence was generated by the cyclo-
position steps have been repeated at least once).
metric, “counter-like” movement of the wheels.
Such a plaintext“plaintext compromise suggests a
The ¬xed substitutions of the rotors were to be
parallel to Kerkhoffs™ method of superimposition.
kept secret, the starting point of the key sequence
The method is based on the simple fact that equal
was to be changed at short intervals. Later “im-
encryption steps perform the same permutation of
provements” were a re¬‚ector (Willi Korn, 1925)
the plaintext letters. The ciphertexts are therefore
which made the encryption self-reciprocal (and
written one below the other and the columns thus
opened a way of attack) and (by request from
formed are kept together.
the German Armed Forces Staff) a plugboard per-
Friedrich L. Bauer forming a substitution that could be changed at




e E




m
M




+4V

Fig. 1. Electric current through a three-rotor Enigma
Crypto machines 117


a more independent line of rotor machines, lead-
ing in 1933 to the M-134-T2, then to the M-134-A
(SIGMYC), and in 1936 to the M-134-C (SIGABA)
of the Army, named CSP889 (ECM Mark II) by the
Navy. The Germans obviously did not succeed in
breaking SIGABA, which had ¬ve turning cipher
rotors with irregular movement. It had been made
watertight by Frank Rowlett (1908“1998), an aide
of Friedman since 1930.
An interesting postwar variant of the ENIGMA
with seven rotors and a ¬xed re¬‚ector was built
and marketed by the Italian company Ottico Mec-
canica Italiana (OMI) in Rome.
The Swiss army and diplomacy used from 1947
on an ENIGMA variant called NEMA (˜Neue Mas-
chine™) Modell 45. It was developed by Hugo
Hadwiger (1908“1981), Heinrich Weber (1908“
1997), and Paul Glur, and built by Zellweger A.G.,
Uster. It had ten rotors, six of which were active
ones, while the others served for rotor movement
only. The use of a re¬‚ector was unchanged.
Based on US-American experiences and simi-
lar to TYPEX was the rotor machine KL-7 of the
Fig. 2. Cipher machine Enigma (four-rotor version)
NATO, in use until the 1960s.
The Swedish inventor Boris Hagelin created the
short intervals (which in fact helped to avoid cer-
Hagelin machine (Figure 3) in 1934. It was an
tain manifest attacks). The German Wehrmacht
Enigma had three rotors (to be selected out of up
to eight) and a re¬‚ector (to be selected out of two).
In the Navy variant of 1942 the re¬‚ector was not
¬xed. Certain weaknesses of the Enigma encryp-
tion were not caused by the machine itself, but by
cryptographic blunders in operating it.
An exceptional role was played by the German
Abwehr, the Intelligence Service of the German
Armed Forces, as far as ENIGMA goes: It used a
variant of the old ENIGMA D with a pinion/tooth
wheel movement of the rotors, with 11, 15, and 17
notches on the wheels (˜11-15-17 ENIGMA™), and
naturally without plugboard”following rather
closely Willi Korn™s German Patent No. 534 947,
¬led November 9, 1928, US Patent No. 1,938,028
of 1933.
A few specimens of a three-rotor-ENIGMA
(˜ENIGMA T™), likewise without plugboard, but
with ¬ve-notched rotors, were destined for the
Japanese Navy, but did not get out of the harbor
and were captured by the Allies near Lorient, in
Brittany.
In England, too, rotor machines were built dur-
ing the Second World War: TYPEX was quite
an improved ENIGMA (instead of the plugboard
there was an entrance substitution performed by
two ¬xed rotors which was not self-reciprocal).
In the USA, under the early in¬‚uence of William
Friedman (1891“1969) and on the basis of the
Hebern development, there was in the early 1930s Fig. 3. The M-209 Hagelin machine
118 Cryptology


automatic mechanical encryption machine, with
alphabet-wheel input and a printing device, per-
forming by a “lug cage” adder a Beaufort substi-
tution (see Beaufort encryption) controlled by ¬ve
keying wheels with 17, 19, 21, 23, and 25 teeth
according to a pre-chosen “step ¬gure.” The lug
matrix and the step ¬gure can be changed by acti-
vating suitable pins. This model, called C-35, was
followed by a C-36, with six keying wheels and 17,
19, 21, 23, 25, and 26 teeth. Under the cover name
M-209, C-36 was built by Smith-Corona for the US
Army, Navy and Air Forces, altogether accounting
for 140 000 machines. The Hagelin machines were
less secure than the Enigma.

Friedrich L. Bauer Fig. 1. Semagram. The message is in Morse code, formed
by the short and long stalks of grass to the left of
the bridge, along the river bank and on the garden
Reference
wall. It reads: “compliments of CPSA MA to our chief
Col. Harold R. Shaw on his visit to San Antonio May
[1] Bauer, F.L. (1997). “Decrypted secrets.” Meth-
11, 1945.” (Shaw had been head of the Technical Oper-
ods and Maxims of Cryptology. Springer-Verlag,
ations Division of the US government™s censorship divi-
Berlin.
sion since 1943)



ment ciphers (veiled secret writings, like the
CRYPTOLOGY null cipher and grilles (see substitutions and
permutations)). Linguistic steganography has
Cryptology is the discipline of cryptography and close connections with cryptography, e.g., the
cryptanalysis and of their interaction. Its aim is uses of grilles and transposition ciphers (see
secrecy or con¬dentiality: the practice of keep- substitutions and permutations) are related.
ing secrets, maintaining privacy, or concealing Semagram: a picture or grapheme hiding a mes-
valuables. A further goal of cryptology is in- sage behind innocent looking, frequently minute
tegrity and authenticity, usually given by a mes- graphic details (Figure 1).
sage authentication code (see MAC algorithms) or Open code: a class of linguistic steganography, se-
digital signature unique to the sender and serving lected words or phrases made to appear innocent
for his identi¬cation. in the surrounding text.
Cryptography: the discipline of writing a message Cue: a short, prearranged jargon-code message,
in ciphertext (see cryptosystem), usually by a usually a word or phrase. The importance of the
translation from plaintext according to some message is strongly linked to the time of trans-
(frequently changing) keytext, with the aim of mission. Famous is the encrypted Japanese mes-
protecting a secret from adversaries, intercep- sage HIGASHI NO KAZE AME (“east wind, rain”) on
tors, intruders, interlopers, eavesdroppers, op- December 7, 1941, a cue with the meaning “war
ponents or simply attackers, opponents, ene- with the USA.”
mies. Professional cryptography protects not Null cipher, where only certain letters are sig-
only the plaintext, but also the key and more ni¬cant (the others being nulls):
r
generally tries to protect the whole crypto- encryption rules of the type “the nth charac-
system. ter after a particular character,” speci¬cally “the
Steganography: counterpart of cryptography, com- next character after a space” (acrostics),
r
prising technical steganography (working with or rules for inserting a null between syllables
invisible inks and hollow heels, etc.) and linguis- (Tut Latin: TUT) or after phonetic consonants
(Javanais: chaussure ’ CHAVAUSSAVURAVE)
tic steganography, the art of hiding information
r or rules for suf¬xing nulls, e.g., un fou ’
by linguistic means. Of the later, we mention
semagrams, open code, comprising jargon code UNDREQUE FOUDREQUE (Metz 1670), also com-
(masked secret writing, e.g., cues), and conceal- bined with shuf¬‚ing of some letters (largonjem:
Cryptrec 119


boucher ’ LOUCHERBEM, pig Latin: third ’
™ Reference
™™
r
IRDTHAY);
a borderline case is pure transposition: revers- [1] Bauer, F.L. (1997). “Decrypted secrets.” Methods
ing letters of a word (back slang), e.g., tobacco and Maxims of Cryptology. Springer-Verlag, Berlin.
’ OCCABOT).

Friedrich L. Bauer
CRYPTREC
Reference
CRYPTREC was initially an abbreviation of
[1] Bauer, F.L. (1997). “Decrypted secrets.” Meth- Cryptography Research and Evaluation Commit-
ods and Maxims of Cryptology. Springer-Verlag, tee, which was set up in 2000 by METI (Ministry
Berlin. of Economy, Trade and Industry, Japan) for the
purpose of evaluating cryptographic techniques to
assure their security for e-Government applica-
tions. However, since the CRYPTREC Advisory
CRYPTOSYSTEM Committee was founded by MPHPT (Ministry
of Public Management, Home Affairs, Posts and
Telecommunications, Japan) and METI in 2001 to
A cryptosystem (or cipher system) is a system con-
perform a policymaking study on the application of
sisting of an encryption algorithm, a decryption
cryptographic techniques, it has been interpreted
algorithm, and a well-de¬ned triple of text spaces:
as the name of the organization of committees
plaintexts, ciphertexts, and keytexts. For a given
involved in the project for evaluation of crypto-
keytext the encryption algorithm will map a plain-
graphic techniques available for the Japanese e-
text to a (usually uniquely determined) ciphertext.
Government. The project itself is now referred
For the corresponding keytext, the decryption al-
to as CRYPTREC. From 2000 to 2002 the main
gorithm will map the ciphertext to the (usually
goal of CRYPTREC was to publish a list of recom-
uniquely determined) plaintext. The cryptosystem
mended ciphers for e-Government use. In March
may be performed by hand methods (“hand ci-
2003 the list was published and established as
pher”), by machine methods (“machine cipher”),
the guiding principle in the usage of cryptographic
or by software (see also Shannon™s model).
techniques in the Japanese government ministries
Plaintext: text in an open language that is com-
and agencies.
monly understood among a larger group of peo-
ple.
EVALUATION TARGETS: In the ¬scal years 2000
Ciphertext: text (“cryptogram”) in a secret lan-
and 2001, CRYPTREC Evaluation Commit-
guage that is understood only by few, autho-
tee called for the submission of the cryptographic
rized people, usually after decryption by hand or
techniques in order to compile a list of crypto-
machine.
graphic techniques that could be employed for e-
We mention two special properties: an endomor-
Government. In the public request for proposals,
phic cryptosystem is a cryptosystem with iden-
the CRYPTREC Evaluation Committee did not
tical plaintext and ciphertext space. Example:
impose any restrictions on the national origin or
{a, b, c, . . . , z} ’’ {a, b, c, . . . , z}. A pure cryptosys-
the organization of the applicant in order to pro-
tem is a cryptosystem that has the following prop-
vide an opportunity for impartial evaluation for
erty: whenever enciphering Ek with key k, followed
all applicants.
by deciphering D j with key j, followed by encipher-
The CRYPTREC Evaluation Committee
ing Ei with key i is performed, there is a key
speci¬ed several cryptographic techniques as
such that E has the same effect: Ei D jEk = E . In
“indispensable cryptographic techniques.” The
a pure cryptosystem, the mappings D jEk (“Ek fol-
CRYPTREC Evaluation Committee also evalu-
lowed by D j”) form a group, with Dk Ek being the
ated several cryptographic techniques as “speci¬c
identity.
evaluation” target ciphers for special reasons such
An endomorphic cryptosystem is pure if and
as requests from standardization organizations
only if its encipherings are closed under compo-
and the Law concerning Electronic Signatures
sition (Shannon), that is if its keys form a group,
and Certi¬cation.
the key group (see key).
Basically, the evaluation targets can be catego-
Friedrich L. Bauer rized into the following three types: “submitted
120 Cryptrec


cryptographic techniques,” “cryptographic tech- cryptographic techniques that satisfy the level of
niques for speci¬c evaluation,” and “indispensable security suf¬cient for e-Government usage. CRYP-
cryptographic techniques.” TREC has also performed software and hardware
implementation evaluations to measure the pro-
cessing speed and amount of system resources
Submitted Cryptographic Techniques
required.
In order to ensure that the technical evalu-
Cryptographic techniques in the categories of
ations are impartial and adequate, CRYPTREC
(1) digital signature, authentication, con¬dential-
has requested several specialists, besides its own
ity, and key agreement for public-key cryptogra-
members, to conduct evaluations (referred to as
phy, (2) 64-bit block ciphers, 128-bit block ciphers,
external evaluations).
and stream ciphers for symmetric-key cryptogra-
In order to ensure that evaluations are fair for
phy, and (3) hash functions and pseudorandom
all the cryptographic techniques in the same cat-
number generators were sought for evaluation.
egory, CRYPTREC has applied the same evalua-
The applicants who submitted techniques were
tion methods as much as possible to allow relative
asked to make their cryptographic techniques
comparisons.
procurable by the end of the ¬scal year 2002.
CRYPTREC Evaluation Committee received a to-
Evaluation Items
tal of 63 applications in both ¬scal years 2000 and
2001.
The evaluation in CRYPTREC progressed gradu-
ally and in parallel to get a good understanding
Indispensable Cryptographic Techniques
of algorithm properties and characteristics such
as security and performance; the evaluation also
In addition to the cryptographic techniques sub-
assessed how easy it was to develop ef¬cient im-
mitted by the applicants, the CRYPTREC Evalua-
plementations. There were four stages of the eval-
tion Committee has selected techniques that were
uation:
considered to be indispensable in the construc-
(1) Screening evaluation. Submitted documents
tion of e-Government systems. Such cryptographic
were studied to investigate whether the tar-
techniques must have either comparatively long
get cryptographic technique had any problems
track records of use and evaluation, or have a long
in the design concept, design policies, security,
history of usage. These targets were selected for
or implementation.
evaluation as “indispensable cryptographic tech-
(2) Full evaluation. The following items were in-
niques” whether or not an applicant submitted
vestigated: (a) whether known attacks are ap-
them.
plicable or not, (b) computational cost required
for a known attack to succeed, (c) validity of
Cryptographic Techniques for provable security, (d) validity of parameter/
Speci¬c Evaluation key generating methods, (e) selection of auxil-
iary functions and methods used to implement
“Cryptographic techniques for speci¬c evaluation” them in the scheme, (f) anticipated problems
are the cryptographic techniques that were eval- of submitted cryptographic techniques in real
uated by CRYPTREC on the basis of a special re- systems, and (g) whether any attack can be
quest, independent of their submission by an ap- mounted or not using the evaluators™ expertise.
plication and independent from a speci¬cation as The techniques were also compared with
“indispensable cryptographic techniques.” Crypto- other cryptographic techniques in order to as-
graphic techniques for speci¬c evaluation in the sess relative strengths and weaknesses.
¬scal years 2000 and 2001 are classi¬ed into (3) Software implementation evaluation. The com-
the following three categories: (1) cryptographic patibility and portability with respect to
techniques speci¬ed in Guidelines on the Law computing resources and environments was
concerning Electronic Signatures and Certi¬ca- veri¬ed by checking whether the software op-
tion Services, (2) cryptographic techniques used in erated as described in the submitted docu-
SSL3.0/TLS1.0, and (3) contributions to ISO/IEC ments in the following environments: (a) gen-
JTC1/SC27. eral PC environment, (b) most popular server
environment, and (c) high-performance, high-
EVALUATION AND SELECTION OF CRYPTO- end environment.
GRAPHIC TECHNIQUES: CRYPTREC has per- (4) Hardware implementation evaluation. It was
formed security evaluations in order to select investigated whether a third party could
Cryptrec 121


design the hardware using the submitted doc- of different input values with the same out-
put value is 2128 or more.
uments only.
(b) Widely used hash functions that have no
Evaluation Criteria security problems in realistic systems and
with a hash length of 160 bits or more are
selected.
The following criteria were set for evaluation
(4) Pseudorandom number generators: Pseudo-
of cryptographic techniques according to the
random number generators must satisfy all
categories.
the following conditions:
(1) Public-key cryptographic techniques. If a
(a) The statistical properties are close to that
public-key cryptographic technique has a solid
of a true random number. A past or future
track record of operation and evaluation over a
unknown output bit is hard to predict from
relatively long period of time and its speci¬ca-
the known output bit history.
tions cannot be changed easily from the stand-
(b) The seed size must be large enough to be
point of interoperability, the following condi-
secure against an exhaustive key search
tions must be satis¬ed:
of the system that uses a pseudorandom
(a) The cryptographic techniques must have
number generator.
been evaluated and researched thoroughly
(c) The statistical properties of pseudorandom
by a number of researchers.
number generators must pass a typical sta-
(b) No security problem has been reported in
tistical test suite for randomness such as
a realistic system.
SP800-22.
Relatively new public-key cryptographic
techniques were required to have at least
“provable security.” A comprehensive secu-
Requirements for the Draft of the
rity evaluation was carried out in addition
e-Government Recommended
to checking the provable security, including
Ciphers List
issues such as the validity of number theo-
retic problems, the method of selecting recom-
The CRYPTREC Advisory Committee has re-
mended parameters, and the method of using
quested the CRYPTREC Evaluation Committee to
auxiliary functions in a scheme.
evaluate the candidates for e-Government ciphers,
(2) Symmetric cryptography techniques. Sym-
cryptographic techniques that allow authentica-
metric-key cryptographic techniques must
tion, key agreement, con¬dentiality, and electronic
satisfy either of the following conditions:
signature functions in the e-Government sys-
(a) Even with the best attacking technique
tem, and prepare an e-Government recommended
available to date, a computational cost
ciphers list considering the following three
of 2128 or more (i.e., exhaustive search
points:
for a secret key) is required to break
(1) Select several cryptographic techniques with
symmetric-key cryptographic techniques.
suf¬cient security for use in the e-Government
It is necessary to show at the techniques
system (security guaranteed roughly 10
are secure against typical cryptanalytic at-
years).
tacks such as differential and linear crypt-
(2) Select for each category at least one crypto-
analysis.
graphic technique that is being-incorporated
(b) Widely used symmetric-key cryptographic
or likely to be incorporated in commercial soft-
techniques that have been evaluated in de-
ware (to be used by the general public).
tails and have no security problems in a
(3) Con¬rm the speci¬cations of cryptographic
realistic system are selected. In this case,
techniques recommended for e-Government to
a computational cost of 2100 or more is re-
guarantee that ciphers satisfying these speci-
quired to break them.
¬cations can be procured.
(3) Hash functions. Hash functions must satisfy
either of the following conditions:
RECOMMENDED CIPHERS
(a) Even with the best attacking technique E-GOVERNMENT
LIST: As a three-year comprehensive project, the
available to date, the computational cost
to ¬nd the input value for a speci¬c output “e-Government recommended ciphers list
value is not less than the computational (draft)” authored by the CRYPTREC Evaluation
cost required for an exhaustive search. Committee was submitted to the CRYPTREC
Also, even if the best attacking technique is Advisory Committee for review. Then, MPHPT
used, the computational cost to ¬nd a pair and METI invited comments from the general
122 Cryptrec


Table 1. e-Government recommended ciphers list (draft) (prepared in November 2002)

Category Name

Public-key Signature DSA
ciphers ECDSA
RSASSA-PKCS1-v1 5
RSA-PSS
Con¬dentiality RSA-OAEP
RSAES-PKCS1-v1 51
Key agreement DH
ECDH
PSEC-KEM2
64-bit block ciphers3
Symmetric-key CIPHERUNICORN-E
ciphers Hierocrypt-L1
MISTY1
3-key Triple DES4
128-bit block ciphers AES
Camellia
CIPHERUNICORN-A
Hierocrypt-3
SC2000
Stream ciphers MUGI
MULTI-S01
128-bit RC45
RIPEMD-1606
Others Hash function
SHA-16
SHA-256
SHA-384
SHA-512
Pseudorandom number PRNG based on SHA-1 in ANSI X9.42-2001 Annex C.1
generator7 PRNG based on SHA-1 for general purpose in FIPS 186-2
(+ change notice 1) Appendix 3.1
PRNG based on SHA-1 for general purpose in FIPS 186-2
(+ change notice 1) revised Appendix 3.1

Notes:
1
Use of this is permitted for the time being because it was used in SSL3.0/TLS1.0.
2
On the assumption that this is used in the KEM (Key Encapsulation Mechanism)-DEM (Data Encapsulation
Mechanism) construction.
3
When constructing a new e-Government system, 128-bit block ciphers are preferable if possible.
4
Using 3-key Triple DES is permitted for the time being under the following conditions:
(1) It is speci¬ed as FIPS 46-3.
(2) It is positioned as the de facto standard.
5
It is assumed that the 128-bit RC4 will be used only in SSL3.0/TLS(1.0 or later). If any other cipher listed
above is available, it should be used instead.
6
If any hash functions with a longer hash value are available when constructing a new e-Government system,
it is preferable that a 256-bit (or more) hash function be selected. However, this does not apply in cases where
the hash function to be used has already been designated according to the public-key cryptographic
speci¬cations.
7
Since pseudorandom number generators do not require interoperability due to their usage characteristics, no
problems will be created by using a cryptographically secure pseudorandom number generating algorithm.
Therefore, these algorithms are examples.


public. Finally, the draft was authorized as the remind uses that some cryptographic techniques
“e-Government recommended ciphers list”. require in employing them for e-Government ap-
In Table 1, we show the e-Government rec- plications. For more details, the reader is referred
ommended ciphers list. The notes are added to to the CRYPTREC Web site [1].
Cut-and-choose protocol 123


OTHER ACTIVITIES CUT-AND-CHOOSE
PROTOCOL
Revision of Guidelines on the Law
Concerning Electronic Signatures
and Certi¬cation Services CUT-AND-CHOOSE PROTOCOLS: A cut-and-
choose protocol is a two-party protocol in which
Guidelines on the Law concerning Electronic Sig- one party tries to convince another party that
natures and Certi¬cation Services were revised some data he sent to the former was honestly con-
corresponding to the CRYPTREC evaluation re- structed according to an agreed upon method. Im-
sults in the ¬scal year 2001. portant examples of cut-and-choose protocols are
interactive proofs [4], interactive arguments [1],
zero-knowledge protocols [1, 3, 4] and witness in-
SSL/TLS Evaluation Report distinguishable and witness hiding protocols [2]
for proving knowledge of a piece of information
CRYPTREC evaluated the security of SSL/TLS that is computationally hard to ¬nd. Such a pro-
(see Secure Socket Layer (SLS) and Transport tocol usually carries a small probability that it is
Layer Security (TLS)) and reported as follows: successful despite the fact that the desired prop-
SSL/TLS is secure against all known attacks. Us- erty is not satis¬ed.
ing SSL/TLS, one needs to ensure that patches The very ¬rst instance of such a cut-and-choose
are applied and that parameters are properly se- protocol is found in the protocol of Rabin [5] where
lected. SSL/TLS is considered to offer an adequate the cut-and-choose concept is used to convince a
security level for practical use. The functionality party that the other party sent him an integer n
of TLS is still being extended. New security weak- that is a product of two primes p, q, each of which
nesses can emerge as a result of these extensions. is congruent to 1 modulo 4. Note that this protocol
Therefore, it is necessary to monitor the status was NOT zero-knowledge.
and progress of TLS and to keep investigating its The expression cut-and-choose was later intro-
security. duced by Chaum [1] in analogy to a popular cake
sharing problem: given a complete cake to be
shared among two parties distrusting each other
Publicizing External Evaluation Reports
(for reasons of serious appetite). A fair way for
them to share the cake is to have one of them cut
CRYPTREC considers it important to publicize
the cake in two equal shares, and let the other one
the cryptographic technique evaluation results in
choose his favourite share. This solution guaran-
order to improve the reliability of security evalu-
tees that it is in the former™s best interest to cut
ations. All external evaluation reports that were
the shares as evenly as possible.
compiled as a part of the evaluation activities of
CRYPTREC are available on the CRYPTREC Web
site [1].


Monitoring and Other Evaluations

After publishing the e-Government recommended
ciphers list, the main responsibility of CRYPTREC
has moved to monitoring the security of crypto-
graphic techniques in the list. CRYPTREC also
has started the evaluation of cryptographic mod-
Claude Cr´ peau
e
ules and protocols.
References
Hideki Imai
Atsuhiro Yamagishi
[1] Brassard, G., D. Chaum, and C. Cr´ peau (1988).
e
“Minimum disclosure proofs of knowledge.” JCSS,
Reference 37, 156“189.
[2] Feige, U. and A. Shamir (1990). “Witness indis-
[1] CRYPTREC Web site, http://www.shiba.tao.go.jp/ tinguishable and witness hiding protocols.” Pro-
kenkyu/CRYPTREC/index.html and http://www. ceedings of the 22nd Annual ACM Symposium on
ipa.go.jp/security/enc/CRYPTREC/index.html the Theory of Computing, Baltimore, MD, May
124 Cyclic codes


est distance between different codewords; it de-
1990, ed. Baruch Awerbuch. ACM Press, New York,
416“426. termines the error correcting capabilities of C. In-
deed, C can correct t = (d ’ 1)/2 errors. Since
[3] Goldreich, Oded, Silvio Micali, and Avi Wigderson
(1991). “Proofs that yield nothing but their validity we focus on cyclic codes and on the most useful of
or all languages in NP have zero-knowledge proof them, the alphabet A will be a ¬nite ¬eld Fq of
systems.” Journal of the Association for Computing
characteristic 2, i.e., q = 2e for some integer e ≥ 1.
Machinery, 38 (3), 691“729.
Moreover, the length of the codes will be generally
[4] Goldwasser, Sha¬, Silvio Micali, and Charles Rack-
2m ’ 1, where e divides m; these codes are said
off (1989). “The knowledge complexity of interactive
primitive.
proof systems.” SIAM Journal on Computing, 18 (1),
186“208.
n
DEFINITION 1. Consider the linear space Fq of all
[5] Rabin, M.O. (1977). “Digitalized signatures.” Foun-
n-tuples over the ¬nite ¬eld Fq . An [n, k, d] linear
dations of Secure Computation. Papers presented
n
at a 3 day workshop held at Georgia Institute of code C over Fq is a k-dimensional subspace of Fq
Technology, Atlanta, October 1977, eds. Richard A. with minimum distance d.
DeMillo et al. Academic Press, New York, 155“166.
By de¬nition, a k-dimensional linear code C is
fully determined by a basis over Fq . When we put
the k vectors of a basis as rows in a k — n matrix G,
CYCLIC CODES we get a generator matrix of C. Indeed, C is given
by {avG | a ∈ Fq }.
k
INTRODUCTION: For a general presentation of The Hamming weight wt(u) of any word u in
cyclic codes, our main reference is the Handbook n
Fq is the number of its nonzero coordinates. Note
of Coding Theory, especially the ¬rst chapter [4] that wt(u) = d(u, 0). Obviously, for linear codes,
(but also Chapters 11, 13, 14, and 19). the minimum distance is exactly the minimum
Cyclic codes were introduced as a particular weight of nonzero codewords.
practical class of error-correcting codes (ECC).
Codes are devoted to the following fundamental PROPOSITION 1. Let C be any [n, k, d] linear code
problem: how to determine what message has been over Fq . Then
sent when only an approximation is received, due
to a noisy communication channel. Cyclic codes d = min{wt(c) | c ∈ C \ {0}}.
belong to the class of block codes since here all
messages have the same length k. Each of them The dual code of C is the [n, n ’ k] linear code:
is encoded into a codeword of length n = k + r. A
C ⊥ = {y ∈ Fq | c · y = 0, for all c ∈ C},
t-error-correcting code is a well-chosen subset C of n
An . Its elements are called codewords and have the
property that each pair of them differs in at least where “·” denotes the ordinary inner product of
2t + 1 coordinates. If the noisy channel generates n’1
vectors: c · y = i=0 ci yi . An (n ’ k) — n generator
matrix of C ⊥ is called a parity check matrix H for
not more than t errors during one transmission,
C. Note that C = {y ∈ Fq | HyT = 0T }.
the received vector will still lie closer to the orig- n
inally transmitted codeword than any other code- When studying cyclic codes, it is convenient
word. This means that code C is able to correct t to view the labeling of the coordinate posi-
tions 0, 1, . . . , n ’ 1 as integers modulo n (see
positions in each codeword.
A codeword will be denoted by modular arithmetic). In other words, viewing
these coordinate positions as forming a cycle with
c = (c0 , c1 , . . . , cn’1 ), ci ∈ A.
n ’ 1 being followed by 0.
When the encoder is systematic, the ¬rst k sym-
bols are called information symbols (they are the DEFINITION 2. A linear code C of length n over
message) and the last r symbols are the redun- Fq is cyclic if and only if it satis¬es for all c =
dancy symbols (added to help recover the mes- c0 · · · cn’2 cn’1 in C:
sage if errors occur). We consider here linear codes,
meaning that A is a ¬nite ¬eld and that C is a (c0 , . . . , cn’2 , cn’1 ) ∈ C =’ (cn’1 , c0 , . . . , cn’2 ) ∈ C.
k-dimensional linear subspace of An .
The vector cn’1 c0 · · · cn’2 is obtained from c by the
The (Hamming) distance between two code-
cyclic shift of coordinates i ’ i + 1.
words, c and c , is de¬ned by:
d(c, c ) = card {i ∈ [0, n ’ 1] | ci = ci }.
EXAMPLE 1. The generator matrix G below de¬nes
The minimum distance d of a code C is the small- an [8, 4, 2] binary cyclic code (length 8, dimension
Cyclic codes 125


4, and minimum weight 2): where m is the smallest positive integer such that
n divides q m ’ 1 (so ± ∈ Fq m ).
® 
The minimal polynomial of ± s over Fq is
1 0 0 0 1 0 0 0
0 0
1 0 0 0 1 0
G= .
°0 0» M±s (x) = (x ’ ± i ),
0 1 0 0 0 1
i∈c (s)
0 0 0 1 0 0 0 1
where the ± i , i ∈ c (s), are called the conjugates
Cyclic codes are some of the most useful
of ± s .
codes known. The involvement of Reed“Solomon
(RS) codes and of Bose“Chaudhury“Hocquen-
If ω is a primitive element of Fq m , then one can
ghem (BCH) codes in a number of applications is
take ± = ω(q ’1)/n . Note that M±s (x) is a polynomial
m

well known. On the other hand, the Golay codes
over Fq while ± ∈ Fq m .
and the Reed“Muller (RM) codes, which are fun-
damental linear codes, can be represented as cyclic
THEOREM 1. Let C be a nonzero cyclic code of
codes.
length n over Fq . There exists a polynomial g(x) ∈
C, called the generator polynomial of C, with the
CONSTRUCTIVE DEFINITION: It seems dif¬cult following properties:
to construct a cyclic code C by means of De¬nition (i) g(x) is the unique monic polynomial of mini-
2. So, useful de¬nitions of cyclic codes are now con- mum degree in C;
sidered. (ii) g(x) is a generator of the ideal C in Rn :
An ef¬cient de¬nition is established by identify-
ing each vector c = (c0 , c1 , . . . , cn’1 ) with the poly- C = g(x) = {a(x)g(x) (mod x n ’ 1) |
nomial c(x) = c0 + c1 x + · · · + cn’1 x n’1 . The fact a(x) ∈ Fq [x]};
that C is invariant under a cyclic shift is then ex-
(iii) g(x) divides x n ’ 1.
pressed as follows:
Let r = deg(g), and let g(x) = r gi xi where
i=0
c(x) ∈ C =’ xc(x) (mod x n ’ 1) ∈ C. gr = 1. Then
(iv) the dimension of C is k = n ’ r ; moreover the
Thus the proper context for studying cyclic codes
polynomials
of length n over Fq is the residue class ring
g(x), xg(x), . . . , x k’1 g(x)
Rn = Fq [X]/(x n ’ 1).
It is well known that Rn is a principal ideal ring. form a basis of C. The corresponding generator
This means that any ideal I in Rn is generated matrix is given by:
by a single element g in I, i.e., I = {ag | a ∈ Rn }. ® 
g0 g1 · · · gn’k ···
(An ideal in Rn is a subset I of Rn satisfying the 0 0
 0 g0 g1 0
· · · gn’k
properties: (1) for all i1 , i2 in I also i1 ’ i1 ∈ I and  
G= . . .
(2) for any i ∈ I and a ∈ Rn also ai ∈ I.) .. .. ..
°. .»
. . .
. .
An alternative de¬nition of a cyclic code can now
··· ···
0 0 g0 g1 gn’k
be given.
(v) Let ± be a primitive nth root of unity in some
DEFINITION 3. A cyclic code C of length n over Fq extension ¬eld of Fq . Denote by M±s the mini-
is a principal ideal of the ring Rn . The codewords mal polynomial of ± s over Fq ; then
are polynomials in Fq [x] of degree less than n. Mul-
tiplication is carried out modulo x n ’ 1. g(x) = M±s (x)
s∈I
The next theorem, which is given in [4, Theorem
where I is a subset of representatives of the
5.2], allows to determine the main parameters of
q-cyclotomic cosets modulo n.
any cyclic code of Rn . We ¬rst recall some basic
de¬nitions.
The dual code of any cyclic code is cyclic too. The
description of C ⊥ can be directly obtained from
DEFINITION 4. Let ± be a primitive nth root of
Theorem 1.
unity in some extension ¬eld of Fq . This means
that 1, ±, . . . , ± n’1 are all different and ± n = 1. For
COROLLARY 1. Let C be a cyclic code of length n
each integer s with 0 ¤ s < n, denote by c (s) the
over Fq , with generator polynomial g(x). Let h(x)
q-cyclotomic coset of s modulo n:
denote the parity check polynomial of C, de¬ned by
c (s) = {s, qs, . . . , q m’1 s (mod n)}, x n ’ 1 = h(x)g(x). Then the generator polynomial
126 Cyclic codes


of C ⊥ is the polynomial SOME CYCLIC CODES: From now on q = 2e and
n = q m ’ 1. Let C be any cyclic code of length n
k
x
h(x ’1 ),
h(x) = where k = n ’ deg(g). over Fq with generator polynomial g(x). The roots
h0 of g(x) are called the zeros of the cyclic code C.
Thus, the code C is fully de¬ned by means of its
EXAMPLE 2. Construction of the binary Hamming
zero™s set; this leads to the classical de¬nition of
code of length n = 15.
the BCH codes and of other important families.
x 15 ’ 1 = (x 4 + x 3 + 1)(x 4 + x + 1)(x 4 + x 3
DEFINITION 5. Let q = 2 and n = 2m ’ 1; denote
+ x 2 + x + 1)(x + 1)(x 2 + x + 1).
by ± a primitive nth root of unity in F2m . Let δ be
Since x 4 + x + 1 is a primitive polynomial (mean- an integer with 2 ¤ δ ¤ n.
ing that its zeros are primitive elements), its root The binary BCH code of length n and de-
± is a generator of the cyclic group of the ¬eld F16 . signed distance δ is the cyclic code with zero™s set:
±, ± 2 , . . . , ± δ’1 and their conjuguates. In other
The polynomial x 4 + x + 1 is the minimal polyno-
mial of ± and has ± and its conjugates as zeros. words, the generator polynomial of this code is
Consider the cyclic code C with generator polyno-
g(x) = l cm{M± (x), M±2 (x), . . . , M±δ’1 (x)}.
mial:
g(x) = (x ’ ±)(x ’ ± 2 )(x ’ ± 4 )(x ’ ± 8 )
EXAMPLE 3. Binary BCH codes of length 15. As in
= x 4 + x + 1.
Example 2, we denote by ± any root of the primi-
The dimension of C is 15 ’ deg(g) = 11. Thus the tive polynomial x 4 + x + 1. Now the factorization
of x 15 ’ 1 into minimal polynomials is as follows:
code C is a [15, 11, 3] cyclic code. The minimum
distance of C is exactly 3 since wt(g) = 3 and no
x 15 ’ 1 = (x ’ 1) (x 4 + x + 1) (x 4 + x 3 + x 2 + x + 1)
smaller weight can appear, as can be checked us-
ing a generator matrix G of C. According to Theo- M(±) M(± 3 )
rem 1, G is an 11 — 15 binary matrix whose lines (x 2 + x + 1) (x 4 + x 3 + 1) .
are g(x)
M(± 5 ) M(± 7 )
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
xxxxxxxxxxx x x x x
There are three nontrivial BCH codes, whose
g(x) 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0
zero™s sets Sδ are as follows:
r S3 = {± i | i = 1, 2, 4, 8} for the [15, 11, 3] BCH
and the 10 shifts of g(x). The parity check polyno-
mial of C and the generator polynomial of C ⊥ are code;
r S5 = S3 ∪ {± i | i = 3, 6, 9, 12} for the [15, 7, 5]
given by:
BCH code;
r
x 15 ’ 1
S7 = S5 ∪ {± i | i = 5, 10} for the [15, 5, 7] BCH
h(x) =
x4 + x + 1 code.
= x 11 + x 8 + x 7 + x 5 + x 3 + x 2 + x + 1. For these codes, the designed distance δ is exactly
the minimum distance; this property does not hold
resp.
for any BCH code.
11
h(x) = h11’i xi
DEFINITION 6. A Reed“Solomon code over Fq is a
i=0
BCH code of length n = q ’ 1.
=x + x 10 + x 9 + x 8 + x 6 + x 4 + x 3 + 1.
11


We then obtain a parity check matrix for C: RS codes appear in several cryptosystems. They
determine, for instance, some secret-sharing sch-
x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x 10 x 11 x 12 x 13 x 14
emes [3]. It is important to note that for RS codes,
1 0 0 1 1 0 1 0 1 1 1 1 0 0 0
the designed distance is exactly the minimum
0.
0 1 0 0 1 1 0 1 0 1 1 1 1 0
distance. Moreover, the RS code with designed dis-
0 0 1 0 0 1 1 0 1 0 1 1 1 1 0
tance δ is an [n, k, δ] code with k = n ’ δ + 1. Since
0 0 0 1 0 0 1 1 0 1 0 1 1 1 1
this k attains the maximum value by the Single-
We explained here, by means of an example, the ton bound (see [4]), one says that RS codes are
general de¬nition of the binary Hamming code of maximum distance separable (MDS) code.
length 2m ’ 1. It is a code whose parity check ma-
DEFINITION 7. Let ± be a primitive root of F2m .
trix has as columns all the nonzero vectors of Fm .
2
It is a [2m ’ 1, 2m ’ m ’ 1, 3] code. Any integer s ∈ [0, 2m ’ 1] can be identi¬ed by its
Cyclic codes 127


binary expansion in Fm : EXAMPLE 4. Consider any binary cyclic code of
2
length n = 2m ’ 1 whose generator polynomial
m’1
is the product of two minimal polynomials,
s= si 2i , si ∈ {0, 1} =’ s = (s0 , . . . , sm’1 ).
say M±r (x)M±s (x). These codes are said to be
i=0
cyclic codes with two zeros and usually denoted
The cyclic Reed“Muller code of length 2m ’ 1 and by Cr,s .
order r , usually denoted by R— (r, m), is the binary Now assume that r = 1 and gcd(s, 2m ’ 1) = 1.
cyclic code with zero set: Then C1,s is an [n, 2m, d] cyclic code; the dual
Sr = { ± s | 1 ¤ wt(s) < m ’ r }, of C1,s is a cyclic code which has two nonzeros
only: ± n’1 and ± n’s (apart from their conjugates).
where wt(s) is the Hamming weight of s. ⊥
According to (1), C1,s is the set of binary codewords
of length n de¬ned as follows: each pair (a, b) of
Note that if one extends all codewords in the
elements of F2m provides the ordered sequence of
cyclic Reed“Muller code above with an overall-
values
parity check symbol, one obtains the regular
x ∈ {1, ±, . . . , ± n’1 } ’’ Tr(ax + bx s ),
Reed“Muller code.
Binary cyclic codes are related to the study
where the Trace function Tr is de¬ned by Tr(β) =
and the construction of cryptographic primitives, m’1
β + β 2 + · · · + β 2 . The power function x ’ x s is
mainly through Reed“Muller codes because of the
a permutation on F2m . It is said to be almost per-
large ¬eld of applications of Boolean functions and
fect nonlinear [1] when C1,s has minimum dis-
binary sequences in cryptography. They play a
tance 5. It is said to be an AB function when the
role in the study of cryptographic mapping on ¬- ⊥
nonzero weights of codewords of C1,s are either
nite ¬elds in general. One well-known application
2m’1 or 2m’1 ± 2(m’1)/2 ; this is possible for odd m
is the construction of almost bent (AB) mappings
only.
(see nonlinearity of Boolean functions), which re-
sist both differential and linear cryptanalysis [1,2]
Pascale Charpin
(see next example). These connections are more
explicit when using the trace representation of bi-
nary codewords of length n = 2m ’ 1. We now la-
References
bel the coordinate positions by ± 0 , ± 1 , . . . , ± n’1 ,
where ± is a primitive nth root of unity. Let c(x)
[1] Canteaut, A., P. Charpin, and H. Dobbertin (1999).
be any codeword of some binary cyclic code C of
“A new characterization of almost bent functions.”
length n. De¬ne Fast Software Encryption (FSE6), Lecture Notes
n’1 in Computer Science, vol. 1636, ed. L.R. Knudsen.
Tc (x) = c(± n’s )x s . (1) Springer-Verlag, Berlin, 186“200.
s=0 [2] Carlet, C., P. Charpin, and V. Zinoviev (1998).
“Codes, bent functions and permutations suitable
This commonly known Fourier transform of c is
for DES-like cryptosystems.” Designs Codes and
called the Mattson“Solomon polynomial of c in al-
Cryptography, 15 (2), 125“156.
gebraic coding theory. It follows that Tc (± j) = c j
[3] McEliece, R.J. and D.V. Sarwarte (1981). “On shar-
and Tc (x) is a sum of traces from some sub¬elds of
ing secrets and Reed“Solomon codes.” Comm. ACM,
F2m to F2 . 24, 583“584.
The mapping x ’ Tc (x) is a Boolean function. [4] Pless, V.S., W.C. Huffman, and R.A. Brualdi (1998).
On the other hand, any binary sequence of pe- “An introduction to algebraic codes.” Handbook of
riod n can be represented in this way (see entries Coding Theory, Part 1: Algebraic Coding. Elsevier,
Boolean functions and Sequences). Amsterdam, The Netherlands, Chapter 1.

<<

. 4
( 5)



>>