Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Hybrid Data Mining to Reduce False Positive and False Negative Prediction in Intrusion Detection System Read chapter Read first chapter

2019 | OriginalPaper | Chapter

Walsh Sampling with Incomplete Noisy Signals

Author : Yi Janet Lu

Published in: Advances in Information and Communication Networks

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Practically Realisable Anonymisation of Bitcoin Transactions with Improved Efficiency of the Zerocoin Protocol
next chapter Investigating the Effective Use of Machine Learning Algorithms in Network Intruder Detection Systems
Footnotes
1
Throughout the paper, we refer to the large transform-domain coefficient d as the one with a large absolute value.
 
2
Sometimes it’s called Shannon’s Second Theorem.
 
3
That is, it is possible that not all the outputs are generated by sampling.
 
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.
 
5
See [14] for most recent results on the conjecture.
 
6
Note that current computing technology [16] can afford exascale WHT (i.e., on the order of \(2^{60}\)) within 2 years, which uses \(2^{15}\) modern PCs.
 
Literature
1.
Arimoto, S.: An algorithm for computing the capacity of arbitrary discrete memoryless channels. IEEE Trans. Inform. Theory IT-18, 14-20 (1972)
2.
Blackledge, J.M.: Digital Signal Processing - Mathematical and Computational Methods. Software Development and Applications, 2nd edn. Horwood Publishing, England (2006)
3.
Blahut, R.: Computation of channel capacity and rate distortion functions. IEEE Trans. Inform. Theory IT-18, 460–473 (1972)
4.
Chen, X., Guo, D.: Robust sublinear complexity walsh-hadamard transform with arbitrary sparse support. In: IEEE International Symposium Information Theory, pp. 2573–2577 (2015)
5.
Cover, T.M., Thomas, J.A.: Elements of Information Theory, 2nd edn. John Wiley & Sons, Hoboken (2006)MATH
6.
Csiszár, I.: Generalized cutoff rates and rényi’s information measures. IEEE Trans. Inform. Theory 41(1), January 1995
7.
Dinur, I., Dunkelman, O., Keller, N., Shamir, A.: Memory-efficient algorithms for finding needles in haystacks. In: CRYPTO 2016. Part II, LNCS, vol. 9815, pp. 185–206 (2016)
8.
9.
Horadam, K.J.: Hadamard Matrices and Their Applications. Princeton University Press, Princeton (2007)CrossRef
10.
Joux, A.: Algorithmic Cryptanalysis. Cryptography and Network Security. Chapman & Hall/CRC, Boca Raton (2009)CrossRef
11.
Li, X., Bradley, J.K., Pawar, S., Ramchandran, K.: The SPRIGHT algorithm for robust sparse Hadamard transforms. In: IEEE International Symposium Information Theory, pp. 1857–1861 (2014)
12.
Lu, Y., Desmedt, Y.: Walsh transforms and cryptographic applications in bias computing. Cryptogr. Commun. 8(3), 435–453 (2016). Springer
13.
14.
15.
Meier, W., Staffelbach, O.: Fast correlation attacks on certain stream ciphers. J. Cryptol. 1(3), 159–176 (1989). Springer
16.
Reed, D.A., Dongarra, J.: Exascale computing and big data: the next frontier. Commun. ACM 58(7), 56–68 (2015)CrossRef
17.
Scheibler, R., Haghighatshoar, S., Vetterli, M.: A fast hadamard transform for signals with sublinear sparsity in the transform domain. IEEE Trans. Inf. Theory 61(4), 2115–2132 (2015)MathSciNetCrossRef
18.
Shokrollahi, M.A.: Personal Communication (2006)
19.
Vaudenay, S.: An experiment on DES - statistical cryptanalysis. In: Third ACM Conference on Computer Security, pp. 139–147 (1996)
20.
Vaudenay, S.: A Classical Introduction to Modern Cryptography. Applications for Communications Security. Springer, New York (2006)MATH
21.
S. Vaudenay, A Direct Product Theorem, submitted
22.
Zhang, B., Xu, C., Meier, W.: Fast correlation attacks over extension fields, large-unit linear approximation and cryptanalysis of SNOW 2.0. In: CRYPTO 2015, LNCS Vol. 9215, pp. 643–662, Springer (2015)
23.
Metadata
Title
Walsh Sampling with Incomplete Noisy Signals
Author
Yi Janet Lu
Copyright Year
2019
Book
Advances in Information and Communication Networks

Print ISBN: 978-3-030-03404-7

Electronic ISBN: 978-3-030-03405-4

Copyright Year: 2019

DOI
https://doi.org/10.1007/978-3-030-03405-4_9