Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Vectorized table select #77

Open
mratsim opened this issue Aug 24, 2020 · 0 comments
Open

Vectorized table select #77

mratsim opened this issue Aug 24, 2020 · 0 comments
Labels
constant time ⏳ Enhancement is suitable for secret data performance 🏁

Comments

@mratsim
Copy link
Owner

mratsim commented Aug 24, 2020

The CMOV instruction that is used for conditional copy is likely optimal for 4~6 limbs.

From Agner Fog tables

image
https://www.agner.org/optimize/instruction_tables.pdf

The throughput is 0.5 hence 2 independent CMOV can be issued per cycle, hence 2-3 cycles are required per Fp element.

However when we have a table precomputed for scalar multiplication/signing with 8 EC elements, each composed of 3 Fp coordinates of 4-6 limbs, using SSE or AVX we can load 2x4 or 2x8 limbs per cycle (2 vector loads per cycle, bottlenecked by memory speed).

This would reduce the overhead of table access. Note that LSB set recoding (#73) uses table with 64 to 256 EC elements (192+ Fp hence thousands of limbs)

i.e. to vectorize:

func secretLookup[T](dst: var T, table: openArray[T], index: SecretWord) =
## Load a table[index] into `dst`
## This is constant-time, whatever the `index`, its value is not leaked
## This is also protected against cache-timing attack by always scanning the whole table
for i in 0 ..< table.len:
let selector = SecretWord(i) == index
dst.ccopy(table[i], selector)

@mratsim mratsim added constant time ⏳ Enhancement is suitable for secret data performance 🏁 labels Aug 24, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
constant time ⏳ Enhancement is suitable for secret data performance 🏁
Projects
None yet
Development

No branches or pull requests

1 participant