<< Ļšåäūäółą’ ńņš. 2(čē 11 ńņš.)ĪĆĖĄĀĖÅĶČÅ Ńėåäóžłą’ >>
loop may be decided by examining the parity of s .
in some semigroup; a semigroup is an algebraic
If m is odd and s is even, then s must be even.
structure that is like a group except that elements
The run time complexity is O((log(n))2 ) bit op-
need not have inverses, and that there may not
erations. Convergence of the algorithm, if not ob-
even be a neutral element). The term exponentia-
vious, can be shown by induction. A complexity
tion assumes that the group operation is written
analysis of the binary euclidean algorithm was
multiplicatively. If the group operation is written
presented by Brent in [2]. Bach and Shallit give
additively, one speaks of scalar multiplication in-
a detailed analysis and comparison to other GCD
stead, but this change in terminology does not af-
algorithms in [1].
fect the essence of the task.
Sorenson claims that the binary Euclidean al-
Let ā—¦ denote the group operation and assume
gorithm is the most efļ¬cient algorithm for com-
that the exponentiation to be performed is ge
puting greatest common divisors [7]. In the same
where g is an element of the group (or semi-
reference Sorenson also proposed a k-ary version
group) and e is a positive integer. Computing the
of the binary GCD algorithm with worst case run-
result g ā—¦ Ā· Ā· Ā· ā—¦ g in a straightforward way by ap-
ning time O(n2 / log(n)).
plying the group operation e ā’ 1 times is feasible
In [3], Jebelean claims that Lehmerā™s Euclidean
only if e is very small; for e ā„ 4, it is possible to
algorithm is more efļ¬cient than the binary GCD
compute ge with fewer applications of the group
algorithm. The same author presents [4] a word-
operation. Determining the minimum number of
level generalization of the binary GCD algorithm
group operations needed for the exponentiation,
with better performance than Lehmerā™s Euclidean
given some exponent e, is far from trivial; see
algorithm.
ļ¬xed-exponent exponentiation. (Furthermore, the
time needed for each single computation of the
group operation is usually not constant: for ex-
Berk Sunar
ample, it often is faster to compute a squaring
A ā—¦ A than to compute a general multiplication
References
A ā—¦ B.) Practical implementations that have to
work for arbitrary exponents need exponentiation
[1] Bach, E. and J. Shallit (1996). Algorithmic Number
algorithms that are reasonably simple and fast.
Theory, Volume I: Efļ¬cient Algorithms. MIT Press,
Assuming that for the exponentiation one can
Cambridge, MA.
[2] Brent, R.P. (1976). āAnalysis of the binary Euclidean use no other operation on group elements than
the group operation ā—¦ (and that one cannot make
algorithm.ā Algorithms and Complexity, ed. J.F.
Traub. Academic Press, New York, 321ā“355. use of additional information such as the order
[3] Jebelean, T. (1993). āComparing several gcd algo- of the group or the order of speciļ¬c group ele-
rithms.ā 11th IEEE Symposium on Computer Arith-
ments), it can be seen that for l-bit exponents
metic.
(i.e., 2lā’1 ā¤ e < 2l ), any exponentiation method
[4] Jebelean, T. (1993). āA generalization of the binary
will have to apply the group operation at least l ā’ 1
gcd algorithm.ā Proceedings of the 1993 Interna-
times to arrive at the power ge . The left-to-right
tional Symposium on Symbolic and Algebraic Com-
binary exponentiation method is a very simple and
putation. ACM Press, New York, 111ā“116.
memory-efļ¬cient technique for performing expo-
[5] Knuth, D.E. (1997). The Art of Computer Pro-
nentiations in at most 2(l ā’ 1) applications of the
gramming, Volume 2: Seminumerical Algorithms
Binomial distribution 33

