Soma Datta

Nabendu Chaki
email: nabendu@ieee.org

Sankhayan Choudhury
email: sankhayan@gmail.com

Information Density Based Image Binarization for Text Document Containing Graphics

Keywords: Iterative partitioning, NTSC color format, Wiener filter, Binarization, Entropy

In this work, a new clustering based binarization technique has been proposed. Clustering is done depending on the information density of the input image. Here input image is considered as a set of text, images as foreground and some random noises, marks of ink, spots of oil, etc. in the background. It is often quite difficult to separate the foreground from the background based on existing binarization technique. The existing methods offer good result if the input image contains only text. Experimental results indicate that this method is particularly good for degraded text document containing graphic images as well. USC-SIPI database is used for testing phase. It is compared with iterative partitioning, Otsu's method for seven different metrics.

Introduction

It is very important to maintain the documents and the legacy of the document. To fulfill these purpose document image processing takes a vital role. Document image binarization is usually performed in optical character recognition (OCR) [START_REF] Thillou | Segmentation-based binarization for color degraded images[END_REF][START_REF] Gonzalez | Digital image processing[END_REF] and image searching. This involves handwriting recognition, extracting logos and pictures from a graphical image. The main purpose of document image processing [START_REF] Namboodiri | Document structure and layout analysis, digital document processing[END_REF] is reduction of paper usage, easy access to the documents with lowest storage cost. At this point the most challenging task is to segment the region of interest (ROI) for further analysis. The simplest method for image segmentation [START_REF] Dinan | Document image processing system[END_REF] is thresholding based binarization which is also an essential technique in enhancement and biomedical image analysis. The output of this process is a binary image [START_REF] Jaimes | Segmentation and automatic descreening of scanned documents[END_REF]. Though researchers work upon document image binarization for several years, the thresholding of compound document images still remains a challenging task due to its sensitivity to noise, illumination, variable intensity and sometimes insufficient contrast. It has been observed that some of the existing methods [START_REF] Ghosh | Blood smear analyzer for white blood cell counting: A hybrid microscopic image analyzing technique[END_REF][START_REF] Parker | Thresholding using an illumination model[END_REF][START_REF] Chen | A fast two-dimensional entropic thresholding algorithm[END_REF][START_REF] Yanowitz | A new method for image segmentation[END_REF][START_REF] Ghosh | Medical aid for automatic detection of malaria[END_REF] offer very good result for text document. However, the performance degrades when a degraded text document contains some graphical images in it. We refer this type of document as compound document in the rest of this paper. In this research work, we aim to devise a new segmentation methodology that would be good for the compound documents. We separate the entire image into three regions as the background, only text region and the graphical image. Our proposed method keeps a good balance both for text and graphics in the degraded compound documents. The proposed binarization method is based on cluster density information. It consists of six phases. These are noise removal with image normalization, entropy calculation, fuzzy c mean clustering, segmenting of each region based on the clustering output, applying local threshold based binarization and finally integrating the segmented region. Each of these phases is described detail in the design methodology section.

Survey on Existing Techniques

Document image binarization has drawn lot of attention in the machine vision research community. Some of the highly cited methods are discussed in this section in a nutshell. Parker et al. proposed a method based on Shen-Castan edge detector to identify object pixels [START_REF] Parker | Thresholding using an illumination model[END_REF]. This method creates a surface using moving least squares method used to threshold images. Chen et al. proposed enhanced speed entropic threshold selection algorithm [START_REF] Chen | A fast two-dimensional entropic thresholding algorithm[END_REF]. This method works upon the selection of global threshold value using maximin optimization procedure. O'Gorman proposed a global approach based on the measurement of information on local connectivity. The threshold values are incorporated at intensity level. Thus this method has advan-tages of local as well as global adaptive approaches. Liu et al. proposed a method based on grey scale and run length histogram. This method carefully handles noisy and complex background problems. Chang et al. worked upon stroke connectivity preservation issues for graphical images [START_REF] Yang | Adaptive thresholding algorithm and its hardware implementation[END_REF]. Their proposed algorithm is able to eliminate the background noise and enhancement of grey levels of texts. This method is used to extract the strokes from low level density as well as darker background. S. Shaikh, et al. [START_REF] Shaikh | A new image binarization method using iterative partitioning[END_REF] proposed iterative partitioning method. In this method, entire input image is divided into four equal sub images if the number of peaks is greater than two in the input image. This process will continue until the sub image contains less than two histogram peaks. This binarization method is offering good result for very old, faded, stained documented images but fails for medical image segmentation. In Otsu's [START_REF] Otsu | A threshold selection method from gray-level histograms[END_REF] method, the thresholding is based on the class variance criterion and the histogram of the input image. This method segments the image into two classes, so that the total variance of different classes is maximized. Otsu's binarization technique produces good result for graphical images; however it can't properly binaries the old spotted document.

Design of New Information Density Based Binarization Technique

Image Acquisition and Enhancement

The design methodology follows a pipelined approach starting with image acquisition and ending with binarization. Histogram based Otsu's method may provide satisfactory result when documented images are clear. However in reality the old and multiple times photocopied documents are not so good. Hence these documents are often not binarized properly using Otsu's method.

Otsu's method is a histogram based generalized binarization. Information density based segmentation is not done here. The algorithm assumes that the input image contains foreground and background pixels and it then calculates the optimal threshold that separates the two regions. USC-SIPI database [START_REF] California | university of southern california[END_REF] is used for testing phase. The quality and size of the original image is not changed. Instead of this database we have also tested our proposed method with some sample documented scanned images that consists of text and graphical images. Image enhancement improves the visual quality of the input image for further processing techniques. The qualities of some images are not so good. Most of the image contains speckle noise, salt and pepper noises and some random noises. Here Wiener tilter is used to remove that kind of mixture noises. This filter is a linear filter to remove additive noise and blurring of the images. It offers good result to reduce the mean square error rate. These filters are often applied in the frequency domain. The corresponding output image is W (f 1 , f 2 ) as follows:

W (f 1 , f 2 ) = H * (f 1 , f 2 )S x (f 1 , f 2 ) |H(f 1 , f 2 )| 2 * S x (f 1 , f 2 ) + S y (f 1 , f 2 ) (1)
Here, S x (f 1 , f 2 ) and S y (f 1 , f 2 ) represent the power spectrum of the original image and the noisy image respectively and H(f 1 , f 2 ) means the blurred filter. The Wiener filter performs deconvolution during minimization of least square error as follows,

e 2 = E{(f -f ) 2 } (2)
Here E is the mean value and f is the un-degraded image.

Convert input color image into gray scale image

Color of a pixel is represented as the combination of chrominance and luminance. Chrominance is the color components of the input image and luminance is the intensity. This intensity is calculated as the weighted means of red, green and blue (RGB) component. Now image is in three dimensional that requires a massive computational time. Hence RGB images are converted into gray scale image using NTSC color format [START_REF] Gonzalez | Digital image processing[END_REF].

Intensity value normalization

Intensity normalization is very important towards handling the variable light intensity. Basically it is a method that maps the intensity values as per prerequisite. Normalization transforms an n dimensional grayscale image represented as, Step 1: Read input image and find its size. 2: Find the cumulative distribution function as Q(x) = x i=1 h(i) where x is the gray scale value and h is the image histogram. 3: Calculate new gray scale values using

