Today software piracy is a major concern to electronic commerce since a digitized product such as software is vulnerable to redistribution and unauthorized use. This paper presents an enhanced electronic software distribution and software protection model. Authentication scheme of the proposed model is based on zero-knowledge (ZK) proof which requires limited computation. The proposed model considers post installation security using authentication agent. It prevents software piracy and illegal copy. It also provides secure and efficient software live-update mechanism based on traitor tracing scheme. Even if software or personal key is copied illegally, a merchant can trace back to its original owner from the electronic license and personal key. The proposed model provides security and reasonable performance and safety.

Dr. Kenji Koyama, one of the most respected and prominent Japanese researchers in modern cryptography, passed away on March 27, 2000. He left behind him many outstanding academic achievements in cryptography as well as other areas such as emotion transmission theory, learning and mathematical games. In this manuscript, with our deepest sympathy and greatest appreciation for his contribution to our society, we introduce his major works mainly in cryptography, although his papers in other areas are included in the bibliography list.

We formalize a model of "demonstration of program result-correctness," and investigate how to prove this fact against possible adversaries, which naturally extends Blum's theory of program checking by adding zero-knowledge requirements. The zero-knowledge requirements are universal for yes and no instances alike.

This paper proposes the first provably secure multi-signature schemes under the random oracle model. The security of our schemes can be proven in the sense of concrete security in Ref. [13]. The proposed schemes are efficient if the random oracle is replaced by practical hash functions. The essential techniques in our proof of security are the optimal reduction from breaking the corresponding identification to breaking signatures (ID Reduction Technique), and the hierarchical heavy row lemmas used in the concrete reduction from solving the primitive problem to breaking the identification scheme.

In this paper, we propose a new type of authentication system, one-time zero-knowledge authentication system. Informally speaking, in this authentication system, double usage of the same authentication is prevented. Based on these one-time zero-knowledge authentication systems, we propose a new untraceable electronic cash scheme satisfying both untraceability and unreusablity. This scheme overcomes the problems of the previous scheme proposed by Chaum, Fiat and Naor through its greater efficiency and provable security under reasonable cryptographic assumptions. We also propose a scheme, transferable untraceable electronic cash scheme, satisfying transferability as well as the above two criteria. Moreover, we also propose a new type of electronic cash, untraceable electronic coupon ticket, in which the value of one piece of the electronic cash can be subdivided into many pieces.

Fiat-Shamir's identification and signature scheme is efficient as well as provably secure, but it has a problem in that the transmitted information size and memory size cannot simultaneously be small. This paper proposes an identification and signature scheme which overcomes this problem. Our scheme is based on the difficulty of extracting theL-th roots modn (e. g.L=2 1020) when the factors ofnare unknown. We prove that the sequential version of our scheme is a zero knowledge interactive proof system and our parallel version reveals no transferable information if the factoring is difficult. The speed of our scheme's typical implementation is at least one order of magnitude faster than that of the RSA scheme and is relatively slow in comparison with that of the Fiat-Shamir scheme.

We describe a formal verification algorithm for pipelined processors. This algorithm proves the equivalence between a processor's design and its specifications by using rewriting of recursive functions and a new type of mathematical induction: extended recursive induction. After the user indicates only selectors in the design, this algorithm can automatically prove processors having more than 10(1010) states. The algorithm is manuary applied to benchmark processors with pipelined control, and we discuss how data width, memory size, and the numbers of pipeline stages and instructions influence the computation cost of proving the correctness of the processors. Further, this algorithm can be used to generate a pipeline invariant.

Let L{0,1}* be a language and let λL : {0,1}*{0,1} be the characteristic function of the language L, i.e., if x ∈ L, λL (x) = 1; otherwise,λL (x) = 0. In this paper, we consider an adaptive checker with a single program F (resp. noncommunicating multiple programs F1, F2,...) for λL that works even when an incorrect program F* (resp. incorrect noncommunicating multiple programs F*1,F*2,...) for λL adaptively behaves according to inputs previously provided to the program F* (resp. the programs F*1,F*2,...). We show that (1) for any language L, there exists an adaptive checker with a single program for λL iff L and respectively have competitive interactive proof systems; and (2) that for any language L, there exists an adaptive checker with noncommunicating multiple programs for λL iff L and respectively have function-restricted interactive proof systems. This implies that for any language L, adaptive chekers with noncommunicating multiple programs for λL are as powerful as static ones with a single program for λL.

