Lina Nouh

Ashkan Rahimian

Djedjiga Mouheb

Mourad Debbabi

Aiman Hanna

BinSign: Fingerprinting Binary Functions to Support Automated Analysis of Code Executables

Keywords: Code Fingerprinting, Static Analysis, Reverse Engineering

Binary code fingerprinting is a challenging problem that requires an in-depth analysis of binary components for deriving identifiable signatures. Fingerprints are useful in automating reverse engineering tasks including clone detection, library identification, authorship attribution, cyber forensics, patch analysis, malware clustering, binary auditing, etc. In this paper, we present BinSign, a binary function fingerprinting framework. The main objective of BinSign is providing an accurate and scalable solution to binary code fingerprinting by computing and matching structural and syntactic code profiles for disassemblies. We describe our methodology and evaluate its performance in several use cases, including function reuse, malware analysis, and indexing scalability. Additionally, we emphasize the scalability aspect of BinSign. We perform experiments on a database of 6 million functions. The indexing process requires an average time of 0.0072 seconds per function. We find that BinSign achieves higher accuracy compared to existing tools.

Introduction

Reverse Engineering and Function Fingerprinting

Fingerprinting binary functions can be of paramount importance in reverse engineering. Function fingerprinting has many applications including compiler identification [START_REF] Rahimian | BinComp: A Stratified Approach to Compiler Provenance Attribution[END_REF], authorship analysis, clone detection, vulnerability detection, provenance analysis, malware detection, malware classification [START_REF] Alrabaee | On the Feasibility of Malware Authorship Attrubution[END_REF], etc. One benefit of function fingerprinting is tagging a suspicious binary as malicious or benign. The number and complexity of malware attacks have been growing significantly. In 2015, around 431 million new malware variants were uncovered [6]. Contrary to conventional signature-based detection, heuristic-based techniques are more effective and robust in detection and classification of new variants [START_REF] Ye | An Intelligent Pe-malware Detection System Based on Association Mining[END_REF].

Approach

An effective fingerprinting approach produces a unique and compact representation of the functionality of a binary function. Functions that perform similar functionalities should be assigned similar fingerprints. It must also be robust to minor byte-level discrepancies and differences in the structure of the Control-Flow-Graph (CFG). The probability of a fingerprint collision must be negligible. In this paper, we present BinSign, a fingerprinting framework for binary functions, which consists of two main components: (1) Scalable fingerprint generation and indexing of a large dataset, (2) Fingerprint matching. Our fingerprint generation approach relies on a set of features that are extracted from assembly functions combined with structural information from partial CFG traces.

To avoid pairwise comparison of a large volume of fingerprints, we use three mechanisms to facilitate achieving a scalable matching process. First, we leverage Locality-Sensitive Hashing (LSH) [START_REF] Rajaraman | Mining of Massive Datasets[END_REF] and min-hashing [START_REF] Andoni | Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions[END_REF] for selecting candidates. Second, we apply a filter based on the number of basic blocks of the CFG. Finally, BinSign system is distributed on multiple machines using Rabbit MQ [START_REF]RabbitMQ Web Site[END_REF] in order to further improve the performance and scalability. In addition, BinSign utilizes the Jaccard similarity to compute similarity scores between the target function and each candidate. To improve accuracy, features are ranked according to their significance while calculating the similarity score.

Contributions

Our contributions can be summarized as follows:

-We propose a fingerprinting approach for binary functions using features that capture syntactic, semantic and structural information of a function. -We design and implement an efficient and scalable matching framework to match a target function fingerprint against a large repository of fingerprints. -We evaluate BinSign in several use cases, including function reuse, malware analysis, obfuscation resilience, and function indexing scalability.

Paper Organization

This paper is structured as follows. Section 2 presents the underlying algorithmics of the components of our fingerprinting methodology, including the details of the fingerprint generation and matching algorithms. Experimental results are discussed in Section 3. Section 4 reviews the state-of-the-art approaches. Concluding remarks are ultimately presented in Section 5.

BinSign Methodology

BinSign utilizes meaningful features for function fingerprinting, which comprises of two main steps: fingerprint generation and fingerprint matching.

Threat Model

We design BinSign to help in the reverse engineering process. It is designed to be resilient to changes in the code such as those introduced by different compilers.

The fingerprints are designed to be resilient to light obfuscation including register replacement, register reassignment, dead-code insertion, code substitution, name stripping, and removal of symbolic information. BinSign is not intended to replace the reverse engineering process, but merely to support it. Unpacking and de-obfuscation lie outside the scope of our threat model.

Feature Extraction

It is important to select the right features that characterize the semantics of programs. The semantics of code operations can be captured by analyzing mnemonic groups and operand types even if the symbols are stripped. Each function's fingerprint includes a feature vector v fi ∈ V in the form of key/value pairs (k i , v i ). Features are extracted at two levels: global and tracelet features. Features that describe each basic block (such as the constants in that block) are combined into tracelet features. The structure of the CFG is captured in the function's fingerprint through the tracelet features (Table 1). The global features occur once per function and describe the function as a whole, such as the return type and function size (Table 2). The symbols "#" and " * " denote "number of" and "size of", respectively. Some features are common to both tracelet features and global features. We take into consideration the following groups of information. Characterization of Function Prototype: Each prototype carries valuable information, such as the return type, the number and types of arguments. Composition of CFG Instructions: These features capture the number of basic blocks and types of instructions in each block. The mnemonics and operands are extracted and normalized. The normalized mnemonics list contains a generalized representation of the instructions, with operands numbered according to their types. General registers are replaced with 1, memory references are coded as 2, etc. After that, a simple frequency analysis is performed: the number of occurrences of each instruction, and the total number of calls to registers and memory addresses are determined. Then, the instruction mnemonics are classified into 15 groups based on the type of operation. Next, the total number of instructions and the number of instructions per group are computed. Types of Local, System, and API Calls: Functions can be categorized according to the execution outcome on a system. System calls are interaction points with the operating system and provide valuable information on the runtime behavior. These calls are used to assign functionality tags. A functionality tag is an annotation assigned to code fragments that provides a high-level description of the context and side effects. Tags are useful for fast identification of specific groups of operations. As described in [START_REF] Rahimian | On the Reverse Engineering of the Citadel Botnet[END_REF], a function is assigned multiple tags if it encloses several system calls. Moreover, combinations of functionality tags can describe the overall functionality of the code regions and highlight the sequence of actions carried out for performing them (e.g., CRY+FIL+NET is translated to crypto-operations on a file, followed by network communication).

Fingerprint Generation

