| IEICE Technical Committee Submission System Conference Paper's Information |
Online Proceedings [Sign in] Tech. Rep. Archives |
| Go Top Page | Go Previous | [Japanese] / [English] |
| Paper Abstract and Keywords | ||
| Presentation | 2021-07-19 13:30 Fundamental Study on Acceleration of Inversion using Binary Extended Euclidean Algorithm for Pairing Computation in RNS Representation Kota Morimoto, Daisuke Fujimoto, Saki Osuka (NAIST), Shinichi Kawamura, Tadanori Teruya (AIST), Yuichi hayashi (NAIST)  ISEC2021-10 SITE2021-4 BioX2021-11 HWS2021-10 ICSS2021-15 EMM2021-15 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (in English) | Pairing computation is an essential tool in advanced cryptography, and Yao et al. have shown that a hardware implementation using the RNS (Residue Number System) representation can achieve a fast implementation with a small circuit area. However, the bottleneck in the implementation of Yao et al. is the surplus multiplication in the inversion using Fermat’s Little Theorem, which can be further accelerated by eliminating this bottleneck. In order to accelerate this process, it is thought to be helpful to use BEEA (Binary Extended Euclidean Algorithm), which does not require multiplication for inversion. However, BEEA has not been adopted so far because of the high computational cost of sign detection in the RNS representation. On the other hand, a sign detection algorithm that can reduce the amount of calculation for sign detection has been proposed recently, and this algorithm is expected to accelerate the inversion using BEEA. In this paper, we investigate how to implement BEEA using an efficient sign detection algorithm based on the pairing calculation circuit of Yao et al. Specifically, we add inverters to the architecture of Yao et al. and apply the BEEA to reduce the cycle count required for the inversion. As a result, we confirmed that the cycle count of inversion required for pairing computation could be reduced by approximately 27% in the architecture of Yao et al. |
|
| Keyword | (in Japanese) | (See Japanese page) |
| (in English) | Binary Extended Euclidean Algorithm, Inversion, Pairing cryptography / Inversion / Pairing cryptography / RNS / / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 121, no. 121, HWS2021-10, pp. 1-7, July 2021. | |
| Paper # | HWS2021-10 | |
| Date of Issue | 2021-07-12 (ISEC, SITE, BioX, HWS, ICSS, EMM) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| Download PDF | ISEC2021-10 SITE2021-4 BioX2021-11 HWS2021-10 ICSS2021-15 EMM2021-15 |
|
| Conference Information | |
| Committee | BioX ISEC SITE ICSS EMM HWS IPSJ-CSEC IPSJ-SPT |
| Conference Date | 2021-07-19 - 2021-07-20 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Paper Information | |
| Registration To | HWS |
| Conference Code | 2021-07-BioX-ISEC-SITE-ICSS-EMM-HWS-CSEC-SPT |
| Language | Japanese |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Fundamental Study on Acceleration of Inversion using Binary Extended Euclidean Algorithm for Pairing Computation in RNS Representation |
| Sub Title (in English) | |
| Keyword(1) | Binary Extended Euclidean Algorithm, Inversion, Pairing cryptography |
| Keyword(2) | Inversion |
| Keyword(3) | Pairing cryptography |
| Keyword(4) | RNS |
| Keyword(5) | |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 1st Author's Name | Kota Morimoto |
| 1st Author's Affiliation | Nara Institute of Science and Technology (NAIST) |
| 2nd Author's Name | Daisuke Fujimoto |
| 2nd Author's Affiliation | Nara Institute of Science and Technology (NAIST) |
| 3rd Author's Name | Saki Osuka |
| 3rd Author's Affiliation | Nara Institute of Science and Technology (NAIST) |
| 4th Author's Name | Shinichi Kawamura |
| 4th Author's Affiliation | National Institute of Advanced Industrial Science and Technology (AIST) |
| 5th Author's Name | Tadanori Teruya |
| 5th Author's Affiliation | National Institute of Advanced Industrial Science and Technology (AIST) |
| 6th Author's Name | Yuichi hayashi |
| 6th Author's Affiliation | Nara Institute of Science and Technology (NAIST) |
| Speaker | Author-1 |
| Date Time | 2021-07-19 13:30:00 |
| Presentation Time | 25 minutes |
| Registration for | HWS |
| Paper # | ISEC2021-10, SITE2021-4, BioX2021-11, HWS2021-10, ICSS2021-15, EMM2021-15 |
| Volume (vol) | vol.121 |
| Number (no) | no.118(ISEC), no.119(SITE), no.120(BioX), no.121(HWS), no.122(ICSS), no.123(EMM) |
| Page | pp.1-7 |
| #Pages | 7 |
| Date of Issue | 2021-07-12 (ISEC, SITE, BioX, HWS, ICSS, EMM) |
[Return to Top Page]