Search

In 2022, Olivier Longuet, a French mathematics teacher, created a game called the \textit{calissons puzzle}. Given a triangular grid in a hexagon and some given edges of the grid, the problem is to find a calisson tiling such that no input edge is overlapped and calissons adjacent to an input edge have different orientations. We extend the puzzle to regions $R$ that are not necessarily hexagonal. The first interesting property of this puzzle is that, unlike the usual calisson or domino problems, it is solved neither by a maximal matching algorithm, nor by Thurston's algorithm. This raises the question of its complexity. We prove that if the region $R$ is finite and simply connected, then the puzzle can be solved by an algorithm that we call the \textit{advancing surface algorithm} and whose complexity is $O(|\partial R|^3)$ where $\partial R|$ is the size of the boundary of the region $R$. In the case where the region is the entire infinite triangular grid, we prove that the existence of a solution can be solved with an algorithm of complexity $O(|X|^3)$ where $X$ is the set of input edges. To prove these theorems, we revisit William Thurston's results on the calisson tilability of a region $R$. The solutions involve equivalence between calisson tilings, stepped surfaces and certain DAG cuts that avoid passing through a set of edges that we call \textit{unbreakable}. It allows us to generalize Thurston's theorem characterizing tilable regions by rewriting it in terms of descending paths or absorbing cycles. Thurston's algorithm appears as a distance calculation algorithm following Dijkstra's paradigm. The introduction of a set $X$ of interior edges introduces negative weights that force a Bellman-Ford strategy to be preferred. These results extend Thurston's legacy by using computer science structures and algorithms., Comment: 26 pages, 20 figures

CG:SHOP is an annual geometric optimization challenge and the 2022 edition proposed the problem of coloring a certain geometric graph defined by line segments. Surprisingly, the top three teams used the same technique, called conflict optimization. This technique has been introduced in the 2021 edition of the challenge, to solve a coordinated motion planning problem. In this paper, we present the technique in the more general framework of binary constraint satisfaction problems (binary CSP). Then, the top three teams describe their different implementations of the same underlying strategy. We evaluate the performance of those implementations to vertex color not only geometric graphs, but also other types of graphs., Comment: To appear at ACM Journal of Experimental Algorithmics

Biometric recognition encompasses two operating modes. The first one is biometric identification which consists in determining the identity of an individual based on her biometrics and requires browsing the entire database (i.e., a 1:N search). The other one is biometric authentication which corresponds to verifying claimed biometrics of an individual (i.e., a 1:1 search) to authenticate her, or grant her access to some services. The matching process is based on the similarities between a fresh and an enrolled biometric template. Considering the case of binary templates, we investigate how a highly populated database yields near-collisions, impacting the security of both the operating modes. Insight into the security of binary templates is given by establishing a lower bound on the size of templates and an upper bound on the size of a template database depending on security parameters. We provide efficient algorithms for partitioning a leaked template database in order to improve the generation of a master-template-set that can impersonates any enrolled user and possibly some future users. Practical impacts of proposed algorithms are finally emphasized with experimental studies.

Cancelable biometric schemes aim at generating secure biometric templates by combining user specific tokens, such as password, stored secret or salt, along with biometric data. This type of transformation is constructed as a composition of a biometric transformation with a feature extraction algorithm. The security requirements of cancelable biometric schemes concern the irreversibility, unlinkability and revocability of templates, without losing in accuracy of comparison. While several schemes were recently attacked regarding these requirements, full reversibility of such a composition in order to produce colliding biometric characteristics, and specifically presentation attacks, were never demonstrated to the best of our knowledge. In this paper, we formalize these attacks for a traditional cancelable scheme with the help of integer linear programming (ILP) and quadratically constrained quadratic programming (QCQP). Solving these optimization problems allows an adversary to slightly alter its fingerprint image in order to impersonate any individual. Moreover, in an even more severe scenario, it is possible to simultaneously impersonate several individuals., Comment: arXiv admin note: text overlap with arXiv:1910.01389 by other authors

This paper describes the heuristics used by the Shadoks team for the CG:SHOP 2021 challenge. This year's problem is to coordinate the motion of multiple robots in order to reach their targets without collisions and minimizing the makespan. It is a classical multi agent path finding problem with the specificity that the instances are highly dense in an unbounded grid. Using the heuristics outlined in this paper, our team won first place with the best solution to 202 out of 203 instances and optimal solutions to at least 105 of them. The main ingredients include several different strategies to compute initial solutions coupled with a heuristic called Conflict Optimizer to reduce the makespan of existing solutions., Comment: Journal version to appear on ACM Journal on Algorithmics

