From d8080824a94e2c35a7e528a6dfab9f4b9eba4ff0 Mon Sep 17 00:00:00 2001 From: Jade Philipoom Date: Sun, 29 Nov 2015 13:30:28 -0500 Subject: Added roadmap of long term goals and current subtasks. --- roadmap.md | 47 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 47 insertions(+) create mode 100644 roadmap.md (limited to 'roadmap.md') diff --git a/roadmap.md b/roadmap.md new file mode 100644 index 000000000..ecace18a7 --- /dev/null +++ b/roadmap.md @@ -0,0 +1,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 -- cgit v1.2.3