Finding Optimal Formulae for Bilinear Maps

Razvan Barbulescu; Jérémie Detrey; Nicolas Estibals; Paul Zimmermann

Paper 2012/110 Original: eprint.iacr.org/2012/110 ↗

Finding Optimal Formulae for Bilinear Maps

Razvan Barbulescu

Jérémie Detrey

Nicolas Estibals

Paul Zimmermann

Abstract

We describe a unified framework to search for optimal formulae evaluating bilinear --- or quadratic --- maps. This framework applies to polynomial multiplication and squaring, finite field arithmetic, matrix multiplication, etc. We then propose a new algorithm to solve problems in this unified framework. With an implementation of this algorithm, we prove the optimality of various published upper bounds, and find improved upper bounds.

Metadata

Available format(s): PDF
Publication info: Preprint.
History: 2012-02-29: last updated; 2012-02-29: published
Short URL: https://ia.cr/2012/110
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2012/110,
      author = {Razvan Barbulescu and Jérémie Detrey and Nicolas Estibals and Paul Zimmermann},
      title = {Finding Optimal Formulae for Bilinear Maps},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/110},
      year = {2012},
      url = {https://eprint.iacr.org/2012/110}
}