Img = {X ⊆ R n } → {M in, M
h(i) = round( Q(1) -Qmin X * Y -Qmin * (L -1)) ( 3
)
where Qmin is the shortest value of the cumulative distribution function. X, Y represents the number of columns and rows of the input image and L is the number of gray levels that are used. 4: New image is created by replacing original gray values by the newly calculated gray values and compare this with the original. 5: Stop

Find the most informative regions

Input images may contain the actual information along with some distortion due to oil ink etc. Hence, it is very much important to segment the actual informative region. In order to find the most informative region, texture based information have been used. Among many texture properties, entropy is used to do the needful. Entropy [START_REF] Jain | Fundamentals of digital image processing[END_REF][START_REF] Abutaleb | Automatic thresholding of gray-level pictures using twodimensional entropy[END_REF] refers to the disorder, uncertainty or randomness of the given dataset. The following algorithm is used to find the most informative regions. The covariance or probability of randomness is higher in the text area but it is less in non text area.

Algorithm 2: ROI segmentation

Assumptions: Input image should be in gray scale. Input: Gray scale image. Output: Only most wanted region.

Step 1: Find the sub image (row1 -n/2 to row2 + n/2 and col1 -n/2 to col1 + n/2) where row1 and col1 is two variable and n denotes the row, column of the sub-window. 2: Repeat step1 for all row1 is in between row1 -n/2 to row1 + n/2 and for all col1 is in between col1 -n/2 to col1 + n/2 . 3: Repeat step 4 to 6 for all sub images and store the entropy value in row1 and col1. 4: Calculate histogram of n*n sub image and store the result in a vector hist. 5: Normalized histogram is stored at hist normalized hist normalized = hist/(n * n) 6: Find all the points at hist normalized where value is 0 and replace that value by1. 7: Calculate entropy element and store them into cee vector cee(i) = hist normalized(i) * log 2 normalized(i), i is used to denote index. 8: Add all entries from cee(i) and multiply the result by (-1) 9: Stop

Segment individual non-overlapped regions.

The next step is to segment the individual non-overlapped regions. Clustering method [START_REF] Datta | Person identification technique using rgb based dental images[END_REF][START_REF] Han | An improved ant colony algorithm for fuzzy clustering in image segmentation[END_REF] has been applied to find out different cluster seed points that are shown in Fig4.a. Here three cluster points have been found. Now our target is to segment each individual clustering region as shown in Fig2.b, Fig2.c and Fig2.d. The next step is to segment each of the regions.

Single Region Set = {P : P isasubsetof Region point Set} Elements of set P form a vector containing row and column number of a pixel. P contains the coordinates of all pixels of a single region. There is no common element between any two elements of Single Region Set. P 1 ∪ P 2 ∪ P 3 ∪ P n = Region point set Where P 1 , P 2 , , P n are all elements of Single Region Set, n is the total no of elements in Single Region Set . P i ∩ P j = φwhere P i , P j are any two elements of Single Region Set and value of i,

Algorithm 3: Clustering Segmentation

Assumptions: Let E = {e1, e2, e3..., en}is the set of entropy values in entropy matrix. C = {C1, C2, C3} is the set of initial cluster centers. Input: Gray scale image. Output: Based on entropy calculation the image is segmented into three groups.

Step 1: Initial cluster centers are {C1, C2, C2} i.e. c = 3 where, C1 is the average entropy value of most informative region in the document. C2 is the average entropy value of less informative region. C3 is the average entropy value of in between region. 2: Calculate the fuzzy membership 'Fij ' using

Fij = 1 e=3 k=1 ( D ij D ik ) (2/m-l) (4)
Where, Fij are the elements of F M matrix (fuzzy membership matrix), Dij is the Euclidean distance between i th object and j th cluster centre. D ik is the Euclidean distance be-tween i th object and j th cluster center, m is a constant. 3: New fuzzy centers N ew Fj is calculated using,

N ew Fj = ( ( n i=1 (Fij) m Xi) ( n i=1 (Fij) m ) )∀j = 1, 2, ......c (5)
4: Repeat Step 2 and 3 until F M (k + 1)F M (k) < β Where, 'k', 'β' are the iteration step and termination criterion between [0, 1] respec-tively. F M (k) = (Fij)n * c is a fuzzy membership matrix after k th iteration and F M (k + 1) is used to denote after (k + 1) th iteration. j is the objective function. 5: Find all the points which belong to the most informative region cluster. This cluster has C1 center and contains the pixel position of the image of most informative region. 6: Stop

Algorithm 4: Segment region

Input: The binary matrix that does not contain any false contours. Output: The coordinates of each contour.

Step 1: Find any coordinate from input binary matrix (region matrix), containing value 1 and this point is called seed point. 2: Find all other coordinates of the binary matrix that belongs to the same contour with the seed point. It is implemented using the stack, 8-connectivity and 4 connectivity properties. 3: The points obtained from step2 are the points that represent a single contour.

These points are sent to the next phase for further processing. 4: Repeat step2 to step3 using a newly found seed value that belongs to a separate region. This iterative process will continue until all disjoint regions are extracted.

5: Stop

After applying segment each region algorithm, the wanted regions are segmented. Now apply global binarization technique on the segmented regions. Threshold value for binarization is calculated as follows [START_REF] Chaki | Exploring image binarization techniques[END_REF].

Performance Analysis

For performance analysis some degraded document images are used that are collected from multiple sites. Our method is tested on the USC-SIPI database arbitrarily for experimental verification purpose. The results are shown in Fig 3. In this work, we have compared seven different metrics in between Otsu's method, iterative partitioning and our proposed method. The seven metrics are recall, precision, F measure, PERR or pixel error rate, MSE or mean squared error, SNR or signal to noise ratio and peak signal to noise (PSNR) [START_REF] Shaikh | A new image binarization method using iterative partitioning[END_REF][START_REF] Su | Binarization of historical document images using the local maximum and minimum[END_REF]. Theoretically recall is the probability of a relevant document is retrieved during search and precision is the probability of whether a retrieved document is relevant or not. However in both of these methods, some text region has been lost. In our method, none of the text region has lost and only the black shirt comes as white due to no change of entropy of that region. Iterative partitioning offers poor result in both the cases as it partitions the image into four sub block based on the histogram. The Table1 shows the average performance analysis between Otsu's method, iterative partitioning and our proposed method. Performance analysis table shows that the probability of retrieval of relevant document is 99.5% and the precision is 96.45% which are quite good. On the other hand misclassification rate is also less than Otsu's method and iterative partitioning. Our method performs much better than the other two methods in the presence of Gaussian and random noises. It makes obvious that the informa-

Conclusion

In this research work, we have proposed a new method using clustering technique of a gray scale image. Here random noises, pepper and salt noises, Gaussian noises are removed. The proposed method has been tested on the benchmarked image data-base. This method easily separates the compound document and produce better result than Otsu's method, iterative partitioning. The proposed method also offers good result for the above said evaluation metrics. However, experimental observation finds limitation of the proposed method towards binarization of X-ray type of medical images. The work may be extended to address this aspect.

Fig. 1 :

 1 Fig. 1: Block diagram of proposed method

Algorithm 1 :

 1 ax}. Image Img consist the intensity values in between Min and Max. This image is converted into a new image,Img = {X ⊆ R n } → {new M in, . . . ., new M ax}. New image Img consist the intensity values in between new Min and new Max. Normalization is done by using the histogram. The following steps are made for normalization. Intensity Value Normalization Assumptions: Input image should be in gray scale. Input: Gray scale image. Output: Scaled intensity image.

Fig. 2 :

 2 Fig. 2: Fig2.a: After applying clustering technique Fig2.b: First most informative region whose cluster centre is 74.1604 Fig2.c: Second most informative region whose cluster centre is 167.7177 Fig2.d: Third most informative region whose cluster centre is 225.7846

Algorithm 5 : 1 : 2 :

 512 BinarizationInput: Gray scale image. Output: binary image.Step Initial threshold value T = (min intensity + max intensity)/2 Partition the image into two regions, R1 consists of value (pixels)< T and R2 consists of value(pixels) > T. 3: For each region, calculate the average intensity value I1 and I2. 4: Preserve the old threshold value and update the threshold value with the new threshold value that is obtained from step3. 5: Continue this iterative process from step2 to step4 until the absolute difference between preserved value and new threshold value is less than tolerance parameter e. 6: Stop

Fig. 3 :

 3 Fig. 3: Comparative Study

Fig. 4 :

 4 Fig. 4: Average performance graph on 7 matrices for the said methods

Table 1 :

 1 Performance Analysis

	Performance mea-surement Otsu Binarization Iterative Our proposed
	Matrices	technique	Parti-tioning	method
	Recall	82.96	99.44	99.50
	Precision	97.87	95.88	96.45
	F measure	89.82	97.62	98.89
	PERR	14.17	3.69	3.91
	MSE	9.32	2.39	2.10
	SNR	31.12	36.08	35.55
	PSNR	57.20	62.13	63.67


Zenon A Sosnowski
email: z.sosnowski@pb.edu.pl

Jarosław S Walijewski

Fuzzy Dempster-Shafer Modelling and Decision Rules

Keywords: Dempster-Shafer Theory, Fuzzy Modelling, Fuzzy Decision Rules 1

In this study, we discuss the use of Dempster-Shafer theory as a wellrounded algorithmic vehicle in the construction of fuzzy decision rules. The concept of fuzzy granulation realized via fuzzy clustering is aimed at the discretization of continuous attributes. Detailed experimental studies are presented concerning well-known medical data sets available on the Web.

Introduction

Fuzzy modeling is regarded to be one of the possible classification architecture of machine learning and data mining. There have been a significant number of studies devoted to generating fuzzy decision rules from sample cases or examples. These include attempts to extend many classical machine learning methods to learn fuzzy rules. One very popular approach is decision trees [START_REF] Quinlann | Induction of decision trees[END_REF]. Since the inception of this concept, it has been extended for the construction and interpretation of more advanced decision trees [START_REF] Chiang | Integration of fuzzy classifiers with decision trees[END_REF][START_REF] Hayashi | Generation of fuzzy decision trees by fuzzy ID3 with adjusting mechanism of AND/OR operators[END_REF][START_REF] Ichihashi | Nero-fuzzy ID3: a method of inducing fuzzy decision trees with linear programming for maximizing entropy and an algebraic method for incremental learning[END_REF][START_REF] Janikow | Fuzzy decision trees: issues and methods[END_REF][START_REF] Pedrycz | C-fuzzy decision trees[END_REF][START_REF] Umano | Generation of fuzzy decision trees by fuzzy ID3 algorithm and its application to diagnosis by gas in oil[END_REF][START_REF] Weber | Fuzzy ID3: A class of methods for automatic knowledge acquisition[END_REF][START_REF] Yun | The new approach on fuzzy decision trees[END_REF]. Although the decision trees based methods can extract a set of fuzzy rules which works well, a problem is that the lack of backtracking in splitting the node leads to lower learning accuracy comparing to other machine learning methods. Another widely used machine learning method is artificial neural network. In recent years enormous work has been done in attempt to combine the advantages of neural network and fuzzy sets [START_REF] Zs | Survey on Neuro Fuzzy Systems and their Applications in Technical Diagnostics[END_REF]. Hayashi [4] has proposed to extract fuzzy rules from trained neural net. Lin [START_REF] Lin | Neural-network-based fuzzy logic control and decision system[END_REF], on the other hand, introduced a method of directly generating fuzzy rules from self-organized neural network. The common weakness of neural network, however, is a problem of determination of the optimal size of a network configuration, as this has a significant impact on the effectiveness of its performance.

The objective of this paper is to employ the Dempster-Shafer theory (DST) as a vehicle supporting the generation of fuzzy decision rules. More specifically, we concentrate on the role of fuzzy operators, and on the problem of discretization of continuous attributes. We show how they can be effectively used in the quantization of attributes for the generation of fuzzy rules.

The material is arranged in the following way. First, we summarize the underlying concepts of the Dempster-Shafer theory and briefly discuss the nature of the underlying construction. By doing so, the intension is to make the paper self-contained and help identify some outstanding design problems emerging therein. In Section 4 we explain essentials of our model. Finally, in Section 5, we report exhaustive experimental studies.

This paper is a continuation of our earlier work [START_REF] Sosnowski | Generating Fuzzy Decision Rules with the Use of Dempster-Shafer Theory[END_REF]. Here we apply theoretical vehicle, introduced in previous research, to the new input data in order to find possible area of application. Our important objective here is to reveal a way in which this approach becomes essential to a more comprehensive treatment of continuous attributes.

Dempster-Shafer Theory

The Dempster-Shafer theory starts by assuming a Universe of Discourse  also called Frame of Discernment, which is a finite set of mutually exclusive alternatives. The frame of discernment may consist of the possible values of an attribute. For example, if we are trying to determine the disease of a patient, we may consider  being the set consisting of all possible diseases. For each subset S of  it is associated:

 a basic probability assignment m(S)  a belief Bel(S)  a plausible belief Pla(S)
m(S), Bel(S) and Pla(S) have value in the interval [0,1], and Bel(S) is not greater than Pla(S).

In particular, m represents the strength of some evidence. For example, in rule-based expert system , m may represent the effect of applying of a rule. Bel(S) summarizes all our reasons to believe S. Pla(S) expresses how much we should believe in S if all currently unknown facts were to support S. Thus the true belief in S will be somewhere in the interval [Bel(S), Pla(S)]. More formally, a map

m : 2  [0,1] (1)
such that for each A  2  (where 2  is set of all subsets of )

