Paper 2012/110

Finding Optimal Formulae for Bilinear Maps

Razvan Barbulescu, Jérémie Detrey, Nicolas Estibals, and 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
Published elsewhere. Unknown where it was published
Keywords
optimal algorithmspolynomial multiplication and squaringfinite field arithmetictensor rankbilinear mapbilinear rank
Contact author(s)
Jeremie Detrey @ loria fr
History
2012-02-29: received
Short URL
https://ia.cr/2012/110
License
Creative Commons Attribution
CC BY

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},
      note = {\url{https://eprint.iacr.org/2012/110}},
      url = {https://eprint.iacr.org/2012/110}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.