Span Programs over Rings and How to Share a Secret from a Module
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.