James Heather
email: j.heather@surrey.ac.uk

Chris Culnane
email: c.culnane@surrey.ac.uk

Steve Schneider
email: s.schneider@surrey.ac.uk

Sriramkrishnan Srinivasan

Zhe Xia
email: xiazhe@whut.edu.cn

Solving the Discrete Logarithm Problem for Packing Candidate Preferences

Ranked elections are used in many places across the world, and a number of end-to-end verifiable voting systems have been proposed to handle these elections recently. One example is the vVote system designed for the Victorian State Election, Australia. In this system, many voters will give a full ranking of up to 38 candidates. The easiest way to do this is to ask each voter to reorder ciphertexts representing the different candidates, so that the ciphertext ordering represents the candidate ranking. But this requires sending 38 ciphertexts per voter through the mixnets, which will take a long time. In this paper, we explore how to "pack" multiple candidate preferences into a single ciphertext, so that these preferences can be represented in the least number of ciphertexts possible, while maintaining efficient decryption. Both the packing and the unpacking procedure are performed publicly: we still provide 38 ciphertexts, but they are combined appropriately before they enter the mixnets, and after decryption, a meet-in-the-middle algorithm can be used to recover the full candidate preferences despite the discrete logarithm problem.

Introduction

Ranked elections are currently used in various elections across the world. For example, they can be found in some local government elections in the US, Scotland, Northern Ireland, New Zealand and Malta. Also, they are used to elect the lower house of parliament in some territories in Australia. Recently, several end-to-end verifiable (e2e) voting systems have been proposed to handle ranked elections. One example is the vVote system [START_REF] Burton | Using Prêt à Voter in the Victorian State elections[END_REF], [START_REF] Burton | A supervised verifiable voting protocol for the Victorian Electoral Commission[END_REF], which is designed for the Victorian State Election, Australia. In this election, there are around 10 parties and up to 38 candidates. The ballot form consists of two parts: the Above-The-Line (ATL) part lists the parties and the Below-The-Line (BTL) part lists the candidates. The voter can cast her vote using either the ATL part or the BTL part. If a voter chooses to use the ATL part, she simply selects a single party and her vote will be interpreted according to this party's pre-published candidate ranking. If this voter does not agree on any pre-published candidate ranking, she can cast her vote by expressing a full ranking of the candidates in the BTL part. After all votes are received, the election result will be tallied using the Single Transferable Vote (STV) method. According to the historical data, among the 430,000 voters in that election, about 95% of them will cast ATL votes and the others will cast BTL votes. To design an e2e voting solution for the vVote system, both situations need to be considered. In theory, the ATL votes can be tallied simply using the homomorphic property [START_REF] Cramer | Multiauthority secret-ballot elections with linear work[END_REF], [START_REF] Cramer | A secure and optimally efficient multi-authority election scheme[END_REF]. However, since the BTL vote contains a full ranking of a very large number of candidates, how to tally these votes in an efficient manner is not so straightforward, and this has been overlooked in many existing schemes.

Design decisions in the vVote system

The vVote system [START_REF] Burton | Using Prêt à Voter in the Victorian State elections[END_REF], [START_REF] Burton | A supervised verifiable voting protocol for the Victorian Electoral Commission[END_REF] is not designed as some theoretical concept, but it aims to be used in the real elections in the State of Victoria, Australia. Hence not only security issues but also efficiency and usability issues have been considered. Here, we review some of the design decisions in the vVote system and briefly explain why they have been made.

-Prêt à Voter style ballot form: the voters will cast their votes using the Prêt à Voter [START_REF] Chaum | A practical voterverifiable election scheme[END_REF], [START_REF] Peter | Prêt à Voter with re-encryption mixes[END_REF], [START_REF] Peter | Prêt à Voter: a Voter-Verifiable Voting System[END_REF] style ballot form. The main reason for this design decision is that in Prêt à Voter, the vote casting and the ballot auditing are nicely separated, and the ballots can be audited without the vote choices being given. Compared with some other e2e schemes, e.g. the Benaloh scheme [START_REF] Benaloh | Towards simple verifiable elections[END_REF], Helios [START_REF] Adida | Helios: web-based open-audit voting[END_REF] and Wombat [START_REF] Wombat | [END_REF], in which voters need to fill in their choices before deciding whether to audit the ballots or to cast them, the Prêt à Voter approach is more appropriate in this case because the voter will only need to give a full ranking of 38 candidates once. -Italian attack: if the election consists of a large number of candidates, a very large number of possible candidate rankings exist. Adversaries can force voters to cast their votes using specific orderings, and check whether ballots with these unique orderings appear among the cast ballots. This has been referred to as the Italian attack in the literature. Recently, existing techniques [START_REF] Teague | Coercion-resistant tallying for STV voting[END_REF], [START_REF] Benaloh | Shufflesum: coercion-resistant verifiable tallying for STV voting[END_REF] have been introduced to solve the Italian attack. However, these techniques are computationally expensive and are not practical to be used in large scale elections. Hence, some compromise needs to be made between security and efficiency: the vVote system has decided not to address the Italian attack. -Mixnets vs. homomorphic encryption in e2e voting schemes, the vote tally phase is normally designed either using mixnets [START_REF] Sako | Receipt-free mix-type voting scheme[END_REF], [START_REF] Neff | A verifiable secret shuffle and its application to e-voting[END_REF], [START_REF] Furukawa | An efficient scheme for proving a shuffle[END_REF] or homomorphic encryption [START_REF] Benaloh | Secret sharing homomorphisms: keeping shares of a secret secret[END_REF], [START_REF] Cramer | A secure and optimally efficient multi-authority election scheme[END_REF], [START_REF] Baudron | Practical multi-candidate election system[END_REF]. However, when the election is tallied using the STV method, votes may need to be transferred during the vote tally phase. Thus, each vote has to be kept separated from the other ones. To hide the voter-vote relationships, mixnets are used to shuffle the received votes.

-ElGamal encryption vs. Paillier encryption ElGamal [START_REF] Elgamal | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF] has been selected in the system design. The main reason for this design decision is that compared with Paillier [START_REF] Paillier | Public-key cryptosystems based on discrete logarithms residues[END_REF], ElGamal is not only more computationally efficient but also easier to implement. For example, in order to achieve the 128-bit security level 3 , 4096-bit p and 256-bit q are normally used in ElGamal, while in Paillier, the size of n is normally chosen to be 4096 bits. Therefore, in ElGamal and Paillier, the size of exponentiation is 256 bits and 4096 bits respectively, and the size of modulus is 4096 bits and 8192 bits respectively. Therefore, when using ElGamal, the re-encryption computation in the shuffle will be several dozen times quicker than using Paillier.

Moreover, the implementation of distributed key generation and threshold decryption in ElGamal is much more straightforward than those in Paillier.

Our contribution

Based on the above design decisions, the BTL vote will be handled using the Prêt à Voter style ballot form. The "onions" in the ballot form are encrypted using ElGamal encryption. The received votes are shuffled using mixnets in the vote tally phase. However, if the Prêt à Voter scheme is used in ranked elections, the candidate ordering on the ballot form needs to be randomly permuted rather than just be cyclicly shifted. Otherwise, if the adversaries know who is the voter's most/least preferred candidate, they can find out the rest of this voter's ranking just by accessing her receipt. A simple method to design the randomly permuted candidate ordering is to assign a ciphertext next to each candidate. The voter's ranking will be used to reorder these ciphertexts (this is demonstrated in Figure 1). But this means that for each ballot, a 38-ciphertext tuple will be inserted into the mixnets, and after the shuffle, each of the ciphertext needs to be decrypted.

Obviously, this will take a long time. 3 Considering that the encrypted votes will be published on the web bulletin board. Some people argue that 128-bit security level is not enough since the votes may need to be protected far into the future. Here, the 128-bit security level is only used as an example.

