• "History has taught us: never underestimate the amount of money, time, and effort someone will expend to thwart a security system. It's always better to assume the worst. Assume your adversaries are better than they are. Assume science and technology will soon be able to do things they cannot yet. Give yourself a margin for error. Give yourself more security than you need today. When the unexpected happens, you'll be glad you did."

    Bruce Schneier, "Why Cryptography Is Harder Than It Looks", 1997

  • "Given their power to intercept and disrupt secret communications, it is not surprising that quantum computers have the attention of various U.S. government agencies.  The National Security Agency, which supports research in quantum computing, candidly declares that given its interest in keeping U.S. government communications secure, it is loath to see quantum computers built. On the other hand, if they can be built, then it wants to have the first one.”

    Prof Seth Lloyd of MIT, MIT Review 2008

  • "Even a relatively small quantum computer, one that had a few tens of thousands of qubits, could consider so many different values at once that it would be able to break all known [ed: RSA, D&H, ECC, AES-128] codes commonly used for secure Internet communication.”

    Prof Seth Lloyd of MIT, MIT Review 2008

  • “When will we be secure? Nobody knows for sure – but it cannot happen before commercial security products and services possess not only enough functionality to satisfy customers’ stated needs, but also sufficient assurance of quality, reliability, safety, and appropriateness for use. Such assurances are lacking in most of today’s commercial security products and services.”

    Brian Snow, Former Technical Director of the US National Security Agency (NSA), "We need Assurance", 2005

  • “The time needed to factor an RSA integer is the same order as the time needed to use that same integer as modulus for a single RSA encryption.   In other words, it takes no more time to break RSA on a quantum computer (up to a multiplicative constant) than to use it legitimately on a classical computer.”

    Professor Gilles Brassard,  "Quantum Information Processing: The Good, the Bad and the Ugly", 1997

  • “The current way which organisations approach security can be recognised as an underlying market failure which consists of fire fighting security problems, silo'd implementation of technologies, uncontrolled application development practices and a failure to address systemic problems. Organisations tend to deal with one problem at a time that results in the deployment of point solutions to treat singular problems. This failure is typical of an uncontrolled marketplace evolving with little or no co-ordination.”

    The British Government’s Technology Strategy Board, 2008

  • “The software security industry today is at about the same stage as the auto industry was in 1930" ... "it looks fast, goes nice but in an accident you die.” ... "The major shortfall is absence of assurance (or safety) mechanisms in software. If my car crashed as often as my computer does, I would be dead by now."

    Brian Snow, Former Technical Director of the US National Security Agency (NSA), "We need assurance!", 1999-2008

  • "First and foremost, there is no proper excuse for continued use of a broken cryptographic primitive (MD5) when sufficiently strong alternatives are readily available, for example SHA-2. Secondly, there is no substitute for security awareness." ... "Advice from experts should be taken seriously and early in the process. In this case, MD5 should have been phased out soon after 2004."

    Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Wegerr, "MD5 considered harmful today - Creating a rogue CA certificate", December 2008

  • “Never underestimate the attention, risk, money and time that an opponent will put into reading traffic.”

    Robert Morris, former Chief Scientist of the US National Security Agency (NSA), National Computer Security Center, "Crypto '95 invited talks by R. Morris and A. Shamir", 1995

  • “Business now relies on information infrastructures that are interlinked and interdependent… The way in which these hidden interdependencies pervade our everyday lives is staggering and, in some cases, may go unchecked for many years until an incident occurs that revels the true nature of the interdependences' impact.”

    The British Government’s Technology Strategy Board, 2008

  • “In the next five years we will counter many 'hacker' attacks but we will not be safe from Nation States and other large entities”

    Brian Snow, Former Technical Director of the US National Security Agency (NSA), "We need assurance!", 1999-2008

  • "Today’s systems must anticipate future attacks. Any comprehensive system – whether for authenticated communications, secure data storage, or electronic commerce – is likely to remain in use for five years or more. It must be able to withstand the future: smarter attackers, more computational power, and greater incentives to subvert a widespread system. There won’t be time to upgrade it in the field."

    Bruce Schneier, "Why Cryptography Is Harder Than It Looks", 1997
Resources Security bibliography Quantum algorithms bibliography: Grover's Algorithm
bibliography: Grover's Algorithm
Security bibliography - Quantum algorithms
Inventors: Lov Grover
Date: 1996
Keywords: public key cryptography, asymmetric encryption, symmetric encryption, digital signatures, quantum computers
Electronic Publication:

Original Paper
Description:

An unsorted, unstructured and unindexed database provides no opportunity for a classical algorithm to optimize a search algorithm. This implies a brute force search must be performed. For a database of N items, to find one item requires (N/2) items to be individually inspected before a match is found on average. This is described as requiring O(N) time which is exponential with respect to the ⎡log2(N)⎤ bits required to store the number.

Grover’s algorithm is a quantum algorithm that runs in exponential in time to the ⎡log2(N)⎤ bits required to store the number, but provides a quadratic improvement over the classical brute force search. Grover’s algorithm allows a quantum computer to find one of exactly k items in an unsorted database of N items in O(√(N/k) ) operations and approximately log2 N qubits.

In cryptographic applications the database being queried will be an invocation to a block cipher, stream cipher, public key algorithm or hash function implemented as a quantum algorithm.
See: n/a
Citation:

Grover L.K.: “A fast quantum mechanical algorithm for database search”, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996)
Derivative Algorithms:
Related work: Shor's algorithm.
 
This website uses cookies to manage authentication, navigation, and to provide you with a better and more personal service. By continuing to use this website, you are consenting to this use. Find out more here.

image Introduction to synaptic Laboratories global cyber safety and Security status 2012 Cyber Security Technical Problems, Drivers and Incentives Video Presentation by Brian Snow

"Synaptic Laboratories is a rare company; they tackle the hard problems! Their basic approach is directly relevant to Governments and/or any commercial companies that deploy products that must function correctly in high-risk environments. They differ from most competitors in that not only do they work hard to get the concepts right, they also work very hard to assure the implementation is correct and robust as well."

Related Items

 

 

 

 

 

 

 

Universal Transaction System