group operation for any l-bit exponent (i.e., within that all bits besides elā’1 are uniformly and inde-
pendently random, (l ā’ 1)/2 general group opera-
a factor of 2 from the lower bound). It is based on
tions (A ā—¦ g or B ā—¦ A) on average.
the binary representation of exponents e:
Various other algorithms are known that can be
lā’1
considered variants or generalizations of binary
e= ei ā {0, 1}.
ei 2i ,
exponentiation: see 2k -ary exponentiation and
i=0
sliding window exponentiation for other meth-
With l chosen minimal in such a representation,
ods for computing powers (which can often be
we have elā’1 = 1. Then ge can be computed as fol-
faster than binary exponentiation), and see simul-
lows:
taneous exponentiation for methods for comput-
for i = l ā’ 2 down to 0 do tiation for techniques that can improve efļ¬ciency
A ā Aā—¦ A in groups allowing fast inversion.
if ei = 1 then
Bodo MĀØ ller
o
A ā Aā—¦ g
return A
If the group is considered multiplicative, then com-
puting A ā—¦ A means squaring A, and computing BINOMIAL DISTRIBUTION
A ā—¦ g means multiplying A by g; hence this algo-
rithm is also known as the square-and-multiply If a two-sided coin is ļ¬‚ipped n times, what is the
method for exponentiation. If the group is consid- probability that there are exactly k heads? This
ered additive, then computing A ā—¦ A means dou- probability is given by the binomial distribution.
bling A, and computing A ā—¦ g means adding g to A; If the coin is unbiased and the coin ļ¬‚ips are in-
hence this algorithm is also known as the double- dependent of one another, then the probability is
and-add method for scalar multiplication. given by the equation
The algorithm shown above performs a left-to-
n ā’n
right exponentiation, i.e., it starts at the most sig- Pr[k heads | n coin ļ¬‚ips] = 2.
k
niļ¬cant digit of the exponent e (which, assuming
big-endian notation, appears at the left) and goes Here, the notation n , read ān choose k,ā is the
k
toward the least signiļ¬cant digit (at the right). number of ways of choosing k items from a set of n
The binary exponentiation method also has a vari- items, ignoring order. The value may be computed
ant that performs a right-to-left exponentiation, as
i.e., starts at the least signiļ¬cant digit and goes
n n!
= .
toward the most signiļ¬cant digit:
k!(n ā’ k)!
k
ļ¬‚ag ā false
For the ļ¬rst several values of n, the following
B ā identity element
probabilities are as follows for an unbiased coin
Aāg
(read k left to right from 0 to n):
for i = 0 to l ā’ 1 do
if ei = 1 then n=0: 1
if ļ¬‚ag then n=1: 1 1
2 2
Bā Bā—¦ A
n=2: 1 1 1
else 4 2 4
B ā A {Equiv. to B ā B ā—¦ A} n=3: 1 3 3 1
8 8 8 8
ļ¬‚ag ā true
n=4: 1 1 3 1 1
if i < l ā’ 1 then 16 4 8 4 16

Aā Aā—¦ A More generally, if the coin ļ¬‚ips are independent
but the probability of heads is p, the binomial dis-
return B
tribution is likewise biased:
This algorithm again presumes that elā’1 = 1. The Pr[k heads | n coin ļ¬‚ips, probability p of heads]
right-to-left method is essentially the traditional
nk
= p (1 ā’ p)nā’k .
algorithm known as āRussian peasant multiplica-
k
tion,ā generalized to arbitrary groups.
For an l-bit exponent, the left-to-right and right- The name ābinomialā comes from the fact that
to-left binary exponentiation methods both need there are two outcomes (heads and tails) and the
l ā’ 1 squaring operations (A ā—¦ A) and, assuming probability distribution can be determined by
34 Biometrics

