Bernd Malle
email: b.malle@hci-kdd.org

Peter Kieseberg
email: pkieseberg@sba-research.org

Edgar Weippl

Andreas Holzinger

The right to be forgotten: Towards Machine Learning on perturbed knowledge bases

Keywords: Machine learning, knowledge bases, right to be forgotten, perturbation, anonymization, k-anonymity, SaNGreeA, information loss, structural loss, cost weighing vector, interactive machine learning

Today's increasingly complex information infrastructures represent the basis of any data-driven industries which are rapidly becoming the 21st century's economic backbone. The sensitivity of those infrastructures to disturbances in their knowledge bases is therefore of crucial interest for companies, organizations, customers and regulating bodies. This holds true with respect to the direct provisioning of such information in crucial applications like clinical settings or the energy industry, but also when considering additional insights, predictions and personalized services that are enabled by the automatic processing of those data. In the light of new EU Data Protection regulations applying from 2018 onwards which give customers the right to have their data deleted on request, information processing bodies will have to react to these changing jurisdictional (and therefore economic) conditions. Their choices include a re-design of their data infrastructure as well as preventive actions like anonymization of databases per default. Therefore, insights into the effects of perturbed / anonymized knowledge bases on the quality of machine learning results are a crucial basis for successfully facing those future challenges. In this paper we introduce a series of experiments we conducted on applying four different classifiers to an established dataset, as well as several distorted versions of it and present our initial results.

Introduction and Motivation for Research

Privacy aware machine learning [START_REF] John C Duchi | Privacy aware learning[END_REF] is an issue of increasing importance, fostered by anonymization concepts like k-anonymity [START_REF] Samarati | Protecting respondents identities in microdata release[END_REF], in which a record is released only if it is indistinguishable from k other entities in the data set. However, k-anonymity is highly dependent on spatial locality in order to effectively implement the technique in a statistically robust way, and in arbitrarily high dimensions data becomes sparse, hence, the concept of spatial locality is not easy to define. Consequently, it becomes difficult to anonymize the data without an unacceptably high amount of information loss [START_REF] Charu | On k-anonymity and the curse of dimensionality[END_REF]. Therefore, the problem of kanonymization is on the one hand NP-hard, on the other hand the quality of the result obtained can be measured at the given factors: k-anonymity means that attributes are suppressed or generalized until each row in a database is identical with at least k -1 other rows [START_REF] Sweeney | Achieving k-anonymity privacy protection using generalization and suppression[END_REF]; l-diversity as extension of the k-anonymity model reduces the granularity of the data representation by generalization and suppression so that any given record maps onto at least k other records in the data [START_REF] Machanavajjhala | Muthuramakrishnan Venkitasubramaniam. l-diversity: Privacy beyond k-anonymity[END_REF]; t-closeness is a refinement of l-diversity by reducing the granularity of a data representation, and treating the values of an attribute distinctly by taking into account the distribution of data values for that attribute [START_REF] Li | t-closeness: Privacy beyond k-anonymity and l-diversity[END_REF]; and delta-presence, which links the quality of anonymization to the risk posed by inadequate anonymization [START_REF] Nergiz | delta-presence without complete world knowledge[END_REF], but not with regard to the actual security of the data, i.e., the re-identification through an attacker. For this purpose, certain assumptions about the background knowledge of the hypothetical enemy must be made. In this work, we are going to measure the effects of the anonymization of knowledge bases on the performance of machine learning algorithms in order to give valuable feedback to data holders and anonymization providers.

Another challenge for data processing entities is increasingly imposed on them by the law. At least within the European Union, where a new Data Protection Reform will apply from 2018 onwards, customers are given a right to be forgotten, which means that an organization is obligated to remove a customer's personal data upon request. Since information in a modern, data driven infrastructure is not only usable for the customer herself, but also constitutes the basis for machine learning algorithms providing better insights and services, this information loss might be problematic, if only in competition with companies / organizations which do not fall under such jurisdiction. The ability to quantify the effects of information loss by erasure of sensitive data is therefore of great importance and the other core focus of our work.

Scenarios of incurring information loss in datasets

Selective perturbation

Within a modern information infrastructure, several layers of data storage and processing might be affected by the right to be forgotten. The first and probably most benign impact would be the one on so-called Front-End databases; those are customer-facing databases on the backend which handle the bulk of day-to-day data transmissions and contain the customer's data in full detail. Erasing a data entry from this Front-end is therefore simple and of manageable consequences.

The second layer impacted by data erasure are archival and backup systems, which are necessary in case of failures on the Front-end. Although data erasure does not pose any technical problem here either, it is necessary to consider it on an organizational level in order to not inadvertently re-introducing already "forgotten" items.

Significant problems are to be expected when executing selective data erasure on statistical databases or knowledge bases prepared for machine-learning. Both kinds of DBs will usually not hold the original user information but merely statistically relevant fragments of it; this difficulty is compounded by the fact that in many cases it might not be technically necessary to even store a link to the original data. In such cases is it not only impossible to delete the relevant fragments from such data stores (not to mention the statistical / parametric results obtained by algorithms working on them), but the whole databases might have to be recreated upon every user deletion request. It is therefore absolutely crucial to have an insight into the results of potential data perturbation, if only to be able to redesign (parts of) an information infrastructure.

Tabular anonymization

Figure 1 illustrates the original tabular concept of anonymization: Given an input table with several columns, we will in all probability encounter three different categories of data:

-Personal identifiers are data items which directly identify a person without having to cross-reference or further analyze them. Examples are first and last names, but even more so an (email) address or social security number (SSN). As personal identifiers are dangerous and cannot be generalized (see Figure 2) in a meaningful way (e.g. one could generalize an email address by only retaining the mail provider fragment, but the result would not yield much usable information), this category of data is usually removed. The table shows this column in a red background color. -Sensitive data, also called 'payload', which is the kind of data we want to convey for statistics or research purposes. Examples for this category would be disease classification, drug intake or personal income level. This data shall be preserved in the anonymized dataset and can therefore not be deleted or generalized. The table shows this column in a green background color. -Quasi identifiers (QI's), colored in the table with an orange background, are data that in themselves do not directly reveal the identity of a person, but might be used in aggregate to reconstruct it. For instance, [START_REF] Sweeney | k-anonymity: A model for protecting privacy[END_REF] mentioned that 87% of U.S. citizens in 2002 had reported characteristics that made them vulnerable to identification based on just the 3 attributes zip code, gender and date of birth. But although this data can be harmful in that respect, it might also hold vital information for the purpose of research (e.g. zip code could be of high value in a study on disease spread). The the actual point of all anonymization efforts is therefore to generalize this kind of information, which means to lower its level of granularity. As an example, one could generalize the ZIP codes 41074, 41075 and 41099 to an umbrella version 410**, as shown in Figure 3. As described in [START_REF] Ciriani | κ-anonymity[END_REF], k-anonymization requires that in each data release every combination of values of quasi-identifiers must be identical to at least k -1 other entries in that release, which can be seen as a clustering problem with each cluster's (also called equivalence class) quasi-identifier state being identical for every data point. This can be achieved via suppression and generalization, where suppression means simply deletion, whereas in generalization we try to retain some usable value.

The process of generalization works through a concept called generalization hierarchies, which form a tree, whose root denotes the most general value available for an attribute (usually the 'all' value) and then branches to more and more specific occurrences, with its leafs representing the set of exact, original values (see Figure 2). In generalizing the original input value, one traverses the tree from the leaf level upwards until a prerequisite is fulfilled. Usually, this comes in the form of the k-anonymity requirement, so that we want to find a group of other data entries whose generalized QI's match the data point being processed.

Each level of generalization involves a certain cost in information loss, so we do not want to construct our clusters in any random sequence but minimize the overall information loss [START_REF] Aggarwal | Approximation algorithms for k-anonymity[END_REF]. This makes k-anonymization an NP-hard problem due to an exponential number of possible generalized QI combinations.

Graph (social network) anonymization

Hitherto we were solely concerned with tabular data; however, as social networks have gained huge popularity over the previous decade, and are widely applicable in other areas as well, the question of how to efficiently anonymize networks has gained ever more significance over the years.

As a start, one could see a graph just as a collection of nodes, where each node contains some kind of feature vector, akin to the row in a data table. Adopting that view, we could be tempted to simply ignore the existence of edges and apply some kind of algorithm suitable to the anonymization of tabular data. The main problem with this however lies in the fact that the structural environment of a node (the constellation of its neighbors within the greater network) provides some additional information. That is, even if we successfully (k-)anonymize the feature vectors of a graph according to the methods described in the previous chapter, we still run the risk of too much information remaining in the form of a known local subgraph structure. Consider Figure 4 for example, in which the nodes of a graph have already been k-anonymized into groups of size 3 and 7, respectively. In this figure, local subgraphs b) and c) are actually (3)-anonymized, because as each node has the exact same local neighborhood structure, the additional information of a node possessing a degree of 0 (or 2) is of no additional value. For local subgraphs a) and d) on the other hand, the additional information of a node being of degree (x) has the potential to reveal its identity, meaning it is not indistinguishable from its neighbors within the equivalence class any more.

Several methods have been proposed to make re-identification of nodes in anonymized social graphs harder. [START_REF] Chester | k-anonymization of social networks by vertex addition[END_REF] for example introduce the idea of vertex addition to labeled and unlabeled datasets. While an algorithm on the former remains NP complete, they provide an efficient (O(nk)) algorithm for unlabeled data. Experimenting on several well known datasets, they show that commonlystudied structural properties of the network, such as clustering coefficient, are only minorly distorted by their anonymization procedure. Person re-identification is both a hard and important problem in many different domains and is challenging. Most approaches aim to model and extract distinctive and reliable features. However, seeking an optimal and robust similarity measure that quantifies a wide range of features against realistic conditions from a distance is still an open and unsolved problem for person re-identification techniques [START_REF] Zheng | Reidentification by relative distance comparison[END_REF].

In order to develop protection techniques in social networks it is necessary to consider three aspects [START_REF] Zhou | A brief survey on anonymization techniques for privacy preserving publishing of social network data[END_REF]: 1) the privacy information which may be under attack; 2) the background knowledge that an adversary may use to attack the privacy of target individuals; and 3) a specification of the usage of the published social network data so that an anonymization method can try to retain the utility of the data as much as possible whilst the privacy is preserved.

The authors of [START_REF] Kapron | Social network anonymization via edge addition[END_REF] take the approach of adding edges to an edge-labeled graph like the Netflix movie database (with users and movies being nodes and edge weights representing movie ratings). They define tables as bipartite graphs and prove NP-hardness for the problems of neighborhood anonymity, i-hop anonymity and k-symmetry anonymity.

