# Stanford CS251: Lecture 18

### Lecture 18: Advanced Topics

Three topics are chosen by students (another three for the next lecture)

#### Topic 1: Quantum Computing

An electron has two states top and bottom spins, represented as `|1>`

and `|0>`

. An electron is in a superposition of those two states with wave functions Ψ_{0} and Ψ_{1}, so, the combined wave function is Ψ = Ψ_{0}.`|0>`

+ Ψ_{1}.`|1>`

with |Ψ_{0}|^{2} + Ψ_{1}^{2} = 1. |Ψ_{0}|^{2} is the proability of seeing state `|0>`

and Ψ_{1}^{2} is the probability of seeing state `|1>`

respectively. Thus, Ψ = [Ψ_{0}, Ψ_{1}] is the overall state matrix. The state evolves using a 2X2 Hamiltonian matrix H, such that, second-degree norm won’t change, `|| H.V || = || V ||`

. This ensures |Ψ_{0}|^{2} + Ψ_{1}^{2} = 1 always holds.

Ψ_{n} = sum of 2^{n} states = vector of dimension 2^{n} states = Σ Ψ_{w}. `|w>`

where w ∊ [0, 1]^{n} with Σ |Ψ_{w}|^{2} = 1, |Ψ_{w}|^{2} is the probability of seeing the state Ψ_{w}

##### Quantum computer

- System starts with a simple state says
`1.|000...>`

- Apply a sequence of Hamiltonians. There are two universal Hamiltonians. One flips a single electron, the other swaps the state of two electrons.
- Observe final state. Highest amplitude is on the correct answer.

Isolating quantum bits (qubits) from environment is hard. And therefore, building quantum computers is hard.

##### Two applications

- Grover’s algorithm – Consider a problem for a function which takes an n-bit input and a binary output, find the input which produces 1 as output. Classical algorithm takes 2
^{n}. Grover’s algorithm takes 2^{n/2}=> quadratic speedup. This has an implication of solving proof of work way faster => difficulty has to adjust from say 2^{70}to 2^{140}=> Death of mining pools, the only people who can mine will be the one who owns quantum computer. - Shor’s Algorithm – Given a periodic function
`F : G -> Y`

whose period P is unknown, it will take O(G) time to find the period P via brute-force. Shor’s algorithm can find P in`O(Log|G| + time(F))`

=> exponential speedup. Finding period is sufficient to break Discrete logs => Breaks ECDSA => Given public key one can find the private key. Bitcoin has to move to post-quantum crypto like hash-based signatures which are 1024 bytes, much longer than 64-bytes ECDSA or Lattice-based signatures which are 1024 bytes as well.

#### Topic 2: Threshold Signatures

Bitcoin uses multi-sig. Standard approach is inflexibles since one has to commit to signers and thresholds in advance. It is not private since script has to be revealed for spent.

Threshold signatures solves this problem. For any signing algorithm like RSA and BLS (but not ECDSA) where signature = H(m)^{Sk}, one can commit to a particular Sk and then find split it across signers. Multiplying the two signed will verify the correctness. If the parties are trutworthy enough to discard their share, one can easily move from 2-of-2 to 2-of-3 or 3-of-3 setup without changing the commitment. ECDSA is hard to thresholdize.

#### Topic 3: Ethereum Contracts with Secret State

For example, playing Blackjack on Ethereum.

Setup using El-Gamal Public Key encryption. Fix G and g in G. There are two private keys s_{k1} and s_{k2} with public values g^{sk1}and g^{sk2}. Public keys = g^{sk1 + sk2}. El-Gamal has an interesting property called re-randomization, so, a ciphertext, can be randomized to another unlinkable ciphertext using the public key. Decryption can happen in phases using s_{k1} and s_{k2}.

Contract

- Store sorted deck of cards – E(pk, 1), E(pk, 2)…
- Alice shuffle deck and re-randomize – E(pk, a1), E(pk, a2)… and also prove using Zero knowledge that shuffle is valid.
- Bob does the same shuffle and re-randomize. Now contracts stores a shuffled deck ct1, ct2…
- Contract deals two cards to Alice. Bob partially decrypts the two cards and then Alice decrypts the cards. Bob does not know which card Alice has.
- At the end, reveal s
_{k1}and s_{k2}. Contract re-verifies integrity and pays winner.