| |
Efficient and secure algorithms for GLV-based scalar multiplication and their implementation on GLV–GLS curves (extended version)
- 作者：Armando Faz-Hernández ; Patrick Longa…
- 关键词：Elliptic curves ; Scalar multiplication ; Side ; channel protection ; GLV method ; GLS method ; GLV–GLS curve ; $$\times $$ × 64 processor ; ARM processor ; NEON vector unit
- 刊名：Journal of Cryptographic Engineering
- 出版年：2015
- 出版时间：April 2015
- 年：2015
- 卷：5
- 期：1
- 页码：31-52
- 全文大小：399 KB
- 参考文献：1. Aranha, D.F., Karabina, K., Longa, P., Gebotys, C.H., López, J.: Faster explicit formulas for computing pairings over ordinary curves. In: Paterson, K.G. (ed.) Advances in cryptology, EUROCRYPT, vol. 6632, pp 48-8. Springer, New York (2011)
2. Bernstein, D.: Cache-timing attacks on AES. href="http://cr.yp.to/antiforgery/cachetiming-20050414.pdf" class="a-plus-plus">http://cr.yp.to/antiforgery/cachetiming-20050414.pdf (2005)
3. Bernstein, D., Birkner, P., Joye, M., Lange, T., Peters, C.: Twisted Edwards curves. In: Vaudenay, S., (ed.) Proceedings of Africacrypt 2008 LNCS, vol. 5023, pp. 389-05. Springer, New York (2008)
4. Bernstein, D., Chuengsatiansup, C., Lange, T., Schwabe, P.: Kummer strikes back: new DH speed records. In: Cryptology ePrint Archive, Report 2014/134 (2014). Available at: href="http://eprint.iacr.org/2014/134" class="a-plus-plus">http://eprint.iacr.org/2014/134
5. Bernstein, D., Duif, N., Lange, T., Schwabe, P., Yang, B.-Y.: High-speed high-security signatures. In: Preneel, B., Takagi, T. (eds.) Proceedings of CHES 2011, LNCS, vol. 6917, pp. 124-42. Springer, New York (2011)
6. Bernstein, D., Lange, T.: eBACS: ECRYPT Benchmarking of Cryptographic Systems. href="http://bench.cr.yp.to/results-dh.html" class="a-plus-plus">http://bench.cr.yp.to/results-dh.html (2013). Accessed 12 Dec 2013
7. Bernstein, D., Schwabe, P.: NEON crypto. In: Prouff, E., Schaumont, P.R. (eds.) Cryptographic Hardware and Embedded Systems, CHES 2012, Lecture Notes in Computer Science, vol. 7428, pp. 320-39. Springer, New York (2012)
8. Bos, J.W., Costello, C., Hisil, H., Lauter, K.: Fast cryptography in genus 2. In: Johansson, T., Nguyen, P.Q. (eds.) Advances in Crytology, EUROCRYPT, LNCS, vol. 7881, pp. 194-10. Springer, New York (2013)
9. Bos, J.W., Costello, C., Hisil, H., Lauter, K.: High-performance scalar multiplication using 8-dimensional GLV/GLS decomposition. In: Bertoni, G., Coron, J.-S. (eds.) Cryptographic Hardware and Embedded Systems, CHES 2013, LNCS, vol. 8086, pp. 331-48. Springer, New York (2013)
10. Bos, J.W., Costello, C., Longa, P., Naehrig, M.: Selecting elliptic curves for cryptography: an efficiency and security analysis. In: Proceedings of Cryptology ePrint Archive, Report 2014/130 (2014). Available at: href="http://eprint.iacr.org/2014/130" class="a-plus-plus">http://eprint.iacr.org/2014/130
11. Brumley, D., Boneh, D.: Remote timing attacks are practical. In: Mangard, S., Standaert, F.-X. (eds.) Proceedings of the 12th USENIX Security Symposium, LNCS, vol. 6225, pp. 80-4. Springer, New York (2003)
12. Faz-Hernández, A., Longa, P., Sánchez, A.H.: Efficient and secure algorithms for GLV-based scalar multiplication and their implementation on GLV-GLS curves. In: Benaloh, J. (ed.) Topics in Cryptology, CT-RSA 2014, vol. 8366, pp. 1-7. Springer, New York (2014)
13. Feng, M., Zhu, B.B. Xu, M., Li, S.: Efficient comb elliptic curve multiplication methods resistant to power analysis. In: Proceedings of Cryptology ePrint Archive, Report 2005/222 (2005). Available at: href="http://eprint.iacr.org/2005/222" class="a-plus-plus">http://eprint.iacr.org/2005/222
14. Feng, M., Zhu, B.B., Zhao, C., Li, S.: Signed MSB-set comb method for elliptic curve point multiplication. In: Chen, K., Deng, R., Lai, X., Zhou, J. (eds) Proceedings of Information Security Practice and Experience (ISPEC 2006), LNCS, vol. 3903, pp. 13-4. Springer, New York (2006)
15. Galbraith, SD, Lin, X, Scott, M (2011) Endomorphisms for faster elliptic curve cryptography on a large class of curves. J. Cryptol. 24: pp. 446-469 href="http://dx.doi.org/10.1007/s00145-010-9065-y" target="_blank" title="It opens in new window">CrossRef
16. Galbraith, S.D., Lin, X., Scott, M.: Endomorphisms for faster elliptic curve cryptography on a large class of curves. In: Joux, A. (ed.) Advances in Cryptology, EUROCRYPT, LNCS, vol. 5479, pp. 518-35. Springer, New York (2009)
17. Gallant, R.P., Lambert, J.L., Vanstone, S.A.: Faster point multiplication on elliptic curves with efficient endomorphisms. In: Kilian, J. (ed.) Advances in Cryptology, CRYPTO, LNCS, vol. 2139, pp. 190-00. Springer, New York (2001)
18. Guillevic, A., Ionica, S.: Four dimensional GLV via the weil restriction. In: Sako, K., Sarkar, P. (eds.) Advances in Cryptology, ASIACRYPT, LNCS, vol. 8269, pp. 79-6. Springer, New York (2013)
19. Hamburg, M.: Fast and compact elliptic-curve cryptography. In: Proceedings of Cryptology ePrint Archive, Report 2012/309 (2012). Available at: href="http://eprint.iacr.org/2012/309" class="a-plus-plus">http://eprint.iacr.org/2012/309
20. Hankerson, D, Karabina, K, Menezes, A (2009) Analyzing the Galbraith–Lin–Scott point multiplication method for elliptic curves over binary fields. IEEE Trans. Comput. 58: pp. 1411-1420 href="http://dx.doi.org/10.1109/TC.2009.61" target - 刊物类别：Computer Science
- 出版者：Springer Berlin / Heidelberg
- ISSN：2190-8516
文摘
We propose efficient algorithms and formulas that improve the performance of side channel protected elliptic curve computations with special focus on scalar multiplication exploiting the Gallant–Lambert–Vanstone (CRYPTO 2001) and Galbraith–Lin–Scott (EUROCRYPT 2009) methods. Firstly, by adapting Feng et al.’s recoding to the GLV setting, we derive new regular algorithms for variable-base scalar multiplication that offer protection against simple side-channel and timing attacks. Secondly, we propose an efficient, side-channel protected algorithm for fixed-base scalar multiplication which combines Feng et al.’s recoding with Lim-Lee’s comb method. Thirdly, we propose an efficient technique that interleaves ARM and NEON-based multiprecision operations over an extension field to improve performance of GLS curves on modern ARM processors. Finally, we showcase the efficiency of the proposed techniques by implementing a state-of-the-art GLV–GLS curve in twisted Edwards form defined over \(\mathbb {F}_{p^2}\) , which supports a four-dimensional decomposition of the scalar and is fully protected against timing attacks. Analysis and performance results are reported for modern \(\times \) 64 and ARM processors. For instance, we compute a variable-base scalar multiplication in 89,000 and 244,000 cycles on an Intel Ivy Bridge and an ARM Cortex-A15 processor (respect.); using a precomputed table of 6KB, we compute a fixed-base scalar multiplication in 49,000 and 116,000 cycles (respect.); and using a precomputed table of 3KB, we compute a double-scalar multiplication in 115,000 and 285,000 cycles (respect.). The proposed techniques represent an important improvement of the state-of-the-art performance of elliptic curve computations, and allow us to set new speed records in several modern processors. The techniques also reduce the cost of adding protection against timing attacks in the computation of GLV-based variable-base scalar multiplication to below 10?%. This work is the extended version of a publication that appeared at CT-RSA (Faz-Hernández et al. Topics in Cryptology, CT-RSA 2014, vol. 8366, pp. 1-7 2014).
| |
NGLC 2004-2010.National Geological Library of China All Rights Reserved.
Add:29 Xueyuan Rd,Haidian District,Beijing,PRC. Mail Add: 8324 mailbox 100083
For exchange or info please contact us via email.
| |
