Johann Grossschädl
email: johann.groszschaedl@uni.lu

Dan Page
email: page@cs.bris.ac.uk

Stefan Tillich
email: tillich@cs.bris.ac.uk

Johann Großschädl

Efficient Java Implementation of Elliptic Curve Cryptography for J2ME-Enabled Mobile Devices

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

Introduction

The Java programming language, introduced by Sun Microsystems in 1995, was originally designed to simplify the software engineering for consumer electronics [START_REF] Gosling | The Java TM Language Environment[END_REF][START_REF] Arnold | The Java TM Programming Language[END_REF]. Many characteristics of the Java language stem from the focus towards the consumer marketplace with its vast number of different hardware platforms and (largely incompatible) operating systems. Unlike C or C++, Java is generic and platform-independent because it is an interpreted rather than a compiled language. That is, when Java source code is compiled, it is not compiled into architecture-dependent "machine" instructions, but into an architecture-neutral intermediate representation consisting of generic instructions (called bytecode) to be executed by a Java Virtual Machine (JVM) [START_REF] Craig | Virtual Machines[END_REF]. The JVM can be seen as a program running on the host processor that interprets generic Java bytecodes and translates them to the processor's native machine instructions as they are executed. A program written in Java and compiled to generic bytecode will, in principle, run unchanged on any platform for which a JVM exists, regardless of what operating system or processor lies underneath. This "Write Once, Run Everywhere" capability has made Java the de-facto standard language for the development of cross-platform applications in the embedded domain.

The Java 2 platform is available in three different editions, each aimed at a specific area of application: J2EE (Java 2 Enterprise Edition) for developing and deploying large-scale server applications, J2SE (Java 2 Standard Edition) for the implementation of Java programs that can be executed on commodity computers, as well as J2ME (Java 2 Micro Edition) for creating Java applications to be run on various kinds of mobile and embedded devices 3 . These platform editions differ in terms of size (and complexity) of the class library and the capabilities of the corresponding JVM. J2ME is, roughly speaking, a stripped-down version of J2SE that contains only a small subset of the standard Java class library, in addition to J2ME-specific classes [START_REF] White | Java 2 Micro Edition[END_REF]. Java applications for mobile phones are called midlets and can be run on devices on which at least 192 kB of memory is available to the J2ME platform. Since the "conventional" interpretation of Java bytecode on such resource-restricted devices is rather slow, different techniques for speeding up the execution of midlets have emerged. For example, some JVMs feature a Just-In-Time (JIT) compiler that translates frequently-executed code segments ("hot spots") into native machine code at run-time (i.e. during execution of the midlet) [START_REF] Cramer | Compiling Java just in time[END_REF]. Another approach is the provision of dedicated hardware support for the JVM through architectural extensions that allow the underlying processor to directly execute Java bytecode (e.g. ARM's Jazelle [START_REF] Limited | Jazelle TM -ARM R Architecture Extensions for Java Applications[END_REF]).

Since J2ME is, roughly speaking, a stripped-down version of J2SE for mobile devices with restricted resources, it lacks many of the classes found in the class library of the larger editions. While the Java Cryptography Architecture (JCA) and Java Cryptography Extension (JCE) are included in J2SE/J2EE, they are absent in J2ME for both technical and legal reasons [START_REF] White | Java 2 Micro Edition[END_REF]. Therefore, developers of J2ME applications are forced to use third-party classes or to implement the required cryptographic operations from scratch. The latter is a tedious task, especially for Elliptic Curve (EC) cryptography, since the J2ME class library does not even contain the J2SE BigInteger class for multi-precision arithmetic. On the other hand, most existing EC implementations for J2ME (e.g. the Bouncy Castle Lightweight API [START_REF]The Legion of the Bouncy Castle: Lightweight Cryptography API (Release 1.47[END_REF] or the SIC JCE-ME [START_REF]and Communication Technologies (SIC)[END_REF]) do not perform very well since they aim to provide high flexibility (i.e. support of many implementation options) rather than high speed. There exist only a few performance-optimized Java implementations of EC cryptography, which is surprising given that more than three billion J2ME-enabled mobile phones have shipped to date 4 . Also the scientific literature on optimizing EC cryptosystems for the J2ME platform is sparse compared to the vast number of papers presenting EC implementations written in C and/or Assembly language.

In the following sections, we describe our efforts to develop a performanceoptimized Java implementation of EC scalar multiplication for J2ME-enabled devices. The focus of our work was to achieve fast execution time, low memory (i.e. RAM) requirements, and small bytecode size. After a thorough evaluation of different implementation options, we decided to use a pseudo-Mersenne (PM) prime field [START_REF] Crandall | Method and apparatus for public key exchange in a cryptographic system[END_REF] over which a Gallant-Lambert-Vanstone (GLV) curve with good cryptographic properties can be defined [START_REF] Gallant | Faster point multiplication on elliptic curves with efficient endomorphism[END_REF][START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]. This particular choice of type of field and type of curve allows for combining fast modular arithmetic (due to the special form of the prime) with fast EC point arithmetic (thanks to an efficiently computable endomorphism). To exemplify our approach, we present an optimized Java implementation of EC scalar multiplication on the GLV curve y 2 = x 3 -7 over the PM prime field F p with p = 2 174 -3. The group of points on this curve has prime cardinality and offers a security level of 87 bits5 . When using mixed Jacobian-affine coordinates, a point addition on this curve requires eight multiplications (8M) and three squarings (3S) in the underlying field (see [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF] for the exact formula). The double of a point given in Jacobian coordinates can be computed using only 3M and 4S since the curve parameter a is 0. A full scalar multiplication of an arbitrary point P by an n-bit integer k represented in Non-Adjacent Form (NAF) [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF] takes 5. 6n multiplications and 5n squarings on average, i.e. 5. 6M + 5S per bit. However, the cost of a scalar multiplication on our GLV curve can be significantly reduced by exploiting the efficiently-computable endomorphism described in [START_REF] Gallant | Faster point multiplication on elliptic curves with efficient endomorphism[END_REF]Ex. 4]. This endomorphism allows one to accomplish an n-bit scalar multiplication k • P through a computation of the form k 1 • P + k 2 • Q, whereby k 1 , k 2 have only half the bit-length of k. The two half-length scalar multiplications can be performed simultaneously and require n/2 point doublings and roughly n/4 additions when k 1 , k 2 are represented in Joint Sparse Form (JSF) [START_REF] Solinas | Low-weight binary representations for pairs of integers[END_REF]. Thus, the total cost of computing k • P amounts to 3.5n multiplications and 2.75n squarings in F p , i.e. 3.5M + 2.75S per bit.

Since our implementation aims at high performance, we did not attempt to make the scalar multiplication on our GLV curve resistant against side-channel attacks such as Simple Power Analysis (SPA) [START_REF] Möller | Securing elliptic curve point multiplication against side-channel attacks[END_REF]. However, all arithmetic operations (except inversion) in the underlying 174-bit prime field are written in a highly regular fashion without any conditional statements, i.e. branches. Such a branch-less implementation of the field arithmetic helps the VM to identify the performance-critical code sections for JiT-compilation and also eliminates the performance penalty due to branch mis-predictions. Note that, even though the field-arithmetic is SPA-resistant, our implementation of scalar multiplication is vulnerable to SPA attacks. We will address this issue in future work dedicated to SPA countermeasures for scalar multiplication on GLV curves.

Prime-Field Arithmetic in Java

Our optimized Java software for EC scalar multiplication uses the prime field F p of order p = 2 174 -3 as underlying algebraic structure. In the following, we explain the rationale behind choosing this particular field and elaborate on the efficient implementation of multiple-precision arithmetic in Java. Most previous software implementations of EC cryptography were written in C (or C++) and contain hand-optimized Assembly code for the performance-critical arithmetic operations. However, even though C/C++ and Java have a similar syntax, there exist also some differences which impact the implementation and optimization of multiple-precision arithmetic.

Selection of Prime Field

A major aspect when implementing EC cryptography is to find an appropriate trade-off between performance and security; this is particularly important for a Java implementation to be run on J2ME-enabled mobile phones or PDAs since (1) such devices are constrained in processing power and (2) the interpretation of platform-independent byte code is much slower than the execution of native machine code. The ECRYPT II report on algorithms and keysizes considers 80 bits as the smallest level of security that "protects against the most reasonable and threatening attack (key search) scenarios" [22, p. 32]. An 80-bit symmetric key can, under certain assumptions, be seen "equivalent" to an EC key of size 160 bits [START_REF]ECRYPT II Yearly Report on Algorithms and Keysizes[END_REF]Table 7.2]. In order to support 160-bit keys, an EC cryptosystem must be designed on basis of an EC group of order roughly 2 160 , which, due to the Hasse-Weil theorem [5, page 278], requires an underlying field of (at least) 160 bits. However, GLV curves have a special structure that could reduce the time required to compute EC discrete logarithms by "a small factor" [12, Section 5], similar to Koblitz curves [START_REF] Wiener | Faster attacks on elliptic curve cryptosystems[END_REF]. To account for this structure, we have to slightly increase the order of the EC group and, consequently, the order of the underlying prime field, e.g. to around 170 bits.

A second criterion to consider when choosing a prime field F p for EC cryptography is the efficiency of arithmetic operations in this field, in particular the efficiency of the reduction modulo p. Mersenne primes are special primes of the form p = 2 k -1 and allow for particularly fast implementation of the reduction operation. A 2k-bit number x can be reduced modulo p = 2 k -1 by adding the higher half of x (i.e. the k most significant bits of x) to the lower half, followed by conditional subtraction(s) of p to obtain the least non-negative residue. Consequently, the reduction costs merely an addition of two k-bit numbers modulo p. Unfortunately, primes of the form 2 k -1 are very rare; none of the Mersenne numbers between 2 127 -1 and 2 521 -1 is prime [START_REF] Cohen | Handbook of Elliptic and Hyperelliptic Curve Cryptography[END_REF]. The second-best option in terms of efficiency of the modular reduction are pseudo-Mersenne (PM) primes [START_REF] Crandall | Method and apparatus for public key exchange in a cryptographic system[END_REF], i.e. primes that can be written as p = 2 k -c where c is "small" compared to 2 k . In the ideal case c = 3, which allows a reduction operation to be carried out through three k-bit additions modulo p. A prime of the form 2 k -3 with a length of roughly 170 bits exists, namely p = 2 174 -3.

