Open AccessLetter

On Secret Sharing with Newton’s Polynomial for Multi-Factor Authentication

Sergey Bezzateev

Vadim Davydov

and

Aleksandr Ometov

^3,*

Technologies of Information Security, Saint Petersburg State University of Aerospace Instrumentation, 190000 St. Petersburg, Russia

Faculty of Secure Information Technologies, ITMO University, 197101 St. Petersburg, Russia

Tampere University, 33720 Tampere, Finland

Author to whom correspondence should be addressed.

Cryptography 2020, 4(4), 34; https://doi.org/10.3390/cryptography4040034

Submission received: 1 September 2020 / Revised: 17 November 2020 / Accepted: 26 November 2020 / Published: 1 December 2020

(This article belongs to the Special Issue Security, Privacy and Trust in the Next Generation Distributed Systems and Networks)

Download Versions Notes

Abstract

Security and access control aspects are becoming more and more essential to consider during the design of various systems and the tremendous growth of digitization. One of the related key building blocks in this regard is, essentially, the authentication process. Conventional schemes based on one or two authenticating factors can no longer provide the required levels of flexibility and pro-activity of the access procedures, thus, the concept of threshold-based multi-factor authentication (MFA) was introduced, in which some of the factors may be missing, but the access can still be granted. In turn, secret sharing is a crucial component of the MFA systems, with Shamir’s schema being the most widely known one historically and based on Lagrange interpolation polynomial. Interestingly, the older Newtonian approach to the same problem is almost left without attention. At the same time, it means that the coefficients of the existing secret polynomial do not need to be re-calculated while adding a new factor. Therefore, this paper investigates this known property of Newton’s interpolation formula, illustrating that, in specific MFA cases, the whole system may become more flexible and scalable, which is essential for future authentication systems.

Keywords:

authentication; interpolation; Netwon’s polynomial; secret sharing

1. Introduction

Today, the digital evolution, along with information and communications technology (ITC) developments, already engross most areas of modern society. Nonetheless, to enable the secure and private operation of such various co-existing systems, we must develop different information security instruments. One of those corresponds to the system’s authentication with its user being either a machine or a human being [1,2,3].

Standalone growth of authentication systems, from ownership factor (key, access card, etc.) towards more complicated knowledge (pin, password, etc.) and biometric-based authentication (fingerprint, facial recognition, gait, etc.), led to the appearance of multi-factor authentication (MFA) (also known as multimodal authentication in the biometry field) systems [4,5]. MFA utilizes an intelligent combination of factors of different types and has already become a strong use case for car-sharing and banking systems [6,7]. Here, each involved factor-provider (physical token, secret code, biometrics, etc.) in the system has some secret share derived from the access key. When the key is restored based on a threshold number of collected shares, the authentication is considered a success. The technology behind has its roots in the field of secret sharing.

One of the most famous secret sharing techniques is the well-known Shamir’s secret sharing scheme [8]. In the classical version of the scheme, the Lagrange interpolation polynomial is used to recover the secret, but the addition of new key shares may be a complicated task.

Many modern systems require a proactive/continuous operation, which is of specific interest in biometry-related authentication [9]. In the example of car-sharing systems that generally are expected to utilize biometry-based factors if one of the authentication sensors breaks, it is necessary to quickly add a new one with an increase (or modification) in the scheme’s threshold. That procedure may be challenging to execute using the Lagrange polynomial when dividing the secret due to the peculiarities of constructing the polynomial. Broadly speaking, the entire system should be reinitialized.

The paper provides an investigation of a known property of the Newton interpolation formula for MFA systems. Namely, using Newton’s interpolation formula instead of the Lagrange interpolation formula with Shamir’s secret sharing scheme is more beneficial. That is mainly since the entire system can be made more flexible and scalable since the coefficients of the existing secret polynomial do not need to be re-calculated [10,11]. Instead of the Lagrange polynomial, its use allows for quick changes of the threshold value, thereby greatly facilitating and simplifying the process of flexible system changes and prompt additions of new factors.

The paper is organized as follows. Section 2 provides a brief history of interpolation formulas, along with descriptions of Lagrange’s and Newton’s polynomials. Further, Section 3 describes the processes of obtaining the Lagrange formula from Newton’s formula and provides the inverse transformation. Next, Section 4 is devoted directly to secret sharing schemes based on the interpolation formulas. Further, Section 5 elaborates on Newton’s polynomial potential for secret sharing and an example of such use. Significantly, Section 6 provides some examples of polynomials’ utilization for MFA systems and shows the proof of Newton’s polynomial property for the sake of completeness. The last section concludes the paper.

2. Overview of Interpolation Polynomials

Generally, interpolation is a method of finding a new solution using a predefined set of results (values) of the function. The unknown value could be defined as a point using this formula. Considering a linear interpolation formula, it may be used to find a new value from two (or another number) of specified points. If we compare such a method with Lagrange’s interpolation formula, a set of points would be required, and the Lagrange method will be used to find the new value [10].

