CWI Cryptology Group

Abstract: Secret sharing is a fundamental primitive in cryptography. In this talk, I consider the problem of reconstructing a shared secret in the presence of faulty shares, with unconditional security. We require that any t shares give no information on the shared secret, and reconstruction is possible even if up to t out of the n shares are incorrect. The interesting setting is n/3

Abstract: We study the power of multi-linear secret-sharing schemes. On the one hand, we prove that ideal multi-linear secret-sharing schemes, in which the secret is composed of p field elements, are more powerful than schemes in which the secret is composed of less than p field elements (for every prime p). On the other hand, we prove super-polynomial lower bounds on the share size in multi-linear secret-sharing schemes. Previously, such lower bounds were known only for linear schemes.
This is joint work with Amos Beimel, Carles Padro, and Ilya Tyomkin

Abstract: Algebraic manipulation detection (AMD) codes, introduced at EUROCRYPT 2008, may, in some sense, be viewed as {\em keyless} combinatorial authentication codes that provide security in the presence of an {\em oblivious}, {\em algebraic} attacker. Its original applications included robust fuzzy extractors, secure message transmission and robust secret sharing. In recent years, however, a rather diverse array of additional applications in cryptography has emerged. In this paper we consider, for the first time, the natural regime of arbitrary positive constant error probability $\epsilon$ in combination with messages of unbounded binary length $\ell$. Adapting a known bound to this regime, it follows that the binary length $\rho$ of the tag satisfies $\rho \geq \log \ell + \Omega_{\epsilon}(1)$. We shall call AMD codes meeting this lower bound {\em optimal}. Owing to our refinement of the mathematical perspective on AMD codes, which focuses on symmetries of codes, we propose novel constructive principles. Our main result is an efficient randomized construction of optimal AMD codes based on a careful adaptation of certain asymptotically good quasi-cyclic codes.
Joint work with Carles Padr{\o'} and Chaoping Xing.

Abstract: Non-malleable codes (Dziembowski et al., ICS 2010) encode a message in such a way that the decoded value corresponding to a modified codeword (w.r.t. some class of modifications) is either the original encoded value or a completely independent one. Compared to error correction/detection, non-malleability is a weaker guarantee that can be achieved for much richer classes of modifications. In this talk I will survey recent results on the construction of non-malleable codes, both in the computational and in the information theoretic setting. In the last part of the talk I will focus on applications relevant for the field of cryptography, mainly in the context of tamper resistance and chosen-ciphertext security.