The fingerprint generation process is depicted in Figure 1. The approach consists of: ( 1 Disassembling and CFG Extraction: Given a binary file, the first step is to disassemble it using the industry-standard disassembler IDA Pro [START_REF]Hex-Rays IDA Pro[END_REF]. In order to capture the structural information of a function, we take into consideration its CFG because it captures syntactic elements (assembly instructions) and relationships (jumps/calls) between blocks.

Tracelet Generation: One of the objectives of BinSign is to generate fingerprints that capture not only the syntactic information of a function, but also its structure. The intent is to capture all execution traces of a function. However, extracting all paths from a CFG is computationally expensive, especially for large functions. Moreover, it would be redundant to consider the common nodes between different paths multiple times. To counter this issue, we adopt the idea presented in [START_REF] David | Tracelet-Based Code Search in Executables[END_REF], by decomposing function CFGs into partial traces of execution, namely tracelets. In BinSign, tracelets are comprised of two basic blocks. This means that each edge in the CFG results in one tracelet. Considering a larger number of basic blocks per tracelet results in redundant information without offering additional benefits. This solution allows us to generate execution traces more efficiently and without losing in functionality since all CFG nodes and edges are visited. After disassembling the function, extracting its CFG, and generating tracelets, the features described in section 2.2 are extracted.

Signature Hashing: We apply min-hashing [START_REF] Andoni | Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions[END_REF] in order to produce a compact representation of the signature. In essence, min-hashing is a technique that reduces the dimensionality of a set using a number of hash functions. Min-hashing is applied to the normalized instructions. The function's normalized instructions constitute a suitable representation of the functionality and can be used effectively in the fingerprint matching process. Each instruction is normalized by replacing the operands with a number that represents the operand's type. Then, every normalized instruction is hashed using all hash functions and the minimum hash value is selected. The collection of the minimum hash values represents the signature hash. Multiple random numbers (seeds) are used in order to generate many different hash functions. The seeds are generated randomly beforehand, and remain constant every time a new fingerprint is generated.

Fingerprint Matching

Through the matching process (Figure 2), a candidate set is selected. After that, the similarity between each candidate and the target is computed. Fingerprint Candidate Selection: Two filters are implemented. First, the functions are filtered by the number of basic blocks. Second, LSH [START_REF] Rajaraman | Mining of Massive Datasets[END_REF] is used. The idea is to divide the hash values of the min-hash signature into bands. Each band consists of multiple hash values. A fingerprint from the dataset is considered as a candidate if all hash values match in at least one band. The values of each band in the target min-hash signature is used to create a query to obtain candidates from the database. The results of all the queries are combined into the candidate set. Through multiple experiments, we find that a band size of seven hash values and a total of thirty bands constitute a suitable signature. Since LSH approximates the Jaccard similarity, this choice of band size and number of bands sets the similarity threshold to about 60%. According to [START_REF] Rajaraman | Mining of Massive Datasets[END_REF] an approximation of the threshold is calculated as

( 1 b ) 1 r
, where b represents the number of bands and r the size of band. To further reduce false positives, we also filter the fingerprints based on the number of basic blocks. It is unlikely for a function with a small number of basic blocks to match a function with a significantly larger number of blocks. Through experiments, we find that a threshold of 30% for the difference in the number of basic blocks is appropriate.

Fingerprint Similarity Computation:

A similarity score between the target fingerprint and each fingerprint in the candidate set is calculated using the Jaccard similarity. More precisely, the Jaccard similarity between the global features is calculated then combined with the Jaccard similarity between the tracelet features. Each feature in the fingerprint has a different effect on the similarity score, as some features are more significant than others. Therefore, each feature that influences the similarity score has a different weight. The weights are assigned using the gain ratio attribute evaluation algorithm provided by Weka [10] for ranking the features. Weka is a tool that offers implementations of several machine learning algorithms. This is performed through a supervised machine learning process where the names of the functions are known.

Experimental Results

We perform several experiments to evaluate BinSign in terms of accuracy, performance, and scalability. We also compare the accuracy with existing tools.

Dataset Description

To evaluate the scalability, we include fingerprints of 6 million functions generated from well-known libraries, malware samples, and system dynamic library files from Microsoft Windows. Additionally, we focus our matching experiments on slightly more than 23,000 functions of our dataset for a more precise evaluation of the accuracy. These functions are from different versions of the libraries: libpng, sqlite, and zlib. These files are compiled using Visual Studio (MSVC) 2010 and 2013. Zeus and Citadel malware samples are also included in the dataset. In our experiments, function names are not used during the matching process, but only for verification. If the candidate with the highest similarity score does not have the same name as the target function, we examine both functions manually. Manual examination is only performed for verification to calculate the accuracy, but it is not required by BinSign.

Comparison with Existing Tools

This experiment compares the accuracy of BinSign against Diaphora [START_REF] Diaphora | A Program Diffing Plugin for IDA Pro[END_REF] and PatchDiff2 [START_REF]Diffng Plugin for IDA[END_REF]. The tools Diaphora and PatchDiff2 are both IDA Pro plugins that can be used for comparing binary files. Diaphora offers different options when matching binary functions. We deactivate the option of using unreliable methods. We also activate the option of ignoring the function names.

We use the libraries libpng, sqlite, and zlib compiled using two compilers. We then compare the two binary files of each library resulting from the compilation using MSVC 2010 and MSVC 2013. By using two different compilers, we introduce some noise into the binary functions so that there are some differences introduced by the compilers. We attempt to match the functions in the file compiled by MSVC 2010 as the target set against the functions in the file compiled by MSVC 2013. We match each function in the target set using BinSign by finding the function in the candidate set with the highest similarity score. Table 3 displays the results of the comparison. The accuracy is calculated by finding the percentage of the correctly matched functions to the total number of functions in the binary file. BinSign consistently achieves the highest accuracy between the tools being compared. This is due to the fuzziness of the method BinSign is using to perform the matching. This allows BinSign to be more lenient when dealing with the modifications presented by different compilers. The difference in accuracy is due to the types of features considered by these tools and that they require an exact match for some of the features.

Function Reuse Detection

We attempt to detect reused functions between versions 1.2.5, 1.2.6, 1.2.7, and 1.2.8 of the zlib library, as well as between the libraries zlib and libpng.

Each version is used to match the corresponding functions in its consecutive version. We also attempt to match reused functions from zlib library in libpng. After manual inspection, we identify 52 reused functions. The function is considered to be matched correctly if the corresponding function in the other version of the library is ranked first with the highest similarity score. The results are shown in Table 4. The LSH similarity threshold is set once to 60% and once to 65%. The number of candidates presented in Table 4 is the sum of the size of the candidate sets for all target functions. Figure 3 plots the number of target functions against the total number of candidates. Increasing the number of functions increases the total number of candidates. There are other factors that affect the total number of candidates such as the size of the target functions. Smaller functions contain fewer distinctive features. As a result, they tend to have a larger candidate set. Therefore, the total number of candidates does not only depend on the number of target functions, but also on their characteristics and size. Figure 4 shows how the number of basic blocks of the functions affects the matching time. Most of the time is spent on computing the similarity scores. Therefore, the number of candidates and the size of the functions are important factors that affect the matching time.

The difference in accuracy when the LSH threshold is set to 60% against 65% is more significant in the first and third rows of Table 4. This is due to more functions with LSH similarity scores lying between 60% and 65% in these cases. When we compare the second and third rows of the table, we see that the third row has a better accuracy score when the threshold is set to 60%. However, this is not the case when it is set to 65%. This is because the comparison displayed in the third row includes more functions with similarity scores between 60% and 65%, which are filtered out when the threshold is increased.

Scalability Evaluation

We index 6 million fingerprints and measure the time it takes. On average, the indexing process requires around 0.0072 seconds per function. This includes the time for fingerprint generation and database communication.

Fingerprint Methodology Scalability: Using min-hashing and LSH, we enhance the scalability by selecting a candidate set through the banding technique.

To speed up the process, only candidates that are selected through our filters are considered instead of brute force matching. 5) using RabbitMQ [START_REF]RabbitMQ Web Site[END_REF]. It is an open source messaging software based on the international standard Advanced Message Queuing Protocol (AMQP) [START_REF]Advanced Message Queuing Protocol (AMQP)[END_REF]. Thanks to its simplicity, we find that it is more suitable to our purposes than other distribution frameworks that require a lot of processing for data analysis and synchronization with the server, leading to a lot of overhead, and thus slowing the process. To index several files, the binaries are distributed to different workers. The distribution is done depending on the power of each worker machine. Each worker runs multiple instances of IDA Pro simultaneously to process the files, generate the fingerprints, and store them in the database. Note that RxPY (reactive extension) is used to run the code in an asynchronous manner. The distribution is performed on a server machine with an Intel Xeon CPU E5-2630 v3 @2.40 GHz (2 processors) and 128 GB of RAM running Microsoft Windows Server 2008 64-bit, along with a PC with an Intel Core i7 CPU 920 @2.67 GHz and 12 GB of RAM running Microsoft Windows 7 64-bit.

Resilience to Different Compiler Optimization Levels

We use MSVC 2013 to compile version 1.2.8 of zlib with four optimization levels. MSVC 2013 offers the optimization levels: disabled optimization (Od), minimize size (O1), maximize speed (O2), or full optimization (Ox). We compile the zlib library with full optimization (Ox) and use the resulting binary functions as the target to match functions compiled using other optimization levels.

The results are presented in Table 5. The lowest accuracy score of 65.05% occurs when matching the fully optimized (Ox) functions against disabled optimization (Od). Compiling with optimization level O1 produces more similar functions to the fully optimized functions, which results in 87.85% accuracy. We find that compiling with the optimization levels Ox and O2 seem to produce identical assembly code in this case. Therefore, comparing the code compiled with O2 against O1 would produce similar results to Ox against O1. Accuracy After taking a closer look, we find that the size of the target functions has an effect on the accuracy. The accuracy of matching functions with different number of basic blocks is displayed in Figure 6. The functions with higher number of basic blocks are matched with higher accuracy. This is due to the fact that larger functions tend to contain more distinctive features. Small functions usually have features and structures that are fairly common. Therefore, there is a higher probability of mismatching smaller functions than larger ones.

When comparing the optimization levels Ox and Od, we notice a dip in the graph, which might seem counter-intuitive. This is because smaller functions (with 5 to 10 basic blocks) may have less room for optimization. However, larger functions (with 10 to 20 basic blocks) contain higher possibilities for optimization. Functions that are even larger (with around 25 basic blocks) tend to have more distinctive features, which increases the accuracy of the matching process.

Malware Similarity Analysis

Since the functions in Citadel are derived from the functions in Zeus [START_REF] Milletary | Citadel Trojan Malware Analysis[END_REF], we match one of these functions, namely the RC4 function. Citadel reuses the RC4 stream cipher function from Zeus with minor modifications [START_REF] Rahimian | On the Reverse Engineering of the Citadel Botnet[END_REF]. IDA Pro identifies 642 functions in Zeus and 896 functions in Citadel. We then generate fingerprints for all the functions and attempt to match the RC4 function. The time it takes to match the RC4 function is 0.463 seconds.

We find that the top match was in fact the modified RC4 function with a similarity score of 0.68787. The other matches with lower similarity scores are from different library files. The CFG of RC4 functions in Zeus and Citadel can be seen in Figure 7a and Figure 7b respectively. Although the number of basic blocks in the two CFG's is different, the RC4 function is still identified because the difference in the number of basic blocks is less than 30%.

Since many of the functions in Citadel are derived from the functions in Zeus, we attempt to match all the functions in Zeus. BinSign matches 591 out of 642 functions in Zeus to functions in Citadel. Out of the matched functions, 517 functions are matched with a high similarity score above 90%.

Obfuscation Resilience

Although heavy obfuscation is out of the scope of our threat model, we provide some insight into its effects. We use the Obfuscator-LLVM [START_REF] Junod | Obfuscator-LLVM: Software Protection for the Masses[END_REF] for this purpose. It offers three obfuscation techniques: control flow flattening, instruction substitution, and bogus control flow. After applying the three obfuscation techniques to a piece of code in C++, we add the three different obfuscated functions to the dataset. The function that results from instruction substitution is identified as a match with a high similarity score of 0.84399, which shows resilience to this type of obfuscation. However, the obfuscated functions resulting from control flow flattening and bogus control flow are not identified. The number of basic blocks increased by more than 30%. Therefore, the fingerprints are filtered out by our filter that considers the number of basic blocks.

Related Work

This section reviews research on binary fingerprinting and related domains.

Exact and Inexact Fingerprint Matching

Several studies focus on fingerprinting library functions in binary files (e.g., [START_REF] Bonfante | Code Synchronization by Morphological Analysis[END_REF][START_REF] Hex-Rays | Fast Library Identifiation and Recognition Technology: In-Depth[END_REF][START_REF] Jacobson | Labeling Library Functions in Stripped Binaries[END_REF]). Some approaches use exact matching and apply byte-level sequence patterns. IDA Pro is an industry-standard disassembler that is widely used by reverse engineers [START_REF] Jacobson | Labeling Library Functions in Stripped Binaries[END_REF][START_REF] Kinable | Malware Classification Based on Call Graph Clustering[END_REF]. It provides a built-in capability for recognizing standard library functions and hex code sequences that are generated by common C-family compilers through IDA F.L.I.R.T [START_REF] Hex-Rays | Fast Library Identifiation and Recognition Technology: In-Depth[END_REF]. Although F.L.I.R.T is a useful mechanism, it has limitations. Library functions with small byte-level discrepancies are not recognized. The inability to perform inexact matching is a major limitation. Other studies examine flexible signature matching techniques alongside graph-based analysis to measure the similarity between programs [START_REF] Bonfante | Code Synchronization by Morphological Analysis[END_REF][START_REF] Bourquin | Binslayer: Accurate Comparison of Binary Executables[END_REF][START_REF] Dullien | Graph-Based Comparison of Executable Objects (english version)[END_REF][START_REF] Jacobson | Labeling Library Functions in Stripped Binaries[END_REF]. Such approaches show higher recall in comparison to exact matching.