As an example, consider a linear interpolation formula

y - y_{1} = \frac{y_{2} - y_{1}}{x_{2} - x_{1}} x - x_{1},

(1)

where points (

x_{1}, y_{1}

) and (

x_{2}, y_{2}

) are known.

Note, there is a significant difference between interpolation and unambiguous reconstruction of a polynomial from its values at a certain number of known points. Finding an interpolation function has many solutions since infinitely many curves can be drawn through given points; each of those will be a graph of a function for which all interpolation conditions are satisfied.

Next, we show the general interpolation scheme for a polynomial in one variable. Consider t points and the following polynomial of at most

(t - 1)

degree with

a_{0}, \dots, a_{t - 1} \in Z

a (x) = a_{0} + \sum_{j = 1}^{t - 1} a_{j} x^{j} .

(2)

Thus, it could be represented as follows.

a (x) = a_{0} + a_{1} x + \dots + a_{t - 1} x^{t - 1},

(3)

where

a_{0}, a_{1}, . . ., a_{t - 1}

are unknown.

Since t points are already known (

{(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{t}, y_{t})}

), we arrive at t linear independent equations with t unknown variables:

\begin{matrix} y_{1} & = a_{0} + a_{1} x_{1} + a_{2} x_{1}^{2} + \dots + a_{t - 1} x_{1}^{t - 1}, \\ y_{2} & = a_{0} + a_{1} x_{2} + a_{2} x_{2}^{2} + \dots + a_{t - 1} x_{2}^{t - 1}, \\ \dots \\ y_{t} & = a_{0} + a_{1} x_{t} + a_{2} x_{t}^{2} + \dots + a_{t - 1} x_{t}^{t - 1} . \end{matrix}

(4)

By rewriting in a matrix form, we arrive at

(\begin{matrix} y_{1} \\ y_{2} \\ ⋮ \\ y_{t} \end{matrix}) = (\begin{matrix} 1 & x_{1} & \dots & x_{1}^{t - 1} \\ 1 & x_{2} & \dots & x_{2}^{t - 1} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & x_{t} & \dots & x_{t}^{t - 1} \end{matrix}) \cdot (\begin{matrix} a_{0} \\ a_{1} \\ ⋮ \\ a_{t - 1} \end{matrix}),

(5)

i.e., a Vandermonde matrix, and there are well-known techniques to find its determinant. Finally, it is not difficult to add a new point after finding values

(a_{0}, a_{1}, \dots, a_{t - 1})

2.1. Newton’s Interpolation Formula

Scientists began to reevaluate the power of interpolation very long ago. The first mentions date back to about 300 BC when Babylonian astronomers used interpolation to fill in the gaps in the planetary celestial coordinate tables known at that time and recorded the data on special tablets. In this work, we will not go deep into the history of the emergence of interpolation formulas since there were no major discoveries before the era of the scientific revolution starting in 1611.

As early as in the 17th century, scientists used an interpolation formula equivalent to the Gregory–Newton formula for the approximation of the function

f (x)

and finally gave the linear interpolation.

In 1675, Isaac Newton began his fundamental work on the classical theory of interpolation. In 1711, his “Methodus Differentialis” met the world [12]. Newton described his discoveries that became fundamental and are used to this day in many real systems.

Almost 80 years later, Edward Waring published an alternative representation of Newton’s general formula for arbitrary interval data in 1779. The method did not require the computation of separated differences, although this formula is attributed to another scientist, Joseph-Louis Lagrange, who proposed the same formula 16 years later [12].

The Newton formula is an interpolation polynomial designed for a given set of data points. It is also called the Newton interpolation polynomial with separation of differences since the polynomial coefficients are calculated using the method of division of Newton differences [13].

For example,

(n + 1)

points are defined as

(x_{0}, y_{0}), \dots (x_{j}, y_{j}), \dots, (x_{n}, y_{n})

. The values defined by

x_{j} (j = 0, \dots, n)

are interpolation points. The values defined by

y_{j} (j = 0, \dots, n)

are interpolation values. For the interpolation of function f, the interpolation values are determined as

y_{j} = f (x_{j}), \forall j = 0, \dots, n .

(6)

The polynomial of Newton’s basis is defined as follows

n_{i} (x) = \prod_{j = 1}^{i - 1} (x - x_{j}),

(7)

where

i = 1, \dots, n

and

n_{0} (x) = 1

The Newton interpolation polynomial is defined as

P_{n} (x) = \sum_{i = 0}^{n} K_{i} n_{i} (x) = K_{0} + K_{1} (x - x_{0}) + K_{2} (x - x_{0}) (x - x_{1}) + \dots + K_{n} (x - x_{0}) \dots (x - x_{n - 1}),

(8)

where