1. m()=0 2.     A A m 1 ) ( is called a basic probability assignment for . Subset A is called a focal element of m if m(A)0.
For a given basic probability assignment m, the Belief of a subset A of  is the sum of m(B) for all subsets B of A, so

Bel : 2   [0,1] (2)
such that

   A B B m A Bel ) ( ) ( .
The Plausibility of a subset A of  is defined as Pla(A)=1-Bel(A'), where A' is the complement of A in  If we are given two basic probability assignments m1 and m2, we can combine them into a third basic probability assignment m:2  [0,1] in the following way.

Let us consider frame of discernment  and two belief functions Bel1 and Bel2. We denote focal elements of Bel1 as A1...AK and focal elements of Bel2 as B1...BL respectively and the basic probability assignments as m1 and m2. Then we can show graphically this combination as an orthogonal sum of m1 and m2.

The mass of probability of the interval Ai  Bj expressed as a measure m1(Ai)m2(Bj) is illustrated in Figure 1. Of course, more intersections can give the same focal element A. In general the mass of probability of set A is defined as:

m2 (BL) ... m2 (Bj) ... m2 (B1) m1 (A1) ... m1 (Ai) ... m1 (AK)
) ( ) ( ) ( 2 , 1 j A B A j i i B m A m A m j i      (3)
Then we find a problem with an empty set. It is possible that sets with empty intersection exist. We can meet this normal situation in many combinations. Then the mass of , according to above definition, will be greater than zero, but according to the definition of basic probability assignment, it is not possible.

We assume that

1 ) ( ) ( 2 , 1       j B A j i i B m A m j i (4)
to define the orthogonal sum m1 and m2, and denote it as m1  m2

Then it is necessary to change the definition (3) of the formula of the basic probability assignment of the combination as follows:

1. m()=0 2.            j i j i B A j i j i A B A j i j i B m A m B m A m A m , 2 1 , 2 1 ) ( ) ( 1 ) ( ) ( ) ( for non-empty A  
We call this as an orthogonal sum of Bel1 and Bel2, and denote as Bel1  Bel2. This is the Dempster Rule for Combining of Beliefs [START_REF] Shafer | Mathematical Theory of Evidence[END_REF].

For  we have m() =     A A m 1 ) ( and for combination if 0 ) ( ) ( 2 , 1       j B A j i i B m A m j i we have m() = 1 ) ( ) ( ) ( ) ( ) ( 2 , 1 2 , 1                j j i i A j A B A j i i A B m A m B m A m A m j i

Fuzzy modelling

Fuzzy set theory is widely known and we do not introduce its underlying concepts essential to understand this framework. Readers interest themselves we refer to [START_REF] Yager | Essentials of Fuzzy Modeling Control[END_REF] and [START_REF] Yager | Including Probabilistic Uncertainty in Fuzzy Logic Controller Modeling Using Dempster-Shafer Theory[END_REF]. Fuzzy Modeling is applied in those areas where the model of the system cannot be described precisely because of many reasons. The input data received by the system may not be completely reliable, may contain noise, or may be inconsistent with other data or with expectation about these data. The system is described by the set of linguistic rules. Let D denotes an output variable of the system, and X1 , X2 , ... , Xn denote an input variables. The linguistic rules have the following format:

If (X1 is Ak,1,j1) And ...And (Xn is Ak,n,jn) Then (D is Sk,p) (5)
where (Xi is Ak,i,ji) are the fuzzy antecedents, Ak,i,ji (1  ji  |Ai|) are values of the i-th input variable, and Sk,p (1  p  |S|) is the value of output variable in k-th rule.

The rules are implemented as fuzzy relation according to the formula:

p k jl n k jl k jl k k S A A A R , , , , 2 , , 1 ,
      (6)
where  denotes the fuzzy Cartesian product. Then all rules are aggregated to relation R described as:

 M k k R R 1   (7)
where M is the number of rules. The conclusion is based on the compositional rule of inference

  R A A A S jn n j j   , 2 , 2 1 , 1 ' ' ' '     (8)
where

jn n j j A A A , 2 , 2 1 , 1 ' , , ' , '  are input values, ' S is a conclusion (decision class),
and  denotes the composition of fuzzy relation.

In fuzzy modeling we can assume that expert defines the rule set, or we can automatically generate them from the set of samples describing the behavior of the system being modeled.

Fuzzy Dempster-Shafer Model

In Fuzzy Dempster-Shafer (FDS) model [START_REF] Binaghi | A Neural Model for Fuzzy Dempster-Shafer Classifiers[END_REF] we consider rules Rr as:

      r j n r n j r m is D Then A is X And A is X If n , , , 1 , 1 ... ... 1 (9)
where Xi and D stand for input and output respectively, and mr is a fuzzy belief structure, that is a standard belief structure with focal elements Sr,p as fuzzy subset of frame of discernment  with basic probability assignment mr (Sr,p), and mr (Sr,p) is the believe that the conclusion should be represented as class Sr,p .

Learning -Rules Construction

In antecedent construction, let us assume that we have n features (attributes) in antecedents of testing example. We consider a collection of m generic linguistic terms characterized by membership functions defined in a universe of discourse being a domain of each attribute. The conclusion belongs to decision class S.

For each element of data t we build a collection:

t m n t m t m t n t t t n t t A A A A A A A A A , , , , 2 , , 1 , 2 , , 2 , 2 , 2 , 1 , 1 , , 1 , 2 , 1 , 1 .
.. ... ...     (10)
where Ai,j,t are the values of j-th membership function for i-th feature and for t-th element of data.

Example 1

We demonstrate the calculations on the set of synthetic data presented in Table 1. First six rows (L1-L6) will constitute learning data, while the remaining ones (T1-T4) will form testing data. All the features are numbers from the <0; 9> interval. The last column represents the decision class equal to 1 or 2. We will consider four membership quadratic functions uniformly distributed along the space of all attributes. Other membership functions will be discussed in the next section. According to [START_REF] Quinlann | Induction of decision trees[END_REF] for row T1 we have:

Item F1 F2 F3 F4 Class L1 1 1 1 1 1 L2 9 8 8 9 2 L3 1 1 3 4 1 L4 2 1 2 2 1 L5 2
1.0 1.0 0.0625 0.0156 0 0 0.9375 0.9844 0 0 0 0 0 0 0 0 ■ On the base of [START_REF] Quinlann | Induction of decision trees[END_REF], for a given data point t we can calculate two vectors: ... : [START_REF] Umano | Generation of fuzzy decision trees by fuzzy ID3 algorithm and its application to diagnosis by gas in oil[END_REF] The firing level of the rule is calculated according to the following formula

t n t t t n A A A A , max , , max , 2 , max , 1 , ...
  t i n i t i A , max , 1     (14)
where  means the operator of fuzzy matching. See sections 5.2. for details. The first four elements are numbers of the best membership function for proper features, the next two are counters for decision classes and the last one is a probability distribution.

Let us observe that rule R2 covers the data L1, L 4 and L5. L1 and L4 produce decision class C1 but L5 decision class C2. ■ Now we can move to the testing of new rules.

Test

In testing we ignore the value from the last column in Table 1, that is decision class number, because our goal is to calculate it.

To compute the firing level of a rule k for a given data

k k n k k k D X X X X , , 2 , 1 .

.. : (22)

where Xi,k -feature's value, Dkconclusion decision class that we have to compare with the result of inference; we build a rule matrix

    k i t i k l i n i t k I l X A max, , , , , 1 , ,   
     R t p r t t F m E m 1 , ) ( (25)
The results of classification are D is m, with focal elements Ek(k=1,...,R |S| ) and distribution m(Ek). That results are calculated using focal elements and appropriate counters ct,1,.., ct,|S|.

Example 5

For sample point L5 and T1 the counters are 3, 1 , and 3, 0 respectively ■ Then we perform defuzzification according to COA method [START_REF] Bezdek | Convergence Theory for Fuzzy c-Means: Counterexamples and Repairs[END_REF].

   | | 1 ) ( S R k k k E m y y (26)
where yk are defuzzified values for focal element Ek defined as

       n t t t k n t t t k t k x x x y 1 , 1 , ) ( ) (   (

Empirical Learning for FDS Model

In this section we compare and analyze the performance of several membership functions and matching operators. We start from a standard solution used in the introduction to fuzzy modeling, then we consider more complicated models. We compute results for the following membership function: Linear, Quadratic, Gaussian, and FCM. We concentrate on Minimum, Multiply and Implication as a matching operators. The most valuable is comparing the results of all calculations. In the end of this section we show some results of experimental research. The simplest, The result are not so good;

2 Quadratic Y= 1-(X-xi) 2 / (xi+1-xi) 2
Still simply calculated function, The result are better than in the case of Linear function;

3 Gaussian

2 1               i x i x i x X e y
Exponential function, Using it leads in general to proper conclusions especially in learn sample; 4

FCM FCM algorithm

The complex algorithmvalues of function have to be previously generated. In general proper conclusion

Table 2. Membership Functions

Membership Functions

The membership function makes possible the division of data into n intervals. It is a way of discretization of the input data. Hence, we get the best result for continuous data or for data with several discrete (nominal) values. If we have discrete or binary data then results of the proposed model are not good enough.

The choice of membership function has a great influence on the quality of rules. Although the quantity of rules is different, the quality of classification is comparable.

The most interesting membership function was generated by Fuzzy c-Means(FCM) algorithm [START_REF] Bezdek | Convergence Theory for Fuzzy c-Means: Counterexamples and Repairs[END_REF]. The results of experimental research with membership functions have been summarized in Table 2.

Matching Operators

It was shown in our experiments that a matching operator applied to data sample with existing rules plays the very important role in the accuracy of diagnoses. It occurred as early as the rules were generated. A matching operator influences the quality of the generated rules. Of course, this quality has secondary means, but in general, the more rules the better accuracy.

From the analysis of the results of experiments in Table 6, we can infer that the most powerful operator is implication. This is not all the true, because Table 6 shows the results only for one fixed threshold value. It is not optimal in all instances, especially in multiply operator. The change of the threshold value (e.g. to 0.25) gives almost the same results as for implication operator. Anyway, the choice of the threshold value is of minor importance here, but it can have influence on the result of the receiving of rules. Of course, we cannot analyze the threshold value without keeping in mind the features of the membership function and the number of intervals. The choice of the threshold value will be subject of future works.

The results of the investigation of various matching operators are collected in Table 3.

Name

Formula Features 1 Minimum Max(0,min(x,y)) The simplest case.

In many experiments the results are good.

2 Multiply Max(0, x*y) It's case of implication, with  = -1. The results are better than in the case of Minimum operator. Important setting of threshold value. 3 Implication Max(0,(+1)* (x+y-1) -*x*y) Function seems to be complex. The best results. Setting constant  -direction for future research.

Table 3. Matching operators

Experimental studies

Some results of experimental research are shown in Table 4. We fixed here count of membership functions on 6 and threshold value on 0.75. All data sets have been divided into two parts: learning (training) data (about 2/3 of the entire data set) and testing data (remaining 1/3). The learning data has been used to generate the rule set. Testing data has been applied to test the produced rule set. To obtain reliable results, we carried out the experiment several times. That formulation does not show the most favorable case but it is allowed to see the part of real results with using different methods for generalizing rules. These results can be comparable.

The methods of automatically generated decision rules that are described in this paper have the best results on Iris data set. In a few points, reach a destination 100% of the decision accuracy. This set consists of all data as continuous values. In other cases, the construction of the data discretization caused a little worse results. In spite of the fact that in the case of Ulcers data set, for which over the half features was discrete, the results on the learning data was nearly the same like in the case of Iris data.

Diabetes data set is a sample of testing proposed algorithms on discrete data. The results of rules accuracy are not satisfactory. It has shown the case when the method of generating and verifying decision rules ineffectual as only one.

Another observation is that, the smaller number of binary data in antecedent, then the better accuracy of our rules. If the features have no binary data or if number of it is strongly less, then others then our rules can be applicable. We can see that during analyzing Breast Cancer Wisconsin and Dermatology data sets. In Echocardiogram data set, when number of binary data is equal to three the results are worse.

In all the instances, intermediate reports were stored in disk data files. It was used to compute results with the FCM algorithm. It also made possible to connect described method with others.

In our research, the proper choice of threshold value gave us information if rule is valuable or not. The importance of this value has been shown in the case of Multiply operator. The result presented in Table 4 could suggest less "weight" of this operator, but it is not true. If we change threshold value, we notice that it has almost the same occurrence as more complied in calculations Implication operator. Implication is a sample of a very interesting and powerful operator of fuzzy relation.

We compare the results of our research with standard decision trees algorithm [START_REF] Quinlann | Induction of decision trees[END_REF]. For all data sets, we get better results using Gaussian function or FCM algorithm [START_REF] Bezdek | Convergence Theory for Fuzzy c-Means: Counterexamples and Repairs[END_REF], and in a few points of Quadratic function, we obtained also better accuracy.

In Dermatology and Echocardiogram data sets, we removed records with missing input features, because we concentrate only on complete data.

Conclusions

The study has focused on the use of Fuzzy Dempster-Shafer model for generating of fuzzy decision rules. Fuzzy sets are useful in discretization of continuous attributes. The approach is discussed in the concrete applications of two real medical data sets (especially to problems of identification of diseases) and several well-known data sets available on the Web. The results are used to classify objects. It has been found through series of experiments that this approach outperforms the results of the C4.5 algorithm in terms of higher classification accuracy.

Fig. 1 .

 1 Fig. 1. Orthogonal sum of m1 and m2

  The rule candidate is added to rules set if   Th threshold value, and  matching operator). This can help to eliminate bad rules from the final rule set.More ten one rule can have the same antecedent part but it is also possible that conclusion of these rules are different. Then we have to use appropriate counters ct,1,.., ct,|S| , where |S| denotes the power of decision class set. These counters can show us how many data, according to rule pattern, vote for each decision class. Example 2 In our sample (T1) the vectors are: A,1 : 1.0000, 1.0000, 0.9375, 0.9844 Ic,1 : 1, 1, 2, 2 with counters vector 1, 0 In our sample matching value equals to 0.9229, were multiplication was used as the matching operator (1.0000* 1.0000* 0.9375* 0.9844 = 0.9229). For the threshold set on 0.75, we obtain a new rule. ■ The product is a new belief structure on X

(

  27)In the next step, the rules structure is simplified to If Antecedentr Then (D is Hr), and T1 we calculate decision class 1. It is correct in case of T1, but wrong for L5. The values of Hr are 0.4283 and 0.4800 respectively. ■

  = (X-xi+1)/( xi-xi+1) F2: Y= (X-xi)/( xi+1-xi)

Table 1 .

 1 Sample data set

			2	2	2	2
	L6	5	6	7	8	2
	T1	3	3	3	2	1
	T2	1	2	2	1	1
	T3	4	7	7	9	2
	T4	2	8	7	8	2

  The first four elements are the rule pattern, the next two are the counters for decision classes. The next four numbers are the values of appropriate membership function. The number 0.859375 is the value of the first membership function, according to the first number in the rule, on the first feature. The next three numbers are calculated in the same way.The last numbers in the above rows are the matching value for the rule. It has been calculated by matching operator for the values of membership function.We focused only on the rows with matching value grater then zero.

	For sample data L5 we have two active rules:
	R1: 1 1 2 2	1 0	0.859375 0.859375 0.609375 0.609375 0.274242
	R2: 1 1 1 1	2 1	0.859375 0.859375 0.859375 0.859375 0.54542
	For sample data T1 we have:
	R1: 1 1 2 2	1 0		0.4375 0.4375 0.9375 0.6094 0.1093
	R2: 1 1 1 1	2 0		0.4375 0.4375 0.4375 0.8594 0.0720
							■
	For each collection of	t t p r F , focal elements	r m ˆ we define an aggregate
						R
				E	 	F	(24)
					t	1 	t t p r ,
	with basic probability assignment
							(23)
	We are interested only in active rules i.e. rows with matching value		k	t , 	0	.
	Example 4
	In test we will demonstrate calculations on
	L5. 2	2	2	2
	T1. 3	3	3	2

 

Table 4 .

 4 Experimental results

	adfa, p. 14, 2011.
	© Springer-Verlag Berlin Heidelberg 2011

Acknowledgement

This work was supported by the grant S/WI/1/2013 from Bialystok University of Technology founded by Ministry of Science and Higher Education.


Katarzyna Stąpor
email: katarzyna.stapor@polsl.pl

Piotr Fabian
email: piotr.fabian@polsl.pl

Classification of Protein Interactions Based on Sparse Discriminant Analysis and Energetic Features

Keywords: sparse discriminant analysis, feature selection, protein-protein interaction

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Prediction of protein-protein interaction (PPI) types is an important problem in life sciences because of fundamental role of PPIs in many biological processes. PPIs have been investigated in various ways, involving both experimental (in vivo or in vitro) and computational (in silico) approaches [START_REF] Bordner | Statistical analysis and prediction of protein-protein interfaces[END_REF][START_REF] Skrabanek | Computational prediction of protein-protein interactions[END_REF]. Experimental approaches tend to be costly, labor intensive and suffer from noise. Therefore, using computational approaches for prediction of PPIs is a good choice for many reasons.

PPIs can be divided into non-obligate and obligate complexes (binding components can/cannot form stable functional structures). Based on the duration and life time of the interactions, there are transient complexes and permanent ones. Although interfaces have been the main subject of study to predict protein-protein interactions, an accuracy of 70% has been independently achieved by several different groups ( [START_REF] Rueda | Biological protein-protein interaction prediction using binding free energies and linear dimensionality reduction[END_REF][START_REF] Skrabanek | Computational prediction of protein-protein interactions[END_REF][START_REF] Zhou | Prediction of protein-protein interaction sites from sequence profile and residue neighbor list[END_REF][START_REF] Zhu | NoxClass: prediction of protein-protein interaction types[END_REF]). These approaches have been carried out by analyzing a wide range of parameters, including solvation energies, amino acid composition, conservation, electrostatic energies, and hydrophobicity.

These includes a method based on PCA combined with Chernoff extension of Fisher linear discriminant analysis [START_REF] Rueda | Biological protein-protein interaction prediction using binding free energies and linear dimensionality reduction[END_REF]. PCA is necessary to reduce the dimensionality of the input feature space (i.e. to be less than the sample size). As a consequence some important information is lost.

In this paper, we propose a new classification approach based on sparse discriminant analysis [START_REF] Qiao | Sparse linear discriminant analysis with applications to high dimensional low sample size data[END_REF] to predict obligate (permanent) and non-obligate (transient) proteinprotein interactions. To characterize properties of protein interaction, we proposed to use the binding free energies.

Fisher and Sparse regularized linear discriminant analyses

Fisher Linear Discriminant analysis (FLDA) [START_REF] Fukunaga | Introduction to statistical pattern recognition[END_REF][START_REF] Stąpor | Classification methods in computer vision[END_REF] is a multivariate technique which is concerned with the search for a linear transformation that reduces the dimension of a given p-dimensional statistical model to q (q<p) dimensions, while maximally preserving the discriminatory information for the several classes within the model. Formally, suppose that there are k classes and let

i ij n j x , , 1 ,   be vectors of ob- servations from the i-th class, . , , 1 k i   Set k n n n     1 and let T kn k n p n k x x x x X ) , , , , , , ( 1 1 11 1
    
, where p is the dimensionality of the input space. FLDA determines a linear mapping L, i.e. a p q  matrix A, that maximizes the so-called Fisher criterion F J :

)

) ( ) (( ) ( 1 T B T W F A AS A AS tr A J   (1)
where

     k i T i i i B m m m m p S 1 ) )( ( and
   k i i i W S p S
T i ij n j i ij i i m x m x n S i ) ( ) ( 1 1 1      
is the within-class covariance matrix of class i, i m is the mean vector of class i, i p is it's a priori probability, and

   k i i i m p m 1 is
the overall mean. FLDA maximizes the ratio of between-class scatter to average within-class scatter in the lower-dimensional space. Optimizing (1) comes down to determining an eigenvalue decomposition of B W S S 1  , and taking the rows of A to equal the q eigenvectors corresponding to the q largest eigenvalues. There are no more than ) 1 , min(  k p eigenvectors corresponding to nonzero eigenvalues. When the number of variables exceeds the sample size, i.e., in the highdimensional, low-sample size (HDLSS) settings, the within-class covariance matrix W S is singular and the classical FLDA breaks down. Several extensions have been proposed to overcome this problem but all of them possess the data pilling problem [START_REF] Marron | Distance-weighted discrimination[END_REF]. To ameliorate this problem, some sparse version of LDA have been proposed.

In our approach, to circumvent this problem, we adapt the sparse linear discriminant approach (slda) from [START_REF] Qiao | Sparse linear discriminant analysis with applications to high dimensional low sample size data[END_REF] that incorporates feature selection in FLDA. The term "sparse" means that the discriminant vectors have only a small number of nonzero components. The underlying assumption is that, among the large number of variables there are many irrelevant or redundant variables for the purpose of classification. This method is based on the connection of FLDA and a generalized eigenvalue problem, stated formally by the following theorem:

Theorem [START_REF] Qiao | Sparse linear discriminant analysis with applications to high dimensional low sample size data[END_REF]: Suppose w S is a positive definite matrix and denote its Cholesky decomposition as

w T w w R R S  ( w R is an upper triangular matrix). Let b H be p k  matrix, q V V , , 1  ( ) 1 , min(   k p q
) denote the eigenvectors of

B W S S 1  corresponding to the q largest eigenvalues q      1 , ] , , [ 1 q A     , ] , , [ 1 q B     . For 0   let B A , ˆ be
the solution to the following problem:

       k i q j j w T j i b T i b T w B A S H AB H R 1 1 2 , , , ) ( min    subject to q p T I A A  
, where:

T i i i b x x n H ) ( ,   is the i-th row of the matrix   T k k b x x n x x n H ) ( , ), ( 1 1     , i n
e is a vector of ones with length i n ,

Then q j j  , 1 , ˆ 
, span the same linear space as

q j V j , , 1 ,   .
The following method of regularization is applied in [START_REF] Qiao | Sparse linear discriminant analysis with applications to high dimensional low sample size data[END_REF] to circumvent the singularity problem and to obtain the sparse linear discriminants: i.e. the first q sparse discriminant directions

q   , , 1 
are defined as the solutions to the following optimization problem:

                   q j j j k i q j j w w T j i b T i b T w B A I p S tr S H AB H R 1 1 , 1 1 1 2 , , , ) ( min       subject to q p T I A A  
, where ] , , [ 1

q B     , 1 j



is the 1-norm of the vector j  , the same  is used for all q directions, different

j , 1
 's are allowed to penalize different discriminant directions.

Our empirical study suggests that the solution is very stable when  varies in a wide range, for example in (0.01, 10000). We can use K-fold cross validation (CV) [START_REF] Stąpor | Classification methods in computer vision[END_REF] to select the optimal parameters j , 1

 , but when the dimension of the input data is very large, the numerical algorithm becomes time consuming and we can let

q , 1 1 , 1     
. The tuning parameter  controls the strength of the regularization of the matrix w S , the large values will bias too much w S towards identity matrix (high degree of regularization). In our empirical studies, we find that the results are not sensitive to the choice of  if a small value that is less than 0.1 is used, in our studies we set 05 . 0   . More careful studies of choice of  are left for future research. The above problem can be numerically solved by alternating optimization over A and B [START_REF] Qiao | Sparse linear discriminant analysis with applications to high dimensional low sample size data[END_REF] and the resulting algorithm is summarized below. *** Regularized sparse LDA ( rSLDA) algorithm (based on [START_REF] Qiao | Sparse linear discriminant analysis with applications to high dimensional low sample size data[END_REF]):

1. Form the matrices from the input data:

              T K n T n w x e x e X H K ) ( ) ( 1 1    T k k b x x n x x n H ) ( , ), ( 1 1     2.
Compute upper triangular matrix w R from the Cholesky decomposition of: ***

         I p S tr S w w ) (  such that w T w w w R R I p S tr S           ) (  3. Solve the q independent optimization problems q j W y W W j j T j T T j j , , 1 , 2 ) ( min 1 1           where             w b p p n R H W  ) ( ~             0 ~1 1 ) ( j w b p n R H y  4. Compute SVD: T B T B T w UDV B H H R   ) (

Protein-protein interaction classification method

To characterize properties of protein interaction, we proposed to use the binding free energies. These were computed using FastContact [START_REF] Camacho | FastContact: rapid estimate of contact and binding free energies[END_REF], which obtains their fast estimates. FastContact delivers the electrostatic energy, solvation free energy, and the top 20 maximum and minimum values for:

1. residues contributing to the binding free energy, 2. ligand residues contributing to the solvation free energy, 3. ligand residues contributing to the electrostatic energy, 4. receptor residues contributing to the solvation free energy, 5. receptor residues contributing to the electrostatic energy, 6. receptor-ligand residue solvation constants, 7. receptor-ligand residue electrostatic constants.

Thus, all these values and the total solvation and electrostatic energy values compose a total of 282 features characterizing interaction.

To create a dataset for classification, we used the pre-classified dataset from previous study [START_REF] Rueda | Biological protein-protein interaction prediction using binding free energies and linear dimensionality reduction[END_REF] containing 62 transient and 75 obligate complexes as two different classes for classification. Each complex is listed in the form of chains for ligand and receptor respectively. The relevant data about the structure of each complex was obtained from the Protein Data Bank (PDB) [START_REF] Berman | The Protein Data Bank[END_REF] and then obtaining the 282 features by invoking FastContact.

Due to the fact that the number of features ( 282) is greater than the number of samples in a dataset (137), we have HDLSS setting, so we apply sparse regularized linear discriminant analysis for the calculation of discriminant directions, i.e. the algorithm sparsed rLDA described above.

For the classification of the samples in the new discriminant space, we applied the nearest centroid method [START_REF] Stąpor | Classification methods in computer vision[END_REF] as the classification algorithm.

Rapid estimation of contact and binding free energies

The estimation of contact and binding free energies may be in general a time consuming job. One of components of the binding energy is electrostatic energy. This term applies to a system of charges and is defined as the work necessary to move all the electric charges from infinity to positions occupied in the analyzed system. This work does not depend on the path traveled by the charges and is one of properties of a static arrangement of charges in space. Electrostatic interaction works on relatively long distances [START_REF] Maleki | The role of electrostatic energy in prediction of obligate protein-protein interactions[END_REF]. For proteins, it refers to the interaction between electrically charged atoms in different proteins or interactions between charges in the surface of the protein and charges in the environment. The exact computation of this energy for each possible conformation would be time consuming.

We have used a method called FastContact, developed by Camacho et al. [START_REF] Camacho | FastContact: rapid estimate of contact and binding free energies[END_REF][START_REF] Camacho | Scoring Docked Conformations Generated by Rigid-Body Protein-Protein Docking[END_REF]. The binding energy is computed as a sum of the electrostatic potential and the desolvation free energy in proteins:

n desolvatio tic electrosta binding G E G  
. In this formula, tic electrosta

E

is the standard intermolecular Coulomb electrostatic potential with relative permittivity varying with the distance r and equal to 4r. The term n desolvatio G includes basic features of the desolvation free energy in proteins: hydrophobic interactions, self-energy change resulting from desolvating charge on polar atom groups and sidechain entropy loss. The n desolvatio

G

term is calculated as a sum of atomic contact potentials (ACP) between all pairs of atoms, where the first atom belongs to the receptor, the second to the ligand. Each term of this sum is additionally multiplied by a function g(r) depending on the distance r between involved atoms. For r > 7 Å the value is 0, for r < 5 Å is 1 and between 5 Å and 7 Å g(r) is a smooth function. These ACPs are defined for 18 atom types. The function g(r) makes possible faster computation by zeroing interactions between distant atoms.

Experimental results

In our experiments we have used the dataset of 137 protein complexes described in [START_REF] Zhou | Prediction of protein-protein interaction sites from sequence profile and residue neighbor list[END_REF]. 75 samples in this dataset belong to the first class (i.e. "obligate interactions") and 62 samples to the second class (i.e. "non-obligate interactions"). This dataset is randomly divided into a "training set" and "testing set" in a ratio of 4:1.

As we have only two classes (k=2), there is only one discriminant direction 1  (q=1). Using all variables in constructing the discriminant vector 1  might cause the overfitting of the training data, resulting in high testing error rate. Moreover it is computationally demanding, so sparsification would be a good choice.

Denote the number of significant variables involved in specifying the discriminant direction 1  (i.e. giving the best prediction), to be m. To find these most significant variables we have performed the experiment with varying values of m. For a given value of m, only the m maximum values of the coordinates of the vector 1  (so called beta values) are left, the rest is zeroed.

Fig. 2 shows the components of vector 1  obtained by the SLDA algorithm in one of experiments converted to the absolute values and sorted in the ascending order.

We leave only m biggest values, zeroing all others. We keep track of indices of these biggest values and modify the original 1  leaving only m biggest values. These values are used to cast the original 282-dimensional vector onto a one-dimensional space. The projection of the samples from the protein dataset uses only these m nonzero coefficients.

Then, classification is performed in such new discriminant space by the nearest centroid method.

The results are shown in Fig. 1. We can observe that the error rate of the nearest mean classifier grows rapidly and then decreases with the rise of m, up to 28 (error = ~25% ±5 measured on the testing set). Then, for bigger values of m, almost a constant error rate was observed.

From the plot it is clear that if we specify m=28 as the number of component variables in discriminant vector 1  -sparse LDA algorithm can discriminate the two classes fairly well (the classifier performance = ~75% ±5).

These 28 input features ("selected" by the rslda algorithm) are the most significant for classification. These are the following (corresponding to the ascending order of the absolute value of the coefficients composing vector Among these 28 features -13 are from the receptor residues contributing to the desolvation free energy, but these are not from the beginning of the above list. It can be observed that in each of the 7 groups of energetic features -only features with extreme (min or max) contribution to the energy are always selected. The features from the beginning of the list are those from the receptor residues contributing to the electrostatics energy. One may conclude that electrostatic energy is the most important in the prediction of obligate/non-obligate protein-protein interactions. Electro-static energy involves a long-range interaction and occur between charged atoms of two interacting proteins.

Thus, the rslda algorithm does suggest which constituents are the most important in the classification of interactions.

Conclusions

We have proposed a classification approach for obligate/non-obligate (transient) protein-protein complexes. We have used regularized version of sparse linear discriminant analysis algorithm [START_REF] Qiao | Sparse linear discriminant analysis with applications to high dimensional low sample size data[END_REF] for feature extraction as well as for input variable selection. To discriminate between two types of protein interactions: obligate and nonobligate, we have used the "energetic features". These are based on the binding free energy defined as the sum of the desolvation and electrostatic energies. These were computed effectively using the package FastContact [START_REF] Camacho | FastContact: rapid estimate of contact and binding free energies[END_REF]. The results on the proteinprotein interactions dataset showed that using only 28 from 282 input variables enables the classification of the mentioned two types of interactions with the performance of 75%. Among the most important features are those from residues contributing to the electrostatic energy. The hypothesis on the importance of the electrostatic energy in the prediction of obligate/non-obligate protein-protein interactions should be confirmed by the additional experiments on bigger protein datasets. This will be the subject of our future research.

5 .

 5 Repeat steps 3 and 4 until converges.

Fig. 1 .

 1 Fig. 1. The average classification error rate as a function of the number of variables using nearest centroid method [10] on the projected data (based on 5 random partitions of the dataset into training and test) -the local minimum is at 28


Tomasz Hyla
email: thyla@zut.edu.pl

Jerzy Pejaś
email: jpejas@zut.edu.pl

A Fault-Tolerant Authenticated Key-Conference Agreement Protocol with Forward Secrecy

Keywords: user authentication; conference-key agreement, group communication, forward secrecy, fault tolerance

In conference channels, users communicate with each other using a conference key that is used to encrypt messages. There are two basic approaches in which the key can be established. In the first one, a central server is used (with a chairman role). The server generates the key and distributes it to participants. The second approach is that all participants compute a key without a chairman. In this paper, we introduce a special type of group authentication using secret sharing, which provides an efficient way to authenticate multiple users belonging to the same group without the chairman. Our proposed protocol is a many-tomany type of authentication. Unlike most user authentication protocols that authenticate a single user each time, our proposed protocol authenticates all users of a group at once.

Introducion

In the era of mobile devices and cloud computing, millions of documents and messages are continuously exchanged over the Internet. The communication channels built using the Internet require security measures that will ensure confidentiality and entities' authentication. Communication channels can be divided into three types: one-to-one, oneto-many (broadcast channels) and many-to-many (conference channels) allowing message exchange between all participants.

Several protocol allowing mutual user authentication and key derivation exists. One of the most popular TLS (Transport Layer Security) is widely used in many kinds of different applications. Situation is more complicated when we need a conference channel. Of course, protocols like TLS can be used to simulate a conference channel by creating independent channels between users. However, when a number of users increases this starts to be infeasible, because the number of channels and exchanged messages increase quadratically.

In conference channels, users communicate with each other using a conference key K that is used to encrypt messages [START_REF] Tzeng | A secure Fault-Tolerant Conference-Key Agreement Protocol[END_REF]. There are two basic approaches in which the key K can be established. In the first one, a central server is used (with a chairman role).

The server generates the key and distributes it to participants. The second approach is that all participants compute a key without a chairman. The first approach is simpler and easier to implement, but it lacks of flexibility and requires an additional service. The second approach is a special case of a secure multiparty computation in which a group of people evaluate securely a function to f(k1, k2, …), with each person possessing a private input ki. The conference key agreement protocols have a few different features in comparison with secure multiparty computation. Firstly, private channels between participants are not available. Secondly, the main goal of an adversary is to disrupt the protocol between honest participants. Thirdly, a cheater is excluded from participating when is found (the cheater secret is not necessary to compute the conference key) [START_REF] Tzeng | A secure Fault-Tolerant Conference-Key Agreement Protocol[END_REF].

The conference-key agreement protocols have several properties [START_REF] Ermiş | An improved conference-key agreement protocol for dynamic groups with efficient fault correction[END_REF][START_REF] Tseng | A communication-efficient and fault-tolerant conference-key agreement protocol with forward secrecy[END_REF]: a) Forward confidentiality-subsequent conference keys cannot be obtained by participants who left the conference sessions [START_REF] Tseng | A communication-efficient and fault-tolerant conference-key agreement protocol with forward secrecy[END_REF][START_REF] Rhee | An architecture for key management in hierarchical mobile ad-hoc networks[END_REF]. b) Backward confidentialityformer conference keys cannot be obtained by participants who joined the conference session [START_REF] Tseng | A communication-efficient and fault-tolerant conference-key agreement protocol with forward secrecy[END_REF][START_REF] Rhee | An architecture for key management in hierarchical mobile ad-hoc networks[END_REF]. c) Key freshness -If a conference-key agreement protocol achieves both backward and forward confidentiality, then the key generated using this protocol is called fresh [START_REF] Tseng | A communication-efficient and fault-tolerant conference-key agreement protocol with forward secrecy[END_REF][START_REF] Rhee | An architecture for key management in hierarchical mobile ad-hoc networks[END_REF]. d) Forward secrecy -A conference-key agreement protocol provides forward secrecy if the long-term secret key xi of any participant Ui is compromised, but will not result in the compromise of previously established conference keys [START_REF] Bellare | Authenticated key exchange secure against dictionary attacks[END_REF][6][START_REF] Tseng | A robust multi-party key agreement protocol resistant to malicious participants[END_REF]. Forward secrecy is different from forward confidentiality as it is related to a longterm key in opposite to forward confidentiality that is related to a short term conference key K. e) Authenticationthe protocol is called an authenticated protocol when it contains mechanism allowing detect if the participant is a member of the conference [START_REF] Ermiş | An improved conference-key agreement protocol for dynamic groups with efficient fault correction[END_REF]. f) Fault tolerancethe protocol is called fault-tolerant when it detects faulty broadcast messages during the communication of participants. The sender of the faulty message is marked as possible malicious one. Faulty messages are re-verified and in a case of a negative result, the participant is excluded from the set of participants [START_REF] Ermiş | An improved conference-key agreement protocol for dynamic groups with efficient fault correction[END_REF]. Such property allows honest participant to establish a conference key, even in malicious participant are trying to disrupt it [1] [8-9]. g) Dynamic settings -The dynamic group operations supported by the protocol (i.e.: single or mass join, single or mass leave, merge or divide groups) [START_REF] Ermiş | An improved conference-key agreement protocol for dynamic groups with efficient fault correction[END_REF].