Graph-Based Binary Fingerprinting

The BinDiff algorithm [START_REF] Dullien | Graph-Based Comparison of Executable Objects (english version)[END_REF] inspired some works that use graph matching for various purposes (e.g., [4, 13-15, 21, 23, 27, 28]). One limiting factor is placing the attention on structural similarity, ignoring the instruction semantics of each basic block. Instruction hash comparison is a simple, fast technique to fingerprint functions and assembly instructions [START_REF] Jin | Binary Function Clustering Using Semantic Hashes[END_REF]. A hash value can represent the semantics of basic blocks. The work in [START_REF] Lakhotia | Fast Location of Similar Code Fragments Using Semantic 'Juice[END_REF] terms such values as semantic juice.

Source and Binary Clone Detection

Research on source code clone detection investigates four types of clones [START_REF] Cordy | Efficient Checking for Open Source Code Clones in Software Systems[END_REF][START_REF] Keivanloo | Internet-Scale Real-Time Code Clone Search via Multi-Level Indexing[END_REF]. Type I clones are exact clones. Type II clones preserve the syntactic structure with changes in identifiers, layout, comments, and types. Type III clones have altered fragments. Type IV clones are semantic clones. Applying source code clone detection techniques to disassemblies is challenging due to limited sourcelevel information. The research on binary clone detection measures the similarity between binary files [START_REF] Huang | BinSequence: Fast, Accurate and Scalable Binary Code Reuse Detection[END_REF][START_REF] Bonfante | Code Synchronization by Morphological Analysis[END_REF][START_REF] Chaki | Supervised Learning for Provenance-Similarity of Binaries[END_REF][START_REF] Elva | Semantic Clone Detection Using Method IOE-Behavior[END_REF][START_REF] Farhadi | Binclone: Detecting Code Clones in Malware[END_REF][START_REF] Ng | Expose: Discovering Potential Binary Code Re-use[END_REF]. The approach presented in [START_REF] Chaki | Supervised Learning for Provenance-Similarity of Binaries[END_REF] measures the provenance similarity of binaries using symbolic execution. Morphological analysis and static code synchronization is another solution for binary clone detection [START_REF] Bonfante | Code Synchronization by Morphological Analysis[END_REF]. These approaches are good candidates for detecting types III and IV clones. The dynamic analysis techniques that monitor input/output behavior of functions result in lower false positive rates in detection of type IV clones [START_REF] Jin | Binary Function Clustering Using Semantic Hashes[END_REF].

Conclusion

In this paper, we defined the main components of function fingerprinting, described the algorithms, and the processes of fingerprint generation and matching. The methodology was evaluated in terms of function matching, malware analysis, obfuscation resilience, and scalability. We showed that the methodology is effective and can improve the accuracy of exact and inexact fingerprint matching. BinSign outperformed existing tools and achieved a higher accuracy score.

We also described different measures undertaken to ensure BinSign's scalability. BinSign performed efficient fingerprint generation of 6 million functions such that the indexing process required 0.0072 seconds per function on average.

FingerprintFig. 1 :

 1 Fig. 1: Fingerprint Generation

Fig. 2 :

 2 Fig. 2: Fingerprint Matching

Fig. 3 :Fig. 4 :

 34 Fig. 3: Number of Target Functions vs. Number of Candidates

Fig. 5 :

 5 Fig. 5: Architecture of the Distribution Process

Fig. 6 :

 6 Fig. 6: Number of Basic Blocks vs.Accuracy After taking a closer look, we find that the size of the target functions has an effect on the accuracy. The accuracy of matching functions with different number of basic blocks is displayed in Figure6. The functions with higher number of basic blocks are matched with higher accuracy. This is due to the fact that larger functions tend to contain more distinctive features. Small functions usually have features and structures that are fairly common. Therefore, there is a higher probability of mismatching smaller functions than larger ones.When comparing the optimization levels Ox and Od, we notice a dip in the graph, which might seem counter-intuitive. This is because smaller functions (with 5 to 10 basic blocks) may have less room for optimization. However, larger functions (with 10 to 20 basic blocks) contain higher possibilities for optimization. Functions that are even larger (with around 25 basic blocks) tend to have more distinctive features, which increases the accuracy of the matching process.

Fig. 7 :

 7 Fig. 7: CFG of RC4 Function in (a) Zeus and (b) Citadel

Table 1 :

 1 Tracelet Features

	Data Constants	Constants, Strings, #Constants, #Strings
	Functionality Tags #API Tags, #Library Tags, #Mnemonic Groups
	Tracelet Info.	#Instructions, #Operands, Code Refs., #Code
		Refs., Function Calls, #Function Calls, Imported
		Functions, #Imported Functions

Table 2 :

 2 Global Features

	Data Constants	#Constants, #Strings
	Prototypes	Return Type, Arguments, #Arguments, *Arguments
	Functionality Tags #API Tags, #Library Tags, #Mnemonic Groups
	Function Info.

*Function, *Local Variables, Function Flags, Tracelets, #Tracelets, #Instructions, #Code Refs., #Out Calls, #Basic Blocks

Table 3 :

 3 Function Matching Comparison Between Tools

	Tool Name Library #Target Functions #Correct Matches Accuracy
		libpng 620	408	65.81%
	Diaphora	sqlite 1489	657	44.12%
		zlib	156	79	50.64%
		libpng 620	510	82.26%
	PatchDiff2	sqlite 1489	937	62.92%
		zlib	156	122	78.21%
		libpng 620	553	89.19%
	BinSign	sqlite 1489	1391	93.42%
		zlib	156	134	85.90%

Table 4 :

 4 Function Reuse Detection Results

	Library Versions	#Functions Threshold Accuracy #Candidates Time
	zlib1.2.5-zlib1.2.6	169	60% 65%	89.47% 78.11%	24970 11372	3.9s 2.8s
	zlib1.2.6-zlib1.2.7	183	60% 65%	94.67% 90.71%	30881 14947	3.7s 2.5s
	zlib1.2.7-zlib1.2.8	178	60% 65%	98.79% 88.76%	26965 12003	4.5s 3.7s
	zlib1.2.8-libpng1.6.17	52	60% 65%	100% 100%	4474 2147	4.7s 4.4s

Table 5 :

 5 Results of Matching Different Optimization Levels

	Optimization	Overall	Average
	Levels	Accuracy	Time
	Ox vs. Od	65.05%	4.2s
	Ox vs. O1	87.85%	4.3s
	Ox vs. O2	100.00% 0.26s

Table 6 :

 6 Candidates of RC4 Function from Citadel

	Function	Similarity Score
	sub_42E92D 0.68787
	sub_10034D0A 0.40042
	png_set_sCAL 0.35377

Acknowledgments. This work is supported by a research grant under the Department of National Defence/Natural Sciences and Engineering Research Council of Canada (NSERC) in collaboration with Google. In addition, the authors acknowledge the contribution of Nhat Nguyen in assisting with the implementation of the distribution mechanism and the web interface.


Jihye Kim
email: jihyek@kookmin.ac.kr

Hyunok Oh

Forward-Secure Digital Signature Schemes with Optimal Computation and Storage of Signers

Keywords: Forward secure, digital signature, fast signing/update, factoring

Forward-secure signatures minimize damage by preventing forgeries for past time periods when a secret key is compromised. Forwardsecure signature schemes are useful for various devices such as logging systems, unattended sensors, CCTV, dash camera, etc. Considering sensors equipped with limited resources and embedded real-time systems with timing constraints, it is necessary to design a forward-secure signature scheme with minimal overhead on signer's side. This paper proposes the first forward secure digital signature schemes with constant complexities in signature generation, key update, the size of keys, and the size of a signature. The proposed algorithms have O(k 3 )time complexity for each signing and key update algorithm and O(k)-size secret keys where k is an RSA security parameter. We prove the security of our proposed schemes under the factoring assumption in the random oracle model and present a concrete implementation of our schemes to demonstrate their practical feasibility.

Introduction

Forward-secure signature schemes mitigate the damage caused by a secret key exposure. The role of the digital logs and data as forensic values has boosted the need for strong authenticity of data. For example, audit logs record the "what happened when by whom" of the system. The forensic value of audit logs makes them an attractive target for attackers [START_REF] Bellare | Forward-security in private-key cryptography[END_REF]. An active attacker compromising a logging machine can modify log entries related to the past, erasing records of the attacker's previous break-in attempts. Forward secure digital signature schemes, of which goal is to preserve the validity of past signatures even if the current secret key has been compromised, become an effective solution to prevent this active attack as well as to provide strong authenticity for the recorded video frames.

Briefly, a forward-secure signature scheme divides the total time into T time periods and uses a different secret key in each time period (while the public key remains fixed). Each subsequent secret key is computed from the current secret key via a key update algorithm. Although it is ideal to have constant complexities regardless of the parameter T in computations and storage sizes overall, it is a challenging work. In the first forward-secure signature scheme proposed by Anderson [START_REF] Anderson | Two remarks on public-key cryptology -invited lecture[END_REF], the size of secret key increases linearly with T . In the Bellare and Miner (BM) scheme [START_REF] Bellare | A forward-secure digital signature scheme[END_REF] both public and secret key sizes are constant, but the signing and the verification time (of a single signature) grows linearly with T . Itkis and Reyzin [START_REF] Itkis | Forward-secure signatures with optimal signing and verifying[END_REF] (IR) propose a scheme to have constant complexities in signing and verification, however, at the expense of key update time and the secret key size which grow logarithmically with T . Malkin, et al. [START_REF] Malkin | Efficient generic forward-secure signatures with an unbounded number of time periods[END_REF] (MMM) proposed a generic forward secure signature scheme based on a hash chain tree with a constant size public key. Although the secret key size, the signature size, signing and verifying time are O(log T ), theoretically, the actual computation time and the storage requirement seem to be independent of T since the hash computation and size are relatively small compared with a public key signature scheme which it uses internally. However a signature in MMM contains two public keys and two signatures with an O(log T ) size hash chain. The resulting signature size is 4 times larger than BM and IR.

