Opened 7 years ago

Closed 3 years ago

#9667 closed defect (wontfix)

Consider batch-exponentiation tricks to improve ntor performance

Reported by: nickm Owned by:
Priority: Medium Milestone: Tor: unspecified
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-relay, performance, ntor
Cc: Actual Points:
Parent ID: #9662 Points:
Reviewer: Sponsor:


In the ntor paper, the authors say:

In our protocol the server needs to compute Xb and Xy. Since the base is the same, squarings in the squareand-multiply algorithm can be parallelized [MN96] reducing the computational cost to 1.33 exponentiations. Further improvements such the \Exponent Combination Method" [MN96, x2.3] can be applied to the computation of the server. However such algorithms further increase the complexity of the computations and the improvements are not always clear cut.

This is why they list "1.33" online exponentiations, while our naive implementation has 2.

We should examine whether we can actually use some/all of these techniques. (I believe there has been some discussion on the point on tor-dev already; anybody want to dig up a link?)

Child Tickets

Change History (6)

comment:1 Changed 7 years ago by rransom

Curve25519 implementations use the ‘Montgomery ladder’ (a fixed differential addition chain which is easy to implement in a side-channel-resistant manner), not the ‘square-and-multiply method’. The square-and-multiply method would be unacceptably slow.

Brauer's algorithm (on Edwards-form group elements) might be worth considering.

comment:2 Changed 6 years ago by nickm

Milestone: Tor: 0.2.5.x-finalTor: 0.2.???

comment:3 Changed 4 years ago by teor

Milestone: Tor: 0.2.???Tor: 0.3.???

Milestone renamed

comment:4 Changed 3 years ago by nickm

Keywords: tor-03-unspecified-201612 added
Milestone: Tor: 0.3.???Tor: unspecified

Finally admitting that 0.3.??? was a euphemism for Tor: unspecified all along.

comment:5 Changed 3 years ago by nickm

Keywords: tor-03-unspecified-201612 removed

Remove an old triaging keyword.

comment:6 Changed 3 years ago by nickm

Resolution: wontfix
Severity: Normal
Status: newclosed
Note: See TracTickets for help on using tickets.