Paper 2020/658

Time-Specific Signatures

Masahito Ishizaka and Shinsaku Kiyomoto

Abstract

In Time-Specific Signatures (TSS) parameterized by an integer $T\in\mathbb{N}$, a signer with a secret-key associated with a numerical value $t\in[0,T-1]$ can anonymously, i.e., without revealing $t$, sign a message under a numerical range $[L,R]$ such that $0\leq L \leq t\leq R\leq T-1$. An application of TSS is anonymous questionnaire, where each user associated with a numerical value such as age, date, salary, geographical position (represented by longitude and latitude) and etc., can anonymously fill in a questionnaire in an efficient manner. In this paper, we propose two \textit{polylogarithmically} efficient TSS constructions based on asymmetric pairing with groups of prime order, which achieve different characteristics in efficiency. In the first one based on a forward-secure signatures scheme concretely obtained from a hierarchical identity-based signatures scheme proposed by Chutterjee and Sarker (IJACT'13), size of the master public-key, size of a secret-key and size of a signature are asymptotically $\mathcal{O}(\log T)$, and size of the master secret-key is $\mathcal{O}(1)$. In the second one based on a wildcarded identity-based ring signatures scheme obtained as an instantiation of an attribute-based signatures scheme proposed by Sakai, Attrapadung and Hanaoka (PKC'16), the sizes are $\mathcal{O}(\log T)$, $\mathcal{O}(1)$, $\mathcal{O}(\log^2 T)$ and $\mathcal{O}(\log T)$, respectively.