Abstract
Superior to single-factor authentication, multi-factor authentication (MFA) provides enhanced security by requiring at least two factors to authenticate an entity. It has been studied extensively in recent years and has been applied to various fields. However, there is no adaptive and quantified method to evaluate the dynamic threats coming from different attacks. In this paper, we introduce fuzzy dominating set to model the multiple factors of privacy-preserving identities, and propose an adaptive MFA combinatorial model to achieve adaptive choosing one or multiple privacy-preserving identities to authenticate the user. Moreover, we propose an integer linear programming for solving the Fuzzy Domination Model, and propose a greedy algorithm for Fuzzy Domination (GFD) and a primal dual greedy algorithm for Fuzzy Domination (PDFD) based on this integer linear programming. This work will reduce the gap between dynamic MFA and its practice applications. Finally, the effectiveness and efficiency of both algorithms in MFA are analyzed and experimental results demonstrate that PDFD is comparatively efficient and effective for solving instances with moderate orders.
Introduction
With the development of Internet, security threats are becoming more and more serious. Single-factor authentication (SFA) can not satisfy the security requirements of many application environments. Multi-factor authentication (MFA) provides enhanced security by requiring at least two factors to authenticate an entity. If one of the multiple factors has been compromised by an adversary, the probability of compromising the other factor is low. Based on this idea, MFA has been studied extensively in recent years and has been applied to various application fields. The authentication factors include some physical object the user has, such as a USB key and a smart card; or some secrets the user knows, such as a password and a PIN code; or some physical characteristic of the user, such as fingerprint and facial features. Although the existing MFA schemes can select more than one factor to authenticate an entity, they can not select these factors adaptively according to the security of each factor. An organization may need a higher level security for some high-risk situations and one can trade off security level and user convenience to adaptively adjust some authentication factors. Further, once some elements of the multiple factors have been compromised, how to adjust the authentication factors adaptively is highlysignificant.
For example, you can login your online account on some bank, but it needs you to provide the other authentication factors, such as a USB key when you carry out transfer on this account. This kind of MFA can be called adaptive, contextual or risk-based MFA. The advantages of using adaptive MFA include enhancing security, dynamic nature and adaptive applications. A good adaptive MFA strategy can trade off the risks of compromised factors, productivity, user experience etc. when determining MFA requirements. One can customize different authentication factors based on different applications dynamically. The MFA is more effective when combined with a single sign-on (SSO) solution, which removes multiple passwords and further improves the user experience. Especially, with the widespread usage of mobile devices and phones, there are more and more security threats. The good adaptive MFA scheme is urgently needed. However, identity hijacking attack still exists in MFA. To conquer these weaknesses, an adaptive MFA combinatorial model is necessary to resist these attacks, such as identity hijacking, identity theft, phishing and social engineering, among others. The adaptive MFA combinatorial model facilitates choosing one or multiple privacy-preserving identities to authenticate the user according to his/her specific characteristics, such as age, gender, occupation, and hobbies etc.
In this paper, the fuzzy graph domination model is proposed to model the adaptive MFA schemes. The contributions of this paper are summarized as follows. An adaptive MFA combinatorial model is proposed to achieve adaptive choosing one or multiple privacy-preserving identities to authenticate the user. We propose to utilize the fuzzy graph domination model for adaptive multi-factor combination authentication. The dominating set is introduced to model the multiple factors of privacy-preserving identities. We design a weighted vertex-edge dominating set to solve this weighted domination problem on fuzzy graphs. Two algorithms are proposed to solve the proposed model, and the experiments demonstrated the feasibility and efficiency of them. We also compare the proposed two algorithms and found that GFD is comparatively efficient and effective for solving instances with moderate orders.
Related work
In order to resist the identity theft threat in single-factor authentication, multi-factor authentication (MFA) is proposed. However, identity hijacking attack still exists in MFA. An adaptive MFA can adjust the authentication factors according to external environment and practical application, therefore an adaptive MFA combinatorial model is necessary to resist these attacks, such as identity hijacking, identity theft, phishing and social engineering, among others.
In 2000, Hwang et al. [11] proposed an authentication scheme using smart cards. It is based on the ElGamal’s public key cryptosystem and does not need to maintain a password table. However, this scheme is vulnerable to impersonation attack [3]. In 2002, Lee et al. [13] proposed a fingerprint-based authentication scheme using smart cards. It is also based on ElGamal’s public key cryptosystem and does not need to maintain a password table. By adding one more secret key than Hwang and Li, the scheme can resist message replaying and impersonation attacks. However, Chang et al. [4] pointed out that their scheme has security flaw that some legitimate users can conspire to forge valid identities and passwords for successfully passing the system authentication. Limbasiya et al. [14] presented a state-of-art survey on three-factor, two-factor, and one-factor with different attacks those are identified till date on them. They discussed distinct attacks and how such an attack makes a system vulnerable. They also gave taxonomy about authentication attacks based on essential parameters, impression on the users, and countermeasures to prevent attacks. Roy et al. [18] proposed to use biometric characteristics to authenticate end users for remote IoT based services.
Barrero et al. [9] proposed a general framework for multi-biometric template protection based on Bloom filters. They gave a statistical methodology for estimating Bloom filter extraction parameters and a weighted feature level fusion to enhance privacy while preserving accuracy. They also illustrated experimental evaluation on carried out on face, iris, fingerprint and fingervein over two totally different sets of publicly available databases. In addition, they showed how the weighted feature level fusion preserves the accuracy of the unprotected score level fusion, while it adds privacy protection to the system. The other research works on MFA can refer to literatures [1, 20].
However, the works described above are not adaptive and they can not adjust the authentication factors according to different scenarios dynamically. An adaptive MFA scheme can adjust the authentication factors according the outside risks dynamically. It is important for current complicated and insecure network environment. In 2014, A. K. Nag and D. Dasgupta [15] proposed a framework to select authentication factors adaptively according to users’ operating environment. But they did not give a scheme for this framework. Following this work, they presented a framework [16] for authenticating a user through a subset of available authentication modalities along with their several features (authentication factors) in time-varying operating environments (devices, media and surrounding conditions) on a regular basis. In 2016, Dasgupta et al. [6] further detailed the framework proposed. They presented a formulation to calculate trustworthy values of different authentication factors.
There is little work on adaptive MFA, and there is no quantified method to evaluate the dynamic threat coming from different attacks. The adaptive MFA combinatorial model facilitates choosing one or multiple privacy-preserving identities to authenticate the user according to his/her specific characteristics, such as age, gender, occupation, and hobbies etc. Therefore, how to adaptively select these multiple factors according to different application scenarios and the security of each factor is a very meaningful research work. Different from the above works, we propose to utilize the fuzzy graph domination model for adaptive multi-factor combination authentication. The dominating set is introduced to model the multiple factors of privacy-preserving identities. We design a weighted vertex-edge dominating set to solve the weighted domination problem on fuzzy graphs. By utilizing the probabilities of attacks and importance, the weighted vertex-edge dominating policy facilitates selecting an optimal combinatorial factors to achieve authentication. At least the probability of one identity of the user that has not leaked is greater than a given threshold. The detailed modeling procedure and algorithms are presented, and the effectiveness and efficiency are analyzed.
Preliminaries and Notations
In this section, we introduce some definitions in fuzzy graphs and the concept of domination in fuzzy graph.
Let V be a finite nonempty set and E be the collection of some two-element subsets of V. The ordered pair (V, E) is called a graph and denoted by G = (V, E). The elements in V and E are called vertices and edges of G, respectively.
For a fuzzy graph F = (V, σ, μ), the underlying crisp graph of F is denoted by F* = (V, σ*, μ*), where σ* = {v ∈ V|σ (v) >0} and μ* = {xy|μ (x, y) >0}. An edge e = xy of a fuzzy graph is called a strong edge if μ (x, y) = min {σ (x) , σ (y)}. For any S ⊆ V, the fuzzy cardinality of S is defined to be ∑v∈Sσ (v).
Now we introduce the definitions of dominating set and domination number in graphs and in fuzzy graphs.
The following definitions are based on the Model FuzzyDomination described in Section 4:
Modeling MFA using Fuzzy Graph Domination
In this section, we introduce the multi-factor combination authentication problem and its transformation via Fuzzy Domination Model.
Assume that an authentication system contains n authentication factors A1, A2, …, A
n
and the cost for authenticating A
i
is c
i
, where i = 1, 2, …, n. Let P (A
i
) be the leakage probability of A
i
, and so the security probability of A
i
is denoted by
Now we construct a graph G with the vertex set {A1, A2, ⋯ , A
n
} and each vertex having the weight
Model Fuzzy Domination:
min:
s.t.: x i + ∑i≠jσ (A j ) μ (A i , A j ) x j ≥ α i ,
∀i ∈ {1, 2, ⋯ , n}
x i ∈ {0, 1}, 1 ≤ i ≤ n
α i ∈ [0, 1], 1 ≤ i ≤ n
σ (A i ) ∈ [0, 1], 1 ≤ i ≤ n
μ (A i , A j ) ∈ [0, 1], 1 ≤ i < j ≤ n
•If α i = α for some α ∈ [0, 1], we say the model FuzzyDomination is a constant model.
•If α i = σ (A i ) for each i ∈ {1, 2, …, n}, we say the model FuzzyDomination is an adaptive model.
An example.
In order to solve the proposed Fuzzy Domination Model, we propose two approximate algorithms. One is the primal dual greedy algorithm for solving a kind of integer linear program, which can be found in [7]. Assume G is a fuzzy graph with vertex set v1, …, v
n
,
choose r ∈ J
k
such that
k ← k + 1;
Algorithm 1 returns a vector
In order to improve the performance of approximations, we propose the following greedy algorithm GreedyFuzzyDomination (called GFD). In such a way, staring with initial fuzzy dominating set C of G, we then repeatedly remove vertices from C until its element can not be removed. During the process, we select a vertex v that maximizes S v .
GreedyFuzzyDomination(G,α);
α w = α;
find k such that S k = max {S v |v ∈ C};
D ← D ∪ {k};
C ← C - {k};
Performance evaluation
In this section we test the property of fuzzy domination of graphs. We first test the fuzzy domination number with different values and numbers of vertices on Pentium G630 (R) Intel processor with CPU 2.70GHz and memory 4GB. The tested graphs are generated from complete graphs with the expectation of each edge weight to be 0.5. With the order from 20 to 140, the software Gurobi 7.5.2 is able to find optimum solution to the model FuzzyDomination within several seconds. Fig. 2 shows their results with constant value α increasing and Fig. 3 shows those with n increasing. It can be seen that in the parameter of the adaptive model, the fuzzy domination number become very small, and this is because there exist some vertices with small weight σ (A i ) even the expectation of each edge weight is 0.5.

