Paper 2016/664

Efficient Conversion Method from Arithmetic to Boolean Masking in Constrained Devices

Yoo-Seung Won and Dong-Guk Han

Abstract

A common technique employed for preventing a side channel analysis is boolean masking. However, the application of this scheme is not so straightforward when it comes to block ciphers based on Addition-Rotation-Xor structure. In order to address this issue, since 2000, scholars have investigated schemes for converting Arithmetic to Boolean (AtoB) masking and Boolean to Arithmetic (BtoA) masking schemes. However, these solutions have certain limitations. The time performance of the AtoB scheme is extremely unsatisfactory because of the high complexity of $\mathcal{O}(k)$ where $k$ is the size of addition bit. At the FSE 2015, an improved algorithm with time complexity $\mathcal{O}(\log k)$ based on the Kogge-Stone carry look-ahead adder was suggested. Despite its efficiency, this algorithm cannot consider for constrained environments. Although the original algorithm naturally extends to low-resource devices, there is no advantage in time performance; we call this variant as the generic variant. In this study, we suggest an enhanced variant algorithm to apply to constrained devices. Our solution is based on the principle of the Kogge-Stone carry look-ahead adder, and it uses a divide and conquer approach. In addition, we prove the security of our new algorithm against first-order attack. In implementation results, when $k=64$ and the register bit size of a chip is $8$, $16$ or $32$, we obtain $58$\%, $72$\%, or $68$\% improvement, respectively, over the results obtained using the generic variant. When applying those algorithms to first-order SPECK, we also achieve about $40$\% improvement. Moreover, our proposal extends to higher-order countermeasures as previous study.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Arithmetic to Boolean maskingKogge-Stone carry look-ahead adderARX-based cryptographic algorithm
Contact author(s)
mathwys87 @ kookmin ac kr
History
2016-07-01: received
Short URL
https://ia.cr/2016/664
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/664,
      author = {Yoo-Seung Won and Dong-Guk Han},
      title = {Efficient Conversion Method from Arithmetic to Boolean Masking in Constrained Devices},
      howpublished = {Cryptology ePrint Archive, Paper 2016/664},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/664}},
      url = {https://eprint.iacr.org/2016/664}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.