Walsh Sampling with Incomplete Noisy Signals

arXiv:1602.00095v2 [cs.IT] 19 Jan 2018

Yi Janet Lu
National Research Center of Fundamental Software, Beijing, P.R.China
Department of Informatics, University of Bergen, Bergen, Norway
Email: yi.janet.lu@gmail.com
January 22, 2018

Abstract
With the advent of massive data outputs at a regular rate, admittedly, signal processing
technology plays an increasingly key role. Nowadays, signals are not merely restricted to physical
sources, they have been extended to digital sources as well.
Under the general assumption of discrete statistical signal sources, we propose a practical
problem of sampling incomplete noisy signals for which we do not know a priori and the sampling
size is bounded. We approach this sampling problem by Shannon’s channel coding theorem. Our
main results demonstrate that it is the large Walsh coefficient(s) that characterize(s) discrete
statistical signals, regardless of the signal sources. By the connection of Shannon’s theorem,
we establish the necessary and sufficient condition for our generic sampling problem for the
first time. Our generic sampling results find practical and powerful applications in not only
statistical cryptanalysis, but software system performance optimization.
Keywords. Walsh transform, Shannon’s channel coding theorem, channel capacity, classical
distinguisher, statistical cryptanalysis, generic sampling, digital signal processing.

1

Introduction

With the advent of massive data outputs regularly, we are confronted by the challenge of big data
processing and analysis. Admittedly, signal processing has become an increasingly key technology.
An open question is the sampling problem with the signals, for which we assume that we do not
know a priori. Due to reasons of practical consideration, sampling is affected by possibly strong
noise and/or the limited measurement precision. Assuming that the signal source is not restricted
to a particular application domain, we are concerned with a practical and generic problem to sample
these noisy signals.
Our motivation arises from the following problem in modern applied statistics. Assume the
discrete statistical signals in a general setting as follows. The samples, generated by an arbitrary
(possibly noise-corrupted) source F , are 2n -valued for a fixed n. It is known to be a hypothesis
testing problem to test presence of any signals. Traditionally, F is a deterministic function with
small or medium input size. It is computationally easy to collect the complete and precise distribution f of F . Based on the notion of Kullback-Leibler distance, the conventional approach
(aka. the classic distinguisher) solves the sampling problem, given the distribution f a priori (see
[20]). Nevertheless, in reality, F might be a function that we do not have the complete description,
or it might have large input size, or it maybe a non-deterministic function. Thus, it is infeasible
1

to collect the complete and precise distribution f . This gives rise to the new generic statistical
sampling problem with discrete incomplete noisy signals, using the bounded number of samples.
In this work, we show that we can solve the generic sampling problem as reliable as possible without knowing signals a priori. By novel translations, Shannon’s channel coding theorem can solve
the generic sampling problem under the general assumption of statistical signal sources. Specifically, the necessary and sufficient condition is given for the first time to sample the incomplete
noisy signals with bounded sampling size for signal detection. It is interesting to observe that the
classical signal processing tool of Walsh transform [2,9] is essential: regardless of the signal sources,
it is the large Walsh coefficient(s) that characterize(s) discrete statistical signals. Put other way,
when sampling incomplete noisy signals of the same source multiple times, one can expect to see
repeatedly those large Walsh coefficient(s) of same magnitude(s) at the fixed frequency position(s).
Note that this is known in application domains such as images, voices. Our results show strong
connection between Shannon’s theorem and Walsh transform, both of which are the key innovative
technologies in digital signal processing. Our generic sampling results find practical and useful
applications in not only statistical cryptanalysis - it is expected to become a powerful universal analytical tool for the core building blocks of symmetric cryptography (cf. [12, 21]), but performance
analysis and heterogeneous acceleration. The latter seems to be one of the main bottlenecks for
large-scale IT systems in the era of the revolutionary development of memory technologies.
The rest of the paper is organized as follows. In Section 2, we review the basics of Walsh
transforms and its application of multi-variable tests in statistics. In Section 3, Shannon’s famous
channel coding theorem, also known as Shannon’s Second Theorem, is reviewed. In Section 4, we
present our main sampling results: we put forward two sampling problems, namely, the classical and
generic versions; we also conjecture a quantitative relation between Renyi’s divergence of degree 1/2
and Shannon’s channel capacity. In Section 5, we give illustrative applications and experimental
results. Finally, we give conclusions and future work in Section 6.

