Conversion from Arithmetic to Boolean Masking with Logarithmic Complexity

Coron, Jean-Sébastien; Groszschädl, Johann; Tibouchi, Mehdi; Vadnala, Praveen Kumar

doi:10.1007/978-3-662-48116-5_7

Reference : Conversion from Arithmetic to Boolean Masking with Logarithmic Complexity


	Document type :	Scientific congresses, symposiums and conference proceedings : Paper published in a book
	Discipline(s) :	Engineering, computing & technology : Computer science
	To cite this reference:	http://hdl.handle.net/10993/25599

Title :	Conversion from Arithmetic to Boolean Masking with Logarithmic Complexity
Language :	English
Author, co-author :	Coron, Jean-Sébastien [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
	Groszschädl, Johann [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
	Tibouchi, Mehdi [NTT Secure Platform Laboratories > Okamoto Research Laboratory]
	Vadnala, Praveen Kumar [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Publication date :	Mar-2015
Main document title :	Fast Software Encryption, 22nd International Workshop, FSE 2015, Istanbul, Turkey, March 8-11, 2015, Revised Selected Papers
Editor :	Leander, Gregor
Publisher :	Springer Verlag
Collection and collection volume :	Lecture Notes in Computer Science, volume 9054
Pages :	130-149
Peer reviewed :	Yes
Audience :	International
ISBN :	978-3-662-48115-8
Event name :	22nd International Workshop on Fast Software Encryption (FSE 2015)
Event date :	from 09-03-2015 to 11-03-2105
Event place (city) :	Istanbul
Event country :	Turkey
Keywords :	[en] Symmetric Cryptography ; Differential Power Analysis (DPA) ; DPA Countermeasures ; Arithmetic Masking ; Boolean Masking
Abstract :	[en] A general technique to protect a cryptographic algorithm against side-channel attacks consists in masking all intermediate variables with a random value. For cryptographic algorithms combining Boolean operations with arithmetic operations, one must then perform conversions between Boolean masking and arithmetic masking. At CHES 2001, Goubin described a very elegant algorithm for converting from Boolean masking to arithmetic masking, with only a constant number of operations. Goubin also described an algorithm for converting from arithmetic to Boolean masking, but with O(k) operations where k is the addition bit size. In this paper we describe an improved algorithm with time complexity O(log k) only. Our new algorithm is based on the Kogge-Stone carry look-ahead adder, which computes the carry signal in O(log k) instead of O(k) for the classical ripple carry adder. We also describe an algorithm for performing arithmetic addition modulo 2^k directly on Boolean shares, with the same complexity O(log k) instead of O(k). We prove the security of our new algorithm against first-order attacks. Our algorithm performs well in practice, as for k=64 we obtain a 23% improvement compared to Goubin’s algorithm.
Permalink :	http://hdl.handle.net/10993/25599
DOI :	10.1007/978-3-662-48116-5_7
Other URL :	http://link.springer.com/chapter/10.1007/978-3-662-48116-5_7

File(s) associated to this reference

Fulltext file(s):

	File	Commentary	Version	Size	Access
Limited access	FSE2015.pdf		Author postprint	9.14 kB	Request a copy

All documents in ORBi^lu are protected by a user license.

University of Luxembourg Library | Feedback | Legal notices