Distinguished Papers

Best Application Paper

The Design of Cryptographic S-Boxes Using CSPs

Venkatesh Ramamoorthy, Marius Silaghi, Toshihiro Matsui, Katsutoshi Hirayama and Makoto Yokoo

Abstract

We use the Constraint Satisfaction Problem (CSP) framework to model and solve the problem of designing substitution functions for substitution-permutation (SP) networks as proposed by Shannon for the architecture of ciphers. Many ciphers are designed using the SP pattern, and differ mainly by two parametrized functions: substitution and permutation. The most difficult of the two is the substitution function, which has to be nonlinear (a requirement that was difficult to define and quantify). Over time, researchers such as Nyberg, Pieprzyk and Matsui have proposed various metrics of nonlinearity that make the function robust to modern attacks. Before us, people have attempted various ways to design functions that respect these metrics. In the past people hand-picked substitution tables (S-boxes) by trying various values. Recently they use difficult to analyze constructs (such as Bent functions, spectral inversion, inverses in Galois fields) whose outputs are tested for nonlinearity. While efficient, such techniques are neither exhaustive (optimal), nor did they manage to generate better substitutions than the ones hand-picked in the past.

We show that Matsui's nonlinearity requirement can be naturally modelled using CSPs. Based on a combination of existing CSP techniques and some new filtering operators that we designed specially for the new types of constraints, we manage to obtain better S-boxes than any previously published ones. The simplicity of the CSP framework and availability of general CSP solvers like ours, makes it easy for more people to design their own ciphers with easy to understand security parameters. Here we report on this new application of CSPs.

Download: Presentation [pdf]

Runner-Up

Optimal Carpet Cutting

Andreas Schutt, Peter J. Stuckey and Andrew R. Verden

Abstract

In this paper we present a model for the carpet cutting problem in which carpet shapes are cut from a rectangular carpe troll with a fixed width and sufficiently long length. Our exact solution approaches decompose the problem into smaller parts and minimise the needed carpet roll length for each part separately. The customers requirements are to produce a cutting solution of a carpet within 3 minutes, in order to be usable during the quotation process for estimating the amount of carpet required. Our system can find and prove the optimal solution for 106 of the 150 real-work instances provided by the customer, and find high quality solutions to the remainder within this time limit. In contrast the existing solution developed some years ago finds (but does not prove) optimal solution for 30 instances. Our solutions reduces the wastage by more than 35% on average compared to the existing approach.

Download: Presentation [pdf]

Best Research Paper

On Minimal Constraint Networks

Georg Gottlob

Abstract

In a minimal binary constraint network, every tuple of a constraint relation can be extended to a solution. It was conjectured that computing a solution to such a network is NP hard. We prove this conjecture. We also prove a conjecture by Dechter and Pearl stating that for k >= 2 it is NP-hard to decide whether a constraint network can be decomposed into an equivalent k-ary constraint network, and study related questions.

Download: Presentation [pdf]

Best Student Paper

Octagonal Domains for Continuous Constraints

Marie Pelleau, Charlotte Truchet and Frederic Benhamou

Abstract

Domains in Continuous Constraint Programming (CP) are generally represented with intervals whose n-ary Cartesian product (box) approximates the solution space. This paper proposes a new representation for continuous variable domains based on octagons. We generalize local consistency and split to this octagon representation, and we propose an octagonal-based branch and prune algorithm. Preliminary experimental results show promising performance improvements on several classical benchmarks.

Download: Presentation [pdf]