One of main hurdles when forward-secure signature schemes are deployed in the real systems is located in their non-constant signing/update overhead. For example, in the video recording devices for streaming applications, a captured video frame is compressed periodically, e.g, every 33ms. If a signature is generated for each frame, the signature computation with key update should be completed within 33ms. When an incident occurs, the stored video frames and their signatures are used for forensic analysis. In this scenario, the signing and update time should be short enough to meet the time constraint. On the contrary, the verification of the signatures may be performed when a forensic is required.

The goal of this paper is to construct forward-secure signature schemes efficient enough to cover even resource-and/or time-constraint devices such as unattended sensors and surveillance real-time streaming systems. To achieve this goal, the computation and size complexities on signer's side should be short and constant at least. For the practical usage like other previous schemes, the public key size also needs to be constant. Setup and verification times not directly related with the signing device are comparatively less important.

Contributions. Our schemes extend the Bellare-Miner (BM) scheme [START_REF] Bellare | A forward-secure digital signature scheme[END_REF] and the Abdalla-Reyzin (AR) scheme [START_REF] Abdalla | A new forward-secure digital scheme[END_REF] to provide a short and constant signature computation time. The proposed schemes, denoted as Fast-BM and Fast-AR, require the same constant size memory for secret/public keys, and generate the same constant size signatures as BM and AR, respectively. The signature computation time complexity is O(k 3 ) in our schemes, while the signature computation time complexity is O(k 2 T ) in the BM scheme, and O(k 2 lT ) in the AR scheme, where l is a security parameter representing the bit length of the hash output, k is a security parameter denoting the bit length in RSA (modulo N is k-bit integer), and T represents the number of periods. Surprisingly, there is no significant performance degradation in other metrics, while we optimize the signing algorithms of BM and AR. In the experiment, our algorithms generate a signature and update their secret keys in 25 ms with security parameters k = 2048 and l = 160 regardless of the total number of periods T . The results show that our proposals are fast enough not only for normal applications but also for real-time streaming applications. The proposed Fast-BM and Fast-AR schemes are secure under the factoring assumption in the random oracle model.

We begin, in the next section, by describing background for forward secure digital signature schemes. Section 3 proposes our fast forward secure digital signature schemes with explaining the underlying schemes. Section 4 discusses the security of the proposed schemes. In Section 5, experimental results present quantitative measurements. We describe related work in Section 6 and summarize our conclusion in Section 7.

Background

This section reviews the syntax and security definitions of a forward secure digital signature scheme and defines its formal notion of security. All definitions provided here are based on those given in [START_REF] Bellare | A forward-secure digital signature scheme[END_REF][START_REF] Abdalla | A new forward-secure digital scheme[END_REF]. We also present the underlying cryptographic assumptions that our proposal relies on. We introduce some basic notations. If S is a set then s $ ← S denotes the operation of picking a random element s of S. We write A(x, y, • • • ) to indicate that A is an algorithm with inputs x, y, • • • and by z ← A(x, y, • • • ) we denote the operation of running A with inputs (x, y, • • • ) and letting z be the output.

Forward secure signature schemes

A forward secure signature scheme is a key-evolving signature scheme. We follow the definition of forward secure signature schemes in [START_REF] Bellare | A forward-secure digital signature scheme[END_REF][START_REF] Abdalla | A new forward-secure digital scheme[END_REF].

Definition 1 (Key-evolving signature scheme). A key-evolving digital signature scheme is a set of four algorithms: FSIG = (Setup, Sig, Upd, Ver), where:

-Setup: The key generation algorithm is a probability algorithm which takes as input a security parameter l and the total number of periods T and returns a pair (SK 0 , P K), the initial secret key and the public key. -Sig: The signing algorithm takes as input the secret key SK i for the current time period i and the message M to be signed, and returns a pair i, s , the signature of M for time period i. -Upd: The key update algorithm takes as input the secret key SK i for the current interval and returns a new secret key SK i+1 for the next interval. -Ver: The verification algorithm takes as input the public key P K, message M and a candidate signature i, s , and returns 1 if i, s is a valid signature of M , or 0, otherwise. It is required that Ver PK (M, Sig SKi (M)) = 1 for every message M and time period i.

We assume that the secret key SK j for period j ≤ T always contains the value j itself and also contains the value T of the total number of periods. Finally, we adopt the convention that SK T +1 is the empty string and Upd(SK T ) returns SK T +1 .

Security: The adversary executes the usual adaptive chosen-message attack (cma) until it breaks in and learns the secret key for a given time period. The adversary is then considered successful if it can create a valid forgery on a new message for a previous time period. Formally, this adversary, denoted by F , is modeled via the following experiment. The adversary, denoted by F , runs in three phases. In the cma phase, F has access to a sign oracle. F is allowed to query multiple signatures in the same period. In the break-in phase, F is given the secret key SK j for the specific interval j. Finally, in the forgery phase (forge), F outputs a pair of a signature and a message. The adversary is successful if it forges a signature of any new message (not previously queried to the signing oracle) for any time period prior to j. The formal experiment is described in the following: Definition 2 (Forward-security). Let FSIG=(Setup, Sig, Upd, Ver) be a keyevolving signature scheme and F an adversary as described above. Let

F-Forge(FSIG, F) : (SK0, P K) $ ← Setup(k, • • • , T); j ← 0 repeat j ← j + 1; SKj ← Upd(SKj ); d ← F Sig SK j (•) (cma, P K) until (d = breakin) or (j = T ) If (d =
Succ fwsig (FSIG[k, • • • , T], F) denote the probability that the experiment F-Forge(FSIG[k, • • • , T ], F ) returns 1.
Then the insecurity of FSIG is the function

InSec fwsig (FSIG[k, • • • , T]; t, q sig ) = max{Succ fwsig (FSIG[k, • • • , T], F)},
where the maximum is taken over all adversaries F making a total of at most q sig queries to the signing oracles across all the stages and for which the running time of the above experiment is at most t.

3 Fast Forward Secure Digital Signature Schemes

Our proposed schemes extend the previous forward secure signature schemes proposed by Bellare and Miner (BM) [START_REF] Bellare | A forward-secure digital signature scheme[END_REF] and by Abdalla and Reyzin (AR) [START_REF] Abdalla | A new forward-secure digital scheme[END_REF].

Since the way of extension is the same for each, we describe our scheme focusing on the AR version (which has a simpler parameter setting). We first overview the scheme proposed by Abdalla-Reyzin (AR) in [START_REF] Abdalla | A new forward-secure digital scheme[END_REF] and then describe our proposed schemes.

Overview of the AR scheme

The AR scheme [START_REF] Abdalla | A new forward-secure digital scheme[END_REF] defines T the maximum number of periods and extends the 2 l -th root signature scheme [START_REF] Ong | Fast signature generation with a fiat shamir-like scheme[END_REF] to have the forward security property. The initial secret key S 0 is arranged as 2 l(T +1) -th root of a public key U . For each period, the secret key is updated by raising it to the 2 l power and thus the secret key at the period j becomes S j = S 2 l(T +1-j)

0

. At period j, the signer proves the knowledge of the 2 l(T +1-j) -th root of U , of which computational cost is proportional to T . Thus, as T increases, the signing time increases. The size of T depends on the application and is possibly large in general to avoid frequent setups. For instance, assume that a signature is generated and a secret key is updated every second. In order to provide a forward security in this device for a year, T should be no less than 31,536,000 (= 60 × 60 × 24 × 365). AR (of which signature computation depends on T ) may be impractical to be used for applications with this large T setting.

Fast-AR

Algorithm 1 summarizes the key setup, the secret key update, the sign, and the verification of our proposed algorithm called Fast-AR. In the proposed algorithm, all numbers including secret keys (S j ), a public key (U ), random numbers (R), and their exponentiations (Y ) are chosen in g where g is a generator of a large subgroup in Z * N . In the following, we describe our approach and details of each algorithm.

Setup: We generate a safe RSA (or a safe-prime product RSA) modulus N = pq where p, q, p ′ , and q ′ are primes such that p = 2p ′ + 1, and q = 2q ′ + 1. Note that p and q are congruent 3 mod 4 and N becomes a Blum integer. Pick a random element g s.t. g generates a maximum subgroup in Z * N , i.e. ord(g) = 2p ′ q ′ and s.t. -1 ∈ g . Note that this holds for about half of the elements in Z * N , and it is easily tested. In addition, the Jacobi symbol of g, (g|N ) = -1.

Additionally, we compute X = g 2 l(T +1) mod N . Using g and X, we can efficiently compute l(T + 1) squaring operations of any group element in g , given the order of the element. Thus, to compute U = S 2 l(T +1) 0 mod N where S 0 = g s mod N for some known s, we compute X s mod N instead. (The same technique is used in the sign algorithm.)

Since the group size φ(N )(= (p -1)(q -1)) is known at setup, computation of X = g 2 l(T +1) mod N has O(k 3 )-time complexity. A secret key S is chosen from g by selecting a random number s in Z N/2 and computing S = g s mod N . A public key U (≡ S 2 l(T +1) ≡ g s2 l(T +1) ≡ X s (modN )) is computed by raising X to the s as we describe above. After computing a secret key and a public key, the primes p, q and the chosen random number s are discarded. g and X are stored in a secret key.

Sign and Update: In AR, the signing overhead occurs mainly due the computation of Y ← R 2 l(T +1-j) mod N for a chosen random R at period j. Since the computation requires l(T + 1 -j) squaring operations of R, the computation complexity is proportional to T . Recall that we select a generator g (of a maximum subgroup of Z * N ) and compute g 2 l(T +1) denoted as X in advance. In the signing procedure of our scheme, we generate R by raising g to a random number e in Z N/2 . Then since Y is R 2 l(T +1) ≡ g e2 l(T +1) ≡ X e ( mod N ), Y can be computed by raising X to the e. So the computation time of Y does not rely on T . After computing R and Y , e is erased. Note that the computation of Y in our scheme is different from AR: Y = R 2 l(T +1) in our scheme, while Y = R 2 l(T +1-j) in AR. I.e., the computation of Y in our scheme is independent of period j, unlike AR. Therefore, after we compute X = g 2 l(T +1) once (in setup), it can be reused at every period. The verification in our scheme is modified accordingly, which is slightly different from AR and slower than AR, but has the same computation complexity as AR.

The key update algorithm is the same as AR, which requires l times squaring operations only.

Algorithm 1 Fast-AR function Setup(k, l, T )
Pick random p ′ and q ′ such that p(= 2p ′ + 1), q(= 2q ′ + 1), p ′ , q ′ are prime, and p and q are k/2 bit and set N ← pq Pick a random element g s.t. g generates a maximum subgroup in Z * N , i.e. ord(g) = 2p ′ q ′ , and such that -1 ∈ g

x ← 2 l(T +1) mod (p -1)(q -1); X ← g x mod N s $ ← Z N/2 ; S0 ← g s mod N ; U ← X s mod N SK ← (N, T,g,X, 0, S0); P K ← (N, U, T ) return (P K, SK) end function function Upd(SK) : parse SK as (N, T,g,X, j, Sj ) ,(Z,σ)) end function function Ver(M, P K, sign) : parse P K as (N, U, T ); parse sign as (j, (Z, σ))

