Progress in Cryptology – AFRICACRYPT 2013

Frontmatter

Adapting Lyubashevsky’s Signature Schemes to the Ring Signature Setting

Abstract

Basing signature schemes on strong lattice problems has been a long standing open issue. Today, two families of lattice-based signature schemes are known: the ones based on the hash-and-sign construction of Gentry et al.; and Lyubashevsky’s schemes, which are based on the Fiat-Shamir framework.

In this paper we show for the first time how to adapt the schemes of Lyubashevsky to the ring signature setting. In particular we transform the scheme of ASIACRYPT 2009 into a ring signature scheme that provides strong properties of security under the random oracle model. Anonymity is ensured in the sense that signatures of different users are within negligible statistical distance even under full key exposure. In fact, the scheme satisfies a notion which is stronger than the classical full key exposure setting as even if the keypair of the signing user is adversarially chosen, the statistical distance between signatures of different users remains negligible.

Considering unforgeability, the best lattice-based ring signature schemes provide either unforgeability against arbitrary chosen subring attacks or insider corruption in log-sized rings. In this paper we present two variants of our scheme. In the basic one, unforgeability is ensured in those two settings. Increasing signature and key sizes by a factor k (typically 80 − 100), we provide a variant in which unforgeability is ensured against insider corruption attacks for arbitrary rings. The technique used is pretty general and can be adapted to other existing schemes.

Carlos Aguilar Melchor, Slim Bettaieb, Xavier Boyen, Laurent Fousse, Philippe Gaborit

GPU-Based Implementation of 128-Bit Secure Eta Pairing over a Binary Field

Abstract

Eta pairing on a supersingular elliptic curve over the binary field \(F_{2^{1223}}\) used to offer 128-bit security, and has been studied extensively for efficient implementations. In this paper, we report our GPU-based implementations of this algorithm on an NVIDIA Tesla C2050 platform. We propose efficient parallel implementation strategies for multiplication, square, square root and inverse in the underlying field. Our implementations achieve the best performance when López-Dahab multiplication with four-bit precomputations is used in conjunction with one-level Karatsuba multiplication. We have been able to compute up to 566 eta pairings per second. To the best of our knowledge, ours is the fastest GPU-based implementation of eta pairing. It is about twice as fast as the only reported GPU implementation, and about five times as fast as the fastest reported single-core SIMD implementation. We estimate that the NVIDIA GTX 480 platform is capable of producing the fastest known software implementation of eta pairing.

Utsab Bose, Anup Kumar Bhattacharya, Abhijit Das

On Constructions of Involutory MDS Matrices

Abstract

Maximum distance separable (MDS) matrices have applications not only in coding theory but also are of great importance in the design of block ciphers and hash functions. It is highly nontrivial to find MDS matrices which is involutory and efficient. In a paper in 1997, Youssef et. al. proposed an involutory MDS matrix construction using Cauchy matrix. In this paper we study properties of Cauchy matrices and propose generic constructions of low implementation cost MDS matrices based on Cauchy matrices. In a 2009 paper, Nakahara and Abrahao proposed a 16 ×16 involutory MDS matrix over \(\mathbb{F}_{2^8}\) by using a Cauchy matrix which was used in MDS-AES design. Authors claimed that their construction by itself guarantees that the resulting matrix is MDS and involutory. But the authors didn’t justify their claim. In this paper we study and prove that this proposed matrix is not an MDS matrix. Note that this matrix has been designed to be used in the block cipher MDS-AES, which may now have severe weaknesses. We provide an algorithm to construct involutory MDS matrices with low Hamming weight elements to minimize primitive operations such as exclusive-or, table look-ups and xtime operations. In a 2012 paper, Sajadieh et. al. provably constructed involutory MDS matrices which were also Hadamard in a finite field by using two Vandermonde matrices. We show that the same matrices can be constructed by using Cauchy matrices and provide a much simpler proof of their construction.

Kishan Chand Gupta, Indranil Ghosh Ray

Homomorphic Encryption with Access Policies: Characterization and New Constructions

Abstract

A characterization of predicate encryption (PE) with support for homomorphic operations is presented and we describe the homomorphic properties of some existing PE constructions. Even for the special case of IBE, there are few known group-homomorphic cryptosystems. Our main construction is an XOR-homomorphic IBE scheme based on the quadratic residuosity problem (variant of the Cocks’ scheme), which we show to be strongly homomorphic. We were unable to construct an anonymous variant that preserves this homomorphic property, but we achieved anonymity for a weaker notion of homomorphic encryption, which we call non-universal. A related security notion for this weaker primitive is formalized. Finally, some potential applications and open problems are considered.

