WikiProject |Emerging

Quantum computing challenges current cryptography

Talk (27)

RP

Richard Pearce

"Good luck! I have a feeling that i..."
Linh Nguyen

Linh Nguyen

"Thank you Gabriel, appreciate it."
Linh Nguyen

Linh Nguyen

"No worries Richard, I appreciated the..."
RP

Richard Pearce

"I've fried my brain enough. To sum..."

Help report on the implications of quantum computing for the security of encryption.

We’re working on a story intended to outline the history of quantum computing and what the future holds for it at a time when attention is perhaps more on blockchain and artificial intelligence.

Questions we’d like to explore:

  • What is quantum computing?
  • What sort of problems can be solved with quantum computing?
  • How secure is today’s encryption against it?
  • What progress has been made to ensure security is protected?

Key facts and concepts we think are central to the story: 

  • The idea was invented only 30 years ago and is still at a nascent stage.
  • Conventional computers are binary: 1s and 0s that represent on/off states. Quantum computing uses qubits, and can be both 0 or 1 at the same time – a state known as superposition – which is the same phenomenon that allows Schrödinger’s cat to be in two states simultaneously.
  • Superposition allows a quantum computer to process more information, much faster.
  • A quantum computer can, theoretically, solve, in a matter of seconds, calculations that would take millions of years for a conventional computer to solve.

Interviews so far or sought include: 

  • John Preskill, runs the Institute for Quantum Information (IQI) at Caltech.
  • Raymond Laflamme, physicist and former director of the Institute for Quantum Computing at the University of Waterloo, Canada.
  • Edward Farhi, Professor of Physics at MIT.
  • Samuel Leon Braunstein, a professor in Computer Science at the University of York, UK.
  • Martin Albrecht, lecturer in Information Security at Royal Holloway, UK.

What or who would you add to this story? Use EDIT to add to directly or tell us in TALK


Started by

United Kingdom
Linh is a staff journalist at WikiTribune with a background in the humanities. She covers the Middle East, Asia, conflict and technology. Though based in London, she has freelanced across Asia, the UK and U.S.

History for stories "Quantum computing challenges current cryptography"

Select two items to compare revisions

07 February 2018

16:36:58, 07 Feb 2018 . .‎ Peter Bale (Updated → Making WP Primary Category)
15:36:34, 07 Feb 2018 . .‎ Linh Nguyen (Updated → tweak)

05 February 2018

18:28:15, 05 Feb 2018 . .‎ Peter Bale (Updated → New headline and improved summary)
18:26:33, 05 Feb 2018 . .‎ Peter Bale (Updated → Modified headline)
17:57:46, 05 Feb 2018 . .‎ Linh Nguyen (Updated → update)
13:36:05, 05 Feb 2018 . .‎ Linh Nguyen (Updated → tweak)
11:48:15, 05 Feb 2018 . .‎ Linh Nguyen (Updated → tweak)
11:47:24, 05 Feb 2018 . .‎ Linh Nguyen (Updated → tweak)
10:56:00, 05 Feb 2018 . .‎ Peter Bale (Updated → Published)

01 February 2018

17:33:33, 01 Feb 2018 . .‎ Linh Nguyen (Updated → update)
17:32:31, 01 Feb 2018 . .‎ Linh Nguyen (Updated → update)
14:29:07, 01 Feb 2018 . .‎ Linh Nguyen (Updated → update)
14:26:47, 01 Feb 2018 . .‎ Linh Nguyen (Updated → update)
14:22:24, 01 Feb 2018 . .‎ Linh Nguyen (Updated → update)
10:38:28, 01 Feb 2018 . .‎ Linh Nguyen (Updated → made a story headline)

Talk for Story "Quantum computing challenges current cryptography"