P_{n} (x_{j}) = f (x_{j}), \forall_{j} = 0, \dots, n

The Newton interpolation polynomial of degree n,

P_{n} (x)

, estimated by

x_{0}

, is

\begin{matrix} P_{n} (x_{0}) = \sum_{i = 0}^{n} K_{i} n_{i} (x_{0}) = a_{0} = f (x_{0}) = f [x_{0}], \end{matrix}

(9)

\begin{matrix} P_{n} (x_{j}) = f (x_{j}), \forall j = 0, \dots, n, \end{matrix}

(10)

where

f [x_{0}]

is a zero order divided difference.

The Newton interpolation polynomial of degree n,

P_{n} (x)

, estimated by

x_{1}

, is

\begin{matrix} P_{n} (x_{1}) = \sum_{i = 0}^{n} K_{i} n_{i} (x_{1}) = K_{0} + K_{1} (x_{1} - x_{0}) = f [x_{0}] + K_{1} (x_{1} - x_{0}) = f [x_{1}] . \end{matrix}

(11)

Therefore,

K_{1} = \frac{f [x_{1}] - f [x_{0}]}{x_{1} - x_{0}} = f [x_{0}, x_{1}],

(12)

where

f [x_{0}, x_{1}]

is the 1-st order divided difference.

Then,

K_{i}

in general form could be written as

K_{i} = \frac{f [x_{1}, \dots, x_{i}] - f [x_{0}, \dots, x_{(i - 1)}]}{x_{i} - x_{0}},

(13)

where

f [x_{1}, \dots, x_{i}]

is the n-th order divided difference.

2.2. Lagrange Interpolation Formula

Even though Waring published an alternative representation of Newton’s general formula for arbitrary interval data first (which did not require the computation of separated differences), this finding was regrettably attributed to another scientist, Joseph-Louis Lagrange, who proposed the same formula 16 years later [12].

The Lagrange formula is traditionally represented as a polynomial, where for

(n + 1)

pairs of numbers

(x_{0}, y_{0}), (x_{1}, y_{1}), \dots, (x_{n}, y_{n}),

where

x_{i} \neq x_{j}

for all

i \neq j

, there is only one a polynomial

L (x)

of degree n, for which

L (x_{j}) = y_{j}

for all

j = 0, \dots, n

L (x) = \sum_{i = 0}^{n} y_{i} l_{i} (x),

(14)

where

l_{i} (x) = \prod_{j = 0, j \neq i}^{n} \frac{x - x_{j}}{x_{i} - x_{j}}

are basic polynomials with the following properties:

$deg l_{i} (x) = n$ ;
$l_{i} (x_{i}) = 1$ ;
$l_{i} (x_{j}) = 0 if j \neq i$ .

3. Interpolation Formulas Relation

3.1. Derivation of Lagrange’s Formula from Newton’s Formula

The Lagrange interpolation formula can be obtained directly from Newton’s formula. Let us consider this transition in more detail.

From (8), we obtain

\begin{matrix} f (x_{i}) = P_{n} (x_{i}) = \sum_{j = 0}^{n} K_{j} n_{j} (x_{i}) . \end{matrix}

(15)

Therefore, we can use the following interpolation formula by multiplying each

P_{n} (x_{i})

by coefficient

l_{i} (x)

\begin{matrix} f (x) = \sum_{i = 0}^{n} \sum_{j = 0}^{i} K_{j} n_{j} (x_{i}) l_{i} (x), \end{matrix}

(16)

\begin{matrix} l_{i} (x) = \frac{(x - x_{0}) (x - x_{1}) \dots (x - x_{i - 1}) (x - x_{i + 1}) \dots (x - x_{n})}{(x_{i} - x_{0}) (x_{i} - x_{1}) \dots (x_{i} - x_{i - 1}) (x_{i} - x_{i + 1}) \dots (x_{i} - x_{n})} . \end{matrix}

(17)

3.2. Derivation of Newton’s Formula from Lagrange’s Formula

Newton’s interpolation formula also can be obtained directly from the Lagrange formula.

We consider polynomials

P_{0} (x) = f (x_{0}), P_{1} (x), \dots P_{n - 1} (x)

. In the classical form, Lagrange polynomial is written as

P_{n} (x) = \sum_{i = 0}^{n} y_{i} \prod_{k = 0, k \neq i}^{n} \frac{x - x_{k}}{x_{i} - x_{k}} .

(18)

Let us do a trick and represent the polynomial as the following sum

P_{n} (x) = P_{0} (x) + \sum_{i = 1}^{n} (P_{i} (x) - P_{i - 1} (x)) .

(19)

From the interpolation definition, we get that

P_{j - 1} (x_{k}) = P_{j} (x_{k}) = f (x_{k})

(20)

for

k = 0, 1 \dots, j - 1

and

j = 1, 2, \dots, n

, which means that

P_{j} (x) - P_{j - 1} (x)

