Comments (4)
It seems using Jacobian coordinates, while offering a speed-up of ~10% in the computation of s.G + h.P in the Schnorr signature verification, would be tricky to integrate inside our AIR program, as they are not complete and we would need a selector for the first bit set to 1 in the scalar multiplication (adding P. to acc = Infinity) to just assign the value of P instead of computing the addition.
Complete addition formulas for Jacobian coordinates, while possible, would induce a higer bidegree, which would make then impractical with respect to existing Projective coordinates formulas.
from cheetah.
The use of Jacobian coordinates now that Lookups are integrated would actually be much more beneficial (while still problematic in the AIR program). In particular, we now have 256 doublings and 64 additions (compared to 256 doublings and 256 additions with prior double-and-add algorithms) for a scalar multiplication, i.e. 80% of doublings.
from cheetah.
There's actually one issue with the use of Jacobian coordinates is constant-time addition of points (either homogenous or mixed with an affine point). While doubling can be made easily constant-time and still efficient (necessitating a final check before returning, similarly to its projective counterpart), there is no efficient exception-free jacobian addition formula, which requires to perform several additional checks (whether p1 or p2 is the infinity point, or if p1 = +/- p2), which would make any jacobian scalar multiplication non-competitive with the existing projective coordinates based one.
from cheetah.
It may make sense to have Jacobian coordinates (or variants) for variable-time operation purposes only, as in that case it would be faster than equivalent variable time scalar multiplication methods in other coordinate systems.
from cheetah.
Related Issues (17)
- Speed-up scalar multiplication in the group HOT 2
- Add custom implementation of double() and square() HOT 1
- Custom implementation of group operations
- Integrate conditional winterfell-related feature? HOT 1
- Add hashing to curve
- Investigate inline assembly
- Add w-NAF scalar multiplication
- Lookup tables with AffinePoint for Projective scalar multiplication
- Use towered extension internally HOT 2
- Bring back Montgomery form?
- Generalization of Shamir's trick for N points HOT 1
- Faster Fp^6 square root HOT 1
- Custom squaring in Fp HOT 1
- Faster squaring in Fp HOT 1
- Pacify clippy HOT 1
- Scalar reveals the secret value HOT 5
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from cheetah.