If multiple candidate references can be packed into one ciphertext before the shuffle, fewer ciphertexts will be sent to the mixnets, and fewer ciphertexts need to be decrypted after the shuffle. To make this idea work, we need to use the additive homomorphic property when packing the ciphertexts. This requires us to use the exponential ElGamal encryption. However, because of the discrete logarithm problem, there does not exist an efficient algorithm to retrieve the voter's rankings after the ciphertext is decrypted.

In this paper, we investigate how to pack the sequence of 38 ciphertexts into the least number of ciphertexts possible, so that they can be mixed and decrypted more efficiently. We also introduce a meet-in-the-middle algorithm that enables the full candidate preferences to be recovered despite the discrete logarithm problem. Note that although our technique is developed using the vVote system as an example, it is applicable to many other ranked elections with a large number of candidates.

Structure of the paper

In Section 2, we briefly review the meet-in-the-middle techniques, especially the Baby-Step-Giant-Step algorithm. This is followed by describing the system parameters in Section 3. Our method to recover the candidate preferences despite the discrete logarithm problem will be introduced in Section 4. We then provide some discussions in Section 5 before concluding in Section 6.

Meet-in-the-middle Review

In the literature, many meet-in-the-middle methods have been introduced. A common property of these methods is that trade-off can be made between time and memory. The benefit is that the search time can be dramatically reduced at the cost of extra storage. For example, because of the meet-in-the-middle attack, double DES is not more secure than the standard DES although its keysize is doubled [START_REF] Diffie | Exhaustive cryptanalysis of the nbs data encryption standard[END_REF]. Triple DES with two keys is also unable to improve security over the standard DES when considering the chosen plaintext attack [START_REF] Merkle | On the security of multiple encryption[END_REF].

Another famous example of the meet-in-the-middle method is Shank's Baby-Step-Giant-Step (BSGS) algorithm, which is used to solve the discrete logarithm problem. Since it shares some similarities with our proposed technique, we briefly review this algorithm here. In BSGS, the discrete logarithm x = log g y is represented as follows:

x = x α • γ + x β where 0 ≤ x α , x β < γ
The value γ is chosen to be the size of the square root of the group order ⌈ √ |G|⌉. This ensures that the value x will span across the entire group. Now, if we denote T = g x = g xα•γ+x β , the above equation can be re-written as follows:

T • (g -γ ) xα = g x β
Thus, in order to find x ∈ G, we need to find a pair (x α , x β ) that satisfies the above equation. To achieve this, we first build a lookup table that stores all possible mappings from g x β to x β , where 0 ≤ x β < γ. Note that the size of this table is √ |G|. Then, we can try all possible x α values in the range 0 ≤ x α < γ, until we find a hit in the lookup table that satisfies T • (g -γ ) xα = g x β . If we find such a pair, x can be calculated as x = x α • γ + x β .

When using the brute force search to solve the discrete logarithm problem, the computational cost is |G|. By using the Baby-Step-Giant-Step algorithm, the cost can be reduced to √ |G|, and the extra cost is to build a lookup table of size √ |G|.

System Parameters

All these parameters are selected publicly before the election.

Crypto parameters: Let p, q be two large primes such that q|p -1. We denote G q as the subgroup of Z * p of order q. Let g be a generator of G q . The public key pk is (p, q, g, y), where y = g x (mod p) and the secret key x is threshold shared among a number of parties [START_REF] Torben | A threshold cryptosystem without a trusted party[END_REF], [START_REF] Gennaro | Secure distributed key generation for discrete-log based cryptosystems[END_REF]. In order to achieve the 128-bit security level, p and q are suggested to be chosen as 4096 and 256 bits respectively 4 . Candidate parameters: Following the idea in [START_REF] Cramer | Multiauthority secret-ballot elections with linear work[END_REF], [START_REF] Baudron | Practical multi-candidate election system[END_REF], we choose a value M which is larger than the number of candidates. Hence in our case, if there are n = 38 candidates, M can be chosen as n + 1 = 39. After the candidates are sorted into the canonical order, the first candidate will be assigned value M 0 (mod q), the second candidate M 1 (mod q), and so on. If we generalise this, the i-th candidate will be assigned the value M i-1 (mod q). Encryption The exponential ElGamal cipher [START_REF] Elgamal | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF] will be used for encryption thanks to its additive homomorphic property, i.e. for two messages m 1 , m 2 ∈ Z q , their ciphertexts can be denoted as E pk (m 1 ) = (g m1 y r1 , g r1 ), E pk (m 2 ) = (g m2 y r2 , g r2 ) respectively 5 , and we have the property that E pk (m 1 )•E pk (m 2 ) = E pk (m 1 + m 2 (mod q)). For the candidates in the canonical order, the ciphertext assigned to the first candidate is C 1 = E pk (M 0 ), the ciphertext assigned to the second candidate is C 2 = E pk (M 1 ), and so on. If we generalise this, the ciphertext assigned for the i-th candidate is

C i = E pk (M i-1 ).

Ciphertext Packing

To make the explanation clear, we describe the "ciphertext packing" technique step by step, where each step improves its previous step.

Packing all 38 ciphertexts into 1 ciphertext

Theoretically, it is possible to pack all the 38 ciphertexts as well as the voter's rankings into a single ciphertext. For example, we first sort the ciphertexts of a received vote based on its rankings, and the result can be represented as {C π(1) , C π(2) , . . . , C π(38) }, where π(i) denotes the i-th candidate in the voter's rankings. Then the set of ciphertexts can be packed as

C = n ∏ i=1 C π(i) i
When the above ciphertext is decrypted, we will get the plaintext as g

∑ n i=1 i•M π(i)-1
. However, because of the discrete logarithm problem, there is no efficient method to retrieve

∑ n i=1 i • M π(i)-1 (mod q) from the decrypted plaintext. One method is to build a lookup table to store all the possible mappings from g ρ to ρ. In our case, the 38 candidates can be ranked in any order. Thus, there will be n! = 38! ≈ 2 148 possible ρ values. Obviously, it is not feasible to build such a lookup table in practice.

Example 1. Suppose there are 5 candidates, and the voter's ranking is ⟨4, 5, 2, 1, 3⟩ (so that π(1) = 4, π(2) = 5 and so on). Then the packing becomes

E pk (M 3 ) 1 • E pk (M 4 ) 2 • E pk (M 1 ) 3 • E pk (M 0 ) 4 • E pk (M 2 ) 5 = E pk (1 • M 3 + 2 • M 4 + 3 • M 1 + 4 • M 0 + 5 • M 2 )

Packing every α ciphertexts into 1 ciphertext

Alternatively, once we have the ciphertext list {C π(1) , C π(2) , . . . , C π(38) } sorted according to the voter's ranking, starting from the first ciphertext, we can make every α ciphertexts as a group

{(C π(1) , C π(2) , . . . , C π(α) ), (C π(α+1) , C π(α+2) , . . . , C π(2α) ), . . .}
For each group of α ciphertexts, we treat their rankings as values from 1 to α, and we pack these α ciphertexts into one as

C j = α ∏ i=1 C π(jα+i) i where j = 0, 1, . . . , ⌈ n α ⌉ -1. When the ciphertext C j is decrypted, the plain- text is g ∑ α i=1 i•M π(jα+i)-1
. Similarly, we need to build a lookup table to retrieve ∑ α i=1 i • M π(jα+i)-1 (mod q) from the decrypted plaintext. In this case, the size of the lookup table is n!/(n -α)! which is smaller than n!. Hence by selecting different value α, we can adjust not only the packing ratio (how many ciphertexts to be packed into one) but also the size of the lookup table: to increase the value α, both the packing ratio and the size of the lookup table increase, and the reverse is true as well. For example, if there are 38 candidates and α = 6, all 38 ciphertexts in a ballot can be packed into ⌈ 38 6 ⌉ = 7 ciphertexts, and the size of the lookup table will be 38!/(38 -6)! ≈ 2 31 . Since the lookup table can be generated in advance (e.g. before the election) and it only needs to be generated once, the construction of such a lookup table is within the computational capacity of modern computers.

