Exploiting the Homomorphic Property of Visual Cryptography

Introduction

Secret sharing encrypts the user data into different secret shadows (also called shares or shadow images) and distributes them to multiple participants, which has attracted more attention of scientist and engineers. Shamir’s polynomial-based scheme (Li, Ma, Su & Yang, 2012; Li, Yang, Wu, Kong & Ma, 2013; Lin et al., 2007; Shamir, 1979; Thien & Lin, 2002; Yang & Ciou, 2010) and visual cryptographic scheme (VCS) (Naor et al., 1994; Tuyls et al., 2005; Wang et al., 2007, Wang, Arce, & Di, 2009, Weir & Yan, 2010; Yan et al., 2014), are the primary branches in secret sharing. A (k,n) threshold secret sharing scheme was first proposed by Shamir (1979) through encrypting the secret into the constant coefficient of a random (k -1)-degree polynomial. The secret image can be perfectly reconstructed using Lagrange’s interpolation. Inspired by Shamir’s scheme, Thien and Lin (2002) reduced share size 1/k times to the secret image utilizing all coefficients of the polynomial for embedding secret. The advantage of Shamir’s polynomial-based schemes (Li, Ma, Su & Yang, 2012; Li, Yang, Wu, Kong & Ma, 2013; Lin et al., 2007; Shamir, 1979; Thien & Lin, 2002; Yang & Ciou, 2010) is that, the secret image can be recovered losslessly. Although Shamir’s polynomial-based schemes only need k shares for reconstructing the distortion-less secret image, it requires more complicated computations, i.e., Lagrange interpolations, for decoding. The limitation makes it useless without computational device and unsuitable for light-weight devices, such as, mobile phone, smart device and so on.

Naor and Shamir [14] first proposed the threshold-based VCS. In their scheme, a secret image is generated into n random shares which separately reveals nothing about the secret other than the secret size. The n shares are then printed onto transparencies and distributed to n associated participants. The secret image can be visually revealed based on human visual system (HVS) and probability by stacking any k or more shares, while less than k shares give no clue about the secret, even if infinite computational power is available.

Unfortunately, traditional VCS has the limitation of the pixel expansion 错误!未找到引用源. The pixel expansion will increase storage and transmission bandwidth. In order to remove the pixel expansion, probabilistic VCSs (Cimato, 2006; Ryo et al., 1999; Yang, 2004) and random grids (RG)-based VCSs (Chen & Tsao, 2013; Guo et al., 2013; Kafri & Keren, 1987; Shyu, 2007; Weir & Yan, 2010; Wu & Sun, 2013) were proposed. Main properties of VCS are simple recovery method and the alternative order of the shadow images. Simply reconstructed method means that the decryption of secret image is light-weighted or completely based on HVS without any cryptographic computation.

On the other hand, recently, rapid technological developments in areas such as cloud computing, online applications, social networking, and distributed processing have raised important concerns about the security (privacy) of user-related content (Lagendijk et al., 2013).

Traditional cryptographic technologies aim to protect data, but fail if the processor itself is untrusted (Lagendijk et al., 2013). In providing a service that needs personal information, the service provider may gain a lot about a user’s past behavior, preferences, and biometrics. On the one hand, in order to use the service, the user must trust the service provider requiring his personal data. On the other hand, the service provider may be untrusted. Thus, the use of personal information becomes more varied with more flexibility in presentation and processing.