Top

Published in:

2019 | OriginalPaper | Chapter

Efficiently Masking Binomial Sampling at Arbitrary Orders for Lattice-Based Crypto

Authors : Tobias Schneider, Clara Paglialonga, Tobias Oder, Tim Güneysu

Published in: Public-Key Cryptography – PKC 2019

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

With the rising popularity of lattice-based cryptography, the Learning with Errors (LWE) problem has emerged as a fundamental core of numerous encryption and key exchange schemes. Many LWE-based schemes have in common that they require sampling from a discrete Gaussian distribution which comes with a number of challenges for the practical instantiation of those schemes. One of these is the inclusion of countermeasures against a physical side-channel adversary. While several works discuss the protection of samplers against timing leaks, only few publications explore resistance against other side-channels, e.g., power. The most recent example of a protected binomial sampler (as used in key encapsulation mechanisms to sufficiently approximate Gaussian distributions) from CHES 2018 is restricted to a first-order adversary and cannot be easily extended to higher protection orders.

In this work, we present the first protected binomial sampler which provides provable security against a side-channel adversary at arbitrary orders. Our construction relies on a new conversion between Boolean and arithmetic (B2A) masking schemes for prime moduli which outperforms previous algorithms significantly for the relevant parameters, and is paired with a new masked bitsliced sampler allowing secure and efficient sampling even at larger protection orders. Since our proposed solution supports arbitrary moduli, it can be utilized in a large variety of lattice-based constructions, like NewHope, LIMA, Saber, Kyber, HILA5, or Ding Key Exchange.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter More Efficient Algorithms for the NTRU Key Generation Using the Field Norm

next chapter Decryption Failure Attacks on IND-CCA Secure Lattice-Based Schemes

In the full version of this paper, all algorithms are given as supplementary material.

The authors of [6] also hint that the k-independent algorithm of [7] can be adopted to other moduli. However, we did not find a working solution. Nevertheless, an adapted algorithm would share the exponential complexity of the original making it only viable for small number of shares and, therefore, not a generic solution for masking at any order. In addition, the bit sizes considered in our case study are relatively small which would further decrease the benefit of a prime-adjusted algorithm.

\(\mathtt {SecMul}\) is implemented similar to \(\mathtt {SecAnd}\) of [14].

Note that there are order-optimized algorithms which can provide an even better performance for specific values of t (i.e., Goubin [19] for \(t=1\), and Hutter and Tunstall [21] for \(t=2\)). However, for power-of-two moduli our \(\mathtt {SecB2A}_q\) is only competitive for larger values of t, and we, thus, exclude these specific examples from the comparison.

