| Presentation | 2021-07-19 Fundamental Study on Acceleration of Inversion using Binary Extended Euclidean Algorithm for Pairing Computation in RNS Representation Kota Morimoto, Daisuke Fujimoto, Saki Osuka, Shinichi Kawamura, Tadanori Teruya, Yuichi hayashi, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(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) |
| Keyword(in English) | Binary Extended Euclidean Algorithm, Inversion, Pairing cryptography / Inversion / Pairing cryptography / RNS |
| Paper # | ISEC2021-10,SITE2021-4,BioX2021-11,HWS2021-10,ICSS2021-15,EMM2021-15 |
| Date of Issue | 2021-07-12 (ISEC, SITE, BioX, HWS, ICSS, EMM) |
| Conference Information | |
| Committee | BioX / ISEC / SITE / ICSS / EMM / HWS / IPSJ-CSEC / IPSJ-SPT |
|---|---|
| Conference Date | 2021/7/19(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Hitoshi Imaoka(NEC) / Tetsuya Izu(Fujitsu Labs.) / Masaru Ogawa(Kobe Gakuin Univ.) / Katsunari Yoshioka(Yokohama National Univ.) / Ryoichi Nishimura(NICT) / Yasuhisa Shimazaki(Renesas Electronics) |
| Vice Chair | Masatsugu Ichino(Univ. of Electro-Comm.) / Naoyuki Takada(SECOM) / Noboru Kunihiro(Tsukuba Univ.) / Goichiro Hanaoka(AIST) / Takushi Otani(Kibi International Univ.) / Takeo Tatsumi(Open Univ. of Japan) / Kazunori Kamiya(NTT) / Takahiro Kasama(NICT) / Masaaki Fujiyoshi(Tokyo Metropolitan Univ.) / Masatsugu Ichino(Univ. of Electro-Comm.) / Makoto Nagata(Kobe Univ.) / Daisuke Suzuki(Mitsubishi Electric) |
| Secretary | Masatsugu Ichino(KDDI Research) / Naoyuki Takada(MitsubishiElectric) / Noboru Kunihiro(Fujitsu Labs.) / Goichiro Hanaoka(Ibaraki Univ.) / Takushi Otani(Yamaguchi Pref Univ.) / Takeo Tatsumi(Hokuriku Univ.) / Kazunori Kamiya(KDDI labs.) / Takahiro Kasama(Okayama Univ.) / Masaaki Fujiyoshi(Utsunomiya Univ.) / Masatsugu Ichino(NICT) / Makoto Nagata(NTT) / Daisuke Suzuki(NAIST) |
| Assistant | Hiroyuki Suzuki(Gunma Univ) / Akihiro Hayasaka(NEC) / Takahiro Matsuda(AIST) / Hideyuki Fujii(NRI-Secure) / Yusuke Tachibana(Fukuoka Inst. of Tech.) / Keisuke Kito(Mitsubishi Electric) / Takeshi Sugawara(Univ. of Electro-Comm.) / Shoko Imaizumi(Chiba Univ.) / Youichi Takashima(Kaishi Professional Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Biometrics / Technical Committee on Information Security / Technical Committee on Social Implications of Technology and Information Ethics / Technical Committee on Information and Communication System Security / Technical Committee on Enriched MultiMedia / Technical Committee on Hardware Security / Special Interest Group on Computer Security / Special Interest Group on Security Psychology and Trust |
|---|---|
| Language | JPN |
| 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 |
| 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) |
| Date | 2021-07-19 |
| Paper # | ISEC2021-10,SITE2021-4,BioX2021-11,HWS2021-10,ICSS2021-15,EMM2021-15 |
| Volume (vol) | vol.121 |
| Number (no) | ISEC-118,SITE-119,BioX-120,HWS-121,ICSS-122,EMM-123 |
| Page | pp.pp.1-7(ISEC), pp.1-7(SITE), pp.1-7(BioX), pp.1-7(HWS), pp.1-7(ICSS), pp.1-7(EMM), |
| #Pages | 7 |
| Date of Issue | 2021-07-12 (ISEC, SITE, BioX, HWS, ICSS, EMM) |