Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
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
29
views
0
downloads
Cite This
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...
Large sparse matrix-vector multiplication over finite fields
Mangır, Ceyda; Cenk, Murat; Manguoğlu, Murat; Department of Cryptography (2019)
Cryptographic computations such as factoring integers and computing discrete logarithms require solving a large sparse system of linear equations over finite fields. When dealing with such systems iterative solvers such as Wiedemann or Lanczos algorithms are used. The computational cost of both methods is often dominated by successive matrix-vector products. In this thesis, we introduce a new algorithm for computing a large sparse matrix-vector multiplication over finite fields. The proposed algorithm is im...
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 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.
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
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.