is an algebraic polynomial with the zeroes in

x_{0}, x_{1}, \dots, x_{j - 1}

Then,

P_{j} (x) - P_{j - 1} (x) = A_{j} (x_{j} - x_{0}) (x_{j} - x_{1}) \dots (x_{j} - x_{j - 1}),

(21)

where

A_{j}

is some number. This number could be found knowing the fact

P_{j} (x_{j}) = f (x_{j})

A_{j} = \frac{f (x_{j}) - P_{j - 1} (x_{j})}{(x_{j} - x_{0}) \dots (x_{j} - x_{j - 1})} .

(22)

Substituting the value of

P_{j - 1}

using Lagrange interpolation formula, we arrive at

A_{j} = \sum_{k = 0}^{l} \frac{f (x_{k})}{(x_{k} - x_{0}) \dots (x_{k} - x_{k - 1}) (x_{k} - x_{k + 1}) \dots (x_{k} - x_{j})} .

(23)

Here, it can be observed that this value is the divided difference of the order j:

A_{j} = f (x_{0}, x_{1}, \dots x_{j})

Expressing the rest of the polynomials recursively, we arrive at

\begin{matrix} P_{n} (x) = & K_{0} + K_{1} (x - x_{0}) + K_{2} (x - x_{0}) (x - x_{1}) + \dots + K_{n} (x - x_{0}) \dots (x - x_{n - 1}) \\ = & K_{0} + \sum_{i = 0}^{n} K_{i} \prod_{j = 0}^{i - 1} (x - x_{j}) . \end{matrix}

(24)

Thus, we have shown the possibility of obtaining one interpolation formula from another using intermediate, auxiliary elements of the corresponding interpolation formulas.

3.3. Additional Notes on the Comparison of the Polynomials

Finally, while speaking about the Lagrange vs. Newton comparison in terms of the number of calculations required to compute the coefficients, it should be pointed out that the Lagrange coefficient’s calculation requires

n^{2}

additions and multiplications. For Newton, it is only

n^{2} / 2

[14], which indicates a benefit of the utilization of the latter one, especially for resource-constrained devices.

Interestingly, the authors of [15] highlight the possibility of using pre-calculated coefficients in the Lagrange formula in the case of a fixed, previously known group of users (devices, factors, parameters, etc.) with the corresponding identifiers (denoted

x_{i}

in this work and as

u_{i}

in [15]). Under this condition, one can pre-calculate the coefficients for the Lagrange interpolation function, significantly reducing computation when assembling a secret. However, when the values of the identifiers (

x_{i}

u_{i}

) of the participants of the secret assembly are not known in advance, or a new factor/parameter appears (as in the following example of the MFA operation,) such a simplification of calculations for the Lagrange formula, unfortunately, cannot be performed.

4. Shamir’s Secret Sharing Scheme

The first

(k, n)

threshold secret sharing scheme was proposed in 1979 by Shamir [16] and Blackley [17], who worked independently of each other. The basic principle of these schemes is sharing the secret between the participants in the information exchange when everyone has only a part of the key. The secret can be recovered only if a specified number of key shares are combined.

Any schema of this type, as a rule, consists of secret sharing and secret recovery phases [18]. For example, let D be a secret data. The scheme’s purpose would be to divide D into n shares

D_{1} \dots D_{n}

with the following conditions met:

D is easily calculated if k or more of its shares are known;
D cannot be calculated if $k - 1$ or fewer of its parts are known.

Shamir’s secret sharing scheme is based on the Lagrange interpolation formula and is still one of today’s most popular schemes. Besides, there are schemes based on the Chinese remainder theorem (CRT) for integer rings proposed by Mignotte [19] and by Asmuth and Bloom [20], and on error-correcting codes proposed by McEliece and Sarwate using non-systematic Reed–Solomon codes [21].

The following subsection will describe the main phases of Shamir’s secret sharing scheme in more detail.

4.1. Secret Sharing

Let us denote a prime number

p > D

. This number is known to all participants in the exchange. Let us construct a polynomial from

F_{p} [x]

of degree

l - 1

with random coefficients and

a_{0} = D

L (x) = a_{l - 1} x^{l - 1} + a_{l - 2} x^{l - 2} + \dots + a_{1} x + D .

(25)

The secret shares are calculated using

\begin{matrix} D_{1} & = L (1), \\ D_{2} & = L (2), \\ \dots \\ D_{n} & = L (n) . \end{matrix}

(26)

As a result, each exchange participant receives his share of the secret and its number.

4.2. Recovering a Secret

To recover the secret, the Lagrange interpolation polynomial is used. Here,

(l + 1)

pairs of numbers

(x_{0}, y_{0}), (x_{1}, y_{1}), \dots, (x_{l}, y_{l})

with

x_{i} \neq x_{j}

for all

i \neq j

and there is one and only one polynomial

L (x)