Example 2. Suppose there are 6 candidates and α = 3. The voter's ranking is ⟨4, 5, 2, 1, 3, 6⟩. The packing becomes

⟨(E pk (M 3 ) 1 • E pk (M 4 ) 2 • E pk (M 1 ) 3 ), (E pk (M 0 ) 1 • E pk (M 2 ) 2 • E pk (M 5 ) 3 )⟩ = ⟨E pk (1 • M 3 + 2 • M 4 + 3 • M 1 ), E pk (1 • M 0 + 2 • M 2 + 3 • M 5 )⟩

Packing every α + β ciphertexts into 1 ciphertext

Now, we improve the above packing method a step further: we show how the packing ratio can be increased without increasing the size of the lookup table. Similar to the existing meet-in-the-middle methods, our search method is also a trade-off between time and memory. Suppose the ciphertext list {C π(1) , C π(2) , . . . , C π(38) } has been sorted according to the voter's ranking. Starting from the first ciphertext, we make every α + β ciphertexts as a group

{(C π(1) , . . . , C π(α) , C π(α+1) , . . . , C π(α+β) ), (C π(α+β+1) , . . . , C π(2α+β) , C π(2α+β+1) , . . . , C π(2α+2β) ) . . .}
For each group of α + β ciphertexts, we treat their rankings as values from 1 to α + β, and we can pack these α + β ciphertexts into one ciphertext as

C j = α+β ∏ i=1 C π(j(α+β)+i) i = α ∏ s=1 C π(j(α+β)+s) s • α+β ∏ t=α+1 C π(j(α+β)+t) t
where j = 0, 1, . . . , ⌈ n α+β ⌉-1. When the ciphertext C j is decrypted, the plaintext is

g ∑ α+β i=1 i•M π(j(α+β)+i)-1 = g ∑ α s=1 s•M π(j(α+β)+s)-1 • g ∑ α+β t=α+1 t•M π(j(α+β)+t)-1
where we have

α ∑ s=1 s•M π(j(α+β)+s)-1 = α+β ∑ i=1 i•M π(j(α+β)+i)-1 - α+β ∑ t=α+1 t•M π(j(α+β)+t)-1 (mod q)
Now we build up two lookup tables: the α-table stores all the possible mappings from g ρ to ρ, where ρ is in the form:

ρ = α ∑ i=1 i • M π(i)-1 (mod q)
and the β-table stores all the possible mappings from g δ to δ, where δ is in the form:

δ = - α+β ∑ j=α+1 j • M π(j)-1 (mod q)
Hence to retrieve the exponent value from the decrypted plaintext

m = g ∑ α+β i=1 i•M π(j(α+β)+i)-1
we can try m • g δ for all the possible δ values in the β- 21 . And both tables can be generated in advance before the election. After the shuffle, when decrypting a ciphertext and extracting its exponent, we need to try m • g δ roughly for half of the possible values in the β-table until the result is in the α-table. Hence we need to repeat the test roughly 2 20 times.

Discussion

Shrink the α-table

When p and q are chosen as 4096 bit and 256 bit respectively, for both the α-table and β-table, each row consists of a 256-bit value and a 4096-bit value. Hence the data size for a row is 544 bytes, which is roughly 0.5 KB. If α = 6 and β = 4, the α-table contains 2 31 rows and its total size is roughly 1 TB. The β-table contains 2 21 rows where its total size is roughly 1 GB.

Note that in the β-table, we will use the g δ value in the calculation m • g δ . Thus we have to keep this value intact. However, we can shrink the g ρ value in the α-table by keeping its last κ bits. The only requirement is that the remaining κ bits of each value is still unique. To check whether m • g δ is in the α-table, we only need to check whether its last κ bits are in the α-table. In practice, we can shrink the g ρ value in the α-table by keeping removing its leading bit when its remaining bits are still unique across the table. Since the size of the α-table is 2 31 , according to the birthday paradox, if κ = 62, there is a 50% chance that every remaining value is unique. In this case, the data size for a row is 40 bytes, and the data size for the entire α-table can shrunk to 80 GB.

Shrink the β-table

Although we mentioned earlier that each value in the β-table has to be kept intact, we can shrink the β-table by reducing the number of rows rather than reducing the size of each row. This can be achieved by applying the Steinhaus-Johnson-Trotter (SJT) algorithm [START_REF] Knuth | The Art of Computer Programming[END_REF] as follows: denote ∆ i,j,l = g i * M l +j * M l+1 for i, j = -β, . . . , 0, . . . , β and l = 0, 1, . . . , n -1. The mappings between (i, j, l) and ∆ i,j,l are stored in the β-table. By multiplying with a single element ∆ i,j,l of this table, we can execute an adjacent transposition in the exponent. Thus, starting from any g δ , we can generate the next possible sequence using a single multiplication. Hence the running time of this approach remains the same, but the number of rows in the β-table has been reduced from n!/(n -β!) to (2β) 2 * n. In case where there are 38 candidates and β = 4, the number of rows have been reduced from 2 21 to 2432 which is negligible.

What if (α + β) ̸ | n?

Previously, we deliberately ignored the case that (α + β) ̸ | n. However, this is an issue we should consider in practice. There are two methods to address this issue: one with padding and one without padding.

Method with padding

We can simply append the ciphertext list by repeating the list from the left side until it exactly divides α + β. For example, suppose the sorted ciphertext list is {C π(1) , C π(2) , . . . , C π(38) }, where α = 6 and β = 4. In this case, we treat every 10 ciphertexts as a group and pack them into one ciphertext. If we copy the first two ciphertexts and append them to the end of the list, all the groups will have exactly 10 ciphertexts. After decryption, the repeated candidate preferences can be removed. This method is very simple, and it always works if the number of candidates is larger than α + β. Next, we introduce another method without using padding.

Method without padding Denote the number of candidates n = k(α + β) + r for some integer k. We now discuss the following various situations:

-When r = α: after every (α + β) ciphertexts have been packed, there will be exactly α ciphertexts remaining, and they will be packed into a single ciphertext. After this packed ciphertext is decrypted, we can use the α-table to retrieve the exponent part of its plaintext. -When 0 < r < α: after every (α+β) ciphertexts have been packed, there will be less than α ciphertexts remaining, and they will be packed into a single ciphertext. After this packed ciphertext is decrypted, neither the α-table nor the β-table can be used to retrieve the exponent part of the plaintext. To solve this problem, we need to build another lookup table, called α ′ -table, which stores all the possible mappings from g ρ ′ to ρ ′ . And there will be ∑ α-1 i=1 n!/(n-i)! number of possible ρ ′ values. In case there are 38 candidates and α = 6, the α ′ -table will contain roughly 2 26 rows, and the size of the α ′table is roughly 2.5 GB. Note that the technique introduced in the previous section can be used to shrink the α ′ -table .  -When α < r < α + β: after every (α + β) ciphertexts have been packed, there will be more than α ciphertexts remaining, and they will be packed into a single ciphertext. After this packed ciphertext is decrypted, we need to build another lookup table, called β ′ -table, and use this table along with the α-table to retrieve the exponent part of the plaintext. The β ′ -table stores all the possible mappings from g δ ′ to δ ′ , and there will be ∑ β-1 i=1 n!/(n -i)! number of possible δ ′ values. To retrieve the exponent part of the plaintext m, we test m • g δ ′ for all the possible δ ′ values in the β ′ -table until the result is in the α-table. In case there are 38 candidates and β = 4, the β ′ -table contains roughly 2 16 rows, and the size of the β ′ -table is roughly 32 MB. Note that the SJT algorithm introduced above also can be applied here to further reduce the β ′ -table.

Constructing the tables

It is possible to construct the tables without requiring a large number of exponentiations. Here, we only informally describe how to build the α-table. The other tables can be built similarly.