2

Walsh Transforms in Statistics

Given a real-valued function f : GF (2)n → R, which is defined on an n-tuple binary vector of
input, the Walsh transform of f , denoted by fb, is another real-valued function defined as
def
fb(i) =

X

(−1)hi,ji f (j),

(1)

j∈GF (2)n

for all i ∈ GF (2)n , where < i, j > denotes the inner product between two n-tuple binary vectors
i, j. For later convenience, we give an alternative definition below. Given an input array x =
(x0 , x1 , . . . , x2n −1 ) of 2n reals in the time domain, the Walsh transform y = x
b = (y0 , y1 , . . . , y2n −1 )
of x is defined by
X
def
yi =
(−1)hi,ji xj ,
(2)
j∈GF (2)n

for any n-tuple binary vector i. We call xi (resp. yi ) the time-domain component (resp. transformdomain coefficient) of the signal with dimension 2n . For properties and references on Walsh transforms, we refer to [9, 12, 17].
Let f be a probability distribution of an n-bit random variable X = (Xn , Xn−1 , . . . , X1 ), where
each Xi ∈ {0, 1}. Then, fb(m) is the bias of the Boolean variable hm, X i for any fixed n-bit vector m,
2

which is often called the output pattern or mask (and note that the pattern m should be nonzero).
Here, recall that a Boolean random variable A has bias , which is defined by
def

 = E[(−1)A ] = Pr(A = 0) − Pr(A = 1).

(3)

Hence, we always have −1 ≤  ≤ 1 and if A is uniformly distributed, A has bias 0.
Walsh transforms were used in statistics to find dependencies within a multi-variable data set.
In the multi-variable tests, each Xi indicates the presence or absence (represented by ‘1’ or ‘0’)
of a particular feature in a pattern recognition experiment. Fast Walsh Transform (FWT) is used
to obtain all coefficients fb(m) in one shot. By checking the Walsh coefficients one by one and
identifying the large 1 ones, we are able to tell the dependencies among Xi ’s. For instance, we have
a histogram of the pdf (the probability density function) of the triples (X0 , X1 , X2 ) as depicted in
Fig. 1. It is obtained by an experiment of trying a total of 160 times. The Walsh spectrum of
the histogram, i.e., of the array (24, 18, 16, 26, 22, 14, 16, 24), as calculated by (2), is shown in Fig.
2. The largest nontrivial Walsh coefficient is found to be 32 located at the index position (0, 1, 1).
This implies that the correlation is observed to be strongest for the variables X1 , X2 .

3

Review on Shannon’s Channel Coding Theorem

We briefly review Shannon’s famous channel coding theorem2 (cf. [5]). First, we recall basic
definitions of Shannon entropy. The entropy H(X) of a discrete random variable X with alphabet
X and probability mass function p(x) is defined by
def

H(X) = −

X

p(x) log2 p(x).

x∈X
1
2

Throughout the paper, we refer to the large transform-domain coefficient d as the one with a large absolute value.
Sometimes it’s called Shannon’s Second Theorem.

3

The joint entropy H(X1 , . . . , Xn ) of a collection of discrete random variables (X1 , . . . , Xn ) with a
joint distribution p(x1 , x2 , . . . , xn ) is defined by
X
def
H(X1 , . . . , Xn ) = −
p(x1 , . . . , xn ) log2 p(x1 , . . . , xn ).
x1
···
xn

Define the conditional entropy H(Y |X) of a random variable Y given X by
X
def
H(Y |X) =
p(x)H(Y |X = x).
x

