uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Implementation of bit-vector variables in a CP solver, with an application to the generation of cryptographic S-boxes
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology.
2014 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

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
National Category
Engineering and Technology
URN: urn:nbn:se:uu:diva-235772OAI: oai:DiVA.org:uu-235772DiVA: diva2:761927
Educational program
Master Programme in Computer Science
Available from: 2014-11-10 Created: 2014-11-10 Last updated: 2014-11-10Bibliographically approved

Open Access in DiVA

fulltext(755 kB)170 downloads
File information
File name FULLTEXT01.pdfFile size 755 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Department of Information Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 170 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 491 hits
ReferencesLink to record
Permanent link

Direct link