if j=T then SK ← ǫ else SK ← (N, T,g,X, j + 1, S 2 l j mod N ) end if return SK end function function Sig(M, SK) : parse SK as (N, T,g,X, j, Sj ) e $ ← Z N/2 ; R ← g e mod N ; Y ← X e mod N ;σ ← H(j, Y, M); Z ← RS σ j mod N return (j
if Z ≡ 0(modN ) then return 0 else Y ′ ← Z 2 l(T +1) /U σ2 lj mod N if σ = H(j, Y ′ , M) then return 1 else return 0 end if end if end function
Verification: As mentioned early, our verification algorithm is slightly different from AR due to the different exponentiation number for Y . While the verification tests whether Y is equal to Z 2 l(T +1-j) U σ in AR, it checks whether Y is equal to Z 2 l(T +1) /U σ2 lj in our scheme. On average, our verification requires twice computation than AR.

Correctness: For a given signature of (j, (Z, σ)) for message M , the verification is to check whether σ = H(j, Y ′ , M ) where

Y ′ ← Z 2 l(T +1) /U σ2 lj . Since Z = RS σ j = g e S 2 lj σ 0 and (g e ) 2 l(T +1) = X e = Y , Z 2 l(T +1) = Y S σ2 lj 2 l(T +1) 0 = Y U σ2 lj .
So the verification works correctly.

Security Analysis

Since the proposed Fast-AR scheme is similar to the existing AR scheme except that numbers are chosen in g rather than Z * N in a signature generation, the security proof is similar to the proof of AR.

Let k and l be two security parameters. Let p = 2p ′ + 1, q = 2q ′ + 1, p ′ , and q ′ be primes and N = pq be a k-bit integer (Since p ≡ q ≡ 3 (mod 4), N is a Blum integer). Let Q denote the set of non-zero quadratic residues modulo N . Note that for x ∈ Q, exactly one of its four square roots is also in Q. In the following description, x $ ← g denotes that r $ ← Z N and x ← g r mod N for ord(g) = 2p ′ q ′ . Lemma 1. Given α = 0, λ > 0, v ∈ Q and X ∈ g such that v α ≡ X 2 λ (mod N ) and α < 2 λ , one can easily compute y such that v ≡ y 2 (modN ).

Proof. Let α = 2 γ β where β is odd. Note that λ > γ. Let β = 2δ + 1. Then (v 2δ+1 ) 2 γ ≡ v α ≡ X 2 λ (modN ), so v 2δ+1 ≡ X 2 λ-γ (modN ). Note that it is allowed to take roots of degree 2 γ since both sides are in Q. Let y = X 2 λ-γ-1 /v δ mod N . Then y 2 ≡ X 2 λ-γ /v 2δ ≡ v(modN ). Note that since α < 2 λ , λ -γ -1 ≥ 0. Theorem 1. If there exists a forger F for FSIG[k, l, T] that runs in time at most t, asking at most q H hash queries and q S signing queries, such that Succ fwsig (FSIG[k, l, T], F) ≥ ǫ, then there exists an algorithm A that factors Blum integers generated by FSIG.key(l, T) in expected time at most t ′ with probability at least ǫ ′ , where

t ′ = 2t + O(k 2 lT + k 3 ), and ǫ ′ = (ǫ-2 3-k qS (qH +1)) 2 2T 2 (qH +1) -ǫ-2 3-k qS (qH +1) 2 l+1 T .
Proof. Suppose that there exists a forger F against F ast -AR scheme that succeeds with ǫ in time t. We construct an algorithm A using F as a subroutine to factor a given Blum-Williams integer N with a probability of ǫ ′ within t ′ time. The goal is to find a pair (p, q) such that N = pq.

A is constructed as follows:

Setup 1. select g $ ← Z * N such that -1 ∈ g [Given a
safe RSA modulus N , with probability about 1/2 we have ord(g)=2p ′ q ′ .] 2. Sign query for M at the j-th period: H(j,Y,M ) is defined then A sets f ail 1 ← true and aborts the execution of F ; otherwise H(j, Y, M ) ← σ. A returns (j, (Z, σ)). Since there are at most q H entries defined in tables H, the probability that f ail 1 happens is at most q H /2 l per sign query. Consider j > b ′ . Since secret S j = v 2 l(j-b ′ -1) , Sig(M, SK) can be performed and (j, (Z, σ)) is returned. Factoring of N Assume that F outputs a forged signature (j, (Z, σ)) for a message M where σ is a hash query for H(j, Y, M ). Assume that the forgery period j is no later than the break-in period b ′ or j ≤ b ′ . If F forges the signature without querying on H(j, Y, M ) then A sets f ail 2 ← true and aborts the execution of F . A resets F with the same random tape as the first time, and runs it again, giving the exact same answers to all F 's queries before the hash query of H(j, Y, M ). On the query of H(j, Y, M ), A comes up with a new answer σ ′ $ ← {0, 1} l , sets H(j, Y, M ) ← σ ′ . Then F returns (j, (Z ′ , σ ′ )). If the second forgery was not based on hash query on H(j, Y, M ) then A fails.

If j ≤ b ′ then Z $ ← g ; σ $ ← Z N/2 ; Y ← Z 2 l(T +1) v 2 l(T -b ′ +j) σ mod N . Y satisfies that Z 2 l(T +1) ≡ Y U 2 lj σ (modN ) since U σ = v 2 l(T -b ′ ) σ mod N . If
We know the following two equations must hold:

Z 2 l(T +1) ≡ Y U 2 lj σ (mod N ) and Z ′2 l(T +1) ≡ Y U 2 lj σ ′ (mod N ). Dividing, we get ( Z Z ′ ) 2 l(T +1) ≡ U 2 lj (σ-σ ′ ) (mod N ). From the setup, we know that U ≡ v 2 l(T -b ′ ) (mod N ). So we can write ( Z Z ′ ) 2 l(T +1) ≡ v 2 l(T +j-b ′ ) (σ-σ ′ ) (mod N ).
Taking roots of degrees 2 l(T +j-b ′ ) of both sides, which we are allowed to do because both sides are in Q and

remain in Q, because v is a square, v σ-σ ′ ≡ ( Z Z ′ ) 2 l(b ′ +1-j) (mod N )
. By applying lemma 1, our algorithm can easily compute a square root of v, denoted as x, by setting α = σ -σ ′ , X = Z/Z ′ , and λ = l(b ′ + 1 -j). If x ≡ ±w mod N then abort. Otherwise, we compute h ← gcd(w -x, N ) which is a non-trivial factor of N . Note that to argue the extracted square root of v differs from ±w, subgroup g should contain at least another square root of v which is not -w. It cannot be -w since -1 does not belong to g by construction. Such an element exists in g because, if the Jacobi symbol of g equals to -1 (or (g|N ) = -1), g p ′ q ′ must be a non-trivial square root of unity in Z * N . As a consequence, g p ′ q ′ • w is another square root of v that belongs to g . Since the signing oracle and the break-in oracle never use w, the knowledge extractor allows to extract g p ′ q ′ with probability 1/2. The computations of the probability and the running time are identical to [START_REF] Abdalla | A new forward-secure digital scheme[END_REF].

5 Experiment We implement the proposed Fast-BM and Fast-AR schemes using openssl library in C. For comparison, we implement BM [START_REF] Bellare | A forward-secure digital signature scheme[END_REF], AR [START_REF] Abdalla | A new forward-secure digital scheme[END_REF], IR, optimized IR (IROpt) [START_REF] Itkis | Forward-secure signatures with optimal signing and verifying[END_REF], and MMM [START_REF] Malkin | Efficient generic forward-secure signatures with an unbounded number of time periods[END_REF]. We use GQ [START_REF] Guillou | A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory[END_REF] as public key signature scheme in MMM. All schemes except MMM generate a short size signature of which size is k while MMM generates a signature of which size is 4k, where k is the bit-length of RSA modulus N . The experiment is performed on Intel i5 2.6GHz laptop with 16GB RAM under OS X. The hash length (l) is fixed to 160 bit. Figure 1 illustrates the key setup time, the signing time per message, the key update time, and the verification time per message by varying the number of periods T from 10 to 100000 denoted as x axis when the security key parameter k is 2048. The y axis represents the execution time in second.

Figure 1 (a) shows the setup time. As T increases, the setup time becomes significantly large in IR and IROpt. For instance, it is 1,000 seconds when T =100,000, and it will be 10,000 seconds when T =1,000,000 in IR and IROpt while in Fast-BM and Fast-AR it is a few ten seconds in which a safe RSA is generated. Figure 1 (c) indicates the key update time. In BM, AR, MMM, Fast-BM, and Fast-AR, the key update time is constant only depending on k and l while it is proportional to T and log T in IR and IROpt, respectively.

Figure 1 (d) denotes the verification time. The verification time is proportional to T in BM, AR, Fast-BM and Fast-AR since T number of exponentiation operations are performed for verification in those algorithms, while it is irrelevant to T in IR, IROpt, and MMM.

Figure 2 illustrates the setup, signing, update, and verification times by varying k which is the bit-length of RSA modulus N when l=160 and T =10000. The setup time increases faster in IR, IROpt, Fast-BM, and Fast-AR since they use a safe RSA where N = pq, p = 2p ′ + 1, q = 2q ′ + 1, and p, q, p ′ , q ′ are prime. When k is 2048, BM, AR, MMM, Fast-BM, and Fast-AR algorithms show a similar setup time.

Figure 2 (b) shows the signing time per message. Since the signing time in all algorithms except Fast-BM and Fast-AR is proportional to k 2 if T and l are fixed, the signing time increases similarly in all algorithms as k increases. On the other hand, the time increases faster in Fast-BM and Fast-AR as k increases. Fast-AR is as fast as Fast-BM while AR is l time slower than BM since Fast-AR does not require l(T + 1) squares. The pioneering studies addressing the forward secure signatures were first proposed by Anderson [START_REF] Anderson | Two remarks on public-key cryptology -invited lecture[END_REF] and subsequently formalized by Bellare and Miner in [START_REF] Bellare | A forward-secure digital signature scheme[END_REF]. In a forward-secure signatures scheme, the forward-security property is attained by dividing time into T discrete intervals, and using a different secret key within each interval. The main challenge in designing forward-secure signature schemes is efficiency: an ideal scheme must have constant (public and secret) key sizes, constant signature size as well as constant signing, verification, and (public and secret) key update operations.

k + l k + 2l (log l + log t + 2)l + 4k k + l k + l setup O(k 3 + lT k 2 ) O(k 3 + lT k 2 ) O(l 3 T + k 3 ) O(k 3 + l 2 log l) O(k 3 + lk 2 log(T )) O(k 3 + k 2 log(lT )) sign O(k 2 (T + l)) O(k 2 lT ) O(k 2 l) O(k 2 l) O(k 3 ) O(k 3 ) update O(k 2 l)) O(k 2 l) O(k 2 lT ) O(k 2 l log(T )) O(k 2 l + l 2 log t) O(k 2 l) O(k 2 l) verification O(k 2 (T + l)) O(k 2 lT ) O(k 2 l) O(k 2 l) O(k 2 (T + l)) O(k 2
In the first category, the schemes use some generic method in which a master public key is used to certify the current public key for a particular time period (via a chain of certificates). Usually, these schemes increase storage space by noticeable factors in order to maintain the current (public) certificates and the (secret) keys for issuing future certificates. They also require longer verification times than ordinary signatures do, because the verifier needs to verify the entire certificate chain in addition to verifying the actual signature on the message. There is, in fact, a trade-off between storage space and verification time. These schemes include the tree-based scheme of Bellare and Miner [BM99] (requiring storage of about O(log T ) secret keys and non-secret certificates, and verification of about O(log T ) ordinary signatures), the scheme of Krawczyk [START_REF] Krawczyk | Simple forward-secure signatures from any signature scheme[END_REF] (requiring storage of T non-secret certificates, and verification of only 2 ordinary signatures), and the scheme of Malkin, et al. [START_REF] Malkin | Efficient generic forward-secure signatures with an unbounded number of time periods[END_REF] has constant-size public key while the secret key size, the signature size, signing and verifying time are O(log t) where t denotes the time interval index which is less than T . The scheme of Holt [START_REF] Holt | Logcrypt: forward security and public verification for secure audit logs[END_REF] has constant-size secret key and signatures but requires T non-secret certificates storage/communication to verify signatures. The generic construction proposed by Libert, et al. [START_REF] Libert | Forward-secure signatures in untrusted update environments: efficient and generic constructions[END_REF] has a non-constant signature size and computational overhead and the exact complexities depend on the underlying schemes.

In the second category, the schemes are built upon standard signature schemes. The main advantage of these schemes is that they achieve better dependence on T . In particular, they typically have constant size parameters. The first such scheme is based on the Fiat-Shamir signature scheme [START_REF] Bellare | A forward-secure digital signature scheme[END_REF]. Abdalla and Reyzin scheme [START_REF] Abdalla | A new forward-secure digital scheme[END_REF] shortens secret and public keys of at the expense of signing and verifying time. Itkis and Reyzin scheme [START_REF] Itkis | Forward-secure signatures with optimal signing and verifying[END_REF] has shorter signing and verifying time derived from the underlying Guillou-Quisquater signature scheme [START_REF] Guillou | A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory[END_REF] at the expense of logarithmic key update time and the secret key size. Kozlov and Reyzin [START_REF] Kozlov | Forward-secure signatures with fast key update[END_REF] propose another scheme based on a similar optimizing technique used in [START_REF] Itkis | Forward-secure signatures with optimal signing and verifying[END_REF]. The scheme is an improved version of [START_REF] Itkis | Forward-secure signatures with optimal signing and verifying[END_REF], and the key update time and the secret key size grow logarithmically in T . However, linear-time operations are needed at the beginning of each period in the scheme.

Boyen, et al. [START_REF] Boyen | Forward-secure signatures with untrusted update[END_REF] proposed a forward-secure signature scheme, where the secret key is encrypted with a second factor such as a user's password and can be updated in its encrypted form. The scheme in [START_REF] Boyen | Forward-secure signatures with untrusted update[END_REF] based on [START_REF] Boneh | Hierarchical identity based encryption with constant size ciphertext[END_REF] features a constant signing time at the expense of its key update time in O(log T ), its secret key size in O(log 2 T ), its public key size in O(log T ), and comparatively stronger cryptographic assumption. It makes use of a very specific mathematical setting consisting of groups equipped with a bilinear mapping whose computation is expensive. Abdalla, et al. [START_REF] Abdalla | Tighter reductions for forwardsecure signature schemes[END_REF] proposed a variant of [START_REF] Itkis | Forward-secure signatures with optimal signing and verifying[END_REF] to have a much tighter security reduction, however, assuming stronger security assumptions.

Conclusion

In this paper, we propose fast forward secure digital signature schemes called Fast-BM and Fast-AR which provide fast signing and key update with constant size public and secret keys, and a short constant size signature. The proposed schemes are applicable to real-time surveillance streaming applications as well as the traditional forward secure signature systems. In the proposed schemes, the signing and the key update are performed in O(k 3 ) meaning that they are independent of the maximum period T , where k denotes the bit length of module N in RSA. In real implementation, the signing and the update can be performed within 25ms in the proposed schemes regardless of T when k = 2048 while they require 200ms in the optimized IR. The signature size is only 2240 bit when k=2048, and l 160 in our schemes. Fast-BM and Fast-AR schemes are secure under the factoring assumption in the random oracle model which is a weaker assumption than a strong RSA which IR is based on.

  breakin) and (j = T ) then j ← T + 1 (M, b, s ) ← F (forge, SKj) If Ver(M, b, s ) = 1 and 1 ≤ b < j and M was not queried of Sig SK b (•) in period b then return 1 else return 0

