CWI Cryptology Group

Abstract: Capacity theory originated in the study of how electrical charges distribute themselves in order to to minimize energy. In this talk I will give an overview of connections between this subject and number theory.

Abstract: The notion of computing in the presence of an adversary which controls or gets access to parts of the system is at the heart of modern cryptography. In such a setting, however, the "corruption" of a party has been viewed as a simple, uniform and atomic operation, where the adversary decides to get control over a party and this party immediately gets corrupted. In this work, motivated by the fact that different parties may require different resources to get corrupted, we put forth the notion of *resource-based corruptions*, where the adversary must invest some resources in order to do so.
If the adversary has full information about the system configuration then resource-based corruptions would provide no fundamental difference from the standard corruption model. However, in a resource "anonymous" setting, in the sense that such configuration is hidden from the adversary, much is to be gained in terms of efficiency and security.
We showcase the power of such "hidden diversity" in the context of the popular paradigm known as "secure multiparty computation" (MPC) with resource-based corruptions, and prove that it can effectively be used to circumvent known impossibility results. For example, if OPT is the corruption budget that violates the completeness of MPC (the case when half or more of the players are corrupted), we show that if hidden diversity is available, the completeness of MPC can be made to hold against an adversary with as much as a B*OPT budget, for any constant B > 1. Regarding efficiency gains, we show that hidden diversity can be used to force the corruption threshold to drop from 1/2 to 1/3, in turn allowing the use of much more efficient (information-theoretic) MPC protocols.
We achieve the above through a series of technical contributions, including:
1) The formulation of the notion of *inversion effort preserving* (IEP) functions which is a type of direct-sum property, and the property of *hardness indistinguishability*. While hardness indistinguishability enables the dissociation of parties' identities and the resources needed to corrupt them, IEP enables the discretization of adversarial work into corruption "tokens," leading to
2) the abstraction of the corruption game as a combinatorial problem and its analysis.
This is joint work with David Johnson (AT&T Labs), Aggelos Kiayias (U. of Athens) and Moti Yung (Google).

Abstract: The three families of Deligne-Lusztig curves arise in connection with representations of the algebraic groups 2A2 (unitary group), 2B2 (Suzuki group) and 2G2 (Ree group). From their abstract definition it is clear that in principle the curves are suitable for constructing long error-correcting codes or secret sharing schemes with many participants. We describe the following results from the April 2013 thesis of Abdulla Eid: A smooth model for the Ree curve, the determination of the Weierstrass semigroup at a rational point, and its application to curve-based secret sharing.

Abstract: The Ihara limit (or -constant) has been a central problem of study in the asymptotic theory of global function fields (or equivalently, algebraic curves over finite fields). It addresses global function fields with many rational points and so far, most applications of this theory do not require additional properties. Motivated by recent applications, we require global function fields with the additional property that their zero class divisor groups contain at most a small number of torsion points. We capture this by the torsion limit, a new asymptotic quantity for global function fields. It seems that it is even harder to determine values of this new quantity than the Ihara constant. In this talk, we survey some recent progress on this topic.
(This is a joint work with Ignacio Cascudo and Ronald Cramer)