In this paper we unveil basic properties of a code Γq for digital fingerprinting based on a projective plane of order q. We consider a situation where a coalition of malicious users generates a pirated digital content in which a binary sequence w is embedded subject to the marking assumption. Here, the size of the coalition is assumed to be less than or equal to a known constant c ≥ 2. We evaluate the number of candidates of the coalition that can also generate w subject to the marking assumption. It is shown that the number of such candidates is completely determined as a function of w for the case of c = 2. In addition, we give a sufficient condition under which all the malicious users are correctly identified from w for the case of c ≥ 3. Relationships between Γq and other existing classes of codes are discussed as well.

The planar Hajos calculus (PHC) is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. The degree-d planar Hajos calculus (PHC(dd)) is PHC with the restriction that all the graphs that appear in the construction (including a final graph) must have maximum degree at most d. We prove the followings: (1) If PHC is polynomially bounded, then for any d ≥ 4, PHC(dd+2) can generate any non-3-colorable planar graphs of maximum degree at most d in polynomial steps. (2) If PHC can generate any non-3-colorable planar graphs of maximum degree 4 in polynomial steps, then PHC is polynomially bounded.

We propose a proof-of-concept of a switchable multi-frequency MMIC (monolithic microwave integrated circuit) oscillator device, operating in the 60 GHz millimeter wave band, which is implemented in GaAs p-HEMT transistor technology. Oscillators that can switch between two frequencies have been designed, fabricated and evaluated. The oscillator uses a cross-coupled FET topology, combined with a bent asymmetric coplanar stripline for the resonator, and a switched-capacitor for the frequency switching components. The oscillator generates two oscillations at f/2 and f where f is the target frequency of around 60 GHz. The switchable oscillator has been demonstrated for the range of frequency from 44 GHz to 68.9 GHz. Moreover, the designed oscillator exhibits a wide-band negative resistance property that allows fabricating switchable oscillators covering the 50 to 75 GHz V-band. An evaluated switchable oscillator delivers -17.09 dBm and -13.72 dBm output power at 62.45 GHz and 64.78 GHz, for a supplied power of 40.6 mW and 39.1 mW, respectively.

A RFID group scanning protocol enables a RFID reader to produce a proof of co-existence of multiple RFID tags. This type of protocol is also referred to as yoking-proof, grouping-proof and co-existence proof. In this letter, we show that all of the previous group scanning protocols are vulnerable to relay attack.

A Multi-Property-Preserving (MPP) hash function is a hash function that simultaneously preserves several security properties of the underlying compression function. The Merkle-Damgård with a Permutation (MDP) was shown to preserve unforgeability and pseudorandom oracle property. In this paper, we consider the most basic security properties of hash functions, namely collision resistance, second-preimage resistance, and preimage-resistance. We first show which of these properties are preserved by MDP in the dedicated-key setting. We also identify the properties preserved by four variants of MDP, and five other variants of Merkle-Damgård iterated hash functions. As a result, for the ten hash functions we analyze, we obtain their complete MPP characteristics.

Tweakable pseudorandom permutations have wide applications such as the disk sector encryption, and the underlying primitive for efficient MACs and authenticated encryption schemes. Goldenberg et al. showed constructions of a tweakable pseudorandom permutation based on the Feistel structure. In this paper, we explore the possibility of designing tweakable pseudorandom permutations based on the Generalized Feistel Structure. We show that tweakable pseudorandom permutations can be obtained without increasing the number of rounds compared to the non-tweakable versions. We also present designs that take multiple tweaks as input.

In the OTS/CafeOBJ method, software specifications are described in CafeOBJ executable formal specification language, and verification is done by giving scripts to the CafeOBJ system. The script is called a proof score. In this study, we propose a test case generator from an OTS/CafeOBJ specification together with a proof score. Our test case generator gives test cases by analyzing the proof score. The test cases are used to test whether an implementation satisfies the specification and the property verified by the proof score. Since a proof score involves important information for verifying a property, the generated test cases are also expected to be suitable to test the property.

The Hajos calculus is a nondeterministic procedure which generates the class of non-3-colorable graphs. If all non-3-colorable graphs can be constructed in polynomial steps by the calculus, then NP = co-NP holds. Up to date, however, it remains open whether there exists a family of graphs that cannot be generated in polynomial steps. To attack this problem, we propose two graph calculi PHC and PHC* that generate non-3-colorable planar graphs, where intermediate graphs in the calculi are also restricted to be planar. Then we prove that PHC and PHC* are sound and complete. We also show that PHC* can polynomially simulate PHC.

This paper presents batch processing protocols for efficiently proving a great deal of partial knowledge. These protocols reduce the computation and communication costs for a MIX-net and secure circuit evaluation. The efficiency levels of the proposed protocols are estimated based on the implementation results of a secure circuit evaluation with batch processing.

Image authentication is applied to protect the integrity of the digital image. Conventional image authentication mechanisms, however, are unfit for the palette-based color images. Palette-based color images such as GIF images are commonly used for media communications. This article proposes a palette-based color image authentication mechanism. This novel scheme can guarantee the essentials of general authentication schemes to protect palette-based color images. Morphological operations are adopted to draw out the tampered area precisely. According to the experimental results, the images embedded with the authentication data still can preserve high image quality; specifically, the new scheme is highly sensitive to altered areas.

This paper describes a semi-fragile watermarking scheme for image authentication and tamper-proofing. Each watermark bit is duplicated and randomly embedded in the original image in the discrete wavelet domain by modifying the corresponding image coefficients through quantization. The modifications are made so that they have little effect on the image and that the watermarking is robust against tampering. The watermark image for authentication is reconstructed by taking a weighted vote on the extracted bits. The bits that lose the vote are treated as having been tampered with, and the locations of the lost bits as indicating tampered positions. Thus, authentication and tamper-proofing can be done by observing the images of watermarks that win and lose votes. Sieving, emphasis, and weighted vote were found to be effectively make the authentication and tamper detection more accurate. The proposed scheme is robust against JPEG compression or acceptable modifications, but sensitive to malicious attacks such as cutting and pasting.

In this paper, we propose a new projector-based display which can perform the color simulator for print industry. The proposed color simulator can change the color of print by projecting the image onto the print. A color of print can be matched to the desired color by projecting the image which is calculated to minimize the color difference between the colors of target print and current print. This current print is measured by digital camera or digital scanner. Ideally, spectral camera or scanner is expected to be used for accurate color simulation on the current print, but it costs a lot for practical application. Therefore, in this paper, we compared two methods for color matching, one is the tristimulus-based method with XYZ tristimulus values and the other is the spectral-based method with spectral values. As the result of computer simulation, the average color difference ΔE *94 was 0.27 by the spectral-based method between the reflected radiance from the color of target print and the color of current print with projector, and the average color difference ΔE *94 was 2.09 by the tristimulus-based method. The efficiency of the proposed system is verified by the subjective evaluation between the target and current print with appropriate image projection.

The notion of correlation intractable function ensembles (CIFEs) was introduced in an attempt to capture the "unpredictability" property of random oracles [12]: If O is a random oracle then it is infeasible to find an input x such that the input-output pair (x,O(x)) has some desired property. In this paper, we observe relationships between zero-knowledge protocols and CIFEs. Specifically, we show that, in the non-uniform model, the existence of CIFEs implies that 3-round auxiliary-input zero-knowledge (AIZK) AM interactive proofs exist only for BPP languages. In the uniform model, we show that 3-round AIZK AM interactive proofs with perfect completeness exist only for easy-to-approximate languages. These conditional triviality results extend to constant-round AIZK AM interactive proofs assuming the existence of multi-input CIFEs, where "multi-input" means that the correlation intractability is satisfied with respect to multiple input-output pairs. Also, as a corollary, we show that any construction of uniform multi-input CIFEs from uniform one-way functions proves unconditionally that constant-round AIZK AM interactive proofs with perfect completeness only for easy-to-approximate languages.

