The certified discrete logarithm problem modulo p prime is a discrete logarithm problem under the conditions that the complete factorization of p-1 is given and by which the base g is certified to be a primitive root mod p. For the cryptosystems based on the intractability of certified discrete logarithm problem, Sakurai-Shizuya showed that breaking the Diffie-Hellman key exchange scheme reduces to breaking the Shamir 3-pass key transmission scheme with respect to the expected polynomial-time Turing reducibility. In this paper, we show that we can remove randomness from the reduction above, and replace the reducibility with the polynomial-time many-one. Since the converse reduction is known to hold with respect to the polynomial-time many-one reducibility, our result gives a stronger evidence for that the two schemes are completely equivalent as certified discrete log cryptosystems.

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.

A family F of min-wise independent permutations is known to be a useful tool of indexing replicated documents on the Web. We say that a family F of permutations on {0,1,. . . ,n-1} is min-wise independent if for any X {0,1,. . . ,n-1} and any x X, Pr[min {π(X)} = π(x)]= ||X||-1 when π is chosen uniformly at random from F, where ||A|| is the cardinality of a finite set A. We also say that a family F of permutations on {0,1,. . . ,n-1} is d-wise independent if for any distinct x1,x2,. . . ,xd {0,1,. . . , n-1} and any distinct y1,y2,. . . ,yd {0,1,. . . , n-1}, Pr[i=1d π(xi) = π(yi)]= 1/{n(n-1) (n-d+1)} when π is chosen uniformly at random from F (note that nontrivial constructions of d-wise independent family F of permutations on {0,1,. . . ,n-1} are known only for d=2,3). Recently, Broder, et al. showed that any family F of pairwise (2-wise) independent permutations behaves close to a family of min-wise independent permutations, i.e., for any X {0,1,. . . ,n-1} such that 3 ||X||=k n-2 and any x X, (lower bound) Pr[min {π(X)}=π(x)] 1/{2(k-1)}; (upper bound) Pr[min {π(X)}=π(x)] O(1/k). In this paper, we extend these bounds to 3-wise independent permutation family and show that any family of 3-wise independent permutations behaves closer to a family of min-wise independent permutations, i.e., for any X {0,1,. . . ,n-1} such that 4 ||X||=k n-3 and any x X, (lower bound) Pr[min {π(X)}=π(x)] 1/{2(k-2)}- 1/{6(k-2)2}; (upper bound) Pr[min {π(X)}=π(x)] 2/k - 2/k + 1/(3kk).

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.

When a store sells items to customers, the store wishes to decide the prices of items to maximize its profit. Intuitively, if the store sells the items with low (resp. high) prices, the customers buy more (resp. less) items, which provides less profit to the store. So it would be hard for the store to decide the prices of items. Assume that the store has a set V of n items and there is a set E of m customers who wish to buy the items, and also assume that each item i ∈ V has the production cost di and each customer ej ∈ E has the valuation vj on the bundle ej ⊆ V of items. When the store sells an item i ∈ V at the price ri, the profit for the item i is pi=ri-di. The goal of the store is to decide the price of each item to maximize its total profit. We refer to this maximization problem as the item pricing problem. In most of the previous works, the item pricing problem was considered under the assumption that pi ≥ 0 for each i ∈ V, however, Balcan, et al. [In Proc. of WINE, LNCS 4858, 2007] introduced the notion of "loss-leader," and showed that the seller can get more total profit in the case that pi < 0 is allowed than in the case that pi < 0 is not allowed. In this paper, we consider the line highway problem (in which each customer is interested in an interval on the line of the items) and the cycle highway problem (in which each customer is interested in an interval on the cycle of the items), and show approximation algorithms for the line highway problem and the cycle highway problem in which the smallest valuation is s and the largest valuation is (this is called an [s,]-valuation setting) or all valuations are identical (this is called a single valuation setting).

The minimum distance of a linear code C is a useful metric property for estimating the error correction upper bound of C and the maximum likelihood decoding of a linear code C is also of practical importance and of theoretical interest. These problems are known to be NP-hard to approximate within any constant relative error to the optimum. As a problem related to the above, we consider the maximization problem MAX-WEIGHT: Given a generator matrix of a linear code C, find a codeword c C with its weight as close to the maximum weight of C as possible. It is shown that MAX-WEIGHT PTAS unless P=NP, however, no nontrivial approximation upper and lower bounds are known. In this paper, we investigate the complexity of MAX-WEIGHT to make the approximation upper and lower bounds more precise, and show that (1) MAX-WEIGHT is APX-complete; (2) MAX-WEIGHT is approximable within relative error 1/2 to the optimum; (3) MAX-WEIGHT is not approximable within relative error 1/10 to the optimum unless P=NP.

A min-wise independent permutation family is known to be an efficient tool to estimate similarity of documents. Toward good understanding of min-wise independence, we present a characterization of exactly min-wise independent permutation families by size uniformity, which represents certain symmetry of the string representation of a family. Also, we present a general construction strategy which produce any exactly min-wise independent permutation family using this characterization.