Michael Clear, Arthur Hughes, Hitesh Tewari

Brandt’s Fully Private Auction Protocol Revisited

Abstract

Auctions have a long history, having been recorded as early as 500 B.C. [17]. Nowadays, electronic auctions have been a great success and are increasingly used. Many cryptographic protocols have been proposed to address the various security requirements of these electronic transactions, in particular to ensure privacy. Brandt [4] developed a protocol that computes the winner using homomorphic operations on a distributed ElGamal encryption of the bids. He claimed that it ensures full privacy of the bidders, i.e. no information apart from the winner and the winning price is leaked. We first show that this protocol – when using malleable interactive zero-knowledge proofs – is vulnerable to attacks by dishonest bidders. Such bidders can manipulate the publicly available data in a way that allows the seller to deduce all participants’ bids. Additionally we discuss some issues with verifiability as well as attacks on non-repudiation, fairness and the privacy of individual bidders exploiting authentication problems.

Jannik Dreier, Jean-Guillaume Dumas, Pascal Lafourcade

HELEN: A Public-Key Cryptosystem Based on the LPN and the Decisional Minimal Distance Problems

Abstract

We propose HELEN, a code-based public-key cryptosystem whose security is based on the hardness of the Learning from Parity with Noise problem (LPN) and the decisional minimum distance problem. We show that the resulting cryptosystem achieves indistinguishability under chosen plaintext attacks (IND-CPA security). Using the Fujisaki-Okamoto generic construction, HELEN achieves IND-CCA security in the random oracle model. Our cryptosystem looks like the Alekhnovich cryptosystem. However, we carefully study its complexity and we further propose concrete optimized parameters.

Alexandre Duc, Serge Vaudenay

Attacking AES Using Bernstein’s Attack on Modern Processors

Abstract

The Advanced Encryption Standard (AES) was selected by NIST due to its heavy resistance against classical cryptanalysis like differential and linear cryptanalysis. Even after the appearance of the modern side-channel attacks like timing and power consumption side-channel attacks, NIST claimed that AES is not vulnerable to timing attacks. In 2005, Bernstein [6] has successfully attacked the OpenSSL AES implementation on a Pentium III processor and completely retrieved the full AES key using his cache timing side-channel attack. This paper reproduces Bernstein’s attack on Pentium Dual-Core and Core 2 Duo processors. We have successfully attacked the AES implemented in the latest OpenSSL release 1.0.1c using the most recent GCC compiler 4.7.0 running on both Windows and Linux in some seconds by sending 2²² plaintexts at most. We improved Bernstein’s first round attack by using 2 way measurements. Instead of using only the above average timing information, we added the above minimum timing information which significantly improved the results.

Hassan Aly, Mohammed ElGayyar

Optimal Public Key Traitor Tracing Scheme in Non-Black Box Model

Abstract

In the context of secure content distribution, the content is encrypted and then broadcasted in a public channel, each legitimate user is provided a decoder and a secret key for decrypting the received signals. One of the main threat for such a system is that the decoder can be cloned and then sold out with the pirate secret keys. Traitor tracing allows the authority to identify the malicious users (are then called traitors) who successfully collude to build pirate decoders and pirate secret keys. This primitive is introduced by Chor, Fiat and Naor in ’94 and a breakthrough in construction is given by Boneh and Franklin at Crypto ’99 in which they consider three models of traitor tracing: non-black-box tracing model, single-key black box tracing model, and general black box tracing model.

Beside the most important open problem of obtimizing the black-box tracing, Boneh-Franklin also left an open problem concerning non-black-box tracing, by mentioning: “it seems reasonable to believe that there exists an efficient public key traitor tracing scheme that is completely collusion resistant. In such a scheme, any number of private keys cannot be combined to form a new key. Similarly, the complexity of encryption and decryption is independent of the size of the coalition under the pirate’s control. An efficient construction for such a scheme will provide a useful solution to the public key traitor tracing problem”.

As far as we know, this problem is still open. In this paper, we resolve this question in the affirmative way, by constructing a very efficient scheme with all parameters are of constant size and in which the full collusion of traitors cannot produce a new key. Our proposed scheme is moreover dynamic.

Philippe Guillot, Abdelkrim Nimour, Duong Hieu Phan, Viet Cuong Trinh

