Sparse polynomial multiplication for lattice-based cryptography with small complexity

详细信息    查看全文

• 作者：Sedat Akleylek ; Erdem Alkım ; Zaliha Yüce Tok
• 关键词：Polynomial multiplication ; Lattice ; based cryptography ; Sparse polynomial ; Sliding window method ; Software implementation
• 刊名：The Journal of Supercomputing
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：72
• 期：2
• 页码：438-450
• 全文大小：1,117 KB
• 参考文献：1.Akleylek S, Yüce Tok Z (2014) Efficient arithmetic for lattice-based cryptography on GPU using the CUDA platform. In: Proceedings of IEEE 22nd signal processing and communications applications conference (SIU 2014), pp 854–857
  2.Akleylek S, Yüce Tok Z (2014) Efficient interleaved montgomery modular multiplication for lattice-based cryptography. IEICE Electron Exp 11(22):1–6CrossRef
  3.Aysu A, Patterson C, Schaumont P (2013) Low-cost and area efficient FPGA implementations of lattice-based cryptography. In: IEEE HOST, pp 81–86
  4.Bailey DV, Coffin D, Elbirt A, Silverman JH, Woodbury AD (2001) NTRU in constrained devices. In: CHES 2001. LNCS, vol 2162, pp 262–272
  5.Chen DD, Mentens N, Vercauteren F, Roy SS, Cheung RCC, Pao D, Verbauwhede I (2014) High-speed polynomial multiplication architecture for ring-LWE and SHE cryptosystems. IEEE Trans Circuits Syst I Regul Pap. doi:10.​1109/​TCSI.​2014.​2350431
  6.Ducas L, Durmus A, Lepoint T, Lyubashevsky V (2013) Lattice signatures and bimodal Gaussians. In: CRYPTO 2013. LNCS, vol 8042, pp 40–56
  7.Güneysu T, Lyubashevsky V, Pöppelmann T (2012) Practical lattice-based cryptography: a signature scheme for embedded systems. In: CHES 2012. LNCS, vol 7428, pp 530–547
  8.Güneysu T, Lyubashevsky V, Pöppelmann T (2014) Lattice-based signatures: optimization and implementation on reconfigurable hardware. IEEE Trans Comput. doi:10.​1109/​TC.​2014.​2346177
  9.Güneysu T, Oder T, Pöppelmann T, Schwabe P (2013) Speed records for lattice-based signatures. In: PqCrypto 2013. LNCS, vol 7932, pp 67–82
  10.Hoffstein J, Silverman JH (1998) NTRU: a ring-based public key Cryptosystem. In: ANTS-III. LNCS, vol 1423, pp 267–288
  11.Karatsuba A, Ofman Y (1962) Multiplication of many-digital numbers by automatic computers. Proc USSR Acad Sci 145:293–294
  12.Knuth D (1997) The art of computer programming volume 2: seminumerical algorithms. Addison-Wesley, Boston
  13.Lee MK, Kim JW, Song JE, Park K (2007) Sliding Window Method for NTRU. In: ANCS 2007. LNCS, vol 4521, pp 432–442
  14.Lee MK, Kim JW, Song JE, Park K (2013) Efficient implementation of NTRU cryptosystem using sliding window methods. IEICE Trans Fundam E96–A(1):206–214
  15.Lindner R, Buchmann J, Doering M (2008) Efficiency improvements for NTRU. In: Sicherheit 2008. LNI, vol 128, pp 163–178
  16.Lyubashevsky V, Peikert C, Regev O (2010) On ideal lattices and learning with errors over rings. In: EUROCRYPT 2010. LNCS, vol 6110, pp 1–23
  17.Peikert C (2014) Lattice cryptography for the internet. In: PQCrypto 2014. LNCS, vol 8772, pp 197–219
  18.Pollard JM (1971) The fast Fourier transform in a finite field. Math Comput 25(114):365–374CrossRef MathSciNet MATH
  19.Pöppelmann T, Güneysu T (2012) Towards efficient arithmetic for lattice-based cryptography on reconfigurable hardware. In: LATINCRYPT 2012. LNCS, vol 7533, pp 139–158
  20.Roy SS, Vercauteren F, Mertens N, Chen DD, Verbauwhede I (2014) Compact ring-LWE cryptoprocessor. In: CHES 2014. LNCS, vol 8731, pp 371–391
  21.Scwabe P (2015) https://​cryptojedi.​org/​crypto/​index.​shtml#lattisigns . Accessed 23 April 2015
  22.Shor PW (1997) Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J Comput 26(5):1484–1509CrossRef MathSciNet MATH
  
• 作者单位：Sedat Akleylek (1) (2)
  Erdem Alkım (3)
  Zaliha Yüce Tok (4)
  
  1. Cryptography and Computer Algebra Group, TU Darmstadt, Darmstadt, Germany
  2. Department of Computer Engineering, Ondokuz Mayıs University, Samsun, Turkey
  3. Department of Mathematics, Ege University, Izmir, Turkey
  4. Institute of Applied Mathematics, Middle East Technical University, Ankara, Turkey
  
• 刊物类别：Computer Science
• 刊物主题：Programming Languages, Compilers and Interpreters
  Processor Architectures
  Computer Science, general
  
• 出版者：Springer Netherlands
• ISSN：1573-0484

文摘

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 \(({\mathbb {Z}}/ p{\mathbb {Z}}) [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 \(({\mathbb {Z}}/ p{\mathbb {Z}}) [x] / (x^{n}+1)\) at least \(80~\%\) and improve the performance of the signature generation and verification process of GLP scheme significantly.