When a store sells items to customers, the store wishes to determine the prices of the items to maximize its profit. Intuitively, if the store sells the items with low (resp. high) prices, the customers buy more (resp. less) items, which provides less profit to the store. So it would be hard for the store to decide the prices of items. Assume that the store has a set V of n items and there is a set E of m customers who wish to buy those items, and also assume that each item i ∈ V has the production cost di and each customer ej ∈ E has the valuation vj on the bundle ej ⊆ V of items. When the store sells an item i ∈ V at the price ri, the profit for the item i is pi=ri-di. The goal of the store is to decide the price of each item to maximize its total profit. We refer to this maximization problem as the item pricing problem. In most of the previous works, the item pricing problem was considered under the assumption that pi ≥ 0 for each i ∈ V, however, Balcan, et al. [In Proc. of WINE, LNCS 4858, 2007] introduced the notion of "loss-leader," and showed that the seller can get more total profit in the case that pi < 0 is allowed than in the case that pi < 0 is not allowed. In this paper, we derive approximation preserving reductions among several item pricing problems and show that all of them have algorithms with good approximation ratio.

An important problem in mathematics and data science, given two or more metric spaces, is obtaining a metric of the product space by aggregating the source metrics using a multivariate function. In 1981, Borsík and Doboš solved the problem, and much progress has subsequently been made in generalizations of the problem. The triangle inequality is a key property for a bivariate function to be a metric. In the metric aggregation, requesting the triangle inequality of the resulting metric imposes the subadditivity on the aggregating function. However, in some applications, such as the image matching, a relaxed notion of the triangle inequality is useful and this relaxation may enlarge the scope of the aggregators to include some natural superadditive functions such as the harmonic mean. This paper examines the aggregation of two semimetrics (i.e. metrics with a relaxed triangle inequality) by the harmonic mean is studied and shows that such aggregation weakly preserves the relaxed triangle inequalities. As an application, the paper presents an alternative simple proof of the relaxed triangle inequality satisfied by the robust Jaccard-Tanimoto set dissimilarity, which was originally shown by Gragera and Suppakitpaisarn in 2016.

In 1978, Merkle and Hellman published two kinds of knapsack type public key cryptosystems, one of which was super-increasing type and the other was multiplicative type. However, the former was broken by Shamir in 1982 and latter was broken by Odlyzko in 1984. Recently, Chor and Rivest proposed a new multiplicative knapsack type cryptosystem based on arithmetic in GF (ph) which cannot be broken by the Odlyzko attack. This paper shows the new cryptosystem is broken if the public knapsack vector has three elements whose values are close to one another or if the primitive polynomial is known. We also present that not only the original secret-key also many other ones can decipher the cryptosystem.

Informally, private information retrieval for k 1 databases (k-PIR) is an interactive scheme that enables a user to make access to (separated) k replicated copies of a database and privately retrieve any single bit out of the n bits of data stored in the database. In this model, "privacy" implies that the user retrieves the bit he is interested in but releases to each database nothing about which bit he really tries to get. Chor et. al. proposed 2-PIR with communication complexity 12 n1/32 that is based on the covering codes. Then Ambainis recursively extended the scheme by Chor et. al. and showed that for each k 2, there exists k-PIR with communication complexity at most ckn1/(2k-1) some constant ck > 0. In this paper, we relax the condition for the covering codes and present time-efficient 2-PIR with communication complexity 12 n1/3. In addition, we generally formulate the recursive scheme by Ambainis and show that for each k 4, there exists k-PIR with communication complexity at most ck' n1/(2k-1) for some constant ck' << ck.

This paper considers the subliminal channel, hidden in an identification scheme, for transferring signatures. We observe the direct parallelization of the Fiat-Shamir identification scheme has a subliminal channel for the transmission of the digital signature. A positive aspect of this hidden channel supplies us how to transfer signatures without secure channels. As a formulation of such application, we introduce a new notion called privately recordable signature. The privately recordable signature is generated in an interactive protocol between a signer and a verifier, and only the verifier can keep the signatures although no third adversary can record the signatures. ln this scheme, then the disclosure of the verifier's private coin turns the signer's signature into the ordinary digital signature which is verified by anybody with the singer's public key. The basic idea of our construction suggests the novel primitive that a transferring securely signatures without secret channels could be constructed using only one-way function (without trapdoor).

The recent burst growth of the Internet use overloads networking systems and degrades the quality of communications, e.g., bandwidth loss, packet drops, delay of responses, etc. To overcome such degradation of the communication quality, the notion of Quality of Service (QoS) has received attention in practice. In general, QoS switches have several queues and each queue has several slots to store arriving packets. Since network traffic changes frequently, QoS switches need to control arriving packets to maximize the total priorities of transmitted packets, where the priorities are given by nonnegative values and correspond to the quality of service required for each packet. In this paper, we derive lower bounds for the competitive ratio of deterministic multi-queue nonpreemptive QoS problem of priorities 1 and α 1: 1 + /α ln if α α*; 1/(1 - e-τ0) if 1 α < α*, where α* 1.657 and τ0 is a root of the equality that e-τ(1/α + τ)=1 - e-τ. As an immediate result, this shows a lower bound 1.466 for the competitive ratio of deterministic multi-queue nonpreemptive QoS problem of single priority, which slightly improves the best known lower bound 1.366.

