×

zbMATH — the first resource for mathematics

Square always exponentiation. (English) Zbl 1291.94069
Bernstein, Daniel J. (ed.) et al., Progress in cryptology – INDOCRYPT 2011. 12th international conference on cryptology in India, Chennai, India, December 11–14, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-25577-9/pbk). Lecture Notes in Computer Science 7107, 40-57 (2011).
Summary: Embedded exponentiation techniques have become a key concern for security and efficiency in hardware devices using public key cryptography. An exponentiation is basically a sequence of multiplications and squarings, but this sequence may reveal exponent bits to an attacker on an unprotected implementation. Although this subject has been covered for years, we present in this paper new exponentiation algorithms based on trading multiplications for squarings. Our method circumvents attacks aimed at distinguishing squarings from multiplications at a lower cost than previous techniques. Last but not least, we present new algorithms using two parallel squaring blocks which provide the fastest exponentiation to our knowledge.
For the entire collection see [Zbl 1228.94001].

MSC:
94A60 Cryptography
68M07 Mathematical problems of computer architecture
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Amiel, F., Feix, B., Marcel, L., Villegas, K.: Passive and Active Combined Attacks. In: Workshop on Fault Detection and Tolerance in Cryptography - FDTC  2007, IEEE Computer Society Press, Los Alamitos (2007)
[2] Amiel, F., Feix, B., Tunstall, M., Whelan, C., Marnane, W.P.: Distinguishing Multiplications from Squaring Operations. In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) SAC 2008. LNCS, vol. 5381, pp. 346–360. Springer, Heidelberg (2009) · Zbl 1256.94038 · doi:10.1007/978-3-642-04159-4_22
[3] Barrett, P.: Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 311–323. Springer, Heidelberg (1987) · doi:10.1007/3-540-47721-7_24
[4] Chevallier-Mames, B., Ciet, M., Joye, M.: Low-Cost Solutions for Preventing Simple Side-Channel Analysis: Side-Channel Atomicity. IEEE Transactions on Computers 53(6), 760–768 (2004) · Zbl 1300.94045 · doi:10.1109/TC.2004.13
[5] Coron, J.-S.: Resistance Against Differential Power Analysis for Elliptic Curve Cryptosystems. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 292–302. Springer, Heidelberg (1999) · Zbl 0955.94009 · doi:10.1007/3-540-48059-5_25
[6] Diffie, W., Hellman, M.E.: New Directions in Cryptography. IEEE Transactions on Information Theory 22(6), 644–654 (1976) · Zbl 0435.94018 · doi:10.1109/TIT.1976.1055638
[7] FIPS PUB 186-3. Digital Signature Standard. National Institute of Standards and Technology (October 2009)
[8] Fouque, P.-A., Valette, F.: The Doubling Attack – Why Upwards is Better Than Downwards. In: Walter, C.D., Koç, Ç.K., Paar, C. (eds.) CHES 2003. LNCS, vol. 2779, pp. 269–280. Springer, Heidelberg (2003) · Zbl 1274.94066 · doi:10.1007/978-3-540-45238-6_22
[9] Hankerson, D., Menezes, A.J., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer Professional Computing Series (January 2003) · Zbl 1059.94016
[10] Joye, M., Yen, S.-M.: The Montgomery Powering Ladder. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 291–302. Springer, Heidelberg (2003) · Zbl 1020.11500 · doi:10.1007/3-540-36400-5_22
[11] Kocher, P., Jaffe, J., Jun, B.: Introduction to Differential Power Analysis and Related Attacks (1998)
[12] 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) · Zbl 1329.94070 · doi:10.1007/3-540-68697-5_9
[13] Kocher, P.C., Jaffe, J., Jun, B.: Differential Power Analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999) · Zbl 0942.94501 · doi:10.1007/3-540-48405-1_25
[14] Menezes, A., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press (1996) · doi:10.1201/9781439821916
[15] Montgomery, P.L.: Speeding the Pollard and Elliptic Curve Methods of Factorization. MC 48, 243–264 (1987) · Zbl 0608.10005
[16] Rivest, R.L., Shamir, A., Adleman, L.: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM 21, 120–126 (1978) · Zbl 0368.94005 · doi:10.1145/359340.359342
[17] Schmidt, J.-M., Tunstall, M., Avanzi, R., Kizhvatov, I., Kasper, T., Oswald, D.: Combined Implementation Attack Resistant Exponentiation. In: Abdalla, M., Barreto, P.S.L.M. (eds.) LATINCRYPT 2010. LNCS, vol. 6212, pp. 305–322. Springer, Heidelberg (2010) · Zbl 1285.94096 · doi:10.1007/978-3-642-14712-8_19
[18] Yen, S.-M., Joye, M.: Checking Before Output Not Be Enough Against Fault-Based Cryptanalysis. IEEE Trans. Computers 49(9), 967–970 (2000) · Zbl 1300.94101 · doi:10.1109/12.869328
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.