Constructing Pairing-Friendly Elliptic Curves under Embedding Degree 1 for Securing Critical Infrastructures
Identifieur interne : 000601 ( Pmc/Corpus ); précédent : 000600; suivant : 000602Constructing Pairing-Friendly Elliptic Curves under Embedding Degree 1 for Securing Critical Infrastructures
Auteurs : Maocai Wang ; Guangming Dai ; Kim-Kwang Raymond Choo ; Prem Prakash Jayaraman ; Rajiv RanjanSource :
- PLoS ONE [ 1932-6203 ] ; 2016.
Abstract
Information confidentiality is an essential requirement for cyber security in critical infrastructure. Identity-based cryptography, an increasingly popular branch of cryptography, is widely used to protect the information confidentiality in the critical infrastructure sector due to the ability to directly compute the user’s public key based on the user’s identity. However, computational requirements complicate the practical application of Identity-based cryptography. In order to improve the efficiency of identity-based cryptography, this paper presents an effective method to construct pairing-friendly elliptic curves with low hamming weight 4 under embedding degree 1. Based on the analysis of the Complex Multiplication(CM) method, the soundness of our method to calculate the characteristic of the finite field is proved. And then, three relative algorithms to construct pairing-friendly elliptic curve are put forward. 10 elliptic curves with low hamming weight 4 under 160 bits are presented to demonstrate the utility of our approach. Finally, the evaluation also indicates that it is more efficient to compute Tate pairing with our curves, than that of Bertoni et al.
Url:
DOI: 10.1371/journal.pone.0161857
PubMed: 27564373
PubMed Central: 5001717
Links to Exploration step
PMC:5001717Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Constructing Pairing-Friendly Elliptic Curves under Embedding Degree 1 for Securing Critical Infrastructures</title><author><name sortKey="Wang, Maocai" sort="Wang, Maocai" uniqKey="Wang M" first="Maocai" last="Wang">Maocai Wang</name><affiliation><nlm:aff id="aff001"><addr-line>School of Computer, China University of Geosciences, Wuhan, Hubei, China</addr-line></nlm:aff></affiliation><affiliation><nlm:aff id="aff002"><addr-line>Hubei Key Laboratory of Intelligent Geo-Information Processing, China University of Geosciences, Wuhan, Hubei, China</addr-line></nlm:aff></affiliation></author><author><name sortKey="Dai, Guangming" sort="Dai, Guangming" uniqKey="Dai G" first="Guangming" last="Dai">Guangming Dai</name><affiliation><nlm:aff id="aff001"><addr-line>School of Computer, China University of Geosciences, Wuhan, Hubei, China</addr-line></nlm:aff></affiliation><affiliation><nlm:aff id="aff002"><addr-line>Hubei Key Laboratory of Intelligent Geo-Information Processing, China University of Geosciences, Wuhan, Hubei, China</addr-line></nlm:aff></affiliation></author><author><name sortKey="Choo, Kim Kwang Raymond" sort="Choo, Kim Kwang Raymond" uniqKey="Choo K" first="Kim-Kwang Raymond" last="Choo">Kim-Kwang Raymond Choo</name><affiliation><nlm:aff id="aff001"><addr-line>School of Computer, China University of Geosciences, Wuhan, Hubei, China</addr-line></nlm:aff></affiliation><affiliation><nlm:aff id="aff002"><addr-line>Hubei Key Laboratory of Intelligent Geo-Information Processing, China University of Geosciences, Wuhan, Hubei, China</addr-line></nlm:aff></affiliation><affiliation><nlm:aff id="aff003"><addr-line>Department of Information Systems and Cyber Security, University of Texas at San Antonio, San Antonio, Texas, United States of America</addr-line></nlm:aff></affiliation></author><author><name sortKey="Jayaraman, Prem Prakash" sort="Jayaraman, Prem Prakash" uniqKey="Jayaraman P" first="Prem Prakash" last="Jayaraman">Prem Prakash Jayaraman</name><affiliation><nlm:aff id="aff004"><addr-line>RMIT University, Melbourne, Australia</addr-line></nlm:aff></affiliation></author><author><name sortKey="Ranjan, Rajiv" sort="Ranjan, Rajiv" uniqKey="Ranjan R" first="Rajiv" last="Ranjan">Rajiv Ranjan</name><affiliation><nlm:aff id="aff005"><addr-line>University of Newcastle, Newcastle, United Kingdom</addr-line></nlm:aff></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">PMC</idno><idno type="pmid">27564373</idno><idno type="pmc">5001717</idno><idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC5001717</idno><idno type="RBID">PMC:5001717</idno><idno type="doi">10.1371/journal.pone.0161857</idno><date when="2016">2016</date><idno type="wicri:Area/Pmc/Corpus">000601</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Constructing Pairing-Friendly Elliptic Curves under Embedding Degree 1 for Securing Critical Infrastructures</title><author><name sortKey="Wang, Maocai" sort="Wang, Maocai" uniqKey="Wang M" first="Maocai" last="Wang">Maocai Wang</name><affiliation><nlm:aff id="aff001"><addr-line>School of Computer, China University of Geosciences, Wuhan, Hubei, China</addr-line></nlm:aff></affiliation><affiliation><nlm:aff id="aff002"><addr-line>Hubei Key Laboratory of Intelligent Geo-Information Processing, China University of Geosciences, Wuhan, Hubei, China</addr-line></nlm:aff></affiliation></author><author><name sortKey="Dai, Guangming" sort="Dai, Guangming" uniqKey="Dai G" first="Guangming" last="Dai">Guangming Dai</name><affiliation><nlm:aff id="aff001"><addr-line>School of Computer, China University of Geosciences, Wuhan, Hubei, China</addr-line></nlm:aff></affiliation><affiliation><nlm:aff id="aff002"><addr-line>Hubei Key Laboratory of Intelligent Geo-Information Processing, China University of Geosciences, Wuhan, Hubei, China</addr-line></nlm:aff></affiliation></author><author><name sortKey="Choo, Kim Kwang Raymond" sort="Choo, Kim Kwang Raymond" uniqKey="Choo K" first="Kim-Kwang Raymond" last="Choo">Kim-Kwang Raymond Choo</name><affiliation><nlm:aff id="aff001"><addr-line>School of Computer, China University of Geosciences, Wuhan, Hubei, China</addr-line></nlm:aff></affiliation><affiliation><nlm:aff id="aff002"><addr-line>Hubei Key Laboratory of Intelligent Geo-Information Processing, China University of Geosciences, Wuhan, Hubei, China</addr-line></nlm:aff></affiliation><affiliation><nlm:aff id="aff003"><addr-line>Department of Information Systems and Cyber Security, University of Texas at San Antonio, San Antonio, Texas, United States of America</addr-line></nlm:aff></affiliation></author><author><name sortKey="Jayaraman, Prem Prakash" sort="Jayaraman, Prem Prakash" uniqKey="Jayaraman P" first="Prem Prakash" last="Jayaraman">Prem Prakash Jayaraman</name><affiliation><nlm:aff id="aff004"><addr-line>RMIT University, Melbourne, Australia</addr-line></nlm:aff></affiliation></author><author><name sortKey="Ranjan, Rajiv" sort="Ranjan, Rajiv" uniqKey="Ranjan R" first="Rajiv" last="Ranjan">Rajiv Ranjan</name><affiliation><nlm:aff id="aff005"><addr-line>University of Newcastle, Newcastle, United Kingdom</addr-line></nlm:aff></affiliation></author></analytic><series><title level="j">PLoS ONE</title><idno type="eISSN">1932-6203</idno><imprint><date when="2016">2016</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en"><p>Information confidentiality is an essential requirement for cyber security in critical infrastructure. Identity-based cryptography, an increasingly popular branch of cryptography, is widely used to protect the information confidentiality in the critical infrastructure sector due to the ability to directly compute the user’s public key based on the user’s identity. However, computational requirements complicate the practical application of Identity-based cryptography. In order to improve the efficiency of identity-based cryptography, this paper presents an effective method to construct pairing-friendly elliptic curves with low hamming weight 4 under embedding degree 1. Based on the analysis of the Complex Multiplication(CM) method, the soundness of our method to calculate the characteristic of the finite field is proved. And then, three relative algorithms to construct pairing-friendly elliptic curve are put forward. 10 elliptic curves with low hamming weight 4 under 160 bits are presented to demonstrate the utility of our approach. Finally, the evaluation also indicates that it is more efficient to compute Tate pairing with our curves, than that of Bertoni et al.</p></div></front><back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Dong, Mx" uniqKey="Dong M">MX Dong</name></author><author><name sortKey="Ota, K" uniqKey="Ota K">K Ota</name></author><author><name sortKey="Laurence, T" uniqKey="Laurence T">T Laurence</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Wang, L" uniqKey="Wang L">L. Wang</name></author><author><name sortKey="Tao, J" uniqKey="Tao J">J. Tao</name></author><author><name sortKey="Ranjan, R" uniqKey="Ranjan R">R. Ranjan</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Kepler, D" uniqKey="Kepler D">D Kepler</name></author><author><name sortKey="Heasley, P" uniqKey="Heasley P">P Heasley</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Zhao, J" uniqKey="Zhao J">J. Zhao</name></author><author><name sortKey="Wang, L" uniqKey="Wang L">L. Wang</name></author><author><name sortKey="Tao, J" uniqKey="Tao J">J. Tao</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Chen, D" uniqKey="Chen D">D. Chen</name></author><author><name sortKey="Liu, Z" uniqKey="Liu Z">Z. Liu</name></author><author><name sortKey="Wang, L" uniqKey="Wang L">L. Wang</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Wang, L" uniqKey="Wang L">L. Wang</name></author><author><name sortKey="Kurze, T" uniqKey="Kurze T">T. Kurze</name></author><author><name sortKey="Tao, J" uniqKey="Tao J">J. Tao</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Wang, L" uniqKey="Wang L">L. Wang</name></author><author><name sortKey="Fu, C" uniqKey="Fu C">C Fu</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Zhang, W" uniqKey="Zhang W">W. Zhang</name></author><author><name sortKey="Wang, L" uniqKey="Wang L">L. Wang</name></author><author><name sortKey="Liu, D" uniqKey="Liu D">D. Liu</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Wang, L" uniqKey="Wang L">L. Wang</name></author><author><name sortKey="Chen, D" uniqKey="Chen D">D. Chen</name></author><author><name sortKey="Hu, Y" uniqKey="Hu Y">Y. Hu</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Raymond, C" uniqKey="Raymond C">C Raymond</name></author><author><name sortKey="Kaur, H" uniqKey="Kaur H">H Kaur</name></author><author><name sortKey="Tao, X" uniqKey="Tao X">X Tao</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Raymond Choo, K" uniqKey="Raymond Choo K">K Raymond Choo</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Raymond Choo, K" uniqKey="Raymond Choo K">K Raymond Choo</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Dong, M" uniqKey="Dong M">M Dong</name></author><author><name sortKey="Ota, K" uniqKey="Ota K">K Ota</name></author><author><name sortKey="Laurence, T" uniqKey="Laurence T">T Laurence</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Dong, M" uniqKey="Dong M">M Dong</name></author><author><name sortKey="Li, H" uniqKey="Li H">H Li</name></author><author><name sortKey="Ota, K" uniqKey="Ota K">K Ota</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Mao, W" uniqKey="Mao W">W Mao</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Joye, M" uniqKey="Joye M">M. Joye</name></author><author><name sortKey="Neven, G" uniqKey="Neven G">G Neven</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Moody, D" uniqKey="Moody D">D. Moody</name></author><author><name sortKey="Peralta, R" uniqKey="Peralta R">R. Peralta</name></author><author><name sortKey="Perlner, R" uniqKey="Perlner R">R. Perlner</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Rahuman, A" uniqKey="Rahuman A">A Rahuman</name></author><author><name sortKey="Athisha, G" uniqKey="Athisha G">G Athisha</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Dai, G" uniqKey="Dai G">G Dai</name></author><author><name sortKey="Wang, M" uniqKey="Wang M">M Wang</name></author><author><name sortKey="Peng, L" uniqKey="Peng L">L Peng</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Miller, V" uniqKey="Miller V">V Miller</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Barreto, P" uniqKey="Barreto P">P Barreto</name></author><author><name sortKey="Galbraith, S" uniqKey="Galbraith S">S Galbraith</name></author><author><name sortKey="Eigeartaigh, C" uniqKey="Eigeartaigh C">C Eigeartaigh</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Barreto, P" uniqKey="Barreto P">P Barreto</name></author><author><name sortKey="Galbraith, S" uniqKey="Galbraith S">S Galbraith</name></author><author><name sortKey="Eigeartaigh, C" uniqKey="Eigeartaigh C">C Eigeartaigh</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct></biblStruct><biblStruct></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Miyaji, A" uniqKey="Miyaji A">A Miyaji</name></author><author><name sortKey="Nakabayashi, M" uniqKey="Nakabayashi M">M Nakabayashi</name></author><author><name sortKey="Takano, S" uniqKey="Takano S">S Takano</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Menezes, A" uniqKey="Menezes A">A Menezes</name></author><author><name sortKey="Okamoto, T" uniqKey="Okamoto T">T Okamoto</name></author><author><name sortKey="Vanstone, S" uniqKey="Vanstone S">S Vanstone</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Brezing, F" uniqKey="Brezing F">F Brezing</name></author><author><name sortKey="Weng, A" uniqKey="Weng A">A Weng</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Pollard, J" uniqKey="Pollard J">J Pollard</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Frey G And Ruck, H" uniqKey="Frey G And Ruck H">H Frey G and Ruck</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Perera, C" uniqKey="Perera C">C Perera</name></author><author><name sortKey="Ranjan, R" uniqKey="Ranjan R">R Ranjan</name></author><author><name sortKey="Wang, L" uniqKey="Wang L">L Wang</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Kolodziej, J" uniqKey="Kolodziej J">J Kolodziej</name></author><author><name sortKey="Khan, S" uniqKey="Khan S">S Khan</name></author><author><name sortKey="Wang, L" uniqKey="Wang L">L Wang</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Wei, J" uniqKey="Wei J">J Wei</name></author><author><name sortKey="Cai, W" uniqKey="Cai W">W Cai</name></author><author><name sortKey="Wang, L" uniqKey="Wang L">L Wang</name></author></analytic></biblStruct></listBibl></div1></back></TEI><pmc article-type="research-article"><pmc-dir>properties open_access</pmc-dir>
<front><journal-meta><journal-id journal-id-type="nlm-ta">PLoS One</journal-id><journal-id journal-id-type="iso-abbrev">PLoS ONE</journal-id><journal-id journal-id-type="publisher-id">plos</journal-id><journal-id journal-id-type="pmc">plosone</journal-id><journal-title-group><journal-title>PLoS ONE</journal-title></journal-title-group><issn pub-type="epub">1932-6203</issn><publisher><publisher-name>Public Library of Science</publisher-name><publisher-loc>San Francisco, CA USA</publisher-loc></publisher></journal-meta><article-meta><article-id pub-id-type="pmid">27564373</article-id><article-id pub-id-type="pmc">5001717</article-id><article-id pub-id-type="publisher-id">PONE-D-16-13711</article-id><article-id pub-id-type="doi">10.1371/journal.pone.0161857</article-id><article-categories><subj-group subj-group-type="heading"><subject>Research Article</subject></subj-group><subj-group subj-group-type="Discipline-v3"><subject>Physical Sciences</subject><subj-group><subject>Mathematics</subject><subj-group><subject>Algebra</subject><subj-group><subject>Algebraic Geometry</subject></subj-group></subj-group></subj-group></subj-group><subj-group subj-group-type="Discipline-v3"><subject>Physical Sciences</subject><subj-group><subject>Mathematics</subject><subj-group><subject>Applied Mathematics</subject><subj-group><subject>Algorithms</subject></subj-group></subj-group></subj-group></subj-group><subj-group subj-group-type="Discipline-v3"><subject>Research and Analysis Methods</subject><subj-group><subject>Simulation and Modeling</subject><subj-group><subject>Algorithms</subject></subj-group></subj-group></subj-group><subj-group subj-group-type="Discipline-v3"><subject>Computer and Information Sciences</subject><subj-group><subject>Cryptography</subject></subj-group></subj-group><subj-group subj-group-type="Discipline-v3"><subject>Physical Sciences</subject><subj-group><subject>Mathematics</subject><subj-group><subject>Cryptography</subject></subj-group></subj-group></subj-group><subj-group subj-group-type="Discipline-v3"><subject>Social Sciences</subject><subj-group><subject>Political Science</subject><subj-group><subject>National Security</subject></subj-group></subj-group></subj-group><subj-group subj-group-type="Discipline-v3"><subject>Engineering and Technology</subject><subj-group><subject>Equipment</subject></subj-group></subj-group><subj-group subj-group-type="Discipline-v3"><subject>Engineering and Technology</subject><subj-group><subject>Equipment</subject><subj-group><subject>Safety Equipment</subject></subj-group></subj-group></subj-group><subj-group subj-group-type="Discipline-v3"><subject>Medicine and Health Sciences</subject><subj-group><subject>Public and Occupational Health</subject><subj-group><subject>Safety</subject><subj-group><subject>Safety Equipment</subject></subj-group></subj-group></subj-group></subj-group><subj-group subj-group-type="Discipline-v3"><subject>Computer and Information Sciences</subject><subj-group><subject>Information Technology</subject><subj-group><subject>Databases</subject></subj-group></subj-group></subj-group><subj-group subj-group-type="Discipline-v3"><subject>Research and Analysis Methods</subject><subj-group><subject>Database and Informatics Methods</subject></subj-group></subj-group></article-categories><title-group><article-title>Constructing Pairing-Friendly Elliptic Curves under Embedding Degree 1 for Securing Critical Infrastructures</article-title><alt-title alt-title-type="running-head">Constructing Pairing-Friendly EC under Embedding Degree 1 for Securing Critical Infrastructures</alt-title></title-group><contrib-group><contrib contrib-type="author"><contrib-id contrib-id-type="orcid" authenticated="false">http://orcid.org/0000-0002-5495-6417</contrib-id><name><surname>Wang</surname><given-names>Maocai</given-names></name><xref ref-type="aff" rid="aff001"><sup>1</sup></xref><xref ref-type="aff" rid="aff002"><sup>2</sup></xref></contrib><contrib contrib-type="author"><name><surname>Dai</surname><given-names>Guangming</given-names></name><xref ref-type="aff" rid="aff001"><sup>1</sup></xref><xref ref-type="aff" rid="aff002"><sup>2</sup></xref><xref ref-type="corresp" rid="cor001">*</xref></contrib><contrib contrib-type="author" equal-contrib="yes"><name><surname>Choo</surname><given-names>Kim-Kwang Raymond</given-names></name><xref ref-type="aff" rid="aff001"><sup>1</sup></xref><xref ref-type="aff" rid="aff002"><sup>2</sup></xref><xref ref-type="aff" rid="aff003"><sup>3</sup></xref></contrib><contrib contrib-type="author" equal-contrib="yes"><name><surname>Jayaraman</surname><given-names>Prem Prakash</given-names></name><xref ref-type="aff" rid="aff004"><sup>4</sup></xref></contrib><contrib contrib-type="author" equal-contrib="yes"><name><surname>Ranjan</surname><given-names>Rajiv</given-names></name><xref ref-type="aff" rid="aff005"><sup>5</sup></xref></contrib></contrib-group><aff id="aff001"><label>1</label><addr-line>School of Computer, China University of Geosciences, Wuhan, Hubei, China</addr-line></aff><aff id="aff002"><label>2</label><addr-line>Hubei Key Laboratory of Intelligent Geo-Information Processing, China University of Geosciences, Wuhan, Hubei, China</addr-line></aff><aff id="aff003"><label>3</label><addr-line>Department of Information Systems and Cyber Security, University of Texas at San Antonio, San Antonio, Texas, United States of America</addr-line></aff><aff id="aff004"><label>4</label><addr-line>RMIT University, Melbourne, Australia</addr-line></aff><aff id="aff005"><label>5</label><addr-line>University of Newcastle, Newcastle, United Kingdom</addr-line></aff><contrib-group><contrib contrib-type="editor"><name><surname>Shi</surname><given-names>Yongtang</given-names></name><role>Editor</role><xref ref-type="aff" rid="edit1"></xref></contrib></contrib-group><aff id="edit1"><addr-line>Nankai University, CHINA</addr-line></aff><author-notes><fn fn-type="COI-statement" id="coi001"><p><bold>Competing Interests: </bold>The authors have declared that no competing interests exist.</p></fn><fn fn-type="con"><p><list list-type="simple"><list-item><p><bold>Conceptualization:</bold> MCW GMD.</p></list-item><list-item><p><bold>Data curation:</bold> MCW KRC.</p></list-item><list-item><p><bold>Formal analysis:</bold> MCW RR.</p></list-item><list-item><p><bold>Funding acquisition:</bold> MCW GMD.</p></list-item><list-item><p><bold>Investigation:</bold> MCW.</p></list-item><list-item><p><bold>Methodology:</bold> MCW GMD.</p></list-item><list-item><p><bold>Project administration:</bold> MCW.</p></list-item><list-item><p><bold>Resources:</bold> MCW.</p></list-item><list-item><p><bold>Software:</bold> MCW GMD.</p></list-item><list-item><p><bold>Supervision:</bold> GMD.</p></list-item><list-item><p><bold>Validation:</bold> MCW GMD PPJ.</p></list-item><list-item><p><bold>Visualization:</bold> PPJ RR.</p></list-item><list-item><p><bold>Writing – original draft:</bold> MCW KRC.</p></list-item><list-item><p><bold>Writing – review & editing:</bold> MCW RR.</p></list-item></list></p></fn><corresp id="cor001">* E-mail: <email>cugdgm@126.com</email></corresp></author-notes><pub-date pub-type="collection"><year>2016</year></pub-date><pub-date pub-type="epub"><day>26</day><month>8</month><year>2016</year></pub-date><volume>11</volume><issue>8</issue><elocation-id>e0161857</elocation-id><history><date date-type="received"><day>5</day><month>4</month><year>2016</year></date><date date-type="accepted"><day>13</day><month>8</month><year>2016</year></date></history><permissions><copyright-statement>© 2016 Wang et al</copyright-statement><copyright-year>2016</copyright-year><copyright-holder>Wang et al</copyright-holder><license xlink:href="http://creativecommons.org/licenses/by/4.0/"><license-p>This is an open access article distributed under the terms of the <ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/licenses/by/4.0/">Creative Commons Attribution License</ext-link>, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.</license-p></license></permissions><self-uri content-type="pdf" xlink:href="pone.0161857.pdf"></self-uri><abstract><p>Information confidentiality is an essential requirement for cyber security in critical infrastructure. Identity-based cryptography, an increasingly popular branch of cryptography, is widely used to protect the information confidentiality in the critical infrastructure sector due to the ability to directly compute the user’s public key based on the user’s identity. However, computational requirements complicate the practical application of Identity-based cryptography. In order to improve the efficiency of identity-based cryptography, this paper presents an effective method to construct pairing-friendly elliptic curves with low hamming weight 4 under embedding degree 1. Based on the analysis of the Complex Multiplication(CM) method, the soundness of our method to calculate the characteristic of the finite field is proved. And then, three relative algorithms to construct pairing-friendly elliptic curve are put forward. 10 elliptic curves with low hamming weight 4 under 160 bits are presented to demonstrate the utility of our approach. Finally, the evaluation also indicates that it is more efficient to compute Tate pairing with our curves, than that of Bertoni et al.</p></abstract><funding-group><award-group id="award001"><funding-source><institution-wrap><institution-id institution-id-type="funder-id">http://dx.doi.org/10.13039/501100001809</institution-id><institution>National Natural Science Foundation of China</institution></institution-wrap></funding-source><award-id>41571403</award-id><principal-award-recipient><contrib-id contrib-id-type="orcid" authenticated="false">http://orcid.org/0000-0002-5495-6417</contrib-id><name><surname>Wang</surname><given-names>Maocai</given-names></name></principal-award-recipient></award-group><award-group id="award002"><funding-source><institution-wrap><institution-id institution-id-type="funder-id">http://dx.doi.org/10.13039/501100002858</institution-id><institution>China Postdoctoral Science Foundation</institution></institution-wrap></funding-source><award-id>2012T50681</award-id><principal-award-recipient><contrib-id contrib-id-type="orcid" authenticated="false">http://orcid.org/0000-0002-5495-6417</contrib-id><name><surname>Wang</surname><given-names>Maocai</given-names></name></principal-award-recipient></award-group><award-group id="award003"><funding-source><institution-wrap><institution-id institution-id-type="funder-id">http://dx.doi.org/10.13039/501100002858</institution-id><institution>China Postdoctoral Science Foundation</institution></institution-wrap></funding-source><award-id>2011M501260</award-id><principal-award-recipient><contrib-id contrib-id-type="orcid" authenticated="false">http://orcid.org/0000-0002-5495-6417</contrib-id><name><surname>Wang</surname><given-names>Maocai</given-names></name></principal-award-recipient></award-group><award-group id="award004"><funding-source><institution-wrap><institution-id institution-id-type="funder-id">http://dx.doi.org/10.13039/501100001809</institution-id><institution>National Natural Science Foundation of China</institution></institution-wrap></funding-source><award-id>61472375</award-id><principal-award-recipient><name><surname>Dai</surname><given-names>Guangming</given-names></name></principal-award-recipient></award-group><funding-statement>This work was supported by National Natural Science Foundation of China (Grant No. 41571403 and 61472375, <ext-link ext-link-type="uri" xlink:href="http://www.nsfc.gov.cn/">http://www.nsfc.gov.cn/</ext-link>) and China Postdoctoral Science Foundation (Grant No. 2012T50681 and 2011M501260, <ext-link ext-link-type="uri" xlink:href="http://www.chinapostdoctor.org.cn">www.chinapostdoctor.org.cn</ext-link>). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.</funding-statement></funding-group><counts><fig-count count="1"></fig-count><table-count count="3"></table-count><page-count count="13"></page-count></counts><custom-meta-group><custom-meta id="data-availability"><meta-name>Data Availability</meta-name><meta-value>All relevant data are within the paper and its Supporting Information files.</meta-value></custom-meta></custom-meta-group></article-meta><notes><title>Data Availability</title><p>All relevant data are within the paper and its Supporting Information files.</p></notes></front><body><sec id="sec001"><title>1 Introduction</title><p>Many countrieshave thrived on the wealth fromthe information technologies(IT) have enabled, and IT forms the backbone of many aspects of the critical infrastructure sectors [<xref rid="pone.0161857.ref001" ref-type="bibr">1</xref>, <xref rid="pone.0161857.ref002" ref-type="bibr">2</xref>]. There are 16 critical infrastructure sectors in the U.S. [<xref rid="pone.0161857.ref003" ref-type="bibr">3</xref>]. As noted by both scholars [<xref rid="pone.0161857.ref004" ref-type="bibr">4</xref>–<xref rid="pone.0161857.ref010" ref-type="bibr">10</xref>] and government agencies, such as U.S. Homeland Security, the critical infrastructure represents systems and assets, and it is also defined in detailed [<xref rid="pone.0161857.ref003" ref-type="bibr">3</xref>].</p><p>The interconnective of the systems in the critical infrastructure sector, and the increasing sophistication, scale and the persistent nature of cyber attacks against such systems, can potentially result in equipment being forced to operate beyond its intended design and safety limits, resulting in cascading system malfunctions and shut downs such as the collapse of an entire electricity grid; or operating procedures or conditions being manipulated to slow the effort of restoring essential services [<xref rid="pone.0161857.ref011" ref-type="bibr">11</xref>, <xref rid="pone.0161857.ref012" ref-type="bibr">12</xref>]. It is, therefore, unsurprising that the cyber security of a nation’s critical infrastructure (including assets, networks, and systems) is regarded as a top priority of national security by countries around the world [<xref rid="pone.0161857.ref013" ref-type="bibr">13</xref>–<xref rid="pone.0161857.ref017" ref-type="bibr">17</xref>].</p><p>One of the key requirements in critical infrastructure cyber security is information confidentiality, and the cryptography is generally the core technology to provide information confidentiality [<xref rid="pone.0161857.ref018" ref-type="bibr">18</xref>].</p><p>Identity-based cryptography(IBC) is a relatively new branch of cryptography, which can directly compute a user’s public key using publicly available information from the user’s identity [<xref rid="pone.0161857.ref019" ref-type="bibr">19</xref>]. Therefore, one does not need to distribute his digital certificate signed by a certificate authority (CA), or query the certificate database to get the other party’s public key when conducting electronic transactions. In other words, IBC resolves the challenges and complexity associated with certificate management and traditional public-key cryptosystem. A limitation of IBC is, however, the computation cost involving in constructing the pairings [<xref rid="pone.0161857.ref020" ref-type="bibr">20</xref>]. IBC has the subject of various research, but it remains a topic of ongoing research interest, and one of the research challenges is the generation of efficient parameters such as pairing-friendly elliptic curves.</p><p>The existing efficient algorithms to compute Weil and Tate pairings [<xref rid="pone.0161857.ref021" ref-type="bibr">21</xref>, <xref rid="pone.0161857.ref022" ref-type="bibr">22</xref>] are generally based on Miller’s algorithm [<xref rid="pone.0161857.ref023" ref-type="bibr">23</xref>]on (hyper) elliptic curves. One line of research which focuses on reducing the loop in Miller’s algorithm was initiated by Duursma-Lee [<xref rid="pone.0161857.ref024" ref-type="bibr">24</xref>] and, subsequently extended by Barreto et al. [<xref rid="pone.0161857.ref025" ref-type="bibr">25</xref>] to supersingular abelian varieties.</p><p>In practice, the cryptographic pairings used to construct these systems are based on the Weil and Tate pairings on elliptic curves over finite fields [<xref rid="pone.0161857.ref026" ref-type="bibr">26</xref>]. Both pairings are a bilinear map from an elliptic curve group on the finite field <italic>F</italic><sub><italic>p</italic></sub> to the multiplicative group of some extension field <inline-formula id="pone.0161857.e001"><alternatives><graphic xlink:href="pone.0161857.e001.jpg" id="pone.0161857.e001g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M1"><mml:mrow><mml:msub><mml:mi>F</mml:mi><mml:mrow><mml:msup><mml:mi>p</mml:mi><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:msub></mml:mrow></mml:math></alternatives></inline-formula>. The parameter <italic>k</italic> is called the embedding degree of the elliptic curve. The pairing is considered to be secure if both discrete logarithms in the groups <italic>E</italic>(<italic>F</italic><sub><italic>p</italic></sub>) and <inline-formula id="pone.0161857.e002"><alternatives><graphic xlink:href="pone.0161857.e002.jpg" id="pone.0161857.e002g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M2"><mml:mrow><mml:msub><mml:mi>F</mml:mi><mml:mrow><mml:msup><mml:mi>p</mml:mi><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:msub></mml:mrow></mml:math></alternatives></inline-formula> are computationally infeasible.</p><p>To optimize the application performance, the parameters <italic>p</italic> and <italic>k</italic> should be determined according to this standard that both discrete logarithm problems approximately have the equal difficulty when using the best known algorithms. Moreover, a large prime factor <italic>r</italic> should be included in the order of the group #<italic>E</italic>(<italic>F</italic><sub><italic>p</italic></sub>). For example, if the large prime factor <italic>r</italic> ≥ 2<sup>160</sup>, the pairing is generally considered to be safe against existing attacks. Therefore, it is essential to be able to construct elliptic curves efficiently for arbitrary <italic>p</italic> and <italic>k</italic> values to differ the security level or to meet the requirement of discrete log in future improvements. This is the gap we attempt to address in this paper.</p><p>This paper is organized as follows. In the next two sections, we introduce the reader to related literature and Tate pairing, respectively. In Section 4, we describe our approach to constructing pairing-friendly elliptic curves under embedding degree 1 and preliminary evaluation results to demonstrate utility and practicality. Our discussion and concluding remarks are provided in the last two sections.</p></sec><sec id="sec002"><title>2 Related Work</title><p>Constructing elliptic curves with various embedding degrees has been the subject of ongoing research. For example, Cocks and Pinch [<xref rid="pone.0161857.ref027" ref-type="bibr">27</xref>] constructed the curves with arbitrary embedding degree <italic>k</italic>, but the efficiency is very low because the size <italic>q</italic> of the field <italic>F</italic><sub><italic>p</italic></sub> is limited by the subgroup of prime order r with <italic>q</italic> ≈ <italic>r</italic><sup>2</sup>. Fotiadis and Konstantinou [<xref rid="pone.0161857.ref028" ref-type="bibr">28</xref>] presented two general methods to produce sparse families and applied them to four embedding degrees <italic>k</italic>, where <italic>k</italic>. Barreto and Naehrig [<xref rid="pone.0161857.ref029" ref-type="bibr">29</xref>] constructed the curves of prime order with <italic>k</italic> = 12. Freeman [<xref rid="pone.0161857.ref030" ref-type="bibr">30</xref>] proposed a construction for the curves with embedding degree <italic>k</italic> = 10. A complete characterization of common elliptic curves of prime order with <italic>k</italic> = 3, 4, or 6, is provided by Miyaji, Nakabayashi, and Takano [<xref rid="pone.0161857.ref031" ref-type="bibr">31</xref>]. Menezes, Okamoto, and Vanstone [<xref rid="pone.0161857.ref032" ref-type="bibr">32</xref>] illustrated that embedding degree <italic>k</italic> should be not more 6 in a supersingular elliptic curve, especially <italic>k</italic> ≤ 3 and <italic>k</italic> ≠ 2 or <italic>k</italic> ≠ 3. Some researches [<xref rid="pone.0161857.ref033" ref-type="bibr">33</xref>] reduced the ratio <inline-formula id="pone.0161857.e003"><alternatives><graphic xlink:href="pone.0161857.e003.jpg" id="pone.0161857.e003g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M3"><mml:mrow><mml:mi>p</mml:mi><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:mtext>log </mml:mtext><mml:mi>p</mml:mi></mml:mrow><mml:mrow><mml:mtext>log </mml:mtext><mml:mi>r</mml:mi></mml:mrow></mml:mfrac></mml:mrow></mml:math></alternatives></inline-formula> for arbitrary <italic>k</italic> between the characteristicp of the finite field and the prime order <italic>r</italic> of the subgroup. However, no concrete examples have been proposed with <italic>ρ</italic> small enough to construct curves with prime order.</p><p>In fact, if <italic>k</italic> = 1, the pairing will become a bilinear map from the elliptic curve group on the finite field <italic>F</italic><sub><italic>p</italic></sub> to the elliptic curve group on the same finite field <italic>F</italic><sub><italic>p</italic></sub>. In other words, we would not involve the extension field <inline-formula id="pone.0161857.e004"><alternatives><graphic xlink:href="pone.0161857.e004.jpg" id="pone.0161857.e004g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M4"><mml:msubsup><mml:mi>F</mml:mi><mml:mi>p</mml:mi><mml:mi>k</mml:mi></mml:msubsup></mml:math></alternatives></inline-formula> when computing the pairing, which is the constraintin pairing-based cryptography applications.</p><p>Izuta, Nogami and Morikawa [<xref rid="pone.0161857.ref034" ref-type="bibr">34</xref>] proposed a method for generating a certain composite order ordinary pairing-friendly elliptic curve of embedding degree 1. In their method, the order has two large prime factors such as the modulus of RSA cryptography. Lee and Park [<xref rid="pone.0161857.ref035" ref-type="bibr">35</xref>] proposed a new algorithm to construct Brezing-Weng-like elliptic curves having the Complex Multiplication(CM) equation of degree 1, as well as presenting new families of curves with larger discriminants.</p><p>It is clear from the literature that pairing-friendly elliptic curves under embedding degree 1 are constructed on the base field, rather than the extension field, which can significantly improve the computation efficiency of Tate pairing. This is the gap that this paper attempts to address. More specifically, this paper proposes an effective method to construct pairing-friendly elliptic curves with low hamming weight 4 under embedding degree 1.</p></sec><sec id="sec003"><title>3 Tate Pairing</title><p>In practice, as the theoretical model is unknown, we use the Monte-Carlo method [<xref rid="pone.0161857.ref036" ref-type="bibr">36</xref>] to generate the required data based on a fixed theoretical model.</p><p>Weil pairing was first introduced into cryptography by Menezes, which was used to study the elliptic curve discrete logarithm problem on certain elliptic curves [<xref rid="pone.0161857.ref032" ref-type="bibr">32</xref>]. Extending on the work of Menezes, Frey introduced Tate pairing to cryptography [<xref rid="pone.0161857.ref037" ref-type="bibr">37</xref>], which is now widely used to design pairing-based cryptosystems because Tate pairing is twice as efficient as Weil pairing.</p><p>Let E be an elliptic curve over a finite field <italic>F</italic><sub><italic>p</italic></sub>, and <italic>r</italic> be a positive integer which is co prime to <italic>p</italic>. In most applications, <italic>r</italic> is a prime and <italic>r</italic>|#<italic>E</italic>(<italic>F</italic><sub><italic>p</italic></sub>). Let <italic>k</italic> be a positive integer such that the field <inline-formula id="pone.0161857.e005"><alternatives><graphic xlink:href="pone.0161857.e005.jpg" id="pone.0161857.e005g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M5"><mml:mrow><mml:msub><mml:mi>F</mml:mi><mml:mrow><mml:msup><mml:mi>p</mml:mi><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:msub></mml:mrow></mml:math></alternatives></inline-formula>. contains the r-th roots of unity, and <italic>k</italic> is called the embedding degree. Then Tate pairing is a mapping [<xref rid="pone.0161857.ref038" ref-type="bibr">38</xref>]:
<disp-formula id="pone.0161857.e006"><alternatives><graphic xlink:href="pone.0161857.e006.jpg" id="pone.0161857.e006g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M6"><mml:mrow><mml:mi>t</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mi>P</mml:mi><mml:mo>,</mml:mo><mml:mi>Q</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>:</mml:mo><mml:mi>E</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:msub><mml:mi>F</mml:mi><mml:msup><mml:mi>p</mml:mi><mml:mi>k</mml:mi></mml:msup></mml:msub><mml:mo>)</mml:mo></mml:mrow><mml:mrow><mml:mo> [</mml:mo><mml:mi>r</mml:mi><mml:mo>]</mml:mo></mml:mrow><mml:mo>×</mml:mo><mml:mi>E</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:msub><mml:mi>F</mml:mi><mml:msup><mml:mi>p</mml:mi><mml:mi>k</mml:mi></mml:msup></mml:msub><mml:mo>)</mml:mo></mml:mrow><mml:mo>/</mml:mo><mml:mi>r</mml:mi><mml:mi>E</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:msub><mml:mi>F</mml:mi><mml:msup><mml:mi>p</mml:mi><mml:mi>k</mml:mi></mml:msup></mml:msub><mml:mo>)</mml:mo></mml:mrow><mml:mo>→</mml:mo><mml:msubsup><mml:mi>F</mml:mi><mml:mrow><mml:msup><mml:mi>p</mml:mi><mml:mi>k</mml:mi></mml:msup></mml:mrow><mml:mo>*</mml:mo></mml:msubsup><mml:mo>/</mml:mo><mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:msubsup><mml:mi>F</mml:mi><mml:mrow><mml:msup><mml:mi>p</mml:mi><mml:mi>k</mml:mi></mml:msup></mml:mrow><mml:mo>*</mml:mo></mml:msubsup><mml:mo>)</mml:mo></mml:mrow><mml:mi>r</mml:mi></mml:msup></mml:mrow></mml:math></alternatives></disp-formula></p><p>According to the definition of Tate pairing, if the embedding degree <italic>k</italic> ≠ 1, then the computation of Tate pairing is related to the extension field <inline-formula id="pone.0161857.e007"><alternatives><graphic xlink:href="pone.0161857.e007.jpg" id="pone.0161857.e007g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M7"><mml:mrow><mml:msub><mml:mi>F</mml:mi><mml:mrow><mml:msup><mml:mi>p</mml:mi><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:msub></mml:mrow></mml:math></alternatives></inline-formula>, and the computation process will be time-consuming. However, if the embedding degree <italic>k</italic> = 1, the computation of Tate pairing only runs on the base field <inline-formula id="pone.0161857.e008"><alternatives><graphic xlink:href="pone.0161857.e008.jpg" id="pone.0161857.e008g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M8"><mml:mrow><mml:msub><mml:mi>F</mml:mi><mml:mrow><mml:msup><mml:mi>p</mml:mi><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:msub></mml:mrow></mml:math></alternatives></inline-formula> rather than the extension field <inline-formula id="pone.0161857.e009"><alternatives><graphic xlink:href="pone.0161857.e009.jpg" id="pone.0161857.e009g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M9"><mml:mrow><mml:msub><mml:mi>F</mml:mi><mml:mrow><mml:msup><mml:mi>p</mml:mi><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:msub></mml:mrow></mml:math></alternatives></inline-formula>. This will greatly improve the computation efficiency of Tate pairing.</p><p>In Tate pairing, both the point <italic>P</italic> and the point <italic>Q</italic> are from two different subgroups with the same order r as subgroup <inline-formula id="pone.0161857.e010"><alternatives><graphic xlink:href="pone.0161857.e010.jpg" id="pone.0161857.e010g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M10"><mml:mrow><mml:mi>E</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>F</mml:mi><mml:mrow><mml:msup><mml:mi>p</mml:mi><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:msub><mml:mo stretchy="false">[</mml:mo><mml:mi>r</mml:mi><mml:mo stretchy="false">]</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> and <inline-formula id="pone.0161857.e011"><alternatives><graphic xlink:href="pone.0161857.e011.jpg" id="pone.0161857.e011g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M11"><mml:mrow><mml:mo form="prefix" stretchy="false">(</mml:mo><mml:msubsup><mml:mi>F</mml:mi><mml:msup><mml:mi>p</mml:mi><mml:mi>k</mml:mi></mml:msup><mml:mo>*</mml:mo></mml:msubsup><mml:msup><mml:mo form="postfix" stretchy="false">)</mml:mo><mml:mi>r</mml:mi></mml:msup></mml:mrow></mml:math></alternatives></inline-formula> respectively. That is to say, if <italic>k</italic> = 1, then the point <italic>P</italic> and the point <italic>Q</italic> come from two different subgroup <italic>G</italic><sub>1</sub> and <italic>G</italic><sub>2</sub> of <italic>E</italic>(<italic>F</italic><sub><italic>p</italic></sub>) with the same order <italic>r</italic>, and <italic>G</italic><sub>1</sub> ∩ <italic>G</italic><sub>2</sub> = ∅. However, “How to construct the elliptic curve which includes two different groups with the same order <italic>r</italic> when <italic>r</italic> is a large prime with <italic>r</italic> ≥ 2<sup>160</sup>?” and “How to find the two different groups?” are two key challenges in designing pairing-friendly elliptic curves under embedding degree 1.</p><p>In this paper, we propose an effective algorithm to construct pairing-friendly elliptic curves under embedding degree 1. In our algorithm, it can be ensured that both the point <italic>P</italic> and the point <italic>Q</italic> are from two different subgroups with the same order <italic>r</italic>, which enables the computation of Tate pairing to run only on the base field.</p></sec><sec id="sec004"><title>4 Constructing Pairing-friendly Elliptic Curves</title><p>In this section, a new method to generate pairing-friendly elliptic curves is proposed, which comprises three algorithms as follows.</p><list list-type="order"><list-item><p>The first algorithm is used to generate a large prime of low hamming with weight 4.</p></list-item><list-item><p>The second algorithm is used to generate the finite field <italic>p</italic>, the order <italic>u</italic> of a non-supersingular elliptic curve over <italic>F</italic><sub><italic>p</italic></sub>, the order <italic>r</italic> of a point on the elliptic curve.</p></list-item><list-item><p>The last algorithm is used to construct pairing-friendly elliptic curves under embedding degree 1.</p></list-item></list><sec id="sec005"><title>4.1 The Construction Method</title><p>In the common method [<xref rid="pone.0161857.ref031" ref-type="bibr">31</xref>, <xref rid="pone.0161857.ref035" ref-type="bibr">35</xref>]to construct elliptic curves, the equation <italic>u</italic> = <italic>p</italic> + 1 ± <italic>W</italic> is used to generate the parameters of the elliptic curves. This equation provides a means to determine the order #<italic>E</italic> of an elliptic curve <italic>E</italic> according to the characteristic p of the finite field <italic>F</italic><sub><italic>p</italic></sub>. However, the order #<italic>E</italic> generated using the equation is generally unable to meet the security requirement. Therefore, it is a challenge to generate a suitable elliptic curve using the common method. Moreover, even if a suitable elliptic curve can be generated, it will take a long time. For example, in the method of Izuta, Nogami and Morikawa [<xref rid="pone.0161857.ref034" ref-type="bibr">34</xref>], it will take about 20 hours to generate an elliptic curve.</p><p>In our method, we present a new equation <italic>p</italic> = <italic>u</italic> ± <italic>W</italic> + 1 to generate the parameters of elliptic curves. On first glance, the new equation may appear similar to the common equation. However, in the new equation, the order #<italic>E</italic> is known, and we need to obtain <italic>p</italic> from the order #<italic>E</italic> (rather than the order #<italic>E</italic> from p). Thus, we only need to determine the characteristic <italic>p</italic> of the finite field <italic>F</italic><sub><italic>p</italic></sub> from the order #<italic>E</italic> of an elliptic curve <italic>E</italic>, and our algorithm 2 describes the process required to generate <italic>p</italic> from the order #<italic>E</italic>. In other words, we can generate an elliptic curve under arbitrary order, while the order #<italic>E</italic> of an elliptic curves <italic>E</italic> can be trivially obtained using <italic>u</italic> = <italic>r</italic> * <italic>r</italic> (from the security requirement), where <italic>r</italic> is a large prime, and <italic>r</italic> has a low hamming with weight 4 (based on our algorithm 1). As the order of the subgroup is a large prime of low hamming with weight 4, the efficiency of generating elliptic curves is significantly improved. More specifically, our method requires about 200 ms to generating a suitable elliptic curve.</p><p><bold>Theorem 1</bold> If <italic>E is a non-super singular elliptic curve over F</italic><sub><italic>p</italic></sub><italic>with order u, D is the</italic> CM discriminant for <italic>p</italic>, according to the discriminant condition 4<italic>p</italic> = <italic>W</italic><sup>2</sup> + <italic>DV</italic><sup>2</sup> and <italic>u</italic> = <italic>p</italic> + 1 ± 1, then
<disp-formula id="pone.0161857.e012"><alternatives><graphic xlink:href="pone.0161857.e012.jpg" id="pone.0161857.e012g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M12"><mml:mrow><mml:mi>p</mml:mi><mml:mo>=</mml:mo><mml:mi>u</mml:mi><mml:mo>±</mml:mo><mml:mi>X</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></alternatives></disp-formula>where <italic>W</italic> = <italic>X</italic> ± 2, <italic>V</italic> = <italic>Y</italic>.</p><p>Proof. It is well known that the CM discriminant <italic>D</italic> for <italic>p</italic> meets the Eqs <xref ref-type="disp-formula" rid="pone.0161857.e013">(1)</xref> and <xref ref-type="disp-formula" rid="pone.0161857.e014">(2)</xref> for every non-super singular elliptic curve over <italic>F</italic><sub><italic>p</italic></sub> with order <italic>u</italic>.
<disp-formula id="pone.0161857.e013"><alternatives><graphic xlink:href="pone.0161857.e013.jpg" id="pone.0161857.e013g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M13"><mml:mrow><mml:mn>4</mml:mn><mml:mi>p</mml:mi><mml:mo>=</mml:mo><mml:msup><mml:mi>W</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:mo>+</mml:mo><mml:mi>D</mml:mi><mml:msup><mml:mi>V</mml:mi><mml:mn>2</mml:mn></mml:msup></mml:mrow></mml:math></alternatives><label>(1)</label></disp-formula><disp-formula id="pone.0161857.e014"><alternatives><graphic xlink:href="pone.0161857.e014.jpg" id="pone.0161857.e014g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M14"><mml:mrow><mml:mi>u</mml:mi><mml:mo>=</mml:mo><mml:mi>p</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>±</mml:mo><mml:mi>W</mml:mi></mml:mrow></mml:math></alternatives><label>(2)</label></disp-formula></p><p>The <xref ref-type="disp-formula" rid="pone.0161857.e015">Eq (3)</xref> can be gotten from the <xref ref-type="disp-formula" rid="pone.0161857.e014">Eq (2)</xref>.
<disp-formula id="pone.0161857.e015"><alternatives><graphic xlink:href="pone.0161857.e015.jpg" id="pone.0161857.e015g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M15"><mml:mrow><mml:mn>4</mml:mn><mml:mi>u</mml:mi><mml:mo>=</mml:mo><mml:mn>4</mml:mn><mml:mi>p</mml:mi><mml:mo>+</mml:mo><mml:mn>4</mml:mn><mml:mo>±</mml:mo><mml:mn>4</mml:mn><mml:mi>W</mml:mi></mml:mrow></mml:math></alternatives><label>(3)</label></disp-formula></p><p>The <xref ref-type="disp-formula" rid="pone.0161857.e016">Eq (4)</xref> can be gotten by replacing 4<italic>p</italic> with the <xref ref-type="disp-formula" rid="pone.0161857.e013">Eq (1)</xref> in the <xref ref-type="disp-formula" rid="pone.0161857.e015">Eq (3)</xref>.
<disp-formula id="pone.0161857.e016"><alternatives><graphic xlink:href="pone.0161857.e016.jpg" id="pone.0161857.e016g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M16"><mml:mrow><mml:mn>4</mml:mn><mml:mi>u</mml:mi><mml:mo>=</mml:mo><mml:msup><mml:mi>W</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:mo>+</mml:mo><mml:mi>D</mml:mi><mml:msup><mml:mi>V</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:mo>+</mml:mo><mml:mn>4</mml:mn><mml:mo>±</mml:mo><mml:mn>4</mml:mn><mml:mi>W</mml:mi></mml:mrow></mml:math></alternatives><label>(4)</label></disp-formula></p><p>The <xref ref-type="disp-formula" rid="pone.0161857.e016">Eq (4)</xref> can be written as the <xref ref-type="disp-formula" rid="pone.0161857.e017">Eq (5)</xref>.
<disp-formula id="pone.0161857.e017"><alternatives><graphic xlink:href="pone.0161857.e017.jpg" id="pone.0161857.e017g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M17"><mml:mrow><mml:mn>4</mml:mn><mml:mi>u</mml:mi><mml:mo>=</mml:mo><mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:mi>W</mml:mi><mml:mo>±</mml:mo><mml:mn>2</mml:mn><mml:mo>)</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:msup><mml:mo>+</mml:mo><mml:mi>D</mml:mi><mml:msup><mml:mi>V</mml:mi><mml:mn>2</mml:mn></mml:msup></mml:mrow></mml:math></alternatives><label>(5)</label></disp-formula></p><p>The <xref ref-type="disp-formula" rid="pone.0161857.e017">Eq (5)</xref> can be written as the <xref ref-type="disp-formula" rid="pone.0161857.e018">Eq (6)</xref>.
<disp-formula id="pone.0161857.e018"><alternatives><graphic xlink:href="pone.0161857.e018.jpg" id="pone.0161857.e018g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M18"><mml:mrow><mml:mn>4</mml:mn><mml:mi>u</mml:mi><mml:mo>=</mml:mo><mml:msup><mml:mi>X</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:mo>+</mml:mo><mml:mi>D</mml:mi><mml:msup><mml:mi>Y</mml:mi><mml:mn>2</mml:mn></mml:msup></mml:mrow></mml:math></alternatives><label>(6)</label></disp-formula>where <italic>X</italic> = <italic>W</italic> ± 2 and <italic>Y</italic> = <italic>V</italic>.</p><p>Therefore, the <xref ref-type="disp-formula" rid="pone.0161857.e013">Eq (1)</xref> can be converted to the <xref ref-type="disp-formula" rid="pone.0161857.e019">Eq (7)</xref> with <italic>X</italic> = <italic>W</italic> ± 2.
<disp-formula id="pone.0161857.e019"><alternatives><graphic xlink:href="pone.0161857.e019.jpg" id="pone.0161857.e019g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M19"><mml:mrow><mml:mn>4</mml:mn><mml:mi>p</mml:mi><mml:mo>=</mml:mo><mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:mi>X</mml:mi><mml:mo>±</mml:mo><mml:mn>2</mml:mn><mml:mo>)</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:msup><mml:mo>+</mml:mo><mml:mi>D</mml:mi><mml:msup><mml:mi>Y</mml:mi><mml:mn>2</mml:mn></mml:msup></mml:mrow></mml:math></alternatives><label>(7)</label></disp-formula></p><p>The <xref ref-type="disp-formula" rid="pone.0161857.e020">Eq (8)</xref> can be gotten from the Eqs <xref ref-type="disp-formula" rid="pone.0161857.e018">(6)</xref> and <xref ref-type="disp-formula" rid="pone.0161857.e019">(7)</xref><disp-formula id="pone.0161857.e020"><alternatives><graphic xlink:href="pone.0161857.e020.jpg" id="pone.0161857.e020g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M20"><mml:mrow><mml:mn>4</mml:mn><mml:mi>p</mml:mi><mml:mo>=</mml:mo><mml:mn>4</mml:mn><mml:mi>u</mml:mi><mml:mo>±</mml:mo><mml:mn>4</mml:mn><mml:mi>X</mml:mi><mml:mo>=</mml:mo><mml:mn>4</mml:mn></mml:mrow></mml:math></alternatives><label>(8)</label></disp-formula></p><p>The <xref ref-type="disp-formula" rid="pone.0161857.e020">Eq (8)</xref> can be be written as the <xref ref-type="disp-formula" rid="pone.0161857.e021">Eq (9)</xref><disp-formula id="pone.0161857.e021"><alternatives><graphic xlink:href="pone.0161857.e021.jpg" id="pone.0161857.e021g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M21"><mml:mrow><mml:mi>p</mml:mi><mml:mo>=</mml:mo><mml:mi>u</mml:mi><mml:mo>±</mml:mo><mml:mi>X</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></alternatives><label>(9)</label></disp-formula></p><p>This ends the proof.</p><p>Theorem 1 provides a method to calculate the characteristic <italic>p</italic> of the finite field <italic>F</italic><sub><italic>p</italic></sub> according to the order <italic>u</italic> of an elliptic curve. That is to say, for any elliptic curve with the order <italic>u</italic> expected, we can easily calculate the characteristic <italic>p</italic> of the finite field <italic>F</italic><sub><italic>p</italic></sub> according to the <xref ref-type="disp-formula" rid="pone.0161857.e021">Eq (9)</xref>. This is a new way, which can generate an elliptic curve under any order we expected.</p><p>In Miller algorithm of computing Tate pairing, if some bit of the binary representation for the order r of subgroup is ‘1’, operators would be needed to compute multiplication and inverse operations [<xref rid="pone.0161857.ref039" ref-type="bibr">39</xref>]. Otherwise, (i.e. if the binary bit is ‘0’), no additional operator is needed. It is clear that the process to compute Tate pairing will be more efficient if the binary representation of the order r has fewer ‘1’ bits and more ‘0’ bits. This forms the basis of the three relative algorithms.</p></sec><sec id="sec006"><title>4.2 Algorithm 1</title><p>Algorithm 1 outlines the method to generate a large prime of low hamming with weight 4. In other words, there are only two ‘1’ bits in addition to the highest bit and the lowest bit in the binary representation for the large prime. The large prime will be used as the order <italic>r</italic> of subgroup in algorithms 2 and 3.</p><p>In algorithm 1, the input parameter is the length <italic>m</italic>(<italic>m</italic> ≥ 160) of the binary representation for the large prime, the output result is the large prime r of low hamming with weight 4.</p><p specific-use="line">Algorithm 1. Generating a large prime of low hamming with weight 4.</p><p specific-use="line">Input: The length <italic>m</italic>(<italic>m</italic> ≥ 160) of the binary representation for the large prime; a positive integer <italic>t</italic> for the number of trials.</p><p specific-use="line">Output: The large prime <italic>r</italic> of low hamming with weight 4.</p><p specific-use="line"><list list-type="simple"><list-item><label>step 1</label><p>Choose random <italic>s</italic>, <italic>t</italic> in the interval (0, <italic>m</italic> − 1) to ensure 0 < <italic>s</italic> < <italic>t</italic> < <italic>m</italic> − 1;</p></list-item><list-item><label>step 2</label><p><italic>r</italic> ← 2<sup>0</sup> + 2<sup><italic>s</italic></sup> + 2<sup><italic>t</italic></sup> + 2<sup><italic>m</italic> − 1</sup>;</p></list-item><list-item><label>step 3</label><p>Compute <italic>v</italic> and an odd value <italic>w</italic>, such that <italic>r</italic> − 1 = 2<sup><italic>v</italic></sup><italic>w</italic></p></list-item><list-item><label>step 4</label><p>For <italic>j</italic> from 1 to <italic>t</italic> do
<list list-type="simple"><list-item><label>step 4.1</label><p>Choose random <italic>a</italic> in the interval 0 < <italic>a</italic> < <italic>r</italic>;</p></list-item><list-item><label>step 4.2</label><p>Set <italic>b</italic> ← <italic>a</italic><sup><italic>w</italic></sup> mod <italic>r</italic></p></list-item><list-item><label>step 4.3</label><p>If <italic>b</italic> = 1 or <italic>b</italic> = <italic>r</italic> − 1, goto step 4.6;</p></list-item><list-item><label>step 4.4</label><p>For <italic>i</italic> from 1 to <italic>v</italic> − 1 do
<list list-type="simple"><list-item><label>step 4.4.1</label><p>Set <italic>b</italic> ← <italic>b</italic><sup>2</sup> mod <italic>r</italic></p></list-item><list-item><label>step 4.4.2</label><p>If <italic>b</italic> = <italic>r</italic> − 1 goto step 4.6;</p></list-item><list-item><label>step 4.4.3</label><p>if <italic>b</italic> = 1, goto step 1;</p></list-item><list-item><label>step 4.4.4</label><p>Next <italic>i</italic>.</p></list-item></list></p></list-item><list-item><label>step 4.5</label><p>goto step 1;</p></list-item><list-item><label>step 4.6</label><p>Next <italic>j</italic>;</p></list-item></list></p></list-item><list-item><label>step 5</label><p>Output <italic>r</italic>.</p></list-item></list></p></sec><sec id="sec007"><title>4.3 Algorithm 2</title><p>Algorithm 2 describes the method to generate the finite field <italic>p</italic>, the order u of a non-supersingular elliptic curve over <italic>F</italic><sub><italic>p</italic></sub>, and the order <italic>r</italic> of a point on the elliptic curve according to the length <italic>m</italic>(<italic>m</italic> ≥ 160) of the finite field <italic>p</italic>.</p><p specific-use="line">Algorithm 2. Generating the finite field <italic>p</italic>, the order <italic>u</italic> of a non-supersingular elliptic curve over <italic>F</italic><sub><italic>p</italic></sub>, and the order <italic>r</italic> of a point on the elliptic curve.</p><p specific-use="line">Input: The length <italic>m</italic>(<italic>m</italic> ≥ 160) of the finite field <italic>p</italic>.</p><p specific-use="line">Output: The finite field <italic>p</italic>, the order <italic>u</italic> of a non-super singular elliptic curve over <italic>F</italic><sub><italic>p</italic></sub>, the order <italic>r</italic> of a point on the elliptic curve.</p><p specific-use="line"><list list-type="simple"><list-item><label>step 1</label><p>Generate a large prime <italic>r</italic> of low hamming with weight 4 using algorithm 1;</p></list-item><list-item><label>step 2</label><p>Compute the order u of a non-supersingular elliptic curve <italic>u</italic> = <italic>r</italic><sup>2</sup>;</p></list-item><list-item><label>step 3</label><p>Assign <italic>D</italic> = 3, set <italic>X</italic> = <italic>r</italic>, <italic>Y</italic> = <italic>r</italic>, such that the values of both <italic>X</italic> and <italic>Y</italic> satisfy the condition 4<italic>u</italic> = <italic>X</italic><sup>2</sup> + <italic>DY</italic><sup>2</sup>;</p></list-item><list-item><label>step 4</label><p>Compute <italic>p</italic> = <italic>r</italic><sup>2</sup> + <italic>r</italic> + 1 according to <italic>p</italic> = <italic>u</italic> ± <italic>X</italic> + 1 when <italic>u</italic> = <italic>r</italic><sup>2</sup>, <italic>X</italic> = <italic>r</italic>;</p></list-item><list-item><label>step 5</label><p>If <italic>p</italic> is not a prime, goto Step 1;</p></list-item><list-item><label>step 6</label><p>Output the finite field <italic>p</italic>, the order <italic>u</italic> of a non-supersingular elliptic curve over <italic>F</italic><sub><italic>p</italic></sub>, the order <italic>r</italic> of a point on a elliptic curve.</p></list-item></list></p><p>We would also remark that “the IEEE Standard Specifications for Public-Key Cryptography” [<xref rid="pone.0161857.ref040" ref-type="bibr">40</xref>] recommends that in the construction of a curve with prescribed CM, if <italic>D</italic> = 3, the coefficients <italic>a</italic><sub>0</sub> and <italic>b</italic><sub>0</sub> of <italic>E</italic> should be 0 and 1 respectively.</p></sec><sec id="sec008"><title>4.4 Algorithm 3</title><p>Algorithm 3 presents the method to construct pairing-friendly elliptic curves under embedding degree 1. We assume that there are two different subgroups with the same order <italic>r</italic> on the elliptic curve generated by algorithm 3, where <italic>r</italic> is a large prime.</p><p>In algorithm 3, the input parameter is the length <italic>m</italic>(<italic>m</italic> ≥ 160) for the subgroup order, and the output results are <italic>a</italic>, <italic>b</italic> and the prime <italic>p</italic> as the parameters of the elliptic curve <italic>y</italic><sup>2</sup> ≡ <italic>x</italic><sup>3</sup> + <italic>ax</italic> + <italic>b</italic> mod <italic>p</italic>, low hamming prime <italic>r</italic> as the order of subgroup, point <italic>P</italic><sub>1</sub> as the base point for generating subgroup <italic>G</italic><sub>1</sub> while calculating Tate pairing, where <italic>rP</italic><sub>1</sub> = 0, and point <italic>P</italic><sub>2</sub> as the base point for generating subgroup <italic>G</italic><sub>2</sub> while calculating Tate pairing where <italic>rP</italic><sub>1</sub> = 0, <italic>rP</italic><sub>2</sub> = 0 and <italic>G</italic><sub>1</sub> ∩ <italic>G</italic><sub>2</sub> = ∅.</p><p>Algorithm 3 is designed to be convenient for users generating pairing-friendly elliptic curves under embedding degree 1, as the only input parameter is the length of the binary representation for the order <italic>r</italic> of the subgroup. Algorithm 3 runs by calling algorithm 2, which in turn calls algorithm 1.</p><p specific-use="line">Algorithm 3. Constructing pairing-friendly elliptic curves.</p><p specific-use="line">Input: The length <italic>m</italic>(<italic>m</italic> ≥ 160) for the subgroup order.</p><p specific-use="line">Output: <italic>a</italic>, <italic>b</italic> and the prime <italic>p</italic> denote the parameters of the elliptic curve <italic>y</italic><sup>2</sup> ≡ <italic>x</italic><sup>3</sup> + <italic>ax</italic> + <italic>b</italic> mod <italic>p</italic>, low hamming order <italic>r</italic> denotes the order of subgroup, point <italic>P</italic><sub>1</sub>(<italic>rP</italic><sub>1</sub> = 0) and point <italic>P</italic><sub>2</sub>(<italic>rP</italic><sub>2</sub> = 0).</p><p specific-use="line"><list list-type="simple"><list-item><label>step 1</label><p>Generate the finite field <italic>p</italic>, the order <italic>u</italic> of a non-supersingular elliptic curve over <italic>F</italic><sub><italic>p</italic></sub>, the order <italic>r</italic> of a point on the elliptic curve using algorithm 2;</p></list-item><list-item><label>step 2</label><p>Select an integer <italic>ζ</italic> with 0 < <italic>ζ</italic> < <italic>p</italic>;</p></list-item><list-item><label>step 3</label><p>Set <italic>a</italic> ← 0 and <italic>b</italic> ← <italic>b</italic><sub>0</sub>ζ mod <italic>p</italic>;</p></list-item><list-item><label>step 4</label><p>Locate a point <italic>P</italic><sub>1</sub> with order <italic>r</italic> on the curve <italic>y</italic><sup>2</sup> ≡ <italic>x</italic><sup>3</sup> + <italic>ax</italic> + <italic>b</italic> mod <italic>p</italic>.</p></list-item><list-item><label>step 5</label><p>If the output of Step 4 is in the wrong order, goto Step 2.</p></list-item><list-item><label>step 6</label><p>Locate a point <italic>P</italic><sub>2</sub> with order r on the curve <italic>y</italic><sup>2</sup> ≡ <italic>x</italic><sup>3</sup> + <italic>ax</italic> + <italic>b</italic> mod <italic>p</italic>, where <italic>P</italic><sub>2</sub> ∉ {<italic>kP</italic><sub>1</sub>|<italic>k</italic> ∈ {1, 2…, <italic>r</italic>}}.</p></list-item><list-item><label>step 7</label><p>The output <italic>p</italic>, <italic>a</italic>, <italic>b</italic> as the parameters of the elliptic curve <italic>y</italic><sup>2</sup> ≡ <italic>x</italic><sup>3</sup> + <italic>ax</italic> + <italic>b</italic> mod <italic>p</italic>, the large prime <italic>r</italic> with low hamming weight as the order of subgroup, the point <italic>P</italic><sub>1</sub> as the base point for generating subgroup <italic>G</italic><sub>1</sub> while calculating Tate pairing, where <italic>rP</italic><sub>1</sub> = 0, and the point <italic>P</italic><sub>2</sub> as the base point for generating subgroup <italic>G</italic><sub>2</sub>, while <italic>rP</italic><sub>2</sub> = 0 and <italic>G</italic><sub>1</sub> ∩ <italic>G</italic><sub>2</sub> = ∅.</p></list-item></list></p><p>The elliptic curve generated by algorithm 3 can potentially include two different subgroups <italic>G</italic><sub>1</sub> and <italic>G</italic><sub>2</sub>, with large prime order <italic>r</italic> with low hamming weight for computing Tate pairing. Because the order <italic>r</italic> of subgroup is a public parameter, these parameters generated by the algorithms presented in the paper do not impact on the security of Pairing-based cryptosystems(PBC).</p></sec><sec id="sec009"><title>4.5 Preliminary Findings</title><p>We implement the construction described in Section 4.1 using Pentium 4 PC (CPU 3.06GHz), and the findings are as follows.</p><p>Algorithm 1:</p><p specific-use="continuation"><italic>r</italic> = 730750818686719107034401070324602422792720220161 = 2159 + 2124 + 228 + 20</p><p>Algorithm 2:</p><p specific-use="continuation"><italic>p</italic> = 53399675901131022287481940452568268554861807611629722703698801201 2286237103997609758897031086083</p><p specific-use="continuation"><italic>r</italic> = 730750818686719107034401070324602422792720220161</p><p specific-use="continuation"><italic>u</italic> = <italic>r</italic><sup>2</sup> = 53399675901131022287481940452568268554861807611556647621830129 2905251836033673007336104310865921</p><p>Algorithm 3:</p><p><xref ref-type="table" rid="pone.0161857.t001">Table 1</xref> describes 10 elliptic curves generated by algorithm 3 under the above <italic>p</italic>, <italic>r</italic>, <italic>u</italic>.</p><table-wrap id="pone.0161857.t001" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161857.t001</object-id><label>Table 1</label><caption><title>10 pairing-friendly curves with low hamming weight 4 under given <italic>p</italic>, <italic>r</italic>, <italic>u</italic>(<italic>r</italic> with 160 bits).</title></caption><alternatives><graphic id="pone.0161857.t001g" xlink:href="pone.0161857.t001"></graphic><table frame="box" rules="all" border="0"><colgroup span="1"><col align="left" valign="middle" span="1"></col><col align="left" valign="middle" span="1"></col><col align="left" valign="middle" span="1"></col><col align="left" valign="middle" span="1"></col></colgroup><thead><tr><th align="center" rowspan="1" colspan="1">Parameters</th><th align="center" rowspan="1" colspan="1">b</th><th align="center" rowspan="1" colspan="1"><italic>P</italic><sub>1</sub></th><th align="center" rowspan="1" colspan="1"><italic>P</italic><sub>2</sub></th></tr></thead><tbody><tr><td align="center" rowspan="1" colspan="1">The 1<sup>st</sup> group</td><td align="center" rowspan="1" colspan="1">5582</td><td align="center" rowspan="1" colspan="1">(92216901,324171638614811955738700451351453938462743355913304125667979195175749628071873615636670182400781)</td><td align="center" rowspan="1" colspan="1">(2900911840,470565327089465608766717290556724343611875827253253971039274229090627830093258979017255917746829)</td></tr><tr><td align="center" rowspan="1" colspan="1">The 2<sup>nd</sup> group</td><td align="center" rowspan="1" colspan="1">411</td><td align="center" rowspan="1" colspan="1">(6456,200783653312643253000427685185361672824889578029877838466376294032581210908578307946592006236274)</td><td align="center" rowspan="1" colspan="1">(7718449758221,246594700063950682499345743858581550409793007029702423620631032309187268322219527336805985703980)</td></tr><tr><td align="center" rowspan="1" colspan="1">The 3<sup>rd</sup> group</td><td align="center" rowspan="1" colspan="1">6888558</td><td align="center" rowspan="1" colspan="1">(63,483447298606802197007667782086007062212874881060089832042154800397367248862591909523693105053579)</td><td align="center" rowspan="1" colspan="1">(503,77335678175724311469109067552943334864235153595640796029200821503606472539285202409938146494560)</td></tr><tr><td align="center" rowspan="1" colspan="1">The 4<sup>th</sup> group</td><td align="center" rowspan="1" colspan="1">1852511737533</td><td align="center" rowspan="1" colspan="1">(28136114,242158699775814654792914165109030127513135019773154553510244588647142304534134418272078033955490)</td><td align="center" rowspan="1" colspan="1">(86590,121551762235427048604306704938720769730830601113589433595621413717086224050169417598237928322315)</td></tr><tr><td align="center" rowspan="1" colspan="1">The 5<sup>th</sup> group</td><td align="center" rowspan="1" colspan="1">111158</td><td align="center" rowspan="1" colspan="1">(9069952,191884782129835076896430782729279489410474467097317768476761535512656282281715989056396995028939)</td><td align="center" rowspan="1" colspan="1">(40,362063866070142646287391901715038404328540944674222712928339139412213864564948793769019222805261)</td></tr><tr><td align="center" rowspan="1" colspan="1">The 6<sup>th</sup> group</td><td align="center" rowspan="1" colspan="1">7134</td><td align="center" rowspan="1" colspan="1">(352,373120637403567989697297819791130549970377887442049625481567602466046997349176087351878502769389)</td><td align="center" rowspan="1" colspan="1">(1171827216,497218853134580777525964760410326161237125053509830407941623317513914592421492486740293952308203)</td></tr><tr><td align="center" rowspan="1" colspan="1">The 7<sup>th</sup> group</td><td align="center" rowspan="1" colspan="1">562</td><td align="center" rowspan="1" colspan="1">(7751170,170089631638765123245772026413070351656555635734890000712753208456308661954335842959630945562639)</td><td align="center" rowspan="1" colspan="1">(9123978,491696588250751128316690742989376247219892973435085382978639044870863996676582978948360971631311)</td></tr><tr><td align="center" rowspan="1" colspan="1">The 8<sup>th</sup> group</td><td align="center" rowspan="1" colspan="1">1105557501121</td><td align="center" rowspan="1" colspan="1">(96209917051711,525449385155426365101090731761951180537095809586740545805755386839131992568764934554139827350205)</td><td align="center" rowspan="1" colspan="1">(12835,74127495296715015118497558174623723156473745792295184182056487700402725864604342423009775785761)</td></tr><tr><td align="center" rowspan="1" colspan="1">The 9<sup>th</sup> group</td><td align="center" rowspan="1" colspan="1">814</td><td align="center" rowspan="1" colspan="1">(76110676327,455230770668674635001073148949612110022716252695998918206294806414038955424454903144922555015137)</td><td align="center" rowspan="1" colspan="1">(856171875,173617915786825757928929966543011205848033233611185463361858494144333951770711174509831733937961)</td></tr><tr><td align="center" rowspan="1" colspan="1">The 10<sup>th</sup> group</td><td align="center" rowspan="1" colspan="1">1110977</td><td align="center" rowspan="1" colspan="1">(935542646001,425605723028492010195922479602517755514636860155519341225132168354176911010027713634301519279864)</td><td align="center" rowspan="1" colspan="1">(211058810,424408607333334853102700723328774094337451473846030924917501392093461859795155755424956700868152)</td></tr></tbody></table></alternatives></table-wrap></sec></sec><sec id="sec010"><title>5 Discussion</title><p>In the Miller algorithm, for every bit of the order <italic>r</italic> of the subgroup, we would need to compute 16 multiplication and 7 inverse operations. If the bit is 1, however,we would need to compute 11 multiplication and five inverse operations. For the order r of the subgroup with 160 bits in ordinary PBCs, there are 80 ‘1’ bits on average. Therefore, we would need to compute 3,429 multiplication and 1,515 inverse operations. It is pleasing to note that using the parameters in our approach, we only need 2,593 multiplication and 1,135 inverse operations, as shown in <xref ref-type="table" rid="pone.0161857.t002">Table 2</xref>.</p><table-wrap id="pone.0161857.t002" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161857.t002</object-id><label>Table 2</label><caption><title>Efficiency analysis.</title></caption><alternatives><graphic id="pone.0161857.t002g" xlink:href="pone.0161857.t002"></graphic><table frame="box" rules="all" border="0"><colgroup span="1"><col align="left" valign="middle" span="1"></col><col align="left" valign="middle" span="1"></col><col align="left" valign="middle" span="1"></col><col align="left" valign="middle" span="1"></col><col align="left" valign="middle" span="1"></col><col align="left" valign="middle" span="1"></col><col align="left" valign="middle" span="1"></col><col align="left" valign="middle" span="1"></col><col align="left" valign="middle" span="1"></col></colgroup><thead><tr><th align="center" rowspan="1" colspan="1"></th><th align="center" colspan="4" rowspan="1">The ordinary PBC</th><th align="center" colspan="4" rowspan="1">PBC with parameter in the paper</th></tr><tr><th align="center" rowspan="1" colspan="1"></th><th align="center" colspan="2" rowspan="1">Every bit (160 bits)</th><th align="center" colspan="2" rowspan="1">Every bit with 1 (79 bits)</th><th align="center" colspan="2" rowspan="1">Every bit (160 bits)</th><th align="center" colspan="2" rowspan="1">Every bit with 1 (3 bits)</th></tr><tr><th align="center" rowspan="1" colspan="1"></th><th align="center" rowspan="1" colspan="1">Multiple</th><th align="center" rowspan="1" colspan="1">Inverse</th><th align="center" rowspan="1" colspan="1">Multiple</th><th align="center" rowspan="1" colspan="1">Inverse</th><th align="center" rowspan="1" colspan="1">Multiple</th><th align="center" rowspan="1" colspan="1">Inverse</th><th align="center" rowspan="1" colspan="1">Multiple</th><th align="center" rowspan="1" colspan="1">Inverse</th></tr></thead><tbody><tr><td align="center" rowspan="1" colspan="1"></td><td align="center" rowspan="1" colspan="1">16</td><td align="center" rowspan="1" colspan="1">7</td><td align="center" rowspan="1" colspan="1">11</td><td align="center" rowspan="1" colspan="1">5</td><td align="center" rowspan="1" colspan="1">16</td><td align="center" rowspan="1" colspan="1">7</td><td align="center" rowspan="1" colspan="1">11</td><td align="center" rowspan="1" colspan="1">5</td></tr><tr><td align="center" rowspan="1" colspan="1"></td><td align="center" rowspan="1" colspan="1">2560</td><td align="center" rowspan="1" colspan="1">1120</td><td align="center" rowspan="1" colspan="1">869</td><td align="center" rowspan="1" colspan="1">395</td><td align="center" rowspan="1" colspan="1">2560</td><td align="center" rowspan="1" colspan="1">1120</td><td align="center" rowspan="1" colspan="1">33</td><td align="center" rowspan="1" colspan="1">15</td></tr><tr><td align="center" rowspan="1" colspan="1">Total</td><td align="right" colspan="4" rowspan="1">Multiple:3429 Inverse:1515</td><td align="right" colspan="4" rowspan="1">Multiple:2593 Inverse:1135</td></tr></tbody></table></alternatives></table-wrap><p>An inverse operation is estimated to be 5.18 multiplication operations [<xref rid="pone.0161857.ref039" ref-type="bibr">39</xref>], and implementing our method outlined in this paper will save 24.9% of the time required to compute the Tate pairing:
<disp-formula id="pone.0161857.e022"><alternatives><graphic xlink:href="pone.0161857.e022.jpg" id="pone.0161857.e022g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M22"><mml:mrow><mml:mfrac><mml:mrow><mml:mn>2593</mml:mn><mml:mo>+</mml:mo><mml:mn>1135</mml:mn><mml:mo>*</mml:mo><mml:mn>5</mml:mn><mml:mo>.</mml:mo><mml:mn>18</mml:mn></mml:mrow><mml:mrow><mml:mn>3429</mml:mn><mml:mo>+</mml:mo><mml:mn>1515</mml:mn><mml:mo>*</mml:mo><mml:mn>5</mml:mn><mml:mo>.</mml:mo><mml:mn>18</mml:mn></mml:mrow></mml:mfrac><mml:mo>=</mml:mo><mml:mn>0</mml:mn><mml:mo>.</mml:mo><mml:mn>751</mml:mn><mml:mo>=</mml:mo><mml:mn>75</mml:mn><mml:mo>.</mml:mo><mml:mn>1</mml:mn><mml:mo>%</mml:mo></mml:mrow></mml:math></alternatives></disp-formula></p><p>To demonstrate the practicality of the new method we proposed,using the parameters with 160 bits presented in <xref ref-type="table" rid="pone.0161857.t001">Table 1</xref>, we implement a proof-of-concepton a Pentium 4 PC (CPU 3.06GHz) in <xref ref-type="table" rid="pone.0161857.t003">Table 3</xref>, using the parameters with 160 bits presented in <xref ref-type="table" rid="pone.0161857.t001">Table 1</xref>.</p><table-wrap id="pone.0161857.t003" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161857.t003</object-id><label>Table 3</label><caption><title>Comparative summary of Tate pairing computations.</title></caption><alternatives><graphic id="pone.0161857.t003g" xlink:href="pone.0161857.t003"></graphic><table frame="box" rules="all" border="0"><colgroup span="1"><col align="left" valign="middle" span="1"></col><col align="left" valign="middle" span="1"></col><col align="left" valign="middle" span="1"></col></colgroup><thead><tr><th align="center" rowspan="1" colspan="1">Parameters</th><th align="center" rowspan="1" colspan="1">The result from Bertoni et al. [<xref rid="pone.0161857.ref039" ref-type="bibr">39</xref>]</th><th align="center" rowspan="1" colspan="1">The result from this paper</th></tr></thead><tbody><tr><td align="center" rowspan="1" colspan="1">Platform</td><td align="center" rowspan="1" colspan="1">PentiumIII @ 1GHz</td><td align="center" rowspan="1" colspan="1">Pentium IV@ 3.06GHz</td></tr><tr><td align="center" rowspan="1" colspan="1">Length of prime</td><td align="center" rowspan="1" colspan="1">160 bits</td><td align="center" rowspan="1" colspan="1">160 bits</td></tr><tr><td align="center" rowspan="1" colspan="1">Low Hamming Weight</td><td align="center" rowspan="1" colspan="1">3</td><td align="center" rowspan="1" colspan="1">4</td></tr><tr><td align="center" rowspan="1" colspan="1">Time for a Tate pairing</td><td align="center" rowspan="1" colspan="1">41ms</td><td align="center" rowspan="1" colspan="1">12.93ms</td></tr></tbody></table></alternatives></table-wrap><p>As shown in <xref ref-type="fig" rid="pone.0161857.g001">Fig 1</xref>., our implementation takes 12.93 ms to compute a pairing. We then compared with the findings from Bertoni et al. [<xref rid="pone.0161857.ref039" ref-type="bibr">39</xref>], as shown in <xref ref-type="table" rid="pone.0161857.t003">Table 3</xref>. In the latter, the large prime of the order of the subgroup is 160 bits, but with a Hamming weight equal to 3 and the embedding degree of 2. As shown in <xref ref-type="table" rid="pone.0161857.t003">Table 3</xref>, our algorithm is more computationally efficient compared to that of Bertoni et al.</p><fig id="pone.0161857.g001" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161857.g001</object-id><label>Fig 1</label><caption><title>The result of computing Tate pairing on the first group curve.</title><p>The first 9 lines gives the parameters of the first group curves. Then the result of <italic>e</italic>(<italic>P</italic>, <italic>Q</italic>), <italic>e</italic>(2<italic>P</italic>, <italic>Q</italic>), <italic>e</italic>(<italic>P</italic>, 2<italic>Q</italic>), <italic>e</italic>(3<italic>P</italic>, <italic>Q</italic>), <italic>e</italic>(<italic>P</italic>, 3<italic>Q</italic>), <italic>e</italic>(<italic>P</italic>, <italic>Q</italic>)<sup>2</sup> and <italic>e</italic>(<italic>P</italic>, <italic>Q</italic>)<sup>3</sup> are given and the bilinear property is verified.</p></caption><graphic xlink:href="pone.0161857.g001"></graphic></fig><p>The computation results depicted in <xref ref-type="fig" rid="pone.0161857.g001">Fig 1</xref>. can also be verified using the bilinear characteristic of Tate pairing, as explained below:
<disp-formula id="pone.0161857.e023"><alternatives><graphic xlink:href="pone.0161857.e023.jpg" id="pone.0161857.e023g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M23"><mml:mrow><mml:mi>t</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mi>P</mml:mi><mml:mo>,</mml:mo><mml:mn>2</mml:mn><mml:mi>Q</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mi>t</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mn>2</mml:mn><mml:mi>P</mml:mi><mml:mo>,</mml:mo><mml:mi>Q</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mi>t</mml:mi><mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:mi>P</mml:mi><mml:mo>,</mml:mo><mml:mi>Q</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:msup></mml:mrow></mml:math></alternatives></disp-formula><disp-formula id="pone.0161857.e024"><alternatives><graphic xlink:href="pone.0161857.e024.jpg" id="pone.0161857.e024g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M24"><mml:mrow><mml:mi>t</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mi>P</mml:mi><mml:mo>,</mml:mo><mml:mn>3</mml:mn><mml:mi>Q</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mi>t</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mn>3</mml:mn><mml:mi>P</mml:mi><mml:mo>,</mml:mo><mml:mi>Q</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mi>t</mml:mi><mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:mi>P</mml:mi><mml:mo>,</mml:mo><mml:mi>Q</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mn>3</mml:mn></mml:msup></mml:mrow></mml:math></alternatives></disp-formula></p><p>Recall that in Tate pairing, if the embedding degree <italic>k</italic> ≠ 1, then the computation of Tate pairing is related to the extension field <inline-formula id="pone.0161857.e025"><alternatives><graphic xlink:href="pone.0161857.e025.jpg" id="pone.0161857.e025g" mimetype="image" position="anchor" orientation="portrait"></graphic><mml:math id="M25"><mml:mrow><mml:msub><mml:mi>F</mml:mi><mml:mrow><mml:msup><mml:mi>p</mml:mi><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:msub></mml:mrow></mml:math></alternatives></inline-formula>, which is very time consuming. Building on Miller’s algorithm, we present an effective algorithm to construct pairing friendly elliptic curves with low hamming weight 4 under embedding degree 1, which enables the computation of Tate pairing only on the base field.</p></sec><sec id="sec011"><title>6 Conclusion</title><p>Ensuring information confidentiality in critical infrastructures will be increasingly important in our increasingly interconnected world. In this paper, we studied the generation method of pairing-friendly elliptic curves for identity-based cryptography(IBC), with the aim to significantly improve the computation efficiency of IBC. We demonstrated how pairing-friendly elliptic curves can be efficiently conducted, both in theory and practice which can be deployed in critical infrastructure systems, such as cyber-physical systems with limited resources [<xref rid="pone.0161857.ref040" ref-type="bibr">40</xref>]. In our approach,pairings computing requires only the base field, rather than the extension field.</p><p>More specifically, in this paper, we described and conducted a preliminary analysis of the new method to construct pairing-friendly elliptic curves under embedding degree 1. Unlike the existed traditional CM methods,the parameters are not randomly generated in our method. The parameters are computed under a given expression, which significantly improves the efficiency of generating elliptic curve. Moreover, in our algorithm, the only input parameter is the binary length of the large prime <italic>r</italic>, and then all parameters of the elliptic curve can be rapidly generated. Our method consists of three algorithms, namely: an algorithm to generate low hamming prime <italic>r</italic> according to the expected length of the large primer, which is also used as the order of the subgroup; an algorithm to calculate the character <italic>p</italic> of the finite field <italic>F</italic><sub><italic>p</italic></sub> and the order <italic>u</italic> of the elliptic curve according to the prime <italic>r</italic>; and an algorithm to generate the pairing-friendly elliptic curves and the two different points <italic>P</italic><sub>1</sub> and <italic>P</italic><sub>2</sub> on the elliptic curve with the same order <italic>r</italic>. It also ensures <italic>G</italic><sub>1</sub> ∩ <italic>G</italic><sub>2</sub> = ∅, where <italic>G</italic><sub>1</sub> is the subgroup generated by <italic>P</italic><sub>1</sub> and <italic>G</italic><sub>2</sub> is the subgroup generated by <italic>P</italic><sub>2</sub>, <italic>G</italic><sub>1</sub> and <italic>G</italic><sub>2</sub> are two different subgroups of <italic>E</italic> with the same order <italic>r</italic>.</p><p>The paper also provided 10 elliptic curves with low hamming, weight 4 under 160 bits generated using our algorithms, which demonstrated the utility of our method. Then, we demonstrated the practicality of our method by implementing the method using Tate pairing.</p><p>Our curves can be applied in real word such as Internet of Things(IoT), Electronic Commerce(EC) and Copyright Protection(CP). In fact, in all fields, which are involved in public key cryptography, the proposed method can be applied to implement digital signature, key management and authentication protocol [<xref rid="pone.0161857.ref041" ref-type="bibr">41</xref>–<xref rid="pone.0161857.ref043" ref-type="bibr">43</xref>]. The future work includes two aspects. The first aspect is to optimize Miller’s algorithm to improve the computation efficiency of Tate pairing. The other aspect is to apply the elliptic curves constructed by our method to the practical cryptosystem.</p></sec><sec sec-type="supplementary-material" id="sec012"><title>Supporting Information</title><supplementary-material content-type="local-data" id="pone.0161857.s001"><label>S1 File</label><caption><title>Pairing-friendly elliptic curves under embedding degree 1 with 160 bits.</title><p>There are 10 group pairing-friendly elliptic curves under embedding degree 1 with 160 bits. In every group, the parameters of <italic>p</italic>, <italic>r</italic>, #<italic>E</italic>, <italic>b</italic>, <italic>P</italic>, <italic>Q</italic> are given. The parameters of <italic>a</italic> is equal 0 in all groups.</p><p>(PDF)</p></caption><media xlink:href="pone.0161857.s001.pdf"><caption><p>Click here for additional data file.</p></caption></media></supplementary-material><supplementary-material content-type="local-data" id="pone.0161857.s002"><label>S2 File</label><caption><title>Pairing-friendly elliptic curves under embedding degree 1 with 190 bits.</title><p>There are 10 group pairing-friendly elliptic curves under embedding degree 1 with 160 bits. In every group, the parameters of <italic>p</italic>, <italic>r</italic>, #<italic>E</italic>, <italic>b</italic>, <italic>P</italic>, <italic>Q</italic> are given. The parameters <italic>a</italic> is equal 0 in all groups.</p><p>(PDF)</p></caption><media xlink:href="pone.0161857.s002.pdf"><caption><p>Click here for additional data file.</p></caption></media></supplementary-material></sec></body><back><ref-list><title>References</title><ref id="pone.0161857.ref001"><label>1</label><mixed-citation publication-type="journal"><name><surname>Dong</surname><given-names>MX</given-names></name>, <name><surname>Ota</surname><given-names>K</given-names></name>, <name><surname>Laurence</surname><given-names>T</given-names></name>, <etal>et al</etal><article-title>LSCD: A Low-Storage Clone Detection Protocol for Cyber-Physical Systems</article-title>. <source>IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems</source>, <year>2016</year>, <volume>35</volume>(<issue>5</issue>):<fpage>712</fpage>–<lpage>723</lpage>. <comment>doi: <ext-link ext-link-type="uri" xlink:href="http://dx.doi.org/10.1109/TCAD.2016.2539327">10.1109/TCAD.2016.2539327</ext-link></comment></mixed-citation></ref><ref id="pone.0161857.ref002"><label>2</label><mixed-citation publication-type="journal"><name><surname>Wang</surname><given-names>L.</given-names></name>, <name><surname>Tao</surname><given-names>J.</given-names></name>, <name><surname>Ranjan</surname><given-names>R.</given-names></name>, <etal>et al</etal><article-title>G-Hadoop: MapReduce across distributed data centers for data-intensive computing</article-title>. <source>Future Generation Computer Systems</source>, <year>2013</year>, <volume>29</volume>(<issue>3</issue>):<fpage>739</fpage>–<lpage>750</lpage><comment>doi: <ext-link ext-link-type="uri" xlink:href="http://dx.doi.org/10.1016/j.future.2012.09.001">10.1016/j.future.2012.09.001</ext-link></comment></mixed-citation></ref><ref id="pone.0161857.ref003"><label>3</label><mixed-citation publication-type="book"><name><surname>Kepler</surname><given-names>D</given-names></name>, <name><surname>Heasley</surname><given-names>P</given-names></name><source>Implementation of EO 13636 and PPD-21: Draft Report and Recommendations</source>. <publisher-name>National Infrastructure Advisory Council</publisher-name>, <year>2013</year></mixed-citation></ref><ref id="pone.0161857.ref004"><label>4</label><mixed-citation publication-type="journal"><name><surname>Zhao</surname><given-names>J.</given-names></name>, <name><surname>Wang</surname><given-names>L.</given-names></name>, <name><surname>Tao</surname><given-names>J.</given-names></name>, etc. <article-title>A security framework in G-Hadoop for big data computing across distributed Cloud data centres</article-title>. <source>Journal of Computer and System Sciences</source>, <year>2014</year>, <volume>80</volume>(<issue>5</issue>):<fpage>994</fpage>–<lpage>1007</lpage>. <comment>doi: <ext-link ext-link-type="uri" xlink:href="http://dx.doi.org/10.1016/j.jcss.2014.02.006">10.1016/j.jcss.2014.02.006</ext-link></comment></mixed-citation></ref><ref id="pone.0161857.ref005"><label>5</label><mixed-citation publication-type="journal"><name><surname>Chen</surname><given-names>D.</given-names></name>, <name><surname>Liu</surname><given-names>Z.</given-names></name>, <name><surname>Wang</surname><given-names>L.</given-names></name>,etc. <article-title>On-demand service hosting on production grid infrastructures</article-title>. <source>MONET</source>, <year>2013</year>, <volume>18</volume>(<issue>5</issue>): <fpage>651</fpage>–<lpage>663</lpage>.</mixed-citation></ref><ref id="pone.0161857.ref006"><label>6</label><mixed-citation publication-type="journal"><name><surname>Wang</surname><given-names>L.</given-names></name>, <name><surname>Kurze</surname><given-names>T.</given-names></name>, <name><surname>Tao</surname><given-names>J.</given-names></name>, etc. <article-title>Natural Disaster Monitoring with Wireless Sensor Networks: A Case Study of Data-intensive Applications upon Low-Cost Scalable Systems</article-title>. <source>The Journal of Supercomputing</source>, <year>2013</year>, <volume>66</volume>(<issue>3</issue>): <fpage>1178</fpage>–<lpage>1193</lpage>.</mixed-citation></ref><ref id="pone.0161857.ref007"><label>7</label><mixed-citation publication-type="journal"><name><surname>Wang</surname><given-names>L.</given-names></name>, <name><surname>Fu</surname><given-names>C</given-names></name>. <article-title>Research Advances in Modern Cyberinfrastructure</article-title>. <source>Generation Comput</source>, <year>2010</year>, <volume>28</volume>(<issue>2</issue>): <fpage>111</fpage>–<lpage>112</lpage>. <comment>doi: <ext-link ext-link-type="uri" xlink:href="http://dx.doi.org/10.1007/s00354-009-0077-9">10.1007/s00354-009-0077-9</ext-link></comment></mixed-citation></ref><ref id="pone.0161857.ref008"><label>8</label><mixed-citation publication-type="journal"><name><surname>Zhang</surname><given-names>W.</given-names></name>, <name><surname>Wang</surname><given-names>L.</given-names></name>, <name><surname>Liu</surname><given-names>D.</given-names></name>, etc. <article-title>Towards building a multi-datacenter infrastructure for massive remote sensing image processing</article-title>. <source>Concurrency and Computation: Practice and Experience</source>, <year>2013</year>, <volume>25</volume>(<issue>12</issue>): <fpage>1798</fpage>–<lpage>1812</lpage>. <comment>doi: <ext-link ext-link-type="uri" xlink:href="http://dx.doi.org/10.1002/cpe.2966">10.1002/cpe.2966</ext-link></comment></mixed-citation></ref><ref id="pone.0161857.ref009"><label>9</label><mixed-citation publication-type="journal"><name><surname>Wang</surname><given-names>L.</given-names></name>, <name><surname>Chen</surname><given-names>D.</given-names></name>, <name><surname>Hu</surname><given-names>Y.</given-names></name>, etc. <article-title>Towards enabling Cyberinfrastructure as a Service in Clouds</article-title>. <source>Computers & Electrical Engineering</source>, <year>2013</year>, <volume>39</volume>(<issue>1</issue>): <fpage>3</fpage>–<lpage>14</lpage>. <comment>doi: <ext-link ext-link-type="uri" xlink:href="http://dx.doi.org/10.1016/j.compeleceng.2012.05.001">10.1016/j.compeleceng.2012.05.001</ext-link></comment></mixed-citation></ref><ref id="pone.0161857.ref010"><label>10</label><mixed-citation publication-type="book"><name><surname>Raymond</surname><given-names>C</given-names></name><chapter-title>A conceptual interdisciplinary plug-and-play cyber securityframework</chapter-title> In <name><surname>Kaur</surname><given-names>H</given-names></name> & <name><surname>Tao</surname><given-names>X</given-names></name>, editors, <source>ICTs and the Millennium Development Goals A United Nations Perspective</source>, pp. <fpage>81</fpage>–<lpage>99</lpage>, <publisher-loc>New York, USA</publisher-loc>: <publisher-name>Springer</publisher-name>, <year>2014</year>.</mixed-citation></ref><ref id="pone.0161857.ref011"><label>11</label><mixed-citation publication-type="journal"><name><surname>Raymond Choo</surname><given-names>K</given-names></name>. <article-title>The cyber threat landscape: Challenges and future research directions</article-title>. <source>Computers & Security</source>, <year>2011</year>, <volume>30</volume>(<issue>8</issue>): <fpage>719</fpage>–<lpage>731</lpage>. <comment>doi: <ext-link ext-link-type="uri" xlink:href="http://dx.doi.org/10.1016/j.cose.2011.08.004">10.1016/j.cose.2011.08.004</ext-link></comment></mixed-citation></ref><ref id="pone.0161857.ref012"><label>12</label><mixed-citation publication-type="other">Eisentrager K, Lauter K, Montgomery P. Fast elliptic curve arithmetic and improved Weil pairing evaluation. Proc. of the 2003 RSA conference on The cryptographers’ track, Berlin, Germany, pp. 343–354, 2003.</mixed-citation></ref><ref id="pone.0161857.ref013"><label>13</label><mixed-citation publication-type="journal"><name><surname>Raymond Choo</surname><given-names>K</given-names></name>. <article-title>High tech criminal threats to the national information infrastructure</article-title>. <source>Information Security Technology Report</source>, <year>2010</year>, <volume>15</volume>(<issue>3</issue>): <fpage>104</fpage>–<lpage>111</lpage>. <comment>doi: <ext-link ext-link-type="uri" xlink:href="http://dx.doi.org/10.1016/j.istr.2009.09.001">10.1016/j.istr.2009.09.001</ext-link></comment></mixed-citation></ref><ref id="pone.0161857.ref014"><label>14</label><mixed-citation publication-type="other">Cornish P, Livingstone D, Clemente D, et al. Cyber Security and the UK’s Critical National Infrastructure. A Chatham House Report, 2011.</mixed-citation></ref><ref id="pone.0161857.ref015"><label>15</label><mixed-citation publication-type="other">Yang Y, Lu J, Raymond C, et al. On Lightweight Security Enforcement in Cyber-physical Systems. In Proceedings of International Workshop on Lightweight Cryptography for Security & Privacy (LightSec 2015), Bochum, Germany, Lecture Notes in Computer Science, Springer-Verlag, 2015.</mixed-citation></ref><ref id="pone.0161857.ref016"><label>16</label><mixed-citation publication-type="journal"><name><surname>Dong</surname><given-names>M</given-names></name>, <name><surname>Ota</surname><given-names>K</given-names></name>, <name><surname>Laurence</surname><given-names>T</given-names></name>, <etal>et al</etal><article-title>LSCD: A Low-Storage Clone Detection Protocol for Cyber-Physical Systems</article-title>. <source>IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems</source>, <year>2016</year>, <volume>35</volume>(<issue>5</issue>):<fpage>712</fpage>–<lpage>723</lpage>. <comment>doi: <ext-link ext-link-type="uri" xlink:href="http://dx.doi.org/10.1109/TCAD.2016.2539327">10.1109/TCAD.2016.2539327</ext-link></comment></mixed-citation></ref><ref id="pone.0161857.ref017"><label>17</label><mixed-citation publication-type="journal"><name><surname>Dong</surname><given-names>M</given-names></name>, <name><surname>Li</surname><given-names>H</given-names></name>, <name><surname>Ota</surname><given-names>K</given-names></name>, <etal>et al</etal><article-title>Rule caching in SDN-enabled mobile access networks</article-title>. <source>IEEE Network</source>, <year>2015</year>, <volume>29</volume>(<issue>4</issue>):<fpage>40</fpage>–<lpage>45</lpage>. <comment>doi: <ext-link ext-link-type="uri" xlink:href="http://dx.doi.org/10.1109/MNET.2015.7166189">10.1109/MNET.2015.7166189</ext-link></comment></mixed-citation></ref><ref id="pone.0161857.ref018"><label>18</label><mixed-citation publication-type="book"><name><surname>Mao</surname><given-names>W</given-names></name>. <source>Modern Cryptography: Theory and Practice</source>. <publisher-name>Prentice Hall</publisher-name>, <year>2003</year></mixed-citation></ref><ref id="pone.0161857.ref019"><label>19</label><mixed-citation publication-type="book"><name><surname>Joye</surname><given-names>M.</given-names></name>, <name><surname>Neven</surname><given-names>G</given-names></name>. <source>Identity-based Cryptography</source>. <publisher-name>IOS Press</publisher-name>, <year>2008</year></mixed-citation></ref><ref id="pone.0161857.ref020"><label>20</label><mixed-citation publication-type="journal"><name><surname>Moody</surname><given-names>D.</given-names></name>, <name><surname>Peralta</surname><given-names>R.</given-names></name>, <name><surname>Perlner</surname><given-names>R.</given-names></name>, etc. <article-title>Report on Pairing-based Cryptography</article-title>. <source>Journal of Research of the National Institue of Standards and Technology</source>, <year>2015</year>, <volume>120</volume>:<fpage>11</fpage>–<lpage>27</lpage>. <comment>doi: <ext-link ext-link-type="uri" xlink:href="http://dx.doi.org/10.6028/jres.120.002">10.6028/jres.120.002</ext-link></comment></mixed-citation></ref><ref id="pone.0161857.ref021"><label>21</label><mixed-citation publication-type="journal"><name><surname>Rahuman</surname><given-names>A</given-names></name>, <name><surname>Athisha</surname><given-names>G</given-names></name>. <article-title>Reconfigurable Architecture for Elliptic Curve Cryptography Using FPGA</article-title>. <source>Mathematical Problems in Engineering</source>, <year>2013</year>, <volume>2013</volume>:<fpage>1</fpage>–<lpage>8</lpage>. <comment>doi: <ext-link ext-link-type="uri" xlink:href="http://dx.doi.org/10.1155/2013/675161">10.1155/2013/675161</ext-link></comment></mixed-citation></ref><ref id="pone.0161857.ref022"><label>22</label><mixed-citation publication-type="journal"><name><surname>Dai</surname><given-names>G</given-names></name>, <name><surname>Wang</surname><given-names>M</given-names></name>, <name><surname>Peng</surname><given-names>L</given-names></name>, <etal>et al</etal><article-title>Implementation and Optimization for Tate pairing</article-title>. <source>Intelligent automation and soft computing</source>, <year>2011</year>, <volume>17</volume>(<issue>5</issue>):<fpage>607</fpage>–<lpage>617</lpage>. <comment>doi: <ext-link ext-link-type="uri" xlink:href="http://dx.doi.org/10.1080/10798587.2011.10643174">10.1080/10798587.2011.10643174</ext-link></comment></mixed-citation></ref><ref id="pone.0161857.ref023"><label>23</label><mixed-citation publication-type="journal"><name><surname>Miller</surname><given-names>V</given-names></name>. <article-title>The Weil pairing and its efficient calculation</article-title>. <source>Journal of Cryptology</source>, <year>2004</year>, <volume>17</volume>(<issue>4</issue>):<fpage>235</fpage>–<lpage>261</lpage>. <comment>doi: <ext-link ext-link-type="uri" xlink:href="http://dx.doi.org/10.1007/s00145-004-0315-8">10.1007/s00145-004-0315-8</ext-link></comment></mixed-citation></ref><ref id="pone.0161857.ref024"><label>24</label><mixed-citation publication-type="other">Duursma I, Lee H S Tate Pairing Implementation for Hyperelliptic Curves <italic>y</italic><sup>2</sup> = <italic>x</italic><sup><italic>p</italic></sup> − <italic>x</italic> + <italic>d</italic>. Proc. of Advances in Cryptology-Asiacrypt, 2003, Heibelberg,Germany, pp. 111–123.</mixed-citation></ref><ref id="pone.0161857.ref025"><label>25</label><mixed-citation publication-type="journal"><name><surname>Barreto</surname><given-names>P</given-names></name>, <name><surname>Galbraith</surname><given-names>S</given-names></name>, <name><surname>Eigeartaigh</surname><given-names>C</given-names></name>, <etal>et al</etal><article-title>Efficient pairing computation on supersingular abelian varieties</article-title>. <source>Designs, Codes and Cryptography</source>, <year>2007</year>, <volume>42</volume>(<issue>3</issue>): <fpage>239</fpage>–<lpage>271</lpage>. <comment>doi: <ext-link ext-link-type="uri" xlink:href="http://dx.doi.org/10.1007/s10623-006-9033-6">10.1007/s10623-006-9033-6</ext-link></comment></mixed-citation></ref><ref id="pone.0161857.ref026"><label>26</label><mixed-citation publication-type="journal"><name><surname>Barreto</surname><given-names>P</given-names></name>, <name><surname>Galbraith</surname><given-names>S</given-names></name>, <name><surname>Eigeartaigh</surname><given-names>C</given-names></name>, <etal>et al</etal><article-title>An efficient key-policy attribute-based encryption scheme with constant ciphertext length</article-title>. <source>Mathematical Problems in Engineering</source>, <year>2013</year>, <volume>2013</volume>:<fpage>1</fpage>–<lpage>7</lpage>.</mixed-citation></ref><ref id="pone.0161857.ref027"><label>27</label><mixed-citation publication-type="other">Cocks C, Pinch R. Identity-based cryptosystems based on the Weil pairing. unpublished manuscript, 2001.</mixed-citation></ref><ref id="pone.0161857.ref028"><label>28</label><mixed-citation publication-type="other">Fotiadis G, Konstantinou E. More Sparse Families of Pairing-Friendly Elliptic Curves. Proc. Proc. of 13th International Conference on Cryptology and Network Security, Heraklion, Greece, pp.384–399, 2014.</mixed-citation></ref><ref id="pone.0161857.ref029"><label>29</label><mixed-citation publication-type="other">Barreto P, Naehrig M. Pairing-friendly elliptic curves of prime order. Proc. Of Selected Areas in Cryptography—12th International Workshop, Kingston, Canada, pp. 319–331, 2005.</mixed-citation></ref><ref id="pone.0161857.ref030"><label>30</label><mixed-citation publication-type="other">Freeman D Constructing Pairing-Friendly Elliptic Curves with Embedding Degree 10. Proc. Of algorithmic number theory, Berlin, Germany, pp.452–465, 2006.</mixed-citation></ref><ref id="pone.0161857.ref031"><label>31</label><mixed-citation publication-type="journal"><name><surname>Miyaji</surname><given-names>A</given-names></name>, <name><surname>Nakabayashi</surname><given-names>M</given-names></name>, <name><surname>Takano</surname><given-names>S</given-names></name>. <article-title>New explicit conditions of elliptic curve traces for FR-reduction</article-title>. <source>IEICE Transactions on Fundamentals</source>, <year>2001</year>, <volume>vol. E84-A</volume>, <issue>no.5</issue>, pp.<fpage>1234</fpage>–<lpage>1243</lpage>.</mixed-citation></ref><ref id="pone.0161857.ref032"><label>32</label><mixed-citation publication-type="journal"><name><surname>Menezes</surname><given-names>A</given-names></name>, <name><surname>Okamoto</surname><given-names>T</given-names></name>, <name><surname>Vanstone</surname><given-names>S</given-names></name>. <article-title>Reducing elliptic curve logarithms to logarithms in a finite field</article-title>. <source>IEEE Transactions on Information Theory</source>, <year>1993</year>, <volume>39</volume>(<issue>5</issue>): <fpage>1639</fpage>–<lpage>1646</lpage>. <comment>doi: <ext-link ext-link-type="uri" xlink:href="http://dx.doi.org/10.1109/18.259647">10.1109/18.259647</ext-link></comment></mixed-citation></ref><ref id="pone.0161857.ref033"><label>33</label><mixed-citation publication-type="journal"><name><surname>Brezing</surname><given-names>F</given-names></name>, <name><surname>Weng</surname><given-names>A</given-names></name><article-title>Elliptic curves suitable for pairing based cryptography</article-title>. <source>Designs, Codes, and Cryptography</source>, <year>2005</year>, <volume>37</volume>(<issue>1</issue>):<fpage>133</fpage>–<lpage>141</lpage>. <comment>doi: <ext-link ext-link-type="uri" xlink:href="http://dx.doi.org/10.1007/s10623-004-3808-4">10.1007/s10623-004-3808-4</ext-link></comment></mixed-citation></ref><ref id="pone.0161857.ref034"><label>34</label><mixed-citation publication-type="other">Izuta T, Nogami Y, Morikawa Y. Ordinary Pairing Friendly Curve of Embedding Degree 1 Whose Order Has Two Large Prime Factors. Proc. of IEEE Region 10 Conference on TENCON 2010, Fukuoka, JAPAN, pp.769–772, 2010.</mixed-citation></ref><ref id="pone.0161857.ref035"><label>35</label><mixed-citation publication-type="other">Lee H, Park C. Generating Pairing-Friendly Curves with the CM Equation of Degree 1. Proc. of 3rd International Conference on Pairing-Based Cryptography, Palo Alto, California, USA, pp.66–77, 2009.</mixed-citation></ref><ref id="pone.0161857.ref036"><label>36</label><mixed-citation publication-type="journal"><name><surname>Pollard</surname><given-names>J</given-names></name>. <article-title>A monte carlo method for factorization</article-title>. <source>BIT Numerical Mathematics</source>, <year>1975</year>, <volume>15</volume>(<issue>3</issue>): <fpage>331</fpage>–<lpage>334</lpage>. <comment>doi: <ext-link ext-link-type="uri" xlink:href="http://dx.doi.org/10.1007/BF01933667">10.1007/BF01933667</ext-link></comment></mixed-citation></ref><ref id="pone.0161857.ref037"><label>37</label><mixed-citation publication-type="journal"><name><surname>Frey G and Ruck</surname><given-names>H</given-names></name>. <article-title>A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves</article-title>. <source>Mathematics of Computation</source>, <year>1994</year>, <volume>62</volume>(<issue>206</issue>): <fpage>865</fpage>–<lpage>874</lpage>. <comment>doi: <ext-link ext-link-type="uri" xlink:href="http://dx.doi.org/10.2307/2153546">10.2307/2153546</ext-link></comment></mixed-citation></ref><ref id="pone.0161857.ref038"><label>38</label><mixed-citation publication-type="other">Zhang F, Naini R and Susilo W. An efficient signature scheme from bilinear pairings and its application. Proc. Of Advances in Cryptography-PKC’04, Heidelberg, Germany, pp. 277–290, 2004.</mixed-citation></ref><ref id="pone.0161857.ref039"><label>39</label><mixed-citation publication-type="other">Bertoni G, Chen L, Fragneto P, et al. Computing Tate Pairing on Smartcards. Proc. Of Proceedings of Workshop on Cryptographic Hardware and Embedded Systems, Edinburgh, Scotland, 2005.</mixed-citation></ref><ref id="pone.0161857.ref040"><label>40</label><mixed-citation publication-type="other">IEEE-SA Standards Board. IEEE standard specifications for public-key cryptography, 2000.</mixed-citation></ref><ref id="pone.0161857.ref041"><label>41</label><mixed-citation publication-type="journal"><name><surname>Perera</surname><given-names>C</given-names></name>, <name><surname>Ranjan</surname><given-names>R</given-names></name>, <name><surname>Wang</surname><given-names>L</given-names></name>, <etal>et al</etal><article-title>Big Data Privacy in the Internet of Things Era</article-title>. <source>IT Professional</source>, <year>2015</year>, <volume>17</volume>(<issue>3</issue>): <fpage>32</fpage>–<lpage>39</lpage>. <comment>doi: <ext-link ext-link-type="uri" xlink:href="http://dx.doi.org/10.1109/MITP.2015.34">10.1109/MITP.2015.34</ext-link></comment></mixed-citation></ref><ref id="pone.0161857.ref042"><label>42</label><mixed-citation publication-type="journal"><name><surname>Kolodziej</surname><given-names>J</given-names></name>, <name><surname>Khan</surname><given-names>S</given-names></name>, <name><surname>Wang</surname><given-names>L</given-names></name>, <etal>et al</etal><article-title>Security, energy, and performance-aware resource allocation mechanisms for computational grids</article-title>. <source>Future Generation Computer Systems</source>, <volume>2014</volume>(<issue>31</issue>):<fpage>77</fpage>–<lpage>92</lpage>.</mixed-citation></ref><ref id="pone.0161857.ref043"><label>43</label><mixed-citation publication-type="journal"><name><surname>Wei</surname><given-names>J</given-names></name>, <name><surname>Cai</surname><given-names>W</given-names></name>, <name><surname>Wang</surname><given-names>L</given-names></name>, <etal>et al</etal><article-title>A secure information service for monitoring large scale gridse</article-title>. <source>Parallel Computing</source>, <year>2007</year>, <volume>33</volume>(<issue>7–8</issue>): <fpage>572</fpage>–<lpage>591</lpage>.</mixed-citation></ref></ref-list></back></pmc></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/CyberinfraV1/Data/Pmc/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000601 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Pmc/Corpus/biblio.hfd -nk 000601 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= CyberinfraV1
|flux= Pmc
|étape= Corpus
|type= RBID
|clé= PMC:5001717
|texte= Constructing Pairing-Friendly Elliptic Curves under Embedding Degree 1 for Securing Critical Infrastructures
}}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Pmc/Corpus/RBID.i -Sk "pubmed:27564373" \
| HfdSelect -Kh $EXPLOR_AREA/Data/Pmc/Corpus/biblio.hfd \
| NlmPubMed2Wicri -a CyberinfraV1
| This area was generated with Dilib version V0.6.25. |  |