\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'<q$. It then makes the protocol in Figure~\ref{Fig: sigma MQ} has soundness error $\frac{1}{q'}$ (instead of $\frac{1}{q})$. Katz et al.~\cite{KKW18} suggested to, instead of letting the verifier choose $1$ out of $k$ setups to execute, we now let him choose $\tau$ out of $M$ setups to execute, which results to the soundness error bounded by
		$$ \max_{0\leq e\leq \tau}\frac{\binom{M-e}{\tau-e}}{\binom{M}{\tau}q'^{\tau-e}}.$$
		See {\cite[Section 7]{Beullens20}} or {\cite{KKW18}} for the details.
		
	\end{itemize}
	
	\subsection{Parameters}
	We follow~{\cite{Beullens20}} for the choice of parameters $m,n,q,\tau,M$. First of all, $q=4$ and $m=n= 88,128,160$ respectively following~\cite{MQDSS}~in the MQDSS submission to the NIST PQC standardization project. The parameters for MQIBS, key and signature sizes are summarized in Table~\ref{Table: params}.
	
		\begin{center}
	\begin{table}[h]
		\caption{Parameters for MQIBS}
	
			\begin{tabular}{||c || c | c | c| c || c|| c|| c||} 
				\hline\hline 
				Security Level & q & n & M & $\tau$ & $|\mpk|$ (B) & $|\msk|$ (B) &   Signature (B) \\ [0.5ex] 
				\hline\hline
				I &  4 & 88 & 191 & 68 & 38 & 16 & 28,838\\
				\hline 
				III & 4 & 128 & 256 & 111 & 56  & 24 & 65,856\\
				\hline 
				V & 4 & 160 & 380 & 136 & 72 & 32 & 111,272\\ 
				\hline\hline 
			\end{tabular}
			\label{Table: params}

	\end{table}
			\end{center}
	In Table, we provide a comparison between existing IBS scheme from multivariate polynomials at the security level I. It can be seen from Table that our scheme outperforms the existing ones (except the ID-Rainbow~\cite{ChenLND19}) in terms of signature size. In addition, our scheme has smallest public key size. Compared to the ID-Rainbow by Chen et al.~\cite{ChenLND19}, our scheme has much bigger signature size (28,838 B vs. 46 B) but has much smaller master public key (38 B vs. 4,220,000B) and secret key (16 B vs. 142,600 B).
	
		\begin{center}
	\begin{table}[h]
		\caption{Comparison between our MQIBS with other existing multivariate IBS}
	
			\begin{tabular}{||c || c|| c|| c||} 
				\hline\hline 
				Scheme & $|\mpk|$ (B) & $|\msk|$ (B) &   Signature (B) \\ [0.5ex] 
				\hline\hline
				Ours (MQIBS) &   38 & 16 & 28,838\\
				\hline 
				IBS-Rainbow~\cite{Luyen19} & 148,300 & 103,700 & 304,300 \\
				\hline
				ID-Rainbow~\cite{ChenLND19} & 4,220,000 & 142,600 & 46\\
				\hline 
				Mul-IBS-Rainbow~\cite{DebnathMSPK23} & 136,100 & 90,900 & 33,400 \\
				\hline\hline 
			\end{tabular}
	
		\label{Table: compare}
	\end{table}
		\end{center}
	
	
	\section{Conclusion}
	In this paper, we propose a design for an identity-based signature, called MQIBS, from multivariate polynomials. Our scheme is derived from the sigma protocol with helper for MQ from Beullens~\cite{Beullens20} from which our MQIBS inherits the efficiency. Compared to existing schemes, our scheme has advantage on both signature size as well as public key and secret key size. Further optimizations and implementations are one of the goals for our future work.

\backmatter
%
%\bmhead{Supplementary information}
%
%If your article has accompanying supplementary file/s please state so here. 
%
%Authors reporting data from electrophoretic gels and blots should supply the full unprocessed scans for key as part of their Supplementary information. This may be requested by the editorial team/s if it is missing.
%
%Please refer to Journal-level guidance for any specific requirements.

\bmhead{Acknowledgements}

The author would like to thank Dung Duong for useful discussions.

\bmhead{Funding}

This research is funded by Vietnam National University, Ho Chi Minh City (VNU-HCM) under grant number C2022-18-03.

%\section*{Declarations}
%%
%%Some journals require declarations to be submitted in a standardised format. Please check the Instructions for Authors of the journal to which you are submitting to see if you need to complete this section. If yes, your manuscript must contain the following sections under the heading `Declarations':
%
%\begin{itemize}
%\item Funding
%\item Conflict of interest/Competing interests (check journal-specific guidelines for which heading to use)
%\item Ethics approval and consent to participate
%\item Consent for publication
%\item Data availability 
%\item Materials availability
%\item Code availability 
%\item Author contribution
%\end{itemize}
%
%\noindent
%If any of the sections are not relevant to your manuscript, please include the heading and write `Not applicable' for that section. 
%
\begin{thebibliography}{10}
	
	\bibitem{NIST2}
	{National Institute of Standards and Technology} additional post-quantum
	signatures.
	\newblock
	\url{https://csrc.nist.gov/projects/pqc-dig-sig/round-1-additional-signatures}.
	\newblock Accessed: 2024-07-24.
	
	\bibitem{NIST}
	{National Institute of Standards and Technology} post-quantum cryptography.
	\newblock \url{https://csrc.nist.gov/projects/post-quantum-cryptography}.
	\newblock Accessed: 2024-07-24.
	
	\bibitem{AS19}
	Sedat Akleylek and Meryem Soysaldi.
	\newblock A novel 3-pass identification scheme and signature scheme based on
	multivariate quadratic polynomials.
	\newblock {\em Turkish Journal of Mathematics}, 43:241--257, 2019.
	
	\bibitem{Beullens20}
	Ward Beullens.
	\newblock {Sigma Protocols for MQ, {PKP} and SIS, and Fishy Signature Schemes}.
	\newblock In Anne Canteaut and Yuval Ishai, editors, {\em Advances in
		Cryptology - {EUROCRYPT} 2020 - 39th Annual International Conference on the
		Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May
		10-14, 2020, Proceedings, Part {III}}, volume 12107 of {\em Lecture Notes in
		Computer Science}, pages 183--211. Springer, 2020.
	
	\bibitem{Beullens22}
	Ward Beullens.
	\newblock Breaking rainbow takes a weekend on a laptop.
	\newblock In Yevgeniy Dodis and Thomas Shrimpton, editors, {\em Advances in
		Cryptology - {CRYPTO} 2022 - 42nd Annual International Cryptology Conference,
		{CRYPTO} 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part
		{II}}, volume 13508 of {\em Lecture Notes in Computer Science}, pages
	464--479. Springer, 2022.
	
	\bibitem{BogdanovERW08}
	Andrey Bogdanov, Thomas Eisenbarth, Andy Rupp, and Christopher Wolf.
	\newblock Time-area optimized public-key engines: Mq-cryptosystems as
	replacement for elliptic curves?
	\newblock {\em {IACR} Cryptol. ePrint Arch.}, page 349, 2008.
	
	\bibitem{ChenCCCDKLY09}
	Anna~Inn{-}Tung Chen, Ming{-}Shing Chen, Tien{-}Ren Chen, Chen{-}Mou Cheng,
	Jintai Ding, Eric~Li{-}Hsiang Kuo, Frost~Yu{-}Shuang Lee, and Bo{-}Yin Yang.
	\newblock {SSE} implementation of multivariate pkcs on modern x86 cpus.
	\newblock In Christophe Clavier and Kris Gaj, editors, {\em Cryptographic
		Hardware and Embedded Systems - {CHES} 2009, 11th International Workshop,
		Lausanne, Switzerland, September 6-9, 2009, Proceedings}, volume 5747 of {\em
		Lecture Notes in Computer Science}, pages 33--48. Springer, 2009.
	
	\bibitem{ChenLND19}
	Jiahui Chen, Jie Ling, Jianting Ning, and Jintai Ding.
	\newblock Identity-based signature schemes for multivariate public key
	cryptosystems.
	\newblock {\em Comput. J.}, 62(8):1132--1147, 2019.
	
	\bibitem{MQDSS}
	Ming-Shing Chen, Andreas H lsing, Joost Rijneveld, Simona Samardjiska, and
	Peter Schwabe.
	\newblock {MQDSSsubmission to the nist post-quantum cryptography project}.
	\newblock In {\em NIST Post-quantum Cryptography}, 2017.
	
	\bibitem{ChenHRSS16}
	Ming{-}Shing Chen, Andreas H{\"{u}}lsing, Joost Rijneveld, Simona Samardjiska,
	and Peter Schwabe.
	\newblock From 5-pass \emph{MQ} -based identification to \emph{MQ} -based
	signatures.
	\newblock In Jung~Hee Cheon and Tsuyoshi Takagi, editors, {\em Advances in
		Cryptology - {ASIACRYPT} 2016 - 22nd International Conference on the Theory
		and Application of Cryptology and Information Security, Hanoi, Vietnam,
		December 4-8, 2016, Proceedings, Part {II}}, volume 10032 of {\em Lecture
		Notes in Computer Science}, pages 135--165, 2016.
	
	\bibitem{DebnathMSPK23}
	Sumit~Kumar Debnath, Sihem Mesnager, Vikas Srivastava, Saibal~Kumar Pal, and
	Nibedita Kundu.
	\newblock Mul-ibs: a multivariate identity-based signature scheme compatible
	with iot-based {NDN} architecture.
	\newblock {\em J. Cryptogr. Eng.}, 13(2):187--199, 2023.
	
	\bibitem{DingS05}
	Jintai Ding and Dieter Schmidt.
	\newblock Rainbow, a new multivariable polynomial signature scheme.
	\newblock In John Ioannidis, Angelos~D. Keromytis, and Moti Yung, editors, {\em
		Applied Cryptography and Network Security, Third International Conference,
		{ACNS} 2005, New York, NY, USA, June 7-10, 2005, Proceedings}, volume 3531 of
	{\em Lecture Notes in Computer Science}, pages 164--175, 2005.
	
	\bibitem{FiatS86}
	Amos Fiat and Adi Shamir.
	\newblock How to prove yourself: Practical solutions to identification and
	signature problems.
	\newblock In Andrew~M. Odlyzko, editor, {\em Advances in Cryptology - {CRYPTO}
		'86, Santa Barbara, California, USA, 1986, Proceedings}, volume 263 of {\em
		Lecture Notes in Computer Science}, pages 186--194. Springer, 1986.
	
	\bibitem{FurueDT19}
	Hiroki Furue, Dung~Hoang Duong, and Tsuyoshi Takagi.
	\newblock An efficient mq-based signature in the {QROM}.
	\newblock In {\em 2019 Seventh International Symposium on Computing and
		Networking, {CANDAR} 2019, Nagasaki, Japan, November 25-28, 2019}, pages
	10--17. {IEEE}, 2019.
	
	\bibitem{book}
	M~R Garey and D~S Johnson.
	\newblock {\em Computers and Intractability: A Guide to the Theory of
		Np-Completeness}.
	\newblock W. H. Freeman, 1979.
	
	\bibitem{KalesZ20}
	Daniel Kales and Greg Zaverucha.
	\newblock An attack on some signature schemes constructed from five-pass
	identification schemes.
	\newblock In Stephan Krenn, Haya Schulmann, and Serge Vaudenay, editors, {\em
		Cryptology and Network Security - 19th International Conference, {CANS} 2020,
		Vienna, Austria, December 14-16, 2020, Proceedings}, volume 12579 of {\em
		Lecture Notes in Computer Science}, pages 3--22. Springer, 2020.
	
	\bibitem{KKW18}
	Jonathan Katz, Vladimir Kolesnikov, and Xiao Wang.
	\newblock {Improved Non-Interactive Zero Knowledge with Applications to
		Post-Quantum Signatures}.
	\newblock In {\em CCS '18: Proceedings of the 2018 ACM SIGSAC Conference on
		Computer and Communications Security}, pages 525 -- 537. ACM, 2017.
	
	\bibitem{KiltzN09}
	Eike Kiltz and Gregory Neven.
	\newblock Identity-based signatures.
	\newblock In Marc Joye and Gregory Neven, editors, {\em Identity-Based
		Cryptography}, volume~2 of {\em Cryptology and Information Security Series},
	pages 31--44. {IOS} Press, 2009.
	
	\bibitem{KipnisPG99}
	Aviad Kipnis, Jacques Patarin, and Louis Goubin.
	\newblock Unbalanced oil and vinegar signature schemes.
	\newblock In Jacques Stern, editor, {\em Advances in Cryptology - {EUROCRYPT}
		'99, International Conference on the Theory and Application of Cryptographic
		Techniques, Prague, Czech Republic, May 2-6, 1999, Proceeding}, volume 1592
	of {\em Lecture Notes in Computer Science}, pages 206--222. Springer, 1999.
	
	\bibitem{Luyen19}
	Le~Van Luyen.
	\newblock An improved identity-based multivariate signature scheme based on
	rainbow.
	\newblock {\em Cryptogr.}, 3(1):8, 2019.
	
	\bibitem{Patarin95}
	Jacques Patarin.
	\newblock Cryptanalysis of the matsumoto and imai public key scheme of
	eurocrypt'88.
	\newblock In Don Coppersmith, editor, {\em Advances in Cryptology - {CRYPTO}
		'95, 15th Annual International Cryptology Conference, Santa Barbara,
		California, USA, August 27-31, 1995, Proceedings}, volume 963 of {\em Lecture
		Notes in Computer Science}, pages 248--261. Springer, 1995.
	
	\bibitem{PetzoldtBB10}
	Albrecht Petzoldt, Stanislav Bulygin, and Johannes Buchmann.
	\newblock Cyclicrainbow - {A} multivariate signature scheme with a partially
	cyclic public key.
	\newblock In Guang Gong and Kishan~Chand Gupta, editors, {\em Progress in
		Cryptology - {INDOCRYPT} 2010 - 11th International Conference on Cryptology
		in India, Hyderabad, India, December 12-15, 2010. Proceedings}, volume 6498
	of {\em Lecture Notes in Computer Science}, pages 33--48. Springer, 2010.
	
	\bibitem{SakumotoSH11}
	Koichi Sakumoto, Taizo Shirai, and Harunaga Hiwatari.
	\newblock Public-key identification schemes based on multivariate quadratic
	polynomials.
	\newblock In Phillip Rogaway, editor, {\em Advances in Cryptology - {CRYPTO}
		2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August
		14-18, 2011. Proceedings}, volume 6841 of {\em Lecture Notes in Computer
		Science}, pages 706--723. Springer, 2011.
	
	\bibitem{Shamir84}
	Adi Shamir.
	\newblock Identity-based cryptosystems and signature schemes.
	\newblock In G.~R. Blakley and David Chaum, editors, {\em Advances in
		Cryptology, Proceedings of {CRYPTO} '84, Santa Barbara, California, USA,
		August 19-22, 1984, Proceedings}, volume 196 of {\em Lecture Notes in
		Computer Science}, pages 47--53. Springer, 1984.
	
	\bibitem{MI78}
	Adi Shamir.
	\newblock Public quadratic polynomial-tuples for efficient
	signature-verification and message-encryption.
	\newblock In G.~R. Blakley and David Chaum, editors, {\em Advances in
		Cryptology, Proceedings of {EUROCRYPT} '88, Davos, Switzerland, May 25-27,
		1988, Proceedings}, volume 330 of {\em Lecture Notes in Computer Science},
	pages 419--553. Springer, 1988.
	
	\bibitem{ShenTX13}
	Wuqiang Shen, Shaohua Tang, and Lingling Xu.
	\newblock Ibuov, {A} provably secure identity-based {UOV} signature scheme.
	\newblock In {\em 16th {IEEE} International Conference on Computational Science
		and Engineering, {CSE} 2013, December 3-5, 2013, Sydney, Australia}, pages
	388--395. {IEEE} Computer Society, 2013.
	
\end{thebibliography}



\end{document}
