Multi-exponentiation algorithm based on binary GCD computation and its application to side-channel countermeasure
A series of algorithms for evaluation of multi-exponentiation are proposed based on the binary greatest common divisor algorithm. The proposed algorithms are inversion free and have the capability to evaluate double or multi-exponentiation with non-fixed base numbers and exponents. They can also be...
| Autores principales: | , , |
|---|---|
| Otros Autores: | |
| Formato: | Journal Article |
| Lenguaje: | English |
| Publicado: |
2014
|
| Materias: | |
| Acceso en línea: | https://hdl.handle.net/10356/100160 http://hdl.handle.net/10220/24096 |
| _version_ | 1826120036317659136 |
|---|---|
| author | Yen, Sung-Ming Chen, Chien-Ning Moon, SangJae |
| author2 | Temasek Laboratories |
| author_facet | Temasek Laboratories Yen, Sung-Ming Chen, Chien-Ning Moon, SangJae |
| author_sort | Yen, Sung-Ming |
| collection | NTU |
| description | A series of algorithms for evaluation of multi-exponentiation are proposed based on the binary greatest common divisor algorithm. The proposed algorithms are inversion free and have the capability to evaluate double or multi-exponentiation with non-fixed base numbers and exponents. They can also be employed in developing side-channel countermeasures. For n-bit double and triple exponentiation, they achieve the average complexity of 1.53n and 1.75n multiplications (including squarings), respectively. The proposed algorithms can be very useful for the implementation of many public-key cryptosystems on small devices with limited memory space, e.g., smart cards. |
| first_indexed | 2024-10-01T05:09:57Z |
| format | Journal Article |
| id | ntu-10356/100160 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T05:09:57Z |
| publishDate | 2014 |
| record_format | dspace |
| spelling | ntu-10356/1001602020-03-07T12:47:21Z Multi-exponentiation algorithm based on binary GCD computation and its application to side-channel countermeasure Yen, Sung-Ming Chen, Chien-Ning Moon, SangJae Temasek Laboratories DRNTU::Science::Mathematics::Discrete mathematics::Algorithms A series of algorithms for evaluation of multi-exponentiation are proposed based on the binary greatest common divisor algorithm. The proposed algorithms are inversion free and have the capability to evaluate double or multi-exponentiation with non-fixed base numbers and exponents. They can also be employed in developing side-channel countermeasures. For n-bit double and triple exponentiation, they achieve the average complexity of 1.53n and 1.75n multiplications (including squarings), respectively. The proposed algorithms can be very useful for the implementation of many public-key cryptosystems on small devices with limited memory space, e.g., smart cards. 2014-10-21T07:30:40Z 2019-12-06T20:17:37Z 2014-10-21T07:30:40Z 2019-12-06T20:17:37Z 2012 2012 Journal Article Yen, S.-M., Chen, C.-N., & Moon, S. (2012). Multi-exponentiation algorithm based on binary GCD computation and its application to side-channel countermeasure. Journal of cryptographic engineering, 2(2), 99-110. https://hdl.handle.net/10356/100160 http://hdl.handle.net/10220/24096 10.1007/s13389-012-0032-4 167125 en Journal of cryptographic engineering © 2012 Springer-Verlag. |
| spellingShingle | DRNTU::Science::Mathematics::Discrete mathematics::Algorithms Yen, Sung-Ming Chen, Chien-Ning Moon, SangJae Multi-exponentiation algorithm based on binary GCD computation and its application to side-channel countermeasure |
| title | Multi-exponentiation algorithm based on binary GCD computation and its application to side-channel countermeasure |
| title_full | Multi-exponentiation algorithm based on binary GCD computation and its application to side-channel countermeasure |
| title_fullStr | Multi-exponentiation algorithm based on binary GCD computation and its application to side-channel countermeasure |
| title_full_unstemmed | Multi-exponentiation algorithm based on binary GCD computation and its application to side-channel countermeasure |
| title_short | Multi-exponentiation algorithm based on binary GCD computation and its application to side-channel countermeasure |
| title_sort | multi exponentiation algorithm based on binary gcd computation and its application to side channel countermeasure |
| topic | DRNTU::Science::Mathematics::Discrete mathematics::Algorithms |
| url | https://hdl.handle.net/10356/100160 http://hdl.handle.net/10220/24096 |
| work_keys_str_mv | AT yensungming multiexponentiationalgorithmbasedonbinarygcdcomputationanditsapplicationtosidechannelcountermeasure AT chenchienning multiexponentiationalgorithmbasedonbinarygcdcomputationanditsapplicationtosidechannelcountermeasure AT moonsangjae multiexponentiationalgorithmbasedonbinarygcdcomputationanditsapplicationtosidechannelcountermeasure |