In Conspiracy Santa, a variant of Secret Santa, a group of people offer each other Christmas gifts, where each member of the group receives a gift from the other members of the group. To that end, the members of the group form conspiracies, to decide on appropriate gifts, and usually divide the cost of each gift among all participants of that conspiracy. This requires to settle the shared expenses per conspiracy, so Conspiracy Santa can actually be seen as an aggregation of several shared expenses problems. First, we show that the problem of finding a minimal number of transaction when settling shared expenses is NP-complete. Still, there exist good greedy approximations. Second, we present a greedy distributed secure solution to Conspiracy Santa. This solution allows a group of n people to share the expenses for the gifts in such a way that no participant learns the price of his gift, but at the same time notably reduces the number of transactions to 2 $\times$ n + 1 with respect to a na{\"i}ve aggregation of n $\times$ (n -- 2). Furthermore, our solution does not require a trusted third party, and can either be implemented physically (the participants are in the same room and exchange money using envelopes) or, over Internet, using a cryptocurrency.

In 1968, Liu described the problem of securing documents in a shared secret project. In an example, at least six out of eleven participating scientists need to be present to open the lock securing the secret documents. Shamir proposed a mathematical solution to this physical problem in 1979, by designing an efficient $k$-out-of-$n$ secret sharing scheme based on Lagrange's interpolation. Liu and Shamir also claimed that the minimal solution using physical locks is clearly impractical and exponential in the number of participants. In this paper we relax some implicit assumptions in their claim and propose an optimal physical solution to the problem of Liu that uses physical padlocks, but the number of padlocks is not greater than the number of participants. Then, we show that no device can do better for $k$-out-of-$n$ threshold padlock systems as soon as $k\geq{\sqrt{2n}}$, which holds true in particular for Liu's example. More generally, we derive bounds required to implement any threshold system and prove a lower bound of $\mathcal{O}{\log(n)}$ padlocks for any threshold larger than $2$. For instance we propose an optimal scheme reaching that bound for $2$-out-of-$n$ threshold systems and requiring less than $2\log_2(n)$ padlocks. We also discuss more complex access structures, a wrapping technique, and other sublinear realizations like an algorithm to generate $3$-out-of-$n$ systems with $2.5\sqrt{n}$ padlocks. Finally we give an algorithm building $k$-out-of-$n$ threshold padlock systems with only $\mathcal{O}{\log(n)^{k-1}}$ padlocks. Apart from the physical world, our results also show that it is possible to implement secret sharing over small fields.

We deal with a set of autonomous robots moving on an infinite grid. Those robots are opaque, have limited visibility capabilities, and run using synchronous Look-Compute-Move cycles. They all agree on a common chirality, but have no global compass. Finally, they may use lights of different colors, but except from that, robots have neither persistent memories, nor communication mean. We consider the infinite grid exploration (IGE) problem. For this problem we give two impossibility results and three algorithms, including one which is optimal in terms of number of robots. In more detail, we first show that two robots are not sufficient in our settings to solve the problem, even when robots have a common coordinate system. We then show that if the robots' coordinate systems are not self-consistent, three or four robots are not sufficient to solve the problem. Finally, we present three algorithms that solve the IGE problem in various settings. The first algorithm uses six robots with constant colors and a visibility range of one. The second one uses the minimum number of robots, i.e., five, as well as five modifiable colors, still under visibility one. The last algorithm requires seven oblivious anonymous robots, yet assuming visibility two. Notice that the two last algorithms also satisfy achieve exclusiveness., Comment: 22 pages

This paper deals with distributed matrix multiplication. Each player owns only one row of both matrices and wishes to learn about one distinct row of the product matrix, without revealing its input to the other players. We first improve on a weighted average protocol, in order to securely compute a dot-product with a quadratic volume of communications and linear number of rounds. We also propose a protocol with five communication rounds, using a Paillier-like underlying homomorphic public key cryptosystem, which is secure in the semi-honest model or secure with high probability in the malicious adversary model. Using ProVerif, a cryptographic protocol verification tool, we are able to check the security of the protocol and provide a countermeasure for each attack found by the tool. We also give a randomization method to avoid collusion attacks. As an application, we show that this protocol enables a distributed and secure evaluation of trust relationships in a network, for a large class of trust evaluation schemes., Comment: Pierangela Samarati. SECRYPT 2016 : 13th International Conference on Security and Cryptography, Lisbonne, Portugal, 26--28 Juillet 2016. 2016