=Paper=
{{Paper
|id=Vol-2588/paper11
|storemode=property
|title=Mathematical Model of the Biometric System of Fingerprint Authentication for Modern Web-Services
|pdfUrl=https://ceur-ws.org/Vol-2588/paper11.pdf
|volume=Vol-2588
|authors=Sergey Rassomakhin,Kate Budianska,Mykhaylo Bagmut,Iryna Chepurko,Tetiana Ivko,Tetiana Kuznetsova
|dblpUrl=https://dblp.org/rec/conf/cmigin/RassomakhinBBCI19
}}
==Mathematical Model of the Biometric System of Fingerprint Authentication for Modern Web-Services==
https://ceur-ws.org/Vol-2588/paper11.pdf
Mathematical Model of the Biometric System of
Fingerprint Authentication for Modern Web-Services
Sergey Rassomakhin, Kate Budianska, Mykhaylo Bagmut, Iryna Chepurko,
Tetiana Ivko and Tetiana Kuznetsova
V. N. Karazin Kharkiv National University, Svobody sq., 4, Kharkiv, 61022, Ukraine
rassomakhin@karazin.ua, budyanskaya96@gmail.com,
sapsanmiha@gmail.com, i.chepurko@karazin.ua, t.ivko@outlook.com
kuznetsova.tatiana17@gmail.com
Abstract. This paper considers mathematical models of biometric fingerprint
images, as well as basic computational procedures for fingerprinting. The main
stages of processing dactyloscopic portraits based on the selection of local fea-
tures, their filtering and digital processing are investigated. The developed
software implements the transformation of fingerprint images with the subse-
quent formation of a cryptographically strong password sequence based on
them. This allows you to simulate a dactyloscopic authentication system for the
purpose of studying certain of its properties, estimating probabilistic perfor-
mance indicators (error probabilities of the first and second kind), and so on.
Keywords: fingerprints, biometric image, password authentication, biometric
system, web-service.
Introduction
To date, biometric technologies are actively used in many areas of everyday life that
are related to providing access to information [1-5], in the tasks of identification and
authentication of personality [6-8]. Biometrics uses the following features that are
inherent to each individual: a papillary finger pattern, a pattern of the iris, voice pa-
rameters, a blood vessel pattern and so on [7, 9-10].
All people have a unique fingerprint pattern, so everyone can be identified. Identi-
fication algorithms use points on fingerprints: the end of the pattern line, line branch-
ing, single points [11-15]. Also, the morphological structure of the fingerprint is con-
sidered, namely, the relative position of the closed, arched and spiral lines of the pa-
pillary pattern. The features of fingerprint portraits are transformed into a unique code
that preserves the informative image of the imprint [7, 14-18].
Thus, the actual formation of a model of a biometric fingerprint portraiture system
and subsequent authentication is relevant. The purpose of this work is to develop a
mathematical method and algorithm for converting fingerprint portraits for reliable
authentication on fingerprints. This research might be useful for the improvement of
various methods of information security, as well as other practical use [19-24].
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attrib-
ution 4.0 International (CC BY 4.0) CMiGIN-2019: International Workshop on Conflict Management in
Global Information Networks.
1 Formation of the model of fingerprints
Dactyloscopy is a subdiscipline of traosology that studies the configuration of papil-
lary lines of the skin on the palms, fingers, legs and special techniques for their inves-
tigation in order to establish the identity of the person in the process of identification
and authentication of users for access to a secure system, etc. [25]. There are two
types of attributes: global and local. The global features include the core (center), the
point "delta" (starting point), line type, counter line, types of patterns. Local signs are
also minutias that are unique for each imprint of signs that determine the points of
change in the structure of papillary lines (ending, splitting, rupture, etc.), the orienta-
tion of the papillary lines and the coordinates in these points. Each imprint can con-
tain from 16 to 70 minutias [7, 9].
Classification of all fingerprints is based on the existence of singular points - glob-
al fingerprint signs [9, 25-30]. Although the fingerprints of different people may have
the same global characteristics, it is completely impossible to have the same local
characteristics. Therefore, global attributes are used to classify the database into clas-
ses - the authentication phase. At the next stage, local identification is used to identi-
fy.
Papillary patterns on the human fingertips form three types of patterns, namely:
"loop" (left, right, central, double), delta or arc (simple and acute), "spiral" (central
and mixed) (Fig. 1).
а b c
Fig. 1. Types of fingerprint patterns: loop (a), delta (b) and spiral (c)
The fundamental distinction between identification and authentication is the level
of trust to the user. At the previous stage of system identification, the level of trust to
the user being logged is a priori high. In a multi-user system, biometric identification
must be carried out under the direct control of its owner or its representative, which
confirms the user's authority and correctness of the behavior during the system train-
ing.
The biometric authentication mode, conversely, implies a low level of confidence
in the identity that is authenticated. When biometric authentication, the applicant must
prove the authenticity of his claimed name by presenting his unique biometric images.
It should be noted that biometric authentication is potentially vulnerable if it is used
regardless of the methods of classical authentication based on protocols using pass-
words and keys. An adequate level of information security can only be achieved by
combining methods of classical and biometric authentication.
Any biometric system can accept errors of the first and the second kind. In biomet-
rics, the most constant notions are FAR (False Acceptance Rate) and FRR (False
Rejection Rate). The first number characterizes the probability of a false coincidence
of the biometric characteristics of two people. The second is the likelihood of denial
of access to a person with a tolerance. The system is considered to be better when the
value of FRR is smaller with the same FAR values [29]. Fingerprint has a characteris-
tic FAR of 0.001%, and FRR of 0.6% [30].
As matters currently stand, it can be identified three basic methods for comparing
fingerprint images: comparing patterns of prints, correlation comparisons and a meth-
od that uses key points - minutias.
In the algorithm of pattern comparison, the peculiarities of the structure of the pa-
pillary pattern are used directly. The image of the fingerprint obtained from the scan-
ner is divided into a large number of small particles, while the size of such cells de-
pends on the required accuracy (the smaller the size of the cell, the more accurate the
result is obtained).
The disposition of the lines in the cell is described by parameters of some sinusoi-
dal wave: the initial phase shift, the wavelength and the direction of its propagation
are determined. Accordingly, to receiving a fingerprint for comparison, it is aligned
and is reduced to the same kind as the template. Then the parameters of the wave
representations of the corresponding cells are compared.
The main advantages of this algorithm are quite high speed and low requirements
for the quality of the resulting image. The method of comparison on the pattern has
not yet become widespread because of the complexity of implementation, as well as
high requirements to the mathematical base.
It should be noted separately that in the automated identification, there are several
problems associated with the difficulty of scanning and recognizing some types of
fingerprints.
In the algorithm that uses a correlation comparison, the received fingerprint is su-
perimposed on each of the standards of the prints of the database and the calculation
of the pixel difference between the input fingerprint and the reference.
The main advantage of this method is the low requirement for the quality of the re-
ceived imprint. Disadvantages: the need for a large amount of memory to store the
database, low speed algorithm. Every time a person places his finger at different an-
gles and different places of the scanner's working area. This means that the process of
comparing its fingerprint with the standards should include a lot of iterations, each of
which the image obtained from the scanner returns at a small angle or slightly shifts
[31]. Because of the duration of the comparison procedure, especially when solving
the identification problem, the "one to many" comparison, this method is extremely
rarely used for solving identification and authentication tasks.
The algorithm of a method that uses minutias describes a template that is formed
on the basis of the fingerprint image on which the end points and branch points are
marked. When comparing the key points at the input fingerprint image are also
marked. After that, the minutias of the given imprint are compared with the templates.
By the number of concurrency points, a decision is made on the identity of the images
[32]. The advantage of this algorithm is the high speed of operation. That is why the
algorithms of this class are the most common.
To work the algorithm for comparing fingerprints from key points, high quality
images with low noise are required. Therefore, special image processing algorithms
are used to improve the quality of the fingerprint images. In particular, as a model of
noisy biometric imaging, the most commonly used normal distribution law with ran-
dom variables. In this paper, the method of taking the inverse function is used to im-
plement this model. This method is especially convenient to use in the case when the
integral law of probability distribution is given analytically and a possible analytical
take of the inverse function from it.
2 Modeling of normally distributed random variables in the
processing of biometric images
The random variable means the value, which as a result of the trial takes a certain
value, and it is unknown in advance, which is exactly [33].
According to the central limit theorem of probability theory, by adding a sufficient-
ly large number of equally distributed independent random variables, we obtain a
random variable with a normal distribution law [33, 34] (1).
F x P(X x) P( X xi ) pi . (1)
xi x xi x
Due to the addition of more than ten random variables with uniform distribution in
the interval ( 0;1) , we obtain a random variable, which with the accuracy sufficient
for most practical problems can be considered as distributed according to the normal
law [33, 34].
For the quantitative characterization of the distribution law it is convenient to use
the probability of an event X x , where x - a certain variable. The probability of
this event obviously depends on x . This dependence is given by the distribution func-
tion of a random variable X (2):
F(x) P(X x) . (2)
Properties of the distribution function are:
the distribution function F(x) does not decrease, that is, when x2 x1 the
F(x2 ) F(x1 ) inequality is performed;
F( ) 0 ;
F( ) 1 .
Knowing the law of the distribution of random variables, we can construct the dis-
tribution function by the following rule.
The function of the distribution of a random variable always is a discontinuous
step function, the jumps of which occur at points corresponding to the possible values
of the random variable, and are equal to the probabilities of these values [33, 35]. The
sum of all jumps is equal to one (Fig. 2).
Fig. 2. Bursting step function
Normal distribution law is found in nature very often, therefore, effective methods
of modeling for it are developed. The formula for the probability distribution of the
values of random variable x under the normal law has the form (3):
(x mx )2
1 2 2x
y e , (3)
x 2
where x - a random variable; y(x) - probability of acceptance of a random value of
value x ; mx - mathematical expectation; x - mean square deviation.
As you can see, a normal distribution has two parameters: the mathematical expec-
tation mx and the mean square deviation x of the value x from this mathematical
expectation.
Normalized normal distribution (Fig. 3) is called a normal distribution, which has
mx 0 and x 1 [33, 36]. With a normalized distribution, you can get any other
normal distribution with given mx and x by the formula: z mx x x .
Fig. 3. A graphical representation of the normal distribution law of a random variable x
The graph of the normal distribution law shows that in the interval x of
the graph, 68% of the distribution area is concentrated, in the interval x
95.4% of the distribution area is concentrated, and in the interval x -
99.7% of the distribution area (the "rule of three sigmas").
Consider the question of simulating random variables given by the normal distribu-
tion law. In this paper, the method of taking the inverse function will be used.
In the case of continuous random variables, their probabilistic characteristics are
determined by the distribution density. The density of the distribution of a random
variable [33, 36] X is called a function f x that (4):
f x F x , (4)
where F x is the distribution function of the quantity X .
Assume that the integral law of probability distribution F x is given to us (5):
x
F x f x dx . (5)
Then it is enough to play a random number, evenly distributed in the range from 0
to 1. Since the function F also varies in this interval, then the random event x can be
determined by taking a reciprocal function graphically or analytically: x F 1 r .
Here r - the number generated by the reference Random Number Generator (RNG)
in the range from 0 to 1, x - generated as a result a random variable. Graphically, the
essence of the method is depicted in Fig. 4, namely the probability density graphs and
the integral probability density of x .
Fig. 4. Illustration of the reverse function method for generating random events x
By the density distribution property f x 0 for all x of the interval a,b , the
function y F x increases strictly in this interval (Fig. 3). Therefore, the function
F x has an unambiguous inverse function x G y with a range of values
y 0,1 and a definition area x a,b on the interval a,b . The function
x G y , as well as the function y F x , is increasing (Fig. 5).
Fig. 5. Graphic display of the function x G y
This function also has an unambiguous reverse function on its interval of definition
0,1 . Obviously, this reverse function is y F x . This method is especially con-
venient to use in the case when the integral law of probability distribution is given
analytically and a possible analytical take of the inverse function from it.
3 Handles dactyloscopic portraits
3.1 Selection of key points in the image
Image processing is an important part in creating automated biometric identifica-
tion systems.
Usually, the image obtained with the scanner is of low quality. The quality of this
image is influenced by many factors: the strength of the finger pressure when scan-
ning, the humidity of the air, the cleanliness of the finger and the scanner itself.
Therefore, different methods of filtering are used to improve the quality of the origi-
nal image. At the stage of thinning operation, the binary image of the image of the
fingerprint is throttled to the skeleton.
The skeleton of the line is called a simple chain u,v passing near the geometric
center of the line, and for each vertex p1 there are exactly two adjacent to it vertices
p2 and p3 , thus, the vertices p2 and p3 are not adjacent.
Thinning operation is a morphological operation that brings a binary image to its
skeleton. The thickness of all lines in the skeleton has a thickness of 1-2 pixels. For
such a result, it is necessary to remove the extreme points from the black lines. The
method pulls the line into the center, without making any breaks.
After that, in the skeleton of the image is searched for minutias - key points. In
most algorithms for recognition, only two types of minutias are used: ending and
branching.
The ending is called the top of the skeleton such that for it there is exactly one ver-
tex adjacent to it. The branching is called a vertex of the skeleton, for which there are
exactly three adjacent vertices and are pairwise noncontiguous.
For each key point, its type, their coordinates in the image and the orientation are
determined.
To correctly determine the minutias, it is needed to process the image and then lead
to a special format. The image processing can take place in two scenarios. Such sce-
narios are conditional, that is, it is possible to combine them.
The first scenario:
1) calculation of orientation of lines;
2) improving the quality of the lines;
3) binaryization of the image;
4) thinning operation to the image.
Second scenario:
1) adaptive filtering, allocation of interest zone;
2) binarization, the allocation of homogeneous areas;
3) morphological treatment;
4) thinning;
5) vectorization;
6) vector post-processing.
3.2 Digital fingerprint image processing
To date, there are several fingerprint filtering algorithms.
Smoothing filter
The smoothing filter is widely used to remove noise in the image in general and in
the form of a fingerprint in particular. It consists in scanning the entire image of the
window N -dimensionality n* n and converting the intensity value for each pixel.
The new value is calculated as the arithmetic mean of the value of all the pixels that
fall into the window (6):
N
I x, y
x,y
I i, j , (6)
n2
where I i, j - the new value of the pixel intensity with coordinates i, j , I x, y -
the initial intensity value for the pixel with coordinates x, y .
Median filter
Similarly, the method of removing noise in an image is widespread. The image is
scanned by the n n dimension window, the value of the intensity of the pixels inside
each window is sorted ascending (descending); the output value is the intensity of the
pixel located in the middle of the list.
The method of spatial filtration of the image
The method of spatial filtration of the image is to realize the physical process of
absorption and reflection of light. The algorithm is implemented in several stages:
1) The input of the algorithm receives a grayscale n n . Then the threshold pro-
cessing of the fingerprint image is performed to obtain a binary image.
Let R i, j - the value of the pixel with coordinates i, j in the binary image,
then R i, j 1 with G i, j R0 , in all other cases R i, j 0 .
2) At this stage, the binary image is scanned by the n n dimension window, for
the central pixel of the window with coordinates i, j , and the reflection coefficient
is calculated, which is equal to the ratio of the number of N i, j white pixels caught
in the window to the dimension of the window (7):
N i, j
k i, j , (7)
n2
where k i, j - the reflection coefficient of the pixel with coordinates i, j .
3) Next, a new intensity value for each pixel is calculated. The new value of the in-
tensity of the pixel is equal to the product of the reflection coefficient on the maxi-
mum intensity of light (8):
I i, j k i, j I max , (8)
where I max - the maximum value of intensity, I i, j - the value of the intensity of
the pixel with coordinates i, j .
Gabor filter.
Processing of the image of a fingerprint by the given algorithm is carried out in
several stages:
1) Normalize the image. Required to set the previous mean values and deviations.
A normalized image G is defined as an image where G i, j - the value of the nor-
malized brightness of the pixel with coordinates i, j .
The normalized image is calculated based on the mean and root mean square devi-
ation of the original image, where M and VAR - the output values of the mean and
the mean square deviation, are calculated by the formulas (9) (10):
1 N 1 N 1
M I i, j ,
N 2 i 0 j 0
(9)
1 N 1 N 1
I i, j M .
2
VAR 2
(10)
N i 0 j 0
2) Orientation image is calculated from the normalized image. It is defined as an
image where O i, j - the local orientation (angle of inclination) of the projection in
the pixel with the coordinates i, j (11):
1 d x2 i, j d y2 i, j
O i, j arctg , (11)
2 2d x i, j d y i, j
where d x i, j and d y i, j - gradients of the pixel with the i, j coordinates on
the axes X and Y respectively.
3) From the normalized image, the frequency image F is calculated. Frequency
image is an image where F i, j - the local frequency of the protuberance, which is
defined as the frequency of papillary lines of the image of the fingerprint. If due to the
features of the papillary pattern, it is not possible to determine the pixel frequency,
then its frequency is defined as the average value of the frequency of adjacent blocks.
Let I - the number of pixels between two adjacent vertices of the crests in the di-
mension block W W with the center of which is a pixel with coordinates i, j ,
then the frequency in this pixel will be (12):
1
F i, j . (12)
I
4) Binaryization of the image. We will define a binary image R as an image
N N showing the i, j pixel category. The pixel may be a pixel of the hollow or
pixel of the ridge.
R i, j 1 , if G i, j R0 , in all other cases R i, j 0 where G i, j - the
threshold of masking, R0 - the intensity of the pixel of the normalized image.
5) The use of Gabor filters configured for the local orientation of the speeches, ap-
plies to the normalized input image (13):
1 x2 y2
G x, y exp 2 2 cos 2 x ,
2 x y
(13)
where x x cos y sin ; y x sin y cos ; - the orientation of
the Gabor filter, - the frequency of the sinusoidal plane wave, x2 and y2 - the
space constants of the Gaussian bypass along the axes x and y , respectively. These
constants are established and adjusted on the basis of empirical data on the operation
of the algorithm.
For the Gabor filter, you need to set up a Fourier transform, which gives the fre-
quency information contained in the signal, that is, what the content of each frequency
in the signal is. The integral is taken from to to the entire time axis. For the
Fourier transform, it is equally true whether there is a certain frequency throughout
the signal being studied, or it arose at a certain time, its contribution will still be the
same.
Fourier transform is not suitable for the analysis of nonstationary signals, with one
exception, when we are interested only in frequency information, and the time of
existence of spectral components is not important.
To correct these shortcomings Gabor's transformation can be used. Let (14):
t 2
1
ga t e 4a , (14)
2 pa
where a is a fixed parameter. The function g a is used as the time window.
Fig. 6 shows the Gabor function, which is a composition of the cosine and expo-
nentials.
Fig. 6. The function of the Gabor (3), which is a composition of the cosine function (1) and
exponent (2).
Indeed, Gabor's transformation localizes the Fourier transform around a point
t b . To construct a one-dimensional Gabor filter, we use the formula (15):
G x exp x 2 / 2 2 cos 2 x , (15)
where - the standard deviation of the Gaussian nucleus, which determines the am-
1
plitude of the function, is the frequency of oscillation, defined as , where T
T
- the period of function cos 2 x . The more is , the more gentle the form will
accept the function.
4 Modeling and analysis of local features
Consider a heuristic approach based on the method of structural and statistical
analysis. The main idea of the proposed model lies in the formation of the space of
independent attributes when recognizing images given in the form of images. To de-
scribe each source image, methods are used to search the main components of the
element (that is, the definition of structural features) and to calculate the statistical
characteristics of this image of the fingerprints.
The proposed model of operators for identifying the characteristic features of fin-
gerprint images when identifying a person includes the stage of determining the set of
fingerprint features. At this stage, a set of characteristic features of fingerprints is
formed, which are determined using both the structural method and the statistical
method of determining the characteristic features of the images. In determining the
structural features of fingerprints (for example, capillary lines of the imprint and spe-
cial points of the prints), the structural method is used, and when calculating the vari-
ous statistical characteristics of the image under consideration (for example, texture
characteristics based on statistics of the first order), the statistical method. As a result
of this stage we will get a set of features that characterize fingerprints. At the next
stage there is a selection of subsets of strongly related features. At this stage, the sys-
tem of "independent" subsets of attributes is determined. The following is a definition
of representative features in each subset of characteristic strongly related features. At
this stage, from each subset of such signs a single sign is determined and as a result of
the implementation of this stage a set of representative features is distinguished. As a
result of this stage we get a reduced space of signs, the dimension of which is much
smaller. The final step is to identify the desired features. As a result of this stage, the
best signs of fingerprints are formed.
Thus, a model of operators of the formation of the space of signs on the images of
fingerprints is constructed. In the process of solving the practical problem it is deter-
mined that the stages of formation of subsets of "independent" features, namely, the
question of determining the number of these subsets and a set of attributes on the
image of fingerprints, as well as choosing a model of recognition, are important in
solving the problem. Therefore, it is necessary to continue the study based on the
identified features. The developed model can be used in the compilation of various
software complexes, focused on solving tasks of classification of objects, given in the
form of images.
To solve the problem of identifying local features in this work it is proposed to ap-
ply a mathematical model of the salesman problem.
The mission of a salesman is important and difficult to solve. It represents the
problem of finding the shortest Hamiltonian path in a complete finite graph with N
vertices. In order to apply a mathematical device in solving a problem, it is necessary
to present it as a mathematical model. The salesman's task can be presented as a graph
using the vertices (minutias) and edges (the distance between the minutias). Let i, j -
the vertices, and ribs i, j - the paths of communication between the points. In this
case, for each of the edges you can match the criterion of the utility of the route
cij 0 .
The Hamiltonian cycle can be called a route that involves passing through each
vertex of the graph exactly once. In order to simplify the task and guarantee the exist-
ence of such a route, it is necessary that the model graph is fully connected. All
known methods for finding the exact solution include searching for a space of deci-
sions, which expands exponentially depending on N . The mission of a salesman can
be solved with heuristic, search and precise algorithms.
Exact algorithms include the algorithm of full-fledging and the method of branches
and boundaries.
The exhaustive search algorithm searches for N ! space solutions by scrolling
through all the options. The result of the algorithm is the exact solution. The disad-
vantage of this algorithm is its temporal complexity - the search space grows expo-
nentially, so when N is heuristic and search algorithms are not significantly less
used.
Experimentally, the complexity of this algorithm was evaluated as
t 0,0056·e( 1,3789·N ) [37].
The advantages of this algorithm include the possibility of parallelization and the
exact solution of the problem.
The method of branches and boundaries is the development of exhaustive search
algorithm. Its essence is to add a test of the criterion that limits the functions and pro-
ceeds from the task at which, at a certain level, you can pause the construction of this
branch of the permutation tree.
It retains all the positive properties of the exhaustive search algorithm, but never-
theless is not suitable for tasks where N is not very small. Experimentally, the com-
plexity of this algorithm was evaluated as t 0,0745·e( 0,8485·N ) [37].
In the case of use as a minimal initial solution, a solution obtained by the "greedy"
method is used. The complexity of the algorithm will be t 0,3164·e( 0,7469 · N ) [37].
The advantages of this algorithm include the possibility of parallelization and the
exact solution of the problem.
Heuristic algorithms include the method of incorporating a remote and BV-
method.
The idea of incorporating a remote method is that the minutias, which are as far
apart as possible, will never be adjacent to the chain. These two points will be the
basis for further resolution. Then again there is a vertex that is as far removed as pos-
sible from the vertices already enclosed in the chain. There is a minimum sum of the
lengths of the edges between the vertex found and the pair of adjacent vertices in the
chain, which sets the place in the chain of the found vertex. This algorithm has a line-
ar complexity, gives an approximate solution to a problem and can not be parallelized.
His temporal complexity was appreciated as
t 28,0600 1,6069·N 0,0227·N 2 [37].
The BV method is based on an analysis of the existing reference route and its op-
timization. The decision can be divided into two stages: obtaining the original refer-
ence solution and optimizing the initial solution. The initial solution is the best of all
decisions made on the basis of the "greedy" method. The second stage is to modernize
the resulting initial reference route with the help of BV modifiers, which allow to
identify non-optimal areas and convert them. This algorithm has a quadratic complex-
ity, gives an approximate solution and can be parallelized at the 2nd stage [38]. His
temporal complexity was appreciated as
t 169,40 15,5786·N 0,4104·N 2 0,0040·N 3 [37].
Search algorithms. The Genetic Algorithm and the Ant Colony System (ACS) al-
gorithm are "leaders" among search algorithms [37].
The most optimal (result / time) among search algorithms is Genetic Algorithm.
However, it also has its disadvantages associated with premature convergence (it is
not always possible to find a way out of the local minimum). Experimentally its tem-
poral complexity was estimated as t 683 42,467·N 1,0696·N 2 [37].
Ant Colony System (ACS) is the development of the Ant System (AS) algorithm.
Its main differences are:
- in the function of choosing a new point the balance between the use of accumu-
lated knowledge and the study of new possible solutions is clearly set;
- at global renewal of pheromone (at the conclusion of each iteration) its addition
occurs only to the arcs belonging to the global shortest path.
Heuristic algorithms are found much faster than the search algorithms. This is con-
nected, as a rule, with the linear organization of the method itself and allows them to
be used in those tasks, when computing time is a critical parameter. Exact methods
are little suitable for solving problems of large size (unable to solve a task in a rea-
sonable time), and search algorithms are a compromise between heuristic and precise
methods [37].
5 Conclusion
Thus, the mathematical models and operations investigated allow us to formulate a
list of unique biometric features that can be applied in user authentication systems.
Structurally, the proposed model of the biometric fingerprint authentication system
consists of the following steps.
In the first stage, it is necessary to generate normally distributed random variables.
Since the normal distribution law is encountered in nature very often, so for it effec-
tive methods of modeling have been developed. In this paper, we propose using the
method of taking the inverse function. This method is especially convenient to use in
the case when the integral law of probability distribution is given analytically and a
possible analytical take of the inverse function from it.
At the next, the second stage, it is necessary to process the data from the matrix
formed at the previous stage. Since we are only interested in key points (they will
correspond to "1" in the matrix), then at this stage the task of finding the shortest path
will be solved, that is, a chain of points, sorted by minimum distances between the
points, will be created.
In the third stage, the algorithm "Method of branches and boundaries" will be used
to solve the salesman problem. Such an optimization algorithm is one of the effective
polynomial algorithms for finding approximate solutions of the salesman problem, as
well as solving similar problems in finding routes in graphs. The general idea of the
method can be described in the example of finding the minimum of a function f(x)
on the set of valid variable x values. For the method of branches and boundaries, two
procedures are required: branching and finding the marks (boundaries). The branching
procedure consists in splitting the set of permissible variable x values into subsets of
smaller sizes. The procedure can be applied recursively. The resulting subsets form a
search tree or tree of branches and boundaries. The nodes of this tree are constructed
subsets of values of a variable x . The procedure for finding estimates is to find the
upper and lower bounds for solving the problem on a subset of admissible values.
Discrete optimization methods, in particular branches and boundaries, allow finding
optimal or approximate solutions for quite large tasks. The result of this stage is an
integer expression, which is the optimal way in the graph, with vertices of which there
are minutias.
On the last, fourth stage, the formation of a passive sequence occurs. To do this, as
one of the options, the SHA-256 hexing algorithm will be applied to the integer ex-
pression. With regard to the use of hexing during the formation of a passive sequence,
such a method requires additional research in the further development of work. Tech-
nical characteristics of the SHA-256 hex function: The length of the message digest is
256 bits, the length of the internal state is 256 (8x32) bits, the block length is 512 bits,
the iteration cycles are 64.
The scheme of the computational algorithm of the developed software implementa-
tion of the biometric fingerprint authentication system is shown in Fig. 7.
Fig. 7. Scheme of computational algorithm
The developed software performs the transformation of fingerprint images, formed
by the normal law of random variables, with subsequent transformation into a passive
sequence. Consequently, it can be provided for modeling the fingerprint authentica-
tion system in order to investigate certain properties of it, to evaluate the probability
indicators of efficiency (probabilities of the first and second kind errors), etc. [39-43].
These and other studies are a promising direction for our further scientific works.
References
1. T. Ignatenko and F. M. J. Willems, "Privacy-leakage codes for biometric authen-
tication systems," 2014 IEEE International Conference on Acoustics, Speech and
Signal Processing (ICASSP), Florence, 2014, pp. 1601-1605. doi:
10.1109/ICASSP.2014.6853868
2. A. Laghari, Waheed-ur-Rehman and Z. A. Memon, "Biometric authentication
technique using smartphone sensor," 2016 13th International Bhurban Confer-
ence on Applied Sciences and Technology (IBCAST), Islamabad, 2016, pp. 381-
384. doi: 10.1109/IBCAST.2016.7429906
3. M. Lafkih et al., "Application of new alteration attack on biometric authentication
systems," 2015 First International Conference on Anti-Cybercrime (ICACC), Ri-
yadh, 2015, pp. 1-5. doi: 10.1109/Anti-Cybercrime.2015.7351944
4. A. Grivei, "Touch based biometric authentication for Android devices," 2015 7th
International Conference on Electronics, Computers and Artificial Intelligence
(ECAI), Bucharest, 2015, pp. WSD-15-WSD-18. doi:
10.1109/ECAI.2015.7301209
5. S. Rassomakhin, A. Kuznetsov, V. Shlokin, I. Belozertsev and R. Serhiienko,
"Mathematical Model for the Probabilistic Minutia Distribution in Biometric Fin-
gerprint Images," 2018 IEEE Second International Conference on Data Stream
Mining & Processing (DSMP), Lviv, Ukraine, 2018, pp. 514-518.
DOI: 10.1109/DSMP.2018.8478496
6. L. Huixian and P. Liaojun, "A Novel Biometric-Based Authentication Scheme
with Privacy Protection," 2009 Fifth International Conference on Information As-
surance and Security, Xi'an, 2009, pp. 295-298. doi: 10.1109/IAS.2009.304
7. A. Kuznetsov, A. Kiyan, A. Uvarova, R. Serhiienko and V. Smirnov, "New Code
Based Fuzzy Extractor for Biometric Cryptography," 2018 International Scien-
tific-Practical Conference Problems of Infocommunications. Science and Tech-
nology (PIC S&T), Kharkiv, Ukraine, 2018, pp. 119-124. doi:
10.1109/INFOCOMMST.2018.8632040
8. N. Doshi and C. Patel, "A Novel Approach for Biometric Based Remote User Au-
thentication Scheme using Smart Card," 2018 International Conference on Ad-
vances in Computing, Communications and Informatics (ICACCI), Bangalore,
2018, pp. 2093-2097. doi: 10.1109/ICACCI.2018.8554825
9. D. Maltoni, D. Maio, A. K. Jain, S. Prabhakar, Handbook of Fingerprint Recogni-
tion, Springer, 2009, ISBN 978-1-84882-253-5.
10. K. Han, Z. Wang and Z. Chen, "Fingerprint Image Enhancement Method based
on Adaptive Median Filter," 2018 24th Asia-Pacific Conference on Communica-
tions (APCC), Ningbo, China, 2018, pp. 40-44. doi:
10.1109/APCC.2018.8633498
11. Jacqueline A. Speir, Jack Hietpas, "Frequency filtering to suppress background
noise in fingerprint evidence: quantifying the fidelity of digitally enhanced fin-
gerprint images", Forensic Science International, vol. 242, no. 9, pp. 94-102,
2014.
12. Matthew B. Thompson, Jason M. Tangen, Duncan J. McCarthy, "Expertise in fin-
gerprint identification", Journal of Forensic Science, vol. 58, no. 6, pp. 1519-
1530, 2013.
13. Stephen Meagher, Vladimir Dvornychenko, Michael Garris, "Characterization of
latent print ‘lights-out’ modes for automated fingerprint identification sys-
tems", Journal of Forensic Identification, vol. 64, no. 3, pp. 255-284, 2014.
14. S. Xi and W. Geng, "Fast Algorithm of Fingerprint Singularity Region Enhance-
ment," 2018 IEEE 3rd International Conference on Image, Vision and Computing
(ICIVC), Chongqing, 2018, pp. 400-404. doi: 10.1109/ICIVC.2018.8492722
15. G. Li, C. Busch and B. Yang, "A novel approach used for measuring fingerprint
orientation of arch fingerprint," 2014 37th International Convention on Infor-
mation and Communication Technology, Electronics and Microelectronics
(MIPRO), Opatija, 2014, pp. 1309-1314. doi: 10.1109/MIPRO.2014.6859770
16. K. Madhavi and B. Sreenath, "Rectification of distortion in single rolled finger-
print," 2016 International Conference on Circuits, Controls, Communications and
Computing (I4C), Bangalore, 2016, pp. 1-4. doi: 10.1109/CIMCA.2016.8053307
17. J. J. Engelsma, S. S. Arora, A. K. Jain and N. G. Paulter, "Universal 3D Wearable
Fingerprint Targets: Advancing Fingerprint Reader Evaluations," in IEEE Trans-
actions on Information Forensics and Security, vol. 13, no. 6, pp. 1564-1578,
June 2018. doi: 10.1109/TIFS.2018.2797000
18. S. P. Sandip and P. H. Zope, "Selective review of fingerprint enhancement, classi-
fication and matching techniques," 2015 IEEE Bombay Section Symposium
(IBSS), Mumbai, 2015, pp. 1-6. doi: 10.1109/IBSS.2015.7456656
19. A. A. Kuznetsov, Yu. І. Gorbenko, D. I. Prokopovych-Tkachenko, М. S. Lutsen-
ko, M. V. Pastukhov. “NIST PQC: Code-Based Cryptosystems.” Telecommunica-
tions and Radio Engineering, Volume 78, 2019, Issue 5, pp. 429-441.
DOI: 10.1615/TelecomRadEng.v78.i5.50
20. I. Gorbenko, A. Kuznetsov, V. Tymchenko, Y. Gorbenko and O. Kachko, "Exper-
imental Studies Of The Modern Symmetric Stream Ciphers," 2018 International
Scientific-Practical Conference Problems of Infocommunications. Science and
Technology (PIC S&T), Kharkiv, Ukraine, 2018, pp. 125-128. doi:
10.1109/INFOCOMMST.2018.8632058
21. M. Selvi, Aloysius George, "FBFET: Fuzzy Based Fingerprint Enhancement
Technique based on Adaptive Thresholding", 4th ICCCNT-2013, July 4-6, 2013.
22. Krasnobayev V., Kuznetsov A., Koshman S., Moroz S. (2019) Improved Method
of Determining the Alternative Set of Numbers in Residue Number System. In:
Chertov O., Mylovanov T., Kondratenko Y., Kacprzyk J., Kreinovich V., Stefa-
nuk V. (eds) Recent Developments in Data Science and Intelligent Analysis of In-
formation. ICDSIAI 2018. Advances in Intelligent Systems and Computing, vol
836. Springer, Cham, pp. 319-328, 05 August 2018. DOI: 10.1007/978-3-319-
97885-7_31
23. I. Moskovchenko, M. Pastukhov, A. Kuznetsov, T. Kuznetsova, V. Prokopenko
and V. Kropyvnytskyi, "Heuristic Methods of Hill Climbing of Cryptographic
Boolean Functions," 2018 International Scientific-Practical Conference Problems
of Infocommunications. Science and Technology (PIC S&T), Kharkiv, Ukraine,
2018, pp. 1-6. doi: 10.1109/INFOCOMMST.2018.8632017
24. Z. Shi, V. Govindaraju, "A Chaincode Based Scheme for Fingerprint Feature Ex-
traction" in Pattern Recognition Letters, Elsevier, pp. 462-468, October 2006.
25. Fingerprinting and genotyposcopy in forensic medicine. Forensic Library, 2000.
[On-line]. Internet: http://www.forens-med.ru/book.php?id=105 (in Russian)
26. Criminalistic Study of the Hands (Dattiloscopy). Principles of fingerprinting.
Online teaching materials, 2019. [On-line]. Internet:
http://pidruchniki.com/2015060965282/pravo/kriminalistichne_doslidzhennya_sli
div_ruk_daktiloskopiya (in Ukrainian)
27. Shvets V., Fesenko A. Basic biometric characteristics, modern systems and tech-
nologies of biometric authentication. Ukrainian Scientific Journal of Information
Security, 2013, vol. 19, pp. 2-103 (in Russian)
28. Rikanov A. Analysis of fingerprint authentification and verification methods, In-
formation Processing Systems, 2010, 6 (87) (in Russian)
29. ChernychenkoI.V. Separate aspects of the formation of fingerprinting until 1900,
Bulletin of criminal justice, No. 3/2005, p. 136 (in Russian)
30. V.O. Romanov, I. B.Galelyuk, P.S. Klochan. Technologies of person's authentica-
tion by biometric characteristics. Computer means, networks and systems, 2010,
No. 9, pp. 54-61 (in Russian)
31. Zaitsev V.G., Stepenko K.S. Method of Access Control on the Basis of Refrigera-
tion of Fingers. National Technical University of Ukraine "Kyiv Polytechnic
Institute", [On-line]. Internet: http://pmk.fpm.kpi.ua/arhive_2009/36-Stepenko.pdf
(in Ukrainian)
32. Moroz AO Biometric Technologies. Methods of fingerprinting. Mathematical
Machines and Systems, 2011, pp. 3 - 64 (in Ukrainian)
33. V.S. Pugachev. Probability Theory and Mathematical Statistics for Engineers,
Elsevier, 1984, 468 p. doi:10.1016/c2013-0-06054-9.
34. Simulation of random variables as a systematic simulation simulation process.
2012. [On-line]. Internet: http://ecolib.com.ua/article.php?book=17&article=1540
(in Ukrainian)
35. V.V. Vyhman, A.A. Yakimenko. Biometric systems of control and access control
in the tasks of information protection: educational method. Manual. Novosibirsk:
Publishing house of the National Technical University, 2016, p. 10 p (in Russian)
36. Normal distribution. Training materials on-line. 2019.
http://pidruchniki.com/18421120/statistika/normalniy_rozpodil (in Ukrainian)
37. Boroznov V.O. Investigation of the salesman's task solution. Computer overclock-
ing and computing technology. Vestnik AGTU. Sir: Office, Computing and In-
formatics, 2009, pp. 2 - 147 (in Russian)
38. Boroznov V. O. Investigation of the heuristic method for solving the problem of
traveling salesman. Electronic Journal "Investigated in Russia", 2008, pp. 322-328
(in Russian)
39. L. Wei, Z. Cong and Y. Zhiwei, "Fingerprint Based Identity Authentication for
Online Examination System," 2010 Second International Workshop on Education
Technology and Computer Science, Wuhan, 2010, pp. 307-310. doi:
10.1109/ETCS.2010.409
40. A. Kuznetsov, A. Kiian, M. Lutsenko, I. Chepurko and S. Kavun, "Code-based
cryptosystems from NIST PQC," 2018 IEEE 9th International Conference on De-
pendable Systems, Services and Technologies (DESSERT), Kyiv, Ukraine, 2018,
pp. 282-287. DOI: 10.1109/DESSERT.2018.8409145
41. G. V. Kumar, K. Prasanth, S. G. Raj and S. Sarathi, "Fingerprint based authentica-
tion system with keystroke dynamics for realistic user," Second International
Conference on Current Trends In Engineering and Technology - ICCTET 2014,
Coimbatore, 2014, pp. 206-209. doi: 10.1109/ICCTET.2014.6966288
42. A. Kuznetsov, A. Pushkar'ov, N. Kiyan and T. Kuznetsova, "Code-based electron-
ic digital signature," 2018 IEEE 9th International Conference on Dependable Sys-
tems, Services and Technologies (DESSERT), Kyiv, Ukraine, 2018, pp. 331-336.
DOI: 10.1109/DESSERT.2018.8409154
43. A. S. Shinde and V. Bendre, "An Embedded Fingerprint Authentication Sys-
tem," 2015 International Conference on Computing Communication Control and
Automation, Pune, 2015, pp. 205-208. doi: 10.1109/ICCUBEA.2015.45