Recovery of the secret on Binary Ring-LWE problem using random known bits - Extended Version

Authors

DOI:

https://doi.org/10.5753/jisa.2024.3871

Keywords:

Postquantum cryptography, Ring-LWE problem, Binary Ring-LWE problem, Internet of Things

Abstract

There are cryptographic systems that are secure against attacks by both quantum and classical computers. Some of these systems are based on the Binary Ring-LWE problem which is presumed to be difficult to solve even on a quantum computer. This problem is considered secure for IoT (Internet of things) devices with limited resources. In Binary Ring-LWE, a polynomial a is selected randomly and a polynomial b is calculated as b = a.s + e where the secret s and the noise e are polynomials with binary coefficients. The polynomials b and a are public and the secret s is hard to find. However, there are Side Channel Attacks that can be applied to retrieve some coefficients (random known bits) of s and e. In this work, we analyze that the secret s can be retrieved successfully having at least 50% of random known bits of s and e.

Downloads

Download data is not yet available.

Author Biographies

Reynaldo Caceres Villena, Universidade de São Paulo

PhD student
at the Department of Computer Science, USP,
Brazil, received his MSc degree in Computer
Science from USP.

Routo Terada, Universidade de São Paulo

Professor at the Department
of Computer Science, University of São Paulo -
USP -, Brazil, MSc in Applied Math from USP
and PhD in Computer Science from University
of Wisconsin-Madison, USA.

References

Albrecht, M. R. (2017). On dual lattice attacks against small-secret lwe and parameter choices in helib and seal. In Advances in Cryptology-EUROCRYPT 2017: 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30-May 4, 2017, Proceedings, Part II, pages 103-129. Springer. DOI: 10.1007/978-3-319-56614-6_4.

Alkim, E., Ducas, L., Pöppelmann, T., and Schwabe, P. (2016). Newhope without reconciliation. [link].

Applebaum, B., Cash, D., Peikert, C., and Sahai, A. (2009). Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In Advances in Cryptology-CRYPTO 2009: 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2009. Proceedings, pages 595-618. Springer. DOI: 10.1007/978-3-642-03356-8_35.

Aysu, A., Orshansky, M., and Tiwari, M. (2018). Binary ring-lwe hardware with power side-channel countermeasures. In 2018 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 1253-1258. IEEE. DOI: 10.23919/DATE.2018.8342207.

Bogdanov, A., Knudsen, L. R., Leander, G., Paar, C., Poschmann, A., Robshaw, M. J., Seurin, Y., and Vikkelsoe, C. (2007). Present: An ultra-lightweight block cipher. In Cryptographic Hardware and Embedded Systems-CHES 2007: 9th International Workshop, Vienna, Austria, September 10-13, 2007. Proceedings 9, pages 450-466. Springer. DOI: 10.1007/978-3-540-74735-2_31.

Brakerski, Z., Gentry, C., and Vaikuntanathan, V. (2014). (leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory (TOCT), 6(3):1-36. DOI: 10.1145/2090236.2090262.

Buchmann, J., Göpfert, F., Güneysu, T., Oder, T., and Pöppelmann, T. (2016a). High-performance and lightweight lattice-based public-key encryption. In Proceedings of the 2nd ACM international workshop on IoT privacy, trust, and security, pages 2-9. DOI: 10.1145/2899007.2899011.

Buchmann, J., Göpfert, F., Player, R., and Wunderer, T. (2016b). On the hardness of lwe with binary error: Revisiting the hybrid lattice-reduction and meet-in-the-middle attack. In Progress in Cryptology-AFRICACRYPT 2016: 8th International Conference on Cryptology in Africa, Fes, Morocco, April 13-15, 2016, Proceedings, pages 24-43. Springer. DOI: 10.1007/978-3-319-31517-1_2.

Dachman-Soled, D., Ducas, L., Gong, H., and Rossi, M. (2020). Lwe with side information: Attacks and concrete security estimation. Cryptology ePrint Archive, Paper 2020/292. Available online [link].

Fan, J. and Verbauwhede, I. (2012). An updated survey on secure ecc implementations: Attacks, countermeasures and cost. Cryptography and Security: From Theory to Applications: Essays Dedicated to Jean-Jacques Quisquater on the Occasion of His 65th Birthday, pages 265-282. DOI: 10.1007/978-3-642-28368-0_18.

Goldwasser, S., Kalai, Y. T., Peikert, C., and Vaikuntanathan, V. (2010). Robustness of the learning with errors assumption. Available at: [link].

Gong, D.-S. D. D. L. and Ristenpart, H. R. M. M. D. (2020). T lwe with side information: attacks and concrete security estimation. In Advances in Cryptology-CRYPTO, volume 2020. Available online [link].

Göpfert, F., van Vredendaal, C., and Wunderer, T. (2017). A hybrid lattice basis reduction and quantum search attack on lwe. In Post-Quantum Cryptography: 8th International Workshop, PQCrypto 2017, Utrecht, The Netherlands, June 26-28, 2017, Proceedings 8, pages 184-202. Springer. DOI: 10.1007/978-3-319-59879-6_11.

Göttert, N., Feller, T., Schneider, M., Buchmann, J., and Huss, S. (2012). On the design of hardware building blocks for modern lattice-based encryption schemes. In Cryptographic Hardware and Embedded Systems-CHES 2012: 14th International Workshop, Leuven, Belgium, September 9-12, 2012. Proceedings 14, pages 512-529. Springer. DOI: 10.1007/978-3-642-33027-8_30.

Lyubashevsky, V., Peikert, C., and Regev, O. (2013). On ideal lattices and learning with errors over rings. Journal of the ACM (JACM), 60(6):1-35. DOI: 10.1007/978-3-642-13190-5_1.

Pöppelmann, T., Oder, T., and Güneysu, T. (2015). High-performance ideal lattice-based cryptography on 8-bit atxmega microcontrollers. In International conference on cryptology and information security in Latin America, pages 346-365. Springer. DOI: 10.1007/978-3-319-22174-8_19.

Roy, S. S., Karmakar, A., and Verbauwhede, I. (2016). Ring-lwe: applications to cryptography and their efficient realization. In Security, Privacy, and Applied Cryptography Engineering: 6th International Conference, SPACE 2016, Hyderabad, India, December 14-18, 2016, Proceedings 6, pages 323-331. Springer. DOI: 10.1007/978-3-319-49445-6_18.

Roy, S. S., Vercauteren, F., Mentens, N., Chen, D. D., and Verbauwhede, I. (2014). Compact ring-lwe cryptoprocessor. In Cryptographic Hardware and Embedded Systems-CHES 2014: 16th International Workshop, Busan, South Korea, September 23-26, 2014. Proceedings 16, pages 371-391. Springer. DOI: 10.1007/978-3-662-44709-3_21.

Villena, R. C. and Terada, R. (2023). Recovery of the secret on binary ring-lwe problem using random known bits. In Anais do XXII Simpósio Brasileiro em Segurança da Informação e de Sistemas Computacionais. Sociedade Brasileira de Computação (short paper). DOI: 10.5753/sbseg.2023.233103.

Wunderer, T. (2016). Revisiting the hybrid attack: Improved analysis and refined security estimates. Cryptology ePrint Archive, Paper 2016/733. Available online [link].

Downloads

Published

2024-04-29

How to Cite

Villena, R. C., & Terada, R. (2024). Recovery of the secret on Binary Ring-LWE problem using random known bits - Extended Version. Journal of Internet Services and Applications, 15(1), 39–45. https://doi.org/10.5753/jisa.2024.3871

Issue

Section

Research article