The mutual information I(X; Y ) between two random variables X, Y is equal to H(Y ) − H(Y |X),
which always equals H(X) − H(X|Y ). A communication channel is a system in which the output
Y depends probabilistically on its input X. It is characterized by a probability transition matrix
that determines the conditional distribution of the output given the input.
Theorem 1 (Shannon’s Channel Coding Theorem). Given a channel, denote the input, output by
X, Y respectively. We can send information at the maximum rate C bits per transmission with an
arbitrarily low probability of error, where C is the channel capacity defined by
C = max I(X; Y ),

(4)

p(x)

and the maximum is taken over all possible input distributions p(x).
For the binary symmetric channel (BSC) with crossover probability p, that is, the input symbols
are complemented with probability p, so the transition matrix is of the form


1−p
p
.
(5)
p
1−p
We can express C by (cf. [5]):
C = 1 − H(p) bits/transmission.
4

(6)

We refer to the BSC with crossover probability p = (1 + d)/2 and d is small (i.e., |d|  1) as an
extremal BSC. Note that such a BSC becomes useful in studying the correlation attacks (see [15])
on stream ciphers. To put simply, the observed keystream bit is found to be correlated with one
bit which is a linear relation of the internal state. In this case, the probability that the equality
holds is denoted by 1 − p (and so the crossover probability of this BSC is p). Using
H

1 + d
2

=1−

we can show

 d2
2

+


d4
d6
d8
1
+
+
+ |{z}
··· ×
,
12 30 56
log 2

1 + d

= 1 − d2 /(2 log 2) + O(d4 ).
2
So, we can show the following result of the channel capacity for an extremal BSC:
H

(7)

O(d10 )

(8)

Corollary 1 (extremal BSC). Given a BSC channel with crossover probability p = (1 + d)/2, if d
is small (i.e., |d|  1), then, C ≈ c0 · d2 , where the constant c0 = 1/(2 log 2).
Therefore, we can send one bit with an arbitrarily low probability of error with the minimum
number of transmissions 1/C = (2 log 2)/d2 , i.e., O(1/d2 ). Interestingly, in communication theory,
this extremal BSC is rare as we typically deal with |d|  0 (see [18]).

4

Sampling Theorems with Incomplete Signals

In this section, we put forward two sampling problems, namely, the classical and generic versions.
Without loss of generality, we assume that the discrete statistical signals are not restricted to a
particular application domain and the signals are 2n -valued for a fixed n.
Specifically, we give the mathematical model on the signal represented by an arbitrary (and not
necessarily deterministic) function F as follows. Let X be the n-bit output sample of F , assuming
that the input is random and uniformly distributed. Denote the output distribution of X by f .
Note that our assumption on a general setting of discrete statistical signals is described by the
assumption that F is an arbitrary yet fixed function with the n-bit output.
The classical sampling problem can be formally stated as follows.
Theorem 2 (Classical Sampling Problem). Assume that the largest Walsh coefficient of f is d =
fb(m0 ) for a nonzero n-bit vector m0 . We can detect signals represented by F with an arbitrarily
low probability of error, using minimum number N = (8 log 2)/d2 of samples of F , i.e., O(1/d2 ).
Note that it can be interpreted as the classical distinguisher which is used often in statistical
cryptanalysis, though the problem statement of the classical distinguisher is slightly different and
it uses a slightly different N (cf. [20]). The classical sampling problem assumes that F together
with its characteristics (i.e., the largest Walsh coefficient d) are known a priori.
Next, we present our main sampling results for practical (and widely applicable) sampling. Assuming that it is infeasible to know signal represented by F a priori, we want to use the bounded
number of samples to detect signals with an arbitrarily low probability of error. Note that the
sampled signal is often incomplete3 and so the associated distribution is not precise. We call this
3

that is, it is possible that not all the outputs are generated by sampling.

5

