• “Consider the use of smart cards ... for especially critical functions.  Although more costly than software, when properly implemented the assurance gain is great.  The form-factor is not as important as the existence of an isolated processor and address space for assured operations – an ‘Island of Security,’ if you will.  Such devices can communicate with each other through secure protocols and provide a web of security connecting secure nodes located across a sea of insecurity in the global net.”

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

  • "But conventional security is not enough. The complexity of today's operational environment means organisations must embrace a level of business resilience that is normally associated with the protection of critical national infrastructure."

    Detica, a BAE Systems Company

  • "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

  • “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

  • 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

  • “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
  • "My colleagues at MIT and I have been building simple quantum computers and executing quantum algorithms since 1996, as have other scientists around the world. Quantum computers work as promised. If they can be scaled up, to thousands or tens of thousands of qubits from their current size of a dozen or so, watch out!

    Prof Seth Lloyd of MIT, MIT Review 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
  • “We are a cyber nation. The U.S. information infrastructure--including telecommunications and computer networks and systems and the data that reside on them--is critical to virtually every aspect of modern life. This information infrastructure is increasingly vulnerable to exploitation, disruption, and destruction by a growing array of adversaries.”

    The National Coordination Office (NCO) for Networking Information Technology Research and Development (NITRD), Federal Register: December 30, 2008 (Volume 73, Number 250).

  • “Briefly and simply, assurance work makes a user or a creditor more confident that the system works as intended without flaws, without surprises, even in the presence of malice.” … “The major shortfall is absence of assurance or safety mechanisms in software.  If my car crashed as often as my computer does, I’d be dead by now.”

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

  • Build-in Security: Ensure that security is considered and built into the design of new infrastructure, so that our critical assets are protected from the start and more resilient to naturally-occurring and deliberate threats throughout their life-cycle."

    Obama-Biden Plan, Agenda: Homeland Security, December 2008

  • "Some physicists predicted that within the next 10 to 20 years quantum computers will be built that are sufficiently powerful to implement Shor’s ideas and to break all existing public key schemes. Thus we need to look ahead to a future of quantum computers, and we need to prepare the cryptographic world for that future.

    Prof Seth Lloyd of MIT, MIT Review 2008

Resources Security bibliography Quantum algorithms bibliography: Shor's quantum algorithm
bibliography: Shor's quantum algorithm
Inventors: Peter Shor
Date: 1985
Keywords: public key cryptography, asymmetric encryption, digital signatures, quantum computers
Electronic Publication:

Original Paper

Notes:

Finding (a) the prime factors of a composite number ({5, 3} ← 15) called integer factorization [201] and (b) discrete logarithms [123], [200] on a classical computer are generally thought to be two computationally hard, sub-exponential time problems [5]. These two problems are related, in that algorithms from one problem are often adapted to the other [123] and discussion on the two problems are regularly found together in the same paper. In fact these two problems are special cases of the “hidden sub group problem” (HSP) [199].

In 1994 Peter Shor introduced two polynomial-time algorithms, one for finding the prime factors of a composite number and one for finding discrete logarithms on a quantum computer. These algorithms make a computationally ‘hard’ classical problem a relatively ‘easy’ quantum problem to solve. Other papers followed that showed how to extend these attacks to other cases of the HSP.

Cryptographic systems that are within the HSP that have polynomial time attacks include Diffie-Hellman-Merkle (D&H), Rivest-Shamir-Adleman (RSA), and all elliptic curve cryptography. The ability for derivatives of Shor’s algorithm to attack these ciphers in polynomial time has led some prominent experts to describe the mainstream public key technologies as being “flat-lined” by quantum computers and other to say “a significant breakthrough in quantum computation would spell doom for all these [above mentioned] systems” [147].

See: n/a
Derivative Algorithms:
Related work: Grover's algorithm.
Last Updated on Sunday, 04 January 2009 10:58
 
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