Several conference protocols have been proposed in recent years. However, the DKCAP protocol with all mentioned above properties was presented in 2015 by O. Ermiş et al. [START_REF] Ermiş | An improved conference-key agreement protocol for dynamic groups with efficient fault correction[END_REF]. Also, they have provided comprehensive comparison of the protocols. The protocol proposed by Chung in 2013 [START_REF] Chung | The design of authentication key protocol in certificate-free public key cryptosystem[END_REF] have all the properties except fault tolerance and supports only two dynamic operations. In contrast, Cheng et al. [START_REF] Cheng | A fault-tolerant group key agreement protocol exploiting dynamic setting[END_REF] proposed a protocol that is fault tolerant, but does not provide forward secrecy. Zhao et al. [START_REF] Zhao | An efficient fault-tolerant group key agreement protocol[END_REF] proposed protocol that is authenticated, fault tolerant, provides forward secrecy and key freshness, but does not have dynamin operations.

Authenticated, fault tolerant and providing key freshness protocols, without the forward secrecy and dynamin operations have been proposed by Huang et al. [START_REF] Huang | A conference key agreement protocol with fault-tolerant capability[END_REF], Wu et al. [START_REF] Wu | Asymmetric group key agreement[END_REF], Wang [START_REF] Wang | Improvement on the fault-tolerant group key agreement protocol of Zhao et al[END_REF]. Katz and Yung [START_REF] Katz | Scalable protocols for authenticated group key exchange[END_REF] proposed an authenticated protocol with forward secrecy and key freshness, but without fault tolerant property and dynamic operations. Tseng proposed two protocol, first one [START_REF] Tseng | An improved conference-key agreement protocol with forward secrecy[END_REF] with all the properties except dynamic operations and second one [START_REF] Tseng | A communication-efficient and fault-tolerant conference-key agreement protocol with forward secrecy[END_REF] with two dynamic operations, but without key freshness.

