Lehrstuhl Mathematik & InformatikPerfect Reconstruction of Black Pixels Revisited
Abstract. It has been shown recently by Koga and Ueda that a visual secret sharing scheme proposed Blundo, De Bonis, and De Santis leads to the largest possible visual contrast among all schemes that perfectly reconstruct black pixels. The main purpose of this paper is to demonstrate that the largest optimal contrast (for this kind of schemes) equals the smallest possible error when we try to approximate a polynomial of degree $k$ on $k+1$ interpolation points by a polynomial of degree $k-1$. Thus, the problem of finding a contrast-optimal scheme with perfect reconstruction of black pixels boils down to a well-known problem (with a well-known solution) in Approximation Theory. A second purpose of this paper is to present a tight asymptotic analysis for the contrast parameter. Furthermore, the connection between visual cryptography and approximation theory discussed in this paper (partially known before) may also find some interest in its own right.