Threshold Visual Cryptography Schemes with Specified Whiteness Levels of Reconstructed Pixels

In 1994, Naor and Shamir introduced an unconditionally secure method for encoding black and white images. This method, known as a threshold visual cryptography scheme (VCS), has the benefit of requiring no cryptographic computation on the part of the decoders. In a -VCS, a share, in the form of a transparency, is given to ">n users. Any ">k users can recover the secret simply by stacking transparencies, but ">k-1 users can gain no information about the secret whatsoever.In this paper, we first explore the issue of contrast, by demonstrating that the current definitions are inadequate, and by providing an alternative definition. This new definition motivates an examination of minimizing pixel expansion subject to fixing the VCS parameters ">h and ">l. New bounds on pixel expansion are introduced, and connections between these bounds are examined. The best bound presented is tighter than any previous bound. An analysis of connections between (2, ">n) schemes and designs such as BIBD's, PBD's, and (">r, )-designs is performed. Also, an integer linear program is provided whose solution exactly determines the minimum pixel expansion of a (2, ">n)-VCS with specified ">h and >l.     

A New Approach for Visual Cryptography

Visual cryptography is to encrypt a secret image into some shares (transparencies) such that any qualified subset of the shares can recover the secret visually. The conventional definition requires that the revealed secret images are always darker than the backgrounds. We observed that this is not necessary, in particular, for the textual images.In this paper, we proposed an improved definition for visual cryptography based on our observation, in which the revealed images may be darker or lighter than the backgrounds. We studied properties and obtained bounds for visual cryptography schemes based on the new definition. We proposed methods to construct visual cryptography schemes based on the new definition. The experiments showed that visual cryptography schemes based on our definition indeed have better pixel expansion in average.     

Optimal Colored Threshold Visual Cryptography Schemes

Visual cryptography schemes allow the encoding of a secret image into n shares which are distributed to the participants. The shares are such that only qualified subsets of participants can visually recover the secret image. Usually the secret image consist of black and white pixels. In colored threshold visual cryptography schemes the secret image is composed of pixels taken from a given set of c colors. The pixels expansion and the contrast of a scheme are two measures of the goodness of the scheme.In this paper, we study c-color (k,n)-threshold visual cryptography schemes and provide a characterization of contrast-optimal schemes. More specifically we prove that there exists a contrast-optimal scheme that is a member of a special set of schemes, which we call canonical schemes, and that satisfy strong symmetry properties.Then we use canonical schemes to provide a constructive proof of optimality, with respect to the pixel expansion, of c-color (n,n)-threshold visual cryptography schemes.Finally, we provide constructions of c-color (2,n)-threshold schemes whose pixels expansion improves on previously proposed schemes.*This author is also a member of the Akamai Faculty Group, Akamai Technologies, 8 Cambridge center, Cambridge, MA 02142, USA.     

Improved Schemes for Visual Cryptography

A (k,n)-threshold visual cryptography scheme ((k,n)-threshold VCS, for short) is a method to encode a secret image SI into n shadow images called shares such that any k or more shares enable the visual recovery of the secret image, but by inspecting less than k shares one cannot gain any information on the secret image. The visual recovery consists of xeroxing the shares onto transparencies, and then stacking them. Any k shares will reveal the secret image without any cryptographic computation.In this paper we analyze visual cryptography schemes in which the reconstruction of black pixels is perfect, that is, all the subpixels associated to a black pixel are black. For any value of k and n, where 2 k n, we give a construction for (k,n)-threshold VCS which improves on the best previously known constructions with respect to the pixel expansion (i.e., the number of subpixels each pixel of the original image is encoded into). We also provide a construction for coloured (2,n)-threshold VCS and for coloured (n,n)-threshold VCS. Both constructions improve on the best previously known constructions with respect to the pixel expansion.     

Constructions and Properties of k out of n Visual Secret Sharing Schemes

The idea of visual k out of n secret sharing schemes was introduced in Naor. Explicit constructions for k = 2 and k = n can be found there. For general k out of n schemes bounds have been described.Here, two general k out of n constructions are presented. Their parameters are related to those of maximum size arcs or MDS codes. Further, results on the structure of k out of n schemes, such as bounds on their parameters, are obtained. Finally, the notion of coloured visual secret sharing schemes is introduced and a general construction is given.     

New Colored Visual Secret Sharing Schemes

