This paper focuses on speeding up NTRU - one of the lattice-based finalists of the NIST PQC competition - by improving the ring multiplication. The Number Theoretic Transform (NTT), Toom-Cook, and Karatsuba are the most commonly used algorithms for implementing NTRU. In this paper, we propose Toeplitz matrix-vector product (TMVP) based algorithms for multiplication for all parameter sets of NTRU. We implement the proposed algorithms on ARM Cortex-M4. The results show that the TMVP-based multiplication algorithms we propose are more efficient than the others in the literature in most cases. Our algorithm forntruhps2048509outperform the Toom-Cook and NTT methods in the literature by 25.4% and 21.5%. We also observe the impact of these improvements on the overall performance of NTRU. We speed up the key generation, encryption, decryption, encapsulation, and decapsulation algorithms ofntruhps2048509by 12.5%, 14.3%, 17.7%, 3.9%, and 14.7%, respectively, compared to state-of-the-art implementation. Moreover, our algorithms require less stack space than the others.

Zero-knowledge protocols (ZKPs) allow a party to prove the validation of secret information to some other party without revealing any information about the secret itself. Appropriate, effective, and efficient use of cryptographic ZKPs contributes to many novel advances in real-world privacy-preserving frameworks. One of the most important type of cryptographic ZKPs is the zero-knowledge range proofs (ZKRPs). Such proofs have wide range of applications such as anonymous credentials, cryptocurrencies, e-cash schemes etc. In many ZKRPs the secret is represented in binary then committed via a suitable commitment scheme. Though there exist different base approaches on bilinear paring-based and RSA-like based constructions, to our knowledge there is no study on investigating the discrete logarithm-based constructions. In this study, we focus on a range proof construction produced by Mao in 1998. This protocol contains a bit commitment scheme with an OR-construction. We investigate the effect of different base approach on Mao's range proof and compare the efficiency of these basis approaches. To this end, we have extended Mao's range proof to base-3 with a modified OR-proof. We derive the number of computations in modulo exponentiations and the cost of the number of integers exchanged between parties. Then, we have generalized these costs for the base-u construction. Here, we mainly show that comparing with other base approaches, the base-3 approach consistently provides approximately 12% efficiency in computation cost and 10% efficiency in communication cost. We implemented the base-3 protocol and demonstrated that the results are consistent with our theoretical computations.

Securing Internet-of-Things (IoT) applications that collect and transport sensitive data by guaranteeing authenticity, integrity, and confidentiality is a critical challenge. Reducing computation and communication overhead of security functions is also a key concern since a large number of constrained devices may take place in such applications. Our main focus, in this article, is group authentication and key management in IoT. The existing group authentication and key management protocols in the literature perform computations using asymmetric ciphers, which costly for IoT. Therefore, applications generally employ simple security primitives that are prone to or lead to cyberattacks by using IoT devices. In this article, we propose a physically unclonable function (PUF)-based lightweight group authentication and key distribution (PLGAKD) protocol that employs PUF, factorial tree, and the Chinese remainder theorem (CRT). In PLGAKD, PUF facilitates lightweight authentication and key distribution for group members. Each group member performs two encryptions, one decryption, four XORs operations, and three HMAC operations. For the key renewal process, the factorial tree and CRT help us reduce the number of keys stored in nodes and the number of communication messages contrary to the binary tree. As an example, a binary tree with 4096 members completes the key renewal process with 12 messages by storing 12 keys. However, the PLGAKD protocol with 5040 members completes this process with six messages by storing seven keys. Moreover, the PLGAKD protocol becomes more efficient in parallel with the increase in the number of members.

Some applications like cryptography involve a large number of multiplications of binary polynomial. In this paper, we consider two-, three-, and four-way methods for parallel implementation of binary polynomial multiplication. We propose optimized three- and four-way split formulas which reduce the space and time complexity of the best known methods. Moreover, we present a block recombination method which provides some further reduction in the space complexity of the considered two-, three-, and four-way split multipliers.

In this study, the authors give a generalisation of special moduli for faster interleaved Montgomery modular multiplication algorithm with simplified pre‐computational phase for GF ( p n ), where p ≥ 2 is a prime number and n is a positive integer. The authors propose different sets of moduli that can be used in elliptic curve crytographic applications and pairing‐based cryptography. Moreover, this method also leads to efficient implementations for the elliptic curve parameters given in standards. It is shown that one can obtain efficient Montgomery modular multiplication architecture in view of the number of AND gates and XOR gates by choosing proposed sets of moduli. The authors eliminate final substraction step with proposed sets of moduli. These methods are easy to implement for hardware.

In this paper, we consider three-way split formulas for binary polynomial multiplication and Toeplitz matrix vector product (TMVP). We first recall the best known three-way split formulas for polynomial multiplication: the formulas with six recursive multiplications given by Sunar in a 2006 IEEE Transactions on Computers paper and the formula with five recursive multiplications proposed by Bernstein at CRYPTO 2009. Second, we propose a new set of three-way split formulas for polynomial multiplication that are an optimization of Sunar's formulas. Then, we present formulas with five recursive multiplications based on field extension. In addition, we extend the latter formulas to TMVP. We evaluate the space and delay complexities when computations are performed in parallel and provide a comparison with best known methods.

We give an efficient multiplication method for polynomials in Chebyshev form. This multiplication method is different from the previous ones. Theoretically, we show that the number of multiplications is at least as good as Karatsuba-based algorithm. Moreover, using the proposed method, we improve the number of additions slightly. We remark that our method works efficiently for any N and it is easy to implement. To the best of our knowledge, the proposed method has the best multiplication and addition complexity for the N-term polynomial multiplication in Chebyshev form with 3 ≤ N ≤ 13.

A method for polynomial multiplication over finite fields using field extensions and polynomial interpolation is introduced. The proposed method uses polynomial interpolation as Toom-Cook method together with field extensions. Furthermore, the proposed method can be used when Toom-Cook method cannot be applied directly. Explicit formulae improving the previous results in many cases are obtained.

Let n and lscr be positive integers and f(x) be an irreducible polynomial over IF2such that lscrdeg(f(x))lscr. This upper bound allows a better selection of the moduli when Chinese Remainder Theorem is used for polynomial multiplication over IF2. We give improved formulae to multiply polynomials of small degree over IF2. In particular we improve the best known multiplication complexities over IF2in the literature in some cases.