of the degree l, for which

L (x_{j}) = y_{j}

for all

j = 0, \dots, l

The following equations are used for the calculation:

\begin{matrix} D = L (0) = \sum_{i = 0}^{l} y_{i} l_{i} (0) mod p, \\ l_{i} (0) = {(- 1)}^{l} \prod_{j = 0, j \neq i}^{l} \frac{x_{j}}{x_{i} - x_{j}} mod p . \end{matrix}

(27)

The above formulas have the following properties:

Polynomial degree n;
$l_{i} (x_{i}) = 1$ ;
$l_{i} (x_{i}) = 0$ if $j \neq i$ .

As shown earlier, Shamir’s secret sharing scheme is based on the Lagrange interpolation polynomial. With an increase in the degree of a polynomial, and accordingly, an increase in the number of interpolation nodes required to restore it, it is necessary to rebuild the entire polynomial, which is inconvenient when using MFA. Let us demonstrate this statement with an example.

Suppose we have a car-sharing system based on the Lagrange polynomial, and currently, three factors are used to authenticate the driver. However, the owner wants to add a new factor (a new immobilizer or a pin code). At the current moment, the system has already calculated the values

l_{0}, l_{1} \dots l_{3}

and calculated the final polynomial

L (x)

. When adding a new factor, the product in the formulas for calculating

l_{i}

must be counted again since n has changed. Thus, it is necessary to recalculate all the values

l_{0}, l_{1}, l_{2}

, and

l_{3}

, and calculate the new value of

l_{4}

, which is quite costly computation-wise. In order to solve this problem, one can use another representation, namely, the Newton polynomial.

5. Newton’s Polynomial in Secret Sharing Schemes

Newton’s interpolation polynomial of degree n can be represented as

P_{n} (x) = \sum_{i = 0}^{n} K_{i} n_{i} (x) = f [x_{0}] + \sum_{i = 1}^{n} f [x_{0}, \dots, x_{i}] n_{i} (x) .

(28)

Note that increasing the degree of the polynomial by one while the values of the polynomial at the previously known points remain unchanged will require adding the

(n + 1)

-th interpolation node, and accordingly, calculating the coefficient

K_{n + 1} = \frac{f [x_{1}, \dots, x_{n + 1}] - f [x_{0}, \dots, x_{n}]}{x_{n + 1} - x_{0}},

(29)

as well as

K_{n + 1} (x - x_{0}) \dots (x - x_{n})

values. Moreover, since the polynomial values at previously known points do not change, for the remaining degrees of the polynomial they do not change. Basically, there is no need to recalculate the previous coefficients; one only need add a new one.

>The recalculated Newton interpolation polynomial of degree

n + 1

can be, thus, represented as

P_{n + 1} (x) = \sum_{i = 0}^{n + 1} K_{i} n_{i} (x) = f [x_{0}] + \sum_{i = 1}^{n + 1} F [x_{0}, \dots, x_{i}] n_{i} (x) = P_{n} (x) + f [x_{0}, \dots, x_{n + 1}] n_{n + 1} (x) .

(30)

In the Lagrange interpolation polynomial, if it is necessary to increase the degree of the polynomial we have to recalculate the values of the polynomial at the previous known points and the corresponding addition of one more

(n + 1)

-th point. All interpolation coefficients must be recalculated since each term of the polynomial takes a single correct value, and when a new point is added, the values of all terms of the polynomial need to be aligned according to the new point.

6. Utilization Examples

6.1. Use Case Description

Let us assume to use an MFA system as a combination with biometric factors, a password, and a physical key. At first, let this system has two biometric factors: fingerprint and facial recognition.

These factors will be represented as two points with the coordinates

(x_{1}, y_{1}), (x_{2}, y_{2})

. By using Lagrange and Newton interpolation formulas, we calculate a function (in this particular case, linear function)

f (x)

, which goes through two these points. Then, we choose password and key values as some points on this curve

(x_{k e y}, y_{k e y}), (x_{p a s s}, y_{p a s s})

. Finally, we have a curve

f (x), deg f (x) = 1

with four factors that are represented as points

(x_{1}, y_{1}), (x_{2}, y_{2}), (x_{k e y}, y_{k e y}),

and

(x_{p a s s}, y_{p a s s})

on it.

It becomes straightforward to construct a threshold system

k = 2

from

n = 4

by using such a curve.

Assume, we wish to add to this MFA system one more biometric factor represented as the point with the coordinates

(x_{3}, y_{3})

. In this case, we have to calculate new function

ϕ (x)

, which goes through three points

(x_{1}, y_{1}), (x_{2}, y_{2}),

and

(x_{3}, y_{3})

associated with the corresponding three biometric factors. Therefore, we should replace the function

f (x)

with function

ϕ (x)

. After that, in the same way as in the previous case, we choose password and key values as some points