A third requirement on the prime p is the suitability to define a GLV curve with "good" cryptographic properties over the field F p . GLV curves of the form y 2 = x 3 + ax require the underlying prime field F p to contain an element of order 4 (which is the case if p ≡ 1 mod 4), whereas GLV curves defined via the equation y 2 = x 3 + b need a field F p with p ≡ 1 mod 3 [START_REF] Gallant | Faster point multiplication on elliptic curves with efficient endomorphism[END_REF]. Furthermore, the curve itself (or, more precisely, the group of points on the curve) has to satisfy certain properties, e.g. it has to contain a large subgroup of prime order. The GLV curve y 2 = x 3 -7 over the 174-bit prime field specified above fulfills this property and also meets a number of other security criteria as we will show in more detail in Subsection 3.1. Taking all these considerations into account, we decided to use the prime field F p with p = 2 174 -3 for our Java implementation of EC scalar multiplication.

Representation of Field Elements. State-of-the-art cryptographic libraries represent the elements of a large prime field (i.e. long integers) as arrays of single-precision words, e.g. arrays of type unsigned int. Most high-performance implementations written in C or Assembly language match the number of bits per single-precision word to the word-size of the target processor so as to take advantage of the full length of the datapath. Also the J2SE BigInteger class follows a similar idea; it uses an int-array as internal data structure and stores 32 bits in each element of the array. However, this approach yields sub-optimal results when the size (i.e. bitlength) of the prime field is constant and known in advance. These inefficiencies, which will be discussed in more detail below, are due to the fact that Java is a platform-independent programming language and that it does not support unsigned data types.

We conducted experiments with different representations of the F p -elements and found that splitting the 174-bit integers into six 29-bit words allows one to achieve the best performance. Our implementation does not store these words in an array but in six independent variables of type int, which are declared as private within the Java class that performs the F p -arithmetic so that they are not visible (and accessible) from "outside" [START_REF] Arnold | The Java TM Programming Language[END_REF]. Avoiding the use of an array is possible and viable in our case since the length of the operands is fixed and we implemented all arithmetic operations (except inversion) in an unrolled fashion without executing any conditional statements to achieve a maximum of performance and resistance against side-channel attacks. Formally, our implementation of F p -arithmetic uses a number representation radix of 2 29 , which means that any integer a ∈ F p can be written as

a = 5 i=0 a i • 2 29i with 0 ≤ a i ≤ 2 29 -1. (1)
However, similar to the work of Bernstein [START_REF] Bernstein | Curve25519: New Diffie-Hellman speed records[END_REF], we allow (i.e. tolerate) individual words a i slightly larger than the radix of 2 29 for reasons of both efficiency and security. Furthermore, our implementation allows incompletely reduced results in the sense that an arithmetic operation does not necessarily return the least non-negative residue modulo p, but the result is always in the range [0, 2p].

Efficient Arithmetic Modulo

p = 2 174 -3
In the following, we describe our Java implementation of fast arithmetic in the prime field F p , i.e. addition and multiplication modulo p = 2 174 -3. We will in particular explain the efficiency of our 29-bit-per-word representation of field elements versus a straightforward representation using 32-bit words.

Addition and Subtraction. Most high-speed cryptographic libraries written in C (or C++) use small Assembly-code fragments to implement performancecritical operations such as multiple-precision addition and multiplication. The former operation can be realized in a (relatively) simple yet efficient way if the underlying processor provides an add-with-carry instruction. Even though also Java features a mechanism to include Assembly code, namely the Java Native Interface (JNI), we did not follow this approach because it contradicts the idea of platform-independence. Furthermore, one has to take into account that some processors (e.g. MIPS, Alpha) do not possess an add-with-carry instruction. To perform multi-precision addition on these processors, the add-with-carry has to be emulated, e.g. by first executing the ordinary add instruction, followed by a comparison of the result with one of the two operands. If the obtained sum is smaller than either of the operands, then an overflow occurred, i.e. the addition produced a carry, which must be processed properly when adding the two nexthigher words. Consequently, from the second word-pair onwards, the addition becomes more complex and time-consuming since an "incoming" carry must be considered.

High-level language implementations of multi-precision addition can follow a very similar approach as described above if the long integers are represented in such a way that the number of bits per single-precision word corresponds to the word-size of the underlying processor (e.g. 32 bits per word on a 32-bit processor). However, the performance of multi-precision addition in C/C++ or Java (or in Assembly language on processors without add-with-carry instruction) can be greatly improved by reducing the number of bits per word, e.g. to 31 when working on a 32-bit machine. In this case, the sum of two single-precision words is at most 32 bits long and, hence, fits into a 32-bit word, i.e. an overflow can not occur. The carry bit is stored in the MSB of the result-word and accessible through a right-shift by 31 bit positions. This approach was originally proposed roughly 30 years ago by Hennessy et al [START_REF] Hennessy | Hardware/software tradeoffs for increased performance[END_REF]Section 2.3.3] to demonstrate the ability of the MIPS architecture (and other architectures lacking a carry flag) to efficiently perform multi-precision addition.

Algorithm 1 shows our Java implementation of addition in F p ; we follow, in principle, the approach of Hennessy et al [START_REF] Hennessy | Hardware/software tradeoffs for increased performance[END_REF] described above, except that we represent the long integers using 29-bit words. The variable s, which is of type int in our implementation, holds the sum of two 29-bit operand-words plus the carry bit. Even though the sum can have a length of up to 30 bits, only the 29 LSBs of s are actually assigned to the result-word z i . The three MSBs of s are masked out via a logical AND operation using a mask value of 0x1fffffff (see line 4 of Algorithm 1). Before adding the next pair of operand-words, the sum Algorithm 1. Addition in Fp Input: Two 174-bit integers, A = (a5, a4, a3, a2, a1, a0) and B = (b5, b4, b3, b2, b1, b0), represented by six 29-bit words. Output: Modular sum Z = A + B mod (2 174 -3) = (z5, z4, z3, z2, z1, z0).

1: s ← 0 2: for i from 0 by 1 to 5 do 3:

s ← ai + bi + (s 29) 4: zi ← s & 0x1fffffff 5: end for 6: z0 ← z0 + 3 • (s 29) 7: return Z = (z5, z4, z3, z2, z1, z0)
s is shifted 29 bit positions to the right to ensure the correct alignment between a i , b i , and the carry bit. In fact, the shift operation yields the carry bit from the previous addition of operand words, i.e. the value of the expression (s 29) in line 3 of Algorithm 1 is either 0 or 1. Note, however, that our implementation does not strictly adhere to the pseudo-code shown in Algorithm 1; we unrolled the loop to maximize performance.

The sum of two 174-bit integers can be up to 175 bits long, which means a reduction modulo p = 2 174 -3 may be necessary to obtain a final result within the range of [0, p -1]. Reducing the sum with respect to the prime p calls for a comparison between the sum and p, followed by a subtraction of p if the sum is greater than or equal to p. The former operation, when realized in a straightforward way, requires comparing up to six single-precision words. However, an exact comparison of the sum with the prime p can, in general, be avoided since modular arithmetic also works with incompletely reduced operands and, consequently, there is no need to fully reduce a result. Our implementation compares the sum with 2 174 instead of the "exact" prime p = 2 174 -3, i.e. the result of a modular addition is not necessarily the least non-negative residue. The obvious advantage of performing the comparison in this way is efficiency; we just have to check whether the 174-bit addition produced a "carry-out," as described in [30, Section 3]. More precisely, after the final iteration of the loop in Algorithm 1, we simply right-shift the variable s by 29 bits to obtain the "carry out." The subtraction of the prime p is realized in our implementation by addition of the 174-bit two's complement of p to the sum, i.e. by addition of 2 174 -p = 3 to the least significant word z 0 . Line 6 of Algorithm 1 performs the modular reduction operation, consisting of the extraction of the "carry out", its multiplication by 3, and the addition of the product to z 0 . Note that, due to this addition, the least significant word z 0 can be up to 30 bits long. However, the extended size of z 0 does not require special consideration since all our arithmetic operations also work correctly with 30-bit words.