problem as generic sampling with incomplete noisy signals. In analogy to the classical distinguisher, this result can be interpreted as a generalized distinguisher4 in the context of statistical
cryptanalysis. We give our main result with n = 1 below.
Theorem 3 (Generic Sampling Problem with n = 1). Assume that the sampling size of F is upperbounded by N . Regardless of the input size of F , in order to detect the signal F with an arbitrarily
low probability of error, it is necessary and sufficient
√ to have the following condition
√ satisfied, i.e.,
f has a nontrivial Walsh coefficient d with |d| ≥ c/ N , where the constant c = 8 log 2.
Assume that f satisfy the following conditions: 1) the cardinality of the support of f is a power
of two (i.e., 2n ), and 2) 2n is small, and 3) f (i) ∈ (0, 3/2n ), for all i. Now, we present a generalized
result for n ≥ 1, which incorporates Theorem 3 as a special case:
Proposition 1 (Generic Sampling Problem with n ≥ 1). Assume that the sampling size of F is
upper-bounded by N . Regardless of the input size of F , in order to detect the signal F with an
arbitrarily low probability of error, it is necessary and sufficient to have the following condition
satisfied, i.e.,
X
(fb(i))2 ≥ (8 log 2)/N.
(9)
i6=0

We note that the sufficient condition can be also proved based on results of the classic distinguisher (i.e.,P
Squared Euclidean Imbalance), which uses the notion of Kullback-Leibler distance and
states that i6=0 (fb(i))2 ≥ (4 log 2)/N is required for a high probability of success [20]. Secondly,
from (9), the discrete statistical signals can be characterized by large Walsh coefficients of the associated distribution. Thus the most significant transform-domain signals are the largest coefficients
in our generalized model.

4.1

Proof of Theorem 3

We first prove the following hypothesis testing result by Shannon’s Channel Coding Theorem:
Theorem 4. Assume that the boolean random variable A has bias d and d is small. We are given
a sequence of random samples, which are i.i.d. following the distribution of either A or a uniform
distribution. We can tell the sample source with an arbitrarily low probability of error, using the
minimum number N of samples (8 log 2)/d2 , i.e., O(1/d2 ).
Proof. We propose a novel non-symmetric binary channel. Assume the channel with the following
transition matrix


1 − pe pe
p(y|x) =
,
(10)
1/2 1/2
where pe = (1 − d)/2 and d is small. The matrix entry in the xth row and the yth column denotes
the conditional probability that y is received when x is sent. So, the input bit 0 is transmitted
by this channel with error probability pe (i.e., the received sequence has bias d if input symbols
are 0) and the input bit 1 is transmitted with error probability 1/2 (i.e., the received sequence has
bias 0 if input symbols are 1). By Shannon’s channel coding theorem, with a minimum number of
4

With n = 1, this appears as an informal result in symmetric cryptanalysis, which is used as a black-box analysis
tool in several crypto-systems.

6

N = 1/C transmissions, we can reliably (i.e., with an arbitrarily low probability of error) detect
the signal source (i.e., determine whether the input is ‘0’ or ‘1’).
To compute the channel capacity C, i.e., find the maximum defined in (4), no closed-form solution exists in general. Nonlinear optimization algorithms (see [1, 3]) are known to find a numerical
solution. Below, we propose a simple method to give a closed-form estimate C for our extremal
binary channel. As I(X; Y ) = H(Y ) − H(Y |X), we first compute H(Y ) by

1
H(Y ) = H p0 (1 − pe ) + (1 − p0 ) ×
,
(11)
2
where p0 denotes p(x = 0) for short. Next, we compute
X
p(x)H(Y |X = x)
H(Y |X) =
x



= p0 H(pe ) − 1 + 1.

(12)

Combining (11) and (12), we have

1
1
− p0 H(pe ) + p0 − 1.
I(X; Y ) = H p0 × − p0 pe +
2
2
As pe = (1 − d)/2, we have
 1−d