Firstly, we build a temporary table of values of the form g j•M i where 0 ≤ i < n and 1 ≤ j ≤ α. Then, building the α-table requires α -1 group multiplications from these values. This removes the need for many unnecessary exponentiations. By using a recursive algorithm to build the table, the computational cost can be reduced even further: We have written a program to build the α-table in Java using a standard laptop (Intel i7 processor with 4 cores at 2.7GHz, 8 GB memory, and 64-bit Windows 7). Our assumption is that there are 38 candidates and α = 6. Our test shows that the time spent to build the table is just under 10 hours, and it costs slightly more than 3 hours to sort the table (this is a necessary step for binary search). The total size of the table is 100.8GB, and an average search in the table takes 49ms.

Related work

As described in Section 2, the BSGS algorithm is an important technique to solve the discrete logarithm problem. Our introduced method shares some similarities with BSGS. However, there are also some differences between them. Firstly, BSGS searches the entire group, while our method makes use of the structure of the plaintext and only searches a much smaller subgroup. Thus our method will be quicker when used in unpacking candidate preferences. Secondly, compared with BSGS, our method is more flexible since the sizes of the two lookup tables can be easily adjusted according to different cases.

Packing different votes in the homomorphic fashion was first introduced in [9], and our method follows this approach. Later, it was briefly mentioned in [START_REF] Cramer | A secure and optimally efficient multi-authority election scheme[END_REF] that the meet-in-the-middle trick can be used to solve the discrete logarithm problem if votes are packed homomorphicly using the exponential ElGamal encryption. However, no technical detail was given about how this can be done. Moreover, in both these works, the ciphertext packing technique was only designed for the First-Past-The-Post (FPTP) elections, while ranked elections were not considered. Our work in this paper can be considered as some extension to these two existing works.

Conclusion

In this paper, we have explored the details to "pack" multiple candidate preferences into the least number of ciphertext. The benefit is that fewer ciphertexts need to be shuffled and decrypted. After decryption, the full candidate preferences can be retrieved using a meet-in-the-middle algorithm despite the discrete logarithm problem. The vVote system was used as an example, and the parameters were carefully chosen accordingly. But the method present here is generic in nature and it has the potential to be applied in many other ranked elections with a large number of candidates.

Fig. 1 .

 1 Fig. 1. The ciphertext ranking represents the candidate ordering

1 .

 1 Set r = 1 (the group identity element) and s = α (the packing ratio), the candidate set C = {1, 2, . . . , n}, and the preference set P = {1, 2, . . . , α}.2. For each candidate i ∈ C:(a) Remove i from C and compute s = s -1.(b) For each preference j ∈ P: i. Removej from P. ii. Set r ← r • g j•M i-1 . iii. If s > 0,recursively run from step 2; otherwise: A. Output r. B. Restore r and s to values at previous recursive step. C. Add j back to P. D. Add i back to C.

  table until the result is in the α-table. In this case, suppose the particular values in the α-table and β-table are ρ ′ and δ ′ respectively, we will have m = g ρ ′ -δ ′ . Hence, ρ ′ -δ ′ (mod q) is the desired exponent value of the decrypted plaintext m. For an election with n = 38 candidates, if we use α = 6 and β = 4, we can pack every 10 ciphertexts into one ciphertext. The size of the α-table is n!/(nα)! = 38!/(38-6)! ≈ 2 31 and the size of the β-table is n!/(n-β)! = 38!/(38-4)! ≈ 2

For more information about the recommended key length by NIST and ECRYPT II, please refer to http://www.keylength.com/

In this document, we assume all arithmetic to be modulo p where applicable, unless otherwise stated.

Acknowledgement

Dr. Sriramkrishnan Srinivasan was at the University of Surrey when this work was carried out. This work was funded by the UK Engineering and Physical Sciences Research Council (EPSRC) under grant EP/G025797/1, and we are grateful to the anonymous reviewers for their valuable comments on the paper.


Saad Islam
email: saadislam@mcs.edu.pk

Mehreen Afzal
email: mehreenafzal@mcs.edu.pk

Adnan Rashdi
email: adnanrashdi@mcs.edu.pk

On the Security of LBlock against the Cube Attack and Side Channel Cube Attack

Keywords: Cube attack, Side channel cube attack, Lightweight block ciphers, LBlock

In this research, a recently proposed lightweight block cipher LBlock, not tested against the cube attack has been analyzed. 7, 8 and 9 round LBlock have been successfully attacked with complexities of O(2 10.76 ), O(2 11.11 ) and O(2 47.00 ) respectively. For the case of side channel cube attack, full version of LBlock has been attacked using a single bit leakage model with the complexity of O(2 55.00 ) cipher evaluations. For this purpose, a generic practical platform has been developed to test various stream and block ciphers against the latest cube attack.

Introduction

Cube attack has been recently introduced by Dinur and Shamir in 2009 [START_REF] Dinur | Cube attacks on tweakable black box polynomials[END_REF][START_REF] Dinur | Cube attacks on tweakable black box polynomials[END_REF]. Preliminarily cube attack has been applied successfully on stream ciphers. Several results can be found on the stream cipher Trivium [START_REF] Cannière | Trivium specifications[END_REF][START_REF] Cannière | Trivium: A stream cipher construction inspired by block cipher design principles[END_REF], one of the finalists of the estream project [START_REF]The ecrypt stream cipher project[END_REF]. Reduced versions of Trivium having 672, 735 and 767 initialization rounds have been attacked. In a similar research, Vielhaber worked on the concept named AIDA (Algebraic IV Differential Attack) and attacked One.Fivium(a variant of Trivium) [START_REF] Vielhaber | Breaking one.fivium by aida an algebraic iv differential attack[END_REF]. His other contributions include [START_REF] Vielhaber | Speeding up aida the algebraic iv differential attack by the fast reed-muller transform[END_REF][START_REF] Vielhaber | Aida vs[END_REF][START_REF] Vielhaber | Aida breaks bivium (a&b) in 1 minute dual core cpu time[END_REF][START_REF] Vielhaber | Shamir's "cube attack[END_REF]. Zhe et al. further improved results of Vielhaber on One.Fivium [START_REF] Zhe | Chosen iv algebraic attack on one.fivium[END_REF]. Other predecessors of cube attack include the work of Englund et al. who showed statistical weaknesses of Trivium up to 736 initialization rounds [START_REF] Englund | A framework for chosen iv statistical analysis of stream ciphers[END_REF] and the attack on 672 round Trivium by Fischer et al. [START_REF] Fischer | Chosen iv statistical analysis for key recovery attacks on stream ciphers[END_REF]. In 2011, Mroczkowski and Szmidt evaluated Trivium by applying the cube attack and used the concept of quadraticity tests [START_REF] Mroczkowski | Corrigendum to: The cube attack on stream cipher trivium and quadraticity tests[END_REF]. Another LFSR-based lightweight stream cipher Hitag2 has been analyzed by Sun et al. against the cube attack in 2011 [START_REF] Sun | Cube cryptanalysis of hitag2 stream cipher[END_REF]. MICKEY [START_REF] Babbage | The mickey stream ciphers[END_REF], also a finalist of the estream project has been found secure by Stefan in [START_REF] Stefan | Analysis and Implementation of ESTREAM and SHA-3 Cryptographic Algorithms[END_REF].

After successful results of cube attack on Trivium, Shamir et al. proposed the concept of Cube testers in 2009 [START_REF] Aumasson | Cube testers and key recovery attacks on reduced-round md6 and trivium[END_REF]. Cube testers are based on efficient propertytesting algorithm. They detect nonrandom behavior rather than performing key extraction. They can also attack cryptographic schemes described by nonrandom polynomials of relatively high degree. The targets of the authors in the mentioned paper are Trivium and MD6 [START_REF] Rivest | The md6 hash function a proposal to nist for sha-3[END_REF]. In 2010, Li et al. worked on cube testers on Bivium [START_REF] Li | Cube testers on bivium[END_REF]. Shamir et al. worked on Grain-128 [START_REF] Hell | A stream cipher proposal: Grain-128[END_REF] and gave results for cube testers and dynamic cube attack in [START_REF] Aumasson | Efficient fpga implementations of high-dimensional cube testers on the stream cipher grain-128[END_REF] and [START_REF] Dinur | Breaking grain-128 with dynamic cube attacks[END_REF]. Conditional differential cryptanalysis by Knellwolf et al. is a predecessor to dynamic cube attack [START_REF] Knellwolf | Conditional differential cryptanalysis of nlfsr-based cryptosystems[END_REF]. Standard cube attack finds the key by solving a system of linear equations in terms of key bits whereas the dynamic cube attack recovers the secret key by exploiting distinguishers obtained from cube testers. Recently in 2012, Shamir et al. has proposed the concept of robust cube attacks for stream ciphers in realistic scenarios and also suggested the use of generalized linearity tests instead of BLR tests [START_REF] Dinur | Applying cube attacks to stream ciphers in realistic scenarios[END_REF].

