blob: ecace18a73e37884de7d6a0381507db8c3922dca (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
# Roadmap
A brief overview of possible long-term targets:
- Ed25519 Signing
* Simplistic implementation: constant-time scalar multiplication
* Fast implementation: fixed-base precomputed constant-time scalar multiplication (big tables)
* Hardest part: ModularBaseSystem for exponent field (non-pseudomersenne modular arithmetic)
- Ed25519 Verification
* Simplistic implementation: two non-constant time scalar multiplications, one addition (probably best thing to work on now)
* Fast implemetation: double-scalar multiplication
* Hardest part: optimizing double-scalar multiplication
- Ed25519 Batch Verification
* Simplistic implementation: many single verifications
* Fast implemetation: multi-scalar multiplication
* Hardest part: max-heap of exponent scalars
- Key agreement (X25519)
* X-coordinate-only Montgomery ladder (similar to square-and-multiply, but not identical)
* Hardest part: proving correctness of differential addition (requires field, nontrivial proof)
## Common Subgoals
- Synthesis of optimized modular arithmetic (ModularBaseSystem) -- necessary for all targets
* expression simplification (plus 0, times 1, etc.)
* bounds/no-overflow proofs
* automatic carry-chain synthesis (depends on bounds automation)
* selection (bx + (not b)y) -- necessary for signing and key agreement
- Scalar arithmetic for exponents (non-pseudomersenne modular arithmetic) -- necessary for signing, batch verification
* less performance-critical than ModularBaseSystem for pseudomersenne primes
* constant-time for signing
* add, sub, mul, reduce
- General theorems about elliptic curve arithmetic (requires field; proofs are hard and rely extensively on existing literature)
* addition is commutative
* our representations are interchangable (except MontgomeryX)
- Gallina with Words to Qhasm translation
* simple expressions -- necessary for all targets
* bounded loops -- necessary for all targets
* lookup tables -- necessary for fast signing
* function abstraction -- would improve performance of all targets, most important for fast verification/batch verification
- Wire format specification -- necessary for all targets
* little byte-Endian integers
* point compression
- Wire format decoding -- necessary for all targets
* converting between BaseSystems whose digit weights are different sequences of powers of 2
* single-coordinate point recovery (use X and a single bit to recover (X, Y)); needs field tactic
- Interfacing with hash functions -- necessary for all signature targets
* no specific properties, just that output is determined by input
|