$Simulation 1 .

 1 ← g ; v ← w 2 mod N [ Will try to find a square root of v that is different from w.] 3. b ′ $ ← {1, • • • , T } [ Choose break-in period hoping that the break-in will occur after b ′ period, and the forgery will be at b ′ or earlier.] 4. U ← v 2 l(T -b ′ ) [ The intention is that S b ′ 2 l = v mod N .] 5. P K ← (N, T, U ) [Build a public key.] Now, we will explain how A simulates. Hash query simulation : If H(j, Y, M ) is undefined then H(j, Y, M ) $ ← {0, 1} l . It returns H(j, Y, M ).

3 .

 3 Update simulation : If j ≤ b ′ then nothing is performed. Otherwise Upd(M, SK) is called. 4. Break-in simulation at the b-th period: If b ≤ b ′ then A sets f ail 3 ← true and aborts the execution of F . Otherwise, A returns S b such that S b = S 2 l(b-b ′ ) b ′ = v 2 l(b-b ′ -1) .

Fig. 1 :

 1 Fig. 1: Execution time variation as T varies when l = 160 and k = 2048

Fig. 2 :

 2 Fig. 2: Execution time variation as k varies when T = 10000

Figure 1 (

 1 Figure 1 (b) represents the signing time per message. The signing time is proportional to T in BM and AR while it is independent of T in IR, IROpt,

Figure 2 (

 2 c) shows the key update time. As k increases, the key update time increases in all schemes. In IR and IROpt, the key update time increases slowly since the effect of T against k decreases where the update time complexities in IR and IROpt are O(k 2 T ) and O(k 2 log T ) while they are O(k 2 ) in the other algorithms.

Figure 2 (

 2 d) represents the verification time. Regardless of k, IR and IROpt show the shortest verification time.

Table 1 :

 1 Comparison of BM, AR, IR, optimized IR, MMM, Fast-BM, and Fast-AR

	Criteria	BM	AR	IR	IROpt	MMM	Fast-BM	Fast-AR
	public key size	k(l + 1)	2k	2k		l	k(l + 1)	2k
	secret key size	kl	k	3k + l k(log(T ) + 2) + l (log l + log t + 2)l + 2k	kl	k
	signature size	2k

Table 1

 1 summarizes the key sizes, setup time, signing time per message, key update time, and verification time in BM, AR, IR, IROpt, MMM, Fast-BM and Fast-AR. Fast-BM and Fast-AR reduce the signing time compared with BM and AR without sacrificing the other parameters.

	lT )

Acknowledgments

This research was supported by IT R&D program MKE/KEIT (No. 10041608, Embedded system Software for New-memory based Smart Device), by Next-Generation Information Computing Development Program through NRF funded by the Ministry of Science, ICT & Future Planning (No. NRF-2016M3C4A7937117), and by Basic Science Research Program through NRF funded by the Ministry of Education(No. 2016R1D1A1B03934545).


Emilie † Dargaud
email: dargaud@gate.cnrs.fr

Gate

Active firms in horizontal mergers and cartel stability *