NaCl on 8-Bit AVR Microcontrollers

Abstract

This paper presents first results of the Networking and Cryptography library (NaCl) on the 8-bit AVR family of microcontrollers. We show that NaCl, which has so far been optimized mainly for different desktop and server platforms, is feasible on resource-constrained devices while being very fast and memory efficient. Our implementation shows that encryption using Salsa20 requires 268 cycles/byte, authentication using Poly1305 needs 195 cycles/byte, a Curve25519 scalar multiplication needs 22 791 579 cycles, signing of data using Ed25519 needs 23 216 241 cycles, and verification can be done within 32 634 713 cycles. All implemented primitives provide at least 128-bit security, run in constant time, do not use secret-data-dependent branch conditions, and are open to the public domain (no usage restrictions).

Michael Hutter, Peter Schwabe

W-OTS+ – Shorter Signatures for Hash-Based Signature Schemes

Abstract

We present W-OTS+, a Winternitz type one-time signature scheme (W-OTS). We prove that W-OTS+ is strongly unforgeable under chosen message attacks in the standard model. Our proof is exact and tight. The first property allows us to compute the security of the scheme for given parameters. The second property allows for shorter signatures than previous proposals without lowering the security. This improvement in signature size directly carries over to all recent hash-based signature schemes. I.e. we can reduce the signature size by more than 50% for XMSS+ at a security level of 80 bits. As the main drawback of hash-based signature schemes is assumed to be the signature size, this is a further step in making hash-based signatures practical.

Andreas Hülsing

New Speed Records for Salsa20 Stream Cipher Using an Autotuning Framework on GPUs

Abstract

Since the introduction of the CUDA programming model, GPUs are considered a viable platform for accelerating non-graphical applications. Many cryptographic algorithms have been reported to achieve remarkable performance speedups, especially block ciphers. For stream ciphers, however, the lack of reported GPU acceleration endeavors is due to their inherent iterative structures that prohibit parallelization. In this paper, we propose an efficient implementation methodology for data-parallel cryptographic functions in a batch processing fashion on modern GPUs in general and optimizations for Salsa20 in particular. We present an autotuning framework to reach the most optimized set of device and application parameters for Salsa20 kernel variants with throughput maximization as a figure of merit. The peak performance achieved by our implementation for Salsa20/12 is 2.7 GBps and 43.44 GBps with and without memory transfers respectively on NVIDIA GeForce GTX 590. These figures beat the fastest reported GPU implementation of any stream cipher in the eSTREAM portfolio including Salsa20/12, as well as the block cipher AES optimized by hand-tuning, and thus, to the best of our knowledge set a new speed record.

Ayesha Khalid, Goutam Paul, Anupam Chattopadhyay

Cryptanalysis of AES and Camellia with Related S-boxes

Abstract

Cryptanalysis mainly has public algorithms as target; however cryptanalytic effort has also been directed quite successfully to block ciphers that contain secret components, typically S-boxes. Known approaches can only attack reduced-round variants of the target algorithms, AES being a nice example. In this paper we present a novel cryptanalytic attack that can recover the specification of S-boxes from algorithms that resist to cryptanalysis, under the assumption that the attacker can work on a pair of such block ciphers that instantiate related S-boxes. These S-boxes satisfy the designer’s requirements but are weakly diversified; the relationship between these unknown components is used in much the same way as relationship between secret keys is used in related-key attacks. This attack (called related S-box attack) can be used, under certain assumptions, to retrieve the content of the S-boxes in practical time. We apply our attack to two well known ciphers, AES and Camellia; these ciphers use 8-bit S-boxes but are structurally very different, and our attack adapts accordingly. This shows that most probably the same can be applied to other ciphers which can be customized to instantiate unknown 8-bit S-boxes.

Marco Macchetti

New Results on Generalization of Roos-Type Biases and Related Keystreams of RC4

Abstract

