Intro To Cryptography

This, by no means, is a thorough post covering all the topics. This is just my notes that I like to make while learning any new topic. I have tried attaching any good resource I found along the way.

ECC

• ECDSA: Elliptic Curve Signatures - Practical Cryptography for Developers
• Elliptic Curve Cryptography: a gentle introduction

nonce: $r$

temp key: $R=r\ast G$

Signature in ECDSA: $s=k^{-1}\ast (h+r\ast x)(modn)$

EdDSA Algorithm

Used to sign arbitrary messages with private keys

• Public key, $PK:xG$
• Create temp key $R$ from random nonce, $r$: $R=rG$
• $e=Hash(R||m)$
• $s=r+ex$

Public key is known, then send $m,R,s$ to other party

EdDSA Verification

Known: PK, m, r, s

$s.G=r.G+ex.G=R+e.PK$

Other party calculates $e,s.G$ If $LHS=RHS$, then signature is correct

ECDH (Elliptic Curve Diffie-Hellman)

Ways for two parties to exchange information without revealing their private keys

Let there be two parties Alex and Alice,

• Alex has $pk$: $x$, Alice has $pk$: $y$
• Generate public keys: $P_{alex}=xG$, $P_{alice}=yG$
• Send each other public keys
• Calculate new public key $P_s=P_{alex}\ast y$ OR $P_{alice}\ast x$

Threshold Signature Schemes

Contrary to multi-sigs, these signature employ MPCs to create signatures using interactive multiple parties, thus not giving ownership of the asset to only one party while not blowing up computation needs.

Shamir Secret Sharing

• Shamir’s Secret Sharing Algorithm | Cryptography - GeeksforGeeks
• Shamir’s Secret Sharing Scheme

Secret $S$ is divided into $n$ pieces or shares $s_1+s_2+\cdots +s_n$ such than any combination of any $k$ pieces is enough to recover the secret, but any $k-1$ pieces cannot recover $S$.

This is based upon polynomials such that any $k-degree$ polynomial can be uniquely identified using $k+1$ distinct points.

Splitting $S$

• Generating polynomial $f(x)$ of degree $k-1$ over a finite field ${\mathbb{F}}_p$
• generating distinct shares: $s_i=x_i,f(x_i)$

Polynomial is of the form:

$f(x)=S+r_{1}x+\cdots +r_{k-1}{x}^{k-1}$

These $r_i$ coefficients are randomly sampled and the points are generated which are the shares.

Recovering $S$

$S$ is recovered using Lagrange polynomial.

Putting $x=0$, gives us $f(0)=S$

Pitfalls

• Zero-share: Common pitfalls occur during share generation as any shareholder who gets $x_i=0$ has its share as $0,S$, thus revealing the secret.
• Non-unique shares: when generating secret back, the protocol needs to evaluate $\frac{x_m}{x_m-x_j}$ , and if $x_m=x_j(modq)$, then $x_m-x_j$ doesn’t exist and protocol fails.

Fiat-Shamir Heuristic

• Feige-Fiat-Shamir and Zero Knowledge Proof
• Non-Interactive Zero Knowledge Proof - GeeksforGeeks
• Ring Signatures (Part 1): Schnorr Identity Protocol
• Fiat-Shamir transformation

Method to convert interactive ZKP system into non-interactive system such that public verifiability is feasible and both prover and verifier doesn’t need to be online at all times.

Let prover prove to verifier that it possess $s1\cdots sk$secrets co-prime to $N$, without revealing any of the number to verifier. Takes advantage of difficulty of calculating modular square roots as verifier can’t derive $s1$ from $v1$

BLS Signatures

• Math & Engineering
• BLS signatures: better than Schnorr
• BLS12-381

Comes under elliptic curve pairing based schemes which makes aggregation easier than other signature schemes like ECDSA, schnorr.

Two main things used in BLS signatures are:

Hash to Curve

For BLS signature to work, message hashing has to be on the curve i.e. $H(m)$ has to be a point on the curve.

To do this, the method is to concatenate message incrementally with counter to try to find a point.

Pairings

Signature/Proof of possession: $S_X=x.H_{G_1}(X)$

$e(S_X,G_2)=e(H{’}_{G_1}(X),X)$

Commitment Schemes

Prover commits to a message and later opens it to reveal the content of the message without revealing it beforehand.

Zero Knowledge Proof System

• Completeness/Liveness: If prover is correct, it will eventually convince verifier
• Soundness/Safety: prover can only convince verifier if it’s correct
• Zero Knowledge

Proving Schnorr Signatures Are Zero-knowledge

Proving completeness is the easiest part in protocol, i.e. if the prover performs protocol honestly, verifier is able to verify it by just substituting g in schnorr signatures.

Soundness is done through another algorithm called extractor which is able to extract secret of the prover by tricking it. Note: it doesn’t actually reveal the secret but only proving that extractor can extract the secret by duping prover. Done through replay attack on schnorr protocol.

Zero-Knowledgness is proven through a simulator which has no knowledge of the the secret and yet it is able to convince every verifier into believing that the statement is true. This has an assumption that verifier is honest. Done through rewinding a verifier so that prover knows challenge $c$

and forging false signature on the basis of it.

References

• CS-355: Topics in Cryptography; Lecture 5: Proofs of Knowledge, Schnorr’s Protocol, NIZK
• GitHub - jlogelin/fiat-shamir: Zero Knowledge Proofs with Fiat-Shamir Heuristic in Solidity
• Lecture 1: Honest Verifier ZK and Fiat-Shamir: https://www.cs.jhu.edu/~susan/600.641/scribes/lecture11.pdf
• 0xPARC ZK Learning Group
• eth-research ZK learning starter pack
• Road to ZK