Keywords: Mergers, Coalitions, Product differentiation JEL classification: L.10, L.13, L.20

In this paper, we study the optimal number of active firms in a coalition and in a merger. We consider two kinds of game : a merger game and a coalition game, both in the context of price competition with horizontal product differentiation. These are two-stage games. The first stage consists of determining the number of active firms; the second stage is price competition between active firms. Firms belonging to the same owner or to the same coalition play cooperatively between themselves but face competition between other firms.

We show that when there is no competitive pressure (i.e. no outside firm) then only merged equilibria can occur in the merger case. In the coalition case we obtain a similar result in which the number of active firms in the second stage is less than the initial number of firms.

Moreover we show that if competitive pressure is high enough then the initial number of firms in the industry is the same as the number of active firms in the last stage for each kind of game.

Introduction

In their seminal paper (1983), Salant, Switzer and Reynolds (SSR) [START_REF] Salant | Losses due to merger : the effects of an exogenous change in industry structure on Cournot-Nash equilibrium[END_REF] have shown that a merger in a standard Cournot framework with linear demand and linear costs is not profitable unless a large majority of the relevant firms are involved in the merger (80 %). This is so because outsiders benefit more than the firms participating in the merger, the "insiders". Since production costs are linear, any coalition of firms is indifferent to how total production is divided between the members of the coalition, so that every coalition of firms behaves as if it were a single firm. [START_REF] Perry | Oligopoly and the incentive for horizontal merger[END_REF] [START_REF] Perry | Oligopoly and the incentive for horizontal merger[END_REF] but also [START_REF] Farrell | Horizontal mergers: an equilibrium analysis[END_REF] [START_REF] Farrell | Horizontal mergers: an equilibrium analysis[END_REF] have challenged the view that a merged firm is no larger than any of the constituent firms. These papers introduce the existence of some crucial assets that are in limited supply in order to capture the notion that some firms are larger than others in a homogeneous product industry. This assumption implies rising marginal cost of output production and, consequently, internal cost savings from mergers could make a merger profitable.

Deneckere and Davidson (1985) [START_REF] Deneckere | Incentives to form coalitions with Bertrand competition[END_REF] have found an opposite result in the case of price competition with differentiated products so that a merger is always beneficial for the insiders.

Kamien and Zang (1990) [START_REF] Kamien | The limits of monopolization through acquisition[END_REF] have explored the possibility of endogenous monopolization of a homogeneous product Cournot oligopoly through one firm's acquisition of the others. They adopt two different approaches; first, an analysis of a centralized game : an owner who has acquired several firms behaves as one entity (as in SSR, 1983). Secondly, they explore the possibility for an owner, possessing several firms, to choose the optimal number of active firms, each of them competing between themselves, this being a decentralized game. More precisely, in this kind of game, they emphasize that an owner, possessing several firms, chooses to operate more than one firm. They show that, for the two kinds of game, monopolization can only occur in industries composed ex-ante of a small number of firms. Moreover, in the centralized game (SSR context (1983)) with a large number of firms, merged equilibria (that means the number of active firms is fewer than the initial number of firms) are non-existent. This confirms and strengthens the SSR's results (1983).

More recent literature takes into account strategic delegation (Gonzalez-Maestre and Lopez-Cunat (2001) [START_REF] Gonzalez-Maestre | Delegation and mergers in oligopoly[END_REF] or [START_REF] Ziss | Horizontal mergers and delegation[END_REF] [START_REF] Ziss | Horizontal mergers and delegation[END_REF]) to study merger profitability. What differs from the decentralized game in [START_REF] Kamien | The limits of monopolization through acquisition[END_REF] [START_REF] Kamien | The limits of monopolization through acquisition[END_REF] is the two types of competition : in production and also in the remuneration of managers. Delegation increases competition between entities inside the firm. Consequently, the incentives to merge and the profitability of merger, under delegation, are considerably increased in stark contrast to the position where there is no delegation. [START_REF] Ziss | Horizontal mergers and delegation[END_REF] [START_REF] Ziss | Horizontal mergers and delegation[END_REF] argues that a merger will result in the merged entity operating only one firm.

Commitment through delegation may be limited by the possible renegotiation of the delegation contract in the absence of a strong enforcing institutional setting avoiding false disclosure and private renegotiation. Precommitment effects seem to rest on the crucial assumption that contracts, once publicly disclosed, cannot be secretly renegotiated. This is at odds with reality: whether legally enforceable or of a more implicit nature, actual contracts can almost always be renegotiated if both parties agree (Caillaud, Jullien and Picard, 1995 [1]). In the same way, in the decentralized game of [START_REF] Kamien | The limits of monopolization through acquisition[END_REF] [START_REF] Kamien | The limits of monopolization through acquisition[END_REF], internal competition is not rational because if contracts were renegotiable ex-post, firms may act cooperatively. In our model, we consider that firms belonging to the same owner play in a cooperative way.

Our purpose is twofold; first, we analyse the incentives to merge in the context of price competition with horizontal product differentiation. We suppose a two stage game. In the first stage, an owner possessing several firms chooses the number of active firms. The second stage is price competition between active firms.

The number of active firms plays a major rôle : since products are horizontally differentiated, demand increases with the number of active firms. This means that a merger can gain market share, but equilibrium price is lower. Active firms create internal competition but reinforce competition with other firms at the same time.

We show that if the market structure of the industry is duopoly then only merged equilibria can occur. This means that only equilibria in which an owner of several firms chooses to let less active firms than he owns exist. Moreover, if the competitive pressure is high enough then merged equilibria can not occur in this game.

Second, we analyse cartel stability in a static case. As previously we consider a two-stage game. In the first stage, each coalition has to decide the number of its active firms but contrary to the merger game, non active firms are not closed, they receive the same profits as active firms. In the second stage only active firms make price competition.

We show that total cartelization of the industry is an equilibrium of this game, which is in contrast with the results obtained by Kamien and Zang (1990) [START_REF] Kamien | The limits of monopolization through acquisition[END_REF].

A major difference exists between these two games. In the merger game, one owner can possess several firms; whereas in the second game, several firms can belong to a same coalition but each firm in a coalition belongs to one owner.

This article is organized as follows. In section 2 we describe the basic model. Characterizations of equilibria are provided in section 3. Concluding remarks follow in section 4. Proofs of results appear in the appendix.

The model

We consider the following utility function derived from Häckner (2000) [START_REF] Häckner | A note on price and quantity competition in differentiated oligopolies[END_REF]:

U (q, I) = n i=1 q i - 1 2 n i=1 q 2 i + 2γ i =j (q i q j ) + I (1)
The parameter γ ∈ [0,1] is a measure of the substitutability between products. Utility is quadratic in the consumption of the n horizontally differentiated products and linear in the consumption of other goods: I, which price is normalized to one.

The demand function is given by:

q i (p i , p j , n) = 1 1 + γ(n -1) 1 - 1 + γ(n -2) 1 -γ p i + γ 1 -γ j =i p j (2)
We assume that entry into the industry is difficult and that each producer operates at a constant and identical marginal and average cost (c). Without loss of generality, we assume that c = 0. All the relevant variables and strategies available to the firms are common knowledge.

We posit an initial industry consisting of 16 identical and independent firms.

Let us now turn to the formal description of our two games.

MERGER GAME

• Stage 1: Number of active firms.

Let K j be the number of firms owned by a merged entity M j (firms belonging to a same owner have been previously purchased by this owner) and Z, the number of outside firms which are firms not belonging to a merged entity M j . Each owner decides the number of his firms which are active. Let k j (0≤k j ≤K j ) be the number of active firms within M j .

A SPNE (Subgame Perfect Nash Equilibrium) in the merger game is said to be merged if the number of firms operated by all owners is fewer than the initial number of firms .

• Stage 2: Price competition.

Firms belonging to the same owner act cooperatively amongst one another but face competition with each other. The active firms in the merged entities (M j ) and the outside firms compete in price.

COALITION GAME

• Stage 1 : Number of active firms.

Each coalition C j owning K j independent firms decides the number of its active firms, denoted by k j . Contrary to the merger stage, non active firms (they do not compete at the competition stage) are not closed. For example those firms can receive an allowance from the active firms. We assume that firms, active or passive, receive the same individual profit which is the total profit of the coalition shared in a equal way between the members of the coalition. Also, let Z be the number of firms not belonging to a coalition.

• Stage 2 : Price competition.

As in the merger case, active firms in coalition and the outside firms compete in price. Firms belonging to the same coalition act cooperatively amongst one another but face competition with each other.

We then characterize pure strategy SPNE of these two games.

Analysis of equilibria

This section characterizes the set of equilibria depending on the kind of game in question : merger or coalition.

Merger case

We analyse successively the case in which two owners have previously bought some firms : the owners M 1 and M 2 , owning respectively K 1 and K 2 firms, and after the situation where only one owner has previously bought firms.

Two mergers

In this section, we consider the case in which two owners, denoted by M 1 and M 2 own K 1 and K 2 firms (K i ≥ 1, ∀i = 1, 2). Each of them operates k 1 and k 2 units respectively. There are Z outside firms. M 1 , M 2 and the outside firms simultaneously choose the product price for each of their firm whilst seeking to maximize their profit. lemma 1. Equilibrium prices of the two mergers (p * 1 and p * 2 ) and the outsiders (p * ) is given by the following three functions :

     p * 1 = (1-γ)(2+2(Z-1)γ+2γk 1 +γk 2 )(2+(2Z-3)γ+2γ(k 1 +k 2 )) A p * 2 = (1-γ)(2+(2Z-3)γ+2γ(k 1 +k 2 ))(2+2(Z-1)γ+γ(k 1 +2k 2 )) A p * = (1-γ)(2+2(Z-1)γ+2γk 1 +γk 2 )(2+2(Z-1)γ+γ(k 1 +2k 2 )) A with A = 2γ 2 k 2 1 (4 -4γ + 3Zγ + 3γk 2 ) + 2(1 + (Z -1)γ + γk 2 )(2(2 + (Z -3)γ)(1 + (Z -1)γ) + γ(4 -4γ + 3Zγ)k 2 ) + γk 1 (2(8 + 5(Z -2)γ)(1 + (Z -1)γ) + γk 2 (22 - 25γ + 17Zγ + 6γk 2 )).