1 + p0 d
I(X; Y ) = H(
) − p0 H(
) − 1 − 1.
2
2
For small d, we apply (8) in Appendix
 1−d

p2 d2
I(X; Y ) = − 0
− p0 H(
) − 1 + O(p40 d4 ).
2 log 2
2

(13)

(14)

(15)

Note that the last term O(p40 d4 ) on the right side of (15) is ignorable. Thus, I(X; Y ) is estimated
to approach the maximum when
p0 = −

H( 1−d
d2 /(2 log 2)
1
2 )−1
≈
= .
2
2
d /(log 2)
d /(log 2)
2

(16)

Consequently, we estimate the channel capacity (15) by
1
1
1−d 
C ≈ − d2 /(2 log 2) +
1 − H(
)
4
2
2
≈ − d2 /(8 log 2) + d2 /(4 log 2),
which is d2 /(8 log 2).
We now proceed to prove Theorem 3. The only nontrivial Walsh coefficient d for n = 1 is fb(1),
which is the bias of F . First, we will show by contradiction that this is a necessary condition.
That is,√if we can identify F with
√ an arbitrarily low probability of error, then, we must have
|d| ≥ c/ N . Suppose |d| < c/ N otherwise. Following the proof of Theorem 4, we know that
the error probability is bounded away from zero as the consequence of Shannon’s Channel Coding
Theorem. This is contradictory. Thus, we have shown that the condition on d is a√necessary
condition. Next, we will show that it is also a sufficient condition. That is, if |d| ≥ c/ N , then,
we can identify F with an arbitrarily low probability of error. This follows directly from Theorem
2 with n = 1. We complete our proof.
7

4.2

Proof of Proposition 1

Assume that the channel have transition matrix p(y|x). Let p(y|x = 0) denote the distribution f ,
and let p(y|x = 1) be a uniform distribution. Denote the channel
P capacity by C. For convenience, we
let f (i) = ui +1/2n for i = 0, . . . , 2n −1. Note that we have i ui = 0 and −1/2n < ui < (2n −1)/2n
for all i.
By Taylor series, for all i we have
 u
1
1
1
ui
i
+ ( 2
)3
log(ui + n ) = log n + 2 2
2
2
3
+
u
+
u
i
i
2n
2n

+···
≈ log

1
+
2n

2ui
,
+ ui

(17)

2
2n

as we know ui /( 22n +ui ) ∈ (−1, 1). And we deduce that with small 2n , we can calculate − log 2·H(f )
by
X
1
1
(ui + n ) log(ui + n )
2
2
i
X
X
1
2ui
≈ log n + 2
ui −
2
2 + 2n · ui
i
i
1 X
1
1
(1 −
).
(18)
≈ log n − n−1
2
2
1 + 2n−1 ui
i

Assuming that |2n−1 ui | < 1 for all i (and small 2n ), we have

X
X
1
n−1
n−1
2
.
≈
1
−
2
u
+
(2
u
)
i
i
1 + 2n−1 ui
i

(19)

i

P
We continue (18) by − log 2·H(f ) ≈ log 21n +2n−1 i u2i . Meanwhile, by property of Walsh transform
(cf. [12, Sect.2]), we know
2
X
X
X
f (i) = 2n
(fb(i))2 = 2n
u2i + 1.
(20)
i

i

i

So, we have shown an important result as follows
2n X
1 2
f (i) − n
2 log 2
2
i
P
b 2
i6=0 (f (i))
= n−
,
2 log 2

H(f ) ≈ n −

(21)

assuming that 1) the cardinality of the support of f is a power of two (i.e., 2n ), and 2) 2n is small,
and 3) f (i) ∈ (0, 3/2n ), for all i.
Next, in order to calculate C, by (21) we first compute
P
p0 i6=0 (fb(i))2
,
(22)
H(Y |X) = p0 H(f ) + (1 − p0 )n ≈ n −
2 log 2
8

