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 = h1x1⋯hLxL. 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 concurrently-secure 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.