The first known result on RC4 cryptanalysis (presented by Roos in 1995) points out that the most likely value of the y-th element of the permutation after the key scheduling algorithm (KSA) for the first few values of y is given by S _N [y] = f _y , some linear combinations of the secret keys. While it should have been quite natural to study the association S _N [y] = f _y ±t for small positive integers t (e.g., t ≤ 4), surprisingly that had never been tried before. In this paper, we study that problem for the first time and show that though the event S _N [y] = f _y  + t occurs with random association, there is a significantly high probability for the event S _N [y] = f _y  − t. We also present several related non-randomness behaviour for the event S _N [S _N [y]] = f _y  − t of RC4 KSA in this direction. Further, we investigate near-colliding keys that lead to related states after the KSA and related keystream bytes. Our investigation reveals that near-colliding states do not necessarily lead to near-colliding keystreams. From this motivation, we present a heuristic to find a related key pair with differences in two bytes, that lead to significant matches in the initial keystream. In the process, we discover a class of related key distinguishers for RC4. The best one of these shows that given a random key and a related one to that (the last two bytes increased and decreased by 1 respectively), the first pair of bytes corresponding to the related keys are same with very high probability (e.g., approximately 0.011 for 16-byte keys to 0.044 for 30-byte keys).

Subhamoy Maitra, Goutam Paul, Santanu Sarkar, Michael Lehmann, Willi Meier

Impact of Sboxes Size upon Side Channel Resistance and Block Cipher Design

Abstract

Designing a cryptographic algorithm requires to take into account various cryptanalytic threats. Since the 90’s, Side Channel Analysis (SCA) has become a major threat against cryptographic algorithms embedded on physical devices. Protecting implementation of ciphers against such attacks is a very dynamic topic of research and many countermeasures have been proposed to thwart these attacks. The most common countermeasure for block cipher implementations is masking, which randomizes the variables by combining them with one or several random values. In this paper, we propose to investigate the impact of the size of the words processed by an algorithm on the security against SCA. For this matter we describe two AES-like algorithms operating respectively on 4 and 16-bit words. We then compare them with the regular AES (8 bits) both in terms of complexity and security with respect to various masking schemes. Our results show that SCA is a determinant criterion for algorithms design and that cryptographers may have various possibilities depending on their security and complexity requirements.

Louis Goubin, Ange Martinelli, Matthieu Walle

Efficient Multiparty Computation for Arithmetic Circuits against a Covert Majority

Abstract

We design a secure multiparty protocol for arithmetic circuits against covert adversaries in the dishonest majority setting. Our protocol achieves a deterrence factor of \(\left(1 - \frac{1}{t}\right)\) with O(Mn ² t ² s) communication complexity and O(Mn ³ t ²) exponentiations where s is the security parameter, n is the number of parties and M is the number of multiplication gates. Our protocol builds on the techniques introduced in (Mohassel and Weinreb, CRYPTO’08), extending them to work in the multiparty case, working with higher deterrence factors, and providing simulation-based security proofs. Our main underlying primitive is a lossy additive homomorphic public key encryption scheme where the lossiness is critical for the simulation-based proof of security to go through. Our concrete efficiency measurements show that our protocol performs better than previous solutions for a range of deterrence factors, for functions such as AES and matrix multiplication.

Isheeta Nargis, Payman Mohassel, Wayne Eberly

Impact of Optimized Field Operations AB,AC and AB + CD in Scalar Multiplication over Binary Elliptic Curve

Abstract

A scalar multiplication over a binary elliptic curve consists in a sequence of hundreds of multiplications, squarings and additions. This sequence of field operations often involves a large amount of operations of type AB,AC and AB + CD. In this paper, we modify classical polynomial multiplication algorithms to obtain optimized algorithms which perform these particular operations AB,AC and AB + CD. We then present software implementation results of scalar multiplication over binary elliptic curve over two platforms: Intel Core 2 and Intel Core i5. These experimental results show some significant improvements in the timing of scalar multiplication due to the proposed optimizations.

Christophe Negre, Jean-Marc Robert

An Attack on RSA Using LSBs of Multiples of the Prime Factors

Abstract

Let N = pq be an RSA modulus with a public exponent e and a private exponent d. Wiener’s famous attack on RSA with d < N ^0.25 and its extension by Boneh and Durfee to d < N ^0.292 show that using a small d makes RSA completely insecure. However, for larger d, it is known that RSA can be broken in polynomial time under special conditions. For example, various partial key exposure attacks on RSA and some attacks using additional information encoded in the public exponent e are efficient to factor the RSA modulus. These attacks were later improved and extended in various ways. In this paper, we present a new attack on RSA with a public exponent e satisfying an equation ed − k(N + 1 − ap − bq) = 1 where \(\frac{a}{b}\) is an unknown approximation of \(\frac{q}{p}\). We show that RSA is insecure when certain amount of the Least Significant Bits (LSBs) of ap and bq are known. Further, we show that the existence of good approximations \(\frac{a}{b}\) of \(\frac{q}{p}\) with small a and b substantially reduces the requirement of LSBs of ap and bq.

