On the number of binary signed digit representations of a given weight

Jiří Tůma; Jiří Vábek

Commentationes Mathematicae Universitatis Carolinae (2015)

  • Volume: 56, Issue: 3, page 287-306
  • ISSN: 0010-2628

Abstract

top
Binary signed digit representations (BSDR’s) of integers have been studied since the 1950’s. Their study was originally motivated by multiplication and division algorithms for integers and later by arithmetics on elliptic curves. Our paper is motivated by differential cryptanalysis of hash functions. We give an upper bound for the number of BSDR’s of a given weight. Our result improves the upper bound on the number of BSDR’s with minimal weight stated by Grabner and Heuberger in On the number of optimal base 2 representations, Des. Codes Cryptogr. 40 (2006), 25–39, and introduce a new recursive upper bound for the number of BSDR’s of any given weight.

How to cite

top

Tůma, Jiří, and Vábek, Jiří. "On the number of binary signed digit representations of a given weight." Commentationes Mathematicae Universitatis Carolinae 56.3 (2015): 287-306. <http://eudml.org/doc/271605>.

@article{Tůma2015,
abstract = {Binary signed digit representations (BSDR’s) of integers have been studied since the 1950’s. Their study was originally motivated by multiplication and division algorithms for integers and later by arithmetics on elliptic curves. Our paper is motivated by differential cryptanalysis of hash functions. We give an upper bound for the number of BSDR’s of a given weight. Our result improves the upper bound on the number of BSDR’s with minimal weight stated by Grabner and Heuberger in On the number of optimal base $2$ representations, Des. Codes Cryptogr. 40 (2006), 25–39, and introduce a new recursive upper bound for the number of BSDR’s of any given weight.},
author = {Tůma, Jiří, Vábek, Jiří},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {binary signed digit representation; NAF; minimal weight},
language = {eng},
number = {3},
pages = {287-306},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {On the number of binary signed digit representations of a given weight},
url = {http://eudml.org/doc/271605},
volume = {56},
year = {2015},
}

TY - JOUR
AU - Tůma, Jiří
AU - Vábek, Jiří
TI - On the number of binary signed digit representations of a given weight
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2015
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 56
IS - 3
SP - 287
EP - 306
AB - Binary signed digit representations (BSDR’s) of integers have been studied since the 1950’s. Their study was originally motivated by multiplication and division algorithms for integers and later by arithmetics on elliptic curves. Our paper is motivated by differential cryptanalysis of hash functions. We give an upper bound for the number of BSDR’s of a given weight. Our result improves the upper bound on the number of BSDR’s with minimal weight stated by Grabner and Heuberger in On the number of optimal base $2$ representations, Des. Codes Cryptogr. 40 (2006), 25–39, and introduce a new recursive upper bound for the number of BSDR’s of any given weight.
LA - eng
KW - binary signed digit representation; NAF; minimal weight
UR - http://eudml.org/doc/271605
ER -

References

top
  1. Booth A.D., 10.1093/qjmam/4.2.236, Quart. J. Mech. Appl. Math. 4 (1951), 236–240. Zbl0043.12902MR0041526DOI10.1093/qjmam/4.2.236
  2. Reitwiesner G., Binary arithmetic, in Advances in Computers, 1, Academic Press, New York, 1960, pp. 231–308. MR0122018
  3. Morain F., Olivos J., Speeding up the computations on an elliptic curve using addition-subtraction chains, RAIRO Inform. Théor. Appl. 24 (1990), 531–543. Zbl0724.11068MR1082914
  4. Koyama K., Tsuruoka Y., Speeding up elliptic cryptosystems by using a signed binary window method, Advances in cryptology - CRYPTO' 92, Lecture Notes in Comput. Sci., 740, Springer, Berlin, 1993, pp. 345–357. Zbl0816.94016MR1287864
  5. Miyaji A., Ono T., Cohen H., 10.1007/BFb0028484, Information and Communications Security, Lecture Notes in Comput. Sci., 1334, Springer, Berlin-Heidelberg, 1997, pp. 282–290. Zbl0939.11039DOI10.1007/BFb0028484
  6. Solinas J., 10.1023/A:1008306223194, Des. Codes Cryptogr. 19 (2000), 195–249. Zbl0997.94017MR1759617DOI10.1023/A:1008306223194
  7. Oswald E., Aigner M., Randomized addition-subtraction chains as a countermeasure against power attacks, Cryptographic Hardware and Embedded Systems – CHES 2001, Lecture Notes in Comput. Sci., 2162, Springer, Berlin, 2001, pp. 39–50. Zbl1012.94549MR1945397
  8. Ha J., Moon S., Randomized signed-scalar multiplication of ECC to resist power attacks, Cryptographic Hardware and Embedded Systems – CHES 2002, Lecture Notes in Comput. Sci., 2523, Springer, Berlin-Heidelberg, 2002, pp. 551–563. 
  9. Ebeid N., Anwar Hasan M., On randomized private keys to counteract DPA attacks, in Matsui M., Zuccherato R. (ed.), SAC 2003, Lecture Notes in Comput. Sci., 3006, Springer, Berlin, 2004, pp. 58–72. MR2094721
  10. Heuberger C., 10.1007/s10998-004-0523-x, Period. Math. Hungar. 49 (2004), no. 2, 65–89. MR2106466DOI10.1007/s10998-004-0523-x
  11. Xiaoyu R., Katti R., Left-to-right optimal signed-binary representation of a pair of integers, IEEE Trans. Comput. 54 (2005), 132–140. 
  12. Muir J.A., Stinson D.R., Minimality and other properties of the width-w nonadjacent form, Math. Comp. 75 (2006), no. 253, 369–384. Zbl1091.94026MR2176404
  13. Heuberger C., Prodinger H., 10.1007/s00605-005-0364-6, Monatsh. Math. 147 (2006), 219–248. Zbl1094.11007MR2215565DOI10.1007/s00605-005-0364-6
  14. Grabner P.J., Heuberger C., 10.1007/s10623-005-6158-y, Des. Codes Cryptogr. 40 (2006), 25–39. Zbl1261.11003MR2226281DOI10.1007/s10623-005-6158-y
  15. Stevens M., Lenstra A., de Weger B., Chosen-prefix collisions for MD 5 and colliding X. 509 certificates for different identities, Advances in cryptology – EUROCRYPT 2007 (Moni Naor, ed.), Lecture Notes in Comput. Sci., 4515, Springer, Berlin, 2007, pp. 1–22. MR2449200
  16. Kim T.H., Han D., Okeya K., Lim J.I., 10.4218/etrij.07.0106.0220, ETRI Journal, vol. 29, no. 5, Oct. 2007, pp. 619–632. DOI10.4218/etrij.07.0106.0220
  17. Bang-ju Wang, Huan-guo Zhang, Zhang-yi Wang, Yu-hua Wang, 10.1007/978-3-540-73417-8_35, Multimedia Content Analysis and Mining, Lecture Notes in Comput. Sci., 4577, Springer, Berlin-Heidelberg, 2007, pp. 277–285. DOI10.1007/978-3-540-73417-8_35
  18. Vábek J., Joščák D., Boháček M., Tůma J., A new type of 2 -block collisions in MD 5 , in Chowdury, Rijmen, Das (ed.), Progress in cryptology – INDOCRYPT 2008, Lecture Notes in Comput. Sci., 5365, Springer, Berlin, 2008, pp. 78-90. MR2546237
  19. Wu T., Zhang M., Du H., Wang R., 10.1007/s11766-010-2241-x, Appl. Math. J. Chinese Univ. Ser.B 25 (2010), no. 3, 331–340. MR2679352DOI10.1007/s11766-010-2241-x
  20. Avanzi R., Heuberger C., Prodinger H., 10.1007/s10623-010-9396-6, Des. Codes Cryptogr. 58 (2011), no. 2, 173–202. Zbl1230.94003MR2770310DOI10.1007/s10623-010-9396-6

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.