| Title:
|
On the number of binary signed digit representations of a given weight (English) |
| Author:
|
Tůma, Jiří |
| Author:
|
Vábek, Jiří |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
56 |
| Issue:
|
3 |
| Year:
|
2015 |
| Pages:
|
287-306 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
binary signed digit representation |
| Keyword:
|
NAF |
| Keyword:
|
minimal weight |
| MSC:
|
11A63 |
| MSC:
|
68R01 |
| idZBL:
|
Zbl 06486994 |
| idMR:
|
MR3390277 |
| DOI:
|
10.14712/1213-7243.2015.129 |
| . |
| Date available:
|
2015-07-09T20:42:41Z |
| Last updated:
|
2017-10-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/144345 |
| . |
| Reference:
|
[1] Booth A.D.: A signed binary multiplication technique.Quart. J. Mech. Appl. Math. 4 (1951), 236–240. Zbl 0043.12902, MR 0041526, 10.1093/qjmam/4.2.236 |
| Reference:
|
[2] Reitwiesner G.: Binary arithmetic.in Advances in Computers, 1, Academic Press, New York, 1960, pp. 231–308. MR 0122018 |
| Reference:
|
[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. Zbl 0724.11068, MR 1082914 |
| Reference:
|
[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. Zbl 0816.94016, MR 1287864 |
| Reference:
|
[5] Miyaji A., Ono T., Cohen H.: Efficient elliptic curve exponentiation.Information and Communications Security, Lecture Notes in Comput. Sci., 1334, Springer, Berlin-Heidelberg, 1997, pp. 282–290. Zbl 0939.11039, 10.1007/BFb0028484 |
| Reference:
|
[6] Solinas J.: Efficient arithmetic on Koblitz curves.Des. Codes Cryptogr. 19 (2000), 195–249. Zbl 0997.94017, MR 1759617, 10.1023/A:1008306223194 |
| Reference:
|
[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. Zbl 1012.94549, MR 1945397 |
| Reference:
|
[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. |
| Reference:
|
[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. MR 2094721 |
| Reference:
|
[10] Heuberger C.: Minimal expansions in redundant number systems: Fibonacci bases and greedy algorithm.Period. Math. Hungar. 49 (2004), no. 2, 65–89. MR 2106466, 10.1007/s10998-004-0523-x |
| Reference:
|
[11] Xiaoyu R., Katti R.: Left-to-right optimal signed-binary representation of a pair of integers.IEEE Trans. Comput. 54 (2005), 132–140. |
| Reference:
|
[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. Zbl 1091.94026, MR 2176404 |
| Reference:
|
[13] Heuberger C., Prodinger H.: Analysis of alternative digit sets for nonadjacent representations.Monatsh. Math. 147 (2006), 219–248. Zbl 1094.11007, MR 2215565, 10.1007/s00605-005-0364-6 |
| Reference:
|
[14] Grabner P.J., Heuberger C.: On the number of optimal base $2$ representations.Des. Codes Cryptogr. 40 (2006), 25–39. Zbl 1261.11003, MR 2226281, 10.1007/s10623-005-6158-y |
| Reference:
|
[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. MR 2449200 |
| Reference:
|
[16] Kim T.H., Han D., Okeya K., Lim J.I.: Differential power analysis on countermeasures using binary signed digit representations.ETRI Journal, vol. 29, no. 5, Oct. 2007, pp. 619–632. 10.4218/etrij.07.0106.0220 |
| Reference:
|
[17] Bang-ju Wang, Huan-guo Zhang, Zhang-yi Wang, Yu-hua Wang: Speeding up scalar multiplication using a new signed binary representation for integers.Multimedia Content Analysis and Mining, Lecture Notes in Comput. Sci., 4577, Springer, Berlin-Heidelberg, 2007, pp. 277–285. 10.1007/978-3-540-73417-8_35 |
| Reference:
|
[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. MR 2546237 |
| Reference:
|
[19] Wu T., Zhang M., Du H., Wang R.: On optimal binary signed digit representation of integers.Appl. Math. J. Chinese Univ. Ser.B 25 (2010), no. 3, 331–340. MR 2679352, 10.1007/s11766-010-2241-x |
| Reference:
|
[20] Avanzi R., Heuberger C., Prodinger H.: Redundant $\tau$-adic expansions I: non-adjacent digit sets and their applications to scalar multiplication.Des. Codes Cryptogr. 58 (2011), no. 2, 173–202. Zbl 1230.94003, MR 2770310, 10.1007/s10623-010-9396-6 |
| . |