Abderrahmane Nitaj

Modification and Optimisation of an ElGamal-Based PVSS Scheme

Abstract

Among the existing PVSS schemes, a proposal by Shoemakers is a very special one. It avoids a common problem in PVSS design and costly operations by generating the secret to share in a certain way. Although its special secret generation brings some limitations to its application, its improvement in simplicity and efficiency is significant. However, its computational cost is still linear in the square of the number of share holders. Moreover, appropriate measures need to be taken to extend its application. In this paper, the PVSS scheme is modified to improve its efficiency and applicability. Firstly, a more efficient proof technique is designed to reduce the computational cost of the PVSS scheme to be linear in the number of share holders. Secondly, its secret generation procedure is extended to achieve better flexibility and applicability.

Kun Peng

Studying a Range Proof Technique — Exception and Optimisation

Abstract

A batch proof and verification technique is employed to design efficient range proof with practical small ranges in AFRICACRYPT 2010. It is shown in this paper that the batch proof and verification technique is not always sound in its application to range proof. We demonstrate that their batch proof and verification technique causes a concern such that in some cases a malicious prover without the claimed knowledge may pass the verification. As a result their range proof scheme to prove that a secret committed integer is in an interval range is not so reliable and cannot guarantee that the committed integer is in the range in some special cases. To ease the concern, we employ an efficient membership proof technique to replace the batch proof and verification technique in their range proof scheme and re-design it to achieve the claimed high efficiency with practical small ranges.

Kun Peng, Li Yi

Key-Leakage Resilient Revoke Scheme Resisting Pirates 2.0 in Bounded Leakage Model

Abstract

Trace and revoke schemes have been widely studied in theory and implemented in practice. In the first part of the paper, we construct a fully secure key-leakage resilient identity-based revoke scheme. In order to achieve this goal, we first employ the dual system encryption technique to directly prove the security of a variant of the BBG − WIBE scheme under known assumptions (and thus avoid a loss of an exponential factor in hierarchical depth in the classical method of reducing the adaptive security of WIBE to the adaptive security of the underlying HIBE). We then modify this scheme to achieve a fully secure key-leakage resilient WIBE scheme. Finally, by using a transformation from a WIBE scheme to a revoke scheme, we propose the first fully secure key-leakage resilient identity-based revoke scheme.

In the classical model of traitor tracing, one assumes that a traitor contributes its entire secret key to build a pirate decoder. However, new practical scenarios of pirate has been considered, namely Pirate Evolution Attacks at Crypto 2007 and Pirates 2.0 at Eurocrypt 2009, in which pirate decoders could be built from sub-keys of users. The key notion in Pirates 2.0 is the anonymity level of traitors: they can rest assured to remain anonymous when each of them only contributes a very small fraction of its secret key by using a public extraction function. This scenario encourages dishonest users to participate in collusion and the size of collusion could become very large, possibly beyond the considered threshold in the classical model. In the second part of the paper, we show that our key-leakage resilient identity-based revoke scheme is immune to Pirates 2.0 in some special forms in bounded leakage model. It thus gives an interesting and rather surprised connection between the rich domain of key-leakage resilient cryptography and Pirates 2.0.

Duong Hieu Phan, Viet Cuong Trinh

Fast Software Encryption Attacks on AES

Abstract

In this work, we compare different faster than brute-force single-key attacks on the full AES in software. Contrary to dedicated hardware implementations, software implementations are more transparent and do not over-optimize a specific type of attack. We have analyzed and implemented a black-box brute-force attack, an optimized brute-force attack and a biclique attack on AES-128. Note that all attacks perform an exhaustive key search but the latter two do not need to recompute the whole cipher for all keys. To provide a fair comparison, we use CPUs with Intel AES-NI since these instructions tend to favor the generic black-box brute-force attack. Nevertheless, we are able to show that on Sandy Bridge the biclique attack on AES-128 is 17% faster, and the optimized brute-force attack is 3% faster than the black-box brute-force attack.

David Gstir, Martin Schläffer

Sieving for Shortest Vectors in Ideal Lattices

Abstract

Lattice based cryptography is gaining more and more importance in the cryptographic community. It is a common approach to use a special class of lattices, so-called ideal lattices, as the basis of lattice based crypto systems. This speeds up computations and saves storage space for cryptographic keys. The most important underlying hard problem is the shortest vector problem. So far there is no algorithm known that solves the shortest vector problem in ideal lattices faster than in regular lattices. Therefore, crypto systems using ideal lattices are considered to be as secure as their regular counterparts.