We check that A > 0.

Proof. See Appendix A.

Equilibrium profit of the merged entity M 1 is given by:

π M 1 = 1 (1 + γ(k 1 + k 2 + Z -1))A 2 (1 -γ)k 1 (1 + (Z -1)γ + γk 2 ) (2 + 2(Z -1)γ + 2γk 1 + γk 2 ) 2 (2 + (2Z -3)γ + 2γ(k 1 + k 2 )) 2 (3)
The expression for merger M 2 is symmetrical. We now determine if an owner of several firms will choose to close some of them or to keep all of them active. proposition 1.

• If Z≥2 then merged equilibria can not occur in this game.

• If Z<2 the game can result in merged equilibria depending on product substitutability. Merged equilibria can occur when there is little product differentiation.

Proof. See Appendix B.

The existence of merged equilibria depends on the number of outsiders. Precisely, the presence of outsiders increases competitive pressure, so that when the number of outsiders is high enough (Z ≥ 2), an owner of several firms will not close some of them to maintain market power. In the remainder of this paper, we assume γ = 0.9 in order to consider all the different cases (merged or unmerged equilibria).

The objective now is to analyse if the number of firms owned by each owner influences the number of their active firms.

The reaction function of the merger M 1 is defined as k * 1 (k 2 ). lemma 2. The reaction function of the merger M 1 is given by :

k * 1 (k 2 , Z) =        K 1 if Z > 1, ∀k 2 f (k 2 ) < K 1 if Z = 1 and k 2 ≥ 8 K 1 if Z = 1 and k 2 < 8 g(k 2 ) if Z = 0
Proof of this is obtained by numerical simulation. Appendix C discloses exact values of functions f and g as well as values of profit functions.

The reaction function of the merger K 2 is a symmetrical function of k * 1 (k 2 ). We observe that k * 1 (k 2 ) is a decreasing function, so k 1 and k 2 are strategic substitutes. lemma 3.

• If there is not competitive pressure (Z = 0), then the owner of several firms will choose to close some of its firms if the other owner keeps all his firms active.

• It competitive pressure is strong enough (Z > 1) then neither of the two owners will close firms.

• If there is only one outside firm, one owner will choose to close some of his firms only if the other owner lets all his firms continue to be active.

proposition 2. If the market structure of the industry is a duopoly then only merged equilibria can occur.

One merger

In this section, we interject a second course in which only the owner M 1 has previously bought some firms and can close some of his firms. The game is solved as previously. We obtain the following proposition : proposition 3. If the market structure of the industry is complete or one of partial monopolization then no merged equilibria can occur.

So whatever the number of outsiders is, only unmerged equilibria occur.

Coalition case

In this section, we analyse the equilibria of the game considering successively the case of two and one coalitions.

Two coalitions

We create two coalitions in this game and we test for stability. The two coalitions and the outsiders choose their price simultaneously in order to maximize their profit. This is exactly the same as in the merger case. It follows that Lemma 1, Proposition 1, Lemma 2 and Lemma 3 are satisified for the coalition game as well.

Now we have to determine equilibria structures for the industry in question. For this we test for internal and external stability for each possible market structure.

Recall that external stability requires that firms inside do not find it desirable to exit and internal stability that firms outside do not find it desirable to enter. proposition 4. Only two coalition structures are stable :

K * 1 = 7, K * 2 = 7, Z = 2 1 {K 1 > 0,K 2 > 0}/K * 1 + K * 2 = 16 Proof. See Appendix D.
The second structure corresponds to the case of maximal concentration in the industry which is in contrast with the results obtained by [START_REF] Kamien | The limits of monopolization through acquisition[END_REF] [START_REF] Kamien | The limits of monopolization through acquisition[END_REF]. In this case (Z = 0), one of the two coalitions will allow all its firms to continue to be active whereas the other will allow fewer firms that he owns to remain active. 2 proposition 5. Maximal concentration in the industry is an equilibrium of this game and corresponds to the case of one coalition which allows all its firms to be active whereas the other not.

One coalition

In this section we analyse the case in which only one coalition is present in the industry. The game is solved as previously. lemma 4. Equilibrium prices of the coalition (p * 1 ) and the outsiders (p * ) are given by :

p * 1 = (1-γ)(2+2(Z-1)γ+2γk 1 )(2+(2Z-3)γ+2γk 1 ) A p * = (1-γ)(2+2(Z-1)γ+2γk 1 )(2+2(Z-1)γ+γk 1 ) A with A = 2γ 2 k 2 1 (4 -4γ + 3Zγ) + 2(1 + (Z -1)γ)(2(2 + (Z -3)γ)(1 + (Z -1)γ)) + γk 1 (2(8 + 5(Z -2)γ)(1 + (Z -1)γ)). 3 1 In this case π out (7, 7, 2) > π C 1 7 (K 1 = 7, K 2 = 7, Z = 2) = π C 2 7 (K 1 = 7, K 2 = 7, Z = 2
) so coalition is not profitable for the insiders.

2 Proof : See lemma 2 3 We check that A > 0.

The coalition will allow all its firms to be active whatever the number of outsiders (proof is obtained by setting k 2 = 0 in lemma 2). proposition 6. There are two equilibria in this game :

K * 1 = 16, Z = 0 K * 1 = 6, Z = 10
So maximum concentration is again an equilibrium of this game (all the firms belong to the coalition).

Concluding remarks

In this paper, we have studied the optimal number of active firms in a coalition and a merger. We have considered two kinds of game : a merger game and a coalition game, both in the context of price competition with horizontal product differentiation. These are two-stage games. The first stage consists of determining the number of active firms. The second stage is price competition between active firms. We assume that firms belonging to the same owner or to the same coalition play cooperatively between themselves but face competition between each other firm.

We show that when there is no competitive pressure (i.e. no outside firm) then only merged equilibria can occur in the merger case. In the coalition case we obtain a similar result in which the number of active firms in the second stage is less than the initial number of firms.

Moreover, we show that when the competitive pressure is high enough (Z ≥ 2) then the initial number of firms in the industry is the same as the number of active firms in the last stage for each kind of game.

Appendix A : Proof of lemma 1

Firms belonging to the same owner play in a cooperative way so the maximization program of the owner M 1 with k 1 active firms is :

max p M 1 1 ,p M 1 2 ,...,p M 1 k 1 (π M 1 ) (4)
where

π M1 = k1 i=1 (p M1 i -c) 1 1 + γ(k 1 + k 2 + Z -1) × (5) (6)
  1 - 1 + γ(k 1 + k 2 + Z -2) 1 -γ p M1 i + γ 1 -γ   i =j p M1 j + j∈M2 p j + j∈out p j    
We stipulate j ∈ out the firms which are outsiders.

We obtain k 1 First Order Conditions (FOC) which are symmetrical, so p

M 1 i = p M 1 , ∀i ∈ M 1 .
After simplifications, we obtain the best response functions:

p M 1 (p -M 1 ) = 1 -γ + γ i / ∈M 1 (p i ) 2 [1 + γ(k 2 + Z -1)] + c 2 (7)
The best-reply function is symmetrical for the merger M 2 .

The maximization program of an outside firm is:

max p i (p i -c) 1 1 + γ 2 i=1 k i + Z -1 * (8) (9)        1 - 1 + γ 2 i=1 k i + Z -2 1 -γ p i + γ 1 -γ     j∈M 1 p j + j∈M 2 p j + j =i j∈out p j           
As before, prices of outsiders are equal, we then replace, p * i by p out for all i / ∈ (M 1 , M 2 ). We obtain :

p out (p -out ) = 1 -γ + γ( j∈M 1 p j + j∈M 2 p j + c[1 + γ( 2 i=1 k i + Z -2)] 2[1 + γ( 2 i=1 k i + Z -2)] -γ(Z -1) (10)
In order to simplify, we replace

(p M 1 (p -M 1 ), p M 2 (p -M 2 ), p out (p -out )) (11)
by

(p 1 , p 2 , p). ( 12
)
The intersection of best response functions yields to :

       p * 1 = (1-γ)+γ(k 2 p 2 +Zp) 2[1+γ(k 2 +Z-1)] p * 2 = (1-γ)+γ(k 1 p 1 +Zp) 2[1+γ(k 1 +Z-1)] p * = (1-γ)+γ(k 1 p 1 +k 2 p 2 ) 2[1+γ(k 1 +k 2 +Z-2)]-γ(Z-1)

Appendix B : Proof of proposition 1

Numerical simulation gives the number of active firms in the merger M 2 in order having k * 1 < K This table can be read in this way :"for Z=3 and γ = 0.9, k 2 must be higher than 20 to π M 1 have an interior maximum (k * 1 < K 1 )". Note that for γ =0.1, k 2 must be very high for merged entity M 1 have a maximum.

Table 2: Reaction functions of the two mergers for Z = 0

K 1 K 2 k 1 k 2 k 1 k 2 1 15 0.
(K 1 ,Z)) K 1 Z=0 Z=1 Z=2 Z=3 Z=4 Z=5 Z=6 Z=7 Z=8 Z=9 Z=10 Z=11 Z=12 Z=13 Z=14 1

  1 .

		γ =0.5 γ =0.9
	Z= k2 ≥	k2 ≥
	0	11	1
	1	17	8
	2	23	14
	3	30	20
	4	36	26
	5	42	33

Table 3 :

 3 Best-response functions (k *

	156969 15

Table 4 :

 4 Profit of the merger M 1 function of the number of outside firms (Z) and the number of firms owned by the merger (K 1 )(where for Z = 0, the first number dictates the profit of the merger M

	1 and k * 2 = K 2 and for the second
	1 when k * 1 < K

Appendix C : Proof of lemma 2 Table 1: Reaction functions of the two mergers for Z = 1 A cartel is stable if it satisfies a property of both internal and external stability.

Internal stability

Internal stability implies that no cooperating firm in a coalition finds it desirable to become independant or to rejoin the other coalition. So internal stability for C i , ∀i = 1, 2, is given by :

External stability

External stability implies that no independent firm finds it desirable to join a cartel. So external stability is given by :