Campan [START_REF] Campan | Data and structural k-anonymity in social networks[END_REF], whose local subgraph problem we already encountered, proposed a solution in the form of a greedy clustering algorithm which takes into account not only the information loss incurred by generalizing features of nodes, but also introducing a structural loss function based on the local neighborhood within an equivalence class (and between them). The author of this thesis implemented that approach utilizing GraphiniusJS and will demonstrate the algorithm in Section 3.2 as well as the anonymized results in Section 4.

Experiments

The following sections will describe our series of experiments in detail, encompassing the data source selected, the algorithm used as well as a description of the overall process employed to obtain our results.

Data

As input data we chose the adults dataset from the UCI Machine Learning repository which was generated from US census data of 1994 and contains approximately 32,000 entries; from those 30,162 were selected after preprocessing. Of the attributes (data columns) provided only one was deleted because it was also represented by a column containing its numerical mapping (education => education num). Figure 5 shows the attribute value distribution of the original input dataset with the exception of the sample weights. As one can see, there are several attributes with one value clearly dominating the others; native-country being the most prominent example with the entry for the United States dwarfing all other countries (which comes as no surprise given the data origin). As anonymization generalizes different countries together if necessary, it was interesting for the author to see how these distributions would change under a relatively large k-factor. Figure 6 shows the same attribute distribution with its values anonymized by a factor of k = 19. Although the dominance of the United states was successfully "broken" by this method, in several instances the generalized-to-all -value (*) now skews the data set even more. Apart from the expected generalization information loss this is another reason why one would assume worse results from a machine learning classifier applied to an anonymized dataset.

Algorithm

SaNGreeA stands for Social network greedy clustering and was introduced by [START_REF] Campan | Data and structural k-anonymity in social networks[END_REF]. In addition to 'clustering' nodes of a graph according to the minimum general information loss (GIL) incurred as described in Section 2.2, this algorithm also considers the structural information loss (SIL) incurred in assigning a node to a certain cluster. The SIL quantifies the probability of error when trying to reconstruct the structure of the initial graph from its anonymized version.

GIL(cl) = |cl| • ( s j=1 size(gen(cl)[N j ]) size(min x N (X[N j ]), max x N (X[N j ])) + t j=1 height(Λ(gen(cl)[C j ]))
height(H Cj ) )

where: -|cl| denotes the cluster cl's cardinality; -size([i1, i2]) is the size of the interval [i1, i2], i.e., (i2 -i1); -Λ(w), w H Cj is the sub-hierarchy of H Cj rooted in w; -height(H Cj ) denotes the height of the tree hierarchy H Cj ;

The total generalization information loss is then given by:

GIL(G, S) = v j=1 GIL(cl j )
And the normalized generalization information loss by:

NGIL(G, S) = GIL(G, S) n • (s + t)
The SIL is composed of two different components: 1) the intra-cluster structural loss, signifying the error probability in trying to reconstruct the original edge distribution within an equivalence class (= anonymized cluster), and 2) the inter-cluster structural loss which represents the error probability in trying to reconstruct the original configuration of edges between two equivalence classes.

For the exact mathematical definitions of SIL & NSIL the reader is kindly referred to the original paper. Because the structural information loss cannot be computed exactly before the final construction of clusters, the exact computations were replaced by the following distance measures:

Distance between two nodes: dist(X i , X j ) = |{l|l = 1..n ∧ l = i, j; b i l = b j l | n -2
Distance between a node and a cluster:

dist(X, cl) = X j cl dist(X, X j ) |cl|
The algorithm starts with initializing a first cluster by a randomly choosing a node. Then, for every new node encountered, the weighted sum of the above two information loss metrics will yield a certain overall information loss in case the node was added to that cluster -the candidate with minimal information loss is then added to the cluster. This process is repeated until the cluster reaches a certain constraint (e.g. size := k -factor) upon which another random node is chosen to constitute the next cluster. This procedure is repeated until all nodes have been assigned; if a cluster of size < k should remain, its member nodes are dispersed accordingly.

Since the algorithm does not take all possible node combinations into account, but simply chooses an arbitrary node and compares all the candidates in a loop, the algorithm runs in quadratic time w.r.t. the input size in number of nodes. This worked well within milliseconds for a problem size of a few hundred nodes, but took up to 60 mins. on the whole adult dataset.

In implementing and demonstrating this algorithm, the authors intended to recreate the original paper's experiment. However, as no suitable real-world graph structure was available to the authors at the time of this writing and any artificially generated network would result in dubious results for the classification tasks applied, we decided to leave out the structural component of the algorithm and focus only on the generalization information loss for this paper, leaving the entire approach to future research initiatives.

Process

To examine the impact of perturbation and anonymization of datasets on the quality of a classification result, we designed the following processing pipeline:

1. Taking the original (preprocessed) dataset as input, we transformed its attributes to boolean values, so instead of native-country -> United-States we considered United-States -> yes / no. 2. We then ran 4 different classifiers on it and computed precision, recall as well as F1 score. The four classifiers used were gradient boosting, random forest, logistic regression and linear SVC. 3. From the obtained results we extracted the 3 attribute values most contributing to a "positive" (>50k) result as well as the top 3 attribute values indicating a "negative" (<=50k) prediction as depicted in Figure 7 4. For each of these 6 attribute values, we subsequently deleted a specific percentage of data rows containing that value from the original dataset, resulting in 30 reduced datasets. The 5 percentages used were 0.2, 0.4, 0.6, 0.8 as well as 1.0. 5. To each of those datasets we re-applied the four chosen classifiers successively and recorded the respective impact on the quality of the classification result.

The results can be seen in Figure 9 and Figure 10.

6. In order to measure the effects of k-anonymization on classifier performance, we used the SaNGreeA's GIL component described in the following section to generate datasets with a k-factor of k = 3, k = 7, k = 11, k = 15 as well as k = 19. Furthermore, we used each of these settings with 3 different weight vectors: 1) equal weights for all attributes, 2) age information preferred (ω(age) = 0.88, ω(other attributes) = 0.01) and 3) race information preferred (ω(race) = 0.88, ω(other attributes) = 0.01). We then re-executed all classifiers on the resulting 15 datasets and recorded the respective results, which can be seen in Figure 8.

Results & Discussion

We expected a steady decline in the quality of classification results over all three scenarios: 1) anonymization of datasets, 2) perturbation by selectively deleting attribute values of positive significance w.r.t the result, 3) perturbation by selectively deleting attribute values of negative significance w.r.t the result. The actual results satisfied our expectations only in the first two cases, with the shape of the actual outcomes being a little bit surprising. As can be seen in Figure 8, the F1 score of all algorithms applied declines more drastically at the beginning, with more benign further losses as the k-factor of anonymization increases. Whereas the F1 curves for gradient boosting, linear SVC and logistic regression approximate a 1/x curve, the random forest classifier reacts more sensitively to even slight anonymization, but seems to stay more robust with higher values of k.

Considering the exact performance, Linear SVC and logistic regression yielded the worst outcomes under anonymization, which is not further surprising given their lower scores on the original input data to begin with.

As far as the second case is concerned (Figure 9), our experiments showed the expected drop in algorithm performance, although the impact shows a different behavior: In the case of deleting rows with capital gain values of > 2000 US-Dollars, the decline seems to be linear, whereas for the other two attribute values the performance seems to collapse with higher rates of erasure. Moreover, this behavior is more or less the same for all applied algorithms. This seems to point to the fact that especially significant attribute values can uphold a good performance even in low quantities.

The only real surprise occurred with applying our classifiers to the datasets perturbed by deleting percentages of attribute values indicating a low yearly income (Figure 10). As with scenario 2 we expected to see a progressive decline in performance -but with all classifiers the results either stayed approximately the same or even improved in some cases (please consider the extremely narrow scale in the respective plots). As the classification score is dependent on (in-)correctly classifying both positive and negative outcomes, this seems rather surprising and will require further investigation. -Find a natural dataset which already contains a graph structure emerged in the real-world rather than a graph generator. We assume that for many modern applications the experiments conducted in this work would be highly relevant to social network analysis and anonymization, and we are planning to conduct such a research effort in a sequel to this investigation. -Consider the structural information loss on a suitable real-world graph and re-apply our methodology to that data-structure. Once realistic results have been obtained, the effects of the same algorithm on artificially generated graphs might be examined, offering another perspective on the information content / structure introduced into datasets by different types of such generators. -Analyze the exact influence different kinds of information loss due to anonymization / perturbation have on the different algorithms. In this work, we have only chosen a series of classifiers to demonstrate our approach. However, other classes of machine learning algorithms might yield interesting results as well, and we are motivated to conduct such future research ourselves. -Interactive machine learning. We have, amongst other settings, experimented with different weight vectors in our approach regarding anonymization. However, such parameters do not easily lend themselves to be produced by an algorithm, since minimizing an artificial metric of information loss does not produce safe datasets in itself. Moreover, data utility is highly dependent on the specific area of application; therefore choosing parameters with regard to the particular demographic and cultural clinical environment is best done by a human agent. The problem of (k-)anonymization thus represents a natural application domain for interactive Machine Learning (iML) with a human-in-the-loop [START_REF] Holzinger | Interactive machine learning for health informatics: When do we need the human-in-the-loop?[END_REF], [START_REF] Kieseberg | A tamper-proof audit and control system for the doctor in the loop[END_REF], [START_REF] Holzinger | Towards interactive machine learning (iml): Applying ant colony algorithms to solve the traveling salesman problem with the human-in-the-loop approach[END_REF]. The authors will strive to design and implement such experiments in the future.

Conclusion

This paper examined the question of how different ways of perturbing or anonymizing knowledge bases would influence the results of machine learning algorithms applied to those datasets. We have seen that newly introduced regulations (inside the European Union) as well as data privacy concerns of database owners naturally lead to the challenge of minimizing the cost / efficiency impact of those requirements not only on the technical, but also the machine learning infrastructure of affected businesses and organizations. Consequently, we conducted a series of experiments to simulate the decline in the F1 score of several clas- sification algorithms on an established dataset. Our results show that selective deletion of valuable data items is less destructive than general anonymization, so that complying with regulations concerning the "right to be forgotten" is still preferable to taking preemptive steps to de-identify personal information in databases. Our results are highly selective however and should be corroborated by applying a wider spectrum of algorithms to larger, more diverse datasets.

Fig. 1 .Fig. 2 .

 12 Fig. 1. The three types of data considered in (k-)anonymization

Fig. 3 .

 3 Fig. 3. Tabular anonymization: input table and anonymization result

Fig. 4 .

 4 Fig. 4. Local subgraph neighborhoods as additional anonymization obstacle. (Example taken from [3].)

Fig. 5 .

 5 Fig. 5. Initial distribution of six selected data columns of the adult dataset.

Fig. 6 .

 6 Fig. 6. Anonymized distribution of six selected data columns of the adult dataset, anonymization factor of k=19, equal weight for each attribute.