computing powers of the two-term polynomial
(binomial) f(x) = px + (1 ā’ p). The probability
that there are exactly k heads after n coin ļ¬‚ips is
exactly the same as the x k term of the polynomial
f(x)n .
As coin ļ¬‚ips (either physical or their compu-
tational equivalent) are the basic building block (a) Fingerprint (b) Face (c) Hand Geometry
1
of randomness in cryptography, the binomial dis- 0.8
0.6
tribution is likewise the foundation of probability 0.4
0.2
analysis in this ļ¬eld. 0
ā’0.2
ā’0.4
Burt Kaliski ā’0.6
ā’0.8
ā’1
012345678
Ć— 104
(d) Signature (e) Iris (f) Voice
BIOMETRICS
Fig. 1. Examples of some of the biometric traits used for
authenticating an individual
A wide variety of systems require reliable au-
thentication schemes to conļ¬rm the identity
of an individual requesting their services (see traditional security techniques. For example,
identiļ¬cation). The purpose of such schemes is to users maintaining different passwords for differ-
ensure that the rendered services are accessed ent applications may ļ¬nd it challenging to recol-
only by a legitimate user, and no one else. Ex- lect the password associated with a speciļ¬c ap-
amples of such applications include secure access plication. In some instances, the user might even
to buildings, computer systems, laptops, cellular forget the password, requiring the system admin-
phones, and ATMs. In the absence of robust au- istrator to intervene and reset the password for
thentication schemes, these systems are vulnera- that user. Maintaining, recollecting, and resetting
ble to the wiles of an impostor. passwords can, therefore, be a tedious and expen-
curity) and ID cards (token-based security) have this problem effectively: a user can use the same
been used to restrict access to systems. However, biometric trait (e.g., right index ļ¬nger) or differ-
security can be easily breached in these systems ent biometric traits (e.g., ļ¬ngerprint, hand geome-
when a password is divulged to an unauthorized try, iris) for different applications, with āpasswordā
user or an ID card is stolen by an impostor. Fur- recollection not being an issue at all.
ther, simple passwords are easy to guess (by an A typical biometric system operates by acquir-
impostor) and complex passwords may be hard ing biometric data from an individual, extracting
to recall (by a legitimate user). The emergence a feature set from the acquired data, and compar-
of biometrics has addressed the problems that ing this feature set against the template feature
plague these traditional security methods. Bio- set stored in the database (Figure 2). In an identi-
metrics refers to the automatic identiļ¬cation (or ļ¬cation scheme, where the goal is to recognize the
veriļ¬cation) of an individual (or a claimed iden- individual, this comparison is done against tem-
tity) by using certain physiological or behavioral plates corresponding to all the enrolled users (a
traits associated with the person. By using biomet- one-to-many matching); in a veriļ¬cation scheme,
rics it is possible to establish an identity based on where the goal is to verify a claimed identity, the
āwho you are,ā rather than by āwhat you possessā comparison is done against only those templates
(e.g., an ID card) or āwhat you rememberā (e.g., corresponding to the claimed identity (a one-to-
a password). Current biometric systems make one matching). Thus, identiļ¬cation (āwhose bio-
use of ļ¬ngerprints, hand geometry, iris, retina, metric data is this?ā) and veriļ¬cation (ādoes this
face, hand vein, facial thermograms, signature, biometric data belong to Bob?ā) are two differ-
voiceprint, etc. (Figure 1) to establish a personā™s ent problems with different inherent complexities.
identity [1, 4]. While biometric systems have their The templates are typically created at the time
limitations (e.g., additional cost, temporal changes of enrollment, and, depending on the application,
in biometric traits, etc.), they have an edge over may or may not require human personnel inter-
traditional security methods in that they cannot vention.
be easily stolen or shared. Biometric systems are being increasingly de-
Biometric systems also introduce an aspect of ployed in large scale civilian applications. The
user convenience that may not be possible using Schiphol Privium scheme at the Amsterdam
Biometrics 35

Identity, I

Enrollment Module
Template
Feature Set
User Biometric Sensor Feature Extractor

Template
Database
Claimed Identity, I

Verification Module

User Template
Biometric Sensor Feature Extractor
Feature Set

Feature Set

Accept/
Feature Matcher
Reject

Fig. 2. The enrollment module and the veriļ¬cation module of a biometric system

the userā™s claimed identity is either accepted or re-
 << Ļšåäūäółą’ ńņš. 2(čē 11 ńņš.)ĪĆĖĄĀĖÅĶČÅ Ńėåäóžłą’ >>