For block ciphers, Dinur and Shamir proposed the idea of side channel cube attack model in which only one bit of information is available to the attacker after each round [START_REF] Dinur | Side channel cube attacks on block ciphers[END_REF]. The time complexities for AES [START_REF] Daemen | Aes proposal: Rijndael[END_REF] and SERPENT [START_REF] Biham | Serpent: A new block cipher proposal[END_REF] are found to be O(2 38 ) and O(2 18 ) for full key recovery. Due to the exponential increase in degree after every round, the standard cube attack becomes limited to reduced versions only while the side channel attack model is applicable to the full versions and thus more practical.

Lightweight block ciphers, which provide a good trade off between security and efficiency, have attained significant attention of researchers. These ciphers are mostly used in resource-constraint environments like RFID and sensor networks. RFID technology has been used in many aspects of life, such as access control, parking management, identification, goods tracking etc. The lightweight block ciphers evaluated against the cube attack include the KATAN family [START_REF] Cannière | Katan and ktantan -a family of small and efficient hardware-oriented block ciphers[END_REF], NOEKEON [START_REF] Daemen | Nessie proposal: Noekeon. Submitted as an NESSIE Candidate Algorithm[END_REF], PRESENT [START_REF] Bogdanov | Present: An ultra-lightweight block cipher[END_REF] and Hummingbird-2 [START_REF] Engels | The hummingbird-2 lightweight authenticated encryption algorithm[END_REF] in [START_REF] Bard | Algebraic, aida/cube and side channel analysis of katan family of block ciphers[END_REF][START_REF] Mroczkowski | The algebraic cryptanalysis of the block cipher katan32 using modofied cube attack[END_REF][START_REF] Abdul-Latip | On the security of noekeon against side channel cube attacks[END_REF][START_REF] Yang | Side channel cube attack on present[END_REF][START_REF] Zhao | Improved side channel cube attacks on present[END_REF][START_REF] Fan | On the security of hummingbird-2 against side channel cube attacks[END_REF]. Mroczkowski and Szmidt have attacked the Courtois Toy Cipher CTC, designed by Courtois [START_REF] Courtois | How fast can be algebraic attacks on block ciphers?[END_REF] against the cube attack [START_REF] Mroczkowski | Cube attack on courtois toy cipher[END_REF][START_REF] Mroczkowski | The cube attack in the algebraic cryptanalysis of ctc2[END_REF]. Lightweight block ciphers which are not evaluated against the cube attack so far include LED [START_REF] Guo | The led block cipher[END_REF], EPCBC [START_REF] Yap | Epcbc -a block cipher suitable for electronic product code encryption[END_REF], PRINCE [START_REF] Borghoff | Prince a low-latency block cipher for pervasive computing applications[END_REF], Piccolo [START_REF] Shibutani | Piccolo: An ultra-lightweight blockcipher[END_REF], mCrypton [START_REF] Lim | mcrypton a lightweight block cipher for security of low-cost rfid tags and sensors[END_REF], TWIS [START_REF] Ojha | Sangeeta: Twis a lightweight block cipher[END_REF], MIBS [START_REF] Izadi | Mibs: A new lightweight block cipher[END_REF], CGEN [START_REF] Robshaw | Searching for compact algorithms: Cgen[END_REF], PRINTcipher [START_REF] Knudsen | Printcipher: A block cipher for ic-printing[END_REF], KLEIN [START_REF] Gong | Klein: A new family of lightweight block ciphers[END_REF], FOX [START_REF] Junod | Fox: a new family of block ciphers[END_REF], HIGHT [START_REF] Hong | Hight: A new block cipher suitable for low-resource device[END_REF], ICEBERG [START_REF] Standaert | Iceberg : An involutional cipher efficient for block encryption in reconfigurable hardware[END_REF], LCASE [START_REF] Tripathy | Lcase: Lightweight cellular automata-based symmetric-key encryption[END_REF], MISTY [START_REF] Matsui | New block encryption algorithm misty[END_REF], PUFFIN [START_REF] Cheng | Puffin: A novel compact block cipher targeted to embedded digital systems[END_REF], SEA [START_REF] Standaert | Sea: a scalable encryption algorithm for small embedded applications[END_REF], TEA [START_REF] Wheeler | Tea, a tiny encryption algorithm[END_REF] and CLEFIA [START_REF] Shirai | The 128-bit blockcipher clefia (extended abstract)[END_REF].

LBlock, a lightweight block cipher recently proposed in 2011 by Wu et al.

has not yet been tested against the cube attack [START_REF] Wu | Lblock: A lightweight block cipher[END_REF]. In the security evaluation of LBlock by the authors, five cryptanalysis techniques have been used. For differential cryptanalysis, there is no useful 15-round differential characteristic for LBlock. For linear cryptanalysis, it is difficult to find useful 15-round linearhulls which can be used to distinguish LBlock from a random permutation. For impossible differential cryptanalysis, attacks on 20-round LBlock has been mounted using 14-round impossible differential distinguishers. Integral attack goes up to 20 rounds and the related key attack goes up to 14 rounds of LBlock. Impossible differential attack has been improved up to 21 and 22-round LBlock in [START_REF] Liu | Impossible differential attacks on reduced-round lblock[END_REF] and [START_REF] Karako | Impossible differential cryptanalysis of reduced-round lblock[END_REF]. Minier et al. improved the related key attack to 22 rounds of LBlock [START_REF] Minier | A related key impossible differential attack against 22 rounds of the lightweight block cipher lblock[END_REF]. Liu et al. also worked on a similar concept on 22-round LBlock [START_REF] Liu | Improved related-key differential attacks on reducedround lblock[END_REF]. Biclique cryptanalysis has been performed by the authors of LBlock and new key scheduling algorithm has been proposed in [START_REF] Wang | Security on lblock against biclique cryptanalysis[END_REF].

The cube attack implementations include Paul Crowley's implementation [START_REF] Crowley | Trivium, sse2, corepy, and the "cube attack[END_REF]68] and a practical platform developed by Bo Zhu [START_REF] Zhu | A practical platform for cube-attack-like cryptanalyses[END_REF]. Zhu et al. has also created an online application which only works for Trivium and checks the cubes for linearity and generate the linear expressions [START_REF] Zhu | A practical platform for cube-attack-like cryptanalyses[END_REF]. However, the tool is not suitable to be extended for the complete cube attack on any generic structure. Cryptool 2.0 [START_REF]Cryptool 2 cryptography for everybody[END_REF] includes the cube attack block having the option for Trivium and DES only.

Our Contribution. LBlock has been evaluated against the developed tool. We are able to successfully attack 7, 8 and 9 round LBlock with complexities of just O(2 10.76 ), O(2 11.11 ) and O(2 47.00 ) cipher evaluations. Full version of LBlock has been attacked using the single bit leakage side channel cube attack model with the complexity of O(2 55.00 ). Cube attack may also be extended to further rounds by using more efficient hardware resources like super computer, the use of GPUs and the concept of distributed computing.

