Proof-of-knowledge of representation of committed value and its applications

We present a zero-knowledge argument system of representation of a committed value. Specifically, for commitments C = Commit1(y), D = Commit2(x), of value y and a tuple x = (x1, . . . , xL), respectively, our argument system allows one to demonstrate the knowledge of (x, y) such that x is a representation of y to bases h1, . . . , hL. That is, y = hx11 · · · hxLL . Our argument system is zero-knowledge and hence, it does not reveal anything such as x or y. We note that applications of our argument system are enormous. In particular, we show how round-optimal cryptography systems, where privacy is of a great concern, can be achieved. We select three interesting applications with the aim to demonstrate the significance our argument system. First, we present a concrete instantiation of two-move concurrently-secure blind signature without interactive assumptions. Second, we present the first compact e-cash with concurrentlysecure withdrawal protocol. Finally, we construct two-move traceable signature with concurrently-secure join. On the side note, we present a framing attack against the original traceable signature scheme within the original model.