Objective

In this paper, we propose the improved authenticated conference key agreement protocol, called Forward-secrecy and Fault-tolerance Authenticated Conference-Key Agreement (FF-ACKA) protocol. FF-ACKA protocol is a modified version of an improved conference-key agreement protocol with forward secrecy (hereinafter in short ICKAP [START_REF] Ermiş | An improved conference-key agreement protocol for dynamic groups with efficient fault correction[END_REF][START_REF] Tseng | An improved conference-key agreement protocol with forward secrecy[END_REF]) for the static group of participants. The protocol is a provable secure conference-key agreement protocol with fault tolerance and forward secrecy. In addition, because the security of ICKAP protocol is preserved, FF-ACKA protocol is resistant against known attacks of a passive and an active adversary.

FF-ACKA protocol requires only a constant size message to be sent by each participant and has two rounds. Both rounds are authenticated by means of long-term certified asymmetric keys of participants. Hence, FF-ACKA protocol is resistant against a classic man-in-the-middle attacks.

Another contribution of this work is to provide a truly contributory group conference key, i.e., in the protocol, the conference key is established jointly by all members of the conference, and not by any single member. Furthermore, the calculation of each participant contribution, in contrast to other protocols (e.g., [START_REF] Ermiş | An improved conference-key agreement protocol for dynamic groups with efficient fault correction[END_REF][START_REF] Tseng | An improved conference-key agreement protocol with forward secrecy[END_REF]), is much less time-consuming.

