ńņš. 2 |

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

See also Euclidean Algorithm.

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-

Aā g ing power products. See also signed digit exponen-

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-

Traditionally, passwords (knowledge-based se- sive task. Biometrics, on the other hand, addresses

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 |