Visual secretsharing (VSS) schemes are used to protect the visual secret bysending n transparencies to different participantsso that k-1 or fewer of them have no informationabout the original image, but the image can be seen by stackingk or more transparencies. However, the revealedsecret image of a conventional VSS scheme is just black and white.The colored k out of n VSS scheme sharinga colored image is first introduced by Verheul and Van Tilborg[1]. In this paper, a new construction for the colored VSS schemeis proposed. This scheme can be easily implemented on basis ofa black & white VSS scheme and get much better block lengththan the Verheul-Van Tilborg scheme.     

Basic Properties of the (t, n)-Threshold Visual Secret Sharing Scheme with Perfect Reconstruction of Black Pixels

In this paper we consider the (t, n)-threshold visual secret sharing scheme (VSSS) in which black pixels in a secret black-white images is reproduced perfectly as black pixels when we stack arbitrary t shares. This paper provides a new characterization of the (t, n)-threshold visual secret sharing scheme with such a property (hereafter, we call such a VSSS the (t, n)-PBVSSS for short). We use an algebraic method to characterize basis matrices of the (t, n)-PBVSSS in a certain class of matrices. We show that the set of all homogeneous polynomials each element of which yields basis matrices of the (t, n)-PBVSSS becomes a set of lattice points in an (n−t+1)-dimensional linear space. In addition, we prove that the optimal basis matrices in the sense of maximizing the relative difference among all the basis matrices in the class coincides with the basis matrices given by Blundo, Bonis and De Santis [3] for all n≥ t ≥ 2.     

Shared Secret Reconstruction

In this paper we consider the secret reconstruction problem in a secret sharing scheme. We emphasize that a shared secret should be reconstructed in a fair way, i.e., all involved participants should have the same chance to be able to reconstruct the shared secret. We propose and analyze several methods to achieve such a fair reconstruction of shared secrets.     

Providing Anonymity in Unconditionally Secure Secret Sharing Schemes

We discuss the concept of anonymity in an unconditionally secure secret sharing scheme, proposing several types of anonymity and situations in which they might arise. We present a foundational framework and provide a range of general constructions of unconditionally secure secret sharing schemes offering various degrees of anonymity.     

Secret Sharing Schemes with Detection of Cheaters for a General Access Structure

In a secret sharing scheme, some participants can lie about the value of their shares when reconstructing the secret in order to obtain some illicit benefit. We present in this paper two methods to modify any linear secret sharing scheme in order to obtain schemes that are unconditionally secure against that kind of attack. The schemes obtained by the first method are robust, that is, cheaters are detected with high probability even if they know the value of the secret. The second method provides secure schemes, in which cheaters that do not know the secret are detected with high probability. When applied to ideal linear secret sharing schemes, our methods provide robust and secure schemes whose relation between the probability of cheating and the information rate is almost optimal. Besides, those methods make it possible to construct robust and secure schemes for any access structure.     

How to Build Robust Shared Control Systems

Previous researchers have designed shared control schemes with a view to minimising the likelihood that participants will conspire to perform an unauthorised act. But, human nature being what it is, systems inevitably fail; so shared control schemes should also be designed so that the police can identify conspirators after the fact. This requirement leads us to search for schemes with sparse access structures. We show how this can be done using ideas from coding theory. In particular, secret sharing schemes based on geometric codes whose dual [n,k,d] codes have d and n as their only nonzero weights are suitable. We determine their access structures and analyse their properties. We have found almost all of them, and established some relations among codes, designs and secret-sharing schemes.     

Unconditionally Secure Group Authentication

Group authentication schemes as introduced by Boyd and by Desmedt and Frankel are cryptographic schemes in which only certain designated groups can provide messages with authentication information. In this paper we study unconditionally secure group authentication schemes based on linear perfect secret sharing and authentication schemes, for which we give expressions for the probabilities of successful attacks. Furthermore, we give a construction that uses maximum rank distance codes.     

Distributing the Encryption and Decryption of a Block Cipher

In threshold cryptography, the goal is to distribute the computation of basic cryptographic primitives across a number of nodes in order to relax trust assumptions on individual nodes, as well as to introduce a level of fault-tolerance against node compromise. Most threshold cryptography has previously looked at the distribution of public key primitives, particularly threshold signatures and threshold decryption mechanisms. In this paper, we look at the application of threshold cryptography to symmetric primitives, and in particular the encryption or decryption of a symmetric key block cipher. We comment on some previous work in this area and then propose a model for shared encryption / decryption of a block cipher. We will present several approaches to enable such systems and will compare them.AMS classification: 94A60, 94A62, 68P25     

