Public repository for exercises, challenges and all the needs of the Sparkling Water Bootcamp.
This first week will be focused on the development of one of the building blocks of Cryptography: Finite Fields.
- An introduction to mathematical cryptography - Chapter 1.
- Finite Fields
- Constructing finite fields
- Cyclic groups
- Summary on Montgomery arithmetic
- Mersenne primes
- Implement Montgomery backend for 32 bit fields.
- Implement efficient Mersenne prime backend.
- Implement efficient backend for pseudo-Mersenne primes.
- Compare specific field implementations with ordinary Montgomery arithmetic.
- Serious Cryptography, Chapters 9 & 10.
- Implement naïve version of RSA.
-
$7$ is a generator of the multiplicative group of$Z_p^\star$ , where$p = 2^{64} - 2^{32} +1$ . Find the generators for the$2^{32}$ roots of unity. Find generators for subgroups of order$2^{16} + 1$ and$257$ . - Define in your own words what is a group, a subgroup, a ring and a field.
- What are the applications of the Chinese Remainder Theorem in Cryptography?
- Find all the subgroups of the multiplicative group of
$Z_{29}^\star$
During the second week we'll continue with Finite Fields and begin with Elliptic Curves and dive deeper into Rust
- Moonmath Manual - Chapter 5, until 5.3
- Programming Bitcoin - Chapters 2 & 3.
- Introduction to Mathematical Cryptography - Chapter 5 until 5.5
- Serious Cryptography - Chapters 11 & 12.
- Pairings for Beginners - Chapters 1 & 2
- Define an elliptic curve element type.
- Implement the basic operations: addition and doubling.
- Implement scalar multiplication.
- Check that the point belongs to the correct subgroup.
- The BLS12-381 elliptic curve is given by the equation
$y^2 = x^3 + 4$ and defined over$\mathbb{F}_p$ with p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab. The group generator is given by the point p1 = (0x04, 0x0a989badd40d6212b33cffc3f3763e9bc760f988c9926b26da9dd85e928483446346b8ed00e1de5d5ea93e354abe706c) and the cofactor is$h_1 = 0x396c8c005555e1568c00aaab0000aaab$ . Find the generator$g$ of the subgroup of order r = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001. - Implement a naïve version of the Diffie - Hellman protocol
- Implement point compression and decompression to store elliptic curve points
- Special CTF challenge (will be revealed later)
- Implement BN254
- Implement Secp256k1
- Implement Ed25519
- Polynomials
- Lagrange interpolation
- Lagrange interpolation and secret sharing
- Moonmath - Chapter 3.4
- Convolution polynomial rings - Introduction to Mathematical Cryptography - Chapter 6.9
- Define a polynomial type.
- Implement basic operations, such as addition, multiplication and evaluation.
- Implement Lagrange polynomial interpolation.
- Implement basic version of Shamir's secret sharing.
- STARKs by Sparkling Water Bootcamp
- Lambdaworks Docs
- Stark 101
- Constraints
- Stark 101 - rs
- Anatomy of a STARK
- BrainSTARK
- A summary on FRI low degree testing
- STARKs by Risc0
- Complete STARK-101
- One time pad - Dan Boneh
- Stream ciphers and pseudorandom generators - Dan Boneh
- Attacks - Dan Boneh
- Semantic security - Dan Boneh
- Block ciphers - Dan Boneh
- Serious Cryptography - Chapters 3 - 5.
- Implement AES round function
- Choose a project: STARKs, Sumcheck protocol or Groth16 (or propose a new project)
- STARKs: see week 4.
- Groth16
- DIZK - Groth 16
- Multilinear polynomials and sumcheck protocol
- Implement a multilinear polynomial type with all the basic operations.
- Moonmath Chapters 6 - 8.
- Proofs, Arguments and Zero Knowledge Chapters 1 - 5.
- Overview of modern SNARK constructions
- Pinocchio protocol overview
- Pinocchio implementation
- SNARKs and STARKs
- EthSTARK
- EthSTARK - paper
- STARK paper
- DEEP FRI
- Proximity gaps
- STARKs by Eli Ben-Sasson I
- STARKs by Eli Ben-Sasson II
- Plookup
- LogUp and GKR
- Neptune - Permutation Argument
- Randomized AIR with preprocessing
- PlonkUp
- Lookups by Ingonyama
- LogUp
- Lookups - Halo2
- Implement IPA commitment scheme
- Implement Jacobian coordinates for Elliptic Curves
- Benchmark elliptic curve operations
- Add improvements to fixed base scalar multiplication in Elliptic Curves
- Add BN254 elliptic curve
- Implement Pasta curves
- Implement Lookup arguments for Plonk (Plookup)
- Sumcheck protocol
- Benchmark and optimize multilinear polynomial operations
- Import circuits from gnark or circom to use with Groth16 backend
- Naïve ECC
- Crypto
- Naïve RSA
- Naïve RSA
- Exercises from weeks 1 & 2
- Programming bitcoin EC
- Shamir secret sharing
- Several exercises
- Finite Fields
- Elliptic Curves
- Polynomials
- Extension fields
- Pairings
- Public key encryption
- Symmetric encryption
- Hash functions
- Signatures
- Authenticated encryption
- SNARKs
- STARKs