Sparse polynomial multiplication for lattice-based cryptography with small complexity

Date

2016-02-01

Author

Akleylek, Sedat
Alkim, Erdem
Tok, Zaliha Yuce

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

242
views

0
downloads

In this paper, we propose efficient modular polynomial multiplication methods with applications in lattice-based cryptography. We provide a sparse polynomial multiplication to be used in the quotient ring (Z/pZ)[x]/(x(n) + 1). Then, we modify this algorithm with sliding window method for sparse polynomial multiplication. Moreover, the proposed methods are independent of the choice of reduction polynomial. We also implement the proposed algorithms on the Core i5-3210M CPU platform and compare them with number theoretic transform multiplication. According to the experimental results, we speed up the multiplication operation in (Z/pZ)[x]/(x(n) + 1) at least 80% and improve the performance of the signature generation and verification process of GLP scheme significantly.

Subject Keywords

Polynomial multiplication, Lattice-based cryptography, Sparse polynomial, Sliding window method, Software implementation

URI

https://hdl.handle.net/11511/66561

Journal

JOURNAL OF SUPERCOMPUTING

DOI

https://doi.org/10.1007/s11227-015-1570-1

Collections

Department of Mathematics, Article

Suggestions

OpenMETU
Core

Efficient interleaved Montgomery modular multiplication for lattice-based cryptography AKLEYLEK, SEDAT; Tok, Zaliha Yuce (2014-01-01) In this paper, we give modified version of interleaved Montgomery modular multiplication method for lattice-based cryptography. With the proposed algorithms, we improve the multiplication complexity and embed the conversion operation into the algorithm with almost free cost. We implement the proposed methods for the quotient ring (Z/qZ)[x]/(x(n) - 1) and (Z/pZ)[x]/(x(n) + 1) on the GPU (NVIDIA Quadro 600) using the CUDA platform. NTRUEncrypt is accelerated approximately 35% on the GPU by using the proposed ...
Faster Montgomery modular multiplication without pre-computational phase for some classes of finite fields Akleylek, Sedat; Cenk, Murat; Özbudak, Ferruh (2010-09-24) In this paper, we give faster versions of Montgomery modular multiplication algorithm without pre-computational phase for GF(p) and GF(2 m ) which can be considered as a generalization of [3], [4] and [5]. We propose sets of moduli different than [3], [4] and [5] which can be used in PKC applications. We show 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. We eliminate precomputational phase wi...
Efficient multiplication in double-struck F sign3ℓm, m ≥ 1 and 5 ≤ ℓ ≤ 18 Cenk, Murat; Özbudak, Ferruh (2008-06-14) Using a method based on Chinese Remainder Theorem for polynomial multiplication and suitable reductions, we obtain an efficient multiplication method for finite fields of characteristic 3. Large finite fields of characteristic 3 are important for pairing based cryptography [3]. For 5 <= l <= 18, we show that our method gives canonical multiplication formulae over F-3lm for any m >= 1 with the best multiplicative complexity improving the bounds in [6]. We give explicit formula in the case F-36.97.
Efficient multiplications in F(5)5n and F(7)7n Cenk, Murat; Özbudak, Ferruh (2011-08-15) Efficient multiplications in finite fields of characteristics 5 and 7 are used for computing the Eta pairing over divisor class groups of the hyperelliptic curves Lee et al. (2008) [1]. In this paper, using the recent methods for multiplication in finite fields, the explicit formulas for multiplication in F(5)5n and F(7)7n are obtained with 10 multiplications in F(5)n for F(5)5n and 15 multiplications in F(7)n for F(7)7n improving the results in Cenk and Ozbudak (2008) [4], Cenk et al. (2009) [5], Lee et al...
Speeding up Curve25519 using Toeplitz Matrix-vector Multiplication Taskin, Halil Kemal; Cenk, Murat (2018-01-24) This paper proposes a new multiplication algorithm over F-2(255)-19 where the de-facto standard Curve25519 [2] algorithm is based on. Our algorithm for the underlying finite field multiplication exploits the Toeplitz matrix-vector multiplication and achieves salient results. We have used a new radix representation that is infeasible when used with schoolbook multiplication techniques but has notable advantages when used with Toeplitz matrix-vector multiplication methods. We present the new algorithm and dis...

Citation Formats

S. Akleylek, E. Alkim, and Z. Y. Tok, “Sparse polynomial multiplication for lattice-based cryptography with small complexity,” JOURNAL OF SUPERCOMPUTING, pp. 438–450, 2016, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/66561.