Comparison for different α and n of n-vertex fuzzy graphs.

Comparison for different α and n of n-vertex fuzzy graphs.
We test the performance of the proposed static model with ILP solver Gurobi 7.5.2, PDFD and GFD algorithms on random graphs with 10000 vertices, and the computational results are presented in Table 1. First, we generate complete graphs with the expectation each edge weight 0.5. As for PDFD, it consumes too much time to obtain a solution. Moreover, the results from PDFD are much worse than those from GFD. The Gurobi 7.5.2 runs on the instances with α from 0.1 to 0.9 with maximum time limit 696.7 seconds. From Table 1, we have that GFD has a very good efficiency and the result is very close to the one from Gurobi. Especially, the instance with α = 0.2, it produces a fuzzy dominating set of order 97, which is better than that from Gurobi with time limit 592.4 seconds. Note that GFD is a polynomial algorithm on n and the general ILP problem is NP-complete, we have that GFD is a very good choice to solve instances with this scale.
Comparison results with ILP, GFD and PDFD algorithms
Multi-factor authentication has been studied extensively, but there is no adaptive and quantified method to evaluate the dynamic threat coming from different attacks. An adaptive MFA scheme can adjust the authentication factors according the outside risks dynamically.
In this paper, we propose a fuzzy graph theory model and apply it to the field of information security. More precisely, we introduce fuzzy dominating set to model the multiple factors of privacy-preserving identities, and propose an adaptive MFA combinatorial model to achieve adaptive choosing one or multiple privacy-preserving identities to authenticate the user. We also propose algorithms PDFD and GFD for solving the proposed model, and the detailed modeling procedure and algorithms are presented, and the effectiveness and efficiency are analyzed. Experimental results indicate that the polynomial time algorithm GFD is comparatively efficient and effective for solving instances with moderate orders.
By utilizing the probabilities of attacks and importance, the weighted vertex-edge fuzzy dominating policy facilitates selecting optimal combinatorial factors to achieve authentication. Note that the probabilities of attacks are very important data set of this model, how to obtain these probabilities is an interesting and challenging avenue of further research.
Footnotes
Acknowledgment
This work is supported by the National Key Research and Development Program under grant 2017YFB0802300, the National Natural Science Foundation of China under grants 61602118, 61802158, 61672050, 61572010 and 11361008, Natural Science Foundation of Guangdong Province under grant 2018A0303130115, Fujian Normal University Innovative Research Team under grant IRTL1207, Natural Science Foundation of Fujian Province under grant 2017J01738.