We implemented the subtraction of two elements a, b ∈ F p through the operation 2p + a -b, which, in turn, is carried out via word-level operations of the form 2p i + a i -b i , followed by a reduction of the result modulo p as described before. Performing the subtraction in this way (instead of a direct computation Listing 1. Nested loop of multi-precision multiplication as implemented in the function multiplyToLen of the BigInteger class (version 1.76)

1 for (int i = xstart-1; i >= 0; i--) { 2 carry = 0; 3 for (int j=ystart, k=ystart+1+i; j>=0; j--, k--) { 4 long product = (y[j] & LONG_MASK) * 5 (x[i] & LONG_MASK) + 6 (z[k] & LONG_MASK) + carry; 7 z[k] = (int)product; 8 carry = product >>> 32; 9 } 10 z[i] = (int)carry; 11 }
of the difference a -b) ensures that the results of all word-level operations, as well as the final 174-bit result, are positive and can be calculated in a straightforward way without the need of any conditional statements. Such branch-less execution of arithmetic operations can help to prevent implementation attacks since always the same sequence of instructions is executed, independent of the actual value of the operands. In fact, due to loop unrolling, our implementation of subtraction in F p does not execute any control-flow statements at all. Multiplication and Squaring. A multiplication of two elements a, b ∈ F p can be accomplished by conventional integer multiplication of a and b, along with a reduction of the obtained 384-bit product modulo the prime p. There exist two principal techniques for implementing multiple-precision multiplication in software, namely operand scanning (also called pencil-and-paper method [START_REF] Menezes | Handbook of Applied Cryptography[END_REF]) and product scanning (also known as Comba's method [START_REF] Comba | Exponentiation cryptosystems on the IBM PC[END_REF]). Both methods execute the same number of single-precision multiplications, but differ in loop structure and inner-loop operation. The operand scanning technique uses a nested loop to calculate the double-precision partial products in a row-by-row fashion [START_REF] Großschädl | Energy-efficient software implementation of long integer modular arithmetic[END_REF]. In each iteration of the inner loop, an operation of the form a • b + c + d is carried out, i.e. two single-precision words are multiplied together and two other words are added to the product. On the other hand, the product scanning algorithm is characterized by a nested-loop structure consisting of two outer loops and two inner loops; the first outer loop calculates the lower half of the product and the second outer loop the upper half [START_REF] Großschädl | Energy-efficient software implementation of long integer modular arithmetic[END_REF]. The partial products are added up in a column-wise fashion using an inner-loop operation of the form s + a • b, i.e. two words are multiplied and the product is added to a cumulative sum.

The relative performance of operand scanning vs. product scanning depends on a range of factors such as the programming language and the representation of the long integers. Most implementations of multiple-precision multiplication written in C/C++ or Java use the operand-scanning method and represent the operands as arrays of single-precision words whose bitlength matches the wordsize of the underlying processor (e.g. 32-bit words on a 32-bit processor). The inner loop of the operand-scanning method is straightforward to implement in a high-level programming language since the result of an operation of the form a • b + c + d is at most 64 bits long (and, therefore, fits into a C/C++ variable of type unsigned long long or a Java variable of type long) when a, b, c, and d are 32-bit words. However, a peculiarity of Java, compared to C/C++, is the lack of unsigned data types, which calls for an implementation of the inner loop as shown in Listing 1. The variables carry and product are of type long and can hold 64-bit signed integers, whereas x, y, and z are 32-bit int arrays. Java requires a type conversion (or "widening") of the operands from int to long in order to get a 64-bit result when multiplying two 32-bit integers. An integral part of this conversion process is sign extension, which means that the upper 32 bits of the 64-bit long representation are filled with the sign bit of the original 32-bit int value. These upper 32 bits have to be masked out to obtain the corresponding unsigned value; the implementation shown in Listing 1 achieves this via a logical AND operation using LONG MASK, a final static variable of type long, which is defined in the BigInteger class and initialized with the literal 0xffffffffL. Of course, performing three such maskings in the inner loop incurs a significant performance degradation.

The product scanning method, on the other hand, performs a multiply-accumulate operation of the form s + a • b in its inner loop, i.e. two single-precision words are multiplied and the double-precision product is added to a cumulative sum [START_REF] Comba | Exponentiation cryptosystems on the IBM PC[END_REF]. However, the bitlength of the cumulative sum can grow beyond double precision when several double-precision products are summed up, which makes the product scanning method quite hard to implement in C/C++ or Java since high-level languages do not provide a primitive integer type whose bitlength is more than twice the length of a single-precision word. A straightforward way to circumvent this problem is to reduce the number of bits per word to less than the wordsize of the underlying processor, following the rationale discussed earlier in this section for the addition of field elements. Since most J2ME-enabled mobile devices are equipped with 32-bit processors, we can, for example, use a 29-bit-per-word representation and implement the product scanning method as shown in Algorithm 2. Having single-precision words of 29 bits means that all double-precision partial products a j • b i-j in Algorithm 2 consist of at most 58 bits. Consequently, we can use a 64-bit variable of type long to hold the cumulative sum s; in this case, up to 2 64-58 = 26 = 64 partial products can be added up without overflowing s. Such a reduction of the bitlength of operand words (which was first suggested by Barrett [3,p. 317] roughly 25 years ago 6 ) allows for a very efficient implementation of the inner loop since masking operations as in Listing 1 can be avoided.

The result of a multiplication performed according to the first part (i.e. line 1 -16) of Algorithm 2 is a 348-bit product Z represented by an array of twelve Algorithm 2. Multiplication in Fp Input: Two 174-bit integers, A = (a5, a4, a3, a2, a1, a0) and B = (b5, b4, b3, b2, b1, b0), represented by six 29-bit words. Output: Modular product Z = A • B mod (2 174 -3) = (z5, z4, z3, z2, z1, z0).

1: s ← 0 2: for i from 0 by 1 to 5 do 3:

for j from 0 by 1 to i do 4:

s ← s + aj • bi-j 5:
end for 6:

zi ← s & 0x1fffffff 29-bit words, i.e. Z = (z 11 , . . . , z 1 , z 0 ). This product has to be reduced modulo p = 2 174 -3 to obtain a final result within the range of [0, p -1]. Since p is a PM prime [START_REF] Crandall | Method and apparatus for public key exchange in a cryptographic system[END_REF] of the form 2 k -c, we can exploit the relation 2 k ≡ c mod p to accomplish the modular reduction in an efficient way. The reduction operation requires to split the product Z into a lower half Z L (comprising, in our case, the six words z 0 , z 1 , . . . , z 5 ) and an upper half Z H (consisting of z 6 , z 7 , . . . , z 11 ) so that Z = Z H • 2 k + Z L . Now, Z can be reduced modulo p = 2 k -c by simply substituting 2 k by c as shown in Equation [START_REF] Arnold | The Java TM Programming Language[END_REF].

Z mod p = Z H • 2 k + Z L mod p = Z H • c + Z L mod p (2)
In essence, this boils down to multiplying Z H by c and adding the product to Z L , which leads to a result that is at most (c + 1) times larger than p (i.e. the result is just a few bits longer than p if c is small). To get a completely reduced result, one can either perform the same procedure again, or simply subtract the prime p until a final result within the range of [0, p -1] is obtained. The second part of Algorithm 2 (i.e. line 17 to 22) formally describes the reduction of the 348-bit product Z = (z 11 , . . . , z 1 , z 0 ) modulo p = 2 174 -3. Note that, in our implementation, the multiplication by 3 in line 19 is realized via three additions of z i+6 . Therefore, reducing Z modulo 2 174 -3 costs, in practice, no more than adding three 174-bit integers. The for-loop in line 18 -21 is very similar to the loop of Algorithm 1 and, thus, can be implemented in Java in the same way as detailed earlier in this subsection for the addition in F p . Due to the 29-bit-perword representation, it is possible to use a 32-bit variable of type int for the sum s and efficiently perform the additions in line 19 without overflow or loss of precision. The final result of Algorithm 2 may be not fully reduced and the least significant word z 0 may be up to 30 bits long instead of 29, similar to the result of Algorithm 1. However, as already mentioned, these "peculiarities" do not require special consideration since all arithmetic operations (bar inversion) are implemented such that they tolerate incompletely-reduced input operands and overlength (i.e. 30-bit) words. Note that Algorithm 2 is a simplified version of our actual Java implementation of multiplication in F p ; we unrolled all loops to maximize performance. Furthermore, as stated in Subsection 2.1, we represent the field elements (i.e. 174-bit integers) by six individual variables of type int instead of arrays. These optimizations allow us to perform a multiplication without executing data-dependent branches or load operations, which helps to prevent certain forms of side-channel attack.

The square A 2 of a long (i.e. multiple-precision) integer A can be calculated considerably faster than the product of two distinct integers. When A = B, all partial products of the form a j • b i-j with j = i -j in Algorithm 2 are identical to the partial products a i-j • b j , i.e. they appear twice. However, an optimized squaring algorithm calculates each of these partial products only once and then shifts it left in order to double it. Due to our 29-bit-per-word representation, a 58-bit partial product held in a 64-bit long variable can be efficiently shifted to the left by one bit position without overflow. Multiplying two 174-bit integers represented by six 29-bit words requires a total of 36 word-level multiplications (i.e. lmul instructions in Java), whereas the squaring of a 174-bit integer costs only 21 word-level multiplications. In theory, squaring is nearly twice as fast as multiplication, but the difference in execution time decreases when taking the modular reduction into account. Modular squaring is generally only about 20% faster than modular multiplication since the reduction operation always takes the same time, regardless of whether a square or a product is reduced.

Inversion. We implemented the inversion in F p according to the binary version of the Euclidean algorithm (Algorithm 2.22 in [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]) and applied some low-level optimizations such as multi-bit shifting. Even though inversion is costly, it has only little impact on scalar multiplication when using projective coordinates.

Point Arithmetic on GLV Curves

This section is devoted to the efficient implementation of scalar multiplication on a GLV curve and structured in a similar way as Section 2. We first explain the rationale behind choosing the curve y 2 = x 3 -7 over F p and then elaborate on different algorithms for scalar multiplication on GLV curves.

Selection of Elliptic Curve

At Crypto 2001, Gallant et al [START_REF] Gallant | Faster point multiplication on elliptic curves with efficient endomorphism[END_REF] introduced special families of elliptic curves over F p that possess an endomorphism of small norm and demonstrated how to exploit this endomorphism to speed up a scalar multiplication. These so-called GLV curves can be seen as somewhat related to Koblitz curves over F 2 m since both provide a "shortcut" in the form of an endomorphism that allows one to perform a scalar multiplication significantly faster compared to random curves [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]. Gallant et al considered in [START_REF] Gallant | Faster point multiplication on elliptic curves with efficient endomorphism[END_REF] curves defined by the Weierstraß equation y 2 = x 3 + ax (i.e. b = 0) and y 2 = x 3 + b (i.e. a = 0) over a prime field F p satisfying p ≡ 1 mod 4 in the former case and p ≡ 1 mod 3 in the latter. Both types of curve feature an endomorphism φ whose characteristic polynomial has small coefficients; in the former case the characteristic polynomial is λ 2 + 1 and in the latter case it is λ 2 + λ + 1 (see [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF] for details). During the past ten years, the work of Gallant et al received considerable attention and the GLV method has been extended to hyperelliptic curves and recently to curves over F p 2 that are twists of curves defined over F p (the so-called GLS curves [START_REF] Galbraith | Endomorphisms for faster elliptic curve cryptography on a large class of curves[END_REF]). However, we decided to use a Weierstraß curve of the form y 2 = x 3 + b over F p for our Java implementation since this choice of curve and field is more compliant with the major standards for EC cryptography (e.g. IEEE P1363 [START_REF]IEEE Std 1363-2000: IEEE Standard Specifications for Public-Key Cryptography[END_REF], SECG [START_REF]Standards for Efficient Cryptography Group (SECG): SEC 1: Elliptic Curve Cryptography[END_REF]) than hyperelliptic curves or elliptic curves over F p 2 .

GLV curves are attractive to implementers for two reasons. First, when exploiting the endomorphism as per [START_REF] Gallant | Faster point multiplication on elliptic curves with efficient endomorphism[END_REF], scalar multiplication on GLV curves is considerably faster than on random curves, even though the speed-up is not as dramatic as for Koblitz curves [START_REF] Koblitz | CM-curves with good cryptographic properties[END_REF]. Second, the GLV method can be applied in settings where arbitrary points are used as input for the scalar multiplication (e.g. in ECDH key exchange), i.e. the GLV method does not rely on a fixed base point that is known a priori. In the next subsection, we will briefly describe the GLV algorithm for scalar multiplication on curves of the form y 2 = x 3 + b. As mentioned above, these curves possess an efficiently computable endomorphism φ with characteristic polynomial λ 2 + λ + 1. Thanks to this endomorphism, it is possible to calculate the scalar multiplication k • P as k 1 • P + k 2 • φ(P ), whereby k 1 and k 2 have only about half of the bitlength of the original k. These two half-length scalar multiplications can be carried out in an "interleaved" fashion using Shamir's trick [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF], which halves the number of point doublings and also reduces the number of point additions compared to a conventional calculation of k • P using the double-and-add algorithm.

Finding a GLV curve with "good" cryptographic properties is a non-trivial task since, as mentioned in [START_REF] Cohen | Handbook of Elliptic and Hyperelliptic Curve Cryptography[END_REF]Section 15.2], "the class of elliptic curves with an endomorphism of small norm is small." This task becomes harder still when one tries to find a combination of PM prime field and GLV curve so that both the field and the curve (resp. group) arithmetic can be implemented efficiently. We used the computer algebra package Magma to enumerate all PM primes of the form 2 k -c for 160 ≤ k ≤ 176 and c < 16, and then search for each of them a GLV curve containing a large cyclic subgroup. Among the pairs of PM prime and GLV curve we found was p = 2 174 -3 and the curve defined through the Weierstraß equation y 2 = x 3 -7 (i.e. a = 0 and b = p -7) over F p , which we finally decided to use for our Java implementation. Since a detailed description of the curve-finding methodology would go beyond the scope of this paper, we restrict ourselves to show that this specific GLV curve is suitable for use in EC cryptography. Both the IEEE standard P1363 [START_REF]IEEE Std 1363-2000: IEEE Standard Specifications for Public-Key Cryptography[END_REF] and the book of Cohen et al [START_REF] Cohen | Handbook of Elliptic and Hyperelliptic Curve Cryptography[END_REF] serve as a good reference for security criteria that an elliptic curve has to fulfill; the most important ones are the following.

