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 + Ψ12 = 1. |Ψ0|2 is the proability of seeing state |0> and Ψ12 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 + Ψ12 = 1 always holds.

Ψn = sum of 2n states = vector of dimension 2n states = Σ Ψw. |w> where w ∊ [0, 1]n with Σ |Ψw|2 = 1, |Ψw|2 is the probability of seeing the state Ψw

Quantum computer

1. System starts with a simple state says 1.|000...>
2. Apply a sequence of Hamiltonians. There are two universal Hamiltonians. One flips a single electron, the other swaps the state of two electrons.
3. 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

1. 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 2n. Grover’s algorithm takes 2n/2 => quadratic speedup. This has an implication of solving proof of work way faster => difficulty has to adjust from say 270 to 2140=> Death of mining pools, the only people who can mine will be the one who owns quantum computer.
2. 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 sk1 and sk2 with public values gsk1and gsk2. Public keys = gsk1 + 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 sk1 and sk2.

Contract

1. Store sorted deck of cards - E(pk, 1), E(pk, 2)…
2. Alice shuffle deck and re-randomize - E(pk, a1), E(pk, a2)… and also prove using Zero knowledge that shuffle is valid.
3. Bob does the same shuffle and re-randomize. Now contracts stores a shuffled deck ct1, ct2…
4. 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.
5. At the end, reveal sk1 and sk2. Contract re-verifies integrity and pays winner.