Speeding up Scalar Multiplication in Genus 2 Hyperelliptic Curves with Efficient Endomorphisms

This paper proposes an efficient scalar multiplication algorithm for hyperelliptic curves, which is based on the idea that efficient endomorphisms can be used to speed up scalar multiplication. We first present a new Frobenius expansion method for special hyperelliptic curves that have Gallant‐Lambe...

Full description

Saved in:
Bibliographic Details
Published in:ETRI journal 2005-10, Vol.27 (5), p.617-627
Main Authors: Park, Tae Jun, Lee, Mun‐Kyu, Park, Kunsoo, Chung, Kyo Il
Format: Article
Language:English
Subjects:
Frobenius expansion
Hyperelliptic curve
scalar multiplication
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites cdi_FETCH-LOGICAL-c3227-8c8db1b912764a1065f416cf2ff9204de9a8da0fef7be2606cd7cf5c166417453
container_end_page 627
container_issue 5
container_start_page 617
container_title ETRI journal
container_volume 27
creator Park, Tae Jun
Lee, Mun‐Kyu
Park, Kunsoo
Chung, Kyo Il
description This paper proposes an efficient scalar multiplication algorithm for hyperelliptic curves, which is based on the idea that efficient endomorphisms can be used to speed up scalar multiplication. We first present a new Frobenius expansion method for special hyperelliptic curves that have Gallant‐Lambert‐Vanstone (GLV) endomorphisms. To compute kD for an integer k and a divisor D, we expand the integer k by the Frobenius endomorphism and the GLV endomorphism. We also present improved scalar multiplication algorithms that use the new expansion method. By our new expansion method, the number of divisor doublings in a scalar multiplication is reduced to a quarter, while the number of divisor additions is almost the same. Our experiments show that the overall throughputs of scalar multiplications are increased by 15.6 to 28.3 % over the previous algorithms when the algorithms are implemented over finite fields of odd characteristics.
doi_str_mv 10.4218/etrij.05.0104.0171
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_27981473</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>27981473</sourcerecordid><originalsourceid>FETCH-LOGICAL-c3227-8c8db1b912764a1065f416cf2ff9204de9a8da0fef7be2606cd7cf5c166417453</originalsourceid><addsrcrecordid>eNqNkL1OwzAUhS0EEqXwAkye2FJsx7GTEVWBIhUh0bJiuc41dZUfYydUfXtSygOw3Luc7-joQ-iWkhlnNL-HPrjdjGQzQgkfj6RnaMJYmiYyZeIcTShjWSK4SC_RVYw7QhjhWT5BHysPULn2Ew8er4yudcAvQ907Xzuje9e12LX4CdohYoYXBw8B6tr53hk8H8I3RLx3_RaX1jrjoO1x2VZd0wW_dbGJ1-jC6jrCzd-fovfHcj1fJMvXp-f5wzIxKWMyyU1ebeimoEwKrikRmeVUGMusLcahFRQ6rzSxYOUGmCDCVNLYzFAhOJU8S6fo7tTrQ_c1QOxV46IZl-oWuiEqJouccpmOQXYKmtDFGMAqH1yjw0FRoo4q1a9KRTJ1VKmOKkcoP0F7V8PhH4Qq12-MCCrTHy0Ieuw</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>27981473</pqid></control><display><type>article</type><title>Speeding up Scalar Multiplication in Genus 2 Hyperelliptic Curves with Efficient Endomorphisms</title><source>Alma/SFX Local Collection</source><creator>Park, Tae Jun ; Lee, Mun‐Kyu ; Park, Kunsoo ; Chung, Kyo Il</creator><creatorcontrib>Park, Tae Jun ; Lee, Mun‐Kyu ; Park, Kunsoo ; Chung, Kyo Il</creatorcontrib><description>This paper proposes an efficient scalar multiplication algorithm for hyperelliptic curves, which is based on the idea that efficient endomorphisms can be used to speed up scalar multiplication. We first present a new Frobenius expansion method for special hyperelliptic curves that have Gallant‐Lambert‐Vanstone (GLV) endomorphisms. To compute kD for an integer k and a divisor D, we expand the integer k by the Frobenius endomorphism and the GLV endomorphism. We also present improved scalar multiplication algorithms that use the new expansion method. By our new expansion method, the number of divisor doublings in a scalar multiplication is reduced to a quarter, while the number of divisor additions is almost the same. Our experiments show that the overall throughputs of scalar multiplications are increased by 15.6 to 28.3 % over the previous algorithms when the algorithms are implemented over finite fields of odd characteristics.</description><identifier>ISSN: 1225-6463</identifier><identifier>EISSN: 2233-7326</identifier><identifier>DOI: 10.4218/etrij.05.0104.0171</identifier><language>eng</language><subject>Frobenius expansion ; Hyperelliptic curve ; scalar multiplication</subject><ispartof>ETRI journal, 2005-10, Vol.27 (5), p.617-627</ispartof><rights>2005 ETRI</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c3227-8c8db1b912764a1065f416cf2ff9204de9a8da0fef7be2606cd7cf5c166417453</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Park, Tae Jun</creatorcontrib><creatorcontrib>Lee, Mun‐Kyu</creatorcontrib><creatorcontrib>Park, Kunsoo</creatorcontrib><creatorcontrib>Chung, Kyo Il</creatorcontrib><title>Speeding up Scalar Multiplication in Genus 2 Hyperelliptic Curves with Efficient Endomorphisms</title><title>ETRI journal</title><description>This paper proposes an efficient scalar multiplication algorithm for hyperelliptic curves, which is based on the idea that efficient endomorphisms can be used to speed up scalar multiplication. We first present a new Frobenius expansion method for special hyperelliptic curves that have Gallant‐Lambert‐Vanstone (GLV) endomorphisms. To compute kD for an integer k and a divisor D, we expand the integer k by the Frobenius endomorphism and the GLV endomorphism. We also present improved scalar multiplication algorithms that use the new expansion method. By our new expansion method, the number of divisor doublings in a scalar multiplication is reduced to a quarter, while the number of divisor additions is almost the same. Our experiments show that the overall throughputs of scalar multiplications are increased by 15.6 to 28.3 % over the previous algorithms when the algorithms are implemented over finite fields of odd characteristics.</description><subject>Frobenius expansion</subject><subject>Hyperelliptic curve</subject><subject>scalar multiplication</subject><issn>1225-6463</issn><issn>2233-7326</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2005</creationdate><recordtype>article</recordtype><recordid>eNqNkL1OwzAUhS0EEqXwAkye2FJsx7GTEVWBIhUh0bJiuc41dZUfYydUfXtSygOw3Luc7-joQ-iWkhlnNL-HPrjdjGQzQgkfj6RnaMJYmiYyZeIcTShjWSK4SC_RVYw7QhjhWT5BHysPULn2Ew8er4yudcAvQ907Xzuje9e12LX4CdohYoYXBw8B6tr53hk8H8I3RLx3_RaX1jrjoO1x2VZd0wW_dbGJ1-jC6jrCzd-fovfHcj1fJMvXp-f5wzIxKWMyyU1ebeimoEwKrikRmeVUGMusLcahFRQ6rzSxYOUGmCDCVNLYzFAhOJU8S6fo7tTrQ_c1QOxV46IZl-oWuiEqJouccpmOQXYKmtDFGMAqH1yjw0FRoo4q1a9KRTJ1VKmOKkcoP0F7V8PhH4Qq12-MCCrTHy0Ieuw</recordid><startdate>200510</startdate><enddate>200510</enddate><creator>Park, Tae Jun</creator><creator>Lee, Mun‐Kyu</creator><creator>Park, Kunsoo</creator><creator>Chung, Kyo Il</creator><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>200510</creationdate><title>Speeding up Scalar Multiplication in Genus 2 Hyperelliptic Curves with Efficient Endomorphisms</title><author>Park, Tae Jun ; Lee, Mun‐Kyu ; Park, Kunsoo ; Chung, Kyo Il</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c3227-8c8db1b912764a1065f416cf2ff9204de9a8da0fef7be2606cd7cf5c166417453</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2005</creationdate><topic>Frobenius expansion</topic><topic>Hyperelliptic curve</topic><topic>scalar multiplication</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Park, Tae Jun</creatorcontrib><creatorcontrib>Lee, Mun‐Kyu</creatorcontrib><creatorcontrib>Park, Kunsoo</creatorcontrib><creatorcontrib>Chung, Kyo Il</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>ETRI journal</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Park, Tae Jun</au><au>Lee, Mun‐Kyu</au><au>Park, Kunsoo</au><au>Chung, Kyo Il</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Speeding up Scalar Multiplication in Genus 2 Hyperelliptic Curves with Efficient Endomorphisms</atitle><jtitle>ETRI journal</jtitle><date>2005-10</date><risdate>2005</risdate><volume>27</volume><issue>5</issue><spage>617</spage><epage>627</epage><pages>617-627</pages><issn>1225-6463</issn><eissn>2233-7326</eissn><abstract>This paper proposes an efficient scalar multiplication algorithm for hyperelliptic curves, which is based on the idea that efficient endomorphisms can be used to speed up scalar multiplication. We first present a new Frobenius expansion method for special hyperelliptic curves that have Gallant‐Lambert‐Vanstone (GLV) endomorphisms. To compute kD for an integer k and a divisor D, we expand the integer k by the Frobenius endomorphism and the GLV endomorphism. We also present improved scalar multiplication algorithms that use the new expansion method. By our new expansion method, the number of divisor doublings in a scalar multiplication is reduced to a quarter, while the number of divisor additions is almost the same. Our experiments show that the overall throughputs of scalar multiplications are increased by 15.6 to 28.3 % over the previous algorithms when the algorithms are implemented over finite fields of odd characteristics.</abstract><doi>10.4218/etrij.05.0104.0171</doi><tpages>11</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1225-6463
ispartof ETRI journal, 2005-10, Vol.27 (5), p.617-627
issn 1225-6463
2233-7326
language eng
recordid cdi_proquest_miscellaneous_27981473
source Alma/SFX Local Collection
subjects Frobenius expansion
Hyperelliptic curve
scalar multiplication
title Speeding up Scalar Multiplication in Genus 2 Hyperelliptic Curves with Efficient Endomorphisms
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-08T04%3A33%3A18IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Speeding%20up%20Scalar%20Multiplication%20in%20Genus%202%20Hyperelliptic%20Curves%20with%20Efficient%20Endomorphisms&rft.jtitle=ETRI%20journal&rft.au=Park,%20Tae%20Jun&rft.date=2005-10&rft.volume=27&rft.issue=5&rft.spage=617&rft.epage=627&rft.pages=617-627&rft.issn=1225-6463&rft.eissn=2233-7326&rft_id=info:doi/10.4218/etrij.05.0104.0171&rft_dat=%3Cproquest_cross%3E27981473%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c3227-8c8db1b912764a1065f416cf2ff9204de9a8da0fef7be2606cd7cf5c166417453%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=27981473&rft_id=info:pmid/&rfr_iscdi=true