-First and foremost, the group of points on the curve has to contain a large subgroup of prime order n. In other words, the curve should have a small co-factor h; ideally, the co-factor is 1. Our curve E : y 2 = x 3 -7 over the field F p with p = 2 174 -3 has the order #E(F p ) = 23945242826029513411849172123055713727388153314904213, which happens to be a 174-bit prime; thus, the co-factor h = #E(Fp) n of this curve is 1. Following the notation from Section 1, a cryptosystem using the group E(F p ) provides a level of security that is well above the minimum (symmetric) level of 80 bits as recommended by ECRYPT II, the European Network of Excellence in Cryptology [START_REF]ECRYPT II Yearly Report on Algorithms and Keysizes[END_REF]Table 7.4].

-In order to circumvent the Semaev-Smart-Satoh-Araki (SSSA) attack, the curve must not be anomalous. This is obviously the case for our GLV curve since #E(F p ) = p. -The embedding degree of the curve must not be small (i.e. the order of the EC group n must not divide p k -1 for "small" values of k) to prevent the Menezes-Okamoto-Vanstons (MOV) attack and other attacks based on the Weil and Tate pairing. Our GLV curve clearly satisfies this condition since p k ≡ 1 mod n for any k ∈ [1, 100].

Efficient Implementation of Scalar Multiplication

A scalar multiplication is an operation of the form k • P whereby P denotes an EC point of large prime order n and k is an integer in the range [1, n -1] (see [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF] for more information). Scalar multiplication in an EC group is nothing else than the repeated application of the group operation (i.e. point addition) on an element of the group, similar to exponentiation in a multiplicative group. It is common practice (at least when using curves over prime fields) to represent the points in projective coordinates as they allow for performing a point addition without inversion in the underlying finite field [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]. Our implementation of the point addition (resp. point doubling) is based on the mixed Jacobian-affine coordinates (resp. projective Jacobian coordinates) from Section 3.2.2 in [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]. An addition of points requires eight multiplications (8M), three squarings (3S), as well as a number of less-costly operations (e.g. additions, subtractions) in the underlying prime field, whereas a point doubling takes 4M + 4S. However, the cost of point doubling on our GLV curve can be reduced by one multiplication to 3M + 4S since the parameter a is 0. Note that several variants of Jacobian point addition/doubling formulae exist, some of which trade multiplications in F p for squarings at the expense of an increased number of certain low-cost field operations 7 . However, none of these variants is capable to speed up our implementation due to the fact that the less-costly operations have a non-negligible execution time of between 0.1M and 0.27M (see Section 4). Thus, we decided to stick with the original formulae from [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF] optimized for a = 0. The most basic technique for performing a scalar multiplication k • P is the double-and-add method [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF], which works in a similar way as the square-andmultiply method for exponentiation. Given a scalar k of a length of n bits, the double-and-add approach executes n point doublings and (in the average case) about n/2 point additions; the exact number of point additions depends on the Hamming weight of k. As mentioned above, a point addition on our GLV curve requires 8M + 3S, whereas a point doubling takes only 3M + 4S. Therefore, the overall cost of the double-and-add method amounts to 3n + 8n/2 = 7n multiplications and 4n + 3n/2 = 5.5n squarings in F p (or, equivalently, 7M + 5.5S per bit of the scalar k). The average number of point additions can be reduced from n/2 to n/3 when the scalar k is represented in Non-Adjacent Form (NAF) [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]. In this case, the double-and-add method requires just 5. 6n multiplications and 5n squarings in the average case, i.e. 5. 6M + 5S per bit. However, a more significant reduction of execution time can be achieved by exploiting the endomorphism φ of our GLV curve as explained in [START_REF] Gallant | Faster point multiplication on elliptic curves with efficient endomorphism[END_REF]. This endomorphism makes it possible to obtain the scalar product k • P via k 1 • P + k 2 • φ(P ), which is, in general, more efficient than a straightforward calculation of k • P since k 1 and k 2 have typically only half the bitlength of k and the two scalar multiplications k 1 • P and k 2 • φ(P ) can be carried out "simultaneously" (i.e. in an interleaved fashion) using Shamir's trick [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]Section 3.3.3].

In the following, we summarize some basic facts about our GLV curve and explain how to exploit its endomorphism φ for scalar multiplication, similar to Section 3.5 in [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]. Since the curve parameter a is 0 and the prime p satisfies p ≡ 1 mod 3, our GLV curve is of the type described in Example 4 in [START_REF] Gallant | Faster point multiplication on elliptic curves with efficient endomorphism[END_REF]. The underlying field F p contains an element β of order 3 (because p ≡ 1 mod 3); in our implementation we use

β = 394094579125250648008654461421808193607170272365849
According to [START_REF] Gallant | Faster point multiplication on elliptic curves with efficient endomorphism[END_REF]Example 4], the map φ : E → E defined by φ : (x, y) → (βx, y) and φ :

O → O (3)
is an endomorphism of E defined over F p . The characteristic polynomial of φ is λ 2 + λ + 1. In order to exploit this endomorphism for scalar multiplication, we need a root modulo n of the characteristic polynomial, i.e. we need a solution to the equation λ 2 + λ + 1 ≡ 0 mod n; our implementation uses λ = 7591969537352440260196679277338091599843085579298264 7 Most of these variants can be found in the Explicit Formulas Database (EFD), an extensive repository of formulae for point arithmetic on various families of elliptic curves. The EFD is available online at http://www.hyperelliptic.org/EFD. The solution λ has the property that φ(P ) = λ • P for all P ∈ E(F p ) [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]. Note that computing φ(P ) for a point P = (x, y) requires only one multiplication in F p , namely β • x. As stated before, the common strategy for computing k • P on a GLV curve is to decompose the n-bit scalar k into two "half-length" integers k 1 and k 2 (often referred to as balanced length-two representation of k [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]) so that k = k 1 + k 2 λ mod n. This decomposition of k into k 1 and k 2 is described in detail in [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF] and requires merely a few multi-precision multiplications if the curve and field are fixed. As k

• P = k 1 • P + k 2 • λ • P = k 1 • P + k 2 • φ(P )
, the result of k • P can be obtained by first computing φ(P ) (which takes one single field multiplication) and then using a simultaneous double-scalar multiplication ("Shamir's trick") to perform these two half-length scalar multiplications in an interleaved fashion. Consequently, the GLV requires only n/2 point doublings for an n-bit scalar multiplication, which corresponds to a 50% reduction compared to the double-and-add method. The number of point additions depends on the joint Hamming density of k 1 and k 2 ; in the average case (i.e. when the joint Hamming density is 0.75), a total of 0.75 • n/2 = 0.375n point additions must be carried out. In summary, the overall cost of the GLV method amounts to 0.5n • 3 + 0.375n • 8 = 4.3n multiplications and 0.5n • 4 + 0.375n • 3 = 3.125n squarings in F p , i.e. 4.3M + 3.125S per bit. However, the Hamming density can be reduced to 0.5 (on average) by representing k 1 and k 2 in Joint Sparse Form (JSF) [START_REF] Solinas | Low-weight binary representations for pairs of integers[END_REF], which, in turn, cuts the number of point additions by roughly one third to 0.5 • n/2 = 0.25n. In this case, the total cost of computing k • P on a GLV curve is reduced to, on average, 0.5n

Implementation Results and Discussion

We evaluated the performance (i.e. execution time) of our Java implementation of the field arithmetic and different algorithms for scalar multiplication on an IBM Thinkpad T60 and a set of mobile phones, including an HTC Desire S, a Nokia X2, and an old Nokia 6610. The most powerful of these test devices is the Thinkpad T60; it features a 32-bit Intel T2300 ("Core Duo") processor clocked with a frequency of 1.66 GHz. At the opposite end of the spectrum is the Nokia 6610, which is equipped with an ARM 11 processor clocked at 104 MHz. Table 1 summarizes the execution times of the field arithmetic operations on the T60 and the three mobile phones. Given the differing computational power of these On the Thinkpad T60, the relative execution times of the arithmetic operations are very similar to that of previous implementations (e.g. [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]) written in C and/or Assembly language. Squaring is about 22% faster than multiplication (i.e. S = 0.78M), whereas addition and subtraction (and similar operations like halving or negation of a field element) execute in roughly 0.1M. The inversion is slow compared to the multiplication (I = 116M), but this not surprising since also most C (and Assembly) implementations of prime-field arithmetic have an I/M ratio of between 50 and 100 [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]. However, the relations are different on the Nokia 6610 because addition and subtraction take more than one fourth of the execution time of a multiplication; the exact ratio of addition to multiplication is 0.27. Also the inversion is very slow compared to the multiplication; based on the results from Table 1 we have I = 235M. An explanation for the differences between the T60 and the Nokia 6610 can be found in the characteristics of the underlying processor. The Core Duo of the T60 is a superscalar processor able to execute several arithmetic/logical instructions in parallel, which has a positive effect on the execution time of addition, subtraction, and inversion. On the other hand, the Core Duo can execute only a single integer multiply instruction at a time, i.e. multiplication and squaring in F p can take little advantage of the superscalar pipeline. In contrast, the ARM 11 processor of the Nokia 6610 has a single-issue pipeline with a relatively fast integer multiplier, which favors the field multiplication over addition, subtraction, and inversion.