For the multi-objective time series search problem, Hasegawa and Itoh [Theoretical Computer Science, Vol.78, pp.58-66, 2018] presented the best possible online algorithm balanced price policy for any monotone function f:Rk→R. Specifically the competitive ratio with respect to the monotone function f(c1,...,ck)=(c1+…+ck)/k is referred to as the arithmetic mean component competitive ratio. Hasegawa and Itoh derived the explicit representation of the arithmetic mean component competitive ratio for k=2, but it has not been known for any integer k≥3. In this paper, we derive the explicit representations of the arithmetic mean component competitive ratio for k=3 and k=4, respectively. On the other hand, we show that it is computationally difficult to derive the explicit representation of the arithmetic mean component competitive ratio for arbitrary integer k in a way similar to the cases for k=2, 3, and 4.

The notion of k-wise independent permutations has several applications. From the practical point of view, it often suffices to consider almost (i.e., ε-approximate) k-wise independent permutation families rather than k-wise independent permutation families, however, we know little about how to construct families of ε-approximate k-wise independent permutations of small size. For any n > 0, let Sn be the set of all permutations on {0,1,..., n - 1}. In this paper, we investigate the size of families of ε-approximate k-wise independent permutations and show that (1) for any constant ε 0, if a family Sn of permutations is ε-approximate k-wise independent, then || n(n - 1) (n - k + 1) if ε< 1; || {n(n - 1) (n - k + 1)}/(1 +ε) otherwise; (2) for any constant 0< ε 1, there exists a family Sn of ε-approximate k-wise independent permutations such that || = ; (3) for any constant ε> 0 and any n = pm - 1 with p prime, it is possible to construct a polynomial time samplable family Sn of ε-approximate pairwise independent permutations such that || = O(n(n - 1)/ε); (4) for any constant ε> 0 and any n = pm with p prime, it is possible to construct a polynomial time samplable family Sn of ε-approximate 3-wise independent permutations such that || = O(n(n - 1)(n - 2)/ε). Our results are derived by combinatorial arguments, i.e., probabilistic methods and linear algebra methods.

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 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 AM languages that seem to be located outside NP co-NP. We give two natural examples of such AM languages, GIP and GH, which stand for Graph Isomorphism Pattern and Graph Heterogeneity, respectively. We show that the GIP is in ΔP2 AM co-AM but is unlikely to be in NP co-NP, and that GH is in ΔP2 AM but is unlikely to be in NP co-AM. We also show that GIP is in SZK. We then discuss some structural properties related to those languages: Any language that is polynomial time truth-table reducible to GIP is in AM co-AM; GIP is in co-SZK if SZK co-SZK is closed under conjunctive polynomial time bounded-truth-table reducibility; Both GIP and GH are in DP. Here DP is the class of languages that can be expressed in the form X Y, where X NP and Y co-NP.

Private information retrieval for k 1 databases (denoted by (k,l)-PIR for short) is a protocol that (1) a user sends an l tuple query to each of k noncommunicating replicated databases; (2) each database responds the user with an answer corresponding to the l tuple query; (3) the user privately retrieve any single bit out of the n bits of data stored in k databases. In this model, "privacy" implies that the user retrieves the bit he is interested in but releases to each database nothing about which bit he wishes to get. In general, the efficiency of (k,l)-PIR is measured by the total amount of bits exchanged between the user and the k databases, but few about its lower bounds are known except for restricted cases. In this paper, we classify (k,l)-PIR into a linear type, a multilinear type, and an affine type with respect to the relationship between queries to each database (made by the user) and answers to the user (made by each database), and show that (1) the lower bound for the communication complexity of any multilinear type (k,l)-PIR is Ω(n1/(l+1)) (Theorem 3.1); (2) the lower bound for the communication complexity of any linear type (k,l)-PIR is Ω(n) (Corollary 3.2); (3) the lower bound for the communication complexity of any affine type (k,l)-PIR is Ω(n1/(l+1)) (Theorem 4.2).

In this paper, we investigate statistical and perfect Knowledge Complexity (KC) with respect ot oracle entropy and average case oracle measures. As main results. we show the following: (1) for any k(n) 1/poly (n), if a language L has perfect KC k(n) + n-ω(1) with respect to oracle entropy measure, then L has perfect KC k(n) with respect to oracle entropy measure (Theorem 3.1); (2) for any k(n) 1/poly(n), if a language L has perfect KC k(n) + n-ω(1) with respect to average case oracle measure, then L has perfect KC k(n) with respect to average case oracle measure (Theorem 3.2); (3) if a language L has statistical KC k(n) ο(1) with respect to oracle entropy measure, then for any ε > 0, L has statistical KC k(n) + 1 + ε with respect to average case oracle measure (Theorem 4.1); and (4) if a language L has perfect KC k(n) ο(1) with respect to oracle entropy measure, then for any ε > 0, L has perfect KC k(n) + 2 + ε with respect to average case oracle measure (Theorem 4.2).