Talk about this Story

  1. Rewrite

    I’ve fried my brain enough.

    To summarise my opinion so far, this is a complex scientific field where there appears to be not opposing views (e.g. the Earth is flat, no it isn’t it’s round) but different opinions on how or (even if) quantum computers will or will not work. Fortunately, we worked out that the Earth is actually round in the end and I guess only time will tell us the what ifs of quantum computing.

    D-Wave claim to have a quantum computer that works and there is serious money (Google have deep pockets) being spent on research. Although I’m interested, I’d have to give up work and lock myself in Schrödinger’s box for 20 years if I wanted to work out how quantum computers actually work. I like cats, but not that much! The scientific contention in my mind is how do you observe the unobservable?

    The D-wave machine (https://www.dwavesys.com/d-wave-two-system) is a serious bit of kit and it is definately not a classical computer. It is enclosed in a faraday cage, shielded to 50,000x less than the Earth’s magnetic field. It is also stored in a vacuum (think outer space) where the pressure is 10 billion times lower than our atmospheric pressure and interestingly it doesn’t use much power (which I can guarantee will be of interest to Google because their electricity bill must be huge).

    The quantum processor (where the stuff we can’t observe happens) has 2000 tiny (this is quantum tech so tiny is a bit of an understatement) superconducting devices (which maybe where the NASA come in as they have done some serious research on superconductors). They are cooled to 180x colder than interstellar space and generate no heat. This is important because I’m guessing they are observing quantum energy to create the classical ones and zeros that we use in the real world.

    I can’t claim to understand how the quantum calculations work and tbh I don’t want to as I’d probably end up looking like a Borg whilst singing the Tra La La song from the Banana Splits. But they say it works with models that search for the “lowest energy point in a vast landscape” and (this is the quantum bit) considers all possibilities at the same time to determine the lowest energy and the values that produce it. Which I guess is like DNA research; they are looking for something but they aren’t sure what or where it is. I don’t walk around all day in a white coat but if you do and you really want to bake your noodle, there is a load of research here https://www.dwavesys.com/resources/publications. Someone wrote them so I guess others read them, personally I’d prefer to be having a pint.

    They don’t say much about the hum though so I guess that’s the clever bit that interfaces the quantum environment with the real world, probably using resonance to make the connection.

    I’m surprised it doesn’t float too, maybe they have it bolted to the floor 🙂

  2. Other

    This looks worth investigating:

    http://www.mondovisione.com/media-and-resources/news/date-change-report-launch-the-quantum-countdown-quantum-computing-and-the-fu/

    Distributed Futures would probably be happy for some press on their report and it sounds like it overlaps significantly with your focus here.

    1. Rewrite
  3. Other

    This is a huge leap of logic on my part but I figured I’d put it out there anyway….

    I was thinking about the question of how do you view the outcome of a quantum process without actually observing it?

    We know that when we observe quantum phenomena it changes so it then follows that it must be impossible to process quantum information. This we know is true, except perhaps (and thinking of the DNA analogy of not looking for something but looking instead for a difference that helps us identify a particular trait) what if we don’t look at the quantum phenomena but look at the energy that it produces instead? Geordie Rose mentioned that they are using a sound (or vibration) in their machine and I know that we can see sound https://www.youtube.com/watch?v=wvJAgrUBF4w

    After watching that video, it reminded me that Nikola Tesla (who invented alternating current and would be naive to ignore as a crackpot) also spoke about making a camera that could capture an image of a thought.

    Given that we can’t “see” a thought but our eyes do transfer an image of the world around us which allows us to create an image of that world in our mind, perhaps these quantum computers are using a type of retina or camera to see the wave/frequency/effect created by the quantum information/energy which the classical component of that computer can then process?

    As Tesla said; “If you want to find the secrets of the universe, think in terms of energy, frequency and vibration”.

    1. Rewrite

      No worries Richard, I appreciated the effort of the leap.

      I myself am fond of Einstein’s description: “spooky action at a distant.”

      In answer to your previous reply, I didn’t pick the subject per se! A community member suggested it, I found it interesting, so thought I should explore it further.

      I’ve reached out to D-Wave but unfortunately no-one is available to speak with me. However, I’ll give Kindred a go, since AI will significantly be affected by quantum computing – perhaps even allow it to reach the singularity? 😛

      1. Rewrite

        Good luck!

        I have a feeling that if quantum technology does take off, it will, like all new things, be the pioneers that will want to make the money from their investment. With that in mind, they may not want to tell you too much about what they are up to.

        I thought it was interesting that D-Wave don’t mention AI when they talk about possible applications;

        – Optimization
        – Machine learning
        – Sampling / Monte Carlo
        – Pattern recognition and anomaly detection
        – Cyber security
        – Image analysis
        – Financial analysis
        – Software / hardware verification and validation
        – Bioinformatics / cancer research

        Maybe that’s because it’s the service that Kindred are pushing and they don’t want to compete with each other.

        In regards to AI, some of the theoretical possibilities scare the sh*t out of me but that’s another subject entirely!

  4. Other

    I recommend you add Eric Ladizinsky to the list of people to interview.

    https://www.youtube.com/watch?v=0uMfGxOIE0g

    1. Other

      Oh, and Geordie Rose, but be warned; you have already interviewed him and he he knows what questions you asked and the answers he gave you 🙂

      https://www.youtube.com/watch?v=cD8zGnT2n_A

      1. Rewrite

        Thank you so much Richard, I am grateful for your suggestions.

  5. Other

    As far as I know, the concerns about quantum computing’s effect on cryptography is isolated to the public key variety. In practical terms, that is far and away the type of cryptography which people encounter in daily life. But it doesn’t have to be.

    The only challenge unique to private key cryptography is secure key exchange. And the whole point of cryptography is that it secures the contents of a message even if the message is accessed. Which means that you could walk into your bank and they could generate an encryption key tied to your account. Then when you want to buy something online, they can generate a key specifically for you which they encrypt and send to their bank where it is re-encrypted, sent to your bank and then re-encrypted and sent to you. Aside from the one trip to the bank, all of the details could be invisible to the user. There is no risk from the third and fourth parties being exposed to the key, since they were going to record the resulting financial transaction anyway. And having the two banks verifying the identity of you and the online vendor gives an additional level of security. (There’s also nothing to prevent public keys to be passed like this, in fact it sounds like a good idea.)

    And I think it would be wise to rethink cryptography for reasons beyond quantum computing. Cryptography is one piece of computer security and certainly not a panacea. With insecure OSes, software, hardware and hacked companies, all of the end points are at risk of being compromised which renders cryptography a moot point. But with public key cryptography in particular, I feel like people tend to invest too much faith. I find the concept of a trapdoor function (the theoretical argument for the security of most public key cryptography) to be dubious. That aside, cryptography is an intellectual arms race and time favors the breakers over the makers. Which is to say, we should never expect permanent secrecy from cryptography.

    To that last point, I’ve actually discovered a vulnerability in RSA which allows for decryption without factoring the semiprime. I have working attack code which looks promising. And I’ve been finding some additional features to exploit which I think will put smaller keys at risk from a supercomputer (but that’s pretty speculative).

    https://www.reddit.com/r/cryptography/comments/7t7a0p/attacking_rsa_without_factoring_a_viable_and/

    The same approach will be effective against any semiprime based cryptography. And as I understand it, discrete logarithm algorithms, too.

    1. Rewrite

      Thank you Gabriel, you clearly know a lot about the subject matter of cryptography and have raised some thoughtful points. Is there any further reading you think I should?

      1. Rewrite

        The Wikipedia pages for RSA and trapdoor function are both really helpful for an introduction to the important concepts (and is about as far as I’ve made it for technical research). A good portion of the cryptography we use is RSA or some variation of it and its security is based on the difficulty of factoring large semiprimes. The theory goes that factoring large semiprimes is a trapdoor function (easy if you know the two prime factors, really hard if you don’t) so a cryptographic algorithm built on information using those two prime factors will be secure.

        This assertion is currently being challenged on two fronts. First, we know that factoring can be done quickly on quantum computers and we are just waiting on the technology to catch up to the application. (This lag of technology behind its planned use reminds me of Ada Lovelace. She was a mathematician who developed the first computer programming language about a hundred years before the first computer.) So for the strictest usage of the term, RSA should be considered broken because we have no way to confirm that people can’t break the encryption today and there is a known way to do so. Secondly, nobody has confirmed its significance but I have found a way to break the encryption without factoring the semiprime. Which means that the problem of decryption without the private key has been decoupled from the factoring challenge. This in and of itself is troubling because there has been no thorough investigation of the vulnerability and therefore no basis to claim that RSA is secure against attacks which exploit it. And then, from what I have seen, the vulnerability does look highly exploitable. (But without a supercomputer, I need to break keys close to real world length on my computer to demonstrate vulnerability. Which would mean RSA is highly insecure.)

        Beyond that, my understanding of these things is primarily from the perspective of an applied mathematician. And sadly, I never had any training on high performance computing type applications (or cryptography, but that’s less exciting). The most insight I do have from school comes from chaos theory, which might be worth looking into. The strict definition of chaos excludes systems which are both discrete and bounded, so the encryption systems we’re talking about don’t qualify. (And I’m not sure if encryption is compatible with true chaos, at least if you want to decrypt again.) But modern cryptosystems are designed to display certain hallmarks of chaos to prevent statistical attacks.

        The one book that jumps out in my mind which may be interesting is “From Clocks To Chaos” by Leon Glass. But that’s getting pretty far from quantum computing, I don’t even recall any mentions of cryptography.

        1. Rewrite

          Hi Gabriel,

          That is very interesting. I am neither a mathematician, nor am I computer scientist but I do have an opinion that I would like to share.

          There appears (to me) at the present time, there are certain mathematical problems that cannot possibly be solved by traditional computing methods, regardless of how powerful our current supercomputers are (or how powerful their decendants ever become in the future). To solve these problems, we need to forget about high performance computing and accept that, in order to solve the unsolveable, we need something else.

          Advances in quantum computing, however, seem to offer a new way of addressing these obstacles where we can approach unsolvable problems in a way that is not available with traditional methods.

          This is important because it will allow us to perform research into what we previously considered the impossible and also to make measurements that traditional computing methods do not and cannot permit. My analogy for this is DNA research; we have no idea what an entire genome consists of, but through scientific analysis of the differences in what we know we can identify unique sequences that relate to a particular genetic trait.

          In the quantum computer world, what we do know is; we don’t know how information will behave at a quantum level when we observe it. We also know that information exists in a number of possible states at all times in an unknown number of (multiple/parallel) systems. It is, however obscure it seems, just data and quantum computing appears to provide an interface where we can ask the questions that we previously considered unaskable.

          1. Rewrite

            Very thoughtful points you’ve raised Richard. So, the idea of quantum computing is that it can solve what a classical computer can’t, and therefore solve more of the world’s problems.

            However, from my research and interviews conducted so far, current progress right now also suggest that it’s unclear whether quantum computing has any use or practical value as of yet. Granted, it’s still early days. Also, because quantum is a whole different paradigm, who’s to say that it can solve the things we hope it can solve? What will these advances lead to? It’s very difficult to know and so far not much indication it would seem.

        2. Rewrite

          Fascinating. The connection between chaos theory, cryptography and quantum computing is rather exciting. I shall explore further and get the book you suggested.

          Also, in reply to your previous comment on how the bit about blockchain seems out of place – you’re right, that was just an initial idea. But the piece has evolved into focusing more on post-quantum cryptography.

          1. Rewrite

            Hi Linh,

            That is correct, I guess it is also safe to say that quantum computers will not replace classical computers or supercomputers (in our currently known universe) any time soon.

            Whether quantum computing will solve the worlds problems (or if it will create problems we are currently unaware of) is questionable and only continuing research will inform us of these possibilities as science progresses. The problem is; how can we find out and therefore know about something that we do not understand or is beyond our current perception of what “is”?

            Quantum mechanics is a rabbit hole of ideas that confuses the hell out of me but what I can see is that quantum computers work with a form of energy that comes from atoms and subatomic particles and classical computers work with the form of energy that we all know of as electricity.

            That’s not to say that quantum computers don’t use electricity, because they do, but they process information in a different manner using the energy signals produced by quantum components instead of electrical pulses. This means they are able to interface with “something” very new to us and that that “something” is not in “this reality”.

            Quantum computers do exist in the real world and companies are buying them for research. I recommend you reach out to D-wave and Kindred Systems to see if they will provide you with some information on any of their customers and what applications those companies are using them for. You can also try contacting Google DeepMind or NASA, you never know, you may get a canned response or you might get something more 🙂 Having a contact name or refferal from the supplier might get you nearer to someone closer to what’s going on.

            Given that Geordie Rose left D-Wave to start Kindred and what Google DeepMind are up to, it’s probably safe to say that artificial intelligence is one application that is currently being developed. I guess once artificial intelligence reaches a certain point, it will be able to use itself to develop quantum computing further.

            Here is another video I recommend you watch; https://www.youtube.com/watch?v=PqN_2jDVbOU

            Kind regards,

            Richard.

            PS. This is a tough subject you’ve picked! How do we explain something that we can’t quite comprehend?

  6. Rewrite

    “Help report on the implications of quantum computing for the booming field of blockchain and the security of encryption.”

    That sentence seems to be out of step with some of the other things you’ve written. Perhaps it would be better with blockchain removed or else you could be clearer that blockchain is a specific focus in other places.

  7. Other

    On February 5, the Washington Post ran a useful story on quantum computing under the following headline: “Quantum computers may be more of an imminent threat than AI.” This story is a good starting point for further coverage.

    1. Rewrite

      Thank you Anthony, I shall look into that.

  8. Other

    “A quantum computer can solve, in a matter of seconds, calculations that would take millions of years for a conventional computer to solve.”

    I think this is still just theoretical at this stage.

    D-Wave’s quantum computers still can’t outperform classical computers.

    1. Rewrite

      Thank you Dan, I’ve made it clearer that it’s still a theory yet to be achieved.

  9. Rewrite

    Some experts in the UK on this topic that I know to be approachable:

    Dr Martin Albrecht, Royal Holloway University of London
    Martin works directly in the area of security, cryptography and thinking about the challenges of quantum computing.
    https://pure.royalholloway.ac.uk/portal/en/persons/martin-albrecht(ab997512-d7f9-4d99-92e1-33967032502b).html

    Dr Vivien Kendon
    Viv is a very experienced researcher and studies the boundary between physics and quantum computing.
    https://www.dur.ac.uk/research/directory/staff/?mode=staff&id=12916

    1. Rewrite

      Thanks very much Adam, these are great suggestions.

  10. Rewrite

    Quantum computing. Suggested expertise:

    U.S. Dept of Energy Office of Science Basic Energy Sciences program supports quantum computing. https://science.energy.gov/bes/

    On that main page see the right navigation under “What’s New” for an SC Statement on Quantum Information Science

    In the “search SC website” box, search for quantum computing. Many DOE labs are engaged in quantum computing. Often on collaboration with major universities.

    Phone and email links are in the left navigation.

    Also in the left navigation review the Basic Energy Sciences Advisory Committee membership list – some of whom may have expertise in quantum computing. Some are from countries other than the U.S.

    The U.S. National Science Foundation funds qusntum physics proposals. Search https://www.nsf.gov for quantum computing and see if any of the scientists who are funded, fit your criteria for expertise in the field.

    Check https://www.nas.nnsa.gov/projects/quantum/ for contacts for the NASA quantum computing program and link to the Universities Space Research Association.

    Search both DOD.mil and dhs.gov

    1. Rewrite

      Thank you Claudia! All very useful stuff.

  11. Rewrite

    Schrödinger’s cat is both alive and dead, not in two places at once.

    1. Rewrite

      You’re right Martin, it should’ve been “two states” not places. It’s corrected now.

Subscribe to our newsletter and be the first to collaborate on our developing stories:

Support Us

Why this is important and why you should care about facts, journalism and democracy

WikiTribune Open menu Close Search Like Previous page Next page Back Next Open menu Close menu Play video RSS Feed Share on Facebook Share on Twitter Share on Reddit Follow us on Instagram Follow us on Youtube Connect with us on Linkedin Email us Message us on Facebook Messenger Save for Later