This paper describes the optical characteristics and static fatigue reliability of a zirconia alignment sleeve, which is a component part of an optical connector with zirconia ferrules. This combination of sleeve and ferrules hardly generates any wear debris during connector insertion and removal cycles. This has reduced the cleaning frequency of the ferrule endface during cycles and greatly improved the return loss stability of the optical connectors. The zirconia alignment sleeve enables stable return loss characteristics to be achieved over a wide temperature range as it has the same thermal expansion coefficient as the zirconia ferrule. Furthermore, the gauge retention force for the zirconia alignment sleeve is defined with a view to its practical use. This force must be between 2.0 and 3.9 N to allow stable optical connections to be made under various mechanical and environmental conditions. We also clarify the conditions for a proof test by which to prevent the occurrence of static fatigue fractures in the sleeve, and we confirm the validity of the test. The static fatigue parameters for zirconia ceramics and derived from the static fatigue theory for brittle materials and fracture testing. We use these static fatigue parameters to predict the lifetime of a zirconia sleeve under working stress. An appropriate stress level for the proof test which eliminates weak sleeves, is about 3 times greater than working stress. The strength of the sleeve as demonstrated in the proof test is confirmed by accelerative stress aging. The performance of this sleeve is superior to that of a conventional copper alloy sleeve and the proof test confirms its reliability; under 0.1 FIT for 20 years of use.

This paper presents a zero-knowledge interactive protocol that demonstrates two factors a and b of a composite number n (=ab) are really known by the prover, without revealing the factors themselves. Here the factors a and b need not be primes. The security of the protocol is based on the difficulty of computing discrete logarithms modulo a large prime.

In this paper, we study the knowledge tightness of zero-knowledge proofs. To this end, we present a new measure for the knowledge tightness of zero-knowledge proofs and show that if a language L has a bounded round zero-knowledge proof with knowledge tightness t(|x|) 2 - |x|-c for some c 0, then L BPP and that any language L AM has a bounded round zero-knowledge proof with knowledge tightness t(|x|) 2-2-O(|x|) under the assumption that collision intractable hash functions exist. This implies that in the case of a bounded round zero-knowledge proof for a language L BPP, the optimal knowledge tightness is "2" unless AM = BPP. In addition, we show that any language L IP has an unbounded round zero-knowledge proof with knowledge tightness t(|x|) 1.5 under the assumption that nonuniformly secure probabilistic encryptions exist.

In this paper, we investigate the knowledge complexity of interactive proof systems and show that (1) under the blackbox simulation, if a language L has a bounded move public coin interactive proof system with polynomially bounded knowledge complexity in the hint sense, then the language L itself has a one move interactive proof system; and (2) under the blackbox simulation, if a language L has a three move private coin interactive proof system with polynomially bounded knowledge complexity in the hint sense, then the language L itself has a one move interactive proof system. These results imply that as long as the blackbox simulation is concerned, any language L AM＼MA is not allowed to have a bounded move public coin (or three move private coin) interactive proof system with polynomially bounded knowledge complexity in the hint sense unless AM = AM. In addition, we present a definite distinction between knowledge complexity in the hint sense and in the strict oracle sense, i.e., any language in AM (resp. IP) has a two (resp. unbounded) move public coin interactive proof system with polynomially bounded knowledge complexity in the strict oracle sense.

In this paper, we show that without any unproven assumption, there exists a "four" move blackbox simulation perfect zero-knowledge interactive proof system of computational ability for any random self-reducible relation R whose domain is in BPP, and that without any unproven assumption, there exists a "four" move blackbox simulation perfect zero-knowledge interactive proof system of knowledge on the prime factorization. These results are optimal in the light of the round complexity, because it is shown that if a relation R has a three move blackbox simulation (perfect) zero-knowledge interactive proof system of computational ability (or of knowledge), then there exists a probabilistic polynomial time algorithm that on input x ∈ {0, 1}*, outputs y such that (x, y)∈R with overwhelming probability if x ∈dom R, and outputs "⊥" with probability 1 if x dom R.