Table 2 shows a comparison of the four algorithms for scalar multiplication discussed in Subsection 3.2. The actual execution times on both the Thinkpad T60 and the mobile phones roughly match with the cost-per-bit figures given in the second column when taking into account that this approximate cost model only considers multiplications and squarings in F p . More concretely, on the T60 the GLV method with JSF representation of k 1 , k 2 is 1.74 times faster than the standard double-and-add technique, which is relatively close to the theoretical speed-up factor of 2.0 suggested by the approximate cost model. However, as stated before, the approximate cost model is based on the number of multiplications and squarings in F p and ignores that the GLV method has to perform other operations such as the decomposition of k into k 1 , k 2 and the calculation of the sum P + φ(P ) in affine coordinates, which may involve a costly inversion in F p . The T60 executes the GLV method in merely 326.9 µs; this translates to over 3,000 scalar multiplications per second. In comparison, the Bouncy Castle Lightweight Crypto API [START_REF]The Legion of the Bouncy Castle: Lightweight Cryptography API (Release 1.47[END_REF] requires 14.95 ms for a 174-bit scalar multiplication, i.e. our implementation outperforms Bouncy Castle by a factor of 45. On the 6610, the GLV method is only 1.58 times faster than the double-and-add method, mainly because of the fact that addition/subtraction and inversion are relatively more costly (versus multiplication) than on the T60. Nonetheless, the Nokia 6610 is able to execute the GLV method in about 400 ms, which is 5.38 times faster than the Java implementation of EC scalar multiplication over the binary extension field F 2 191 reported in [START_REF] Tillich | A survey of public-key cryptography on J2ME-enabled mobile devices[END_REF].

The GLV method compares very well with other approaches for scalar multiplication and other forms of elliptic curves, e.g. Montgomery [START_REF] Montgomery | Speeding the Pollard and elliptic curve methods of factorization[END_REF] or Edwards curves [START_REF] Edwards | A normal form for elliptic curves[END_REF]. A Montgomery curve over F p is defined by an equation of the form By 2 = x 3 + Ax 2 + x with (A 2 -4)B = 0 and allows for fast computation of the x-coordinate of the sum P + Q of two points P , Q whose difference P -Q is known. More precisely, a point addition performed according to the formula in [21, p. 261] requires four multiplications (4M) and two squarings (2S), whereas a point doubling costs 3M and 2S. However, one of the three multiplications in the point doubling uses the constant (A -2)/4 as operand, which is small if the parameter A is chosen properly. Our experiments show that multiplying a field element by a small (up to 29 bits) constant costs some 0.2M. Furthermore, the point addition formula given in [21, page 261] can be optimized when using the so-called Montgomery ladder (Algorithm 13.35 in [START_REF] Cohen | Handbook of Elliptic and Hyperelliptic Curve Cryptography[END_REF]) for scalar multiplication and representing the base point in projective coordinates with Z = 1 (see also Remark 13.36 (ii) in [START_REF] Cohen | Handbook of Elliptic and Hyperelliptic Curve Cryptography[END_REF]). In this case, a "ladder"-based implementation of the scalar multiplication requires exactly 5.2n multiplications and 4n squarings in F p , i.e. 5.2M + 4S per bit, which is still a lot more than the 3.5M + 2.75S of the GLV method with JSF-representation of the two half-length scalars.

Conclusions

We introduced a Java implementation of scalar multiplication on a GLV curve over a 174-bit prime field. Our implementation supports arbitrary base points (making it suitable for ECDH key exchange) and is optimized to reach high performance, low memory footprint and small bytecode size. Furthermore, the described implementation is highly self-contained as it needs only a few classes from the standard Java class library. On a Thinkpad T60 with a 1.66 GHz Core Duo processor, our GLV method reaches a throughput of 3,000 scalar multiplications per second, which is about 45 times higher than the throughput of the widely-used Bouncy Castle library for J2ME. The scalar multiplication time on mobile phones ranges from less than 2 ms (HTC Desire S) to roughly 400.6 ms (Nokia 6610). We attribute the high performance of our GLV technique to the efficiency of both the field and group arithmetic. The radix-2 29 representation of field elements allows for a branch-less implementation of the field arithmetic modulo p = 2 174 -3, which facilitates the execution on JiT-enabled JVMs. We also demonstrated that, when exploiting their endomorphism, GLV curves are considerably faster than ordinary Weierstraß curves or Montgomery curves. In summary, our measured results confirm the great potential of GLV curves and PM prime fields for the implementation of high-speed EC cryptography.

The full Java source code of the implementation described in this paper is available for download at https://cryptolux.org.

Table 1 .

 1 Timings of the field arithmetic on different devices.

	Operation	T60	HTC	X2	6610
	Addition	24.2 ns	124.2 ns	1319 ns	63.1 µs
	Subtraction	24.4 ns	130.0 ns	1772 ns	64.6 µs
	Multiplication 255.5 ns	994.4 ns	7256 ns	232.3 µs
	Squaring	197.9 ns	860.2 ns	6702 ns	186.9 µs
	Inversion	26,6 µs	191.4 µs	1479 µs	54,8 ms

Table 2 .

 2 Comparison of scalar multiplication methods on different devices , it is not surprising that the measured execution times vary by a large extent. However, besides the differences in processing speed, one must also take into account the capabilities of the particular JVM of each device. On the T60 we used the HotSpot Client VM that comes with Sun's JDK 6 Update 27; this VM features a JiT compiler for efficient execution of bytecodes. Most modern smart phones have either a VM with JiT compilation or a processor with Java extensions. On the other hand, the old Nokia 6610 provides a conventional VM without JiT compiler or any other form of Java acceleration. In order to obtain accurate timings, we put each arithmetic function into a loop and performed a sufficiently large number of iterations so that the overall execution time was in the range of several seconds. We measured the execution time with help of the currentTimeMillis function, which is provided by the System class. Table1specifies the average execution time (i.e. the quotient of overall execution time and number of iterations) of the arithmetic operations.

	Algorithm	Cost per bit	T60	HTC	X2	6610
	Dbl-and-Add	7M + 5.5S	569.1 µs	2745 µs 19.79 ms 632.5 ms
	Dbl-and-Add (NAF)	5. 6M + 5S	490.3 µs	2352 µs 17.24 ms 552.9 ms
	GLV method	4.3M + 3.125S 362.5 µs	2057 µs 13.36 ms 437.4 ms
	GLV method (JSF)	3.5M + 2.75S 326.9 µs	1885 µs 12.20 ms 400.2 ms

devices

More precisely, the cardinality of the group of Fp-rational points on said curve is a 174-bit prime. A properly implemented EC cryptosystem using this group provides a security level similar to that of a 87-bit secret-key cryptosystem, which is well above the "smallest general-purpose level" of 80 bits recommended by ECRYPT[START_REF]ECRYPT II Yearly Report on Algorithms and Keysizes[END_REF].

Note that several other implementations of the product-scanning method, e.g. the one of Curve25519[START_REF] Bernstein | Curve25519: New Diffie-Hellman speed records[END_REF], take advantage of Barrett's idea to increase performance.


Chaya Ganesh
email: chaya.ganesh@gmail.com

C Pandu

Optimal Parameters For Efficient Two-Party Computation Protocols

Keywords: secure computation, malicious adversaries, cheating probability, communication complexity

We study the optimal parameters to minimize the cheating probability and communication complexity in protocols for two party computation secure against malicious adversaries. In cut-and-choose protocols for two party computation, we analyze the optimal parameters to keep the probability of undetected cheating minimum. We first study this for a constant number of circuits, and then generalize it to the case of constant bandwidth. More generally, the communication cost of opening a circuit is different from retaining the circuit for evaluation and we analyze the optimal parameters in this case, by fixing the total bits of communication. In the second part of our analysis, we minimize the communication complexity for a given probability of undetected cheating. We study, what should be the parameters to achieve a given cheating probability in minimum amount of communication in a given cut-and-choose protocol. While still keeping the security guarantees, that is, the cheating probability negligible, we achieve a concrete improvement in communication complexity by using optimal parameters in existing cut-and-choose protocols.

Introduction

Secure two party computation. Secure two-party computation allows two parties with respective private inputs x and y to jointly compute a functionality f (x, y) = (f 1 (x, y), f 2 (x, y)), such that the first party receives f 1 (x, y) and the second party receives f 2 (x, y). The security requirements are privacy and correctness, that is, nothing should be learned from the protocol other than the output, and that the output should be distributed according to the prescribed functionality. The formal definition blends both the requirements and follows the simulation paradigm [START_REF] Goldreich | Basic Applications[END_REF]. Security must be guaranteed even when one of the parties is adversarial. An adversary may be semi-honest, in which case it follows the specification of the protocol, but attempts to learn additional information by analyzing the transcript of messages of the protocol execution. In contrast, the adversary may even be malicious, in which case it can arbitrarily deviate from the specifications of the protocol. Yao [START_REF] Yao | How to generate and exchange secrets[END_REF] presented the first general solutions for the problem of secure computation, with security against semi-honest adversaries for the two-party case, and Goldreich, Micali and Wigderson [START_REF] Goldreich | How to play any mental game or a completeness theorem for protocols with honest majority[END_REF] gave the solution for the multi-party case with security even against malicious adversaries.

Yao's Protocol. Yao gave a constant-round protocol for the secure computation of any functionality in the presence of semi-honest adversaries. Let f be the functionality that the two parties agree to compute, and let x,y be their respective inputs. (for simplicity, assume that both parties wish to receive f (x, y)). In Yao's protocol, party P 1 first generates an encrypted (called "garbled") circuit computing f (x, •) and then sends it to P 2 . The circuit is such that it reveals nothing in its garbled form and therefore reveals nothing to P 2 . P 2 can, however, obtain the intended output f (x, y) by "decrypting" the circuit. This decryption must ensure that it reveals nothing more than f (x, y) to P 2 . That is, P 2 should learn the value on the circuit output wire without learning the values on any of the internal wires. This is accomplished by P 2 obtaining a series of keys corresponding to its input y, such that given the garbled circuit and these keys, the output value f (x, y), and only this value, may be obtained. Now, P 2 must somehow receive these keys from P 1 while making sure not to reveal anything about y to P 1 . This is accomplished by running secure 1-out-of-2 Oblivious Transfer (OT) protocol [START_REF] Rabin | How to exhange secrets by oblivious transfer[END_REF]. A detailed description of Yao's protocol, and a proof of security can be found in [START_REF] Lindell | A proof of yao's protocol for secure two-party computation[END_REF]. Yao's generic protocol is known to be efficient, and even practical, for functionalities that have relatively small circuits.

Malicious behavior and cut-and-choose. Yao's protocol is secure only in the presence of relatively weak semi-honest adversaries. Goldreich, Micali and Wigderson gave the first positive results for general secure computation against malicious adversaries. The compiler of GMW [START_REF] Goldreich | How to play any mental game or a completeness theorem for protocols with honest majority[END_REF] converts any protocol that is secure for semi-honest adversaries into one that is secure for malicious adversaries. The compiler, however, is based on reducing the statement that needs to be proved (the honesty of the parties' behavior in this case) to an NP-complete problem, and using generic zero-knowledge proofs to prove the statement. The secure protocol resulting from the compiler runs in polynomial time but is rather inefficient.

