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

Abstract

Our paper is motivated by differential cryptanalysis of hash functions. We give an upper bound on the number of binary signed digit representations (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 and introduce a new recursive upper bound for the number of BSDR's of any given weight.

Keywords

• number
• binary
• signed
• digit
• representations
• given
• weight