Efficient Construction of the Dual Span Program
Serge Fehr
Manuscript, May 1999.
We consider monotone span programs as a tool for representing, we will say computing, general access structures. It is known that if an access structure is computed by a monotone span program, then the dual access structure is computed by a monotone span program of the same size. We will strengthen this result by proving that such an span program not only exists, but can be efficiently computed.
BibTeX Citation
@misc{Fehr99,
author = {Serge Fehr},
title = {Efficient Construction of the Dual Span Program},
year = {1999},
month = {5},
howpublished = {Manuscript},
}