CWI Cryptology Group

Abstract: Given two (linear) codes C, D with the same length, their product CD is defined as the linear span of all componentwise products xy, with x in C, y in D. If C=D, C^2 is also called the square of the code C. Our interest in this notion is motivated by a number of cryptographic applications, such as error-correcting pairs, secret sharing and cryptanalysis of code-based cryptosystems. The first part of the talk will survey these applications.
Then we characterize Product-MDS pairs, i.e. pairs of codes C, D whose product has maximum-possible minimum distance. We prove in particular, for C=D, that if C^2 has minimum distance at least 2, and (C,C) is a Product-MDS pair, then either C is a Reed-Solomon code, or C is a direct sum of self-dual codes. In passing we establish coding-theoretic analogues of classical theorems of additive combinatorics.
This is a joint work with G. Zémor.

Abstract: With computation power in the cloud becoming a commodity, it is more and more convenient to outsource computations to external computation parties. Assuring confidentiality, even of inputs by mutually distrusting inputters, is possible by distributing computations between different parties using multiparty computation. Unfortunately, this typically only guarantees correctness if a limited number of computation parties are malicious. If correctness is needed when all computation parties are malicious, then one currently needs either fully homomorphic encryption or ``universally verifiable'' multiparty computation; both are impractical for large computations. In this work we show for the first time how to achieve practical privacy-friendly outsourcing with correctness guarantees, by using normal multiparty techniques to compute the result of a computation, and then using slower verifiable techniques only to verify that this result was correct. We demonstrate the feasibility of our approach in a linear programming case study.

Abstract: We present a novel method for constructing linear secret sharing schemes (LSSS) from linear error correcting codes and linear universal hash functions in a blackbox way. The main advantage of this new construction is that the privacy property of the resulting secret sharing scheme essentially becomes independent of the code we use, only depending on its rate. This allows us to fully harness the algorithmic properties of recent code constructions such as efficient encoding and decoding or efficient list-decoding. Choosing the error correcting codes and universal hash functions involved carefully, we obtain solutions to the following open problems: (1) A linear near-threshold secret sharing scheme with both linear time sharing and reconstruction algorithms and large secrets (i.e. secrets of size Ω(n)). Thus, the computational overhead per shared bit in this scheme is constant. (2) An efficiently reconstructible robust secret sharing scheme for n/3 ≤ t ≤ (1-ε) n/2 corrupted players (for any constant ε > 0) with shares of optimal size O(1+λ/n) and secrets of size Ω(n+λ), where λ is the security parameter.
Joint work with R. Cramer, I. Damgård, S. Fehr, and G. Spini.