Workshop on Mathematics of Information-Theoretic Cryptography

A workshop on Mathematics of Information-Theoretic Cryptography has been held this week in Leiden. The first morning started with a very interesting talk given by Amos Beimel on Multilinear Secret Sharing Schemes. He described a recent joint work with Aner Ben-Efraim, Carles Padro, and Ilya Tyomkin.   Multilinear secret sharing schemes (MSSS) can be seen as a generalization of  linear secret sharing schemes, in which  the secret is composed by some field elements instead of just one, and they are based on multi-target monotone span  program, a generalization of monotone span program. He showed, using representation of groups, that ideal multilinear p-schemes (in which the secret is composed of p field elements, for every prime p) are more powerful of ideal k-linear multilinear schemes for k<p.

The  talk  “Low Rank Parity Check Codes (LRPC) and their applications to cryptography”, by Gilles Zemor, was particularly appealing.  These codes can be seen as the equivalent of LDPC codes (Low Density Parity Check codes) for the rank metric. More precisely, a LRPC code of rank d, length n and dimension k over F_q^m,   is a code with parity  check matrix H, that is  an (n-k) x m matrix such that the subspace of F_q^m  generated by its coefficients has dimension at most d. He described how these codes can be used to define a  public key cryptosystem, with small keys and a poor structure, which is not based on the Gabidulin codes. Interestingly, as the more recent MDPC cryptosystem,  this construction can be seen as a  generalization of the NTRU cryptosystem, but with the rank metric.

The last talk of the day was given by Harald Niederreiter. He showed some applications of global function fields, i.e. algebraic function fields of one variable over a finite fields.

For me, the highlight of the third day was the talk given by Serge Fehr. He presented a joint work with Marco Tomamichel, Jedrzej Kaniewski, and Stephanie Wehner, that will be presented at Eurocrypt next week. During the talk he described a new quantum game (a monogamy-of-entangled-game) with various and important applications in cryptography. For example it is used to prove that standard BB84 QKD (Quantum Key Distribution) remains secure even when one party uses fully untrusted measurement devices.