We have developed a graphical user interface toolkit which can load any stream or block cipher into it(as a function) and can check its resistance against the cube attack. The tool shows how may rounds of the cipher can be attacked, and it outputs the cube expressions found in a text file. The options such as cube size, number of linearity tests, output bit index, public bit size and secret bit size can be set from the GUI. The tool is user friendly and can be used easily without the help of the developers. The developed tool is capable of detecting the total number of processors in the machine and can utilize all of them for efficient execution. The tool works on both x86 and x64 systems having any windows version as it is just an executable file. The algorithm of cube attack used in our implementation can be found in [START_REF] Stefan | Analysis and Implementation of ESTREAM and SHA-3 Cryptographic Algorithms[END_REF].

Organization of the Paper. The cube attack has been explained in Section 2. An introduction of the cipher LBlock is given in Section 3 and the results of cube attack against LBlock are given in Section 4. Section 5 contains the results of side channel cube attack against LBlock. Detail of our software toolkit is given in Section 6. Section 7 concludes the article and proposes some future work.

The Cube Attack

The Cube Attack is a chosen public key attack which means chosen IV attack for stream ciphers and chosen plaintext attack for block ciphers. Ciphers can be represented as black box polynomials in terms of secret and private variables. These black boxes can be attacked by hitting them with chosen input values and obtaining the output. Definition 1. Assume some polynomial p (x 1 , ..., x n ) and a set I ⊆ {1, ...n} of indices to the variables of p Let t I be a subterm of p which is the product of the variables indexed by I. Then factorizing p by t I yields Equation 1.

p (x 1 , ..., x n ) = t I .p S(I) + q (x 1 , ..., x n ) (1)
where p S(I) is the superpoly of I in p and q is the linear combination of all terms which do not contain t I .

For detailed description of the attack, refer to [START_REF] Dinur | Cube attacks on tweakable black box polynomials[END_REF]. The attack consists of two phases, the preprocessing phase and the online phase.

Preprocessing Phase

In the Preprocessing stage of the attack, the target is to find the maximum number of linearly independent expressions in terms of key bits. These expressions are called maxterm equations. This phase is time consuming and may take several weeks. The precomputation phase consists of two parts, finding maxterms and the superpoly reconstruction.

Finding Maxterms A maxterm or a cube is a set of positions of plaintext block bits for which 2 cubesize crafted plaintexts are generated. These plaintexts P i are generated by inserting all the possible values at cube positions keeping all other positions zero or constant. Summing a fixed output bit C j for all P i 's while setting a same random key K in GF (2) is called a cube sum for key K with output bit index j. Cube sum or summing over a cube is an important terminology. Linear cubes are searched whose cube sums satisfy the linearity tests(Blum Luby Rubinfeld tests) [START_REF] Blum | Self-testing/correcting with applications to numerical problems[END_REF]. BLR test checks for the condition

f (0) ⊕ f (K 1 ) ⊕ f (K 2 ) = f (K 1 ⊕ K 2 )
where K 1 and K 2 are random keys and f is the cube sum with a certain key over a cube to be tested. The probability that f is linear for 3N tests is 1 -2 -N . If a cube satisfies all the linearity tests, it is placed in the results table with the corresponding output bit index and the reconstructed maxterm equation which is explained in the next part. For the selection of cubes, the authors have proposed a random walk process in [START_REF] Dinur | Cube attacks on tweakable black box polynomials[END_REF].

Reconstructing Maxterm Equations Reconstructing maxterm equations or the superpoly reconstruction in terms of key bits (e.g 1 ⊕ k 3 ⊕ k 4 ) is the second part of the preprocessing phase. According to Theorem 2 in [START_REF] Dinur | Cube attacks on tweakable black box polynomials[END_REF], the constant term can be easily computed by setting K = 0 and calculating the cube sum. If the sum is 1, the maxterm contains the free term 1, otherwise not. The coefficients of the key bit variables k i can be found by setting each k i to one and remaining zeros and calculating the cube sums. If the sum is different from that for K = 0, that k i will be the part of the maxterm equation. This is because if the value of a variable in a linear expression is flipped, the value of the expression is also flipped.

Online Phase

In the online phase there is an unknown set key which has to be recovered and the adversary can only tweak the plaintext bits. The target of this phase is to determine the right hand sides of the found expressions and their solution. This stage consists of two phases, forming and solving a system of linear equations.

Forming System of Linear Equations In this part, cube sums are calculated for the same cubes found in the preprocessing stage and their relevant output bit index. These sums make the right hand side of the expressions making a system of linear equations (e.g 1 ⊕ k 3 ⊕ k 4 = 0).

Solving System of Linear Equations The system of linear equations may be solved using Gaussian elimination. The number of key bits recovered is equal to the number of linearly independent relations found in the preprocessing phase. For finding further relations the time consumed by the first phase increases exponentially.

Attack Complexity The attack complexity includes two things. One is the number of iterations of the cipher carried out in the formation of system of linear equations and the other is the complexity to solve the linear relations in the online phase. Hence, the total complexity becomes O(2 d-1 n + n 2 ) where d is the degree of the cryptosystem and n is the number of secret bits. Brute force complexity of the remaining unknown key bits is also added to the total.

LBlock: A Lightweight Block Cipher

LBlock, LuBan LOCK or Lightweight BLOCK cipher has been proposed by Wu and Zhang in 2011 [START_REF] Wu | Lblock: A lightweight block cipher[END_REF]. The cipher is a good trade off between efficiency and security. The hardware implementation of LBlock requires about 1320GE on 0.18µm technology with a throughput of 200Kbps at 100KHz and its software implementation on 8-bit microcontroller requires about 3955 clock cycles to encrypt a plaintext block.

Specification of LBlock

LBlock has a Fiestel structure having block length of 64-bit, key length of 80-bit and 32 rounds see Figure 1, where concatenation of X 1 and X 0 represents the plaintext block, K 1 -K 32 are the 32 subkeys generated through a key scheduling procedure, <<< 8 sign indicates 8-bit left cyclic shift operation, ⊕ is the XOR operation, X 32 and X 33 represents the concatenated ciphertext block. The round function F contains the confusion layer having eight 4×4 S-Boxes and a diffusion layer having permutation of eight 4-bit words.

The Cube Attack on LBlock

We have applied the cube attack on LBlock having 7, 8 and 9 rounds. The machine used throughout our analysis is Dell XPS 17 Laptop, 2nd generation Intel Core i7 2.20 GHz, 8GB DDR3, NVIDIA GeForce GT 550M 1GB graphics. Extension of the attack to further rounds has been constrained by the available computational capability. However, the concept of supercomputing and GPUs can greatly reduce the simulation time. 4 and Table 5 in Appendix-A.

Results of the Online Phase

In the online phase of the attack, the set of expressions obtained in the preprocessing phase are converted into the system of linear equations by determining the right hand sides. The values have been found by setting a random test key and summing over the same cubes found in the first phase. The example equations are shown below: x26

x1 = 0, x2 = 0, 1 + x3 + x4 = 1, x4 = 0, x5 = 0, x6 = 0, x7 = 0, x8 = 1, 1 + x9 = 1, x10 = 0, 1 + x11 = 0, x12 = 0, 1 + x13 = 1, x14 = 0, 1 + x15 + x16 = 1, x16 = 1, x17 = 0, x18 = 1, 1 + x19 = 1, 1 + x20 = 1, x21 = 0, x22 = 1, x23 + x24 = 1, 1 + x24 = 0, 1 + x25 = 1, x26 = 1, 1 + x27 + x28 = 0, x28 = 0, x29 = 0, x30 = 1, 1 + x31 + x32 = 1, 1 + x32 = 0, x38 = 0, x2 + x39 = 0, x40 + x41 = 0, x41 = 1, x42 = 0, x43 = 1, 1 + x10 + x44 + x45 = 0, x45 = 1, 1 + x46 = 1, x47 = 1, x47 + x48 + x49 = 1, 1 + x22 + x49 = 1, x50 = 1, x30 + x51 = 1, 1 + x52 + x53 = 0, x53 = 1, x18 + x54 = 0, x55 = 0, 1 + x17 + x56 + x57 = 1, x57 = 1, x58 = 1,
+ x59 = 0, 1 + x60 + x61 = 0, 1 + x61 = 0, x67 = 1, 1 + x68 = 0, x69 + x70 = 0, x70 = 1, x71 = 1, x72 = 0, x71 + x73 + x74 = 1, x74 = 1, 1 + x75 = 1, x76 = 1, x76 + x77 + x78 = 1, x76 + x78 = 0, x79 = 0, x79 + x80 = 0 (2)
Solving Equations 2, 70 key bits are recovered as shown below:

