2025.03.29 Jeff / FoodChain Agenda About Me Motivation ZKP Applications in ZKP About Me

2025.02.19 Agenda About Me tl;dr Motivation What & How? Some examples About Me

Overview This report shows the 1st milestone of zkmopro GPU acceleration. In this milestone, we refactored the EC Backend in Metal Shader, profiled our previous implementation to measure its performance, and developed an optimization plan and criteria for our future work. Tasks :heavy_check_mark: Adapted and refactored a better EC backend for Metal[X] bigint backend implementation [X] field backend implementation [X] montgomery multiplication implementation [X] elliptic curve backend implementation :heavy_check_mark: Profiling Current Metal MSM

Name: Fu-Chuan Chung Student Number: 2941673 Course: MSc Software Development Supervisor: Dr. Nguyen Truong An overview of the system and demonstration. First question Can you briefly explain the ZKP you use in the application? Does it requires interactions between the prover and veriifer? 

Links link to milestone 2 report Things we have done Researched zprize works and papers related to MSM acceleration. Integrate zprize2022/TrapdoorTech works on msm into current mopro and get the benchmark of it. Adapt the benchmarking method arkworks pippenger msm into zprize convention, which using 10 instances of $2^{16}$ points and scalars on BLS12_377 curve as benchmark data. Benchmark Result We set up with the following parameters:

Symmetric Cipher Homophonic Substitution Cipher: Plaintext: HELLO Homophonic substitution: H → 28, 83, 79 E → 31, 22, 19, 75, 91 L → 47, 58 O → 62, 35, 89 Ciphertext: 28 31 47 47 62

Mathematical Foundation of cryptography Theorems and Their Proofs Math Foundations Polynomial Arithmetic Information Theory Symmetric Encryption Feistel Ciphers DES implementaion AES implementation

Some problems Congruence Arithmetics $\text{Exercise 17.}$ $$69x \equiv 5 \pmod{23}$$ $69x \pmod{23} \equiv 0x \pmod{23}$ since $69 | 23$. Therefore, this equation has no solution for $x$. The other way to think:

This is a document for anyone who wants to put their notes or any useful resources in. Shared Notes MM Ch3: Arithmetics MM Ch4: Algebra MM Ch5: Elliptic Curves MM Ch6: Statements MM Ch7: Circuit Compilers MM Ch8: Zero Knowledge Proofs

This is a method to securely generate and exchange key pairs and is universally used not only in the field of cryptography but also computer science. When we were discussed about symmetric encryption, we assume that 2 parties share a same secret key to do encryptions and decryptions. DHM allows these 2 parties to generate a shared secret key over an insecure channel, which can be used in a symmetric encryption and is also followed afterwards by RSA, the other way to exchange keys in asymmetric encryption. Math Explanation DH key exchange protocol allows 2 party to share a secret key, but what do they do in the math? There are 2 people, Alice and Bob, who want to exchange some msg by using the same secret to encrypt and decrypt.

Before drilling into the nitty-gritty of ZKP, we first refer the classic proof system. Proof System is just a interactive process, where composed of a prover and a verifier. Proof System Illustration Proof System Simpified Illustration Prover has to submit the proof (a string/ binary, etc) and the Verifier has to calculate for the result (1 for true/accept; 0 for false/reject). Prover works hard (calculate proof with time) to compute the proof, yet Verifier has limited time to calculate. In the system, the prover and verifier are actually algorithms.

:::info Latest Updated: Feb. 21st, 2024 ::: Things we have done Implement reusable testing interface on iOS app We build the testing inferface that can easily integrate with more MSM algorithms. This resuable feature allow us to move faster in further works about benchmarking other MSM algorithms and find the suitable one with mobile GPU. <u>reproducing steps (from root directory):</u>

This is a method to securely generate and exchange key pairs and is universally used not only in the field of cryptography but also computer science. When we were discussed about symmetric encryption, we assume that 2 parties share a same secret key to do encryptions and decryptions. In fact, DH allows these 2 parties to generate a shared secret key over an insecure channel, which can be used in a symmetric encryption and is also followed afterwards by RSA, the other way to exchange keys in asymmetric encryption. Math Explanation DH key exchange protocol allows 2 party to share a secret key, but what do they do in the math? There are 2 people, Alice and Bob, who want to exchange some msg by using the same secret to encrypt and decrypt.

Arithmetics Arithmetics Algebra Algebra Elliptic Curves Elliptic Curve Elliptic Curve & its importance in cryptography

Personal Notes Recursive SNARK (1) Recursive SNARK (2) Moon Math Manual Note Roadmap Prequals[ ] 1. From AIRs to RAPs [ ] 2. A Brief History of Lookup Arguments [ ] 3. Multiset checks in PLONK and Plookup [ ] 4. Spartan: Efficient and general-purpose zkSNARKs without trusted setup

Some terminology plaintext: original message needed to be transmitted. ciphertext: the encrypted data which is "unreadable". cipher: the math or algorithms responsible for turning plaintext into ciphertext.Stream cipher Block cipher Encryption: process of {plaintext > ciphertext} Decrpytion: process of {ciphertext > plaintext}

This note documents some common theorems and the proofs of them. Fermat's Little Theorem if $p$ is a prime number, then for any integer $a$ that is not divisible by $p$, it holds $a^{p-1} \equiv 1 \pmod p$.

:::info Latest Updated: Jan. 31st, 2024 ::: This page illustrate what we have done in milestone 2 for mopro issue #21. In this milestone, we will focus on swift tests in mopro-ffi, where rust code would be called in swift functions and we will test the utility and efficiency of msm-benchmark method. Main modifications default feature in mopro-ffi/Cargo.toml is changed to default=["gpu-benchmarks"]. Thus, we don't have to use --features flag to enable gpu-benchmarks here.

:::info Latest Updated: Jan. 17th, 2024 ::: This page illustrate what we did in milestone 1 for mopro issue #21. Current work can be seen in this branch Things we have done Implement msm benchmarking

SNARK Recap $S(C)$ --> public parameters $(pp, vp)$ for prover and verifier. $P(pp, x, w)$ --> proof $\pi$ $V(vp, x, \pi)$ --> accept or reject Why do we recursive SNARK? There are multiple SNARK proof system and each of them has their advantage and disadvantage. For example, groth16 could generate a short proof, yet the prover time is quite long ($O(n \log{n})$, as we call it quasilinear).Another example is FRI-based proofs, which has a faster proof but larger proof.