# Photon phreaking:

## What quantum can (actually) do for security

Gemalto Crypto Club 23 Feb 2017
Alan Robertson
Sarah Kaiser

### Quantum Operations

• Classical: Bitflip
• Quantum: Rotations about some axis
• Quantum: Measurement is the overlap between the state and some basis vector

### Quantum Measurement

• Requires a basis
• Outcomes are non-deterministic
• Destroys phase information, only can measure once

### Quantum System Properties

• No-Cloning Theorem: Quantum states cannot be copied
• Entanglement: The state of a qubit is "correlated" with the state of another qubit
• You cannot describe the effect of a rotation on only one qubit in set of entangled qubits

### Quantum Algorithms

Deutch-Jozsa: Free$^{*}$ parallelism, reduces from $O(2^{n-1})$ to $O(1)$ function calls

Grover's Algorithm: Search an unsorted list for an$^{**}$ element in $O(\sqrt{n})$, best classical is $O(n)$

Shor's Algorithm: A faster prime factoring algorithm, because fourier transforms are unitary

### Shor's Algorithm

GNFS: Generate polynomials and hope that their roots form a smooth ring such that the 'square root' of the ring is a homomorphism to the prime factors

Shor's algorithm: Find the period of the prime field using the quantum fourier transform, the 'square root' then gives the prime factors

## Common Myths and Misconceptions

• Quantum computers are NOT universally faster or more powerful than classical computers

• Quantum computers will NOT be here tomorrow.
have:100 qubits / need: 100 million

• Dwave is NOT a quantum computer. Evidence shows quantum annealer at best

• There is no one right material or system to make qubits

## Why don't we all have quantum keys?

1. Hardware developments

2. Distance/Loss: $\approx 300$ km

3. Realistic device security models