Span Programs over Rings and How to Share a Secret from a Module

Serge Fehr

Master's thesis, ETH Zurich, Institute for Theoretical Computer Science, 1998.

Monotone span programs are a model of computation, based on linear algebra, for computing monotone functions. They also give rise to general-access- structure secret sharing over fields. We introduce and study the notion of extended span programs, which are span programs defined over a ring (instead of over a field), and show how this gives rise to general-access-structure secret sharing over rings and even over modules. As an application, we present a general-adversary distributed RSA signature scheme. We consider passive and active adversaries.

BibTeX Citation

@mastersthesis{Fehr98,
    author       = {Serge Fehr},
    title        = {Span Programs over Rings and How to Share a Secret from a Module},
    year         = 1998,
    address      = {Institute for Theoretical Computer Science},
    school       = {ETH Zurich},
}