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

GT compression #129

Merged
merged 13 commits into from
Jun 20, 2022
Merged

GT compression #129

merged 13 commits into from
Jun 20, 2022

Conversation

yelhousni
Copy link
Collaborator

Compress F_{p^k} elements (E24, E12, E6) when they are in the cyclotomic subgroup, i.e. z^{\Phi_k(p)} == 1. This works in particular to compress GT elements after a pairing. The compression ratio is 1/2 using Torus-based T2 lossless compression following "COMPRESSION IN FINITE FIELDS AND TORUS-BASED CRYPTOGRAPHY", K. RUBIN AND A. SILVERBERG (section 2).

Note we can have a lossless compression with ratio 1/3 using CEILIDH (section 3) if we decide to change the extensions tower (e.g. Fp2-Fp4-Fp12 for E12). This would result is a slightly slower pairing though.

@yelhousni yelhousni added this to the v0.7.0 milestone Jan 19, 2022
@yelhousni yelhousni marked this pull request as draft January 19, 2022 15:01
@mratsim
Copy link

mratsim commented Feb 15, 2022

See also Benger-Scott paper https://eprint.iacr.org/2009/556.pdf

image

Devigili et al https://eprint.iacr.org/2006/471.pdf has the costs between the different towerings and direct sextic:
image
image
image

Timings

image

It seems like the same perf.

And we can change representation (supranational/blst#101 (comment), supranational/blst#102 (review))

@yelhousni yelhousni marked this pull request as ready for review March 16, 2022 17:01
@gbotrel gbotrel modified the milestones: v0.7.0, v0.8.0 Mar 30, 2022
@gbotrel gbotrel removed their request for review June 1, 2022 18:34
@yelhousni yelhousni requested a review from gbotrel June 17, 2022 15:56
@yelhousni yelhousni merged commit c3db6a7 into develop Jun 20, 2022
@yelhousni yelhousni deleted the feat/GT-compression branch June 20, 2022 08:18
@gbotrel gbotrel mentioned this pull request Aug 3, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

4 participants