where p0 denote p(x = 0) for short. Denote the distribution of Y by DY . We have DY (i) =
p0 f (i) + (1 − p0 )/2n = p0 ui + 1/2n for all i. Again we can apply (21) and get
P
P
2
d
p20 i6=0 (fb(i))2
i6=0 (DY (i))
H(Y ) ≈ n −
=n−
.
(23)
2 log 2
2 log 2
So, we have
I(X; Y ) = H(Y ) − H(Y |X) ≈

(p0 − p20 )

b 2
i6=0 (f (i))

P

2 log 2

.

(24)

When p0 = 1/2, we have the maximum I(X; Y ), which equals
2
P  b 2
P
1
n
2
f
(i)
f
(i)
−
n
i6=0
i
2
=
.
(25)
C≈
8 log 2
8 log 2
P
b 2
Consequently, we have N ≥ 1/C, i.e.,
i6=0 (f (i)) ≥ (8 log 2)/N . And this is a necessary and
sufficient condition, following Shannon’s theorem.

4.3

More Generalized Results

Above we consider the case that f (i) is not so far from the uniform distribution. Based on the
weaker assumption that 2n is small and f (i) = 1/2n + ui > 0 (i.e., ui > −1/2n ) for all i, we now
show a a more general result. We have
1 X
ui
H(f ) ≈ n +
(26)
log 2
1 + 2n−1 ui
i

by (18). Following similar computations we have
H(Y |X) ≈ n +
H(Y ) ≈ n +

p0 X
ui
,
log 2
1 + 2n−1 ui
i
p0 ui
1 X
log 2

i

1 + 2n−1 p0 ui

(27)
.

So, we obtain the following general result,

1 X
p0 ui
p0 ui
−
.
C ≈ max
p0 log 2
1 + 2n−1 p0 ui
1 + 2n−1 ui

(28)

(29)

i

2/2n

Recall that if |u( i)| <
for all i, (29) can be approximated by (25), which is achieved with
p0 = 1/2. Specifically, if |u( i)| < 2/2n , the approximation for the addend in (29) can be expressed
as follows,
p0 ui
p0 ui
(
−
) ≈ 2n−1 u2i (p0 − p20 ),
(30)
n−1
1+2
p0 ui
1 + 2n−1 ui
v
1
where we use 1+v
= 1 − 1+v
≈ 1 − (1 − v + v 2 ) = v − v 2 (for |v| < 1).
v
Note that for |v| > 1, we have 1+v
≈ 1 − 1/v + 1/v 2 . We can show that with 2n−1 ui = k > 1
for some i, the addend in (29) can achieve the maximum when p0 = 1/k, that is,

max(
p0

p0 ui
p0 ui
1
1
1
1
−
) ≈ n−1 (1 − + 2 − 3 ).
n−1
n−1
1+2
p0 ui
1+2
ui
2
k k
k
9

(31)