Paper organisation

The remainder of this paper is organized as follows. Section 2 contains description of a security model, definitions and notations. In Sections 3 is described the proposed FF-ACKA protocol (A Fault-Tolerant Authenticated Key-Conference Agreement Protocol with Forward Secrecy). Next, in Section 4 the security analysis of FF-ACKA protocol is provided. The paper ends with conclusion.

Preliminaries

We adopt the system and security model, definitions, and notations similar to Tseng's works ( [START_REF] Tseng | A communication-efficient and fault-tolerant conference-key agreement protocol with forward secrecy[END_REF], [START_REF] Tseng | An improved conference-key agreement protocol with forward secrecy[END_REF], see also [START_REF] Ermiş | An improved conference-key agreement protocol for dynamic groups with efficient fault correction[END_REF]).

2.1

System model

In the system, each participant has a long-term private key and a corresponding public key. The public system parameters and each participant's public key information with its certificate are stored in a public directory. All participants are connected using a broadcast network and can distribute messages to each other. The transmission between them should be protected and needs to establish a conference key to encrypt their communications. Below, we present two definition which is strongly related to FF-ACKA protocol given in Section 3.

Definition 1 (Conference participants, [START_REF] Ermiş | An improved conference-key agreement protocol for dynamic groups with efficient fault correction[END_REF]). Participant, participant set and their properties:

(a) Each conference participant is an entity and denoted as Ui.

(b) The participant list is represented as (U1, U2, …, , Un). Each participant knows all participants and theirs identities. (c) Participants in a conference session can be categorized in two groups. If a participant fully follows the protocol, it is called a honest participant, or if a participant tries to cheat other participants to miscalculate the key is called a malicious participants.

Definition 2 (Verification Matrix, [START_REF] Ermiş | An improved conference-key agreement protocol for dynamic groups with efficient fault correction[END_REF]). Let U = {U1, U2, …, Un} be the set of participants. During the execution of the protocol, participant Uj, which for 1  i  n and i ≠ j has at least one verification matrix entry Vi,j = 'Step4:failure' or Vi,j = 'Step5:failure' with the proper credentials, is defined as a potential malicious participant until its malicious behaviour is proved in a fault detection and correction step. Otherwise, i.e., if the verification matrix entry Vi,j = 'Step4:success'' or Vi,j = 'Step5:success'', the participant is defined as honest participant.

Security properties

Under the same definitions as used in Tzeng's protocol [START_REF] Tzeng | A secure Fault-Tolerant Conference-Key Agreement Protocol[END_REF], there are malicious adversaries. The first is a passive adversary (an eavesdropper) who is not a participant, but who tries to learn the conference key from the broadcast messages. The conference-key agreement protocol is secure against a passive attack, if a selected random value and the established conference key are computationally indistinguishable for an adversary.

The second is an active adversary. This is an adversary that is also a participant and who tries to disrupt the establishment of a conference key among the honest participants. A conference-key agreement protocol is secure against an active adversary. Even if the adversary does not follow the protocol in any way, he still cannot disrupt the establishment of the conference key. The security of the conference key protocol discussed in the paper is based on the Discrete Logarithm (DL) problem.

The Proposed Protocol with Forward Secrecy