In this paper we present IdealListSieve, a variant of the ListSieve algorithm, that is a randomized, exponential time sieving algorithm solving the shortest vector problem in lattices. Our variant makes use of the special structure of ideal lattices. We show that it is indeed possible to find a shortest vector in ideal lattices faster than in regular lattices without special structure. The practical speedup of our algorithm is linear in the degree of the field polynomial. We also propose an ideal lattice variant of the heuristic GaussSieve algorithm that allows for the same speedup.

Michael Schneider

An Identity-Based Key-Encapsulation Mechanism Built on Identity-Based Factors Selection

Abstract

A new approach to identity-based encryption (IBE), called identity-based factors selection (IBFS), allows to build efficient and fully collusion-resistant IBE schemes without the need for pairings or the use of lattices. The security of these constructions (in the random oracle model) rests on the hardness of a new problem which combines the computational Diffie-Hellman problem with the fact that linear equation systems with more variables than given equations do not have unambiguous solutions. The computational efficiency of the resulting IBE schemes is (for values of the security parameter not smaller than 80) better than in previous IBE schemes. The construction of these schemes may be seen as an extension of the ElGamal public-key encryption scheme. The sender of a message computes the ElGamal-like public key of the message receiver by first selecting, uniquely determined by the identity of the receiver, from a set of group elements \(\{g^{e_1}, ..., g^{e_z} \}\) made available as public parameters a subset, and then multiplying the selected elements.

Sebastian Staamann

A Comparison of Time-Memory Trade-Off Attacks on Stream Ciphers

Abstract

Introduced by Hellman, Time-Memory Trade-Off (TMTO) attacks offer a generic technique to reverse one-way functions, where one can trade off time and memory costs and which are especially effective against stream ciphers. Hellman’s original idea has seen many different improvements, notably the Distinguished Points attack and the Rainbow Table attack. The trade-off curves of these approaches have been compared in literature, but never leading to a satisfying conclusion. A new TMTO attack was devised for the A5/1 cipher used in GSM, which combines both distinguished points and rainbow tables, which we refer to as the Kraken attack. This paper compares these four approaches by looking at concrete costs of these attacks instead of comparing their trade-off curves. We found that when multiple samples are available the Distinguished Points attack has the lowest costs. The Kraken attack is an alternative to save more disk space at the expense of attack time.

Fabian van den Broek, Erik Poll

On the Expansion Length Of Triple-Base Number Systems

Abstract

Triple-base number systems are mainly used in elliptic curve cryptography to speed up scalar multiplication. We give an upper bound on the length of the canonical triple-base representation with base {2, 3, 5} of an integer x, which is \(\mathcal{O}(\frac{\log x}{\log\log x})\) by the greedy algorithm, and show that there are infinitely many integers x whose shortest triple-base representations with base {2, 3, 5} have length greater than \(\frac{c\log x}{\log\log x\log\log\log x},\) where c is a positive constant, using the universal exponent method. This analysis gives a limit how much scalar multiplication on elliptic curves may be made faster.

Wei Yu, Kunpeng Wang, Bao Li, Song Tian

Triple-Base Number System for Scalar Multiplication

Abstract

The triple-base number system is used to speed up scalar multiplication. At present, the main methods to calculate a triple-base chain are greedy algorithms. We propose a new method, called the add/sub algorithm, to calculate scalar multiplication. The density of such chains gained by this algorithm with base {2, 3, 5} is \(\frac{1}{5.61426}\). It saves 22% additions compared with the binary/ternary method; 22.1% additions compared with the multibase non-adjacent form with base {2, 3, 5}; 13.7% additions compared with the greedy algorithm with base {2, 3, 5}; 20.9% compared with the tree approach with base {2, 3}; and saves 4.1% additions compared with the add/sub algorithm with base {2, 3, 7}, which is the same algorithm with different parameters. To our knowledge, the add/sub algorithm with base {2, 3, 5} is the fastest among the existing algorithms. Also, recoding is very easy and efficient and together with the add/sub algorithm are very suitable for software implementation. In addition, we improve the greedy algorithm by plane search which searches for the best approximation with a time complexity of \(\mathcal{O}(\log^3 k)\) compared with that of the original of \(\mathcal{O}(\log^4 k)\).

Wei Yu, Kunpeng Wang, Bao Li, Song Tian

Backmatter