1. Notation Group elements (curve points) are capitals $K,R,P,\ldots$ Scalars (field elements) are lowercase $s,k,\ldots$ Scalar multiplication in the group is $[k]P$. Vectors are bold: $\mathbf{D}$. Tuples: $\mathcal{C}$ 2. Components 2.1 Cryptographic Primitives Curve $\mathbf{E}$ defined over field $\mathbb{F}_q$ (supposedly BN254) with group of prime order $\mathbb{F}_r$;
5/26/20231. Problem $f\in \mathbb{F}^d[X]$; $(a_1,a_2,\ldots,a_d)\in \mathbb{F}$ $(c_1,c_2,\ldots,c_d)\in \mathbb{F}$ $c(X)$ such that $c(\omega^i) = a_i$ and $c(\omega^{d + i}) = c_i$ Prove that $f( c(w^i))=c_i$ for all $1 \leq i \leq d$. 2. Warmup: Proof of Division
11/20/2022Dmitry Khovratovich Problem: whenever we implement an algorithm that works over $Z_{N}$, with $N=2^{16}$ or $N=2^{32}$, we need to reduce all computations modulo $N$ and range-check all variables against $N$. These operations are expensive. We suggest a new scheme that implements the mod-$N$ arithmetic without range checks. 1. State of the art: Simplified Plonk Notation: $N =2^n$. First recall (and simplify) how Plonk arranges its witness.
11/18/20221. Notation $n$ -- ring degree (512 or 1024) $q$ -- modulus $=12289 = 3\cdot 2^{12}+1$ $\widehat{\beta} = \lfloor\beta^2\rfloor$ -- max norm (34 034 726 or 70 265 242) $\phi=X^n+1$ 2. Single Signature Verification Inputs:
9/7/2022