Our Forward-secrecy and Fault-tolerance Authenticated Conference-Key Agreement (FF-ACKA) protocol consists of three phases, including a parameter generation phase, long-term keys and a certificates' generation phase, a temporary public-key distribution phase, a secret distribution and commitment phase, a sub-key computation and verification phase, a fault detection phase, and a conference key computation phase. These phases and theirs detailed structures are explained below.

The FF-ACKA protocol with a forward secrecy property uses a temporary public key to distribute keys, thus even the disclosure of the user's secret key will not result in the compromise of previously established conference keys. The authenticity of the user's temporary key can be verified by checking the signature on the key (hereinafter referred as a temporary certificate) generated with the long-term private key. Hence, each instance of the protocol uses both the static long-term public keys as well as the temporary public keys, which makes the protocol forward secure.

Without loss of generality, let U = {U1, U2, ..., Un} be the initial set of participants that want to establish a common conference key. Each Ui (i = 1, …, n), knows the set U. In FF-ACKA protocol, we assume that a conference can be started by the creator of U set who as a member of this set plays a role of a conference initiator.

3.1

Step 1: Setup

On input a security parameter  ∈ Z, this algorithm runs as follows (see [START_REF] Ryabko | Basics of Contemporary Cryptography for IT Practioners[END_REF][START_REF] Katz | Introduction to Modern Cryptography: Principles and Protocols[END_REF]): (a) generates a random (λ+1)-bit prime number p;

(b) calculates a prime q number equal to q = (p -1)/2; (c) chooses an arbitrary

* p Z x  with p x mod 1   and sets p x g mod 2 
; g is a generator for the subgroup * p q Z G  ;

(d) chooses cryptographic hash functions (like as in [START_REF]IEEE Standard 1363.3 -2013 -IEEE Standard for Identity-Based Cryptographic Techniques using Pairings[END_REF]):

  q Z H  * 1 , 0 : ,   q Z G  * 1 , 0 :
. Hence, the system parameters are params = {Gq, Zp, Zq, p, q, g, H}.

Step 2: Keys and long-term certificates generation

We assume that each user Ui in the system makes the following operations: (a) picks an random integer The resulting public key is (p, q, g, yi), while the private key has a form of (p, q, g, xi). The authenticity of this key pair confirms the certificate certi issued by the CA. The protocol is started by the initiator who calls for a conference by initializing a set of participants U. In addition, the function of time stamp T is required, and it will be updated to a new one for each conference session.

* q i Z x

3.3

Step 3: Temporary public-key distribution

Each from n participants belonging to a set U generates a temporary key pair and issues certificate related to the key pair. The temporary certificate is signed by the user using his private key and is valid only for a period of the key establishment phase in the conference protocol.

We use the Galindo-Garcia signature scheme given in [START_REF] Chatterjee | Galindo-Garcia Identity-Based Signature Revisited[END_REF][START_REF] Chatterjee | A Closer Look at Multiple Forking: Leveraging (In)Dependence for a Tighter Bound[END_REF] to generate a temporary certificate. This signature scheme is based on the discrete logarithm problem and is secure against the adaptively chosen message attack in the random oracle model.

The algorithm described is executed by users Ui  U :

(a) a user Ui select a short-term private key

* q i Z t
    i i i i i i g h x v t tCert    mod q, ( 1
)
where Finally, the i tCert can be called as a certificate for the temporary public key Ti or a temporary certificate in short.

  T V

Step 4: Secret distribution and commitments

Upon receiving all messages tMj = (

j tCert , j tCI , j T , j V , T,   ), j = 1, …,i-1, i+1, …, n, each user Ui (1 ≤ i ≤ n) validates that j t is
The user Ui also validates whether:

(a) the long-term certificate j cert related to the public key j y is authentic and un- revoked.

(b) Tj is a generator of a subgroup Gq, i.e., if 2  Tj  p -1 and  

1 mod  p T q j .
If any check for tMj of Uj does not hold, then the participant Ui sets Vi,j = 'Step4:failure', otherwise Vi,j = 'Step4:success'. For both cases, the participant Ui computes credentials:

    T V q T H h j i x k i k i , , mod , ,  , k = 1, …, n; k ≠ i, (3)
and broadcasts a tuple vMi,j = (Vi,j, h1,i, …, hi-1,i,, hi+1,i, hn,i, T). Next, Vi,j = 'Step4:failure', the participant Ui goes to Step 6 for fault detection and correction. Otherwise, each participant Ui:

(a) randomly selects a sub-key

* q i Z K 
and a random linear function fi(z)

over q Z :   q i i i Z z a K z f    , (4)
where the coefficient ai is in

q Z ; (b) calculates   1 0 , i i f   , generates random numbers * , q i i Z    , calculates p g i i mod    and p g i i mod   
, subsequently calculates for each j = 1, …, n; j ≠ i:

(a)   q T z i j j i mod ,   (b)     j i j i j i i j i tCert tCert z H z f , , , , ,    (c) issues an attestation in a form:     i i i i i i d c t       mod q (5)
where

  T H c i i ,  
, and

  i i i i c K T G d , , ,   ; then sends each participant j (j ≠ i) a message Mi = ( i  , i cert , i tCert , 0 , i  , 1 , i  , 2 , i  , , n i,  , i  , i  ).
Similarly as in step 3 (see Eq. 2), to issue a certificate a Galindo-Garcia signature scheme [START_REF] Chatterjee | Galindo-Garcia Identity-Based Signature Revisited[END_REF][START_REF] Chatterjee | A Closer Look at Multiple Forking: Leveraging (In)Dependence for a Tighter Bound[END_REF] was used.

3.5

Step 5: Subkey computation and verification

Upon receiving message Mj = ( j  , j cert , j tCert , 0 , j  , 1 , j  , 2 , j  , , n j,  , j  , j  ) from
Uj (1 ≤ j ≤ n), each participant Ui for j ≠ i uses his short-term private key ti to reconstruct the sub-key Kj as follows:

(a) checks the time stamp T;

(b) computes   q z i t j i j mod ,   and     i j i j i j i j j tCert tCert z H z f , , , , ,    ; (c) calculates a sub-key:     q i j j i j i j i j j j Z z f z z z f K        , , , , 1 1 1 1 (6)
(d) checks if the following equality is fulfilled:

    j j j d c j j j T g       (mod p) ( 7
)
where

  T H c j j      j j j j c K T G d      , , , .
If it holds, a user Ui accepts a sub-key Kj = j K  and sets Vi,j = 'Step4:success'. Otherwise, a participant Ui sets Vi,j = 'Step5:failure'. For both cases the participant Ui computes the credentials:

  T V z H r j i i k i k , , , , ,  , k = 1, …, n; k ≠ i, (8)
and broadcasts a tuple rMi,j = (Vi,j, r1,i, …, ri-1,i,, ri+1,i, …, rn,i, T).

3.6

Step 6: Fault detection All faults messages broadcasted by participants in steps 4 and 5 should be verified and corrected. Each participant Uj, which does not follow the protocol in any way, should be treated as possible malicious participants and marked as Vi,j = 'StepX:failure' in the verification matrix, where X = 4 or 5. Such approach is reasonable, because any malicious participant Uj can try to send the wrong evidences to other participants and disrupt the establishment of a conference key among the honest participants. The broadcast messages of possible malicious participants are re-verified by honest participants. The broadcast messages of participants are verified in both secret distribution and commitment step (Step 4) and the sub-key computation and verification step (Step 5). Therefore, the fault messages in the FF-PA protocol that are sent by any malicious participant to other participants should be re-verified by honest ones.

Before the proper fault detection phase is started, each participant Ui (1 ≤ i ≤ n) on receiving the message vMj,m or/and rMj,m (see respective Step 4 and Step 5), first computes (for i ≠ j ≠ m):

    T V q y H h m j t j j i i , , mod , ,   , (9)
or/and

    T V q H r m j t j j i i , , mod , ,    , (10)
and then verifies whether holds the equations To detect and correct the faults, each participant U U i  (i ≠ j ≠ m) receiving Vj,m acts in accordance to the following rules (compare also [START_REF] Ermiş | An improved conference-key agreement protocol for dynamic groups with efficient fault correction[END_REF][START_REF] Huang | A conference key agreement protocol with fault-tolerant capability[END_REF][START_REF] Lee | An Enhanced Fault-Tolerant Conference Key Agreement Protocol[END_REF]): 7)); if Eq. ( 7) holds, sets Uj as a malicious participant, otherwise, the malicious one is Um.

(c) removes the malicious participant (Ui or Um) from the group U, i.e., the set of users is updated as U = U \ {Uj}; similar operations are made by the other honest participants and finally the protocol is restarted.

Step 7: Conference-key computation

If no more faults are detected and all malicious participants are excluded from U, each honest participants Ui in the set of

  m i i i U U U U , 2 , 1 , , , ,   
, where n m  , may cal- culate the conference key K as follows:

  q K K K K m i i i mod , 2 , 1 ,      (11)

Security Analysis

In this section, we give the security analysis of FF-ACKA protocol in fault tolerance and its forward secrecy. In the paper, a formal security analysis of the protocol is omitted. The formal analysis includes protocol resistance to passive and active attacks. Because of the similarity of the structures of the FF-ACKA and DCKAP [START_REF] Ermiş | An improved conference-key agreement protocol for dynamic groups with efficient fault correction[END_REF] protocols, the security proof is similar to analysis presented in [START_REF] Ermiş | An improved conference-key agreement protocol for dynamic groups with efficient fault correction[END_REF][START_REF] Tseng | A communication-efficient and fault-tolerant conference-key agreement protocol with forward secrecy[END_REF].

For the fault tolerance analysis of FF-ACKA protocol we use the same approach as given in [START_REF] Tzeng | A secure Fault-Tolerant Conference-Key Agreement Protocol[END_REF][START_REF] Ermiş | An improved conference-key agreement protocol for dynamic groups with efficient fault correction[END_REF][START_REF] Huang | A conference key agreement protocol with fault-tolerant capability[END_REF]]. Let's consider two general attack scenarios on FF-ACKA protocol (compare also [START_REF] Lee | An Enhanced Fault-Tolerant Conference Key Agreement Protocol[END_REF]). In the first scenario, all participants may generate different conference while in second one the honest participants can be excluded from the conference. Furthermore, we assume that an adversary A is able to alter the exchanged messages in the sub-key computation and verification phase.

Given the first scenario, the participant Ui is a malicious participant who sends a wrong message tMj (Step 4) or Mj (Step 5). Suppose, that one of the honest participants Uj broadcasts message Vj,i='Step4:failure' or Vj,i='Step5:failure' after verifying the digital signature tCertj (Eq. ( 3)) or i  (Eq. ( 8)). However, an adversary A modifies the intercepting message Vj,i='Step4:failure' or Vj,i='Step5:failure' to Vj,i='Step4:success' or Vj,i='Step5:success' and broadcasts it to other participants. As a result, all participants compute and accept different conference keys.

