一般情况下，一个普通的数字签名具有公开验证性，即任何人都可根据签名者的公钥验证签名的合法性。然而，许多情况下，这种公开验证性并不适用。例如，当签名涉及一些商业敏感信息或者对于签名接收者而言比较敏感的信息时，签名的接收者希望签名仅仅能够由自己进行验证。同时，为防止签名者抵赖，签名的接收者还可向权威机构证明签名的合法性。为此，Kim、Park和Won提出了记名签名方案，并指出该签名可满足以上的验证特点。

一个记名签名方案由以下算法组成。

（1）密钥生成算法（Gnominator，Gnominee）。Gnominator是一个概率多项式时间算法，其输入一个安全参数1n，输出一对字符串（记名者的公钥，记名者的私钥），即Gnominator（1n）=（G1nominator（1n），G2nominator（1n））。Gnominee是一个概率多项式时间算法，其输入一个安全参数1n，输出一对字符串（被记名者的公钥，被记名者的私钥），即Gnominee（1n）=（G1nominee（1n），G2nominee（1n））。

（2）签名算法（Sign）。Sign是一个概率多项式时间算法，其输入一个安全参数1n、消息m、记名者的私钥、被记名者的公钥，输出一个字符串（记名签名），可用Sign（1n，m，G1nominator（1n），G2nominee（1n））表示这个算法（简写为Sign（m））。

（3）验证算法（Verify）。Verify为一个概率多项式时间算法，其输入一个安全参数1n、消息m、Sign（m）、记名者的公钥、被记名者的私钥。若Sign（m）为m的一个合法签名，则其输入为1，即Verify（1n，m，Sign（m），G2nominator（1n），G1nominee（1n））=1；否则，Verify（1n，m，Sign（m），G2nominator（1n），G1nominee（1n））=0。(www.daowen.com)

（4）确认算法（Conf（nominee，thirdparty））。Conf（nominee，thirdparty）是一个由被记名者和第三方（Third Party）参与的交互式证明算法，其以安全参数1n、消息m、Sign（m）、记名者的公钥、被记名者的公钥为公共输入，输出为1（true）或0（false）。其中，被记名者扮演一个证明者的角色，其辅助输入为私钥G1nominee（1n）；第三方扮演一个验证者的角色，对所有的消息m、任意的常数c以及足够大的n成立；若Sign（m）为m的一个合法签名，则概率Pr（Conf（nominee，thirdparty）（1n，m，Sign（m），G2nominator（1n），G2nominee（1n）））=1）＞1-1/nc；否则，概率Pr（Conf（nominee，thirdparty）（1n，m，Sign（m），G2nominator（1n），G2nominee（1n）））=0）＞1-1/nc。

同时，一个记名签名应该满足以下要求。

（1）只有被记名者才能验证记名者生成的签名S（即使记名者也无法验证S）；

（2）只有被记名者才能向第三方证明签名S是由记名者生成的签名，并且S是有效的（即使记名者也无法证明S是有效的）。