Lindell and Pinkas gave an efficient protocol secure against malicious adversaries, based on cut-and-choose methodology in [START_REF] Lindell | An efficient protocol for secure two-party computation in the presence of malicious adversaries[END_REF]. Let us consider what happens when P 1 is malicious. It can construct a garbled circuit that computes a function which is different than the one P 1 and P 2 jointly agreed to compute. The "cut-and-choose" technique is a solution to this problem. P 1 first constructs many garbled circuits and sends them to P 2 . Then, P 2 randomly chooses half of them and asks P 1 to "open" the chosen half, that is, reveal the decryption keys corresponding to the chosen circuits. P 1 opens the chosen half, and P 2 checks that they were constructed correctly. If they were indeed correct, then P 2 evaluates the remaining circuits and computes the output. The opened and checked circuits are called check circuits, and the rest are evaluation circuits. The idea behind the cut-and-choose methodology is that if a malicious P 1 constructs the circuits incorrectly, then it will be caught by P 2 with high probability. This so-lution solves the problem of P 1 constructing the circuit incorrectly. Now, since the parties evaluate a number of circuits, some mechanism must be employed to force the parties to use the same input when evaluating each circuit; otherwise, an adversarial party could learn more information than allowed. This, and other requirements that are not met by just applying the cut-and-choose technique are handled by the protocol implementation given in [START_REF] Lindell | An efficient protocol for secure two-party computation in the presence of malicious adversaries[END_REF], where the authors give a cut-and-choose based solution, and a simulation based proof of security.

Motivation. In a cut-and-choose protocol for two party computation, half of the total number of garbled circuits are check circuits in all protocols in literature. We ask, what should be the number of check circuits, so as to minimize the probability of undetected cheating by P 1 ? We study this question in two settings: same cost circuits, and cheaper check circuits. Then, we ask, what should be the number of check circuits to achieve a given cheating probability in minimum amount of communication? With increasing interest from both within and outside the cryptographic community in secure protocols that are efficient enough to be implemented in practice, efficiency issues are an important consideration. Communication complexity of interactive protocols is one of their most important complexity measures. Bandwidth optimization is interesting in settings where communication is expensive, e.g, for a mobile roaming user. This is the motivation of our work in this paper.

Our Results. We study the optimal parameters for cut-and-choose protocols for general secure computation. Consider a cut-and-choose protocol: the total number of garbled circuits constructed by P 1 , the number of circuits opened out of the total (these are called check circuits and the rest are evaluation circuits) are the parameters of the protocol, and the protocol achieves some (negligible) probability of undetected cheating incurring a certain communication complexity. Each garbled circuit has a communication cost associated, which is the number of bits that needs to be communicated in order to send the circuit to the other party. In general, the communication cost of a check circuit need not be the same as the cost of an evaluation circuit. In this paper, we analyze the optimal parameters to achieve minimum probability of undetected cheating and minimum communication complexity. We first study the optimal fraction of the total number of circuits that should be check circuits, so as to minimize the probability of undetected cheating by P 1 . We then generalize this to the case when the communication cost of a check circuit is cheaper than the cost of an evaluation circuit (as in [START_REF] Goyal | Efficient two party and multi party computation against covert adversaries[END_REF]). We show the optimal number of check circuits to minimize the cheating probability in this setting.

Further, we minimize the communication complexity of a cut-and-choose protocol, while still keeping the probability of undetected cheating by P 1 negligible. We study the optimal number of check circuits to minimize the communication complexity while achieving a given cheating probability. Our analysis yields parameters which can be used in any of the existing cut-and-choose protocols and get a concrete improvement in the communication complexity.

Related work. Efficient protocols for secure two party computation based on the cut-and-choose technique have been studied in [START_REF] Mohassel | Efficiency tradeoffs for malicious two party computation[END_REF], [START_REF] Lindell | An efficient protocol for secure two-party computation in the presence of malicious adversaries[END_REF], [START_REF] David | Revisiting the efficiency of malicious two party computation[END_REF] and [START_REF] Lindell | Secure two-party computation via cut-andchoose oblivious transfer[END_REF]. The optimization of parameters for secure computation protocols has been done earlier only in [START_REF] Shelat | Two-output secure computation with malicious adversaries[END_REF]. Our results are more general, we use a different technique to arrive at optimal parameters for minimum probability of undetected cheating, and our techniques further extend to a more general case of cheaper check circuits. Furthermore, we study the optimal parameters for minimum communication complexity, while achieving a given cheating probability.

Background

Cut-and-Choose Protocol

Lindell and Pinkas gave an efficient two party protocol secure against malicious adversaries [START_REF] Lindell | An efficient protocol for secure two-party computation in the presence of malicious adversaries[END_REF]. Their construction is based on applying cut-and-choose techniques to the original Yao's circuit and inputs. Security is proved in the ideal/real simulation paradigm.

A malicious P 1 is forced to construct the garbled circuit correctly so that it indeed computes the desired function. P 1 constructs many independent copies of the garbled circuit and sends them to P 2 . Party P 2 randomly chooses half of them, and asks P 1 to open the chosen circuits. Now, P 2 checks that the opened circuits are constructed correctly. If they are, then P 2 is convinced that most of the remaining garbled circuits are also constructed correctly. If there are many circuits that are incorrectly constructed, then with high probability, one of those circuits will be in the set that P 2 challenges P 1 to open. The parties then evaluate the remaining circuits as in the original Yao's protocol for semi-honest adversaries, and take the majority output. The protocol also has to force both P 1 and P 2 to use the same inputs in each circuit. Such consistency checks are necessary, because if the parties were allowed to use different inputs to different copies of the circuit, then they can learn information that is more than just the desired output of the function. P 2 can do so, since it observes the outputs of all circuits, but in fact even P 1 , who only gets to see the majority output, can learn additional information: For example, if the protocol computes n invocations of a circuit computing the inner-product between n bit inputs. A malicious P 2 could provide the inputs 10

• • • 0 , 010 • • • 0 , • • • , 0 • • • 01 to the n different garbled circuits, and learn P 1 's input completely. If P 1 is malicious, it could also provide the inputs 10 • • • 0 , 010 • • • 0 , • • • , 0 • • • 01 . P 2 now
sends P 1 the majority output value, which is equal to the majority value of P 2 's input bits. A malicious P 1 could thus get additional information about P 2 's input. The protocol enforces consistency checks by having P 1 commit to the garbled circuits and also to the garbled values corresponding to the input wires of the circuits. We give a high-level overview of the protocol here.

Parties P 1 and P 2 have respective inputs x and y, and wish to compute the agreed function f (x, y).

1. The parties first decide on a circuit C that computes f . This circuit is then changed by replacing each input wire of P 2 by a gate whose input consists of s new input wires of P 2 and whose output is the exclusive-or of these wires.

The number of input wires of P 2 increases by a factor of s. P 2 's input is encoded in this way to prevent the following attack by P 1 : A malicious P 1 may provide corrupt input to one of possible inputs of P 2 in an OT protocol. In case P 2 chooses to learn this input it will not be able to decrypt the garbled tables which use this value, and will have to abort.

If on the other hand, P 2 chooses to learn the other input associated with this wire then it will never know that the first input is corrupt. P 1 can thus learn P 2 's input by observing whether or not P 2 aborts. Checking that the circuit is correctly constructed will not help in preventing this attack, since the attack is based on changing P 1 's input to the OT protocol. The attack is prevented by replacing the input bits of P 2 with s new input bits whose exclusive-or is used instead of the original input. P 2 can now encode a 0 input in 2 s-1 ways, and encode a 1 in 2 s-1 way. Given its input, P 2 chooses an encoding with uniform probability. The protocol is then executed with the new circuit, and P 2 uses oblivious transfer to learn the garbled values of its new inputs. As is shown in [START_REF] Lindell | An efficient protocol for secure two-party computation in the presence of malicious adversaries[END_REF], if P 1 supplies incorrect values as garbled values that are associated with P 2 's input, the probability of P 2 detecting this cheating is almost independent of P 2 's actual input. 2. P 1 commits to s different garbled circuits, all of them computing f , where s is a statistical security parameter. Additionally, P 1 also commits to the garbled values corresponding to the input wires of the circuits. P 1 can prove consistency of its inputs the following way. The proof is based on a cut-and-choose test for the consistency of the commitment sets combined with the cut-and-choose test for the correctness of the construction of circuits. P 1 constructs s pairs of sets of commitments, for each of its input wires. One set in every pair contains commitments to the 0 values of this wire in all circuits, and the other set is the same with respect to value 1. The protocol now randomly chooses a subset of these pairs, and a subset of the circuits, and checks that these sets give consistent inputs for these circuits. The protocol then evaluates the remaining circuits, and asks P 1 to open, in each of the remaining pairs, and only in one set in each pair, its garbled values for all evaluated circuits. This way, nothing is revealed to P 2 about whether these garbled values correspond to a 0 or to a 1. For the committed sets and circuits to pass P 2 's checks, there must be large subsets C and S, of the circuits and commitment sets, respectively, such that every choice of a circuit from C and a commitment set from S results in a circuit and garbled values which correctly compute f . P 2 accepts the verification stage only if all the circuits and sets it chooses to check are from the subsets C and S, respectively. If P 2 does not abort, then circuits which are not from C are in a minority of the evaluated circuits with high probability, and similarly for S. Therefore the majority result of the evaluation stage is correct. 3. Parties P 1 and P 2 run a 1-out-of-2 oblivious transfer protocol for every input bit of P 2 in which P 2 learns the garbled values of input wires corresponding to its input.