In this paper, we consider a class of the languages that have (constant round) perfect zero-knowledge interactive proofs without assuming any complexity assumptions. Especially, we investigate the interactive protocol with the restricted prover who runs in probabilistic polynomial time and knows the complete factorization as a trapdoor information of the integer associated with the input. We give a condition of the existence of constant round perfect zero-knowledge interactive proofs without assuming any complexity assumptions. The bit commitment based on the quadratic residuosity has an important role in our protocol and the simulation is based on the technique developed by Bellare, Micali, and Ostrovsky in Ref. (9), so call double running process. However, the proof of perfect zero-knowledgeness needs a more powerful simulation technique. Our simulation extracts more knowledge, the complete factorization of the integer associated with the input, from a (cheating) verifier than Bellare-Micali-Ostrovsky's simulation does. Furthermore, our main result implies that Blum integer has a five move perfect zero-knowledge interactive proof without assuming any complexity assumptions. (All previous known zero-knowledge protocols for Blum integer required either unproven cryptographic assumptions or unbounded number of rounds of message exchange.)

In this paper, we investigate the round complexity of zero-knowledge interactive proof systems of possession of knowledge, and mainly show that if a relation R has a three move blackbox simulation zero-knowledge interactive proof system of possession of knowledge, then there exists a probabilistic polynomial time algorithm that on input x{0,1}*, outputs y such that (x,y)R with overwhelming probability if xdom R, and outputs "" with probability 1 if x dom R. The result above can not be generalized to zero-knowledge interactive proof systems of possession of knowledge with more than four moves, because it is known that there exists a "four" move blackbox simulation perfect zero-knowledge interactive proof system of possession of knowledge for a nontrivial relation R.

Given an integer N, it is easy to determine whether or not N is prime, because a set of primes is in LPP. Then given a composite number N, is it easy to determine whether or not N is of a specified form? In this paper, we consider a subset of odd composite numbers +1MOD4 (resp. +3MOD4), which is a subset of odd composite numbers consisting of prime factors congruent to 1 (resp. 3) modulo 4, and show that (1) there exists a four move (blackbox simulation) perfect ZKIP for the complement of +1MOD4 without any unproven assumption; (2) there exists a five move (blackbox simulation) perfect ZKIP for +1MOD4 without any unproven assumption; (3) there exists a four move (blackbox simulation) perfect ZKIP for +3MOD4 without any unproven assumption; and (4) there exists a five move (blackbox simulation) statistical ZKIP for the complement of +3MOD4 without any unproven assumption. To the best of our knowledge, these are the first results for a language L that seems to be not random self-reducible but has a constant move blackbox simulation perfect or statistical ZKIP for L and without any unproven assumption.

In this paper, we investigate the discrepancy between a serial version and a parallel version of zero-knowledge protocols, and clarify the information "leaked" in the parallel version, which is not zero-knowledge unlike the case of the serial version. We consider two sides: one negative and the other positive in the parallel version of zero-knowledge protocols, especially of the Fiat-Shamir scheme.

In this paper, we propose a multi-purpose proof system which enables a user remembering only one piece of secret data to perform various proof protocols. These proofs include identity proof, membership proof without disclosing identity, and combined identity and membership proof. When a user participates in a group, he will obtain a secret witness from the group administrator. Many secret witnesses can be combined into one piece of secret data. But the size of the secret data is independent of the number of the groups in which the user participates. Our system satisfies other desirable properties which were not attained by the previously proposed systems.

The subject of the paper is to analyze time complexity of the minimum axiom set problem (MASHC) in the Horn clause propositional logic. MASHC is defined by "Given a set H of Horn clauses and a query Q, all in propositional logic, such that Q is provable over H, find an axiom set of minimum cardinality, HH, with respect to Q, where Q is provable over H if and only if Q can be shown to be true by repeating Modus Ponens starting from clauses of H under the assumption that all of them are originally assumed to be true". If Q is provable over H then H is called an axiom set (with respect to Q). As stated in the definition of MASHC, detecting if Q is provable over H is required. This leads us to a problem, called the provability detecting problem (PDPHC), defined by "Given a set H of Horn clauses and a query Q in propositional logic, determine if Q is provable over H". First an O(σ) algorithm BFSHC for PDPHC is given based on the breadth-first search, where σ is the formula size of a given set of Horn clauses. For MASHC, it is shown that the problem is NP-complete, and an O(σ) approximation algorithm FMAS is given. Its experimental evaluation is also presented.

This paper proposes a new construction of the minimum knowledge undeniable signature scheme which solves a problem inherent in Chaum's scheme. We formulate a new proof system, the minimum knowledge interactive bi-proof system, and a pair of languages, the common witness problem, based on the random self-reducible problem. We show that any common witness problem has the minimum knowledge interactive bi-proof system. A practical construction for undeniable signature schemes is proposed based on such a proof system. These schemes provide signature confirmation and disavowal with the same protocol (or at the same time).