x1 = 0, x2 = 0, x3 = 0, x4 = 0, x5 = 0, x6 = 0, x7 = 0, x8 = 1, x9 = 0, x10 = 0, x11 = 1, x12 = 0, x13 = 0, x14 = 0, x15 = 1, x16 = 1, x17 = 0, x18 = 1, x19 = 0, x20 = 0, x21 = 0, x22 = 1, x23 = 0, x24 = 1, x25 = 0, x26 = 1, x27 = 1, x28 = 0, x29 = 0, x30 = 1, x31 = 1, x32 = 1, x38 = 0, x39 = 0, x40 = 1, x41 = 1, x42 = 0, x43 = 1, x44 = 0, x45 = 1, x46 = 0, x47 = 1, x48 = 1, x49 = 1, x50 = 1, x51 = 0, x52 = 0, x53 = 1, x54 = 1, x55 = 0, x56 = 1, x57 = 1, x58 = 1, x59 = 1, x60 = 0, x61 = 1, x67 = 1, x68 = 1, x69 = 1, x70 = 1, x71 = 1, x72 = 0, x73 = 1, x74 = 1, x75 = 0, x76 = 1, x77 = 1, x78 = 1, x79 = 0, x80 = 0
Remaining bits x33, ..., x37, x62, ...x66 may be recovered using quadraticity tests [START_REF] Mroczkowski | Corrigendum to: The cube attack on stream cipher trivium and quadraticity tests[END_REF] or brute force search. The recovered bits can be further compared with the test key. The test key may be set to any random value. The online phase is not computationally expensive and just takes fraction of a second.

Attack Complexity

The total complexity includes the complexity of the online phase and of the brute force search. Precomputation is the one time effort and thus not included in the calculations. 66 out of 70 cubes are of size 4 having complexity equal to 66 × 2 4 = 1056. 4 out of 70 cubes are of size 5 having complexity equal to 4 × 2 5 = 128. Total becomes 1056 + 128 = 1184 iterations of LBlock. Brute force complexity for remaining 10 bits is 2 10 . So final complexity becomes 1184 + 2 10 = 2208 approximately equal to O(2 11.11 ) which is quite less. Similarly for 7-round LBlock the complexity becomes 17×2 2 +32×2 3 +18×2 4 +3×2 5 +2 10 ≈ O 2 10.76 . For 9-round LBlock the complexity is 12×2 4 +11×2 5 +10×2 6 +2 47 ≈ O 2 47.00 .

The Side Channel Cube Attack on LBlock

The side channel cube attack is a variant of the standard cube attack which is more practical in realistic scenarios. The standard cube attack is restricted on the reduced versions of the ciphers whereas the side channel cube attack is a threat in practical situations for the full versions. In this type of attack the adversary is able to get one bit of leakage information of the state after each round of an iterated block cipher. The process may be made possible via physical probing, power measurement, or any other type of side channel. However, this information is quite noisy and this problem is addressed by using error correction techniques like erasure codes [START_REF] Luby | Efficient erasure correcting codes. Information Theory[END_REF].

Results of the Preprocessing Phase

LBlock achieves complete diffusion after 8 rounds, as mentioned by the authors of LBlock [START_REF] Wu | Lblock: A lightweight block cipher[END_REF]. So, a single bit leakage after 8 th round may give maximum number of linear relations as compared to inner rounds. We have taken the MSB of the right half X R of the state after 8 th round as the leakage bit and used for our analysis. Thousands of linear relations have been found but 25 linearly independent have been extracted using Gaussian elimination technique. The results of the preprocessing phase for full version of LBlock are shown in Table 3. Time consumed for searching all possible combinations for various cube sizes is shown in Table 2 where the number of linearity tests has been set to 100. The results are for the single core execution with the multi-processing feature disabled.

Cube Attack Software Toolkit

We have developed a GUI based software tool using the MFC application in Microsoft Visual Studio 2010 Professional. There is a function named cipher which is to be replaced by any stream or block cipher to be tested. The function is capable of taking the plaintext, key and number of rounds as input and should return the ciphertext as the output. All inputs/outputs have to be in hexadecimal notation. After replacing the function, one has to start debugging and an executable file is made as the output. This executable will be able to run on any Windows version on both x86 and x64 platforms. In the GUI, we have five inputs public bit size, secret bit size, cube size, number of linearity tests and the number of rounds which can be set to any desired position. The results are compiled in a text file at the end of the simulation which include the cubes found, the output bit indexes, total simulation time in seconds and the reconstructed maxterms, see Figure 2. next comb function is responsible for randomly generating different cubes of the required size. cube function is responsible for testing the cubes for the linearity tests.

cipher function is invoked millions of times to get the required output bits for the crafted plaintexts. -Results are written in the results.txt file at the end of the simulation.

The number of rounds in the GUI represents the initialization or setup rounds in case of stream ciphers and the main rounds in case of block ciphers. Hence, the tool is generalized for both of them. The option to set number of rounds is for the variants or reduced versions of ciphers. This helps in better understanding about the resistivity of the ciphers.

The tool is intelligent to use all the available CPU cores in a system, thus decreasing the simulation time to a great extent. OpenMP (Open Multiprocessing) has been used to implement this task [START_REF]The openmp api specification for parallel programming[END_REF]. Another option has been added in the tool to work on multiple output bits on each iteration. The standard cube attack works on a single output bit model and the remaining block of is not utilized in. The concept has been explained in Figure 3. The same concept holds true for the stream ciphers and thus complete reinitialization of the cipher is not required to get each output bit. This feature increased the speed of the simulation 27 times in our experiments. The option is turned off when working on single bit leakage models. 11.11 ) and O(2 47.00 ) respectively. Full version of LBlock has been attacked using single bit side information after 8 rounds with a complexity of O(2 55 ). A software tool has been developed for the application of cube attack to any black box cipher. The tool can be easily used for testing and evaluation purposes.

Higher order tests like quadraticity tests may be implemented to recover more number of key bits where linearity tests have failed to produce the linear relations. BLR tests may be replaced by generalized linearity tests. The efficiency of the tool may be increased by the use of GPUs as their highly parallel structure makes them more effective than CPUs. The task can also be divided to a number of computers connected in a network, a concept known as distributed computing. Another solution is to use a super computer having a number of processors having multiple cores along with the powerful GPUs. Cube testers and dynamic cube attacks are the next steps after the cube attack.

Fig. 1 .

 1 Fig. 1. Encryption Procedure for LBlock

Fig. 2 .

 2 Fig. 2. Cube Attack Implementation Architecture

Fig. 3 .

 3 Fig. 3. Attacking Multiple Output Bits