For the second scenario, both Ui and Uj are honest participants in the set U. In Step 4 or Step 5 the participant Uj verifies receiving message tMj (Step 4) or Mj (Step 5). If check holds, Uj broadcasts Vj,i='Step4:success' or Vj,i='Step5:success'. However, like as in the first scenario, any adversary A can intercept this message and modify it to Vj,i='Step4: failure' or Vj,i='Step5: failure'. It is obvious that all participants start the fault detection procedure and although the participants Ui is honest all participants remove it from the set of honest participants. Of course participant Ui should be removed from a set of honest participants, but only if Ui is indeed a malicious participant and sends out the fake message Vi,j='Step4: failure' or Vi,j='Step5: failure', declaring Uj who is actually honest as a malicious one.

In the following theorem, we demonstrate that the proposed protocol can provide fault tolerance.

Theorem 1 (Fault tolerance, [START_REF] Tzeng | A secure Fault-Tolerant Conference-Key Agreement Protocol[END_REF][START_REF] Ermiş | An improved conference-key agreement protocol for dynamic groups with efficient fault correction[END_REF][START_REF] Lee | An Enhanced Fault-Tolerant Conference Key Agreement Protocol[END_REF]). If honest participants follow the protocol, they may compute the same conference key even if: (i) A malicious participant cheats the honest participants by sending wrong key values, and (ii) A malicious participant cheats the honest participants by identifying an honest participant as a possible malicious participant.

Proof. For the first condition, assume that the participant Ui is a malicious participant and attempts to disrupt the establishment of a conference key among honest participants.

    i i i d c i i i T g       (mod p), where   T H c i i ,    and   i i i i c K T G d      , , ,
, holds or not.

If the i K value is wrong the validations do not hold, and so any honest participant Uj can claim that Vj,i='Step5:failure'.

Additionally, for both above presented forgeries assume that one of the honest participant Uj broadcasts message Vj,i = 'Step4: failure' or Vj,i = 'Step5:failure' after verifying the wrong message tMi or Mi. However, an adversary A can intercept the message vMj,i or rMj,i sent by Uj and modify this message to Let's take a closer look at above described adversary attack. It is easy to see that this type of attack is detected in the early stage of the fault detection phase. To show this, suppose that an adversary A replaces i j

V

, with

    j j j g h j j j tCert y V T g  (mod p) (see point (a) of
Step 6) or messages Mj and (j, aj, Kj) according to the point (b) of Step 6. The information about any malicious attempt of Ui or an adversary A who eavesdrops on the broadcast channel and tries to alter the exchanged messages in Step 4 or Step 5, is placed in Vj,i element of the verification matrix, for all 1 ≤ j ≤ n, j ≠ i. On receiving such fault messages, all honest participants start the fault detection phase and decide that Ui is indeed malicious participant. As a result, a participant Ui will be proved to be the malicious participant and then be removed from the set of honest participants. Now, consider second condition (ii). Since in this case, where any honest participants Ui and Uj follow the protocol and broadcast valid messages, all participants can properly compute the same sub-key Ki. This is truth even if a malicious participant Um sends out the failure message to convince other honest participants that Ui and Uj are dishonest or if an adversary A intercepts the message Because these two conditions hold, our FF-ACKA protocol satisfies the fault-tolerance property. The last security property in this section is the forward secrecy. Below, we demonstrate that the proposed protocol has the forward secrecy property. Forward secrecy should protect the previously established conference keys and all its components against compromises, even if the long-term private key is compromised.

Theorem 2 (Forward secrecy, [START_REF] Tseng | An improved conference-key agreement protocol with forward secrecy[END_REF]) If solving the discrete logarithm problem is computationally infeasible, the FF-CKAP provides forward secrecy.

Proof. The proof of Lemma 2 is similar to the proof of [START_REF] Tseng | An improved conference-key agreement protocol with forward secrecy[END_REF]. Suppose that adversary A compromises at time ( + 1) the long-term private key i x of any participant Ui and can obtain the conference key K at time , where K is composed of all participants' subkeys Ki (1 mod q (see respective Eq. (1) and Eq. ( 4)). For the first case, it is obvious that the calculation of j t is equivalent to solving the discrete logarithm problem. However, DL problem is nevertheless considered to be computationally hard. For the second case, even if the adversary knows j x , the solving of     j j j j j j g h x v t tCert    mod q to obtain j t is also discrete problem [START_REF] Chatterjee | Galindo-Garcia Identity-Based Signature Revisited[END_REF]. In the last case, the adversary with Uj's secret key The value j  (like j tCert ) is short signature computed using a signature scheme con- sidered in [START_REF] Chatterjee | Galindo-Garcia Identity-Based Signature Revisited[END_REF]. According to Theorem 1 in [START_REF] Chatterjee | Galindo-Garcia Identity-Based Signature Revisited[END_REF] this signature scheme is existentially unforgeable under a chosen message attack in the random oracle model, assuming that DL problem is believed to be computationally hard. As a result, the proposed protocol FF-CKAP satisfies the forward secrecy under the difficulty of computing the discrete logarithm problem.

 i  n). Because each Ki is distributed to other participants Uj (1  j  n, j ≠ i)

Conclusion

In this paper, we proposed an improved authenticated conference-key agreement protocol (FF-ACKA) for a static set of participants. The protocol provides important security properties like forward secrecy and fault-tolerance. Due to the last properties it is possible to ensure that all participants can obtain the same conference key. The proposed protocol uses only two rounds to generate a conference key and enables the efficient detection and elimination of malicious participants from the set of honest participants. Nevertheless, the size of messages exchanged during protocol is proportional to the number of participants.

The FF-ACKA protocol was developed to meet requirements that emerged while we have been developing MobInfoSec project [START_REF] El Fray | Practical authentication protocols for protecting and sharing sensitive information on mobile devices[END_REF][START_REF] El Fray | Protection Profile for Secure Sensitive Information System on Mobile Devices[END_REF][START_REF] Hyla | Certificate-Based Encryption Scheme with General Access Structure[END_REF][START_REF] Hyla | A practical certificate and identity based encryption scheme and related security architecture[END_REF][START_REF] Hyla | Implicit and explicit certificates-based encryption scheme[END_REF]. We have needed an authenticated conference channel between mobile devices. We have achieved such channel using several one-to-one channels with a chairman. Such solution was working, but it was not scalable and generated some efficiency and security issues related to the service implementing a chairman role. The FF-ACKA protocol is designed to solve that two problems: to improve overall speed and to improve security by eliminating the necessity to have trust service that plays a chairman role. Preliminary analysis has shown that our protocol should have similar efficiency or in some situations should be faster than protocols proposed by [START_REF] Tzeng | A secure Fault-Tolerant Conference-Key Agreement Protocol[END_REF][START_REF] Ermiş | An improved conference-key agreement protocol for dynamic groups with efficient fault correction[END_REF][START_REF] Katz | Scalable protocols for authenticated group key exchange[END_REF][START_REF] Lee | An Enhanced Fault-Tolerant Conference Key Agreement Protocol[END_REF]. We are planning to implement the protocol during our future works and test it in several practical scenarios.

  each U group member.

  really issued by Uj, i.e., Ui verifies the time stamp T, computes

  are satisfied, then Ui starts the execution of the fault detection phase, or else, sets Uj as a malicious participant and restarts the protocol for new honest participant group U = U \ {Ui}.

o

  (a) if Vj,m = 'Step4failure' for any participant Um, then other honest participants Ul, where 1 ≤ l ≤ n, re-verify the broadcast messages tMm and if the verification result is still Vl,m = 'failure:Step4' (for any participant Ul), the participant Ul sets Um as a malicious participant and goes to the step (c); (b) otherwise, if Vj,m = 'Step5:failure', the participants Ui knows that according to Uj the source of faulty is Um (m ≠ i); hence Ui: (i) waits for the fault detection message (m, am, Km) from Um; (ii) sets Um as a malicious participant and goes to the step (c), if no one receives the fault detection message from Um; (iii) checks whether previously distributed values (Vm, Tm, ) are correct, i.e.: o checks whether m satisfies p checks whether Eq. (1) holds for Vm, Tm and m tCert ; o inputs (am, Km) into Eq. (4), calculates ) is the right signature on a sub-key Km made by Um (see Eq. (

  Step5:success', and then broadcasts it to all other participants.

  success' sent from Ui and changes it to failure'. It can be noticed, that as above, these attacks are detected in fault detection phase.

  The malicious participant Ui can use two methods of attacks. In first one, Ui broadcasts wrong messages in Step 4 or Step 5, while in second one Ui broadcasts the message Vi,j='Step4: failure' or Vi,j='Step5:failure' to claim that Uj is a malicious participant, although Uj is indeed a honest participant. If Ui tries to cheat other honest participants in Step 4, then the broadcast messages tMi = ( , holds or not. If the message tMi of Ui is wrong, at least one honest participant Uj (j ≠ i) is able to claim Vj,i='Step4:failure', because the wrong messages tMi are unable to pass the validation. If Ui broadcasts wrong messages Mi in Step 5, each honest participant Uj can also validate the message Mi and concludes if the equations

	i tCert ,	i tCI , i T , i V , T,   ) are validated by each honest participant by checking
	whether	g	tCert	i		i T	 V i	  i y	i h	 i g	(mod p), where	h i		H	 tCI	i	V i ,	,	T		,	g	i		G	 T i	,	T	,	tCI	i	,	i h	

.

  In the second method of attacks, a malicious participant Ui broadcasts the message Vi,j='Step4: failure' or Vi,j='Step5:failure' to claim that Uj is a malicious participant, while Uj is actually an honest participant. In such case, Uj resends message tMj (for Step 4) or Mj and (j, aj, Kj) (for Step 5) to prove his honesty. Next, other honest participants validate message tMj by checking

																																					V	 and resends it to all other partici-
																																					j	,	i
	pants. On receiving	V	i  and j ,	k h	j , (Eq. (4)) or	k r	j , (Eq. (8)), any Uk (k ≠ i ≠ j ) first
	computes		h k 	,	j		H	   y j	t	k	mod	q	,	V	j  ,	i	,	T		or	k r 	,	j		H	 z	k	,	j	,	V	j  ,	i	,	T		and checks whether
	k h 	j , 	k h	,	j	or	k r 	j , 		k r	,	j		holds or not. It is obvious that if these equations holds, an
	adversary should be able to compute	w k	j , 	  T k	x	j	mod	q	or	z	k	,	j		j   	t	k	mod	q	.
	However, it is well known that a problem of finding	k w	j , or	z	k	j , values is computa-
	tionally hard, i.e., to obtain these values we need to solve DL problem for the equations
	y	j		g	x	j		mod	p	and	T k		g	t	k	mod	p	or		j		g j 	mod	p