\documentclass[sn-mathphys-num]{sn-jnl} \usepackage{graphicx}% \usepackage{multirow}% \usepackage{amsmath,amssymb,amsfonts}% \usepackage{amsthm}% \usepackage{mathrsfs}% \usepackage[title]{appendix}% \usepackage{xcolor}% \usepackage{textcomp}% \usepackage{manyfoot}% \usepackage{booktabs}% \usepackage{algorithm}% \usepackage{algorithmicx}% \usepackage{algpseudocode}% \usepackage{listings}% \theoremstyle{thmstyleone}% \newtheorem{theorem}{Theorem} \newtheorem{proposition}[theorem]{Proposition}% \theoremstyle{thmstyletwo}% \newtheorem{example}{Example}% \newtheorem{remark}{Remark}% \theoremstyle{thmstylethree}% \newtheorem{definition}{Definition}% \raggedbottom \usepackage{mdframed} \newenvironment{protocol}{ \begin{mdframed}[style=figstyle]}{ \end{mdframed}} %\newtheorem{theorem}{Theorem} \newtheorem{hypothesis}[theorem]{Hypothesis} %\newtheorem{corollary}[theorem]{Corollary} \newtheorem{construction}{Construction} \theoremstyle{definition} \newtheorem{action}{Group Action} %\newtheorem{definition}[theorem]{Definition} \newtheorem{assumption}{Assumption} \newtheorem{observation}{Observation} %\newtheorem{example}{Example} %\newtheorem{remark}[theorem]{Remark} %\newcommand{\abs}[1]{\left|{#1}\right|} %cryptocode \newcommand{\bra}[1]{\langle{#1}|} \newcommand{\ket}[1]{|{#1}\rangle} \newcommand{\ip}[2]{\langle{#1}, {#2}\rangle} \newcommand{\braket}[2]{\langle{#1}|{#2}\rangle} \newcommand{\mode}[1]{\textnormal{\textsf{#1}}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\F}{\mathbb{F}} %\renewcommand{\P}{\mathbb{P}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\Matrix}{\mathrm{M}} \newcommand{\Tensor}{\mathrm{T}} \newcommand{\id}{\mathrm{id}} \newcommand{\ATF}{\mathrm{ATF}} \newcommand{\rk}{\mathrm{rk}} \newcommand{\probsty}[1]{\textsf{#1}\xspace} \newcommand{\GI}{\probsty{GI}} %\newcommand{\pk}{\mathrm{pubk}} %cryptocode \newcommand{\PK}{\mathrm{PK}} \newcommand{\SK}{\mathrm{SK}} \newcommand{\CFI}{\probsty{CFI}} \newcommand{\ID}{\probsty{ID}} \newcommand{\QFMI}{\probsty{QFMI}} \newcommand{\pGpI}{$p$\probsty{GpI}} \newcommand{\ATFE}{\probsty{ATFE}} \newcommand{\MEDS}{\probsty{MEDS}} \newcommand{\LESS}{\probsty{LESS}} \newcommand{\ALTEQ}{\probsty{ALTEQ}} \newcommand{\CSIFiSh}{\probsty{CSI-FiSh}} \newcommand{\SeaSign}{\probsty{SeaSign}} \newcommand{\CSIDH}{\probsty{CSIDH}} \newcommand{\ATFEThres}{\probsty{ATFE-Thres}} \newcommand{\BKP}{\probsty{BKP}} \newcommand{\DATFE}{\probsty{DATFE}} \newcommand{\MATFE}{\probsty{MATFE}} \newcommand{\PATFE}{\probsty{PATFE}} \newcommand{\Exp}{\probsty{Exp}} \newcommand{\ATFESig}{\probsty{ATFE-Sig}} \newcommand{\ALTEQOne}{\probsty{ATFEOne}} \newcommand{\ATFA}{\probsty{ATFA}} \newcommand{\psATFE}{\probsty{psATFE}} \newcommand{\EUFCMA}{\probsty{EUF-CMA}} \newcommand{\sEUFCMA}{\probsty{sEUF-CMA}} \newcommand{\EUFNMA}{\probsty{EUFNMA}} \newcommand{\GMW}{\probsty{GMW}} \newcommand{\FS}{\probsty{FS}} \newcommand{\PI}{\probsty{PI}} \newcommand{\TIp}{\probsty{TI}} \newcommand{\DTI}{\probsty{DTI}} \newcommand{\TTI}{\probsty{3TI}} \newcommand{\gainv}{\probsty{GA-Inv}} \newcommand{\gapr}{\probsty{GA-PR}} \newcommand{\msg}{\mathrm{M}} \newcommand{\cB}{\mathcal{B}} \newcommand{\cA}{\mathcal{A}} \newcommand{\cI}{\mathcal{I}} \newcommand{\cX}{\mathcal{X}} \newcommand{\cY}{\mathcal{Y}} \newcommand{\cZ}{\mathcal{Z}} \newcommand{\cK}{\mathcal{K}} \newcommand{\cP}{\mathcal{P}} \newcommand{\cS}{\mathcal{S}} \newcommand{\cD}{\mathcal{D}} \newcommand{\tA}{\mathtt{A}} \newcommand{\class}[1]{\ensuremath{\mathrm{#1}}\xspace} \newcommand{\NP}{\class{NP}} \newcommand{\TI}{\class{TI}} \newcommand{\coNP}{\class{coNP}} %\newcommand{\coAM}{\class{coAM}} %cryptocode %\newcommand{\secpar}{\lambda} %cryptocode \newcommand{\usecpar}{1^\secpar} \newcommand{\veps}{\varepsilon} \newcommand{\bit}{\{0,1\}} \newcommand{\FG}{\mathrm{FG}} \newcommand{\abbrsty}[1]{\ensuremath{\mathrm{#1}}\xspace} \newcommand{\OWA}{\abbrsty{OWA}} \newcommand{\PRA}{\abbrsty{PRA}} \newcommand{\PROD}{\abbrsty{PROD}} \newcommand{\INV}{\abbrsty{INV}} \newcommand{\QRO}{\abbrsty{QRO}} \newcommand{\GLAT}{\abbrsty{GLAT}} \newcommand{\pg}{\mathcal{G}} \newcommand{\params}{\texttt{params}} \newcommand{\attack}{\mathcal{A}} \newcommand{\hvsim}{\mathcal{S}} \newcommand{\dualkey}{{\widetilde{pk}}} \newcommand{\signlist}{\mathcal{L}} \newcommand{\PRF}{\mathsf{PRF}} \newcommand{\Aut}{\mathrm{Aut}} \newcommand{\Stab}{\mathrm{Stab}} \newcommand{\orbit}{\mathcal{O}} \newcommand{\lencom}{{\ell_{\mathrm{in}}}} \newcommand{\lench}{{\ell_{\mathrm{ch}}}} \newcommand{\lenr}{{\ell_{\mathrm{re}}}} \newcommand{\prep}{\ell} \newcommand{\algstyle}[1]{\textsc{#1}\xspace} \newcommand{\ids}{\algstyle{ID}} \newcommand{\gaids}{\algstyle{GA-ID}} \newcommand{\kg}{\algstyle{KG}} \newcommand{\dkg}{\algstyle{KG}^*} \newcommand{\skg}{\algstyle{KeyGen}} %\renewcommand{\sign}{\algstyle{Sign}} %cryptocode \newcommand{\vrfy}{\algstyle{Verify}} \newcommand{\unruhsign}{\algstyle{SIGN}} \newcommand{\gasign}{\algstyle{GA-SIGN}} \newcommand{\fssign}{\algstyle{FS-SIGN}} \newcommand{\gafssign}{\algstyle{GA-FS-SIGN}} %\newcommand{\prg}{\algstyle{PRG}} %cryptocode \newcommand{\ggm}{\algstyle{GGM}} \newcommand{\tr}[1]{#1^{\mathrm{t}}} %\newcommand{\sEUFCMA}{\probsty{sEUF-CMA}} % zhili's macros \newcommand{\ComSet}{\mathsf{ComSet}} \newcommand{\ChaSet}{\mathsf{ChSet}} \newcommand{\ResSet}{\mathsf{ResSet}} \newcommand{\com}{\mathsf{com}} \newcommand{\Com}{\mathsf{Com}} %\newcommand{\res}{\prover.\mathsf{Res}} \newcommand{\ver}{\verifier.\mathsf{Ver}} \newcommand{\gen}{\mathsf{Gen}} \newcommand{\lgen}{\mathsf{LossyGen}} \newcommand{\Igen}{\mathsf{IGen}} \newcommand{\rsample}{\gets_R} \newcommand{\sgn}{\mathsf{Sign}} \newcommand{\vrf}{\mathsf{Verify}} \newcommand{\pkey}{\mathsf{pk}} \newcommand{\skey}{\mathsf{sk}} \newcommand{\mpk}{\mathsf{mpk}} \newcommand{\msk}{\mathsf{msk}} \newcommand{\ppp}{\mathsf{pp}} \newcommand{\vkey}{\mathsf{vk}} \newcommand{\ls}{\mathsf{ls}} \newcommand{\Time}{\mathsf{Time}} \newcommand{\Advantage}{\mathsf{Adv}} \let\O\undefined \let\S\undefined \DeclareMathOperator{\O}{\mathrm{O}} \DeclareMathOperator{\S}{\mathrm{S}} %\DeclareMathOperator{\adv}{\mathbf{Adv}} %cryptocode %\DeclareMathOperator{\poly}{\mathrm{poly}} %cryptocode %\DeclareMathOperator{\negl}{\mathrm{negl}} %cryptocode \newcommand{\poly}{\mathsf{poly}} \newcommand{\DS}{\mathsf{DS}} \newcommand{\DSKGen}{\mathsf{DS.KGen}} \newcommand{\DSSign}{\mathsf{DS.Sign}} \newcommand{\DSVer}{\mathsf{DS.Verify}} \newcommand{\KGen}{\mathsf{KeyGen}} \newcommand{\Sign}{\mathsf{Sign}} \newcommand{\Ver}{\mathsf{Verify}} \newcommand{\Setup}{\mathsf{Setup}} \newcommand{\IBS}{\mathsf{IBS}} \newcommand{\KeyDer}{\mathsf{KeyDer}} \newcommand{\uskey}{\mathsf{usk}} \newcommand{\EUFIDCMA}{\probsty{EUF-ID-CMA}} \newcommand{\RS}{\mathsf{RS}} \newcommand{\RSSetup}{\mathsf{RS.Setup}} \newcommand{\RSKGen}{\mathsf{RS.KGen}} \newcommand{\RSSign}{\mathsf{RS.Sign}} \newcommand{\RSVer}{\mathsf{RS.Verify}} \newcommand{\sample}{\overset{\$}{\leftarrow}} \newcommand{\TS}{\mathsf{TS}} \newcommand{\TSSetup}{\mathsf{TS.Setup}} \newcommand{\TSKGen}{\mathsf{TS.KGen}} \newcommand{\TSSign}{\mathsf{TS.Sign}} \newcommand{\TSVer}{\mathsf{TS.Verify}} \newcommand{\TSCom}{\mathsf{TS.Combine}} \newcommand{\game}{\mathsf{Game}} \newcommand{\W}{\mathsf{W}} \newcommand{\ccase}{\mathsf{Case}} \newcommand{\HVZK}{\textsf{HVZK}} \newcommand{\DualATFE}{\textsf{DualRing-ATFE}} \newcommand{\Sim}{\textsf{Sim}} \newcommand{\Ext}{\textsf{Ext}} \newcommand{\ch}{\mathsf{ch}} \newcommand{\rsp}{\mathsf{rsp}} %\newcommand{\P}{\mathsf{P}} \newcommand{\V}{\mathsf{V}} \newcommand{\GAIP}{\mathsf{GAIP}} \newcommand{\KGAIP}{\textsf{K-GAIP}} \newcommand{\KPseudo}{\textsf{K-Pseudorandomness}} \newcommand{\gact}[2]{\alpha(#1,#2)} \newcommand{\linkgact}[2]{\beta(#1,#2)} \newcommand{\GA}[2]{\ensuremath{\mathsf{\gact{#1}{#2}}}\xspace} \newcommand{\GASig}{\ensuremath{\mathsf{\gact{G}{S}}}\probsty{-GMW-FS-lossy}} \usepackage[n,operators,advantage,sets,adversary,landau,probability,notions,logic,ff,mm,primitives,events,complexity,asymptotics,keys]{cryptocode} \setlength{\parskip}{8pt} \begin{document} \title[Article Title]{MQIBS: An Efficient Multivariate Identity-based Signature from Sigma Protocols with Helper} \author[1,2]{\fnm{Le} \sur{Van Luyen}}\email{lvluyen@hcmus.edu.vn} \affil[1]{Faculty of Mathematics and Computer Science, University of Science, Ho Chi Minh City, Vietnam} \affil[2]{Vietnam National University, Ho Chi Minh City, Vietnam} \abstract{Identity-based signature (IBS) is an important cryptographic primitive which allows authentication of a party’s public key without the need for certificates. In this paper, we construct a post-quantum provable identity-based signature scheme from multivariate polynomials. Our scheme is constructed from the sigma protocols with helper by Beullens at Eurocrypt 2020 and the Fiat-Shamir paradigm. Concrete choice of parameters show that our scheme is more efficient than existing multivariate IBS schemes.} \keywords{Identity-based signatures, Multivariate Polynomials, MQ Problem} \maketitle \section{Introduction} %\subsection{Post-quantum Cryptography} Post-quantum Cryptography (PQC) has become an emerging research direction since the announcement of NIST (National Institute of Standards and Technology) for the PQC standardization process since 2016~\cite{NIST}. NIST selected several candidates for standardization in 2022 and called for additional digital signatures whose the first round deadline was June 2023~\cite{NIST2}. Among the candidates for PQC, multivariate cryptography is one of the main candidates for this standardization~\cite{NIST,NIST2}. It is shown in ~\cite{ChenCCCDKLY09,BogdanovERW08} that multivariate schemes are very fast in general and suitable for limited computational resources, such as smart cards ran RFID chips. The security of multivariate schemes is normally based on the hardness of the \textit{MQ-Problem}, which is proven to be NP-Hard $\mathbb{F}_2$~\cite{book}, that asks for a solution of a given system of multivariate quadratic polynomials over the field $\mathbb{F}_q$. Multivariate cryptography is dated back to the early work of Matsumoto and Imai in 1988~\cite{MI78}, and since then, there has been a rich development of designing multivariate schemes in several directions. Notably in the history is the (Unbanlanced) Oil and Vineger (UOV) signature scheme by Patarin et al. after he broke the Matsumoto-Imai scheme~\cite{Patarin95,KipnisPG99}. Since then, there have been the main direction on improving the UOV schemes, including the multi-layer variant Rainbow by Ding and Schmidt~\cite{DingS05}, and its cyclic version~\cite{PetzoldtBB10}. Rainbow was one of the main candidates in the NIST PQC Process until Round 3, but it was not selected due to the attack by Beullens~\cite{Beullens22} which reduced the proposed security levels. Since then, the intention focuses back to improving the UOV scheme. Especially there have been many such submissions in the round 1 of NIST Additional PQC Signatures~\cite{NIST2} including for example MAYO, PROV, QR-UOV and TUOV; see~\cite{NIST2} for the details. One drawback of UOV signatures is that they do not have a provable security proof. Recent submissions like MAYO or PROV do have such a proof but it was reduced to a new assumption, not the NP-complete MQ problem as expected. For a provable secure construction, another direction of construction multivariate signatures is to follow the Fiat-Shamir paradigm~\cite{FiatS86}. In this case, one needs first an identification scheme and the Fiat-Shamir transformation converts it into a secure digital signature. The first multivariate identification schemes were proposed by Sakumoto et al.~\cite{SakumotoSH11}. They include a 3-pass and 5-pass identification schemes. The 5-pass identification was used to design the MQDSS signature~\cite{MQDSS,ChenHRSS16} which was a candidate for NIST PQC Round 2. However, it was broken by Kales and Zaverucha~\cite{KalesZ20}. All work in this direction is hence focusing on improving one from 3-pass identification scheme by Sakumoto et al.~\cite{SakumotoSH11}, including~\cite{FurueDT19,AS19}. Recently, Beullens~\cite{Beullens22} developed sigma protocols with helper, inspring from the work by Katz et al.~\cite{KKW18}, and applied to the 3-pass identification scheme by Sakumoto et al.~\cite{SakumotoSH11} to obtain a more efficient multivariate digital signature compared to MQDSS~\cite{MQDSS}. %\subsection{Identity-based Signatures} Identity-Based Signature (IBS), proposed by Shamir~\cite{Shamir84}, allows for the generation of a public key for an entity using only some basic scheme parameters and an identifier string (such as an email address or phone number). A private key generator (PKG) derives private keys from a master secret and distributes them to the entities involved in the scheme. This approach removes the requirement for certificates, unlike in traditional public key infrastructure. There have been many post-quantum constructions of IBS. In the area of multivarate cryptography, there have been several proposals for IBS based on UOV such as~\cite{ShenTX13,ChenLND19} or Rainbow such as~\cite{Luyen19,ChenLND19}. Recently, there has been a proposal for identity-based signature by Debnath et al.~\cite{DebnathMSPK23}. In this paper, we investigate the sigma protocol with helper by Beullens and design an identity-based signature scheme from multivariate polynomials, which we call MQIBS. Our MQIBS scheme enjoys the security reduction to the underlying MQ problem and more efficient then existing schemes; see Table~\ref{Table: compare} for the details. The rest of the paper is organized as the following. In Section 2, we recall some basic notions on commitment schemes and identity-based signatures including their definition and security model. We recall the sigma protocols with helper from Beullens~\cite{Beullens22} in Section 3 and our construction of MQIBS is presented in Section 4. In Section 5, we provide the choice of parameters and compute the key and signature size of MQIBS as well as a comparison between MQIBS with existing multivariate IBS. Section 6 concludes the paper. %\subsection{Our contribution} \section{Preliminaries} %\subsection{Multivariate Public Key Cryptography} \iffalse To build a multivariate public key cryptosystem, one starts with an easily invertible quadratic map $\mathcal{F}: K^n \to K^m$ ({\it central map}). To hide the structure of $\mathcal{F}$ in the public key, one composes it with two invertible affine (or linear) maps $\mathcal{T}:K^m \to K^m$ and $\mathcal{S}: K^n \to K^n$. The \textit{public key} is therefore given by $\mathcal{P}=\mathcal{T} \circ \mathcal{F} \circ \mathcal{S}: K^n \to K^m$. The \textit{private key} consists of $\mathcal{T}, \mathcal{F}$ and $ \mathcal{S}$. In this paper we consider multivariate signature schemes. For these schemes, we require $n \geq m$, which ensures that every message has a signature.\\ \noindent {\it Signature Generation}: To generate a signature for a message (or its hash value) $\mathbf{d} \in K^m$, one computes recursively $\mathbf{w}=\mathcal{T}^{-1}(\mathbf{d}) \in K^m,~ \mathbf{y}=\mathcal{F}^{-1}(\mathbf{w}) \in K^n$ and $\mathbf{z}=\mathcal{S}^{-1}(\mathbf{y})$. Then ${\bf z} \in K^n$ is the signature of the message $\bf d$. Here, ${\cal F}^{-1}({\bf w})$ means finding one (of possibly many) pre-image of $\bf w$ under the central map $\cal F$.\\ \\ \noindent {\it Signature Verification}: To check the authenticity of a signature ${\bf z} \in K^n$, the verifier simply computes ${\bf d}'= {\cal P}({\bf z})$. If the result is equal to the message $\bf d$, the signature is accepted, otherwise rejected. \begin{figure} \begin{center} \begin{picture}(250,110) \put(70,100){\textbf{Signature Generation}} \put(10,80){${\bf d} \in K_q^m$} \put(45,83){\vector(1,0){30}} \put(80,80){${\bf w} \in K_q^m$} \put(115,83){\vector(1,0){30}} \put(150,80){${\bf y} \in K_q^n$} \put(185,83){\vector(1,0){30}} \put(220,80){${\bf z} \in K_q^n$} \put(25,25){\vector(0,1){50}} \put(25,25){\line(1,0){210}} \put(235,25){\line(0,1){50}} \put(130,30){$\cal P$} \put(55,85){${\cal T}^{-1}$} \put(125,85){${\cal F}^{-1}$} \put(195,85){${\cal S}^{-1}$} \put(95,10){\textbf{Verification}} \end{picture} \end{center} \caption{Two processes of multivariate signature schemes} \label{figmultisig} \end{figure} \fi \subsection{Commitment Schemes} A commitment scheme $\Com: \{0,1\}^\lambda\times\{0,1\}^* \to \{0,1\}^{2\lambda}$, where $\lambda$ is the security parameter, is a function that takes as input $\lambda$ uniformly random bit $r\in\{0,1\}^\lambda$ and a message $m\in\{0,1\}^*$, outputs a $2\lambda$ bit long commitment $\Com(r,m)$. We require the following two properties of a commitment scheme (\cite{Beullens20}). \begin{definition}[Computational binding] For an adversary $\mathcal{A}$ we define its advantage for the commitment binding game as $$\sf{Adv}_\com^{\sf{Binding}}(\adv) = \Pr[\Com(r,m)=\Com(r',m') | (r,m,r',m')\gets\adv(1^\lambda)].$$ We say that $\Com$ is computationally binding if for all polynomial time algorithms $\adv$, the advantage $\sf{Adv}_\com^{\sf{Binding}}(\adv)$ is a negligible function of the security parameter $\lambda$. \end{definition} \begin{definition}[Computational hiding] For an adversary $\adv$ we define the advantage for the commitment hiding game for a pair of messages $m,m'$ as $$ \sf{Adv}_\Com^{\sf{Hiding}}(\adv,m,m')=|\Pr_{r\gets\{0,1\}^\lambda}[1=\adv(\Com(r,m)] - \Pr_{r\gets\{0,1\}^\lambda}[1=\adv(\Com(r,m')]|. $$ We say that $\Com$ is computationally hiding if for all polynomial time algorithms $\adv$, and every pair of messages $m,m'$ the advantage $\sf{Adv}_\Com^{\sf{Hiding}}(\adv,m,m')$ is a negligible function of the security parameter $\lambda$. \end{definition} \subsection{Identity-based Signature Scheme} An identity-based signature (IBS) scheme is a tuple of polynomial-time algorithms $\IBS = (\Setup, \KeyDer, \Sign, \Ver)$ as follows: \begin{description} \item[$\Setup(1^\lambda)$:] On input the security parameter $\lambda$, it outputs the master public key and secret key pair $9\mpk,\msk)$. \item[$\KeyDer(\msk,\id)$:] On input the master secret key $\msk$ and a user identity $ID$, it generates the user secret key $\uskey$. \item[$\Sign(\mpk,\uskey,M)$:] On input the master public key $\mpk$, the user secret key $\uskey$ and a message $M$, it outputs a signature $\sigma$. \item[$\Ver(\mpk,\id,\sigma,M)$:] On input the master public key $\mpk$, user identity $ID$, a signature-message pair $(\sigma,M)$, it outputs $1$ for acceptance and $0$ for rejection. \end{description} We consider following properties for an IBS scheme. First, the correctness guarantees that a signature generated by honest signer will always pass the verification algorithm. \begin{definition}[Correctness] We say that an identity-based signature $\sf{IBS}$ is correct, if for all $\lambda \in \mathbb{N}$, all identity $\id \in \mathcal{ID}$ and all message $M \in \mathcal{M} $ that if $ (\sf{mpk}, \msk) \leftarrow \sf{Setup}(1^\lambda)$, $\sf{usk}_{\id} \leftarrow \sf{KeyDer}(\mpk, \msk, \id)$, $\sigma \leftarrow \mathsf{Sign}(\mpk, \mathsf{usk}_{\id}, M)$ then it holds that $$ \Pr [\mathsf{Verify}(\mpk, \id, \sigma, M) = 1] =1-\sf{negl}(\lambda). $$ \end{definition} Second, it is requires that an adversary cannot create a new tuple (id, message, signature) for an identity and a message that it hasn't been queried before, given that it has already seen some identities' secret keys and signatures for some tuples (identity, message) of its choice. \begin{definition}[EUF-ID-CMA] We say that an identity-based signature $\sf{IBS}$ is $\sf{EUF\text{-}ID\text{-}CMA}$ if, for every PPT adversary $\adv$, it holds that $\adv$ has a negligible advantage in the following experiment. \newline $\mathsf{Exp}_{\adv}^\mathsf{EUF\text{-}ID\text{-}CMA}(\lambda):$ \begin{itemize} \item [1.] The challenger generates $(\mpk,\msk) \gets \sf{Setup}(1^\lambda)$ and sets $\mathcal{Q}_{\id} \gets \emptyset$, $\hat{\mathcal{Q}}_{\id} \gets \emptyset$, $\mathcal{Q}_{\sf{usk}_\id} \gets \emptyset$ and $\mathcal{Q}_{M} \gets \emptyset$. \item [2.] The challenger gives $\mpk$ to the adversary $\adv$. Moreover, $\adv$ can access two signing oracles $\mathcal{O}_{\sf{KeyDer}}$, $\mathcal{O}_{\sf{Sign}}$, where \begin{itemize} \item[i.] Key derivation oracle $\mathcal{O}_{\sf{KeyDer}}$: On input a key derivation query $\id \in \mathcal{ID}$, the oracle $\mathcal{O}_{\sf{KeyDer}}$ checks whether $(\id, \cdot) \in \mathcal{Q}_{\id}$. If $(\id, \cdot) \in \mathcal{Q}_{\id}$ for some $\mathsf{usk}_{\id} \in \mathcal{USK}$, it returns $\mathsf{usk}_{\id}$. Otherwise, it returns $\mathsf{usk}_{\id} \gets \mathsf{KeyDer}(\mpk, \msk, \id)$ and sets $\mathcal{Q}_{\id} \gets \mathcal{Q}_{\id} \cup \{(\id, \sf{usk}_{\id})\}$ \item[ii.] Signing oracle $\mathcal{O}_{\sf{Sign}}$: On input a signing query $(\id, M) \in \mathcal{ID} \times \mathcal{M}$, the oracle $\mathcal{O}_{\sf{Sign}}$ sets $\mathcal{Q}_M \gets \mathcal{Q}_{M} \cup \{ (\id, M)\}$ and checks whether $(\id,\cdot) \in \mathcal{Q}_{\id}$ \begin{itemize} \item If $(\id, \cdot) \in \mathcal{Q}_{\id}$ for some $\sf{usk}_{\id} \in \mathcal{USK}$, returns $\sigma \leftarrow \Sign(\mpk, \sf{usk}_{\id}, M)$. \item If there does not exist $(\id, \cdot) \in \mathcal{Q}_{\id}$ for any $\sf{usk}_{\id} \in \mathcal{USK}$, it computes $\sf{usk}_{\id} \gets \sf{KeyDer}(\mpk, \msk, \id)$, return $\sigma \gets \sf{Sign}(\mpk, \sf{usk}_{\id}, M)$ and sets $\mathcal{Q}_{\id} \gets \mathcal{Q}_{\id} \cup \{ (\id, \sf{usk}_{\id}) \}$. \end{itemize} \end{itemize} \item [3.] In the end, the adversary outputs a forgery $(\id^*,M^*,\sigma^*)$. \item [4.] The challenger outputs 1 if the following three conditions are hold: \begin{itemize} \item There does not exist $(\id^*, \cdot) \in \mathcal{Q}_{\id}$ for any $\sf{usk}_{\id^*} \in \mathcal{USK}$, \item $(\id^*,M^*) \notin \mathcal{Q}_M$, \item $\sf{Verify}(\mpk, \id^*, M^*, \sigma^*) = 1$ \end{itemize} \end{itemize} The advantage of $\adv$ is defined by $\sf{Adv}_{\adv}^\mathsf{EUF\text{-}ID\text{-}CMA}(\lambda) = \Pr[\sf{Exp}_{\adv}^\mathsf{EUF\text{-}ID\text{-}CMA}(\lambda)=1].$ %\jnote{It is better to define the advantage of $\adv$ more above. It is also better to input a security parameter $\lambda$. e.g., $\sf{Adv}_{\adv}^\mathsf{EUF\text{-}ID\text{-}CMA}(\lambda)$, $\sf{Exp}_{\adv}^\mathsf{EUF\text{-}ID\text{-}CMA}(\lambda)$. Actually, it is used at the final part of the proof of Thm 1.} \end{definition} \section{Sigma Protocols with Helper} \label{sec: Sigma with helper} Beullens~\cite{Beullens20} introduced a Sigma protocol with a helper, which involves a three-round Sigma protocol that includes a trusted third party, known as the helper. At the start of each protocol execution, the helper runs a setup algorithm using a random seed. The helper then sends auxiliary information to the verifier and provides the seed value used in the setup algorithm to the prover.. The syntax can be summarized in the Figure~\ref{Fig: sigma with helper}. \begin{definition}[Sigma protocol with helper~\cite{Beullens20}]\label{Defn: Sigma with Helper} A protocol is a sigma protocol with helper for relation $R$ with challenge space $\mathcal{C}$ if it is of the form of Fig.~\ref{Fig: sigma with helper} and satisfies: \begin{description} \item[Completeness.] If all parties $(\sf{Helper}, \sf{Prover}, \sf{Verifier})$ follow the protocol on input $(x, w) \in R$, then the verifier always accepts. \item[2-Special soundness.] From an adversary $\adv$ that outputs with noticeable probability two valid transcripts $(x, \sf{aux}, \com, ch,\sf{rsp})$ and $(x, \sf{aux}, \com, ch',\sf{rsp}')$ with $ch\ne ch'$ and where $\sf{aux} = \Setup(\sf{seed})$ for some seed value $\sf{seed}$ (not necessarily known to the extractor) one can efficiently extract a witness $w$ such that $(x, w) \in R$. \item[Special honest-verifier zero-knowledge.] There exists a PPT simulator $S$ that on input $x$, a random seed value $\sf{seed}$ and a random challenge $ch$ outputs a transcript $(x, \sf{aux}, \com, ch,\sf{rsp})$ with $\sf{aux} = \Setup(\sf{seed})$ that is computationally indistinguishable from the probability distribution of transcripts of honest executions of the protocol on input $(x, w)$ for some $w$ such that $(x, w) \in R$, conditioned on the auxiliary information being equal to $aux$ and the challenge being equal to $ch$. \end{description} \end{definition} \begin{figure}\label{Fig: sigma with helper} \begin{mdframed} $\textbf{Helper}(x)$\\ \pcind $\mathsf{seed} \sample \{0,1\}^\lambda$\\ \pcind $\mathsf{aux} \leftarrow \text{Setup}(\sf{seed})$\\ \pcind Send $\mathsf{seed}$ to the prover and $\mathsf{aux}$ to the verifier. \begin{center} \pseudocode{ \textbf{ Prover}(x,w,\mathsf{seed}) \< \< \textbf{Verifier}(x, \mathsf{aux}) \\% [0.1][\hline] \<\< \\[-0.5\baselineskip] \sf{com}, \mathsf{P}_{\mathsf{state}} \leftarrow P_1(x,w,\mathsf{seed}) \< \< \\ \< \sendmessageright{length=2cm,top=\sf{com}} \< \\ \< \< ch \sample \mathcal{C}\\ \< \sendmessageleft{length=2cm,top=\sf{c}} \< \\ \sf{rsp} \gets P_2(\mathsf{P}_{\mathsf{state}}, ch)\< \< \\ \< \sendmessageright{length=2cm,top=\sf{rsp}} \< \\ \< \< \textbf{return} \leftarrow V(x, \mathsf{aux},\mathsf{com}, ch, \sf{rsp}) } \end{center} \end{mdframed} \caption{The structure of a sigma protocol with trusted setup.} \end{figure} Beullens then transformed sigma protocols with helper in Figure~\ref{Fig: sigma with helper} into a standard zero-knowledge proof of knowledge without helper using the ``Cut-and-choose" approach by Katz et al.~\cite{KKW18}. We recall it in Figure~\ref{Fig: sigma without helper}. \begin{figure}\label{Fig: sigma without helper} \begin{mdframed} \begin{center} \pseudocode{ \textbf{ Prover}\< \< \textbf{Verifier} \\% [0.1][\hline] \<\< \\[-0.5\baselineskip] \textbf{for}~i\in\{1,\dots,k\}~\textbf{do} \< \< \\ ~\quad \sf{seed}_i\sample\{0,1\}^\lambda \< \< \\ ~\quad \sf{aux}_i\gets\Setup(\sf{seed}_i) \< \< \\ ~\quad \sf{com}_i\gets P_1(x,w,\sf{seed}_i) \< \< \\ \textbf{end for} \< \< \\ \< \sendmessageright{length=2cm,top=${\sf{aux}_i,\sf{com}_i~\forall i}$} \< \\ \< \< I \sample \{1,\dots,k\}\\ \< \< ch\sample\mathcal{C} \\ \< \sendmessageleft{length=2cm,top={(I,ch)}} \< \\ \sf{rsp} \gets P_2(x,w,\sf{seed}_I,\sf{com}, ch)\< \< \\ \< \sendmessageright{length=2cm,top={$\sf{seed}_i~\forall i\ne I,\sf{rsp}$}} \< \\ \< \< \textbf{if}~\exists i\ne I: \sf{aux}_i\ne\Setup(\sf{seed}_i)\\ \<\< \textbf{then} \\ \<\< ~\quad \textbf{return}~0 \\ \<\< \textbf{end if} \\ \<\< \textbf{return } \leftarrow V(x, \mathsf{aux},\mathsf{com}, ch, \sf{rsp}) } \end{center} \end{mdframed} \caption{Zero-knowledge proof without helper.} \end{figure} \begin{theorem}[{\cite[Theorem 3]{Beullens20}}] Let $(\Setup, P_1,P_2,V)$ be a sigma protocol with helper and challenge space $\mathcal{C}$, if the used commitment scheme is hiding, then the protocol of Fig.~\ref{Fig: sigma without helper} is an honest-verifier zero knowledge proof of knowledge with challenge space $\{1,\dots, k\}\times\mathcal{C}$ and $\max(k, |\mathcal{C}|) + 1$-special soundness (and hence it has soundness error $\max(\frac{1}{k},\frac{1}{|\mathcal{C}|})$. \end{theorem} \section{Construction of MQIBS} \label{sec: construction} \subsection{Sigma Protocol with Helper for MQ Problem} In this section, we recall the sigma protocl with helper for MQ Problem from~\cite{Beullens20} in proving knowledge of a solution of a system of multivariate quadratic equations over a finite field $\mathbb{F}_q$. This scheme improves the previous two schemes by Sakumoto et al.~. In particular, the two schemes by Sakumoto et al. has soundness errors $\frac{2}{3}$ and $\frac{1}{2}+\frac{1}{2q}$ respectively while the one with helper has soundness error to only $\frac{1}{q}$. Let $\mathcal{F}:\mathbb{F}_q^n\to\mathbb{F}_q^m$ is a multivariate quadratic map of $m$ polynomials in $n$ variables, define the polar form of $\mathcal{F}$ as $$\mathcal{G}(\mathbf{x},\mathbf{y}) := \mathcal{F}(\bf{x}+\bf{y}) -\mathcal{F}(\bf{x}) -\mathcal{F}(\bf{y}).$$ Note that $\mathcal{G}$ is linear in both $\bf{x}$ and $\bf{y}$. The sigma protocol is described in Figture~\ref{Fig: sigma MQ}. \begin{figure} \begin{mdframed} $\textbf{Helper}(\mathcal{F})$\\ \pcind $\mathsf{seed} \sample \{0,1\}^\lambda$\\ \pcind Generate $\mathbf{e}\in\mathbb{F}_q^m$ and $\mathbf{t}, \mathbf{r}_0\in\mathbb{F}_q^n$ from $\sf{seed}$.\\ \pcind \textbf{for} each $c\in\mathbb{F}_q$~{\bf do} \\ \pcind ~\quad ${\bf e}_c\gets c{\cal F}({\bf r}_0)-{\bf e}$ \\ \pcind ~\quad ${\bf t}_c\gets c{\bf r}_0-{\bf t}$ \\ \pcind ~\quad Generate commitment randomness $\bf{r}_c\in\{0,1\}^\lambda$ from~$\sf{seed}$.\\ \pcind ~\quad $\com_c\gets\Com(\bf{r}_c,(\bf{e}_c,\bf{t}_c))$\\ \pcind {\bf end for}\\ \pcind ${\sf aux}\gets[\com_c | c\in\mathbb{F}_q$] \\ \pcind Send $\mathsf{seed}$ to the prover and $\mathsf{aux}$ to the verifier. \begin{center} \pseudocode{ \textbf{Prover}(\mathcal{F}, {\bf s}, \sf{seed})\< \< \textbf{Verifier}(\mathcal{F}, {\bf v}, \sf{aux}) \\% [0.1][\hline] \<\< \\[-0.5\baselineskip] \text{Regenerate}~ {\bf e}, {\bf t}, {\bf r}_0~\text{from}~\sf{seed} \< \< \\ {\bf r}\gets\{0,1\}^\lambda \<\< \\ \com\gets\Com({\bf r}, ({\bf r}_1, {\bf e}+\mathcal{G}({\bf r}_1,{\bf t}))) \<\< \\ \< \sendmessageright{length=2cm,top=$\com$} \< \\ \< \< \alpha\sample\mathbb{F}_q \\ \< \sendmessageleft{length=2cm,top=$\alpha$} \< \\ \text{Recompute}~{\bf r}_\alpha, {\bf e}_\alpha, {\bf t}_\alpha~\text{from}~\sf{seed}\< \< \\ \< \sendmessageright{length=2cm,top={$({\bf r}, {\bf r}_\alpha, {\bf r}_1,{\bf e}_\alpha, {\bf t}_\alpha)$}} \< \\ \< \< {\bf x}\gets\alpha({\bf v}-\mathcal{F}({\bf r}_1))-{\bf e}_\alpha-\mathcal{G}({\bf r}_1,{\bf t}_\alpha) \\ \<\< b_1\gets \com=\Com({\bf r}, ({\bf r}_1,{\bf x}))\\ \<\< b_2\gets\com_\alpha = \Com({\bf r}, ({\bf e}_\alpha, {\bf t}_\alpha)) \\ \<\< \textbf{Return}~b_1\wedge b2 } \end{center} \end{mdframed} \caption{Zero-knowledge proof without helper.} \label{Fig: sigma MQ} \end{figure} \begin{theorem}[{\cite[Theorem 1]{Beullens20}}] Suppose the used commitment scheme is computationally binding and computationally hiding, then the protocol of Fig.~\ref{Fig: sigma MQ} is a sigma protocol with trusted setup as in Definition~\ref{Defn: Sigma with Helper} with challenge space $\mathbb{F}_q$. \end{theorem} \subsection{Our Identity-based Signature Construction} In this Section, we propose a construction of an identity-based signature from the sigma protocol with helper presented in Figure~\ref{Fig: sigma MQ}, which we call MQIBS. The idea is to follow the construction by Kiltz et al.~\cite{KiltzN09}. The MQIBS scheme consists of the following polynomial-time algorithms. \begin{description} \item[$\Setup(1^\lambda)$:] Given security parameter $\lambda$, output public parameters consisting of $m,n,q,k$, a random system of polynomials $\mathcal{F}:\F_q^n\to\F_q^m$, and a hash function $H:\{0,1\}^*\to \{1,\dots,k\}\times\mathbb{F}_q$, and do the following: \begin{itemize} \item Choose ${\bf s}\sample\F_q$ and compute ${\bf v}:=\mathcal{F}({\bf s})\in\F_q^m$. \item Output $\mpk = (\mathcal{F},{\bf v})$ and $\msk={\bf s}$. \end{itemize} \item[$\KeyDer(\msk,\id)$:] Given the master secret key $\msk ={\bf s}$ and a user identity $\id$, do the following: \begin{itemize} \item Choose a random system $\mathcal{F}_\id:\F_q^n\to\F_q^m$, ${\bf s}_\id\sample\F_q^n$ and compute ${\bf v}_\id=\mathcal{F}_\id({\bf s}_\id)$. \item For $i\in\{1,\dots,k\}$ do \begin{itemize} \item ${\sf seed}_i\sample\{0,1\}^\lambda$ \item Compute ${\sf aux}_i$ as in the procedure of Helper($\mathcal{F}$) in Figure~\ref{Fig: sigma MQ}. \item Compute $\com_i$ as in the first step of the Prover as in Figure~\ref{Fig: sigma MQ}. \end{itemize} \item Set ${\sf COM}_\id: = (\com_i,{\sf aux}_i)_{i\in\{1,\dots,k\}}$. \item Compute $(I,\alpha) := H({\sf COM}_\id,\mathcal{F}_\id\|\id)$ \item Retrieve ${\sf seed}_I$ and compute the response $\rsp$ (using ${\bf s}$) as in the response by the Prover as in Figure~\ref{Fig: sigma MQ}. Set ${\sf RSP}_\id = (\rsp, {\sf seed}_i~\forall i\ne I)$. \item Output the user secret key as $\uskey=({\bf s}_\id, {\bf v}_i, \mathcal{F}_\id, {\sf COM}_\id, {\sf RSP}_\id)$. \end{itemize} \item[$\Sign(\mpk,\uskey,M)$:] Given the master public key $\mpk$, the user secret key $\uskey$ of a user $\id$ and a message $M$, do the following: \begin{itemize} \item Parse $\uskey$ as $({\bf s}_\id, {\bf v}_\id, \mathcal{F}_\id, {\sf COM}_\id, {\sf RSP}_\id)$. \item For $i\in\{1,\dots,k\}$ do \begin{itemize} \item ${\sf seed}_i\sample\{0,1\}^\lambda$ \item Compute ${\sf aux}_i$ as in the procedure of Helper($\mathcal{F}_\id$) in Figure~\ref{Fig: sigma MQ}. \item Compute $\com_i$ as in the first step of the Prover as in Figure~\ref{Fig: sigma MQ}. \end{itemize} \item Set ${\bf COM}: = (\com_i,{\sf aux}_i)_{i\in\{1,\dots,k\}}$. \item Compute $(J,c) := H({\bf COM},M)$ \item Retrieve ${\sf seed}_J$ and compute the response $\rsp$ (using ${\bf s}_\id$) as in the response by the Prover as in Figure~\ref{Fig: sigma MQ}. Set ${\sf RSP} = (\rsp, {\sf seed}_i~\forall i\ne I)$. \item Output a signature as $\sigma=({\bf v}_\id, \mathcal{F}_\id, {\sf COM}_\id, {\sf RSP}_\id, {\sf COM}, {\sf RSP})$. \end{itemize} \item[$\Ver(\mpk,\id,\sigma,M)$:] Given a master public key $\mpk$, an identity $\id$, a signature-message pair $\sigma$ and $M$, do the following: \begin{itemize} \item Parse the signature $\sigma$ as $\sigma=({\bf v}_\id, \mathcal{F}_\id, {\sf COM}_\id, {\sf RSP}_\id, {\sf COM}, {\sf RSP})$. \item Use $({\bf v}_\id, \mathcal{F}_\id,{\sf COM}, {\sf RSP})$ and $M$ do the verification as by the Verifier in Figure~\ref{Fig: sigma MQ}. Let the result of the verification be $b_1$. \item Use $\mpk$, $\mathcal{F}_\id\|\id$, ${\sf COM}_\id, {\sf RSP}_\id$ as an input for the verification procedure as in Figure~\ref{Fig: sigma MQ}. Call the result of this process to be $b_2$. \item If $b_1=b_2=1$ then output 1, otherwise output 0. \end{itemize} \end{description} \paragraph{Correctness.} The correctness is straight-forward with noting that $({\sf COM}, {\sf RSP})$ is a signature for the message $M$ under the public key ${\bf v}_\id, \mathcal{F}_\id$ and secret key ${\bf s}_\id$ of the user $\id$, and ${\sf COM}_\id, {\sf RSP}_\id$ is a signature for the message $\mathcal{F}_\id\|\id$ under the master public key $\mpk$ and master secret key $\msk$. \paragraph{Security.} The security is also straight-forward following the result by Kitlz et al.~\cite{KiltzN09}. In fact, the MQIBS is EUF-ID-CMA secure provided that the underlying signature is EUF-CMA secure which is again based on the security of the sigma protocol in Figure~\ref{Fig: sigma MQ}; see~\cite{Beullens20} for such a proof. \section{Parameters} \subsection{Optimizations} In this section, we review about the techniques presented in~\cite{Beullens20}, which was followed from Katz et al.~\cite{KKW18}, for optimizations. Some are as follows; see~{\cite[Section 7]{Beullens20}} for the details. \begin{itemize} \item Build a Merkle tree on the commitments $\com_i$ computed in the $\KeyDer$ process as well as the $\Sign$ process to reduce the user secret key $\uskey$ as well as signature size $\sigma$. In particular, instead of including all $\com_i$ in ${\sf COM}_\id$ (resp. ${\sf COM}$), we use only the root of the Merkle tree created by the $\com_i$, and hence ${\sf RSP}_\id$ (resp. ${\sf RSP}$) consists only $\lceil\log_2(q)\rceil$ nodes required to reconstruct the root of the Merkle tree. Similarly, we can do the same for ${\sf aux}_i$ in ${\sf COM}_\id$ (resp. ${\sf COM}$), and ${\sf seed}_i$ in ${\sf RSP}_\id$ (resp. ${\sf RSP}$). \item For some applications, the finite field $\F_q$ is large and hence not practical to compute Merkle trees of size $q$. We then can reduce the challenge space to $\F_{q'}$ with $q'