(x_{k e y^{'}}, y_{k e y^{'}}), (x_{p a s s^{'}},

and

y_{p a s s^{'}})

on this curve.

Finally, we have a curve

ϕ (x), deg ϕ (x) = 2

with five factors which are represented as points

(x_{1}, y_{1}), (x_{2}, y_{2}), (x_{3}, y_{3}), (x_{k e y^{'}}, y_{k e y^{'}}),

and

(x_{p a s s^{'}}, y_{p a s s^{'}})

in it.

Using this curve allows us to construct a threshold system

k = 3

from

n = 5

Now, we will resolve this case in terms of Lagrange and Newton interpolation formulas.

To construct a new curve associated with the function

ϕ (x), deg (ϕ (x)) = 2

, we should use two previous known points

(x_{1}, y_{1}), (x_{2}, y_{2})

and one new point

(x_{3}, y_{3})

. Using Lagrange interpolation formula, it is necessary to change the polynomial, and thereby all basis polynomials must be recalculated. In Newton’s polynomial form, there is an advantage that only the last term must be found to obtain the new polynomial. Next, we show some simple examples of adding one new biometric factor using two variants of polynomials.

6.2. Lagrange Interpolation Example

This section shows a simple example of how to add a new point using a Lagrange interpolation formula.

At first, let us assume that there are two known points

(x_{1}, y_{1}), (x_{2}, y_{2})

associated with two biometric factors, and it is required to find the function

f (x)

, which goes through the corresponding two points.

x	$x_{1}$	$x_{2}$
	−1	0
$f (x)$	$y_{1}$	$y_{2}$
	4	2

To find the function

f (x)

, we use the Lagrange interpolation formula

f (x) = \frac{(x - x_{2})}{(x_{1} - x_{2})} \cdot y_{1} + \frac{(x - x_{1})}{(x_{2} - x_{1})} \cdot y_{2} .

(31)

Then, we simply calculate

f (x)

f (x) = \frac{(x - 0)}{(- 1 - 0)} \cdot 4 + \frac{(x + 1)}{(0 + 1)} \cdot 2 = - 4 x + 2 x + 2 = - 2 x + 2 .

(32)

If we add a third biometric factor as a point

(x_{3}, y_{3})

on the second step, we obtain the following.

x	$x_{1}$	$x_{2}$	$x_{3}$
	−1	0	1
$f (x)$	$y_{1}$	$y_{2}$	$y_{3}$
	4	2	−2

To find a new function

ϕ (x)

with degree 2, we should recalculate all coefficients in the following way.

ϕ (x) = \frac{(x - x_{2}) (x - x_{3})}{(x_{1} - x_{2}) (x_{1} - x_{3})} \cdot y_{1} + \frac{(x - x_{1}) (x - x_{3})}{(x_{2} - x_{1}) (x_{2} - x_{3})} \cdot y_{2} + \frac{(x - x_{1}) (x - x_{2})}{(x_{3} - x_{1}) (x_{3} - x_{2})} \cdot y_{3} .

(33)

Therefore, we obtain

\begin{matrix} ϕ (x) & = \frac{(x - 0) (x - 1)}{((- 1) - 0) ((- 1) - 1)} \cdot 4 + \frac{(x - (- 1)) (x - 1)}{(0 - (- 1)) (0 - 1)} \cdot 2 + \frac{(x - (- 1)) (x - 0)}{((1) - (- 1)) ((1 - 0)} \cdot (- 2) \\ = - x^{2} - 3 x + 2 . \end{matrix}

(34)

Here, we demonstrated how to find a new interpolation function using the dataset extended by one biometric factor. In this case, all basis polynomials must be recalculated.

6.3. Newton Interpolation Example

This subsection presents a simple example of how to add a point

(x_{3}, y_{3}) = (1, - 2)

using Newton interpolation formula. The same example as in the previous subsection is used.

x	$x_{1}$	$x_{2}$
	−1	0
$f (x)$	$y_{1}$	$y_{2}$
	4	2

To find the function

f (x)

, we use Newton interpolation formula

\begin{matrix} f (x) = K_{0} + K_{1} (x - x_{1}) . \end{matrix}

(35)

Let us find divided differences:

\begin{matrix} K_{0} = y_{1} = 4, \end{matrix}

(36)

\begin{matrix} K_{1} = f [x_{1}, x_{2}] = \frac{y_{2} - y_{1}}{x_{2} - x_{1}} = \frac{- 2}{1} = - 2 . \end{matrix}

(37)

Next, we calculate the function

f (x)

\begin{matrix} f (x) = 4 + (- 2) \cdot (x + 1) = - 2 x + 2 . \end{matrix}

(38)

If we add a third biometric factor as a point

(x_{3}, y_{3})

at the second step, we obtain the following.

x	$x_{1}$	$x_{2}$	$x_{3}$
	−1	0	1
$f (x)$	$y_{1}$	$y_{2}$	$y_{3}$
	4	2	−2

Then, we only have to find a new divided difference instead of full recalculation as

\begin{matrix} f [x_{1}, x_{3}] = \frac{y_{3} - y_{1}}{x_{3} - x_{1}} = \frac{- 6}{2} = - 3, \end{matrix}

(39)

\begin{matrix} K_{2} = \frac{f [x_{1}, x_{3}] - K_{1}}{x_{3} - x_{2}} = \frac{(- 3) + 2}{1} = - 1, \end{matrix}

(40)

and next, we just need to calculate the polynomial

\begin{matrix} ϕ (x) = K_{0} + K_{1} (x - x_{1}) + K_{2} (x - x_{1}) (x - x_{2}) = f (x) + K_{2} (x - x_{1}) (x - x_{2}), \end{matrix}

(41)

\begin{matrix} ϕ (x) = - 2 x + 2 - (x + 1) x = - 2 x + 2 - x^{2} - x = - x^{2} - 3 x + 2 . \end{matrix}

(42)

This simple example clearly shows the features of two interpolation algorithms. The presented calculations demonstrate the fundamental difference between the Newton formula and the Lagrange formula: when the number of interpolation points increases in the Newton formula, it is unnecessary to recalculate all the previous components of the interpolation formula.

7. Conclusions

The evolution of the authentication schemes towards multi-factor ones leads to the need to redesign the access procedures to become more proactive with regard to potentially missing factors (due to sensor failure or the human factor). In this paper, we propose to use the Newton polynomial instead of the Lagrange polynomial in secret sharing schemes. The resulting flexible scheme can quickly change the number and composition of factors, which means that secret sharing schemes based on Newton’s interpolation polynomial are potentially suitable for organizing MFA and can be recommended for use in various modern systems that require a timely reaction to the changes.

Comparing the Newton and Lagrange interpolation formulas, some significant advantages of using it should be highlighted. Firstly, Newton’s polynomial application allows for faster execution time compared to Lagrange’s interpolation, since the latter requires divisions, whereas Newton’s polynomial does not use divisions at all. Secondly, the coefficients in the Newton form can be found somewhat faster than in the Lagrange form (

n^{2} / 2

versus

n^{2}

), since the use of Newton’s polynomial does not require full recalculation of the polynomial. Finally, it was shown that one could substantially reduce complexity using Newton’s polynomial instead of the Lagrange one when necessary to increase the number of interpolation points in secret sharing schemes.

Author Contributions

Conceptualization, S.B. and V.D.; methodology, S.B.; validation, A.O.; formal analysis, A.O.; investigation, S.B. and V.D.; writing—original draft preparation, V.D.; writing—review and editing, S.B. and A.O.; visualization, A.O.; supervision, S.B.; project administration, A.O. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Conflicts of Interest

The authors declare no conflict of interest.

References

Wang, D.; Wang, P.; Wang, C. Efficient Multi-Factor User Authentication Protocol with Forward Secrecy for Real-Time Data Access in WSNs. ACM Trans. Cyber Phys. Syst. 2020, 4, 1–26. [Google Scholar] [CrossRef] [Green Version]
Ometov, A.; Petrov, V.; Bezzateev, S.; Andreev, S.; Koucheryavy, Y.; Gerla, M. Challenges of Multi-Factor Authentication for Securing Advanced IoT Applications. IEEE Netw. 2019, 33, 82–88. [Google Scholar] [CrossRef]
Das, S.; Wang, B.; Tingle, Z.; Camp, L.J. Evaluating User Perception of Multi-Factor Authentication: A Systematic Review. arXiv 2019, arXiv:1908.05901. [Google Scholar]
Ometov, A.; Bezzateev, S.; Mäkitalo, N.; Andreev, S.; Mikkonen, T.; Koucheryavy, Y. Multi-Factor Authentication: A Survey. Cryptography 2018, 2, 1. [Google Scholar] [CrossRef] [Green Version]
Kumar, K.; Farik, M. A Review of Multimodal Biometric Authentication Systems. Int. J. Sci. Technol. Res. 2016, 5, 5–9. [Google Scholar] [CrossRef]
Genovese, A.; Munoz, E.; Piuri, V.; Scotti, F. Advanced Biometric Technologies: Emerging Scenarios and Research Trends. In From Database to Cyber Security; Springer: Berlin/Heidelberg, Germany, 2018; pp. 324–352. [Google Scholar]
Park, S.H.; Kim, J.H.; Jun, M.S. A Design of Secure Authentication Method with Bio-Information in the Car Sharing Environment. In Advances in Computer Science and Ubiquitous Computing; Springer: Berlin/Heidelberg, Germany, 2016; pp. 205–210. [Google Scholar]
Shamir, A. How to Share a Secret. Commun. ACM 1979, 22, 612–613. [Google Scholar] [CrossRef]
Alotaibi, S.; Alruban, A.; Furnell, S.; Clarke, N.L. A Novel Behaviour Profiling Approach to Continuous Authentication for Mobile Applications. In Proceedings of the International Conference on Information Systems Security and Privacy, Prague, Czech Republic, 23–25 February 2019; pp. 246–251. [Google Scholar]
Kogan, N.; Tassa, T. Improved Efficiency for Revocation Schemes via Newton Interpolation. ACM Trans. Inf. Syst. Secur. (TISSEC) 2006, 9, 461–486. [Google Scholar] [CrossRef] [Green Version]
Stavros, D.; Iraklis, S. Complexity Comparison of Lagrange and Newton Polynomial based Revocation Schemes. In Proceedings of the 2nd Conference on European Computing Conference, Athens, Greece, 25–27 September 2007; World Scientific and Engineering Academy and Society (WSEAS): Athens, Greece, 2008; pp. 44–53. [Google Scholar]
Meijering, E. A Chronology of Interpolation: From Ancient Astronomy to Modern Signal and Image Processing. Proc. IEEE 2002, 90, 319–342. [Google Scholar] [CrossRef] [Green Version]
Sebah, P.; Gourdon, X. Newton’s Method and High Order Iterations. Numbers Comput. 2001, 1, 10. [Google Scholar]
Werner, W. Polynomial Interpolation: Lagrange versus Newton. Math. Comput. 1984, 43, 205–217. [Google Scholar] [CrossRef]
Naor, M.; Pinkas, B. Efficient Trace and Revoke Schemes. In Proceedings of the International Conference on Financial Cryptography, Anguilla, UK, 21–24 February 2000; Springer: Berlin/Heidelberg, Germany, 2000; pp. 1–20. [Google Scholar]
O’Gorman, L. Comparing Passwords, Tokens, and Biometrics for User Authentication. Proc. IEEE 2003, 91, 2021–2040. [Google Scholar] [CrossRef]
Blakley, G.R. Safeguarding Cryptographic Keys. In Proceedings of the International Workshop on Managing Requirements Knowledge (MARK), New York, NY, USA, 4–7 June 1979; IEEE: Piscataway, NJ, USA, 1979; pp. 313–318. [Google Scholar]
Kaya, K.; Selçuk, A.A. Secret Sharing Extensions based on the Chinese Remainder Theorem. IACR Cryptol. ePrint Arch. 2010, 2010, 96. [Google Scholar]
Mignotte, M. How to Share a Secret. In Workshop on Cryptography; Springer: Berlin/Heidelberg, Germany, 1982; pp. 371–375. [Google Scholar]
Asmuth, C.; Bloom, J. A Modular Approach to Key Safeguarding. IEEE Trans. Inf. Theory 1983, 29, 208–210. [Google Scholar] [CrossRef]
McEliece, R.J.; Sarwate, D.V. On Sharing Secrets and Reed-Solomon Codes. Commun. ACM 1981, 24, 583–584. [Google Scholar] [CrossRef]

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

© 2020 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Bezzateev, S.; Davydov, V.; Ometov, A. On Secret Sharing with Newton’s Polynomial for Multi-Factor Authentication. Cryptography 2020, 4, 34. https://doi.org/10.3390/cryptography4040034

AMA Style

Bezzateev S, Davydov V, Ometov A. On Secret Sharing with Newton’s Polynomial for Multi-Factor Authentication. Cryptography. 2020; 4(4):34. https://doi.org/10.3390/cryptography4040034

Chicago/Turabian Style

Bezzateev, Sergey, Vadim Davydov, and Aleksandr Ometov. 2020. "On Secret Sharing with Newton’s Polynomial for Multi-Factor Authentication" Cryptography 4, no. 4: 34. https://doi.org/10.3390/cryptography4040034

APA Style

Bezzateev, S., Davydov, V., & Ometov, A. (2020). On Secret Sharing with Newton’s Polynomial for Multi-Factor Authentication. Cryptography, 4(4), 34. https://doi.org/10.3390/cryptography4040034

Article Menu

On Secret Sharing with Newton’s Polynomial for Multi-Factor Authentication

Abstract

1. Introduction

2. Overview of Interpolation Polynomials

2.1. Newton’s Interpolation Formula

2.2. Lagrange Interpolation Formula

3. Interpolation Formulas Relation

3.1. Derivation of Lagrange’s Formula from Newton’s Formula

3.2. Derivation of Newton’s Formula from Lagrange’s Formula

3.3. Additional Notes on the Comparison of the Polynomials

4. Shamir’s Secret Sharing Scheme

4.1. Secret Sharing

4.2. Recovering a Secret

5. Newton’s Polynomial in Secret Sharing Schemes

6. Utilization Examples

6.1. Use Case Description

6.2. Lagrange Interpolation Example

6.3. Newton Interpolation Example

7. Conclusions

Author Contributions

Funding

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI