ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

Efficient Construction of the Dual Span Program

Serge Fehr

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.