{'fraction_non_alphanumeric': 0.03260594826859887, 'fraction_numerical': 0.01272221754149465, 'mean_word_length': 4.541549953314659, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A preliminary study of bit-integer hash function for bilinear pairing identity-based cryptosystem

Hash function is a crucial part of identity-based cryptosystem, especially for identity-based cryptosystem that utilize bilinear pairing as its core mechanism. However, the hash function has specific requirement that most of commonly known function are not suitable for this purpose, especially the requirement that requires the output length of function is varies. A variable length hash function, such as HAVAL, only provide multiple option for its output length. While the identity-based cryptosystem require that the length of the output can be any number. This study aims to create a hash function to fulfil the identity-based cryptosystem requirement. This study modifies the MD5 hashing algorithm to produce a variable length output, which called the Bit-Integer hash function. The result shows a proof-of-concept that Merkle-Damgård construction can be used to create a variable length hash function. The hash value of Bit-Integer hash function can produce random-like result which is essential for any cryptographic hash function.


Introduction
Identity-based cryptosystem is an asymmetric cryptosystem that uses user identity as its public key [1]. The cryptosystem offers an encryption and signature scheme that does not require any third party to story user's public key, thus reducing the complexity of an encryption scheme. The most common method to implement identity-based cryptosystem is by using bilinear pairing as its main mechanism [2].
This bilinear pairing-based identity-based cryptosystem requires 3 (three) types of hash function as part of its algorithm. Hash function is a one-way function, it is easy to compute the result for a certain input but extremely difficult to obtain that certain input given the result and the function. The first hash function takes a variable length bit string and map it to a member of a predetermined group, 1 : {0,1} * → . The second function convert an arbitrary bit string into an integer with certain order, 2 : {0,1} * → ℤ . The third hash function takes an input of arbitrary integer and maps it into a bit string with variable length, 3 : ℤ → {0,1} .
The requirement of each hash function is so specific that most of known cryptographic hash function is not suitable for this purpose. The hash functions require a change of data types, for example from integer to bit string and vice versa. The commonly known hash function, for example Rivest, Carreira and Shen, can fulfill this requirement [3][4][5]. The MD5 can convert any message (usually in string) into a binary hash value (usually represented as hexadecimal). However, the problem lies within the variable length requirement. The common hash function produces a fixed length output. For example, MD5 always produce a 128-bit long hash value. This condition is not suitable for the implementation of identity-based cryptosystem, especially for 3 . There are several hash functions that can produce a variable length hash value, such as Zheng et al. and Wang et al. However, the functions in Zheng and Wang are more suitable to be called as having multiple output rather than variable output [6,7]. HAVAL provides an output length option that can be chosen at the start of algorithm: 128, 160, 192, 224, or 256 bits [6]. The 3 used in Malone-Lee needs to produce a hash value with length that matched the original message before encryption [8]. Since the length of message is arbitrary, HAVAL is not suitable to be implemented for this case.
This study is a preliminary study that aims to create a hash function that suitable for identity-based cryptosystem. Particularly, this study only focuses on creating 3 function. The basic hypothesis is that such a function can be constructed by using Merkle-Damgård construction [9,10]. To achieve the proofof-concept of this hypothesis, this study will modify MD5 function so that it can produce a variable length output.

Basic construction of bit-integer hash function
As one-way function, a hash function should have a certain characteristic. Given a certain input, there should be no entity that can predict the output. However, if the same input is used again in the hash function, then the output should still the same. An arithmetic circuit constructed using Merkle-Damgård construction method should have the characteristic [9].
A function in Merkle-Damgård construction is an iterative circuit. A plaintext (to be hashed) is usually divided into blocks with fixed length (figure 1). Using a constant initiation vector, each block is processed as part of each iteration. The hash value is produced at the end of iteration. The hash value usually has a fixed length (e.g. 128 bit). The result should act like a randomly generated, in sense that no one can predict the precise result from a particular input. The function 3 in identity-based cryptosystem takes an input in form of an integer and produce an output in form of binary integer with a predetermined length. The length of the output is determined by the user before the calculation began. To formalize these requirements, the function 3 can be defined as follow: Definition 1. Let 3 = ( , ) be a one-way function that takes input of ∈ ℤ and a length of > 0, ∈ ℤ. Function 3 is suitable for identity-based cryptosystem if for any , 3 produce a randomlike binary string with length , 3 = {0,1} . There are several popular Merkle-Damgård hash algorithm, including MD5 [3] and SHA-1. The MD5 and SHA-1 function is acting as random oracle [10], thus producing a random result. Both functions also operate on binary level, so it always produces a binary string as a result. However, both functions have fixed length (MD5 has 128-bit length and SHA-1 has 160-bit length), so both functions cannot satisfy Definition 1.
The proposed Bit-Integer hash function is based on MD5 algorithm. As preliminary study, this choice is sufficient, as this work aims to explore the possibility on how Definition 1 can be fulfilled. To overcome the fixed-length problem of MD5, similar approach from Zheng and Wang is used [6,7]. In Zheng and Wang, the iterative function produces a fixed-length result. The result is then post processed according to the chosen length option. By using AND operation on each bit element, a desired length of hash value is produced [6,7].
The complete steps of Bit-Integer hash function can be seen in figure 2. An input in form of integer is divided into blocks, using padding rule of MD5. To divide the integer, each number is treated as a string and parsed as a byte (an 8-bit string) and padded with padding bits so the total length is equal to modulo 512. The bits then divided into block with length 512-bits each. The MD5 algorithm will create a 128-bit long hash value. The value is then post-processed, so the length of the bit is equal to the desired length. The complete algorithm of Bit-Integer hash function can be found in Algorithm 1.  In algorithm 1, the symbol "[index]" is used to represent the number of array element. While symbol "≪ " means that the bit is left shifted by . From the algorithm, the length of result is gained by adding each byte in ℎ′. By doing so, the desired length can be controlled freely. The length in Boneh and Malone-Lee represent the length of original plaintext that will be encrypted using identity-based encryption algorithm [2,8]. Since the plaintext can be divided into each character and each character can be represented as a single byte (value of its bits representation), it can be concluded that is always a multiplication of 8. That is why, in algorithm 1 the length is controlled in bytes.

Verification of proposed hash function
The aim of this study is to achieve a proof-of-concept that Merkle-Damgård construction can be used to construct a suitable hash function for bilinear pairing identity-based cryptosystem, especially for a Bit-Integer type hash function. To prove that the constructed Bit-Integer hash function satisfies definition 1, the function is verified using several tests.
The first test is to see that the function can produce a random-like output for a certain input. Table  1 show the result of this test. There are 7 inputs for this test, each input slightly differs than the default value, with "1234567" as the default value. The result in table 1 shows that each input produces a different output. Hamming distance is used to show that the bits result has significant difference, thus illustrating that the output cannot be predicted even for two similar value [11]. The Hamming distance measure the difference of value per position between two string with equal length, which formulated as follow: where denotes the position of bit in the string, and 1 , 2 denotes the compared bit-strings. The result of the first test show that each output greatly differs, with average Hamming distance of 19. This prove that the proposed Bit-Integer hash function can produce a random-like output. The closest distance is produced by input "1234567" and "1234467". Even on those input, the hash function still produces results with Hamming distance of 13. That means there are 13 bits difference from the entire 64 bits result. The result in table 1 also show that there is no certain pattern that can be seen from the output, thus create a random-like result.
The second test aims to see that the bit-integer hash function can produce an output with variable length and retain the random-like result. To prove this capability, a single input is feed to the function repeatedly, each with a different output length. The result of this test can be seen in table 2. From the result, the Bit-Integer hash function can produce variable output length. The output length can be freely determined compared to the length options from function in Zheng and Wang [6,7]. However, as can be seen from the result, aside the first 8-bits all the bits are similar. This condition is generated from the post-processing phase in the Bit-Integer hash algorithm. From the algorithm, it can be seen that only the first byte has different input value that depends on the output length, while the rest of bytes is the same regardless the output length. However, this result is satisfying enough for the purpose of this preliminary study. Since, it shows the needed proof-of-concept that existing Merkle-Damgård construction can be used to construct a suitable hash function for identity-based cryptosystem.

Conclusion
The proposed Bit-Integer hash function to a certain extend can fulfil definition 1. Thus, making it suitable to be used in the implementation of identity-based cryptosystem, such as Boneh and Malone-Lee [2,8]. This study shows that any Merkle-Damgård based hash function can be modified to produce an output with variable length. The output length can be freely controlled, not like Zheng and Wang that provide an option of output length [6,7]. The hash value produced by Bit-Integer hash function also have the random-like characteristic, making it a proper cryptographic hash value. However, the proposed function still has its limitation. For a certain input, the function still produces the same hash value despite the desired output length. This condition could enable a person to guest the hash value of an input of any length if the person has a value of a single length. To tackle this problem, the Merkle-Damgård construction can be used again. In this study, and similar study to produce variable output length, the output length is controlled in post processing phase. There is an opportunity to create an entirely new Merkle-Damgård-based hash function, where the number of iteration correspondence to the desired length of output. This approach, in theory, could produce a random-like result in various output, even for a single same output.