Recovery of the secret on Binary Ring-LWE problem using random known bits - Extended Version
DOI:
https://doi.org/10.5753/jisa.2024.3871Keywords:
Postquantum cryptography , Ring-LWE problem , Binary Ring-LWE problem, Internet of ThingsAbstract
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
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].
