|
| related topics |
| {algorithm, log, probability} |
| {let, theorem, proof} |
| {key, protocol, security} |
| {energy, gaussian, time} |
| {bell, inequality, local} |
| {equation, function, exp} |
|
Deutsch-Jozsa Algorithm Revisited in the Domain of Cryptographically
Significant Boolean Functions
Subhamoy Maitra, Partha Mukhopadhyay
abstract: 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.
- oai_identifier:
- oai:arXiv.org:quant-ph/0410042
- categories:
- quant-ph
- arxiv_id:
- quant-ph/0410042
- created:
- 2004-10-06
Full article ▸
|
|
| related documents |
| 9907020v2 |
| 0304131v1 |
| 0403140v2 |
| 0010034v1 |
| 0607148v3 |
| 0207131v1 |
| 9903071v1 |
| 0511272v1 |
| 9802040v2 |
| 0505007v3 |
| 0201152v1 |
| 9905026v1 |
| 0504067v3 |
| 0302022v1 |
| 9706003v4 |
| 0206089v2 |
| 0210077v1 |
| 0612089v3 |
| 0303175v1 |
| 0408150v2 |
| 0008059v3 |
| 0609220v1 |
| 0510185v1 |
| 0610235v2 |
| 0504083v2 |
|