4. P 1 sends to P 2 the garbled circuits, as well as all the commitments that it prepared above. 5. P 1 and P 2 run a coin-tossing protocol to choose a random string. The resulting string defines which garbled circuits and commitments will be opened. 6. P 1 opens the garbled circuits and commitments which are chosen in the previous step. P 2 verifies that the opened circuits are correct and runs the consistency checks on the input values. P 2 checks the correctness of the check circuits. It verifies that each check circuit is a garbled version of the circuit C. The input tables are constructed by checking that the decommitments in the above step are valid, and associating the first value with the garbled value for 0 and the second value with 1. P 2 next checks the decommitments to P 1 's inputs. Finally, given all the garbled values to the input wires and their associated binary values, P 2 now decrypts the garbled circuit and compares it to the circuit C. If any of the checks fail, P 2 aborts. 7. P 1 sends the garbled values corresponding to P 1 's input wires in the unopened garbled circuits (evaluation circuits), P 2 runs consistency checks on these values, that is, for every evaluation circuit, all of the commitments that P 1 opened in evaluation sets commit to the same garbled value. 8. If all the checks pass, P 2 evaluates the unopened circuits, and takes the majority value as output.

Efficient two party computation protocols -Cheaper Check circuits

In [START_REF] Goyal | Efficient two party and multi party computation against covert adversaries[END_REF], the authors design an efficient multi party computation protocol in the covert adversary model. The techniques used in the two party case generalize to the case of two party computation protocols secure against standard malicious adversaries. To achieve an improvement in communication complexity, they take a different approach to constructing the garbled circuit. To construct a garbled circuit and commitments for the input keys, P 1 first generates a short random seed and feeds it to a pseudorandom generator. This generates the necessary randomness. P 1 then uses this randomness to construct the garbled circuit and the commitments. When the protocol begins, P 1 sends only a hash of each garbled circuit using a collision-resistant hash function to P 2 . P 2 chooses half of the circuits at random. In order to expose the secrets of each of the chosen circuit later, P 1 sends the seeds corresponding to the circuit, and not the whole opened circuit. P 2 uses the pseudorandom generator to generate the randomness from the sent seed and constructs the check circuits, and checks that they are indeed garbled versions of the agreed circuit. Once the checks go through, P 1 sends the remaining circuits, called the evaluation circuits to P 2 . The communication cost of a check circuit is therefore, not the whole circuit but only a hash as opposed to the cost of an evaluation circuit.

We briefly give the garbling procedure of [START_REF] Goyal | Efficient two party and multi party computation against covert adversaries[END_REF]. Let G be the description of a pseudorandom generator, seed a seed of suitable length, C be the description of the circuit that computes the agreed function, which is to be garbled.

Garble(G, seed, C, 1 s ) denotes the garbling procedure where s is the security parameter. The randomness required for constructing the garbled circuits includes, the random keys corresponding to the circuit wires, the random permutation chosen for the garbled entries of each gate table, and the random string chosen for each encryption. A random string of length O(s|C|) is sufficient for garbling. A pseudorandom generator G : {0, 1} n1 → {0, 1} n2 , where n 1 is polynomial in s and n 2 = O(s|C|) is used. The algorithm Garble runs G on seed to generate the randomness required for the circuit, and then computes the garbled circuit for C as described in [START_REF] Lindell | A proof of yao's protocol for secure two-party computation[END_REF].

Optimal number of check circuits

In the cut-and-choose protocol described in Section 2.1, we have the flexibility of choosing the number of check circuits. This is the subject of this section; we study what is the optimal number of circuits that should be check circuits to minimize the probability of undetected cheating by Party P 1 . In Section 3.1, we keep the total number of garbled circuits a constant, and minimize the cheating probability. In the next subsection, we generalize this to the case where a constant amount of communication bits is allowed (but the total number of circuits is not fixed). We minimize the cheating probability in these settings by choosing the optimal number of check circuits, c. In [START_REF] Shelat | Two-output secure computation with malicious adversaries[END_REF], the authors show the optimal number of check circuits, but our techniques to get an approximation for the expression of cheating probability makes the analysis extendible to the more general case of cheaper check circuits. We discuss both the cases, of same cost circuits and cheaper check circuits as the latter is an extension of the computations done for the former case.

Same-cost circuits

We consider the case where both check circuits and evaluation circuits have the same communication cost. Let n be the number of garbled circuits constructed by P 1 , and let c be the number of circuits checked. Assume that i out of n circuits are constructed incorrectly by a cheating P 1 . P 1 's cheating is not caught if all the check circuits are constructed correctly, and P 2 does not abort after evaluation of the remaining circuits. Now, the probability of P 1 's cheating not caught is given by

n-i c n c If i < n -c 2
, then the majority output is correct, and if i > n -c, corrupt P 1 is caught in one of the check circuits.

Therefore, the cheating probability is,

P = max i n-i c n c = 1 n c max i n -i c
The above is maximum for i = n -c 2 . Thus,

P = n+c 2 c n c = n+c 2 ! c! n-c 2 ! (n -c)!c! n! = n+c 2 ! n-c 2 ! (n -c)! n! By Stirling's approximation, n! ≈ √ 2πn n e n P ≈ (n + c) n+c+1 2 (n -c) n-c 2 2 c n n+ 1 2 (1)
To minimize P for a given n, we differentiate partially with respect to c and set the resulting expression to 0.

Taking logarithm of (1), we get,

log P = n + c + 1 2 log(n + c) + n -c 2 log(n -c) -c log 2 -n + 1 2 log n Now differentiating, dP dc = P 2 log n + c 4(n -c) - n -c n -c + n + c + 1 n + c
We now have,

dP dc = 0 log n + c 4(n -c) - n -c n -c + n + c + 1 n + c = 0 n+c+1 n+c ≈ 1, Therefore, we have, log n + c 4(n -c) = 0 n + c 4(n -c) = 1
This yields,

c = 3n 5
Therefore, for a given number of total circuits, n, minimum cheating probability is achieved when the number of check circuits is 3/5th of n.

Theorem 1. For a given total number of garbled circuits n, constructed and sent by P 1 in the cut-and-choose protocol, P 2 should ask 3 5 th of them to be opened, to minimize the probability of undetected cheating by P 1 .

Thus, challenging P 1 to open 3/5 of the circuits is better for P 2 than challenging half as is done in existing cut-and-choose strategies. Independent of us, the above result is also obtained in [START_REF] Shelat | Two-output secure computation with malicious adversaries[END_REF], by counting the number of bad circuits that optimizes the cheating probability. They do not derive an explicit expression for the cheating probability as we do above, which we use in the generalization to cheaper check circuits which is the subject of the next section.

Cheaper check circuits

In this section, we consider the more general case of cheaper check circuits. A given number of communication bits does not fix the total number of circuits when the costs of a check circuit and an evaluation circuit are different. Consider the protocol of [START_REF] Goyal | Efficient two party and multi party computation against covert adversaries[END_REF], i.e applying the ideas of [START_REF] Goyal | Efficient two party and multi party computation against covert adversaries[END_REF] to the protocol of the previous section. In this protocol, P 1 uses a short seed and a pseudorandom generator to generate the required randomness for construction of the garbled circuits. A hash of the n garbled circuits are sent to P 2 . P 2 asks for a random half of them to be opened, and P 1 sends only the short seeds of the selected half. P 2 verifies that they are constructed correctly. The evaluation circuits are now sent by P 1 . The cost of a check circuit is therefore, less than the cost of an evaluation circuit; once the hashes of all n circuits are sent, only a short seed is communicated in case of a check circuit, whereas the whole garbled circuit is the communication cost for an evaluation circuit. In this case, we analyze the optimal number of check circuits for minimum cheating probability. In the previous case when the costs of a check circuit and an evaluation circuit are the same, fixing the communication bits k, also fixes the total number of circuits n. We now study the general case when a check circuit is cheaper than an evaluation circuit. Given a constant amount of communication bits, we minimize the cheating probability. Our analysis yields the total number of circuits to be constructed and the number of circuits to be challenged so as to achieve minimum probability of undetected cheating in a given amount of communication bandwidth.

Let k be the number of bits of communication allowed. Let c be the number of check circuits, e the number of evaluation circuits and n the total number of circuits.

Then,

c • Cost check + e • Cost eval = k
Let q be the ratio of the cost of check circuits to the cost of evaluation circuits.

cq + e = s where,

q = Cost check Cost eval , s = k Cost eval
Using n = c + e and e = s -cq in the cheating probability, we have,

P ≈ (n + c) n+c+1 2 (n -c) n-c 2 2 c n n+ 1 2 = (2c + e) 2c+e+1 2 e e 2 2 c (e + c) e+c+ 1 2 = (2c + s -cq) 2c+s-cq+1 2 (s -cq) s-cq 2 2 c (s -cq + c) s-cq+c+ 1 2 (2)
We now differentiate with respect to c and equate the resulting expression to zero.

Taking logarithm of (2) we get,

log P = (2 -q)c + s + 1 2 log ((2 -q)c + s)+ s -cq 2 log (s -cq)-c log 2-c(1 -q) + s + 1 2 log (c(1 -q) + s)
Differentiating with respect to c we have,

1 P dP dc = 2 -q 2 log ((2 -q)c + s) - q 2 log(s -qc) -log 2 -(1 -q) log ((1 -q)c + s)
Now setting the derivative to zero,

dP dc = 0 log ((2 -q)c + s) 2-q 2 2(s -qc) q 2 ((1 -q)c + s) 1-q = 0 ((2 -q)c + s) 2-q 2 2(s -qc) q 2 ((1 -q)c + s) 1-q = 1
This implies,

((2 -q)c + s) 2-q 2 = 2(s -qc) q 2 ((1 -q)c + s) 1-q (3)
(2c + e) 1-q 2 = 2 e q 2 (c + e) 1-q (n + c) 1-q 2 = 2 (n -c) q 2 n 1-q 1 + c n 2-q = 4 1 - c n q (4)
Let r be the fraction of the circuits which are check circuits. i.e r = c n Using this in (4) yields,

(1 + r) 2-q = 4 (1 -r) q (1 + r) 2 = 4 1 -r 2 q (5)
Given q, the ratio of costs, we can solve the above equation for r.

The total number of circuits to be sent n is then given by,

n = k (1 -r) Cost eval + r Cost check
Given that we are allowed a constant k bits of communication, the total number of circuits, and the number of check circuits can be set as in the above analysis to minimize the cheating probability by P 1 . If the cost of check circuit is the same as the cost of the evaluation circuit, i.e when,

