Paper 2021/698

Multi-Dimensional Sub/Super-Range Signatures

Masahito Ishizaka and Shinsaku Kiyomoto

Abstract

In time-specific signatures (TSS) [Paterson \& Quaglia, SCN'10] [Ishizaka \& Kiyomoto, ISC'20] with $T$ numerical values, each signer is given a secret-key associated with a numerical value $t\in [0,T-1]$ and each signature on a message is generated under a numerical range $[L,R]$ s.t. $0\le L\le R\le T-1$. A signer with $t$ can correctly generate a signature under $[L,R]$ if $t$ is truly included in $[L,R]$, i.e., $t\in [L,R]$. As a generalized primitive of TSS, we propose multi-dimensional \textit{sub}-range signatures (MDSBRS). As a related primitive, we also propose multi-dimensional \textit{super}-range signatures (MDSPRS). In MDSBRS (resp. MDSPRS) with $$ dimensions, each secret-key is associated with a set of $$ ranges $$ s.t. $$ and a threshold value $$, and it correctly produces a signature on any message under a set of $$ ranges $$ s.t. $$, if and only if total number of key-ranges every one $$ of which is a \textit{sub}-range (resp. \textit{super}-range) of the corresponded signature-range $$, i.e., $$ (resp. $$), is more than $$. We show that, by extending (or generalizing) an existing TSS scheme, we obtain MDSBRS and MDSPRS schemes each one of which is secure, i.e., existentially unforgeable and perfectly (signer-)private, under standard assumption and asymptotically efficient.