Recovering the Secret on Binary Ring-LWE problem with Random Known bits
Resumo
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.
Referências
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.
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.
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.
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.
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. https://eprint.iacr.org/2020/292.
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.
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.
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.
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.
Wunderer, T. (2016). Revisiting the hybrid attack: Improved analysis and refined security estimates. Cryptology ePrint Archive.
