The third talk of the first day of the workshop "Is Cryptographic Theory Practically Relevant?" was given by David Naccache (a video of the talk is available online). In his abstract, he noted that the talk was intended for people bored by 'random oracles, lattices, security reductions and games'. As described by the title, the problems he discussed were not directly related to cryptography, but rather nice mathematical problems that arose from a number of practical security problems.
The first problem had to do with the depiction of data on radar charts. The point was to rearrange the axes of the chart to maximize the area depicting the attributes of ones employer, while minimizing the area depicting the attributes of their competitors. This problem was probably the least related to security, but a general theme throughout his talk was that many mathematical problems are interesting; you just need to convince people to give you funding for looking at them.
The second problem was related to physically protecting electronic devices or chips from tampering by embedding them in a 3D mesh of metal. This lead to the study of random Hamiltonian cycles in 3-dimensional planar graphs of a cube-like structure. The goal was to end up with a 'cage' with has the device embedded in the center, such that it is hard to drill towards the device. However, due to the particular structure of the graph, a single cage would always leave regularly spaced holes in between the edges. Fortunately, it is possible to interleave a smaller cage inside the bigger cage, thus neatly filling up the holes. These cages were constructed taking a regular Hamiltonian cycle in the graph and then transforming them randomly to get rid of the regular structure.
David went on to talk about the third problem, which arose from the probing of chips. It is possible to probe chips with special machines, in order to analyze what exactly happens on these chips. To somehow defend against this, David and his students looked at the problem of physically 'scattering' a secret on the chip, thus maximizing the physical distance between parts (such as shares from secret sharing). The chip was modeled as an n by n chessboard and the shares of different secrets were modeled as colored pawns. You have pawns of n colors and must place them on the board such that pawns of the same color are as far from each other as possible. This problem turned out to be related to the mathematical theory of tiling. David noted that the solutions obtained would always be periodic, which might be undesirable from a security point of view. Thus, some care must be taken to make periodic solutions non-periodic, which possible reduces the distances between pawns of the same color slightly. As someone in the audience pointed out, it is possible to extend this model by adding colorless pawns to model unimportant information that does not need to be scattered.
At this point, David was running out of time and offered to take questions. However, his next subject was titled "How to identify quickly" and the audience encouraged him to use the remaining two minutes to show how quickly one could identify. He used these last few minutes to describe how to speed up comparisons of a biometric scan to a database of biometric data for identification purposes. The trick was to add additional data such as the person's height and then sort the database entries by the distance from the measured height to the recorded heights. This could be extended to several types of data (he gave height and IQ as examples because they were independent) but this might require some extra statistics to remove dependence between these attributes. Unfortunately, he really was out of time at this point and did not get to talk about other problems that he had prepared. More information can be found once his slides become available, but he said that if people were interested in these problems they should send him an email as well.
No comments:
Post a Comment