Table 1 .

 1 Maxterms for 8-Round LBlock

	Maxterm	Cube Output	Maxterm	Cube	Output
	Equations Indexes Index	Equations	Indexes	Index
	x1	2,4,23,51	25	x41	2,3,4,23
	x2	1,3,51,52	11	x42	9,10,11,15
	1+x3+x4 1,2,51,52	11	x43	9,11,14,56
	x4	1,2,51,52	12	1+x10+x44+x45 11,12,14,54
	x5	6,7,19,43	1	x45	11,12,15,54
	x6	5,7,19,43	1	1+x46	2,22,23,24
	x7	5,6,19,43	1	x47	3,21,22,23
	x8	5,6,18,42	4	x47+x48+x49	3,21,22,24
	1+x9	10,11,15,54	13	1+x22+x49	2,23,24,57
	x10	11,41,55,56	1	x50	26,29,31,32	6
	1+x11	9,10,15,54	13	x30+x51	27,31,32,63	5
	x12	9,10,14,55	13	1+x52+x53	27,30,31,32	5
	1+x13 14,15,45,48	5	x53	27,29,31,62	6
	x14	6,13,33,47	10	x18+x54	5,19,20,36
	1+x15+x16 10,14,46,47	21	x55	6,17,18,19	9
	x16	13,14,47,48	23	1+x17+x56+x57 7,18,19,33	9
	x17	7,18,19,35	10	x57	7,18,19,33
	x18	6,17,19,34	9	x58	25,27,28,31
	1+x19	6,17,18,34	9	x26+x59	27,28,31,40
	1+x20 17,18,33,36	9	1+x60+x61	26,27,28,31
	x21	2,22,23,59	18	1+x61	26,27,28,31
	x22	21,23,58,59	1	x67	41,43,44,62
	x23+x24 3,21,22,58	18	1+x68	41,43,55,56
	1+x24 21,22,59,60	1	x69+x70	42,43,44,62
	1+x25 26,27,39,40	14	x70	42,43,44,63
	x26	27,37,38,57	3	x71	49,50,51,55
	1+x27+x28 25,26,39,40	14	x72	50,51,52,54
	x28	25,26,30,38	29	x71+x73+x74 22,49,50,52,54
	x29	31,32,50,51	27	x74	22,51,52,55,56
	x30	26,28,29,62	5	1+x75	42,62,63,64
	1+x31+x32 29,30,63,64	6	x76	43,61,62,63
	1+x32 27,29,30,63	6	x76+x77+x78	43,61,62,64
	x38	1,3,4,22	28	x76+x78	25,42,61,62,64
	x2+x39	3,4,23,52	25	x79	34,37,39,40
	x40+x41	2,3,4,22	28	x79+x80	31,35,37,38,40

Table 2 .

 2 Elapsed Times against the Cube Sizes for Preprocessing

	Cube Size Time in Seconds
	3	2
	4	53
	5	1667
	6	28739
	7	704582
	5.2 Attack Complexity
	10 out of 25 cubes are of size 4 having complexity = 10 × 2 4 = 160. Remaining
	15 cubes are of sizes 5, 6, 7 and 8 having complexities, 5 × 2 5 = 160, 4 × 2 6 =
	256, 3 × 2 7 = 384 and 3 × 2 8 = 768 respectively. Total becomes 160 + 160 + 256 +
	384 + 768 = 1728 iterations of LBlock. Brute force complexity for remaining
	55 bits = 2 55 . So final complexity becomes 1728 + 2 55 approximately equal to
	O(2 55.00 ).

Table 3 .

 3 Maxterms for Full LBlock using Leakage Bit after 8 th Round

	Maxterm	Cube	Maxterm	Cube
	Equations	Indexes	Equations	Indexes
	x1	3,4,21,41,54,55	x22	21,23,58,59
	x2	3,19,23,49,50,55 1+x23+x24	21,22,58,59
	1+x3+x4 1,2,19,51,52,55	1+x24	21,22,59,60
	x1+x4 3,18,23,50,51,55 x25+x26+x28	27,31,62,63,64
	x5	6,7,19,43	x38	1,3,4,18,22,41,55
	x6	5,7,19,43	1+x38+x39 1,2,4,23,41,52,55,56
	x7	5,6,19,43	1+x40+x41 1,2,3,21,41,54,55
	1+x5+x8	7,18,42,43	x41	1,2,3,9,23,24,41,49
	1+x9	10,11,41,54,56 1+x71+x72	19,49,50,51,55
	x10	11,41,55,56	1+x72	19,50,51,52,54
	1+x11+x12 10,41,55,56 x71+x73+x74 1,2,3,17,18,22,50,54
	x12	9,10,18,41,55	x74	1,2,3,19,22,50,55
	1+x21	22,24,59,60

Table 4 .

 4 Maxterms for 7-Round LBlock

	Maxterm Cube Output	Maxterm	Cube	Output
	Equations Indexes Index	Equations	Indexes	Index
	x1	3,4	4	x41	3,4,23,50
	x2	1,50	4	x42	9,10,11,54
	1+x3+x4 2,49,50	1	x43	10,11,12
	1+x4	3,50	3	x10+x44+x45	11,12,54
	x5	7,8	24	1+x45	50,51,63,64
	x6	7,42	24	1+x46	23,24,60
	1+x7+x8 6,41,42	21	x21+x47	22,23,60
	x8	5,6,42	28	x22+x48+x49	1,23,24,46
	1+x9	10,12,55	25	1+x22+x49	23,24,57
	x10	11,53	27	x50	29,30,31,63	4
	1+x11+x12 10,53	27	x30+x51	31,32,64	4
	x12	9,10,55	25	1+x52+x53	31,32,62	4
	1+x13	14,15,45	13	x53	27,29,31,62
	x14	13,47	13	1+x18+x54	19,20,36
	1+x15+x16 14,46	16	1+x55	19,20,33
	x16	13,14,47	15	1+x17+x56+x57	18,19,33
	1+x17	18,20,34	20	x57	7,18,19,33
	x18	20,35	16	x58	25,26,27,40	5
	1+x17+x19 6,20,34	41	1+x26+x59	27,28,40	5
	x17+x20	19,34	18	1+x60+x61	26,27,28,31
	x21	22,23,59	5	x61	26,27,28	5
	x22	23,58	8	x67	41,43,44,62	4
	1+x23+x24 22,58	8	1+x68	41,43,55,56
	1+x24	21,22,59	6	x69+x70	18,43,44,62	3
	x25	27,28	9	x70	18,43,44,63	1
	x26	25,38	9	x71	49,50,51,55
	x27	25,26,39	5	1+x72	49,52,55
	1+x28	25,26,39	10	x71+x73+x74	50,52,55
	x29	31,32	29	x74	22,51,52,55
	x30	29,62	29	1+x75	27,43,63,64
	1+x31	29,30,63	1	x76	41,42,62,63
	x32	29,30,62	32	x76+x77+x78 14,41,61,65,64
	x38	1,3,4,22	60	x76+x78	25,42,61,62,64
	x2+x39	3,4,51	31	x79	34,37,39,40
	x40+x41	3,4,50	31	x79+x80	31,35,37,38,40

Table 5 .

 5 Maxterms for 9-Round LBlock

	Maxterm	Cube	Output Maxterm	Cube	Output
	Equations	Indexes	Index Equations	Indexes	Index
	x1	2,3,41,43,44	28	x30	29,32,41,43,44,64
	x2	29,35,37,38,39	6	x32	29,30,41,43,44,64
	1+x3+x4	1,2,41,43,44	28	x67	41,43,44,62
	x4	46,57,58,59	9	x67+x68	41,42,44,61,62
	x5	6,7,41,61,63,64	17	x69+x70	42,43,44,62
	x6	2,47,57,58,59	10	x70	42,43,44,63
	x7	33,35,36,39	29	x71	49,50,51,55
	x7+x8	7,33,34,36,39	29	x72	50,51,52,54
	1+x9+x10	34,35,36,39	29	x71+x73+x74 22,49,50,52,54
	x10	34,35,36,38	32	x74	22,49,50,52,55
	1+x17	18,19,31,37,39,40	5	x75	26,42,61,62,63
	x18	17,19,31,37,39,40	5	x76	43,61,62,63
	x25	8,26,27,34,35,36	32	x76+x77+x78	43,61,62,64
	x26	5,28,33,35,36,37	30	x76+x78	25,42,61,62,64
	x9+x10+x27+x28 25,26,34,35,36,37	30	x79	34,37,39,40	6
	1+x25+x28	27,39,40,57,59,60	11	x79+x80	31,35,37,38,40	5
	x29	30,32,41,43,44,64	25

Acknowledgments. We are thankful to the authors of LBlock especially Lei Zhang. They confirmed us that the security analysis of LBlock against the cube attack has not been done yet and we may try. We are also thankful to Michael Vielhaber, Deian Stefan and Bo Zhu who coordinated with us on email that helped us in understanding the cube attack.