Note that there is typo in the final equation: \(T_n' = 2n + T_n + B_n + 3n^2 + n\).

In the full version of the paper we derive the complexity of the remaining algorithms.

It was shown in [13] that the logarithmic adder offers a significant improvement over the linear approach for \(k>32\) at first-order.

In contrast to [25], our cycle counts do not include the generation of the input bit vectors. Therefore, our 3,757 cycles for one sample do not match the 6 million cycles for 1024 coefficients reported in [25]. However, as the generation of the input samples is a constant overhead that is independent from the sampling algorithm or the \(\mathtt {B2A}_q\) conversion, we decided to exclude it from our measurements.

Alkim, E., et al.: NewHope algorithm specifications and supporting documentation. https://newhopecrypto.org/data/NewHope_2017_12_21.pdf. Accessed 09 May 2018

Alkim, E., Jakubeit, P., Schwabe, P.: NewHope on ARM Cortex-M. In: Carlet, C., Hasan, M.A., Saraswat, V. (eds.) SPACE 2016. LNCS, vol. 10076, pp. 332–349. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-49445-6_19CrossRef

Avanzi, R., et al.: CRYSTALS-Kyber. Technical report, National Institute of Standards and Technology (2017). https://pq-crystals.org/kyber/data/kyber-specification.pdf

Barthe, G., Belaïd, S., Dupressoir, F., Fouque, P., Grégoire, B.: Compositional verification of higher-order masking: application to a verifying masking compiler. IACR Cryptology ePrint Archive, 2015:506 (2015)

Barthe, G., et al.: Strong non-interference and type-directed higher-order masking. In: ACM CCS 2016, pp. 116–129. ACM (2016)

Barthe, G., et al.: Masking the GLP lattice-based signature scheme at any order. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 354–384. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_12CrossRef

Bettale, L., Coron, J., Zeitoun, R.: Improved high-order conversion from Boolean to arithmetic masking. TCHES 2018, 22–45 (2018)

Biryukov, A., Dinu, D., Corre, Y.L., Udovenko, A.: Optimal first-order Boolean masking for embedded IoT devices. In: Eisenbarth, T., Teglia, Y. (eds.) CARDIS 2017. LNCS, vol. 10728, pp. 22–41. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-75208-2_2CrossRef

Chari, S., Jutla, C.S., Rao, J.R., Rohatgi, P.: Towards sound approaches to counteract power-analysis attacks. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 398–412. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_26CrossRef

10.

Chen, C., Eisenbarth, T., von Maurich, I., Steinwandt, R.: Differential power analysis of a McEliece cryptosystem. In: Malkin, T., Kolesnikov, V., Lewko, A.B., Polychronakis, M. (eds.) ACNS 2015. LNCS, vol. 9092, pp. 538–556. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-28166-7_26CrossRef

11.

Chen, C., Eisenbarth, T., von Maurich, I., Steinwandt, R.: Masking large keys in hardware: a masked implementation of McEliece. In: Dunkelman, O., Keliher, L. (eds.) SAC 2015. LNCS, vol. 9566, pp. 293–309. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-31301-6_18CrossRefMATH

12.

Coron, J.-S.: High-order conversion from Boolean to arithmetic masking. In: Fischer, W., Homma, N. (eds.) CHES 2017. LNCS, vol. 10529, pp. 93–114. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66787-4_5CrossRef

13.

Coron, J.-S., Großschädl, J., Tibouchi, M., Vadnala, P.K.: Conversion from arithmetic to Boolean masking with logarithmic complexity. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 130–149. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48116-5_7CrossRef

14.

Coron, J.-S., Großschädl, J., Vadnala, P.K.: Secure conversion between Boolean and arithmetic masking of any order. In: Batina, L., Robshaw, M. (eds.) CHES 2014. LNCS, vol. 8731, pp. 188–205. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44709-3_11CrossRefMATH

15.

D’Anvers, J.-P., Karmakar, A., Roy, S.S., Vercauteren, F.: SABER: Mod-LWR based KEM. Technical report, National Institute of Standards and Technology (2017). https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions

16.

Debraize, B.: Efficient and provably secure methods for switching from arithmetic to Boolean masking. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol. 7428, pp. 107–121. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33027-8_7CrossRefMATH

17.

Ding, J., Takagi, T., Gao, X., Wang, Y.: Ding Key Exchange. Technical report, National Institute of Standards and Technology (2017). https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions

18.

Eisenbarth, T., Kasper, T., Moradi, A., Paar, C., Salmasizadeh, M., Shalmani, M.T.M.: On the power of power analysis in the real world: a complete break of the KeeLoq code hopping scheme. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 203–220. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_12CrossRefMATH

19.

Goubin, L.: A sound method for switching between Boolean and arithmetic masking. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 3–15. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44709-1_2CrossRef

20.

Güneysu, T., Lyubashevsky, V., Pöppelmann, T.: Practical lattice-based cryptography: a signature scheme for embedded systems. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol. 7428, pp. 530–547. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33027-8_31CrossRefMATH

21.

Hutter, M., Tunstall, M.: Constant-time higher-order Boolean-to-arithmetic masking. IACR Cryptology ePrint Archive, 2016:1023 (2016)

22.

Ishai, Y., Sahai, A., Wagner, D.A.: Private circuits: securing hardware against probing attacks. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 463–481. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_27CrossRef

23.

Karroumi, M., Richard, B., Joye, M.: Addition with blinded operands. In: Prouff, E. (ed.) COSADE 2014. LNCS, vol. 8622, pp. 41–55. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10175-0_4CrossRef

24.

Kocher, P.C.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68697-5_9CrossRef

25.

Oder, T., Schneider, T., Pöppelmann, T., Güneysu, T.: Practical CCA2-secure and masked ring-LWE implementation. TCHES 2018, 142–174 (2018)

26.

National Institute of Standards and Technology. Post-quantum cryptography - round 1 submissions. https://csrc.nist.gov/projects/post-quantum-cryptography/round-1-submissions. Accessed 10 Dec 2018

27.

National Institute of Standards and Technology. Submission requirements and evaluation criteria for the post-quantum cryptography standardization process. https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf. Accessed 10 May 2018

28.

Reparaz, O., Roy, S.S., de Clercq, R., Vercauteren, F., Verbauwhede, I.: Masking ring-LWE. J. Crypt. Eng. 6(2), 139–153 (2016)CrossRef

29.

Saarinen, M.-J.O.: HILA5. Technical report, National Institute of Standards and Technology (2017). https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions

30.

Schneider, T., Moradi, A., Güneysu, T.: Arithmetic addition over Boolean masking towards first- and second-order resistance in hardware. In: Malkin, T., Kolesnikov, V., Lewko, A.B., Polychronakis, M. (eds.) ACNS 2015. LNCS, vol. 9092, pp. 559–578. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-28166-7_27CrossRefMATH

31.

Smart, N.P., et al.: LIMA-1.1: a PQC encryption scheme. Technical report, National Institute of Standards and Technology (2017). https://lima-pq.github.io/files/lima-pq.pdf

32.

Standaert, F.-X., et al.: The world is not enough: another look on second-order DPA. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 112–129. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17373-8_7CrossRef

33.

Won, Y.-S., Han, D.-G.: Efficient conversion method from arithmetic to Boolean masking in constrained devices. In: Guilley, S. (ed.) COSADE 2017. LNCS, vol. 10348, pp. 120–137. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-64647-3_8CrossRef

Title: Efficiently Masking Binomial Sampling at Arbitrary Orders for Lattice-Based Crypto
Authors: Tobias Schneider
Clara Paglialonga
Tobias Oder
Tim Güneysu
Publisher: Springer International Publishing
Book: Public-Key Cryptography – PKC 2019
Print ISBN: 978-3-030-17258-9

Electronic ISBN: 978-3-030-17259-6

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-17259-6_18

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner