An important issue of fragile watermarking for image is to locate and restore the tampered pixels individually and accurately. This issue is resolved for concentrated tampering. In contrast, for diverse tampering, only localization is realized. This paper presents a restoration method for the most accurate scheme tolerant against diverse tampering. We analyze the error probability and experimentally confirm that the proposed method accurately restores the tampered pixels. We also show two variations based on the fact that the authentication data used for deriving the watermark is a maximum length sequence code.

A broadcast distribution system (BDS) is a system for the distribution of digital contents over broadcast channel where the data supplier broadcasts the contents in encrypted form and gives each subscriber a decoder containing a secret decryption key. A traitor is a subscriber who offers the information which allows to decrypt the broadcast. When a pirate decoder is captured, if at least one traitor can be identified from it, a BDS is said to be traitor-tracing. If the data supplier can prevent subscribers from obtaining the contents without recalling their decoders, a BDS is said to be subscriber-excluding. In this paper, we propose an efficient BDS which is both subscriber-excluding and traitor-tracing. We use similar mathematics to a threshold cryptosystem. In the proposed BDS, the maximum number of excluded subscribers reaches the maximum number of traitors in a coalition for which at least one traitor can be identified. We prove that the proposed BDS is secure against ciphertext-only attack if and only if ElGamal cryptosystem is secure against the attack and the discrete logarithm problem is hard. The proposed BDS is the first one which satisfies all the following features: Both subscriber-excluding and traitor-tracing, identifying all the traitors, black box tracing and public key system.

This paper introduces a new computational problem on a two-dimensional vector space, called the vector decomposition problem (VDP), which is mainly defined for designing cryptosystems using pairings on elliptic curves. We first show a relation between the VDP and the computational Diffie-Hellman problem (CDH). Specifically, we present a sufficient condition for the VDP on a two-dimensional vector space to be at least as hard as the CDH on a one-dimensional subspace. We also present a sufficient condition for the VDP with a fixed basis to have a trapdoor. We then give an example of vector spaces which satisfy both sufficient conditions and on which the CDH is assumed to be hard in previous work. In this sense, the intractability of the VDP is a reasonable assumption as that of the CDH.

A cover free family (CFF) is a useful mathematical tool for cryptographic schemes where any pre-defined number of sets in the family do not cover another set in the family. The common disadvantage of CFF-based schemes is the requirement for a significantly large amount of data such as public keys and ciphertexts. This paper proposes a simple method to reduce the size of ciphertexts in CFF-based broadcast encryption schemes by removing redundant elements from sets in the family, and then analyzes the size of cihpertexts. As a result, in a typical distribution case, the average amount of ciphertexts is reduced to 83 percents (from 691Kbits to 576Kbits).

A secret sharing scheme is said to be d-multiplicative if the scheme allows the players to multiply shared d secrets by locally converting their shares into an additive sharing of the product. In the previous work, the following negative result for perfect secret sharing has been shown: The d-multiplicative secret sharing for d players is impossible. This paper extends the impossibility result to non-perfect secret sharing. Our main result is a proof that d-multiplicative secret sharing for d players is impossible even if every player has partial information on the secret (e.g., all but one bit). This result means that there is no need to relax the privacy requirement with leakage of partial information only for the purpose of d-multiplication.

This paper introduces a novel type of digital watermarking, which is mainly designed for embededing information into cryptographic data such as keys, ciphertexts, and signatures. We focus on a mathematical structure of the recent major cryptosystems called pairing-based schemes. We present a detection-type watermarking scheme by which a watermark is visible by anyone but unremovable without secret trapdoor. The important feature is that both correctness and security of cryptographic data remain satisfied even if the trapdoor is published.

A typical watermarking scheme consists of an embedding scheme and a detection scheme. In detecting a watermark, there are two kinds of detection errors, a false positive error (FPE) and a false negative error (FNE). A detection scheme is said to be optimum if the FNE probability is minimized for a given FPE probability. In this paper, we present an optimum watermark detection scheme for an additive embedding scheme with a spatial domain. The key idea of the proposed scheme is to use the differences between two brightnesses for detecting a watermark. We prove that under the same FPE probability the FNE probability of the proposed optimum detection scheme is no more than that of the previous optimum detection scheme for the additive embedding scheme with the spatial domain. Then, it is confirmed that for an actual image, the FNE probability of the proposed optimum detection scheme is much lower than that of the previous optimum detection scheme. Moreover, it is confirmed experimentally that the proposed optimum detection scheme can control the FPE probability strictly so that the FPE probability is close to a given probability.

This paper presents a new scheme for Timed-Release Encryption (TRE), which is mainly designed for global use. TRE aims to control the timing of disclosing information. The major approach to TRE assumes that any participants can receive a time token broadcasted by a trusted agent, called a time server. Our scheme is based on this approach and allows participants to generate an encrypted message that can be decrypted using designated or any authenticated time servers including even those which are authenticated after encryption. In this sense, our scheme has a more flexible framework in terms of message decryption.

We consider delivering interactive dramas. A viewer interacts with a contents provider by answering multiple-choice questions and the answers to these questions influence the plot of delivered story. All possible plots can be represented by a directed graph such that every plot corresponds to some path of the graph. A delivery should be controlled according to the directed graph such that each viewer's history of answered choices forms a path of the graph. On the other hand, because some character of a viewer is known to a contents provider from his history of choices, a viewer tries to prevent even a contents provider from linking choices made by him. In this paper, we introduce unlinkable delivery for an interactive drama and propose such a delivery system for interactive dramas that viewer's choices are unlinkable and delivery is controlled according to the directed graph.

Data retrieval is used to obtain a particular data item from a database. A user requests an item in the database from a database server by sending a query, and obtains the item from an answer to the query. Security requirements of data retrieval include protecting the privacy of the user, the secrecy of the database, and the consistency of answers. In this paper, a data retrieval scheme which satisfies all the security requirements is defined and an efficient construction is proposed. In the proposed construction, the size of a query and an answer is O((log N)2), and the size of data published by the database server when the database is updated is only O(1). The proposed construction uses the Merkle tree, a commitment scheme, and Oblivious Transfer. The proof of the security is given under the assumption that the used cryptographic schemes are secure.

Solutions based on error-correcting codes for the blacklisting problem of a broadcast distribution system have been proposed by Kumar, Rajagopalan and Sahai. In this paper, detailed analysis of the solutions is presented. By choosing parameters properly in their constructions, we show that the performance is improved significantly.