Cost check = Cost eval , q = 1 Setting q = 1 in equation ( 5) yields, r = 3 5 and this agrees with our earlier conclusion when the costs are same.

Theorem 2. Let q be the ratio of the communication cost of a check circuit to the cost of an evaluation circuit in a two party cut-and-choose protocol, and k, a constant amount of communication bits allowed. Then, probability of cheating by P 1 is minimized if the ratio of the number of check circuits to the number of evaluation circuits, r is as given by, (1 + r) 2 = 4 1 -r 2 q , and the total number

of circuits, n = k (1 -r) Cost eval + r Cost check .
In this section, we minimize the number of communication bits for a given cheating probability. We show how to achieve a given negligible probability of undetected cheating in minimum communication. We show that, for our choice of parameters, the communication complexity of existing cut-and-choose protocols can be improved. The communication complexity of existing protocols are stated in the following theorems.

Theorem 3. ( [START_REF] David | Revisiting the efficiency of malicious two party computation[END_REF]) Let n be the number of circuits, and g the number of gates in the circuit. The protocol of [START_REF] David | Revisiting the efficiency of malicious two party computation[END_REF] is secure in the malicious model with inverse exponential (in n) probability of undetected cheating. The communication complexity is O(ng).

Theorem 4. ( [START_REF] Mohassel | Efficiency tradeoffs for malicious two party computation[END_REF]) The equality-checker protocol of [START_REF] Mohassel | Efficiency tradeoffs for malicious two party computation[END_REF] is secure in the malicious model with probability of undetected cheating . If g is the number of gates the circuit, and I the number of input bits, the communication complexity of the scheme is O(ln 1 g + ln 1 2 I).

Minimize Communication Complexity

We now formulate the problem as minimizing the communication complexity which is a function of two variables, given a cheating probability. Given a cheating probability p, for what relation between the check circuits and the total number of circuits, is p achieved in minimum number of communication bits? Minimize the function,

f (c, n) = c • Cost check + (n -c) • Cost eval That is, minimize, k = c + (n -c)Q subject to the constraint that, p = 1 2 c (n + c) n+c+1 2 (n -c) n-c 2 n n+ 1 2
where,

Q = Cost eval
Cost check Since the constraint equation is exponential, we go back to the expression of cheating probability and try to get a more friendly approximation.

p ≈ n+c 2 c n c
We know that,

x y ≥ x y y x y ≤ x y y! ≤ x y 2 y-1 Therefore, p ≥ ( n+c 2c ) c n c 2 c-1 = n + c cn c 2 c-1 2 c p ≥ 1 2 1 c + 1 n c (2p) 1 c ≥ 1 c + 1 n 1 n ≤ (2p) 1 c - 1 c n ≥ c c (2p) 1 c -1
Since we do not get a closed form for c in terms of n and p, we investigate, of what order c should be in, so that k is minimized while keeping p negligible.

Let n -c = n , and, = log log n log n For this value of , n = log n, and n -n = c = n -log n.

For the case when check circuits are cheap as opposed to evaluation circuits, the total communication is dominated by the number of evaluation circuits. For the above value of c, p is still negligible. We now show that the cheating probability p is negligible when c = n -log n.

p = 1 2 c (n + c) n+c+1 2 (n -c) n-c 2 n n+ 1 2 For c = n -log n, p = 1 2 n-log n (2n -log n) 2n-log n+1 2 (log n) log n 2 n n+ 1 2
For large n, and c = n -n , p is still negligible. That is, p ≈ 1

n 1 2 + log n 2 .
We observe that, the cheating probability p remains negligible, for = log log n log n , giving communication cost dominated by the cost of evaluation circuits. Therefore, we get constant factor improvement on the communication complexity by the new choice of parameters; by choosing the number of check circuits to be, c = n-log n. Thus, the communication cost of existing cut-and-choose protocols can be improved, while still retaining the security guarantees, i.e. keeping the cheating probability negligible. The communication complexity and the cheating probability achieved by the above optimal parameters in a cut-and-choose protocol are stated in the following theorem.

Theorem 5. The number of check circuits to achieve near optimal communication cost is given by c = n -log n, where n is the total number of circuits. The communication complexity is dominated by O(C log n), and the probability of undetected cheating is p ≈ 1

n 1 2 + log n 2
, where C is the communication cost of an evaluation circuit.

The improvement by using the above parameters in the setting of cheaper check circuits [START_REF] Goyal | Efficient two party and multi party computation against covert adversaries[END_REF], is discussed in the following section. Using the above choice of parameters for , the number of check circuits c and the technique of [START_REF] Goyal | Efficient two party and multi party computation against covert adversaries[END_REF] as applied to cut-and-choose protocol for general secure two party computation, we get an improvement in the communication complexity in concrete terms compared to the protocols of [START_REF] Mohassel | Efficiency tradeoffs for malicious two party computation[END_REF], [START_REF] David | Revisiting the efficiency of malicious two party computation[END_REF], [START_REF] Lindell | Secure two-party computation via cut-andchoose oblivious transfer[END_REF].

Comparison of communication cost

In the previous section, we analyzed in detail the parameter values such as the number of circuits to be challenged and arrived at optimal values to achieve minimum communication complexity. We now show how the use of these optimal parameters in existing protocols significantly improve the communication complexity. In particular, we sketch how our optimal parameters along with the technique of [START_REF] Goyal | Efficient two party and multi party computation against covert adversaries[END_REF], improve the efficiency of existing cut-and-choose constructions. Informally, in the setting of [START_REF] Goyal | Efficient two party and multi party computation against covert adversaries[END_REF], P 1 sends only a hash of the check circuits, and the entire garbled circuit is sent only for an evaluation circuit. Check circuits are therefore cheaper than evaluation circuits. Let the total number of circuits be n. From the analysis of Section 4.1, we choose the number of evaluation circuits to be optimal for minimum communication cost which is log n. We summarize our results below.

Let the size of a garbled circuit be, |GC| = 4g|E|, where |E| is the size of the ciphertext of the encryption scheme, g the number of gates in the circuit and I the input size. Let |E| also be the output size of the commitment scheme. If t is the number of garbled circuits in [START_REF] Mohassel | Efficiency tradeoffs for malicious two party computation[END_REF], the number of bits communicated is t|GC| + t 2 I|E| = 4tg|E| + t 2 I|E| (Theorem 4). The same protocol, by using the parameters of our analysis communicates, roughly, 4g|E| log n + (log n) 2 I|E| bits, where n is the total number of circuits (Theorem 5). Consider a circuit with 32 gates and input wires, g = I = 32. The cheating probability and the communication complexity achieved by [START_REF] Mohassel | Efficiency tradeoffs for malicious two party computation[END_REF] and by incorporating the optimal choice from our analysis in [START_REF] Mohassel | Efficiency tradeoffs for malicious two party computation[END_REF] is shown in the table below.

For the purpose of our comparison, we fix the cheating probability. Setting the number of circuits t and n, in the two variants such that, the cheating probability is the same, say, 2 -50 , we get t = 196 and log n = 10. Substituting the values of t and n in the number of communication bits shown above, we see that the communication bits using our optimal parameters is around 20 times less than the communication bits of [START_REF] Mohassel | Efficiency tradeoffs for malicious two party computation[END_REF]. It is also important to note that this factor of improvement increases as the number of gates and input wires in the circuit increase. We now consider the protocol of [START_REF] David | Revisiting the efficiency of malicious two party computation[END_REF]. If t is the number of garbled circuits in [START_REF] David | Revisiting the efficiency of malicious two party computation[END_REF], the number of bits communicated is roughly 4tg|E|+2tI|E|+tg+tI|E|. The number of bits communicated by using our techniques is, roughly, 4g|E| log n + 3 log nI|E| (Theorem 5), where n is the total number of circuits. If we consider a circuit with 32 gates and input wires, g = I = 32, and set the parameters t and n such that the cheating probability is the same, then, t = log n 2 + (log n) 2 2 . Now, for a cheating probability of 2 -50 , we get t = 50 and log n = 10. Substituting the values of t and n in the number of communication bits shown above, we see that the communication bits using our optimal parameters is a factor of 9 less than the scheme of [START_REF] David | Revisiting the efficiency of malicious two party computation[END_REF]. More recently, in [START_REF] Lindell | Secure two-party computation via cut-andchoose oblivious transfer[END_REF], Lindell and Pinkas presented a protocol using the cutand-choose methodology relying on DDH assumption, and significantly improved the efficiency. We give the improvement in communication cost by using optimal parameters in [START_REF] Lindell | Secure two-party computation via cut-andchoose oblivious transfer[END_REF]. The communication complexity of [START_REF] Lindell | Secure two-party computation via cut-andchoose oblivious transfer[END_REF] is the exchange of 5tI +14I +7t+5 group elements and t copies of the garbled circuit. The cheating probability is 1/2 t/4 . The communication cost is dominated by the garbled circuits. Using the techniques in this paper, the communication cost of sending the garbled circuits is 4 log ng|E|, for a cheating probability of 1

n 1 2 + log n 2 .
To achieve = 2 -50 , and solve the quadratic equation to get log n = 10. This gives a factor of 20 improvement in the communication cost. Thus, for the same cheating probability, our techniques lead to a factor of 20 less communication between the parties in the protocol of [START_REF] Lindell | Secure two-party computation via cut-andchoose oblivious transfer[END_REF]. We also remark that the increase in computational complexity is feasible. log n = 10 ⇒ n = 2 10 implies that the total number of GC's the parties need is 1024.

Conclusion

In this paper we gave an analysis for optimal parameters in cut-and-choose protocols to achieve: (a) minimum probability of undetected cheating for samecost circuits and cheaper check circuits, and (b) minimum communication bits in which a given cheating probability can be achieved. It would be interesting from a practical point of view, to carry out such optimization as part of an actual implementation of a specific protocol.

Table 1 .

 1 This paper 128|E| log n + 32(log n) 2 |E| 1/n

	Scheme	Communication Complexity Cheating Probability
	[7]	128t|E| + 32t 2 |E|	2. (1/2) t/4
			1 2 + log n 2

Table 2 .

 2 the same cheating probability, say 2 -50 we set 1/2 t/4 = 2 -50 and compute the number of GC's required as t = 200. We now set

	Scheme	Cheating Probability
	[6]	1/2 t/4
	This paper 1/n	1 2 + log n 2
					1
			n	1 2	+	log n 2