Implementation of bit-vector variables in a CP solver, with an application to the generation of cryptographic S-boxes
Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
We present a bit-vector variable implementation for the constraint programming (CP) solver Gecode and its application to the problem of finding high-quality cryptographic substitution boxes (S-boxes).
S-boxes are a component in some cryptographic protocols, for example DES, which are critical to the strength of the entire system. S-boxes are arrays of bit-vectors, where each bit-vector is itself an array of bits.The desirable properties of an S-box can be described as relationships between its constituent bit-vectors.
We represent substitution boxes as arrays of bit-vector variables in Gecode in order to leverage CP techniques for finding high-quality S-boxes. In a CP solver, bit-vectors can alternatively be represented as sets or as arrays of Boolean variables. Experimental evaluation indicates that modeling substitution boxes with bit-vector variables is an improvement over both set- and Boolean-based models.
We additionally correct an error in previous work which invalidates the main experimental result, extend a heuristic for evaluating S-box quality, present two symmetries for substitution boxes, define several generic bit-vector propagators, and define propagators for the S-2 and S-7 DES design criteria.
Place, publisher, year, edition, pages
IT, 14 063
Engineering and Technology
IdentifiersURN: urn:nbn:se:uu:diva-235772OAI: oai:DiVA.org:uu-235772DiVA: diva2:761927
Master Programme in Computer Science
Flener, PierreChristoff, Ivan