Cryptographic Significance of the Carry for Ciphers Based on Integer Addition

Integer addition has been proposed for use in cryptographic transformations since this operation is nonlinear when considered over GF(2). In these applications nonlinearity or confusion is achieved via the carry. If the carry happens to be biased, there result correlations to linear functions which can be cryptanalytically exploited.The aim of the present paper is to investigate the probability distribution of the carry for integer addition with an arbitrary number n of inputs. It is shown that asymptotically the carry is balanced for even n and biased for odd n. As a result, for n = 3 the carry is strongly biased, whereas for increasing n it is shown that the bias tends to 0.