Fig. 7 .

 7 Fig. 7. The attribute values of the adult dataset which contribute most positively / negatively to the classification result. The columns to the right strongly indicate a yearly income of above 50k, whereas the columns to the outer left indicate a yearly income of below 50k. The least significant columns in the middle part were cut out.

Fig. 8 .

 8 Fig. 8. The impact of anonymization on the F1 score of different classifiers

Fig. 9 .

 9 Fig. 9. The impact of perturbation (selectively deleting quantiles of rows containing one of the TOP 3 positively contributing attributes) on the F1 score of different classifiers

Fig. 10 .

 10 Fig. 10. The impact of perturbation (selectively deleting quantiles of rows containing one of the TOP 3 negatively contributing attributes) on the F1 score of different classifiers


Yoan Miche

Ian Oliver

Silke Holtmanns

Aapo Kalliola

Anton Akusok

Amaury Lendasse

Kaj-Mikael Björk

Data Anonymization as a Vector Quantization Problem: Control over Privacy for Health Data

This paper tackles the topic of data anonymization from a vector quantization point of view. The admitted goal in this work is to provide means of performing data anonymization to avoid single individual or group re-identification from a data set, while maintaining as much as possible (and in a very specific sense) data integrity and structure. The structure of the data is first captured by clustering (with a vector quantization approach), and we propose to use the properties of this vector quantization to anonymize the data. Under some assumptions over possible computations to be performed on the data, we give a framework for identifying and "pushing back outliers in the crowd", in this clustering sense, as well as anonymizing cluster members while preserving cluster-level statistics and structure as defined by the assumptions (density, pairwise distances, cluster shape and members. . . ).

Introduction

In this paper, we limit ourselves to the problem of user re-identification from a dataset. We decide to focus on two very specific questions: given a set of records with no obvious information that would allow for easily identifying a single person from the dataset, (i) can we make sure that no one is easily identifiable from the data (and identify it), and (ii) if some individuals are easy to identify, can we modify the data so as to "blend them in" while retaining the key characteristics of the data statistics? The approach we take is to consider the data fields (over a set of records) as separate entities and try to build clusters of records based on metric proximity: if the records have similar values accross several vector elements, they are likely to be grouped together. We assume then that if such a group is large enough and that the records inside that group have been "stirred" enough, identification of a single individual becomes impossible. One of the main assumption in this paper is that whatever further processing is to be performed on the anonymized data, is relying on these "group statistics/properties" to be as intact as possible. The proposed "stirring" of the data implies that global data statistics and structures will be preserved, but local ones are disturbed.

We basically want to preserve the underlying manifold structure (in terms of the cluster of data that it is composed of) as much as possible, while locally shuffling the data around. In order to clarify some of the notions presented, we introduce here an example data set of health-related information in Table 1. We consider for the purpose of this example that this represents the full health records from a certain medical institution. The records from Table 1 show no obvious easily identifiable information when considering single fields. Nevertheless, relationships between the non-sensitive fields in this data can probably make it relatively easy to identify some individuals: within a zip code, the nationality and the age allow someone to restrict the set of possible individuals dramatically. The last individual in the table is even more striking as her age, nationality and zip code surely make her stand out of the rest.In such a situation, the proposed approaches in this paper seek to "blend in" this last individual from Table 1 with the rest of the records, as well as making sure that all the records get "shuffled" (regarding each of the fields) so as to make the data anonymized. In effect, we want here to actively modify the data values, not by changing their nature (as would hashing the values do, e.g.) or by omitting them, but really by modifying the values to realistic ones (belonging to the same category/set) in a way that preserves some of the information.

High-Level Motivation for Data Privacy

In this section, we propose a high level description of the problem tackled in this paper. The next sections then describe the proposed means of doing so. In an ideal situation, data mining and classification or partition of data, in particular for health and medical data [START_REF] Kieseberg | A tamper-proof audit and control system for the doctor in the loop[END_REF], can be made in an unambiguous manner; meaning that, for example, a classification of the data can be made and the number of border cases is minimal. Application of algorithms that increase the privacy (or the entropy) of a system distort this in some known manner, in terms of the direct effects on the data fields. For example κ-anonymity [START_REF] Ciriani | κ-anonymity[END_REF] and ℓ-diversity [START_REF] Machanavajjhala | ℓ-diversity: Privacy beyond κ-anonymity[END_REF] reduce the distribution and amounts of unique values in the discrete valued cases; differential privacy [START_REF] Dwork | Differential privacy: A survey of results[END_REF] adds noise in the continuous valued cases, for example, speeds, distances etc. A privacy function distorts a system such that classification and/or mining either cannot be made or becomes difficult to make in a reasonable manner [START_REF] Kieseberg | Protecting Anonymity in Data-Driven Biomedical Science[END_REF].

In this work, we consider the case of such privacy functions that modify the data in such a way as to avoid changing the "format" of the data, and thus the underlying space in which the data lies. Indeed, another way to consider this is that the privacy functions usually alter the underlying space or topology of the space rather than moving the elements themselves. This altering of the topology in the best case involves continuous (in the sense of metric preserving or homotopy preserving) stretching and shrinking, but may also include noncontinuous tearing and creasing of the space such that the resolution of the original metric function is no longer possible. The challenge here is then to avoid this deformation of the underlying space, by attempting to shuffle and move the data around in the best manner (regarding increasing the privacy and minimising the distortions on the data). The work in this paper is aimed at this problem: proposing several practical solutions to the identification problem from Table 1. We first define in the next section, some notations and assumptions on the structure of the data, and first look at the problem of moving a single sample (or a group of them) back into bigger clusters. We then tackle the problem of increasing the privacy for the samples within a cluster so as to make sure that re-identification, even within a cluster, is more difficult.

Methodology for Data Anonymization in a Data

Clustering Context

Some Notational Details

Traditionally in the data privacy literature, one defines a table T of N records as T = {t 1 , . . . t N }, with attributes {A 1 , . . . , A d }. We have that T ∈ Ω, the set of all possible records (samples), and A = {A 1 , . . . , A d } is the set of all possible d attributes (in this case, all possible attributes are used in table T). Typically, one denotes the value of a certain attribute A j for sample t i as t i [A j ]. In this paper, and for the developments below, we take the liberty to note X (j) the set of all possible values for a certain attribute A j . Referring to Table 1 for our example case, if A j is the attribute for the Zip Code of the patients, this means that X (j) represents the set of all possible Zip Codes (possibly limited to the existing ones that make sense within the context of this table, e.g. limited to a country).

We then assume that it is possible to define a distance function d (j) : X (j) × X (j) -→ R + over this set X (j) . Note that the metric space X (j) = (X (j) , d (j) ), defined by these two entities need not be Euclidean. Some considerations on such distance functions over non-Euclidean spaces are detailed in the following section 3.2. Departing slightly from the data privacy notations and denoting by T = [t 1 , . . . , t N ]

T , the matrix of N samples holding the health records. A record t i is now defined as t i = [a i,1 , a i,2 , . . . , a i,d ] , a i,j ∈ X (j) , with X (j) the set considered as part of the metric space X (j) = (X (j) , d (j) ).

With these extended notations, we can see the column [a 1,j , . . . , a N,j ]

T ∈ X (j) N ×1 as a discrete random variable (or a set of realizations of the underlying random variable, more precisely) over X (j) . The following section discusses the previous assumption of being able to define a distance function over a potentially non-Euclidean space.

Distance Functions over non-Euclidean spaces

The argument for considering the use of distances over non-Euclidean spaces in this work, is that it is possible to tweak and modify such non-Euclidean distances so that their distribution and properties will be "close enough" to that of the original Euclidean distance. Most of the developments in this paper rely on having "meaningful and consistent" distance functions across all the dimensions, so that they can be at least compared, even if this means re-mapping the distribution of its values.

More formally, let us assume that we have two metric spaces

X (i) = (X (i) , d (i)
) and X (j) = (X (j) , d (j) ), with X (i) the canonical Euclidean space (i.e. X (i) = R d and d (i) the Euclidean norm) and X (j) a non-Euclidean metric space endowed with a non-Euclidean metric. Drawing uniformly samples from the set X (j) , we form

x (j) = [ x (j) 1 , . . . , x (j) n ]
, a set of values (realizations of the underlying random variable), with x (j) l ∈ X (j) . Denoting then by f d (j) the distribution of pairwise distances over all the samples in x (j) , we assume that it is possible to modify the distribution of the values of the non-Euclidean metric d (j) (into a distribution

f map d (j) ) such that lim n→∞ f map d (j) = f d (i) , (1)
where f d (i) is the distribution of the Euclidean distances d (i) over the Euclidean space X (i) and f map d (j) is a non-linear transformation of the original distribution f d (j) by a certain function.

The limit here is over n as the distribution f d (j) is considered to be estimated using a limited number n of realizations of the random variables, and we are interested in the limit case where we can "afford" to draw as many samples as possible to be as close to the Euclidean metric as possible. That is, that we can make sure that the non-Euclidean metric behaves over its non-Euclidean space, as would a Euclidean metric over a Euclidean space. This assumption is "theoretically reasonable", as it comes down to being able to transform a distribution f d (j) into another f map d (j) , given both. And while this may not be simple nor possible using linear transformation tools, most Machine Learning techniques are able to fit a continuous input to another different continuous output (this is basically the well-known Universal Function Approximator property [START_REF] Cybenko | Approximations by superpositions of sigmoidal functions[END_REF]). It can be noted that using such tools, the mapping will not be perfect (as we will work with discrete versions of the distributions) and will not result in the equality case from Eq. 1. Nevertheless, we assume in this paper that this is sufficient for our needs. With this assumption in mind, we come to the problem of addressing Differential Privacy approaches as a Vector Quantization matter. Quantization problem Using the previous notations introduced, Differential Privacy aims at finding sets or clusters (groups) C l of samples

C l = {t i , t j ∈ T|∀i, j ∈ 1, N , i ̸ = j, ∀k ∈ 1, d , d (k) (a i,k , a j,k ) ≤ ε k } , ( 2
)
with ε k the maximum radii of the cluster C l (each dimension k can have a separate radius, thus). The total number of clusters C is here determined by the choices made for the maximum radii of them, i.e. the ε k . Intuitively, these C l are clusters of samples that are "not too distant from each other". If all the metric spaces (across all dimensions) were Euclidean, Eq. 2 would simply define the sets of samples that have pairwise Euclidean distance smaller than a certain epsilon. In this respect, we are considering similarity between groups of sample as a defined by cluster density across all dimensions. In our case, we generalize this definition by potentially having a different distance function for each dimension, thus bounded by different ε k . Note that samples that are "alone" in their cluster basically represent outliers in terms of the data they hold (and thus, individuals): they might be very easy to identify/recognize out of the rest of the records, as they do not "fit with others". This observation can be generalized to clusters that have "few samples" in the ball they define. "Few" has to be defined, in this case. This is directly related to the κ in κ-anonymity.

