Hardware Accelerator for the Tate Pairing in Characteristic Three Based on Karatsuba-Ofman Multipliers

Jean-Luc Beuchat; Jérémie Detrey; Nicolas Estibals; Eiji Okamoto; Francisco Rodríguez-Henríquez

inria-00424011, version 1

Hardware Accelerator for the Tate Pairing in Characteristic Three Based on Karatsuba-Ofman Multipliers

Jean-Luc Beuchat ()^a^, 1, Jérémie Detrey ()^b^, 2, Nicolas Estibals ()^c^, 2, Eiji Okamoto () ¹, Francisco Rodríguez-Henríquez ()^d^, 3

11th International Workshop on Cryptographic Hardware and Embedded Systems - CHES 2009 5747 (2009) 225-239

Résumé : This paper is devoted to the design of fast parallel accelerators for the cryptographic Tate pairing in characteristic three over supersingular elliptic curves. We propose here a novel hardware implementation of Miller's loop based on a pipelined Karatsuba-Ofman multiplier. Thanks to a careful selection of algorithms for computing the tower field arithmetic associated to the Tate pairing, we manage to keep the pipeline busy. We also describe the strategies we considered to design our parallel multiplier. They are included in a VHDL code generator allowing for the exploration of a wide range of operators. Then, we outline the architecture of a coprocessor for the Tate pairing over $\mathbb{F}_{3^m}$. However, a final exponentiation is still needed to obtain a unique value, which is desirable in most of the cryptographic protocols. We supplement our pairing accelerator with a coprocessor responsible for this task. An improved exponentiation algorithm allows us to save hardware resources. According to our place-and-route results on Xilinx FPGAs, our design improves both the computation time and the area-time trade-off compared to previoulsy published coprocessors.

a – University of Tsukuba
b – INRIA
c – Université Henri Poincaré - Nancy I
d – Insituto Politécnico Nacional
1 : Laboratory of Cryptography and Information Security (LCIS)
University of Tsukuba
2 : CACAO (INRIA Lorraine - LORIA)
CNRS : UMR7503 – INRIA – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
3 : Centro de Investigacion y de Estudios Avanzados del Instituto Politécnico Nacional (CINVESTAV)
Centro de Investigacion y de Estudios Avanzados del IPN

inria-00424011, version 1
http://hal.inria.fr/inria-00424011
oai:hal.inria.fr:inria-00424011
Contributeur : Jérémie Detrey <>
Soumis le : Mardi 13 Octobre 2009, 16:46:51
Dernière modification le : Mardi 22 Décembre 2009, 15:28:39

Voir la fiche détaillée

Documents associés

PDF :

DOI : 10.1007/978-3-642-04138-9_17

Exporter

Bibtex EndNote TEI RefWorks

