Fast verification of masking schemes in characteristic two. (English) Zbl 1479.94296

Canteaut, Anne (ed.) et al., Advances in cryptology – EUROCRYPT 2021. 40th annual international conference on the theory and applications of cryptographic techniques, Zagreb, Croatia, October 17–21, 2021. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 12697, 283-312 (2021).
Summary: We revisit the matrix model for non-interference (NI) probing security of masking gadgets introduced by S. Belaïd et al. [Lect. Notes Comput. Sci. 12107, 311–341 (2020; Zbl 07436949)]. This leads to two main results.

1) We generalise the theorems on which this model is based, so as to be able to apply them to masking schemes over any finite field – in particular \(\mathbb{F}_2\) – and to be able to analyse the strong non-interference (SNI) security notion. We also follow S. Faust et al. [“Composable masking schemes in the presence of physical defaults & the robust probing model”, IACR Trans. Cryptogr. Hardw. Embed. Syst. 2018, No. 3, 89–120 (2018; doi:10.13154/tches.v2018.i3.89-120)] to additionally consider a robust probing model that takes hardware defects such as glitches into account.
2) We exploit this improved model to implement a very efficient verification algorithm that improves the performance of state-of-the-art software by three orders of magnitude. We show applications to variants of NI and SNI multiplication gadgets from [G. Barthe et al., Lect. Notes Comput. Sci. 10210, 535–566 (2017; Zbl 1411.94050)] which we verify to be secure up to order 11 after a significant parallel computation effort, whereas the previous largest proven order was 7; SNI refreshing gadgets; and NI multiplication gadgets from H. Groß et al. [“Domain-oriented masking: compact masked hardware implementations with arbitrary protection order”, in: Proceedings of the 2016 ACM workshop on theory of implementation security, TIS’16, Vienna, Austria, 2016. New York, NY: Association for Computing Machinery (ACM). 3 (2016; doi:10.1145/2996366.2996426)] secure in presence of glitches. We also reduce the randomness cost of some existing gadgets, notably for the implementation-friendly case of 8 shares, improving here the previous best results by 17% (resp. 19%) for SNI multiplication (resp. refreshing).
For the entire collection see [Zbl 1475.94011].


94A62 Authentication, digital signatures and secret sharing
94A60 Cryptography
68P25 Data encryption (aspects in computer science)


maskVerif; Tornado
Full Text: DOI


[1] Barthe, G.; Belaïd, S.; Cassiers, G.; Fouque, P-A; Grégoire, B.; Standaert, F-X; Sako, K.; Schneider, S.; Ryan, PYA, maskVerif: automated verification of higher-order masking in presence of physical defaults, Computer Security - ESORICS 2019, 300-318 (2019), Cham: Springer, Cham
[2] Barthe, G.; Belaïd, S.; Dupressoir, F.; Fouque, P-A; Grégoire, B., Compositional verification of higher-order masking: application to a verifying masking compiler, IACR Cryptology ePrint Archive, 2015, 506 (2015)
[3] Barthe, G., et al.: Strong non-interference and type-directed higher-order masking. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016, pp. 116-129. ACM (2016)
[4] Barthe, G., Improved parallel mask refreshing algorithms: generic solutions with parametrized non-interference & automated optimizations, IACR Cryptology ePrint Archive, 2018, 505 (2018)
[5] Belaïd, S.; Benhamouda, F.; Passelègue, A.; Prouff, E.; Thillard, A.; Vergnaud, D.; Fischlin, M.; Coron, J-S, Randomness complexity of private circuits for multiplication, Advances in Cryptology - EUROCRYPT 2016, 616-648 (2016), Heidelberg: Springer, Heidelberg · Zbl 1371.94624
[6] Belaïd, S.; Benhamouda, F.; Passelègue, A.; Prouff, E.; Thillard, A.; Vergnaud, D.; Katz, J.; Shacham, H., Private multiplication over finite fields, Advances in Cryptology - CRYPTO 2017, 397-426 (2017), Cham: Springer, Cham · Zbl 1418.94031
[7] Barthe, G., et al.: Parallel implementations of masking schemes and the bounded moment leakage model. In: Coron and Nielsen [CN17], pp. 535-566 (2017) · Zbl 1411.94050
[8] Belaïd, S.; Dagand, PÉ; Mercadier, D.; Rivain, M.; Wintersdorff, R.; Canteaut, A.; Ishai, Y., Tornado: automatic generation of probing-secure masked bitsliced implementations, Advances in Cryptology - EUROCRYPT 2020, 311-341 (2020), Cham: Springer, Cham · Zbl 07436949
[9] Bloem, R.; Gross, H.; Iusupov, R.; Könighofer, B.; Mangard, S.; Winter, J.; Nielsen, JB; Rijmen, V., Formal verification of masked hardware implementations in the presence of glitches, Advances in Cryptology - EUROCRYPT 2018, 321-353 (2018), Cham: Springer, Cham · Zbl 1428.94062
[10] Belaïd, S., Goudarzi, D., Rivain, M.: Tight private circuits: achieving probing security with the least refreshing. In: Peyrin and Galbraith [PG18], pp. 343-372 · Zbl 1446.94099
[11] Bordes, N.; Karpman, P., Fast verification of masking schemes in characteristic two, IACR Cryptol. ePrint Arch., 2019, 1165 (2019)
[12] Bronchain, O.; Standaert, F-X, Side-channel countermeasures’ dissection and the limits of closed source security evaluations, IACR Cryptology ePrint Archive, 2019, 1008 (2019)
[13] Coron, J-S; Greuet, A.; Prouff, E.; Zeitoun, R.; Gierlichs, B.; Poschmann, AY, Faster evaluation of SBoxes via common shares, Cryptographic Hardware and Embedded Systems - CHES 2016, 498-514 (2016), Heidelberg: Springer, Heidelberg · Zbl 1411.94055
[14] Coron, J-S; Nielsen, JB, Advances in Cryptology - EUROCRYPT 2017 (2017), Cham: Springer, Cham · Zbl 1360.94005
[15] Duc, A.; Faust, S.; Standaert, F-X; Oswald, E.; Fischlin, M., Making masking security proofs concrete, Advances in Cryptology - EUROCRYPT 2015, 401-429 (2015), Heidelberg: Springer, Heidelberg · Zbl 1370.94508
[16] Fan, J.; Gierlichs, B., Constructive Side-Channel Analysis and Secure Design (2018), Cham: Springer, Cham · Zbl 1439.94001
[17] Faust, S.; Grosso, V.; Pozo, SMD; Paglialonga, C.; Standaert, F-X, Composable masking schemes in the presence of physical defaults & the robust probing model, IACR Trans. Cryptogr. Hardw. Embed. Syst., 2018, 3, 89-120 (2018)
[18] Goudarzi, D., Journault, A., Rivain, M., Standaert, F.-X.: Secure multiplication for bitslice higher-order masking: optimisation and comparison. In: Fan and Gierlichs [FG18], pp. 3-22 · Zbl 1450.94032
[19] Groß, H., Mangard, S., Korak, T.: Domain-oriented masking: compact masked hardware implementations with arbitrary protection order. In: Bilgin, B., Nikova, S., Rijmen, V. (eds.) ACM TIS@CCS 2016, p. 3. ACM (2016)
[20] Gao, S.; Marshall, B.; Page, D.; Oswald, E., Share-slicing: friend or foe?, IACR Trans. Cryptogr. Hardw. Embed. Syst., 2020, 1, 152-174 (2020)
[21] Grégoire, B., Papagiannopoulos, K., Schwabe, P., Stoffelen, K.: Vectorizing higher-order masking. In: Fan and Gierlichs [FG18], pp. 23-43 · Zbl 1450.94034
[22] Goudarzi, D., Rivain, M.: How fast can higher-order masking be in software? In: Coron and Nielsen [CN17], pp. 567-597 · Zbl 1411.94062
[23] Ishai, Y.; Sahai, A.; Wagner, D.; Boneh, D., Private circuits: securing hardware against probing attacks, Advances in Cryptology - CRYPTO 2003, 463-481 (2003), Heidelberg: Springer, Heidelberg · Zbl 1122.94378
[24] Journault, A.; Standaert, F-X; Fischer, W.; Homma, N., Very high order masking: efficient implementation and security evaluation, Cryptographic Hardware and Embedded Systems - CHES 2017, 623-643 (2017), Cham: Springer, Cham · Zbl 1450.94037
[25] Kocher, P.; Jaffe, J.; Jun, B.; Wiener, M., Differential power analysis, Advances in Cryptology — CRYPTO’ 99, 388-397 (1999), Heidelberg: Springer, Heidelberg · Zbl 0942.94501
[26] Knuth, D.E.: Combinatorial Algorithms, Part 1, volume 4A of The Art of Computer Programming. Addison Wesley (2011) · Zbl 1354.68001
[27] Karpman, P., Roche, D.S.: New instantiations of the CRYPTO 2017 masking schemes. In: Peyrin and Galbraith [PG18], pp. 285-314 · Zbl 1446.94143
[28] Knichel, D.; Sasdrich, P.; Moradi, A.; Moriai, S.; Wang, H., SILVER - statistical independence and leakage verification, Advances in Cryptology - ASIACRYPT 2020, 787-816 (2020), Cham: Springer, Cham
[29] Liu, C.N., Tang, D.T.: Enumerating combinations of m out of n objects [G6] (algorithm 452). Commun. ACM 16(8), 485 (1973)
[30] Moos, T.; Moradi, A.; Schneider, T.; Standaert, F-X, Glitch-resistant masking revisited or why proofs in the robust probing model are needed, IACR Trans. Cryptogr. Hardw. Embed. Syst., 2019, 2, 256-292 (2019)
[31] Nijenhuis, A., Wilf, H.S.: Combinatorial Algorithms for Computers and Calculators, 2nd edn. Academic Press, New York (1978) · Zbl 0476.68047
[32] Peyrin, T.; Galbraith, S., Advances in Cryptology - ASIACRYPT 2018 (2018), Cham: Springer, Cham · Zbl 1402.94008
[33] Prange, E., The use of information sets in decoding cyclic codes, IRE Trans. Inf. Theory, 8, 5, 5-9 (1962)
[34] Schwartz, JT, Fast probabilistic algorithms for verification of polynomial identities, J. ACM, 27, 4, 701-717 (1980) · Zbl 0452.68050
[35] Walsh, T.R.: A simple sequencing and ranking method that works on almost all gray codes. Unpublished research report. https://www.labunix.uqam.ca/ walsh_t/papers/sequencing_and_ranking.pdf
[36] Wang, W.; Guo, C.; François-Xavier Standaert, YY; Cassiers, G., Packed multiplication: how to amortize the cost of side-channel masking?, IACR Cryptol. ePrint Arch., 2020, 1103 (2020)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.