Secret Sharing Schemes with Three or Four Minimal Qualified Subsets

In this paper we study secret sharing schemes whose access structure has three or four minimal qualified subsets. The ideal case is completely characterized and for the non-ideal case we provide bounds on the optimal information rate.AMS Classification 94A62     

A Linear Algebraic Approach to Metering Schemes

A metering scheme is a method by which an audit agency is able to measure the interaction between servers and clients during a certain number of time frames. Naor and Pinkas (Vol. 1403 of LNCS, pp. 576–590) proposed metering schemes where any server is able to compute a proof (i.e., a value to be shown to the audit agency at the end of each time frame), if and only if it has been visited by a number of clients larger than or equal to some threshold h during the time frame. Masucci and Stinson (Vol. 1895 of LNCS, pp. 72–87) showed how to construct a metering scheme realizing any access structure, where the access structure is the family of all subsets of clients which enable a server to compute its proof. They also provided lower bounds on the communication complexity of metering schemes. In this paper we describe a linear algebraic approach to design metering schemes realizing any access structure. Namely, given any access structure, we present a method to construct a metering scheme realizing it from any linear secret sharing scheme with the same access structure. Besides, we prove some properties about the relationship between metering schemes and secret sharing schemes. These properties provide some new bounds on the information distributed to clients and servers in a metering scheme. According to these bounds, the optimality of the metering schemes obtained by our method relies upon the optimality of the linear secret sharing schemes for the given access structure.     

Sharing Multiple Secrets: Models, Schemes and Analysis

A multi-secret sharing scheme is a protocol to share more than one secret among a set of participants, where each secret may have a distinct family of subsets of participants (also called ‘access structure’) that are qualified to recover it. In this paper we use an information-theoretic approach to analyze two different models for multi-secret sharing schemes. The proposed models generalize specific models which have already been considered in the literature. We first analyze the relationships between the security properties of the two models. Afterwards, we show that the security property of a multi-secret sharing scheme does not depend on the particular probability distribution on the sets of secrets. This extends the analogous result for the case of single-secret sharing schemes and implies that the bounds on the size of the information distributed to participants in multi-secret sharing schemes can all be strengthened. For each of the two models considered in this paper, we show lower bounds on the size of the shares distributed to participants. Specifically, for the general case in which the secrets are shared according to a tuple of arbitrary (and possibly different) access structures, we show a combinatorial condition on these structures that is sufficient to require a participant to hold information of size larger than a certain subset of secrets. For specific access structures of particular interest, namely, when all access structures are threshold structures, we show tight bounds on the size of the information distributed to participants.     

威客电子商务作弊评价模型及算法研究

威客模式是一种新型电子商务模式,有助于知识、智慧、经验、技能体现经济价值,是电子商务应用领域的一个热点.在介绍威客电子商务模式的基础上,重点研究了影响威客电子商务发展的作弊问题,建立了作弊评价模型.利用威客的历史信息和对设计方案相似性的评价,设计了一种基于定量和定性指标的作弊可能性计算算法.根据威客电子商务的特点,探讨了基于任务金额、结合作弊评价结果的威客信用评价体系.以猪八戒威客网站两个作弊争议案例为例进行了实证分析,说明了作弊评价算法的有效性.     

The State of Elliptic Curve Cryptography

Since the introduction of public-key cryptography by Diffie and Hellman in 1976, the potential for the use of the discrete logarithm problem in public-key cryptosystems has been recognized. Although the discrete logarithm problem as first employed by Diffie and Hellman was defined explicitly as the problem of finding logarithms with respect to a generator in the multiplicative group of the integers modulo a prime, this idea can be extended to arbitrary groups and, in particular, to elliptic curve groups. The resulting public-key systems provide relatively small block size, high speed, and high security. This paper surveys the development of elliptic curve cryptosystems from their inception in 1985 by Koblitz and Miller to present day implementations.     

Information Security, Mathematics, and Public-Key Cryptography

Public-key cryptography is today recognized as an important tool in the provision of information security. This article gives an overview of the field on the occasion of its 22nd birthday.