Efficient interleaved Montgomery modular multiplication for lattice-based cryptography

Download
2014-01-01
AKLEYLEK, SEDAT
Tok, Zaliha Yuce
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 method. We receive at least 19% improvement with the proposed method for the polynomial multiplication in (Z/pZ)[x]/(x(n) + 1), where n is an element of{1024, 2048, 4096}.
IEICE ELECTRONICS EXPRESS

Suggestions

Sparse polynomial multiplication for lattice-based cryptography with small complexity
Akleylek, Sedat; Alkim, Erdem; Tok, Zaliha Yuce (2016-02-01)
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 numbe...
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...
Efficient hybrid discrete Fourier transform-moment method for fast analysis of large rectangular arrays
Chou, HT; Ho, HK; Pathak, PH; Nepa, P; Aydın Çivi, Hatice Özlem (Institution of Engineering and Technology (IET), 2002-02-01)
A novel approach combining the moment method (MoM) and the discrete Fourier transform (DFT) is developed for the fast analysis of electromagnetic (EM) radiation/scattering from electrically large, finite, planar rectangular arrays. In particular, the unknown array distribution to be solved is represented in terms of the DFT within the MoM for a given array excitation. The proposed DFT-MoM approach for large arrays has the advantage that it can overcome the inefficiency of the conventional MoM approach by dr...
Citation Formats
S. AKLEYLEK and Z. Y. Tok, “Efficient interleaved Montgomery modular multiplication for lattice-based cryptography,” IEICE ELECTRONICS EXPRESS, pp. 0–0, 2014, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/64696.