On the other hand, the right-hand side of (30) equals (p0 − p20 )k 2 /2n−1 , which is much larger than
(31).
Meanwhile, with 2n−1 ui = k = 1 for some i, we have
p0 ui
p0 ui
−
)
1 + 2n−1 p0 ui
1 + 2n−1 ui
1 p0
1
1
≈ max n−1 ( − p20 ) =
·
,
p0 2
2
16 2n−1
max(
p0

(32)

when p0 = 1/4.

4.4

Further Discussions

Based on Renyi’s information measures (cf. [6]), we make a conjecture5 below for an even more
general form of our channel capacity C. Recall that Renyi’s information divergence (see [6]) of
order α = 1/2 of distribution P from another distribution Q on a finite set X is defined as
def

Dα (P kQ) =

X


1
log
P α x Q1−α x .
α−1

(33)

x∈X

So, with α = 1/2,
def

D1/2 (P kQ) = (−2) log

Xp

P (x)Q(x).

(34)

x∈X

Conjecture 1. Let Q, U be a non-uniform distribution and a uniform distribution over the support
of cardinality 2n . Let the matrix of T consist of two rows Q, U and 2n columns. We have the
following relation between Renyi’s divergence of degree 1/2 and the generalized channel capacity of
degree 1/2 (i.e., standard Shannon’s channel capacity),
D1/2 (QkU ) = 2 · C1/2 (T ).

(35)

Finally, assume that 2n -valued F has potentially large input space 2L . The collected normalized
distribution of N  2n output samples in the time-domain approximately fits in the noisy model of
[4,11]. That is, the additive Gaussian noise is i.i.d. and has zero mean and variance σ 2 = 1/(N 2n ).
In this case, noisy sparse WHT [4] can be used for our generic sampling problem in recovering the
nonzero Walsh coefficients fb(i) and index positions i. And we obtain evaluation time N queries of
F , processing time roughly on the order of n, provided that
X
(fb(i))2 ≥ (8 log 2)/N,
(36)
i6=0

that is,
SNR =

X
i6=0

5

2 1
2
X
n
2
b
b
f (i) /( ) ≥ 8 log 2.
f (i) /(2 · σ ) =
N
i6=0

see [14] for most recent results on the conjecture.

10

(37)

5

Applications and Experimental Results

We first demonstrate a cryptographic sampling application. The famous block cipher GOST 2814789 is a balanced Feistel network of 32 rounds. It has a 64-bit block size and a key length of 256
bits. Let 32-bit Li and Ri denote the left and right half at Round i ≥ 1 and L0 , R0 denote the
plaintext. The subkey for Round i is denoted by ki . For the purpose of multi-round analysis, our
target function is F (Ri−1 , ki ) = Ri−1 ⊕ ki ⊕ f (Ri−1 , ki ), where f (Ri−1 , ki ) is the round function.
We choose N = 240 . It turns out that the largest three Walsh coefficients are 2−6 , 2−6.2 , 2−6.3
respectively. This new weakness leads to various severe attacks [13] on GOST. Similarly, our
cryptographic sampling technique is applicable and it further threatens the security of the SNOW
2.0 cipher [22].
For general SNR ≥ 8 log 2, regardless of 2L , when N ∼ 2n , we choose appropriate b such
that N = b · 2` . So, roughly b · ` processing time is needed. With L = 64, it would become a
powerful universal analytical tool6 for security evaluation of the core building blocks of symmetric
cryptography (cf. [12, 21]).
Another notable practical application is software performance optimization. Modern largescale IT systems are of hybrid nature. Usually, only partial information about the architecture as
well as some of its component units is known. Further, the revolutionary change of the physical
components (e.g., main memory, storage) inevitably demand that the system take full advantages
of the new hardware characteristics. We expect that our sampling techniques (and the transformdomain analysis of the running time) would help with performance analysis and optimization for
the whole heterogeneous system.

6

Conclusion

In this paper, we model general discrete statistical signals as the output samples of an unknown
arbitrary yet fixed function (which is the signal source). We translate Shannon’s channel coding
theorem to solve a hypothesis testing problem. The translated result allows to solve a generic sampling problem, for which we know nothing about the signal source a priori and we can only afford
bounded sampling measurements. Our main results demonstrate that the classical signal processing tool of Walsh transform is essential: it is the large Walsh coefficient(s) that characterize(s)
discrete statistical signals, regardless of the signal sources. By Shannon’s theorem, we establish the
necessary and sufficient condition for the generic sampling problem under the general assumption
of statistical signal sources. As for future direction of this work, it is interesting to investigate noisy
sparse WHT for our generic sampling problem in a more general setting N  2n and 2n is large,
in which case the noise cannot be modelled as Gaussian.

References
[1] S. Arimoto, An algorithm for computing the capacity of arbitrary discrete memoryless channels. IEEE Trans. Inform. Theory, IT-18 14-20, 1972.
6

Note that current computing technology [16] can afford exascale WHT (i.e., on the order of 260 ) within 2 years,
which uses 215 modern PCs.

11

[2] J. M. Blackledge. Digital Signal Processing – Mathematical and Computational Methods,
Software Development and Applications. Horwood Publishing, England, Second Edition, 2006.
[3] R. Blahut, Computation of channel capacity and rate distortion functions. IEEE Trans. Inform.
Theory, IT-18: 460-473, 1972.
[4] X. Chen, D. Guo, Robust Sublinear Complexity Walsh-Hadamard Transform with Arbitrary
Sparse Support, IEEE Int. Symp. Information Theory, pp. 2573 - 2577, 2015.
[5] T. M. Cover, J. A. Thomas. Elements of Information Theory. John Wiley & Sons, Second
Edition, 2006.
[6] I. Csiszár, Generalized Cutoff Rates and Rényi’s Information Measures, IEEE Trans. Inform.
Theory, Vol.41, no.1, Jan. 1995.
[7] Itai Dinur, Orr Dunkelman, Nathan Keller, Adi Shamir, Memory-Efficient Algorithms for
Finding Needles in Haystacks, CRYPTO 2016, Part II, LNCS 9815, pp. 185 - 206, 2016.
[8] R. M. Gray, L. D. Davisson. An Introduction to Statistical Signal Processing. Cambridge
University Press, 2004. http://www-ee.stanford.edu/~gray/sp.pdf.
[9] K. J. Horadam. Hadamard Matrices and Their Applications. Princeton University Press, 2007.
[10] A. Joux. Algorithmic Cryptanalysis. Chapman & Hall/CRC, Cryptography and Network Security, 2009.
[11] X. Li, J. K. Bradley, S. Pawar, K. Ramchandran, The SPRIGHT algorithm for robust sparse
Hadamard transforms, IEEE Int. Symp. Information Theory, pp. 1857 - 1861, 2014.
[12] Y. Lu, Y. Desmedt, Walsh Transforms and Cryptographic Applications in Bias Computing,
Cryptography and Communications, Vol.8, no.3, pp. 435 - 453, Springer, 2016.
[13] Y. Lu, New Linear Attacks on Block Cipher GOST, IACR eprint, http://eprint.iacr.org/
2017/487, 2017.
[14] Y. Lu, New Results on the DMC Capacity and Renyi’s Divergence, arXiv:1708.00979, 2017.
[15] W. Meier, O. Staffelbach, Fast Correlation Attacks on Certain Stream Ciphers, Journal of
Cryptology, Vol.1, no.3, pp. 159 - 176, Springer, 1989.
[16] D. A. Reed, J. Dongarra, Exascale Computing and Big Data: The Next Frontier, Communications of the ACM, Vol.58, no.7, pp. 56 - 68, 2015.
[17] R. Scheibler, S. Haghighatshoar, M. Vetterli, A Fast Hadamard Transform for Signals With
Sublinear Sparsity in the Transform Domain, IEEE Transactions on Information Theory,
Vol.61, no.4, pp. 2115 - 2132, 2015.
[18] M. A. Shokrollahi, Personal Communication, 2006.
[19] S. Vaudenay, An experiment on DES - statistical cryptanalysis, Third ACM Conference on
Computer Security, pp. 139 - 147, 1996.

12

[20] S. Vaudenay. A Classical Introduction to Modern Cryptography - Applications for Communications Security. Springer, New York, 2006.
[21] S. Vaudenay, A Direct Product Theorem, submitted.
[22] B. Zhang, C. Xu, W. Meier, Fast correlation attacks over extension fields, large-unit linear
approximation and cryptanalysis of SNOW 2.0, CRYPTO 2015, LNCS Vol. 9215, pp. 643 662, Springer, 2015.
[23] B. Zhang, C. Xu, D. Feng, Practical Cryptanalysis of Bluetooth Encryption with Condition
Masking, Journal of Cryptology, https://doi.org/10.1007/s00145-017-9260-1, Springer,
2017.

13