%% inria-00424011, version 1
%% http://hal.inria.fr/inria-00424011
@inproceedings{beuchat:inria-00424011,
    hal_id = {inria-00424011},
    url = {http://hal.inria.fr/inria-00424011},
    title = {{Hardware Accelerator for the Tate Pairing in Characteristic Three Based on Karatsuba-Ofman Multipliers}},
    author = {Beuchat, Jean-Luc and Detrey, J{\'e}r{\'e}mie and Estibals, Nicolas and Okamoto, Eiji and Rodr{\'\i}guez-Henr{\'\i}quez, Francisco},
    abstract = {{This paper is devoted to the design of fast parallel accelerators for the cryptographic Tate pairing in characteristic three over supersingular elliptic curves. We propose here a novel hardware implementation of Miller's loop based on a pipelined Karatsuba-Ofman multiplier. Thanks to a careful selection of algorithms for computing the tower field arithmetic associated to the Tate pairing, we manage to keep the pipeline busy. We also describe the strategies we considered to design our parallel multiplier. They are included in a VHDL code generator allowing for the exploration of a wide range of operators. Then, we outline the architecture of a coprocessor for the Tate pairing over $\mathbb{F}\_{3^m}$. However, a final exponentiation is still needed to obtain a unique value, which is desirable in most of the cryptographic protocols. We supplement our pairing accelerator with a coprocessor responsible for this task. An improved exponentiation algorithm allows us to save hardware resources. According to our place-and-route results on Xilinx FPGAs, our design improves both the computation time and the area-time trade-off compared to previoulsy published coprocessors.}},
    language = {Anglais},
    affiliation = {Laboratory of Cryptography and Information Security - LCIS , CACAO - INRIA Lorraine - LORIA , Centro de Investigacion y de Estudios Avanzados del Instituto Polit{\'e}cnico Nacional - CINVESTAV},
    booktitle = {{11th International Workshop on Cryptographic Hardware and Embedded Systems - CHES 2009}},
    publisher = {Springer},
    pages = {225-239},
    address = {Lausanne, Suisse},
    volume = {5747},
    editor = {Christophe Clavier and Kris Gaj },
    series = {Lecture Notes in Computer Science },
    audience = {internationale },
    doi = {10.1007/978-3-642-04138-9\_17 },
    year = {2009},
    month = Sep,
    pdf = {http://hal.inria.fr/inria-00424011/PDF/bdeor\_ches2009.pdf},
}

%F inria-00424011, version 1
%0 Conference Proceedings
%U http://hal.inria.fr/inria-00424011
%2 INFO:INFO_CR;INFO:INFO_AO;INFO:INFO_AR
%T Hardware Accelerator for the Tate Pairing in Characteristic Three Based on Karatsuba-Ofman Multipliers
%A Beuchat, Jean-Luc
%A Detrey, Jérémie
%A Estibals, Nicolas
%A Okamoto, Eiji
%A Rodríguez-Henríquez, Francisco
%+ Laboratory of Cryptography and Information Security - LCIS , CACAO - INRIA Lorraine - LORIA , Centro de Investigacion y de Estudios Avanzados del Instituto Politécnico Nacional - CINVESTAV
%X This paper is devoted to the design of fast parallel accelerators for the cryptographic Tate pairing in characteristic three over supersingular elliptic curves. We propose here a novel hardware implementation of Miller's loop based on a pipelined Karatsuba-Ofman multiplier. Thanks to a careful selection of algorithms for computing the tower field arithmetic associated to the Tate pairing, we manage to keep the pipeline busy. We also describe the strategies we considered to design our parallel multiplier. They are included in a VHDL code generator allowing for the exploration of a wide range of operators. Then, we outline the architecture of a coprocessor for the Tate pairing over $\mathbb{F}_{3^m}$. However, a final exponentiation is still needed to obtain a unique value, which is desirable in most of the cryptographic protocols. We supplement our pairing accelerator with a coprocessor responsible for this task. An improved exponentiation algorithm allows us to save hardware resources. According to our place-and-route results on Xilinx FPGAs, our design improves both the computation time and the area-time trade-off compared to previoulsy published coprocessors.
%G Anglais
%8 2009-09-00
%2 internationale
%B 11th International Workshop on Cryptographic Hardware and Embedded Systems - CHES 2009
%2 Lausanne
%2 Suisse
%8 2009-09-06
%8 2009-09-09
%E Christophe Clavier and Kris Gaj
%I Springer
%2 Cryptographic Hardware and Embedded Systems - CHES 2009
%V 5747
%N Lecture Notes in Computer Science
%P 225-239
%R 10.1007/978-3-642-04138-9_17

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Communications avec actes</head>
<biblStruct type="inproceedings" xml:id="inria-00424011"><analytic>
<author><persName><forename>Jean-Luc</forename><surname>Beuchat</surname></persName>
<affiliation>
<orgName type="laboratory">LCIS</orgName>
<orgName type="team">Laboratory of Cryptography and Information Security</orgName>
<country>JP</country>
<orgName type="institution">University of Tsukuba</orgName>
</affiliation>
</author>
<author><persName><forename>Jérémie</forename><surname>Detrey</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">CACAO</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Nicolas</forename><surname>Estibals</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">CACAO</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Eiji</forename><surname>Okamoto</surname></persName>
<affiliation>
<orgName type="laboratory">LCIS</orgName>
<orgName type="team">Laboratory of Cryptography and Information Security</orgName>
<country>JP</country>
<orgName type="institution">University of Tsukuba</orgName>
</affiliation>
</author>
<author><persName><forename>Francisco</forename><surname>Rodríguez-Henríquez</surname></persName>
<affiliation>
<orgName type="laboratory">CINVESTAV</orgName>
<orgName type="team">Centro de Investigacion y de Estudios Avanzados del Instituto Politécnico Nacional</orgName>
<country>MX</country>
<orgName type="institution">Centro de Investigacion y de Estudios Avanzados del IPN</orgName>
</affiliation>
</author>
<title type="main" level="a">Hardware Accelerator for the Tate Pairing in Characteristic Three Based on Karatsuba-Ofman Multipliers</title></analytic><monogr><meeting>11th International Workshop on Cryptographic Hardware and Embedded Systems - CHES 2009</meeting><imprint><publisher>Springer</publisher><pubPlace><settlement>Lausanne</settlement><country>Suisse</country></pubPlace><biblScope type="publicationDate">2009-09-00</biblScope><biblScope type="vol">5747</biblScope><biblScope type="pp">225-239</biblScope></imprint></monogr><idno type="doi">10.1007/978-3-642-04138-9_17</idno><idno type="HALid">http://hal.inria.fr/inria-00424011</idno><idno type="HALFile">http://hal.inria.fr/inria-00424011/PDF/bdeor_ches2009.pdf</idno></biblStruct>
</listBibl>
</listBibl>