Denoting by m, the previous "few", if |C l1 | ≤ m, there are not enough records in the cluster: They might be easy to identify, or represent too obvious a group. The goal is then to modify as few dimensions as possible (so as to minimize distortion of the data) to bring these records in the nearest cluster C l2 which respects |C l2 | > m or so that |C l1 | + |C l2 | > m. To be able to find which nearby cluster is the most fitting for such a lonesome sample, we decide to rely on centroids. We thus need to calculate a centroid (or representative) of the clusters such that |C l | > m. Note that as the sets X (j) across which the data is defined do not necessarily have any implied order, we have to use solely the distances between samples to calculate the most fitting centroid.

This comes to determining the centroid c l of cluster C l with only inter-records distances (pairwise distances for all samples within one cluster):

c (j) l = arg min a k,j ∈X (j)   ∑ ai,j ∈C l d (j) (a i,j , a k,j )   , ( 3
)
where c

(j) l denotes the j-th coordinate of the centroid c l of cluster C l , and Eq. 3 has an abuse of notations in the summation index to avoid too heavy notations: the summation is made over the j-th coordinate a i,j of all the samples t i in cluster C l . This is to avoid defining the set of samples in the cluster formally.

From Eq. 3, it can be seen that the centroid coordinates are picked from the sets X (j) , and not calculated as some mean value over the samples present in the cluster. This would not have any sense in the case of discrete X (j) , so this definition is more practical for the general purpose.

We do not discuss in this paper the algorithmic means of finding such centroids based on this definition from Eq. 3. With the centroids of each cluster estimated, we can then decide how to move samples that are lonesome and too easy to identify.

Moving samples to nearby clusters

The task of moving a sample (or a small enough group of them) into a near cluster first requires the determination of the most suitable cluster for each of these samples.

Identifying the most suitable cluster Intuitively, and in order to preserve data as much as possible, the most suitable cluster C l for this application is such that the total distortion, approximated in this case by how much the outlier t o is moved across all dimensions, is minimal. Thus, denoting by t o = [a o,1 , . . . , a o,d ] an outlier, C = {C k } 1≤k≤C the set of all the clusters (which have a sufficient amount of samples in them), and by d (j) map the mapped version of the distance function d (j) (so that the distribution of its values matches that of an Euclidean metric, see section 3.2), we get

C l = arg min C k ∈C   d ∑ j=1 d (j) map ( a o,j , c (j) k )   . ( 4
)
One argument for using the mapped distances d

(j)
map in this determination of the suitable cluster, is that we have to make a decision over all the dimensions at once, regarding the distortion generated by moving the outlier into a cluster. Therefore, in order to quantify this distortion across all dimensions at once, it is important that the distances are all within similar ranges and following similar distributions (otherwise, some dimensions will be "favoured" by the sum, possibly unjustly). Actual weighting of the distances in order to artificially favour some dimensions is the subject of further work.

Moving the sample to the decided cluster Once the most suitable cluster C l for outlier t o has been determined (note that there might not be a unique solution to this cluster determination), the problem is to move the outlier within that cluster so as to modify the actual values of the outlier as little as possible. We identify three ways to do this in practice, out of which the first is probably the best in terms of low distortion, but also the most difficult -and thus probably not achievable in real cases. In all the following three cases, the following steps are applied:

∀k ∈ 1, d ,        a o,k = a new o,k if d (k) (a o,k , c (k) l ) > max a i,k ∈C l [ d (k) (a i,k , c (k) l ) ] a o,k unchanged otherwise , ( 5
)
where a new o,k is the new value to be given to the k-th coordinate of the outlier t o , and max

a i,k ∈C l [ d (k) (a i,k , c (k) l ) ]
is in fact the maximum intra-cluster distance between cluster elements and the centroid c l of the cluster C l . Thus, we ensure that the modification of this specific dimension does not modify too much the intra cluster distances. We then propose three approaches to determine the new a new o,k value: (a) Setting it to the centroid value, and adding some noise; (b) Setting it to the centroid value only; (c) Setting it to an existing cluster element value.

(a) Centroid and Noise In this case, we set the new value of the outlier coordinate

a new o,k as a new o,k = c (k) l + r, ( 6
)
where r is randomly drawn from a certain distribution such that the distribution of the distances from the cluster samples to the cluster centroid is not modified too much. More precisely, with f dC l the distribution of the distances between the samples in cluster C l and its centroid, and f new d C l the same distribution after modifying the outlier coordinate a o,k , we want to make sure that KL(f d C l , f new dC l ) ≤ ε, where KL(•, •) stands for the Kullback-Leibler divergence between the two distributions [START_REF] Kullback | On information and sufficiency[END_REF]. In practice, other metrics could be used in this place, such as the Earth-Mover Distance [START_REF] Bogachev | The monge-kantorovich problem: achievements, connections, and perspectives[END_REF][START_REF] Mallows | A note on asymptotic joint normality[END_REF], e.g. This approach, as said before, although probably very desirable, is rather difficult to achieve practically, as drawing the noise value r in such a way as described above is difficult.

a new o,k = c (k) l . (7)
While this approach has a very clear advantage of being simple, it might lead to moving the outlier "too close" to the centroid. Remember here that the centroid is likely not an actual sample from the data, and we are thus inserting a sample with unseen before coordinates, in this cluster.

(c) Flattening to a Cluster Element Value Finally, this third approach is probably a good compromise of simplicity of execution and low distortion of the data. Here, we set the new value of a new o,k as

a new o,k = a i,k with a i,k drawn at random from C l . (8)
In this case, we thus draw from the existing sample values from this cluster for this specific dimension. This ensures that we avoid disturbing too much the existing samples within the cluster, while moving effectively the outlier within the cluster. Once we have the outlier(s) moved back into the most appropriate cluster, we can assume that the isolated individuals these samples were representing are no longer as easy to re-identify as before. We can move on to the second part of this work: anonymizing the data within a cluster.

Anonymizing the data within a cluster

The idea behing this approach is to provide some methods to anonymize the data (by modifying its inherent values) while retaining, as in the previous sections, the structure of it -in the same data clustering sense as in the rest of the paper. For this, we propose two approaches that aim at anonymizing the data within a cluster (and not the whole cluster in itself), so that samples (individuals) within a cluster cannot be re-identified easily. The two approaches are relatively destructive on purpose, in order to provide a means of destroying "intelligently" the data for some specific data fields. The first one relies on flattening the required dimensions: if a specific data field is deemed sensitive, it can be summarized, for a single cluster, by a single value. The second approach is a lot less destructive, and tries to preserve the overall cluster statistics as much as possible, by randomizing the values within a cluster for all the samples so that the cluster remains similar.

Flattening dimensions

Referring back to Table 1, it is for example likely that the data in the "Sensitive" field, namely the Condition, would need to be modified before this data is released. For such cases where destructive data alterations are desirable or even needed, it would be possible to replace the sensitive values by empty or unusable ones. This would effectively destroy some of the data statistics and structures within the cluster considered. But in the cases where one would want to preserve some of this information in order to keep some structure within the cluster, the question becomes: how do we modify this data so that it is as close to destroying it as possible, while maintaining the cluster structure/statistics? The proposed straightforward way to do this is to "flatten" the sensitive field (dimension) to the value of the centroid. The effect of collapsing a specific dimension is illustrated on Figure 1. In effect, what happens for each cluster

C l is ∀k ∈ S, ∀t i ∈ C l , a i,k = c (k) l , ( 9
)
where S is the set of the considered sensitive fields to be anonymized "destructively". While this approach effectively destroys the data structure within the cluster to some extent, there is a risk that the cluster is already initially as on Figure 1; this could likely happen if the initial clustering of the data samples is efficient already in the first place. The flattening procedure proposed here would then have no effect and one could argue that the anonymization is not carried out.

This is unlikely to happen for all clusters at the same time, although this is obviously highly data-dependent. For this reason, we propose the second method, also considered as destructive regarding the data values, but "safer" in this respect.

Shuffling data around

This second method is about preserving the intracluster data structure as much as possible, while still modifying the sample values as much as possible. This approach is the most costly in terms of computations and general costs. In this case, we shuffle the samples (on one dimension at a time only) around the centroid. In effect, for a cluster C l ,

∀k ∈ S, ∀t i ∈ C l , a i,k = a new i,k s.t. KL(f dC l , f new d C l ) ≤ ε, (10)
where, as before, f dC l is the distribution of the distances between the samples in cluster C l and its centroid, and f new dC l the same distribution after modifying the coordinate a i,k , and a new i,k ∈ X (k) is the new value for the coordinate k of sample t i in C l . This approach is illustrated on Figure 2, where one can see that the overall effect is to "shuffle around" within the cluster, while preserving the distances between the samples in the cluster and the cluster centroid. Note in this case that we do not try to preserve explicitly the pairwise distances between the samples within a cluster. Such distances will, at the whole cluster level, be preserved somewhat in any case, by preserving the distances to the centroid.

Conclusions and Future Work

In this paper, we propose an early version of a data anonymization framework, focusing on making individual re-identification difficult, while preserving clusters/group statistics and structure, over any type of data field (provided it can be abstracted as a metric space). We first develop the means of identifying outliers in terms of clustering the data, and propose ways to modify the data so as to "push back" this outlier with the rest of the crowd. We then propose several methods to "stir" the data within a cluster, effectively modifying the data values completely, but retaining the internal structure of the clusters. This to allow for further data processing at a somewhat global level, while ensuring the privacy of individuals. As can be noted, some of the data alterations proposed in this work are relatively computationally heavy, and currently require many iterations to converge to an acceptable solution (e.g. the case from section 4.2 where one shuffles data around within a cluster so as to minimize the distortions on the distances distributions). Current and future work will focus on developing efficient algorithms to perform the proposed anonymization tasks, and experiment the proposed framework over large data sets composed of very different data fields.

  (b) Flattening to Centroid This case is a direct simplified version of the previous one. Here, we set the new value of a new o,k as

Fig. 1 .

 1 Fig. 1. Example of collapsing of one dimension to the centroid value. This obviously breaks cluster distribution and distances to the centroid.

Fig. 2 .

 2 Fig. 2.Example of re-distributing the samples within a cluster (or adding noise to them in a controlled fashion): The distribution of the distances to the centroid is preserved and the overall cluster structure is preserved.

Table 1 .

 1 Example of Health Data records from a medical institution.

	Non-Sensitive	Sensitive
	ID Zip Code Age Nationality Condition
	01 13053 28 Russian Heart Disease
	02 13068 29 American Heart Disease
	03 13068 21 Japanese Viral Infection
	04 13053 23 American Viral Infection
	05 14853 50	Indian	Cancer


Rashed Mazumder

Atsuko Miyaji
email: miyaji@comm.eng.osaka-u.ac.jp

Chunhua Su
email: su@comm.eng.osaka-u.ac.jp

An Efficient Construction of a Compression Function for Cryptographic Hash

Keywords: cryptographic hash, collision resistance, constrained device

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

Introduction

A cryptographic hash (CH) is defined as to proceed data from an arbitrary domain to a fixed domain [START_REF] Bogdanov | Hash Functions and RFID Tags: Mind the Gap[END_REF][START_REF] Menezes | Handbook of Applied Cryptography[END_REF][START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Lee | The price of security in wireless sensor networks[END_REF][START_REF] Ozen | Another Glance at Double-Length Hashing[END_REF]. The applications of CH are enormous. Generally, the CH is used in message verification, password verification, pseudorandom generation, and message authentication [START_REF] Bogdanov | Hash Functions and RFID Tags: Mind the Gap[END_REF][START_REF] Menezes | Handbook of Applied Cryptography[END_REF][START_REF] Kaps | Energy Comparison of AES and SHA-1 for Ubiquitous Computing[END_REF][START_REF] Lee | The price of security in wireless sensor networks[END_REF]. Furthermore, the cryptographic hash is an efficient primitive of security solution for IoT-end device, RfID, and resource constrained device [START_REF] Barreto | An Authentication Model for IoT Clouds[END_REF][START_REF] Riahi | A systemic and cognitive approach for IoT security[END_REF][START_REF] Lee | A lightweight authentication protocol for Internet of Things[END_REF][START_REF] Jing | Security of the Internet of Things: perspectives and challenges[END_REF][START_REF] Abomhara | Security and privacy in the Internet of Things: Current status and open issues[END_REF][START_REF] Yoshida | On the standardization of cryptographic application techniques for IoT devices in ITU techniques for IoT devices[END_REF]. Usually, the internal construction of CH depends on compression function [START_REF] Black | Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV[END_REF][START_REF] Black | An Analysis of the Blockcipher-Based Hash Functions from PGV[END_REF]. The compression function is based on scratch or blockcipher [START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Ozen | Another Glance at Double-Length Hashing[END_REF][START_REF] Black | Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV[END_REF][START_REF] Black | An Analysis of the Blockcipher-Based Hash Functions from PGV[END_REF][START_REF] Mazumder | A New Scheme of Blockcipher Hash[END_REF]. The blockcipher based compression function is a combination of component functions (Fig. 1). The component functions depend on the 16 modes of PGV construction so far [START_REF] Ozen | Another Glance at Double-Length Hashing[END_REF][START_REF] Black | Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV[END_REF][START_REF] Black | An Analysis of the Blockcipher-Based Hash Functions from PGV[END_REF]. Additionally, a classical structure of Merkle Damgrad is used for message encryption of the cryptographic hash, if message size is bigger than the blocksize [START_REF] Bogdanov | Hash Functions and RFID Tags: Mind the Gap[END_REF][START_REF] Menezes | Handbook of Applied Cryptography[END_REF][START_REF] Kaps | Energy Comparison of AES and SHA-1 for Ubiquitous Computing[END_REF]. According to Fig. 1, message (M ) is multiple of blocklength. Hence, message is partitioned as M |m i=1 ||. . .||m l . Thereafter, partitioned message injects as input with initial vector value (IV ). The function F i is called compression function, which is built by blockcipher or scratch. Usually, one of the PGV modes needs to select as a component function of compression function [START_REF] Ozen | Another Glance at Double-Length Hashing[END_REF][START_REF] Black | Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV[END_REF][START_REF] Black | An Analysis of the Blockcipher-Based Hash Functions from PGV[END_REF]. On the contrary, the generic of blockcipher compression function is more suitable than that of the scratch for encryption of a constrained device, IoT-end device because of implementation of blockcipher rather than the encryption function [START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Hirose | Some Plausible Constructions of Double-Block-Length Hash Functions[END_REF][START_REF] Armknecht | The Preimage Security of Double-Block-Length Compression Functions[END_REF]. [START_REF] Menezes | Handbook of Applied Cryptography[END_REF][START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Ozen | Another Glance at Double-Length Hashing[END_REF][START_REF] Mazumder | A Single Key Scheduling based Compression Function[END_REF] Usually, the blockcipher based compression function is classified as single blocklength (SBL) and double block-length (DBL). Due to short size of output, the application of SBL is limited now [START_REF] Menezes | Handbook of Applied Cryptography[END_REF][START_REF] Lee | MJH: A Faster Alternative to MDC-2[END_REF][START_REF] Miyaji | A New (n, n) Blockcipher Hash Function: Apposite for Short Messages[END_REF]. On the other hand, the DBL is more reliable construction due to its better resistance against birthday attack [START_REF] Menezes | Handbook of Applied Cryptography[END_REF][START_REF] Hirose | Some Plausible Constructions of Double-Block-Length Hash Functions[END_REF][START_REF] Black | Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV[END_REF][START_REF] Hirose | Collision Resistance of Hash Functions in a Weak Ideal Cipher Model[END_REF][START_REF] Lee | A New Double-Block-Length Hash Function Using Feistel Structure[END_REF]. Moreover, the DBL is categorized as (n, n) and (n, 2n) blockcipher (base is key size). The (n, 2n) blockcipher is better due to upper security bound (larger key space) [START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Ozen | Another Glance at Double-Length Hashing[END_REF][START_REF] Hirose | Some Plausible Constructions of Double-Block-Length Hash Functions[END_REF][START_REF] Nandi | Security Analysis of a 2/3-Rate Double Length Compression Function in the Black-Box Model[END_REF][START_REF] Miyaji | A new (n, 2n) Double Block Length Hash Function based on Single Key Scheduling[END_REF]. Generally, there are certain parameters that indicate the strength of blockcipher based compression function such as:

-security bound (CR : collision and P R : preimage resistance) -efficiency-rate (r) -number of calling blockcipher (#E)

-key scheduling (KS) -operational mode (OM )

The CR is defined as a game, where an adversary tries to find similar output under two different input, but the advantage of adversary is very limited [START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Hirose | Some Plausible Constructions of Double-Block-Length Hash Functions[END_REF][START_REF] Lee | A New Double-Block-Length Hash Function Using Feistel Structure[END_REF]. Under P R, it is infeasible for adversary to find any m (message) such that y = F (m), where y is predefined by the adversary [START_REF] Menezes | Handbook of Applied Cryptography[END_REF][START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Black | Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV[END_REF]. The number of blockcipher (#E) depends on number of calling blockcipher per message-block encryption. The KS directs the number of key requirement for single message block encryption [START_REF] Black | Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV[END_REF]. Furthermore, the OM stands for operational mode (parallel or serial) [START_REF] Black | An Analysis of the Blockcipher-Based Hash Functions from PGV[END_REF][START_REF] Hirose | Collision Resistance of Hash Functions in a Weak Ideal Cipher Model[END_REF]. In addition, the efficiencyrate [START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Mennink | Optimal Collision Security in Double Block Length Hashing with Single Length Key[END_REF] is defined as: r = size of message block/per iteration (number of blockcipher call) × block-length

Name

CR KS r # E OM MR [START_REF] Miyaji | A new (n, 2n) Double Block Length Hash Function based on Single Key Scheduling[END_REF][START_REF] Mazumder | A New Scheme of Blockcipher Hash[END_REF] Motivation. The parameters of CR, P R, r, #E, OM , and KS are vital for any satisfactory scheme of blockcipher based compression function [1, 6-8, 13, 21]. Firstly, certain gaps are identified from the current familiar schemes based on the above parameters. Thus, the importance of the findings are shown in the field of efficient and secure communication. For example, the key scheduling cost is analysed in respect of construction of compression function. Usually, 176 bytes are needed for operating of single key scheduling [START_REF] Joan | The Design of Rijndael, AES-The Advanced Encryption Standard[END_REF]. Hence, minimization of key scheduling is a common practice. Additionally, the operation mode is very crucial for resource limited devices, where the parallel mode can provide maximum support in respect of memory system [START_REF] Burak | Parallelization of a Block Cipher Based on Chaotic Neural Networks[END_REF][START_REF] Bos | Efficient Hashing Using the AES Instruction Set[END_REF]. Moreover, the efficiency-rate needs to reach the landmark (r = 1) [START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Hirose | Some Plausible Constructions of Double-Block-Length Hash Functions[END_REF][START_REF] Mennink | Optimal Collision Security in Double Block Length Hashing with Single Length Key[END_REF][START_REF] Lee | A New Double-Block-Length Hash Function Using Feistel Structure[END_REF]. There are some well-known schemes of blockcipher compression function such as MR, Weimar, Hirose, Tandem, Abreast, Nandi, and ISA09 (Table 1). For example, the CR of MR scheme is bounded by q = 2 126.70 but the r is 1/2 (q : number of queries). The scheme of Weimar-DM provides tight security bound such as q = 2 126.23 [START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF]. Moreover, it follows double key scheduling including 1/2 efficiency-rate. The scheme of Hirose delivers marginal security bound as q = 2 124.55 but it ensures a single key scheduling. However, the CR and P R bound of the Tandem-DM and Abreast-DM are not satisfactory as that of the MR, Weimar, and Hirose [START_REF] Miyaji | A new (n, 2n) Double Block Length Hash Function based on Single Key Scheduling[END_REF]. Moreover, the efficiencyrate of Tandem-DM and Abreast-DM is 1/2 like MR, Weimar, and Hirose [START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Lee | The Security of Abreast-DM in the Ideal Cipher Model[END_REF][START_REF] Lee | The Collision Security of Tandem-DM in the Ideal Cipher Model[END_REF]. Though the scheme of Nandi is bounded by q = O 2 2n/3 but it provides higher efficiency-rate (r = 2/3) [START_REF] Nandi | Security Analysis of a 2/3-Rate Double Length Compression Function in the Black-Box Model[END_REF]. Additionally, the construction of ISA09 provides better efficiency-rate (r = 2/3) [START_REF] Lee | A New Double-Block-Length Hash Function Using Feistel Structure[END_REF]. According to the above discussions and Table 1, most of the existing schemes have rigorous security margin. However, the efficiencies are low for the constructions of MR, Weimar, Hirose, Tandem and Abreast. On the other hand, the schemes of Nandi and ISA09 satisfies higher efficiency-rate. Moreover, the constructions of Nandi and ISA09 satisfies KS = 3 and #E = 3 [START_REF] Nandi | Security Analysis of a 2/3-Rate Double Length Compression Function in the Black-Box Model[END_REF][START_REF] Lee | A New Double-Block-Length Hash Function Using Feistel Structure[END_REF]. On the contrary, the OM is serial for Nandi and ISA09 schemes. Thus, the overall efficiencies are not adequate for the ISA09 and Nandi schemes. Now-a-days, the importance of an efficient blockcipher compression function are enormous [START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Ozen | Another Glance at Double-Length Hashing[END_REF][START_REF] Hirose | Some Plausible Constructions of Double-Block-Length Hash Functions[END_REF][START_REF] Miyaji | A New (n, n) Blockcipher Hash Function: Apposite for Short Messages[END_REF][START_REF] Mazumder | A Single Key Scheduling based Compression Function[END_REF][START_REF] Zanella | Internet of Things for Smart Cities[END_REF][START_REF] Xu | Internet of Things in Industries: A Survey[END_REF][START_REF] Yoshida | On the standardization of cryptographic application techniques for IoT devices in ITU techniques for IoT devices[END_REF]. The blockcipher is one of the important cryptographic primitive for the security solution of IoT environment according to certain standards such as ISO/IEC29192-1, ISO/IEC29192-2, ISO/IEC29192-3, and ISO/IEC29192-4, [START_REF] Hirose | A Lightweight 256-Bit Hash Function for Hardware and Low-End Devices: Lesamnta-LW[END_REF][START_REF] Shirai | The 128-bit Blockcipher CLEFIA[END_REF][START_REF] Yoshida | On the standardization of cryptographic application techniques for IoT devices in ITU techniques for IoT devices[END_REF]. Generally, IoT-end device, RfID, and constrained device are used in IoT environment [START_REF] Abomhara | Security and privacy in the Internet of Things: Current status and open issues[END_REF][START_REF] Zanella | Internet of Things for Smart Cities[END_REF][START_REF] Xu | Internet of Things in Industries: A Survey[END_REF][START_REF] Hirose | A Lightweight 256-Bit Hash Function for Hardware and Low-End Devices: Lesamnta-LW[END_REF]. Furthermore, these devices need to operate fast but the major draw-backs are limited memory, power, and processor [START_REF] Lee | A lightweight authentication protocol for Internet of Things[END_REF][START_REF] Jing | Security of the Internet of Things: perspectives and challenges[END_REF][START_REF] Hirose | A Lightweight 256-Bit Hash Function for Hardware and Low-End Devices: Lesamnta-LW[END_REF][START_REF] Shirai | The 128-bit Blockcipher CLEFIA[END_REF][START_REF] Yoshida | On the standardization of cryptographic application techniques for IoT devices in ITU techniques for IoT devices[END_REF]. Therefore, the cryptographic solution scheme should satisfies the property of better efficiency. In summary, the targets for an efficient blockcipher compression function are as follows:

O(2 n ) 1 1/2 2 Parallel Weimar [6] O(2 n ) 2 1/2 2 Parallel Hirose [13] O(2 n ) 1 1/2 2 Parallel Tandem [6, 14] O(2 n ) 2 1/2 2 Parallel Abreast [6, 14] O(2 n ) 2 1/2 2 Parallel Nandi [20] O(2
-higher efficiency-rate -reasonable key scheduling -less number of calling blockcipher (#E) -operational mode -satisfiable security bound Contribution. In this paper, a blockcipher based compression function is proposed. The component function of the proposed construction follows one of the secure modes of PGV. The contributions of the proposed construction are as follows:

-efficiency rate, r = 0.996

-KS = 2 -#E = 2 -Parallel mode -CR security bound, q = 2 125.84 |q : number of query
In addition, a comparative study of the proposed construction and current familiar schemes is given through Table 2.

Outline. The basic preliminaries are provided in Section 2. The technical details of the proposed scheme are given in Section 3. Section 4 is responsible for the analysis of security bound. Furthermore, the result analysis is given including performance analysis in section 5. Finally, the conclusions and future works are provided in Section 6.

Table 2. Comparison: The proposed scheme and existing familiar schemes [START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Armknecht | The Preimage Security of Double-Block-Length Compression Functions[END_REF][START_REF] Mennink | Optimal Collision Security in Double Block Length Hashing with Single Length Key[END_REF][START_REF] Nandi | Security Analysis of a 2/3-Rate Double Length Compression Function in the Black-Box Model[END_REF][START_REF] Lee | A New Double-Block-Length Hash Function Using Feistel Structure[END_REF][START_REF] Miyaji | A new (n, 2n) Double Block Length Hash Function based on Single Key Scheduling[END_REF]

CR

(n, k) is E = {0, 1} n × {0, 1} k → {0, 1} n .
The reply of forward (E) and backward E -1 query is random and independent permutation of K ∈ {0, 1} k . Let BLOCK k n is the set of all blockciphers B (n, k). Under ideal cipher model, E is chosen randomly from BLOCK k n . Actually, E invokes key and plaintext as input and returns ciphertext as output. On the contrary, input of E -1 are key and ciphertext. Then output is plaintext. Usually, the query and response through E and E -1 are stored as k i , x i , y i . Moreover, the adversary is not allowed to make any duplicate query [START_REF] Black | An Analysis of the Blockcipher-Based Hash Functions from PGV[END_REF][START_REF] Shannon | Communication Theory of Secrecy Systems[END_REF].

security definition

There are certain properties, which are responsible for analysing the security issue of blockcipher compression function. For example, collision resistance (CR), preimage resistance (P R), padding oracle attack, and initial value (CV ) attack are the most familiar properties [START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Hirose | Some Plausible Constructions of Double-Block-Length Hash Functions[END_REF][START_REF] Miyaji | A new (n, 2n) Double Block Length Hash Function based on Single Key Scheduling[END_REF][START_REF] Abed | Counter-b DM: A Provably Secure Family of Multi-Block-Length Compression Functions[END_REF]. In this section, the collision and preimage resistance of the blockcipher compression function are briefly discussed [START_REF] Black | Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV[END_REF][START_REF] Black | An Analysis of the Blockcipher-Based Hash Functions from PGV[END_REF][START_REF] Hirose | Collision Resistance of Hash Functions in a Weak Ideal Cipher Model[END_REF][START_REF] Liscov | Constructing an ideal hash function from weak ideal compression function[END_REF] .

collision resistance of compression function

The adversary A is allowed for accessing to the blockcipher oracle E ∈ BLOCK k n . Hence, the output of compression function are (α 1 , β 1 , m 1 ) and (α 2 , β 2 , m 2 ). Furthermore, an experiment is defined as Exp-coll f E (A). The output of the experiment is 1 iff following condition satisfies.

f E (α 1 , β 1 , m 1 ) = f E (α 2 , β 2 , m 2 ) ∧ {(α 1 , β 1 , m 1 ) = (α 2 , β 2 , m 2 )}
, where f E is a blockcipher compression function and α, β are chaining values including m| message. The advantage of adversary for finding a collision under f E is defined below. Let,

Adv coll f E (A) = Pr [Exp-coll f E (A) = 1]
, where coll stands for collision. The advantage of adversary A is quantified by the number of queries that are allowed to ask blockcipher oracle. Therefore,

Adv coll f E (q) = max A Adv coll f E (A)
, where the maximum is taken over all adversaries that ask at most q oracle queries [START_REF] Black | Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV[END_REF][START_REF] Liscov | Constructing an ideal hash function from weak ideal compression function[END_REF].

preimage resistance of compression function

The adversary A has access on blockcipher oracle E ∈ BLOCK k n . Furthermore, A selects value of α, β randomly before making any query to blockcipher oracle. Let the feedback of oracle are α and β in respect of adversarial query. In addition, assume an experiment Exp-pre f E (A), where pre stands for preimage. Hence, the output of the defined experiment is 1 iff:

f E (α 1 , β 1 , m 1 ) = (α, β)
, where f E is a blockcipher compression function and α 1 , β 1 are chaining values including m| message. The advantage of adversary for finding a preimage under f E is defined by

Adv pre f E (A) = Pr [Exp-pre f E (A) = 1].
Moreover, the advantage of A is evaluated through the total number of queries. Therefore,

Adv pre f E (q) = max A Adv pre f E (A)
, where the maximum is taken over all adversaries that ask q oracle queries [START_REF] Black | Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV[END_REF][START_REF] Liscov | Constructing an ideal hash function from weak ideal compression function[END_REF].

Proposed Scheme

Usually, the efficiency-rate can be increased by using three calls of blockcipher. The above method is used in Nandi and ISA09 [START_REF] Nandi | Security Analysis of a 2/3-Rate Double Length Compression Function in the Black-Box Model[END_REF][START_REF] Lee | A New Double-Block-Length Hash Function Using Feistel Structure[END_REF]. Furthermore, a method of using a pair of chaining values including message in the two blockciphers is also useful. Such kind of method is used in MDC-2 and later in MDC-4 [START_REF] Wang | Cryptanalysis of the Hash Functions MD4 and RIPEMD[END_REF][START_REF] Lee | MJH: A Faster Alternative to MDC-2[END_REF][START_REF] Fleischmann | The Collision Security of MDC-4[END_REF]. The proposed construction is actually inspired and followed by the construction of MDC-2 and MDC-4 [START_REF] Wang | Cryptanalysis of the Hash Functions MD4 and RIPEMD[END_REF][START_REF] Lee | MJH: A Faster Alternative to MDC-2[END_REF][START_REF] Fleischmann | The Collision Security of MDC-4[END_REF]. However, in respect of security there is a drawback for these (MDC-2, 4) kind of construction. In MDC-2, two chaining values are used as input, where message is common for two blockciphers. There is no dependency between two chaining values as input. On the contrary, it can be said that the computations of the two block ciphers used in the compression function are completely isolated. For example, given the input and output (x 1 , y 1 → x 2 , y 2 ) , if the input is swapped then the new output will be swapped values of the old output (y 1 , x 1 → y 2 , x 2 ). It actually suffers for symmetric property. Therefore, certain changes are occurred in the proposed construction (Fig. 2). For example, one constant bit 0 and 1 is used to each of the block ciphers as part of the key for the proposed scheme (trivial practice in cryptography, [START_REF] Armknecht | The Preimage Security of Double-Block-Length Compression Functions[END_REF]). Hence, the attacker can't predict the output of the chaining values which is given under the assumption where the attacker can freely alter the input of chaining values and message. This premise is used for breaking the symmetric property of the proposed scheme, where x||y and y||x will be treated as two different values. Moreover, the scheme is secured under a generic attack because of the ideal cipher model primitive [START_REF] Yevgeniy | On the Relation Between the Ideal Cipher and the Random Oracle Models[END_REF]. Additionally, the MDC-2, MDC-4 are (n, n)-bit DBL hash functions with efficiency-rate 1/2 and 1/4 [START_REF] Abed | Counter-b DM: A Provably Secure Family of Multi-Block-Length Compression Functions[END_REF],

where the proposed scheme is based on (n, 2n) blockcipher. Furthermore, a different component function is used in respect of the MDC-2 and MDC-4. The proposed scheme can compress 4n bits into 2n bits, where MDC-2 and MDC-4 can compress 3n bits to 2n bits. Furthermore, the proposed scheme satisfies type-1 (from Stam's conjecture), where two blockciphers E l , E r are distinct and independent under the ICM [START_REF] Ozen | Another Glance at Double-Length Hashing[END_REF][START_REF] Black | Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV[END_REF]. In general, the proposed scheme is defined as variant of the MDC-2 and MDC-4.

1 i a  1 i b  i a i b n 2n 2n n   2 1 0,1 n i m   l E r E     0,1 n i l m      0,1 n i l m  c c i x i y Fig. 2. Proposed Scheme (Variant of MDC-2, 4)
Definition 1. Let E ∈ BLOCK k n be a block cipher taking a set of k-bit key and n-bit block-length such that

E l,r = {0, 1} k ×{0, 1} n → {0, 1} n . E dbl = {0, 1} k ×{0, 1} 2n → {0, 1}
2n is defined as a double block length (dbl) cipher and parallel calling of two independent blockciphers of E l, r such that,

x i ← E l,(mi||c) a i-1 ⊕ l (m i ) y i ← E r,(mi||c) (b i-1 ⊕ l (m i ))
where parameters are defined as m i ∈ {0, 1} 2n-1 , (a, b, x, y) ∈ {0, 1} n and l (m i ) = lsb of m i ∈ {0, 1} n , c = {1}. Thus, the final output is f E (a i , b i ) where,

a i ← x i ⊕ (a i-1 ⊕ l (m i )) ⊕ c b i ← y i ⊕ (b i-1 ⊕ l (m i )) ⊕ c Definition 2. Let f E = {0, 1} k × {0, 1} 2n → {0, 1} 2n be a blockcipher based compression function such as (a i , b i , m i ) = f (a i , b i , m i ) , where, a i ∈ {0, 1} n , b i ∈ {0, 1} n , m i ∈ {0, 1} 2n-1
, and c = {0, 1}. Therefore, f E consists of ideal blockcipher (E) such as:

  a i = f l a i-1 ⊕ l (m i ), mi ||c ⊕ (a i-1 ⊕ l (m i )) ⊕ c ← E l a i-1 ⊕ l (m i ), mi ||c ⊕ (a i-1 ⊕ l (m i )) ⊕ c   b i = f r (b i-1 ⊕ l (m i ) , m i ||c) ⊕ (b i-1 ⊕ l (m i )) ⊕ c ← E r (b i-1 ⊕ l (m i ) , m i ||c) ⊕ (b i-1 ⊕ l (m i )) ⊕ c

Security Analysis

The security proof of the proposed scheme follows an ICM [START_REF] Black | Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV[END_REF][START_REF] Black | An Analysis of the Blockcipher-Based Hash Functions from PGV[END_REF], where A is not allowed to make any duplicate query. For example, the query of E (k, x) = y isn't being executed by the adversary, if E -1 (k, y) = x query is already in the query storage (Q). The adversary A searches for a collision under a pair of different inputs (query) through the blockcipher oracle. Additionally, A tries to find an output of compression function for making collision with initial chaining value. Moreover, the preimage attack means: Adversary A selects α , β randomly and tries to find f (α, β, m) = α , β . In addition, the advantage of A is very limited to get the above success.

collision security analysis

An adversary A has access to a blockcipher oracle for finding a collision. The query is Q i and corresponding response is triplet as (m : mesage, k : key, c : ciphertext). For any i-th iteration (i ≤ q), the query process looks either

Q i ∈ {(m, k) = c} or Q i ∈ {(c, k) = m}. The Q i stores in Q ∈ (Q 1 , Q 2 , ..., Q i )
for each iteration of i where Q : query storage. Under this circumstance, adversary A has target to find,

f E (m i , k i , c i ) = f E (m j , k j , c j )| ∵ (m i , k i , c i ) = (m j , k j , c j ) ∧ (i = j) (1)
According to the definition of proposed scheme, 1 is re-defined as:

f E (a i , b i , m i ) = f E (a j , b j , m j )| ∵ (a i , b i , m i ) = (a j , b j , m j ) ∧ (i = j) (2)
Theorem 1. Let f E be a double block-length compression function (Def. 1, 2). An adversary, A is assigned for finding a collision (coll) under the f E after q pairs of queries. Hence, the advantage of A is bounded by,

Adv coll f E (q) ≤ 6q 2 -2q (2 n -q) 2
Proof. An adversary A makes a relevant query to the blockcipher oracle, where the number of query is limited by q queries. For any i-th query, the reply of x i and y i randomly selects by the adversary from the blockcipher oracle. The main difficulty is to find out the set size of an oracle from where these fresh value come. There are three possible incidents that are responsible for collision-hit under any i-th iteration. In the beginning, the three incidents are clarified through two targets (T AR1, T AR2). The goal of the first incident is to find a collision for two distinct queries (j < i) where T AR1 represents the responsibilities of the first incident. The T AR2 is responsible for second and third incident. Since A has target to find a collision through single query. Furthermore, A investigates for a collision against initial chaining values. Finally, three phases of QUERY, RESPON SE, and CHECK have been defined under Algorithm 1 T AR1 (for notations follow Def. 1, 2 )

1: Q: Query storage, q: query, A: Adversary, T AR1 C i : event, m : message 2: for each node (i < q) do 3:

QUERY: E ← BLOCK k n ← A E,E -1 4:
RESPON SE:

5: q i,1 ← x i = E (mi||c) a i-1 ⊕ l (m i ) ∧ q i,2 ← y i 6:
CHECK:

7:
if (q i,1 , q i,2 )=(q j,1 , q j,2 ), where j < i then 8:

1. Call:

T AR1 C i ∧ terminate 9:
else 10:

write the value of q i,1 , q i,2 to Q 11:

end if 12: end for T AR1 and T AR2. Let adversary A is allowed to ask query to blockcipher oracle at QUERY phase. Moreover, corresponding feedback assign under RESPON SE phase. In addition, a collision is checked in the phase of CHECK.

collision probability based on the first incident (T AR1). Under an iteration of i, a pair of query is executed that returns two distinct outputs. According to algorithm 1, there is a chance to make collision through two different query-pairs after any i-th (j < i < q) iteration. For example, a query pair of j-th iteration are:

a j ← E l, mj ||c a j-1 ⊕ l (m j ) ⊕ (a j-1 ⊕ l (m j )) ⊕ c, b j ← E r,mj ||c (a j-1 ⊕ l (m j )) ⊕ (a j-1 ⊕ l (m j )) ⊕ c
Moreover, the query responses are

a i ← E l, m||c a i-1 ⊕ l (m i ) ⊕ (a i-1 ⊕ l (m i )) ⊕ c and b i ← E r,m||c (a i-1 ⊕ l (m i )) ⊕ (a i-1 ⊕ l (m i )) ⊕ c on the i-th (j < i) iteration.
Let T AR1 C i be an event, where adversary tries to find a collision through different two iterations (j < i ≤ q). Thus, equation 2 is re-defined as:

{a i ← (c ⊕ a i-1 ⊕ l (m i ) ⊕ x i )} = {a j ← (c ⊕ a j-1 ⊕ l (m j ) ⊕ x j )} ∨ {a i ← (c ⊕ a i-1 ⊕ l (m i ) ⊕ x i )} = {b j ← (c ⊕ b j-1 ⊕ l (m j ) ⊕ y j )} (3)
{b i ← (c ⊕ b i-1 ⊕ l (m i ) ⊕ y i )} = {a j ← (c ⊕ a j-1 ⊕ l (m j ) ⊕ x j )} ∨ {b i ← (c ⊕ b i-1 ⊕ l (m i ) ⊕ y i )} = {b j ← (c ⊕ b j-1 ⊕ l (m j ) ⊕ y j )} (4)
From 3 ∧ 4, the probability of collision hit under the event of

T AR1 C i is 2(i-1) (2 n -(i-1)) 2
(when j < i ≤ q). Therefore, the probability of single event under the T AR1 is:

Pr T AR1 C = 2 (i -1) (2 n -(i -1)) 2
If T AR1 C be the events of all colliding pairs under the f E for q pairs of queries. Hence,

Pr T AR1 C = Pr T AR1 C 2 ∨ .. ∨ T AR1 C q ≤ q i=2 Pr T AR1 C i ≤ 2 × 2 × (i -1) (2 n -i) 2 = 2q 2 -2q (2 n -q) 2 (5)
collision probability based on the second and third incident (T AR2). Let a i , b i be the output of compression function (i < q), where

{(a i ← x i ⊕ (a i-1 ⊕ l (m i )) ⊕ c) , (b i ← y i ⊕ (b i-1 ⊕ l (m i )) ⊕ c)}
Hence, there is a probability to make collision when a i = b i . Let T AR2 C i be a collision event for the above condition under the check phase of i < q. Furthermore, there is an option to make a collision with initial chaining values. For example, the output pair of the proposed scheme a i , b i collides with the initial chaining values (a 0 , b 0 ) at any phase of query process. Therefore, the conditions of collision-hit under the initial key attack are

{a i = (a 0 ) , (b 0 )} ∨ {b i = (a 0 ) , (b 0 )}.
Algorithm 2 (for T AR2)

1: T AR2: line 2 to 7 is replaced of T AR1 (from line 4) 2: if (q i,1 = q i,2 ) then 3: create the event T AR2 C i ∧ terminate 4:
"AND" 5:

if (q i,1 , q i,2 ) = (q 0,1 , q 0,2 ) then

6: create the event T AR2 C i ∧ terminate 7: end if 8: end if
Hence, the probability of collision under two incidents is at most 1/(2 n -i) × 2 × 2/(2 n -i). Finally, the probability of these two incidents under the event of T AR2 C for q pairs of queries is:

Pr T AR2 C = Pr T AR2 C 1 ∨ .. T AR2 C q ≤ q i=1 Pr T AR2 C i = q i=1 1 (2 n -i) × 2 × 2 (2 n -i) ≤ q (2 n -q) × 2 × 2 × q (2 n -q) = 4q 2 (2 n -q) 2 (6)
Adding the values of 5 and 6, Theorem 1 satisfies.

Preimage Security Analysis

A standard proof technique of Armknecht et al. is used for the preimgae security proof of the proposed scheme [START_REF] Armknecht | The Preimage Security of Double-Block-Length Compression Functions[END_REF]. The P R security bound of MR, Weimar, Hirose, Tandem and Abreast is also based on [START_REF] Armknecht | The Preimage Security of Double-Block-Length Compression Functions[END_REF]. The two important concepts are adopted such as query: super, normal and adjacent query-pair from [START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Armknecht | The Preimage Security of Double-Block-Length Compression Functions[END_REF]. Let A randomly picks the output value of compression function (a , b ). Now A has target to find a probability for preimage-hit through f p E (a i , b i , m) = (a , b ) condition, where a i , b i , m : input of compression function and a i = b i .

Theorem 2. Let f E be a double block-length compression function. An adversary A is defined for finding a preimage-hit under the f E after q pairs of queries. Hence, the advantage of A is bounded by,

Adv pre f E (q)≤ 8q N 2 + 8q (N -q) 2
Proof. An adversary A keeps a query database in the form of,

a i ← E l,m||c a i-1 ⊕ l (m i ) ⊕ (a i-1 ⊕ l (m i )) ⊕ c and b i ← E r,m||c (b i-1 ⊕ l (m i )) ⊕ (b i-1 ⊕ l (m i )) ⊕ c
In such a fashion, when the oracle size reaches N/2 (N : Oracle size (2 n )), the rest of the queries under the key-set reaches the adversary as free query [START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Armknecht | The Preimage Security of Double-Block-Length Compression Functions[END_REF][START_REF] Coron | Merkle-Damgard revisited: How to construct a hash function[END_REF]. This free set of queries exist in the domain which is called the super query database (SQD).

On the other hand, the first N/2 is defined as a normal query database (N QD) [START_REF] Armknecht | The Preimage Security of Double-Block-Length Compression Functions[END_REF]. Additionally, the free queries are asked by the adversary non-adaptively in the super query database (SQD). Therefore the successful conditions of a preimage-hit are: for N/2 < i < N do for super query 6:

a i ← E l, mi||c a i-1 ⊕ l (m i ) ⊕ (a i-1 ⊕ l (m i )) ⊕ c , a j ← E l, mj ||c a j-1 ⊕ l (m j ) ⊕ (a j-1 ⊕ l (m j )) ⊕ c = {(a ) , (b )} (7)
b i ← E r,m||ci (b i-1 ⊕ l (m i )) ⊕ (b i-1 ⊕ l (m i )) ⊕ c , b j ← E r,m||cj (b j-1 ⊕ l (m j )) ⊕ (b j-1 ⊕ l (m j )) ⊕ c = {(a ) , (b )} (8)
(QUERY ∧ CHECK)

7:

end for 8: end procedure probability of N QW. The adversary A makes any relevant query independently and receives a i , b i . Furthermore, A executes until the oracle set size reaches to N/2 [START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Armknecht | The Preimage Security of Double-Block-Length Compression Functions[END_REF]. According to the above mentioned conditions [START_REF] Lee | The price of security in wireless sensor networks[END_REF][START_REF] Ozen | Another Glance at Double-Length Hashing[END_REF], the hitting probability is 2 × 2 (2 n -q).

If A makes a query E l,mi||c a i-1 ⊕ l (m i ) (left block) then the answer of a right block provides as free query to A because of the adjacent query pair [START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Armknecht | The Preimage Security of Double-Block-Length Compression Functions[END_REF]. Thereafter, the set size is (2 n -q)/2 which outfits the probability as 2 (2 n -q). Thus, the probability of the normal query is:

Pr [N QW] = q × 2 × 2/(2 n -q) × 2/(2 n -q) = 8q (2 n -q) 2 (9)
probability of SQW . The concept of a super query oracle is very simple [START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Armknecht | The Preimage Security of Double-Block-Length Compression Functions[END_REF]. If the query oracle reaches at the point of N/2, then the rest of the queries set as free to the adversary [START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Armknecht | The Preimage Security of Double-Block-Length Compression Functions[END_REF]. Later these queries are asked by the adversary non-adaptively [START_REF] Armknecht | The Preimage Security of Double-Block-Length Compression Functions[END_REF] for finding a preimage-hit (Algorithm 3). Moreover, the preimage-hit is notified either in this domain (SQD) or not. Thus, the probability is either 2/N or 0 for any output value of a i /b i . Now a pair of conditions under SQW are:

{a i ← (l (m i ) ⊕ a i-1 ⊕ x i ) ⊕ c} = (a ) , (b ) (10)
{b i ← (l (m i ) ⊕ b i-1 ⊕ y i ) ⊕ c} = (a ) , (b ) (11)
According to 10, the answer of a i has a possibility to come from the set size of N/2. Hence, the probability is 2/N . Recalling the concept of an adjacent query pair (free query) [START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Armknecht | The Preimage Security of Double-Block-Length Compression Functions[END_REF], where the answer of another block (right block) comes from the set size of N/2. As a result, the probability of 10 is in total 4/N 2 . In similar way, the probability of 11 is 4/N 2 . Now, the final probability of the SQW is evaluated based on the the number of points for a SQW, the cost of SQW and the probability of obtaining preimgae-hit such as:

Pr [SQW] = q/(N /2) × (N /2) × 2 × 4 N 2 = 8q N 2 (12)
Adding the values of 9 and 12, Theorem 2 satisfies.

5 Result Analysis

collision resistance analysis

Theorem 1 provides a probability of collision hit under the given adversary A. The number of queries (q) is important for finding an upper bound of the collision security. Hence, the value of q is required to investigate when the adversarial advantage is 1/2 (birthday attack). Let, N = 2 n and Adv coll f E (A) ≤ 6q 2 -2q (2 n -q) 2 [Theorem 1.], where n = 128. According to the birthday attack [START_REF] Bogdanov | Hash Functions and RFID Tags: Mind the Gap[END_REF][START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Hirose | Some Plausible Constructions of Double-Block-Length Hash Functions[END_REF][START_REF] Nandi | Security Analysis of a 2/3-Rate Double Length Compression Function in the Black-Box Model[END_REF][START_REF] Lee | A New Double-Block-Length Hash Function Using Feistel Structure[END_REF], Adv coll f E (A) = 1 2 . Thus, the number of queries are q = 2 125.84 .

Efficiency-rate

The efficiency-rate of a blockcipher based compression function is defined as r = |m| (n×#E) , where |m|=length of message, n=blocklength and #E=number of blockcipher calls. According to the definitions (Def. 1, Def.2) of the proposed scheme, the efficiency-rate is r = 0.996 ⇒ r ≈ 1. In Fig. 3, the proposed scheme is compared with the existing schemes in respect of efficiency-rate .

Next, the above cost (Table 4) is generalized including the number of iterations (l) for tn-bit message (t > 2) in Table 5. Additionally, the proposed scheme is faster than that of the MR, Weimar, Tandem, Abreast (if, m > 2n) in certain cases.

Conclusion

This paper studied the gap between security bound and efficiency of compression function for the cryptographic hash. Additionally, study result introduces that the blockcipher based compression function is more suitable than the scratch based construction for security solution of IoT-end devices, RfID, and constrained devices. Thus, a better efficient compression function (blockcipher based) is proposed in this paper. Additionally, the proposed scheme provides improved efficiency-rate, less call of blockcipher, and reasonable security bound. It satisfies two calls of 2n-bit key property, where two block ciphers are independent. The proof technique of this scheme depends on the ICM tool. The proposed scheme has a provision of fixed size message encryption property. Therefore, this property opens a window for new applications, where a variable length of the message can be encrypted without padding. Finally, the proposed scheme is secure under one of the modes of PGV which can be extended to make the scheme secure under all modes of the PGV [START_REF] Black | An Analysis of the Blockcipher-Based Hash Functions from PGV[END_REF][START_REF] Hirose | Collision Resistance of Hash Functions in a Weak Ideal Cipher Model[END_REF][START_REF] Liscov | Constructing an ideal hash function from weak ideal compression function[END_REF].

Fig. 1 .

 1 Fig.1. Basic concept of cryptographic hash[START_REF] Menezes | Handbook of Applied Cryptography[END_REF][START_REF] Fleischmann | Weimar-DM: A Highly Secure Double-Length Compression Function[END_REF][START_REF] Ozen | Another Glance at Double-Length Hashing[END_REF][START_REF] Mazumder | A Single Key Scheduling based Compression Function[END_REF]

2n 3 ) 3 2/3 3

 333 Serial ISA09 [21] O(2 n ) 3 2/3 3 Serial CR: Collision resistance, KS: Key Scheduling, r: Efficiency rate #E: Number of blockcipher calls, OM : Operational mode

  r KS #E OM MR 2 126.70 r = 0.5 1 2 P Weimar 2 126.23 r = 0.5 2 2 P Hirose 2 124.55 r = 0.5 1 2 P Tandem 2 120.87 r = 0.5 2 2 P Abreast 2 124.42 r = 0.5 2 2 P proposed scheme 2 125.84 r = 0.996 2 2 P Nandi O(2 2n/3 ) r = 0.66 3 3 S ISA09 O(2 n ) r = 0.66 3 3 S MDC-2 O(2 n ) r = 0.5 2 2 P MDC-4 O(2 n ) r = 0.5 4 4 SP P : Parallel, S: Serial, SP : Semi-Parallel 2 Preliminaries 2.1 ideal cipher model (ICM) In ideal cipher model, a blockcipher is defined as B (n, k) where n means block-length and k means key-length. The operation of B

Table 5 .

 5 Required memory for key scheduling, when m = tn Name l V B + V Proposed scheme l = tn/2n γ a + γ MR l = tn/n γ b + γ Weimar l = tn/n γ c + γ Hirose l = tn/n γ d + γ Tandem l = tn/n γ e + γ Abreast l = tn/n γ f + γ a, b, c, d, e, f: these values come from the Table IV (column B)

Table 1 .

 1 Result of existing familiar schemes

  Equation 7 and 8 can occur in either in the domain of a normal query win (N QW) or super query win (SQW). Therefore, the probability of the preimage-hit is Pr [N QW]+ Pr [SQW].

	Algorithm 3
	1: procedure PREIMAGE TARGET
	2:	for i < N/2 do (for normal query)
	3:	run QUERY ∧ RESPON SE ∧ CHECK
	4:	end for
	5:

This work is partially supported by the Grant-in-Aid for Scientific Research (C)(15K00183) and (15K00189) and Japan Science and Technology Agency, CREST and Infrastructure Development for Promoting International S&T Cooperation JSPS Grant-in-Aid for Young Scientists (15K16005)

2 l = 2 e ← 2 × 176 B γ e + γ Abreast [START_REF] Lee | The Security of Abreast-DM in the Ideal Cipher Model[END_REF] 2 l = 2 f ← 2 × 176 B γ f + γ l: number of iteration for processing 2n-bit message B: required memory for key scheduling in byte V: memory require for storing output (γ = 2n bit) B + V: total required memory for key scheduling, when message = 2n

Performance analysis

In this section, a comparison study is given for the proposed scheme in respect of memory resources. It is known that 176 bytes of memory is required for single key scheduling [START_REF] Joan | The Design of Rijndael, AES-The Advanced Encryption Standard[END_REF]. For example, a 2n-bit size of message is taken for encryption. Therefore, the following Table 3 and 4 are made based on the characteristics of the current familiar schemes and the proposed scheme. For any DBL compression function, the output is 2n-bit. Therefore, assume that the minimum 2n → γ bit is required to store the output value (denoted as V) of i-th iteration. In Table 4, the message size is 2n-bit for example. Hence, the memory resource doesn't need to store the output for the proposed scheme.