Computing Bilinear Pairing on sensor platforms has become an important research topic since the introduction of pairing-based cryptography to Wireless Sensor Networks (WSNs). Some previous works have provided benchmarks for the pairing computation on sensors. However, a complete pairing- based cryptographic scheme requires much more than just a bilinear pairing operation, and little work has been done yet in this area. In this paper, we present the first fully functional pairing-based cryptographic library for WSNs. The library is fast and lightweight, and has an additional of one identity-based encryption scheme and two short signature schemes included. We also propose several new algorithms and techniques, and show that they significantly improve the speed and reduce the memory usage of the library. The performance results of implementing the three pairing-based cryptographic schemes show that pairing- based cryptosystems are feasible and applicable in WSNs. In particular, the amount of RAM and ROM taken by each of these pairing-based cryptographic schemes is no more than 10% and 20%, respectively, of the total capacities of a MICAz mote.
Index Terms-pairing-based cryptosystems; cryptographic li- brary for motes; secure wireless sensor networks; and security and privacy
I. INTRODUCTION
Bilinear Pairing has received much attention in both re- search and application since its introduction to the construc- tion of the first identity-based encryption scheme by Boneh and Franklin 2001 [1]. Besides enabling the construction of identity-based encryption schemes, bilinear pairing also facilitates the more efficient construction of traditional cryp- tographic schemes. For example, the signature scheme by Boneh, Lynn and Shacham (BLS) [2] reduces the size of DSA signature by 50% while achieving the same security level. The public key broadcast encryption system by Boneh, Gentry and Waters (GBW) [3] achieves constant ciphertext size, while the ciphertext sizes of previous non-pairing-based broadcast encryption schemes are all linear.
In the context of Wireless Sensor Networks (WSNs), pairing-based cryptographic schemes have also been shown to be very useful in solving some major security problems [4]-[7]. Sensor platforms usually have very limited memory capacity and computational power. The memory may not be enough for storing or running complex public key crypto-
graphic algorithms, and the size of data transmitted should also be kept small for extending the battery life.
We believe that presenting an open-source pairing based cryptographic library for the research community is an impor- tant contribution in the view that little work has been done in this area and no fully functional pairing-based cryptographic library is available for WSNs while more and more crypto- graphic schemes and protocols designed for securing WSNs are pairing based.
Due to the limited memory capacity and constrained com- putational power of sensors, pairing-based cryptographic al- gorithms have largely been restricted from running on sensors in the past. Early results [8] show that one pairing operation takes 30 seconds to complete and requires 18,384 bytes of ROM and 1,831 bytes of RAM for storing the program code and running it, respectively, that are over 44.7% and 14% of the total RAM and ROM capacities of a MICAz mote, respectively. The demand of resources is too much in terms of both computation time and memory footprint, given that a cryptographic scheme requires not just a pairing operation, but also several other operations such as elliptic curve point scalar multiplication, multi-precision arithmetic operations, arithmetic operations over extension fields, etc., and this is also the case for many cryptographic schemes and protocols for WSNs [4]-[7].
In recent years, there has been much effort put on making the pairing operation faster to run [9]-[11] and smaller in size [10]. However, as mentioned, a complete pairing-based cryptographic scheme or protocol requires much more than just a bilinear pairing operation. To the best of our knowledge, no study or evaluation of the performance has been reported on implementing a fully functional pairing-based cryptographic scheme on sensor platforms that may involve, in addition to bilinear pairing, many other operations. It remains unknown if all the algorithms that constitute a complete cryptographic scheme can fit into a resource-constrained sensor and also be able to execute on it with a reasonable speed.
In this paper, we propose an efficient and lightweight pairing-based cryptographic library for sensors. The library achieves fast computation and low memory consumption (for both RAM and ROM), by deliberately choosing some super-
singular elliptic curve as the pairing group and some specific finite field of characteristic three as the underlying finite field which defines the elliptic curve pairing group. In the library, we also apply some improved algorithms we recently proposed in [10] for speeding up multiplication, cubing and modular reduction in the underlying finite field, GF (3m ). Besides bilinear pairing, another time consuming operation that is commonly used in pairing-based cryptographic schemes is the elliptic curve point scalar multiplication. By adopting the tech- niques of projective coordinate [12] and radix-3 NAF (Non- Adjacent Form) [13], the computation time of performing one point scalar multiplication on a MICAz can be optimized to 2.5 seconds. Without applying these two techniques, the library takes 7.75 seconds to do the same operation (see Table I).
This pairing-based cryptographic library is the first fully
functional and ready-to-use one, in the sense that it includes all the primitives that are needed for the implementation of major pairing-based cryptographic schemes. Besides bilinear pairing, those primitives include elliptic curve group operation, random number generation, hash function evaluation (includ- ing map-to-point hash), multi-precision arithmetic operations, arithmetic over extension fields, element compression, elliptic curve point coordinate conversion, and so on. Traditional algorithms for implementing most of these primitives are carried out in binary or large prime field; we introduce the variants of these primitives in the field of characteristic three and give the performance comparison in Sec. V. One of the main advantages of implementing all these primitives in the field of characteristic three is that they consume much less memory for achieving the same level of security, and also compare favorably in speed with those implemented in binary and large prime fields.
In our implementation, we also include the implementa-
tion of three well-known pairing-based cryptographic schemes which have been employed in some recent solutions to securing WSNs [4]. These schemes are: BF identity-based encryption [1], BLS short signature [2], and the short signature by Boneh and Boyen [14]. Our implementations of these schemes are lightweight. We show that less than 10% and 20% of the RAM and ROM capacities, respectively, are needed for storing and running these schemes, including the parameters and key materials used by these schemes.
The rest of the paper is organized as follows. Sec. II
describes the design principles of TinyPairing library. In Sec. III, we introduce some related background on bilinear pairing and the underlying field of characteristic three. In Sec. IV, we give the details of the library internals, our newly improved algorithms and some supplementary functions included in the TinyPairing library that are specific to the field of characteristic three. In Sec. V, we evaluate the performance of the library by comparing the speed and memory consumption of the three pairing-based cryptographic schemes that included in the TinyPairing library with some previous non-pairing-based cryptographic schemes implemented on MICAz motes.
II. THE DESIGN PRINCIPLES OF TINYPAIRING
We call this library as TinyPairing. It is designed to be portable so that it can be run over various sensor platforms.
Because of the limited memory capacity and constrained computational power that most sensors have, we target to make the library lightweight. To do so, we choose a particular underlying field that the bilinear pairing operation is to be operated on so that the memory consumption on both RAM and ROM can be minimized (see Sec. III). Also as explained above, we target to provide a fully functional pairing-based cryptographic library to the research community, we therefore require the library to have the aforementioned supplementary algorithms implemented as well. In addition, three commonly- used pairing-based cryptographic schemes are also imple- mented using the library and their source codes are available together with that of TinyPairing [15].
A. Fast and Lightweight
Unlike other computing devices, such as desktop ma- chines or smartphones, sensor platforms are much resource- constrained. MICAz, as an example, which has been used extensively in the research of WSNs, has only 4KB RAM,
128KB ROM, and 7.3828-MHz ATmega128L microcontroller. When speeding up the computation of bilinear pairing and other supplementary algorithms in the TinyPairing library, it is important to keep the program size (i.e. ROM usage) as well as the runtime variable size (i.e. RAM usage) small, so that enough memory will still be available for the actual applications of the library. As we will see in Sec. V, almost all the algorithms of the three cryptographic schemes we implemented using our library can be completed in a few seconds, and the RAM and ROM usages are kept below 10% and 20% of the total capacities of MICAz mote, respectively.
B. Ready-to-Use
Functions supported by the TinyPairing library include ηT pairing [16], elliptic curve group operation, arithmetic over underlying field and extension field, random number generation, hash functions (including map-to-point hash) and multi-precision arithmetic operations. As mentioned, the three pairing-based cryptographic schemes implemented are BLS short signature [2], BB short signature [14] and BF identity- based encryption [1]. We give two implementations for each of the first two schemes. In one implementation we consider multi-precision arithmetic operations in binary; while in the other, we consider the operations in the finite field F3m . In Sec. V, we discuss about their performance.
C. Portable
There are dozens of platforms and numerous sensor boards used in research and industry, for example, the MICA family, Telos mote, eyesIFX mote, Intel's Imote, etc. The entire TinyPairing library was written in NesC for TinyOS v2.x [17] and we did not make use of any platform dependent optimizations or inline assembly code. These make the library easy to port to most of sensor platforms.
III. BACKGROUND
This section reviews bilinear pairing and gives some obser- vations regarding choosing the most suitable underlying field for sensor platforms in terms of reducing memory requirement.
.
A. Mathematics of Pairing
Let E be an elliptic curve defined over a finite field Fq
where q = pm , m is a positive integer and p is said to be the characteristic of Fq . Let O be the point at infinity for E. The order of a point P ∈ E is the least nonzero integer l such that lP = O. The set of points of order l in E
is denoted as E(Fq )[l]. The group E(Fq )[l] is said to have security multiplier or embedding degree k for some k > 0 if
l | qk − 1 and l qs − 1 for any 0 < s < k.
The reduced Tate pairing of order l is the map:
IV. LIBRARY INTERNALS AND OPTIMIZATIONS
In this section, we first describe the internals of the Tiny- Pairing library, and the optimizations we have made in our implementation. This is followed by the introduction of several pairing-related supplementary functions. With the help of these functions, we show that multi-precision arithmetic operations and radix conversion over F3m can be saved from the pairing- based cryptographic schemes we implemented, and therefore less memory is needed for storing the program code.
qk
el : E(Fq )[l] - E(Fqk )[l] → F-
(1)
A. Library Internals
We refer readers to [16], [18] for more details of the pairing definition. There is a revised version of this reduced Tate pairing, call ηT Pairing [16]. It currently is the fastest pairing for supersingular elliptic curves. In our implementation of the ηT pairing, we employ an algorithm due to [18] followed by some improvements we recently obtained in [10] as well as some further optimizations that will be described in the next section of this paper.
Elements in the underlying field F3m are represented as polynomials of degree at most m − 1 with multiplica-
tion and cubing performed modulo an irreducible polyno- mial of degree m. For an element A(x) in F3m , A(x)
i=0
is represented as m−1 ai xi (ai ∈ F3 ). ai is encoded
in two bits, ai = {(ai )hi , (ai )lo }, where (ai )hi , (ai )lo ∈
{0, 1}. In the implementation, we choose 0 = (0, 0), 1 =
(0, 1), 2 = (1, 0). The element A(x) is then encoded as
(Ahi , Alo ), where Ahi = ((am−1 )hi , (am−2 )hi , ..., (a0 )hi ),
B. Basic Field of Characteristic Three
Alo = ((am 1 )
, (a
) , ..., (a )
). We implemented the
There exist efficient algorithms to compute bilinear pairing
− lo
m−2 lo
0 lo
In addition, supersingular curves give a distortion map that maps a point from E(Fq )[l] to E(Fqk )[l]. With this map, the pairing operation can take the second input from E(Fq )[l] and hence reducing the memory for point storage. Some ordinary (non-supersingular) elliptic curves also have efficient algorithms for computing pairing, for example MNT curves [19]. However, they do not have a distortion map, and the size of the second input of the pairing operation is therefore much larger. Supersingular curves can be defined on prime fields Fp , finite fields of characteristic two F2n , or finite fields of characteristic three F3m with embedding degrees of 2, 4, 6, respectively.
The security of pairing-based cryptosystems relies on two number-theoretic assumptions: elliptic curve discrete loga- rithm problem (ECDLP) in the elliptic curve group or its subgroup E(Fq )[l] and discrete logarithm problem in the finite field Fqk . The best known algorithm for solving ECDLP is Pol-
lard's rho method [20] which takes exponential time O(|l|/2),
where the group order l is the largest prime in #E(Fq ). If an elliptic curve is chosen such that #E(Fq )/l is a small
integer, the cost of solving ECDLP is about O(|q|/2). The
k 1/3
most efficient method to solve discrete logarithm problem in the extension field is index-calculus algorithms with subexpo-
library in the underlying field F397 . As data operated on sensor
platforms are multiple of 8 bits, an element in F397 needs 26
bytes to store.
A point P (x, y) on an elliptic curve is represented as two elements x, y ∈ F3m . An element in the extension field F36m
is encoded in six F3m elements.
B. Optimizations
1) Arithmetic in F3m : Polynomial multiplication, cubing and modular reduction in F3m are extensively used in the computation of ηT pairing. In our implementation, we employ the improved algorithms we proposed in [10] for these three operations and obtain the overall performance of the ηT pair- ing by 1.26 times faster than that if the improved algorithms are not applied. These improved algorithms only require an additional of 20 bytes RAM and 1702 bytes ROM. All the algorithms are hardware independent, and to the best of our knowledge this result is fastest one known that no hardware- specific technique is used [11]. For the details of the improved algorithms, we refer readers to [10].
2) Point Scalar Multiplication: Point scalar multiplication is required not only in conventional ECC schemes but also in many pairing-based cryptographic schemes. It is also the
nential running time L[qk ] = e(c+O(1))(log q )
(log log qk )2/3
second most expensive operation, just after the pairing opera-
[21], [22]. We can see that ECDLP in #E(Fq ) is much harder to break than DLP in the extension fields Fqk , which implicitly implies the size of extension fields Fqk should be very large while size of base field Fq could be kept relatively small. Field of characteristic three has embedding degree of 6, which gives rise to a large extension field size while keeping the size of base field smaller. For example, according to [23], extension fields F2239-4 and F397-6 achieve the same security level. Although each element in F3 takes two bits, the memory required for storing an element in F397 is still less than that for storing an element in binary field F2239 .
tion. Benchmarks for computing point scalar multiplication in prime field and binary filed on sensor can be found in [24] and [25]. We provide the first result of point scalar multiplication in the field of characteristic three. As shown in Sec. V, one point scalar multiplication without optimization takes 7.8 seconds on MICAz mote. With optimization, the speed can be improved to 2.5 seconds. The techniques we used are radix-3 NAF [13] and projective coordinate [12].
A point scalar multiplication kP , where k is an integer and P is an elliptic curve group generator, is typically computed using the double-and-add algorithm if the elliptic curve group
is defined over a prime or binary field. In our implementation, the underlying field is ternary. Instead of using double-and-add algorithm, we use triple-and-add algorithm since the cost of tripling a point is negligibly small when compared with that of point doubling. When doing kP , k is first converted to ternary representation, that is, each digit is in radix 3, with the value
in {0, 1, 2}, and the average non-zero density of k is 2/3. By
applying the general NAF technique [26] with width-2 sliding window, the expected non-zero density of k can be reduced to
2/5 and the precomputation of 5 point additions is required for computing kP . By applying the special radix-3 NAF [13], we can achieve the same degree of non-zero density for k but reduce the number of precomputed point additions to 2.
As we can see, point scalar multiplication boils down to
the computation of point addition. For point addition, we use projective coordinate rather than affine coordinate. There is almost no cost to convert from affine coordinate to projective coordinate. Also point addition over projective coordinate does not require the expensive field inversion operation and hence shortens the computation time. Field inversions are only needed for converting the result back to affine coordinate, and the overall speed of point scalar multiplication can then be improved.
A conventional projective (or homogeneous) point is rep-
resented as (X, Y, Z ), which corresponds to (X/Z, Y /Z ) in affine coordinate. Another projective coordinate is Jacobian which is known as a weighted coordinate with the point (X, Y, Z ) corresponding to (X/Z 2 ,Y /Z 3 ) in affine coordi- nate. Homogeneous representation takes 9 multiplications in the base field for a point addition, while Jacobian representa- tion takes 8 [12]. However, Jacobian representation introduces an extra point doubling into the point tripling operation, which is equivalent to adding one more point addition operation. Hence in our implementation, we use the Homogeneous pro- jective coordinate. Together with the radix-3 NAF technique, the speed of doing one point scalar multiplication can be improved to 2.5 seconds (from the original 7.8 seconds).
C. Supplementary Functions in Finite Field F3m
Hash-to-Point: This is a special type of hash functions which hash (or map) a binary string, M ∈ {0, 1}-, to a point
on an elliptic curve. It has been used in many pairing based cryptographic schemes, for example, the short signature in [2]. In the following, we give a variant of this algorithm for elliptic curves over F3m .
1) Set i = 0 and j = 1
6) Otherwise, set i = i +1 and go back to step 2.
Field Element and Point Compression: As mentioned in Sec. IV-A, each digit of an element in F3m is encoded using two bits, and on average 25% of the bits (i.e. '11') are wasted. To shorten the representation, one may consider each element as an integer in radix 3 and convert it to radix 2. In this way, an element in F397 which originally requires 26 bytes to represent in radix-3 can be shortened to 20 bytes in binary. However, radix conversion involves multi-precision operation, which incurs non-negligible computation and additional memory. In our implementation, we do not use this method. Instead, we map every 5 ternary digits to 8 bits. Namely, the range of numbers that can be represented by 5 ternary digits is [0,242], which therefore can be represented using 8 bits. No multi- precision conversion is required and the conversion involves almost no additional cost. For the case of F397 , only 20 bytes are needed in this representation with the most 4 significant bits of the most significant byte unused.
An elliptic curve point consists of two base field elements (x, y) and it is well known that y can be compressed into one bit, which indicates which square root that y corresponds to. In our implementation, we store this bit at the unused most significant bit of x (i.e the most significant bit of the 20th byte of x for the case that the based field is F397 ). As a result, a compressed elliptic curve point only takes 20 bytes to represent.
Revised Point Scalar Multiplication: In Sec. IV-B2 above, we can see that the multiplier k in the point scalar multiplica- tion should be represented in radix 3 so that the triple-and-add algorithm can be applied. To avoid multi-precision operations in radix conversion, we store k in radix 3 at the first place using the field element representation described above. In this way, some pairing-based cryptographic schemes can benefit from this radix-3 representation in both speed and program size (See Sec. V for details).
Random Ternary Digits Generation: Due to the spe- cial field element presentation and the 'revised' point scalar multiplication described above, cryptographic schemes will benefit greatly in performance if there exists a random ternary digit generator than merely having the existing random bit generator. To do so, we retrieve random ternary digits from the source of random bits and convert every two bits to one ternary digit in the same way as we do the conversion in the hash-to- point algorithm described above. The random source bits are obtained from TinyOS's native pseudo random functions.
2) digest ← H (i M ) where H : {0, 1}- → {0, 1}
is a
conventional cryptographic hash function. For example, if H is SHA-512 based, then = 512.
3) Encode every two bits of digest to the j-th digit of element x ∈ F3m (i.e. 00 → 0, 01 → 1, 10 → 2, and
discard 11). Then set j = j + 1.
4) If digest is not long enough for generating all the m
digits of x, go back to step 2.
5) compute f (x) where f is the elliptic curve equation. If
f (x) has two roots y0 , y1 , set
(x, y0 ) as the output point and return if i is even,
(x, y1 ) as the output point and return if i is odd.
V. EVAL UAT I ON
We measured the performance of TinyPairing library on a MICAz mote. In each test, we picked at least 10 random inputs and measured the average running time. The RAM and ROM usage by each pairing-based schemes were obtained using the TinyOS toolchain [17]. In the following, we first provide the benchmark for ηT pairing and its related functions. We then compare the pairing-based signature and encryption schemes with ECC-based counterparts which are available in an ECC cryptographic library called TinyECC [24].
TABLE I
RUNNING TIME OF PAIRING -RELATED FUNCTIONS ON MICAZ
Time (sec)
Hash-to-Point (16 bytes msg)
0.89
Point compression
Point decompression
0.38
0.38
Point scalar mult (original)
Point scalar mult (optimized) Point scalar mult (revised)
7.75
2.50
2.45
ηT pairing
5.32
A. Benchmarks for Pairing and Its Supplementary Functions
Table I shows the speed of the following functions: hash- to-point, point compression/decompression, point scalar mul- tiplication and ηT pairing. These functions are implemented in the field of characteristic three and no previous results have been reported on these functions in this field. Hash- to-point function is evaluated by taking 16 bytes of message as the input. One point scalar multiplication originally takes
7.75 seconds to compute if no optimization is applied. After applying the optimizations described in Sec. IV-B2 (i.e. radix-
3 NAF and projective coordinate), the time is significantly reduced to 2.5 seconds (i.e. 64% less). After further applying the 'revised' field element representation method described in Sec. IV-C, the time is reduced to 2.45 seconds. For ηT pairing, the speed obtained is the same as that in our recent work [10] and is currently the most efficient one for bilinear group over F397 .
B. Benchmarks for Pairing-Based Cryptographic Schemes
The most related cryptographic library for sensor networks is TinyECC [24]. TinyECC is a highly configurable library which allows users to use more memory for getting better speed. It supports some standard elliptic curve cryptographic algorithms such as ECDSA (digital signature) and ECIES (encryption). It does not support bilinear pairing. In our performance tests, we configure TinyECC into two versions, one with all the optimizations (i.e. opt) turned on; and the other one with all of them switched off (i.e. non-opt). An initial pre-computation step is needed in TinyECC. The TinyPairing library does not need such an initialization step. In Tables II and III, the results of TinyECC are obtained in the 160-bit prime field and the results of TinyPairing are obtained in the underlying field F397 .
Pairing-based short signature schemes in TinyPairing and
ECC-based one in TinyECC are compared in Table II. The
BLS SS (short signature) [2] over the base field F397 is only
160 bits long which is half the size of an ECDSA signature
in the 160-bit prime field and BB SS [14] is 312 bits, that is, 160 bits for a compressed point and the other 152 bits for a random integer. In the revised version of BLS SS (i.e. applying the 'revised' field element representation described in Sec. IV-C), random integers are represented in radix 3, and hence no conversion from radix 2 to 3 is needed (i.e. no multi- precision operation). Besides speed, this also saves 790 bytes of program size (i.e. the ROM usage). From Table II, we can also see that the running time of signing a message in BLS SS is less than that of ECDSA even when the ECDSA is running
in the optimized mode (note: the initialization time is also taken into account). The verification time is long due to the involvement of two pairing operations. On the running time memory consumption, both BLS SS and BB SS use less than
400 bytes of RAM, whcih is only about 25% of the RAM
used by the optimized ECDSA.
Table III shows the performance comparison between the pairing-based BF IBE (identity-based encryption scheme [1]) and the ECIES (TinyECC). The public key size in ECIES is
160 bits in the 160-bit prime field. In the IBE, an identity ID is the public key and can be of any length provided that it can uniquely identify the user, for example, the ID can be the MAC address of a sensor node. The encryption and decryption takes about 10 and 5 seconds, respectively, in IBE, and are longer than that required for conventional ECC-based ECIES as it only involves several point scalar multiplications. However, the running memory (RAM) used by ECIES is much higher than that of BF IBE, which uses only 392 bytes.
VI. CONCLUSION
Pairing-based cryptography has become an important re- search topic for WSNs, while there is no benchmark or concrete implementation result reported about implementing some concrete pairing-based encryption and signature schemes on a sensor node. In this paper, we presented a pairing- based cryptographic library called TinyPairing for sensors. The library not only contains implementation of the BF IBE [1], BLS SS [2] and BB SS [14], it also provides the pairing primitive and some supplementary functions which are useful for implementing other pairing-based cryptographic schemes (for example, broadcast encryption [3]). We also proposed an efficient point compression method and a field element representation technique which help reduce the storage size and shorten the time for radix conversion. According to our experimental results (Section V), the library takes less than
10% and 20% of the total capacities of RAM and ROM, respectively, of a MICAz mote. This leaves plenty of space for running other WSN applications such as secure routing, key establishment and distribution, etc.
