This work completes the definition of a library which provides the basic arithmetic operations in binary finite fields as a set of functional terms with very specific features. Such a functional terms have type in Typeable Functional Assembly (TFA). TFA is an extension of Dual Light Affine Logic (DLAL). DLAL is a type assignment designed under the prescriptions of Implicit Computational Complexity (ICC), which characterises polynomial time costing computations. We plan to exploit the functional programming patterns of the terms in the library to implement cryptographic primitives whose running-time efficiency can be obtained by means of the least hand-made tuning as possible. We propose the library as a benchmark. It fixes a kind of lower bound on the difficulty of writing potentially interesting low cost programs inside languages that can express only computations with predetermined complexity. In principle, every known and future ICC compliant programming language for polynomially costing computations should supply a simplification over the encoding of the library we present, or some set of combinators of comparable interest and difficulty. We finally report on the applicative outcome that our library has and which is a reward we get by programming in the very restrictive scenario that TFA provides. The term of TFA which encodes the inversion in binary fields suggested us a variant of a known and efficient imperative implementation of the inversion itself given by Fong. Our variant, can outperform Fong’s implementation of inversion on specific hardware architectures.

Light combinators for finite fields arithmetic

ROVERSI, Luca
2015-01-01

Abstract

This work completes the definition of a library which provides the basic arithmetic operations in binary finite fields as a set of functional terms with very specific features. Such a functional terms have type in Typeable Functional Assembly (TFA). TFA is an extension of Dual Light Affine Logic (DLAL). DLAL is a type assignment designed under the prescriptions of Implicit Computational Complexity (ICC), which characterises polynomial time costing computations. We plan to exploit the functional programming patterns of the terms in the library to implement cryptographic primitives whose running-time efficiency can be obtained by means of the least hand-made tuning as possible. We propose the library as a benchmark. It fixes a kind of lower bound on the difficulty of writing potentially interesting low cost programs inside languages that can express only computations with predetermined complexity. In principle, every known and future ICC compliant programming language for polynomially costing computations should supply a simplification over the encoding of the library we present, or some set of combinators of comparable interest and difficulty. We finally report on the applicative outcome that our library has and which is a reward we get by programming in the very restrictive scenario that TFA provides. The term of TFA which encodes the inversion in binary fields suggested us a variant of a known and efficient imperative implementation of the inversion itself given by Fong. Our variant, can outperform Fong’s implementation of inversion on specific hardware architectures.
2015
111
3
365
394
http://www.sciencedirect.com/science/article/pii/S0167642315000672
Lambda calculus Finite fields arithmetic Type assignments Implicit computational complexity
Canavese, D.; Cesena, E.; Ouchary, R.; Pedicini, M.; Roversi, L.
File in questo prodotto:
File Dimensione Formato  
CanaveseCesenaOucharyPediciniRoversiSCICO215.pdf

Accesso aperto

Tipo di file: PREPRINT (PRIMA BOZZA)
Dimensione 602.06 kB
Formato Adobe PDF
602.06 kB Adobe PDF Visualizza/Apri
1-s2.0-S0167642315000672-main.pdf

Accesso riservato

Tipo di file: PDF EDITORIALE
Dimensione 691.72 kB
Formato Adobe PDF
691.72 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/1526049
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact