Physics – Quantum Physics
Scientific paper
2004-10-06
Physics
Quantum Physics
Scientific paper
Boolean functions are important building blocks in cryptography for their wide application in both stream and block cipher systems. For cryptanalysis of such systems one tries to find out linear functions that are correlated to the Boolean functions used in the crypto system. Let $f$ be an $n$-variable Boolean function and its Walsh spectra is denoted by $W_f(\omega)$ at the point $\omega \in \{0, 1\}^n$. The Boolean function is available in the form of an oracle. We like to find an $\omega$ such that $W_f(\omega) \neq 0$ as this will provide one of the linear functions which are correlated to $f$. We show that the quantum algorithm proposed by Deutsch and Jozsa (1992) solves the above mentioned problem in constant time. However, the best known classical algorithm to solve this problem requires exponential time in $n$. We also analyse certain classes of cryptographically significant Boolean functions and highlight how the basic Deutsch-Jozsa algorithm performs on them.
Maitra Subhamoy
Mukhopadhyay Partha
No associations
LandOfFree
Deutsch-Jozsa Algorithm Revisited in the Domain of Cryptographically Significant Boolean Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Deutsch-Jozsa Algorithm Revisited in the Domain of Cryptographically Significant Boolean Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deutsch-Jozsa Algorithm Revisited in the Domain of Cryptographically Significant Boolean Functions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-170882