DISCQ0

To describe the quantum state of this collection of particles, one must specify a number for every possible result of measuring the particles.

These numbers are the amplitudes of the possible outcomes and relate to the probability of the outcome.

To perform operations on the particles:

• hit them with laser pulses or radio waves
• transforms all 2^1000 numbers at the same time.
• read the quantum state

BUT when we measure we will pick out just one possibility at random

Quantum Algorithms

The amplitudes can be positive or negative and can combine SO a good quantum algorithm takes advantage of this:

• computational paths leading to a wrong answer cancel out destructive interference, decreases the probability of finding them

• computational paths leading to a correct answer combine constructive interference, increases the probability of finding them

Alternative cryptography is needed

Confidence

• We need algorithms
• We need randomisation and padding

Usability

• We need protocols
• We need software / hardware

Efficiency

• We need speedups
• We need to know what kind of key sizes to use

Discourse on Implications for

Security and Cryptography

of Quantum Oddness

Uncertainty Principle

“The more precisely the position is determined, the less precisely the momentum is known in this instant, and vice versa.”

Heisenberg, Uncertainty Paper, 1927

2009 researchers at Yale University created the first rudimentary solid-state quantum processor two-qubit superconducting chip was able to run elementary algorithms.

2011 University of Bristol created an all-bulk optics system able to run an iterative version of Shor's algorithm and factorised 21

2011 D-Wave Systems announced the first commercial quantum annealer on the market by the name D-Wave One. The company claims this system uses a 128 qubit processor chipset.

BQP

Factoring

Decoherence

I think I can safely say that nobody understands quantum mechanics.

Richard Feynman, in The Character of Physical Law (1965

...the "paradox" is only a conflict between reality and your feeling of what reality "ought to be."

Richard Feynman, in The Feynman Lectures on Physics, vol III, p. 18-9 (1965)

P

Solve in polynomial time

Number of steps increases in proportion to n^2 Classical computers solve these efficiently.

Test if a number is prime

An efficient solution to one would provide an efficient solution to all.

Effectively the hardest NP problems as no known algorithm is known to solve them efficiently

n x n Suduko

NP-complete

Superposition of states 'collapses' leading to classical behaviour.

Systems need to be isolated from the environment to prevent decoherence

Number of steps to solve increases exponentially

NP

polynomial memory, exponential steps

n x n Chess

n x n Go

PSPACE

Quantum Mechanics

Prepare state

Manipulate the state

Measure state

Graeme Neilson

Aura Information Security

New Zealand

My specialities are cryptanalysis, reverse engineering, networks.

I am not a quantum physicist (in this universe at least)

Questions anytime

• pair of particles interact physically then are separated

• they have an indefinite shared state (eg spin)

• measurement causes one member of such a pair to take on a definite value (eg clockwise spin)

• the other member of the pair will at any subsequent time be found to have taken the appropriately correlated value

Quantum

Computing

Entanglement

A physical system exists partly in all its particular, theoretically possible states simultaneously.

When measured, it gives a result corresponding to only one of the possible configurations

cats

Superposition

Quantum Computer requirements

• number of qubits must be physically scalable.
• initialise qubits to arbitrary values.
• quantum gates must be faster than decoherence time.
• measure: qubits must be read easily.

Scalability not yet proved but...

...how long do you need your data to be secret?

Qubits

Classical 3 Bit Register

{000} or {001} or {010} or {011} or {100} or {101} or {110} or 111 }

Quantum ( Qubit) 3 Bit Register

{ 000 001 010 011 100 101 110 111 }

Qubits = controlled particles + the means of control

A system of n qubits can perform 2^n operations at once

Imagine a 1000-qubit quantum computer. It's state is described by 2^1000 complex numbers...that is a BIG number

• Quantum anything is a field day for marketing
• Scientific peer review needed for crypto
• IP will be invoked

• Common asymmetric may be broken by QC
• Satrt using longer keys for symmetric ciphers
• Hashes are fine

• Watch for developments in post QC

Qonclusion

thank you for listening

this talk may be completely unnecessary as there may never be a successful large scale quantum computer built...in this universe...but somewhere in the multiverse it is necessary

5487-4228-4931-6764-6721

• Physical techniques to generate random secret bits

• Requires direct fibre optic connection between parties

• If implemented correctly its security follows from accepted fundamental laws of physics

Quantum Key Exchange Eavesdropping

2009: Vadim Makarov, Qin Liu, Ilja Gerhardt, Antía Lamas-Linares, Christian Kurtsiefer

Norwegian Institute of Science & Technology

Centre for Quantum Technologies, Singapore

Crypto weaknesses are rarely in theory usually in practice (implementation)

Post Quantum Cryptography Status

• Hash functions are secure.

• Most current symmetric crypto is secure.

• Common asymmetric crypto is NOT secure

Shors Algorithm 1994 [Asymmetric Crypto]

• Exponential speedup factoring primes

• RSA, DSA, ECDSA are now disco

• Does not speed up attacks against AES

• BUT how are AES keys exchanged / stored

Protocol BB84 (Bennett & Brassard 1984)

Prepare and measure individual quantum states of photons.

Protocol E91 (Eckert 1991)

Entagle pairs of photons so they are described by a combined quantum state.

Any eavesdropper measurement of the photons will change their quantum state (Heisenberg Uncertainty Principle).

Quantum

Key

Distribution

I think I want a quantum key generator...

except

• limited to ~100km link lengths (can chain)
• US$50k for key exchange opex?

.

..but I KNOW I want a Quantum Hack Case...

Commercially available for ~ US $50,000

Cool names:

• IdQuantique
• MagicQ
• SmartQuantum
• Quintessence Labs

Keys are regenerated frequently...unhackable...?

Post Quantum

Cryptography

Grover's Algorithm 1996 [Symmetric Crypto]

• Can speed up attacks against symmetric ciphers

• S equals all possible solutions in quantum superposition.

• Correct solution after approx [square root of S] steps.

• Does not transform exponential to polynomial time, only a smaller exponential.

Exploit component imperfections in the single photon detectors.

Send background light to blind detectors and they now work in classical mode (blind to single photons).

Make the detector 'click' by supplying enough light above a threshold.

Fake state above intensity threshold to make detector “click”

Hashing

Any quantum algorithm needs exponential time to solve the collision problem.

Approaches

• Secret key [AES]
• Hash-based [Merkle signature scheme]
• Code-based [McEliece encryption] 1978
• Lattice-based [NTRU and GGH] 2005
• Multivariate-quadratic [HFEv-] 1988