Though there are intensive researches on off-line electronic cash (e-cash), the current computer network infrastructure sufficiently accepts on-line e-cash. The on-line means that the payment protocol involves with the bank, and the off-line means no involvement. For customers' privacy, the e-cash system should satisfy unlinkability, i.e., any pair of payments is unlinkable w.r.t. the sameness of the payer. In addition, for the convenience, exact payments, i.e., the payments with arbitrary amounts, should be also able to performed. In an existing off-line system with unlinkable exact payments, the customers need massive computations. On the other hand, an existing on-line system does not satisfy the efficiency and the perfect unlinkability simultaneously. This paper proposes an on-line system, where the efficiency and the perfect unlinkability are achieved simultaneously.

In this paper, we propose a proof scheme of shuffle, which is an honest verifier zero-knowledge proof of knowledge such as the protocols by Groth and Furukawa. Unlike the previous schemes proposed by Furukawa-Sako, Groth, and Furukawa, our scheme can be used as the shuffle of the elements encrypted by Paillier's encryption scheme, which has an additive homomorphic property in the message part. The ElGamal encryption scheme used in the previous schemes does not have this property.

This paper provides algorithms in order to solve an interval implicit function of the Poincare map generated by a continuous piece-wise linear (CPWL) vector field, with the use of interval arithmetic. The algorithms are implemented with the use of MATLAB and INTLAB. We present an application to verification of canards in two-dimensional CPWL vector field appearing in nonlinear piecewise linear circuits frequently, and confirm that the algorithms are effective.

Tamper proofing is a crucial problem in the watermarking application. Aiming at the credibility of multimedia, we present a semi-fragile watermark based on the image permutation. Watermarking detection is performed without resorting to the host image and it is only controlled by secrete keys, thus the whole scheme does not have certain security gaps. The simulation experiments show that it can survive the JPEG compression and effectively specify the region of the image that has been modified maliciously.

OMAC is a provably secure MAC scheme proposed by Iwata and Kurosawa. NIST currently intends to specify OMAC as the modes recommendation. In August 2003, Mitchell published a note "On the security of XCBC, TMAC and OMAC" to propose a new variant of OMAC. We call it OMAC1". In this paper, we prove that OMAC1" is less secure than the original OMAC. We show a security gap between them. As a result, we obtain a negative answer to Mitchell's open question--OMAC1" is not provably secure even if the underlying block cipher is a PRP. Further, we point out limitations of discussion in [16].

Goldwasser and Sipser proved that every interactive proof system can be transformed into a public-coin one (a.k.a. an Arthur-Merlin game). Unfortunately, the applicability of their transformation to cryptography is limited because it does not preserve the computational complexity of the prover's strategy. Vadhan showed that this deficiency is inherent by constructing a promise problem Π with a private-coin interactive proof that cannot be transformed into an Arthur-Merlin game such that the new prover can be implemented in polynomial-time with oracle access to the original prover. However, the transformation formulated by Vadhan has a restriction, i.e., it does not allow the new prover and verifier to look at common input. This restriction is essential for the proof of Vadhan's negative result. This paper considers an unrestricted transformation where both the new prover and verifier are allowed to access and analyze common input. We show that an analogous negative result holds even in this unrestricted case under a non-standard computational assumption.

We present an efficiency improvement on an existing unlinkable divisible e-cash system. In the based e-cash system, an e-coin can be divided to spent, and thus the exact payments are available. Furthermore, to protect customer's privacy, the system also satisfies the unlinkability in all the payments, which is not satisfied in other existing divisible e-cash systems. The unlinkability means the infeasibility of determining whether two payments are made by the same customer. However, in the unlinkable divisible e-cash system, the payment protocol needs O(N) computations, and thus inefficient, where N indicates the divisibility precision. For example, in case of N=100,000, about 200,000 exponentiations are needed for the worst. We improve the payment protocol using the tree approach. In case of N=100,000, the protocol with our improvement needs only about 600 exponentiations for the worst. This good result can be obtained for other N which is more than about 100.