用来编码对象中随机分布特征的系统和方法

摘要

所述系统和方法涉及编码对象中的随机分布特征。确定验证对象中的随机分布特征。表示随机分布特征的数据被压缩，并用签名进行编码。标签被创建，并包括验证对象和经编码数据。该数据可通过确定关联于该验证对象的概率密度函数来压缩。与随机分布属性相关联的向量是至少部分地基于概率密度函数被确定的。使用算术编码算法编码该向量。

说明书

技术领域

本文所述的系统和方法一般涉及防伪和/或防篡改标签，尤其涉及利用对象的随机分布特征(无论嵌入的或自然固有的)来限制对伪造和/或篡改标签的未经授权尝试。

背景技术

标签的伪造和篡改使产品销售商和产品制造商在损失收入和损失客户方面每年花费数十亿美元。随着计算机技术的迅速成长，产生象真品的标签已变得越来越容易。例如，可利用扫描仪来扫描真标签的高分辨率图像，然后以最少成本重复再生产。还有，礼券也可以被扫描、更改(例如改为有更大面值)、重复印制、并兑换。

近年来已利用各种技术来制止伪造和篡改的泛滥成灾。一种保护标签的方法是通过加入条形码。条形码通常是印在标签上的机器可读码。使用条形码扫描仪，可快速读取并验证带有条形码的标签。当前条形码标签的一个问题是在各个产品上要使用相同的标签。

当前的另一方案是使经扫描条形码对照存储在数据库中的安全数据(例如电子收款机系统POS系统)进行检查。然而，这个方案需要加入来自销售商或制造商的最近数据。这种方案需要多方的及时并紧密合作。还有，这种方案限制了其实现的灵活性，且并非总是可行的。

然而，这些技术有一个通病；即，对于给定产品所扫描的标签物理上是相同的。因此，尽管产生合理标签的制造过程是高度复杂的，但对于伪造者而言要确定产生伪造合格品的方法通常却并不需要很长时间。而且，一旦标签被成功复制了一次，它就可以重复再生产了(例如建立低成本可复制的主副本)。即使在使用若干次后秘密地将标签列于数据库中，也不能保证先扫描的标签确实是真标签。

因此，当前方案不能提供较难复制且可较便宜生产的标签。

发明内容

本文所述的系统和方法涉及编码对象中的随机分布特征。在一方面中，确定验证对象中的随机分布特征。代表随机分布特征的数据被压缩并用签名编码。标签产生，并且它包括验证对象和经编码数据。

在另一方面中，通过确定关联于验证对象的概率密度函数来压缩数据。关联于随机分布属性的向量至少部分地基于概率密度函数来确定。使用算术编码算法来对向量进行编码。

附图说明

图1显示用作标签一部分的示例验证对象，诸如验证证书。

图2是示出验证系统的示例证书，以及由该系统采用的用以签发并校验验证证书的示例过程的示意图。

图3A是示例扫描系统的示意图，该系统用以捕捉关联于验证证书的验证对象的随机分布特征。

图3B是图3A中所示验证对象的顶视图。

图4是可用以创建验证证书的示例过程流程图。

图5是可用以压缩代表验证对象随机分布属性的数据的示例过程流程图。

图6是对应于示例验证对象四个不同区域的区域图形表示。

图7是示例验证对象上十九个不同区域的图形表示。

图8是正方形验证对象的概率密度函数的示例图形。

图9是验证对象中区域的图形表示。

图10是算术编码器如何编码字符串“aba”的示例的图形表示。

图11是用节点显示的验证对象实例的示例。

图12是为优化成本效率而设计的验证证书的图形表示。

图13示出了所述系统和方法可全部或部分实现的示例计算设备。

具体实施方式

I.导言

在此所述的系统和方法涉及有关在标签中使用的对象随机方法特征的编码信息。标签可包括任何类型的附于或包括在产品上的识别手段。被配置用以验证的标签在此称为验证证书。在验证证书中使用的带有随机分布特征的对象在此称为验证对象。为了使能自校验，验证证书可包括验证对象和关于随机分布特征的信息。可使用压缩方法来增加可编码并包括在验证证书中的关于随机分布特征的信息量。根据一示例计算，伪造验证证书的成本与压缩该信息上的改进成指数比例增加。这种伪造成本上的实质性增加导致了一种制造相对便宜但却难以伪造的可靠验证证书。

图1显示了用作部分标签的示例验证对象100，诸如验证证书。为了有效地在验证证书中使用，验证对象100通常包含唯一而且难以复制的随机分布特征。图1中所示的示例验证对象100是基于纤维验证证书的一部分，并包含以随机方式嵌入对象中的纤维110。纤维110作为验证对象100的随机分布特征。纤维110可以任何方法加入验证对象100。例如，可把纤维110喷在验证对象100上。也可在制造过程中把纤维110嵌到验证对象100中。在一实施例中，纤维110是能够在端点之间传送光线的光学纤维。因而，通过在验证对象100的某区域120上照光，至少有一端在点亮区域内的纤维131-133的端点被照亮。

图1中，验证对象100包括κ个随机分布纤维。以L×L象素的分辨率扫描验证对象100。每根纤维有固定长度为R。尽管图1中的示例验证对象100包含纤维，可以理解，也可以相似方式在验证证书中使用带有其它随机分布特征的验证对象。

验证对象100的随机分布特征可在验证证书中使用，以保护诸如产品的随机对象验证的证据。例如，某些有关验证证书随机分布特征的难以复制的数据可被数字化、用签发器(issuer)的私钥签名、并且签名以机器可读形式印在验证证书上以便校验产品是真的。验证证书的每个实例都与签发器想要证明其真实性的对象相关联。在一实施例中，验证的校验通过使用签发器公钥提取经签名数据(关于随机分布特征的数据)，并校验提取数据与验证证书的相关联实例数据相匹配来完成。为了伪造被保护对象，对手需要：(i)算出签发器私钥，(ii)设计可准确复制验证证书的已签名实例的制造过程，或者(iii)验证证书的不当签名实例。从这个角度而言，验证证书可被用来保护其值大约不超过伪造单个验证证书实例(包括成功的对抗性制造过程累积开发)的成本的产品。

验证证书系统的目标是确保产品或关联于产品的某些信息的验证。其应用的集是众多并广泛的，范围从软件和介质(例如DVD、CD)的防盗版，到不可伪造礼券和防篡改硬件的设计。例如，制造防篡改芯片将需要在其包装上覆盖一个验证证书。在每次使用前，应当校验验证证书的完整性，以便校验被保护硅片的真实性。

下面，将讨论用以便宜但有效地读出基于纤维验证证书的随机分布特征的实例硬件平台。硬件平台可包括条形码。由于对于低成本读取器条形码的容量限制为约3k比特，由私钥签名的消息也被限制为同样长度。还有，由于验证证书系统的目标之一是使打算伪造验证证书特定实例的对手要花费的精力最多，将讨论关联于在固定长度的经签名消息中存储尽可能多的关于基于纤维验证证书的唯一且随机分布特征的信息的困难。将提供用于基于纤维验证证书的示例分析模型。然后，以下的讨论也将正式提出点集压缩问题，并显示验证证书实例中纤维位置的优化压缩是NP-完全问题。为了探索式地解决该问题，将提供一种对常规压缩方法的压缩比例上有极大改进的算法。

II.签发并校验验证证书

图2是示出验证系统200的示例证书，以及由该系统采用的用以签发并校验验证证书的示例过程的示意图。验证系统200的证书包括验证证书210、签发器230以及验证者250。如图2所示，验证证书210可包括图1中的验证对象、条形码213和文本215。

在验证证书上需要保护的信息包括：(a)验证对象100难以复制的随机分布特征的表示以及(b)任意相关联文本数据。开始，使用硬件设备扫描诸如纤维位置的验证对象100的随机分布特征。如何收集并表示该信息的细节将结合图3如下进行讨论。

为了进行讨论，假设结果信息f是n_F个比特的随机字符串。参数n_F是固定的，并等于n_F＝k*n_RSA，k∈N，其中n_RSA是RSA公钥的长度(例如，n_RSA＝1024)，且k通常设定为k∈[1，3]。给定一固定n_F，代表验证对象100随机分布特征的数据231的摘录f可使任何两个不同验证证书实例之间的距离统计地为最大。在验证步骤中该目标直接转化为假阴性和假阳性的最小可能性。

文本数据t是取决于应用(例如，过期日期、制造商保证)的任意字符串。文本数据源自如图2所示印在验证证书210上的文本215。

可使用一种诸如SHA1的密码学安全散列算法237来使文本数据形成散列。散列函数的输出被表示为有n_T比特的消息t。签发器230创建可通过RSA签名的消息m。例如，使用确保m的每个比特都取决于f和t二者的所有比特的可逆运算符，消息f和t被合并成长度为n_M＝n_F的消息m。这个步骤可使需要在用以创建某消息m的数据231以及文本215中进行操作的比特数达最多。这种运算符的示例是使用t或者来自t的比特子集为密钥的对f的对称加密 $>>m>=>tver>>>>\otimes >>·>>f>\equiv >>E>t>>>(>f>)>>.>>>使用签发器230的私钥233用RSA签名235对消息m进行签名。结果签名s有n$_S＝n_M＝n_F比特。该消息被编码并在验证证书210上印制为条形码213(诸如遵照PDF417标准的条形码)。

验证证书210的校验包括若干步骤。开始校验器扫描印制组件：文本215和条形码213。条形码213被解码为原始印制签名s。文本215被扫描并形成散列以便创建消息t。注意对该任务而言不需要一般光学字符识别(OCR)，因为用以印制该文本的字体为校验器250已知，并为改进OCR优化。为了验证证书的成功校验，需无错误地读取文本215和条形码213；这是用现代扫描技术就可轻松完成的任务。

校验器250使用签发器的公钥253来执行s上的RSA签名校验255，并获取经签名消息m。然后检验者250计算 $>>f>=>m>>>(ver>>>>\otimes >>·>>)>>>->1>>>t>.>>>在使用加密为的示例中，这可通过解密$ >>f>=sup>>E>t>>->1>sup>>>(>m>)>>>>来完成。接着，检验者250扫描表示验证对象100中随机分布特征的数据251，并创建其表现f\prime 。检验者250比较f\prime 和经提取f。检验者250需要对两组数据之间的相互关系进行量化：附于证书上的数据和用以创建验证证书上签名的数据。在判定框259，如果两组数据的相似度超过了某阈值，检验者250宣布验证证书210是真的，反之亦然。$$

图3A是示例扫描系统300的示意图，该系统用以捕捉关联于验证证书的验证对象310的随机分布特征。扫描系统300包括光学扫描仪322和光源324。光学传感器322被配置用以扫描验证对象310，并可包括特定分辨率的电荷耦合装置(CCD)矩阵。在一实施例中，光学传感器322的分辨率为128×128象素。光源324被配置用以提供有特定波长的光，以照亮验证对象310的区域。电源324可包括例如发光二极管。如图3A所示，验证对象310中纤维326的一端被光源324照亮。光线传送到纤维326的另一端，并被光学传感器322所检测。

图3B是图3A中验证对象310的顶视图。操作中，扫描系统300将验证对象310分成诸如311-314的多个区域。如图3B所示，扫描系统300的光源324照在区域314上，而区域311-313从光源324隔离。通过照亮区域314，验证对象310在区域311-313中的端点位置可由光学传感器322确定。因而，验证对象310中随机分布特征的读取包括包含四个不同点集的四个数字化图像。每个点集与一个特定区域相关联，且通过照亮该区域来确定。

可以想像，诸如纳米技术(nanotechnology)的技术进步可使电子装置能够解码来自验证证书的随机分布特征，并创建对应于这些特征的光图案。这种装置可能能够伪造验证证书。在一实施例中，扫描系统300可配置成通过改变光源324使用的光线波长(例如颜色)来防止这种伪造方法。例如，每次由扫描系统300扫描验证对象时，随机选择光线的波长。光学传感器322可被配置成检测由验证对象中纤维发出的光线波长，并确定该波长是否对应于光源324发出的光线波长。如果发出的波长与检测的波长不匹配，则验证证书可能是伪造品。

图4是用以创建验证证书的示例过程400的流程图。在方框405，扫描验证证书中的验证对象。可使用图3A中的扫描系统300来扫描验证对象。

在方框410，确定表示验证对象随机分布特征的数据。在基于纤维的验证对象中，数据可包括诸如图3B所示端点的被照亮纤维端点的位置。

在方框415，压缩数据以提高验证证书的安全度。数据压缩将结合图5进行详述。简言之，可确定用以压缩表示验证对象中随机分布属性的一部分数据的路径。

在方框420，编码经压缩的数据。例如，经压缩的数据可使用图2中私钥233进行签名。在方框425，经编码的数据被加入验证证书。例如，经编码数据可在印制证书上印成诸如图2中条形码213的条形码。

图5是示例过程500的流程图，该过程可用以压缩表示验证对象随机分布属性的数据。为了进行讨论，过程500将在基于纤维验证证书的上下文中进行描述。然而，过程500可应用于任何类型的验证证书。

在方框505，确定关联于验证对象的概率密度函数。概率密度函数将在小节III-A中讨论。示例概率密度函数如等式11所示。示例概率密度函数的图形表示在图8中示出。简言之，概率密度函数表示在验证对象的某位置发现一个随机分布属性单元的可能性。在基于纤维验证证书的上下文中，概率密度函数可表示在验证对象区域中一特定点被照亮的概率。也可使用概率密度函数来计算在特定区域中一共有多少纤维将被照亮。

在方框510，确定关联于随机分布属性的向量。在基于纤维验证证书的上下文中，使用点对点向量并在小节IV-A中讨论。特别地，等式16被用来计算点对点向量以表示基于纤维验证证书中的随机分布属性。

在方框515，使用算术编码算法来编码向量。算术编码算法将在小节IV-A中讨论。示例算法在表格2中显示。

在方框520，确定用于在固定量数据中压缩部分向量的路径。用以计算路径的方法在小节IV-B中讨论。可使用等式20来计算示例路径。在方框525，返回表示部分随机分布属性的经压缩数据的路径。

III.验证证书模型

在本小节中，讨论基于纤维验证证书的分析模型。模拟了验证证书S的两个特征。假设照亮了验证证书的特定区域S_i，计算在S-S_i中特定点被照亮的概率密度函数。同样，假设在S中有K根纤维，可计算在S-S_i中被照亮纤维的预期数量。

A.被照亮纤维端点的分布

验证对象(L，R，K)被模拟为边长为L单元的正方形，其上随机抛掷有固定长度为R≤L/2的K根纤维。诸如可变纤维长度或随意形状验证对象的其它模型变量，可从该模型推理。验证对象位于图1所示2D笛卡尔坐标系统的正象限中。另外，验证对象被分成四个相等的正方形S＝{S₁，S₂，S₃，S₄}。每个都被用来记录结合图3A和3B所述的3D纤维结构。然后，纤维被表示为点A，BS的多元组f＝{A，B}，从而它们间的距离为‖A-B‖＝R。

定义1.被照亮纤维端点的分布。假设一个正方形S_i被照亮，对任意点Q(x，y)S-S_i通过任何区域PS-S_i包含纤维f＝{A，B}的被照亮纤维端点A的概率ξ(i，P)来定义概率密度函数(pdf)(i，Q(x，y))，以其它端点B位于被照亮区域S_i的事实为条件。更正式地，对于任何PS-S_i：

$>>\xi >>(>i>,>P>)>>=>>P>r>>[>A>⋐>P>|>f>=>\{>A>,>B>\}>⋐>S>,>B>⋐>>S>i>>]>>>$

假设把纤维f＝{A，B}掷入验证对象包括两个相关联事件：(i)第一端点A落于验证对象上以及(ii)第二端点B碰到验证对象。尽管A可以落在COA上的任意地方，B的位置却取决于A的位置。端点B必须落于以A为中心半径为R且包含在验证对象中圆的部分圆周内。在本小节的剩余部分，函数(i，Q(x，y))基于对事件(i-ii)的分析进行分析计算。为简便起见，当区域S_i被点亮时仅计算(i，Q(x，y))。(i，Q(x，y))分两步进行计算。

定义2.圆周容纳(Perimeter Containment)。首先，对于给定点AS，定义测量以A为中心半径为R被整个验证对象S包围的圆的部分圆周(弧)长度的容纳函数l(A)。在验证对象中有四个ρ(A)同一计算的不同区域(在图6中标记为P1到P4)。

图6是对应于示例验证对象600中四个不同区域的区域P1-P4的图形表示。对于某区域Px的每个点，以对该区域独特的封闭分析形式使用如下讨论的等式7-10来计算圆周容纳函数。

区域P1。这是圆周对象的中心区域，对于任意点QP1，以Q为中心半径为R的圆与验证对象的任何边界不相交。该区域由R≤x≤L-R，R≤y≤L-R定界。

                     ρ(Q(x，y))＝2Rπ.(7)

区域P2。有四个不同P2区域，在以任意点QP2为中心半径为R的圆与验证对象的一个边界正好相交两次。为了简便，仅考虑以下区域：R≤x≤L-R，0≤y＜R。可对称计算其它三个区域的等式。

$>>\rho >>(>Q>>(>x>,>y>)>>)>>=>R>[>\pi >+>2>arcsin>>(>>y>R>>)>>]>.>->->->>(>8>)>>>>$

区域P3。有四个不同P3区域，在以任意点QP3为中心半径为R的圆与验证对象的两个不同边界相交两次。为了简便，仅考虑以下区域：0≤x＜R，0≤y＜R，x²+y²≥R²。

$>>\rho >>(>Q>>(>x>,>y>)>>)>>=>2>R>[>\pi >->arccos>>(>>x>R>>)>>->arccos>>(>>y>R>>)>>]>.>->->->>(>9>)>>>>$

区域P4。有四个不同P4区域，在以任意点QP4为中心半径为R的圆与COA的两个边界相交一次。仅考虑以下区域：x²+y²＜R²。

$>>\rho >>(>Q>>(>x>,>y>)>>)>>=>R>[>>\pi >2>>+>arcsin>>(>>x>R>>)>>+>arcsin>>(>>y>R>>)>>]>.>->->->>(>10>)>>>>$

在所有的等式8-10中，仅考虑在{0，π/2)中函数arcsin(·)和arccos(·)的返回值。

在第二个步骤，仅当B位于以Q(x，y)为中心直径为R并被包含于S₁的圆C(Q，R)的部分上时，基于纤维f＝{A，B}的被照亮端点A在位置A＝Q(x，y)上的事实计算有效的(1，Q(x，y))。

引理3.(i，Q(x，y))源于ρ(Q(x，y))的相关性。使用函数ρ(Q(x，y))，用以下积分计算pdf(i，Q(x，y))：

其中在C(Q，R)S的圆周上递进，而且α是常量从而：

仅因为纤维f＝{Q，B}点QS-S_i可被照亮，从而BS_i。这隐含了B位于由S_i包含的圆C(Q，R)的圆周上的某处。对于某给定纤维f＝{A，B}，A落在长度为dlS的特定无限小圆弧上的概率等于dl/e(B)。因此：

其中函数area(S-S_i)计算在S-S_i下的区域。因而，在点QS-S_i上的pdf(1，Q(x，y))与ρ(·)在C(Q，R)S_i上值的倒数的积分成比例。

图7是示例验证对象700上十九个不同区域的图形表示，该对象有独特的分析公式作为等式11中确定的积分的解式。为了简便，使用简单的数字计算近似解答(1，Q(x，y))。结果在图8中示出。

图8是带有从单元点上采集的参数L＝64以及R＝28的正方形验证对象的示例概率密度函数的曲线图。图8显示了纤维端点落在某小区域PS-S_i的可能性取决于P在S-S_i中的特定位置而有极大的变化。通过使用关于(i，Q(x，y))在整个S-S_i中变化的信息，可大大改进点子集压缩算法，如小节IV中所示。在整个区域S-S_i上制造验证对象使(i，Q(x，y))＝常量不是一个琐碎的任务而已，可能会和伪造原始验证对象一样困难。

表格1(注解：area-区域，bounds-边界)

B.纤维端点的照亮比例

定义3.纤维端点的照亮比例。对于验证对象(L，R，K)及其照亮区域S_i，照亮比例λ被定义为纤维f＝{A，B}落在对象上使得其端点之一在BS-S_i中的概率，其中以其它端点在AS_i的事实为条件：

λ＝Pr[BS-S_i|f＝{A，B}，AS₁].(14)

定义4.可能照亮圆弧。对于任意点AS_i，函数(i，A(x，y))被定义为测量包含于S-S_i内C(A，R)的边界部分的长度的函数。

图9是区域T0-T8的图形表示，使用独特的封闭分析形式来计算(i，Q(x，y))函数。(i，Q(x，y))基于小节III-A上对事件(i-ii)的分析进行分析计算。类似于小节III-A，仅在区域S_i被点亮的情形进行计算。在COA中有九个不同区域(图9中标记为T0到T8)，其中(1，Q)同一计算。取决于Q在S₁中的位置对(1，Q)的分析封闭形式在表格1中给出。

引理4.(1，Q(x，y))、ρ(Q(x，y))和λ的相关性。如定义3中定义的照亮系数(illumination ratio)可如下计算：

$>>\lambda >=>>\int >>Q>>(>x>,>y>)>>⋐>>s>i>>>>>>\psi >>(>i>,>Q>>(>x>,>y>)>>)>>>>\rho >>(>Q>>(>x>,>y>)>>)>>>>dxdy>.>->->->>(>15>)>>>>$

以点AS为中心的半径为R的圆被表示为C(A，R)。对于每个点QS_i，纤维f＝{Q，B}的另一端点B落于S-S_i内的可能性，等于C(Q，R)分别被S-S_i和S包含的圆周长度的比例。通过将该比例对S_i中所有点积分，可获得等式15。

给定使用λ由数字近似等式15和来自表格1的(1，Q)封闭形式计算的验证对象(L，R，K)，可计算当S₁被照亮为λK/2时S-S₁中被照亮点的预期数量。例如，对于验证对象(64，28，100)结果λ≈0.74，其含义是在S₁被照亮的情形中被照亮的端点数量平均约为0.74·50＝37。

IV.COA中点子集的压缩

验证证书系统的目标是确保制造(即伪造)特定验证对象实例的任务尽可能地困难。该目标被量化为对记录验证对象尽可能多纤维的位置的需求。在示例压缩算法中，验证对象的区域数等于4；因此，对于每个区域S_i，经签名消息m中的1/4比特数n_M/4被用以存储尽可能多的一旦照亮了S_i，S-S_i中被照亮的纤维端点。注意一般而言，不需要存储所有的被照亮端点；仅需要使用n_M/4比特数编码的这些点的最大子集。

在本小节中，描述了一种机制，其被配置为用以编码验证对象中两个照亮点之间的距离。该机制基于算术编码。然后，形式化使用固定比特数来压缩尽可能多纤维端点的问题。最后，讨论将显示该问题是NP-完全问题，并提供一种建设性试探法作为次优方案。

A.编码点对点向量

在本分节中，描述了如何使用接近最少的比特数来编码由其起点和终点定义的向量。附加限制是被考虑区域中的点根据给定pdf出现。

1)算术编码

算术编码器(AC)把任意长度的输入流转换成[0，1}中的单一有理数。AC的主要优点是它能接近熵(entropy)地任意压缩。以下的讨论显示如果给定带有未知pdf符号出现的字母表，如何对字“aba”进行编码。

图10是如果给定带有未知pdf符号出现的字母表L＝{a，b}，算术编码器如何编码字符串“aba”的示例的图形表示。示例如图10所示。开始时，AC的范围被重设为[0，1}，且L中每个符号都有相等的出现可能性Pr[a]＝Pr[b]＝1/2。因而，AC将其范围分成二个子范围[0，0.5}和[0.5，1}，每个分别代表“b”和“a”。通过把AC的范围限制成对应于该符号即[0.5，1}的范围，对符号a进行编码。另外，AC为符号“a”的出现更新计数器，并重新计算P_r[a]＝2/3以及P_r[b]＝1/3。在下一次迭代中，根据已更新P_r[a]和P_r[b]，AC将其范围分成[0.5，0.6667}以及[0.6667，1}，每个分别代表“b”和“a”。当下次“b”到达时，AC将其范围减到相应的[0.5，0.6667}，更新P_r[a]P_r[b]＝2/4，并将该新范围分成[0.5，0.5833}以及[0.5833，0.6667}，每个分别代表“b”和“a”。由于最终的符号为“a”，AC通过选择[0.5833，0.6667}中的任意数作为输出来编码该符号。通过选择用最少比特数编码的数字(我们示例中的数字)，0.6，AC创建其最终输出。解码器由明显在经压缩消息首部或通过专用的“end-of-file”符号知道消息长度。

AC迭代地减少其操作范围直到某一点，当其范围中上边界和下边界的主要数字相等。然后，传送主要数字。称为“重正化”(renormalization)的该过程可用限定精度算术单元进行任何长度的文件压缩。传统AC的性能改进集中在：使用预先计算的算术运算近似值，将用移位和加法替换除法和乘法。

使用等于源熵 $>>H>>(>s>)>>=>->>\Sigma >>s>i>>>Pr>[>>s>i>>]>l>>og>2>>>(>Pr>[>>s>i>>]>)>>>>的比特数，AC编码一个序列的输入符号s＝s$₁，s₂，……。因此，对于不相关并同一分布符号的半无限流，在带有无限精度算法的计算机上，AC是最佳的熵编码器。

2.最短距离点对点向量的算术编码

给定一个验证对象(L，R，K)，假设光线照在其四分体之一S_i。然后，我们假设验证对象被分割成L×L单元方块的网格U＝u(i，j)i＝1…L，j＝1…L，其中每个u(i，j)覆盖x∈{i-1，i]，y∈{j-1，j]中的方形区域。单元区域模拟验证对象数字化扫描的象素。扫描分辨率等于L×L。然后，单元u(x，y)的主要点被定义为坐标为(x，y)的点Q_u。

引理5.单元照亮可能性。假设有κ根纤维的只有一个端点在S-S_i中，任何单元区域u(x，y)S-S_i包含至少一个被照亮纤维端点的概率等于：

$>>\tau >>(>u>)>>=>Pr>[>>>(>\exists >f>=>\{>A>,>B>\}>\in >F>)>>A>⋐>u>,>B>⋐>>S>i>>]>->->->>(>16>)>>>>>>$

$>>=>1>->[>1>->\xi >>(>i>,>u>)>>>]>\kappa >>.>>>$

以及

$>>\tau >>(>u>)>>=>Pr>[>>(>\exists >f>=>\{>A>,>B>\}>\in >F>)>>A>⋐>u>,>B>⋐>>S>i>>]>=>1>->Pr>[>>(>⫬>\exists >c>\in >F>)>>A>⋐>>>>$

$>>u>,>B>⋐>>S>i>>]>=>1>->>>(>1>->Pr>[>A>⋐>u>,>B>⋐>>S>i>>|>f>=>\{>A>,>B>\}>]>)>>\kappa >>>>$

由等式7可得出等式16。在小节III-B中，计算出κ的期望值为E[κ]＝λK/2。

问题1.对COA的双向量编码。以单元US-S_i包含一被照亮纤维端点的事实为条件，目标是要使用尽可能少的比特数来编码相对于单元u的另两个被照亮单元v₁和v₂的位置。附加限制是在S-S_i的所有被照亮单元中，分别为Q₁和Q₂的v₁和v₂主要点位于离u主要点Q_u的两个欧几里得几何(Euclidean)最短距离上。优先规则设置为如果一组单元V，|V|＞1位于相对于u的相同距离上，最有可能照亮的那个单元argmax_vV(τ(v))被首先编码。

设定U是S-S_i-u中所有单元区域的列表。所有经标记单元的列表M(u)被设定为M(u)＝φ。do  找出所有的单元区域V＝argmin_v∈V‖Q_v…Q_u‖。  do    找出单元区域w＝argmax_v∈Vξ(1，v)。    设定w的AC范围为γ(w，u)(参见等式17，18)。    排列在w之前节点组是M_w(u)＝M(u)。    M(u)＝M(u)∪w，V＝V-W，U ＝U-w.  while V≠ while U≠

                     表格2.算法A1

使用AC完成单元对单元向量的编码，其中使用算法A1在每个编码符号(即不同于源单元u的每个单元vS-S_i)编码间隔上分配的相应范围。对于每个单元v，算法A1分配了等于v是相对源单元u两个最近被照亮单元之一的概率的范围。该概率表示为p(v|u)。在当κ＞＞1预期在S-S_i中单元被照亮时，可如下计算p(v|u)：

$>>p>>(>v>|>u>)>>=>\tau >>(>v>)>>>>>\Pi >>>>w>⋐>>M>v>>>(>u>)>>>>[>1>->\tau >>(>w>)>>]>+>->->->>(>17>)>>>>$

$>>>\Sigma >>w>⋐>>M>v>>>(>u>)>>>>\tau >>(>v>)>>\tau >>(>w>)>>>\Pi >>z>⋐>>M>v>>>>(>u>)>>i>>z>\ne >w>>>[>1>->\tau >>(>z>)>>]>,>>>$

其中单元组M，(u)以算法A1进行计算。对于每个单元v，以已编码u的事实为条件，算法A1分配由AC使用的范围γ(v，u)以编码v。该范围等于：

$>>\gamma >>(>v>,>u>)>>=>>>p>>(>v>|>u>)>>>>>\Sigma >>w>⋐>S>->>S>i>>>>p>>(>w>|>u>)>>>>.>->->->>(>18>)>>>>$

因而，两个最近的被照亮单元由接近最优的构建进行编码(例如在带有无限精度算法的处理器上编码最优)，因为使用约等于源熵的若干比特来编码一系列符号：

$>>H>>(>u>)>>=>->>\Sigma >>v>⋐>S>->>S>i>>>>\gamma >>(>v>,>u>)>>>log>2>>[>\gamma >>(>v>,>u>)>>]>.>->->->>(>19>)>>>>$

双向量编码被用作基元(primitive)，以小节IV-B中给出的整体压缩算法来编码点子集。尽管该编码算法对于小节IV-A.2中给出的那组假设而言是接近最优的，但是相同的限制组并不对整体压缩目标有效。因此，通过A1使用带有范围分配的算法编码的固有最优性在小节IV-B中讨论。

B.点子集的压缩

模拟了使用固定比特数来压缩尽可能多被照亮单元区域位置的最优化问题。考虑以下带有权重边界的有向完全图形。对于每个被照亮单元uS-S_i，创建节点n_u。从节点n_u到节点n_v的有向边界e(u，v)用编码指向v(如等式19中ω(e(u，v))＝-log₂[γ(v，u)])向量的编码字最优长度被赋以权重，假设u已被编码的事实为条件。将此图表示为G(N，E，Ω)，其中N，E，Ω分别表示节点组、有向边界、以及相应的权重。

问题2.点子集的压缩(CPS)。

实例：有向、完全、且带有权重的图形G(N，E)，其具有非负顶点函数Ω：E→R、正整数l_min∈z⁺、正实数Λ∈R⁺。

问题：有没有这样的l＞l_min节点子集N^*N，其具有穿过节点的路径即排列＜n_π(l)^*，…，n_π(f)^*＞，使得沿路径的权重和为：

问题2模拟了使用固定存储(例如Λ)来压缩验证对象中尽可能多(例如1)纤维端点的最优化问题。该问题是NP完全的，因为它证明通过对Λ的二进制检索非对称流动推销员问题(ATSP)可被简化为CPS,在本小节的剩余部分，给出了针对解决该问题的有效建设性试探法A2。试探法的先决设计要求是快速的运行时性能，因为每个验证证书必须在生产线上单独签名。

首先，N中两节点间的距离测量不遵从所有节点的三角不等式。直观地，小节IV-A中的编码过程使用与某单元是两个最近的被照亮单元之一的可能性成比例的若干比特来对S-S_i中的向量进行编码。因此，由于离源节点较远的单元不太可能出现，就以长得多的编码字对它们编码，这使在方案路线中到这些节点的捷径变得极为不合需要。

定理2.距离测量ω一般不遵从三角不等式：

ω(e(u，v))+ω(e(v，w)≥ω(u，w)

为简便起见，假设(uS-S_i)r＝τ(u)＝常量，则u，v和w都位于S-S_i中的同一线条上。欧几里得距离‖u-v‖，‖v-w‖和‖u-w‖分别是a，b和a+b。三角不等式隐含了f(u，v，w)＝log₂[γ(w，u)]-log₂[γ(v，u)]-log₂[γ(w，v)]≥0。从等式17和18，可计算出以下等式：

$>>f>>(>a>,>b>,>t>)>>=>2>ab\pi >>log>2>>>(>1>->t>)>>+>>log>2>>>t>>1>->t>>>->->->->>(>21>)>>>>$

$>>->>log>2>>>>>>(>1>->t>)>>2>>+>>(>>a>2>>+>>b>2>>)>>\pi t>>(>1>->t>)>>+>>a>4>>>b>4>>>\pi >2>>>t>2>>>>1>+>[>>>(>a>+>b>)>>2>>\pi >->1>]>t>>>,>>>$

且显示对于abπ1＞＞1，三角不等式不成立，即f(a，b，t)＜0。

三角不等式成立的ATSP最佳近似算法，所产生的方案最多比最优方案差log(|N|)倍。或者，就作者所知，还未开发出三角不等式不成立的ATSP变式的近似算法。通常，当距离度量函数ω任意时，ATSP问题是NPO完全的，即除非P＝NP才会有好的近似算法。另一方面，可解决TSP变式的满足三角不等式比例版本

μ(ω(e(u，v))+ω(e(v，w)))≥ω(u，w)，μ＞l的近似算法，其最坏结果是比最优方案差(3μ+1)μ/2倍。距离度量ω不遵从该限制，因此，问题2的试探法无最差情形保证地进行开发。另外，我们追求试探法的尽可能好的平均性能，而不是最差情形保证。可去除不能满意压缩的验证对象实例。这种事件的可能性应当是很小，少于百万分之一。

    收缩P_h使得∑_ecPhω(e)≤ρΛ，其中ρ是从ρ∈{0.4，0.8}中随机选取的收缩因子。    将节点n_o和n_l表示为P_h的第一个和最后一个节点。    while∑_ecPhω(e)≤Λ    在具有n_o和n_l分别作为目标或源的边界中，找出带有最小权重的边界e。    将e连接到P_h。    reroute(P_h)

                          表格3.算法A2

使用来自小节IV-A的距离度量之后的基本原理，是基于这样的假设：好的方案经由两个最近邻节点成功遍历路径上的每个节点。因此，在问题2的范围内，仅当最佳方案被发现满足该属性时所使用度量才是最佳的。如果最终方案并无此属性，编码单个向量的最优性取决于方案中边界权重的分布。

已开发的试探法A2有两个步骤：建设性阶段和迭代改进阶段。建设性阶段遵从建立初始方案的贪婪试探法。开始时，A2标识一组优势边界E’。对于节点u，v之间的每对边界e(u，v)，e(v，u)，A2仅选择两者中较短边界并将之存储在E’中。然后通过对E’中的边界排序并选择其权重和尽可能接近Λ的最短前K个边界，创建一组初始子路径P。路径P_h中的第一个和最后一个节点被分别表示为s_i和d_i。在下一步骤中，A2以权重的递增顺序来迭代地连接来自P的子路径：在任何点上，直到建立了所有可能连接，才连接具有共同源-目标节点d_i＝s_j的最短子路径对p_i，p_j。在|P|＝1的不太可能的情形中，找到了最佳方案并停止搜索。否则，从P中去除所有单边界子路径。然后，使用Dijkstra算法，A2找出P中每个子路径p_i的每个目标端点d_i和所有其它子路径s_j，i＝l…|P|，i≠j的源端点之间的所有最短路径。经由不在P中的节点，定出最短路径路线。s_i和d_j之间的最短路径表示为q(i，j)。在另一贪婪步骤中，A2根据其权重/节点计数比例来排序所有的连接p，|q(i，j}|P_i。以该度量的递增顺序，A2继续经由N-P中的节点连接P中子路径，直到剩余路径的总数为|P|＝maxP(通常maxP＝9)。使用找出带有最佳度量(最大基数和权重之和小于Λ)路径p_h的精确算法来连接这些剩余路径。在最后步骤中，重定路径过程浏览了所有P中的节点，并使用Dijkstra算法尝试找出经由E中剩余节点到P中其它节点的最短路径。相同的过程还尝试找出比p_h中存在的更好结束端点。对于每个重定路径，A2检查新的重定路径是否比当前的最佳路径p_h有更好的度量。

图11是验证对象实例的示例，被示为具有κ＝88个节点的(512，0.4·512，256)。A2返回用粗线表示路径。该路径的权重和比Λ＝512小。为了记录该路径，使用12.11比特/点。

在迭代改进阶段中，我们重复以下循环若干次。在第一步中，A2把当前发现的最佳路径P_best收缩为p_h，从而|p_h|是最大值且沿p_h的权重和小于ρΛ的一小部分。收缩参数ρ是在每次迭代中在ρ∈{0.4，0.8}范围内随机选取的。节点n_o和n_l被表示为p_h中的第一个和最后一个节点。虽然p_h上权重和小于Λ，在把n_o或n_l分别作为目标或源的边界之中，我们发现带有最小权重的边界e并把其连接到p_h。当创建了新的候选路径p_h时，如果其度量比迄今为止所创建的最佳度量更好，则将其采用为最佳方案。在迭代改进循环的最后一步时，A2执行前述的重定路径过程。

为了使A2对于特定验证对象(L，R，K)类的运行时在一秒之内，改进循环重复I＝{100,10000}次。一般而言，当通过Dijkstra算法计算多源最短路径时，A2的最差次数复杂性为O(|N|³log|N|)。在使用Floyd-Warshall算法来计算所有成对最短路径的实现中，A2的复杂性可降为O(|N|³)。尽管图形原来是完全的，通过去除具有高权重的边界，我们还是创建了稀疏图形，其中用于计算所有成对最短路径的Johnson算法产生了O(|N|²log|N|+|N|E|)。

V.经验估算

本小节中的讨论示出验证对象(L，R，K)参数如何影响算法A2的执行。图11示出了对问题单个实例-验证对象(512，0.4·512，256)的方案。扫描对准L＝512的扫描单元网格。该图示出了当验证对象的左下四分体被照亮时的情形。使用相应被照亮纤维端点建立的图形G(N，E)用中等粗线示出。仅示出了从图中每个κ＝88节点开始的最短的前十个边界。在图中用粗线示出的结果路径包括四十一个节点。沿路径边界的权重和小于存储限制：Λ＝512比特。使用12.11比特/纤维端点(b/fep)压缩了该路径。不经压缩存储该数据需要41.18＝738比特，因而压缩比为0.61。压缩比被定义为经压缩消息尺寸与原消息尺寸的比例。

VI.COA系统的设计目标

验证证书设计者的目标是使用有限制造成本ζ_m使伪造成本ζ_f最高。若干参数可影响ζ_m。为简便起见，讨论三个参数：

纤维总长度RK≤Ф，

扫描误差ζ，以及

条形码存储Λ。

通过限制对手可进行的对经签名纤维端点足够的分组精确定位的试验次数(小节VI-A)并选取系统参数{R.，K.}，来最优化系统性能，从而使预期伪造成本ζ_f(A2)达最高(小节VI-B)。

A.限制对手试验次数

考虑把κ个被照亮纤维端点中的G个存储在限定为Λ的存储器中。一般而言，当伪造验证证书时，对手可使用所有κ根纤维来尝试把其中至少Gζ根精确置入相应位置。伪造验证证书的成本大部分取决于可进行试验的次数。在这里，提出了一种通过检测在验证期间经签名纤维端点周围纤维的非正常分布，以减少对手试验次数K_T的技术。

签发COA实例扫描当灯光照在S_i上时被照亮的κ个点的组N。使用Λ个比特来压缩分组PN，其中G＝|P|≤κ。找出单元分组US-S_i，从而    (u_i∈U)(p_j∈P)min(‖u_i-p_j‖)＜ε₁.  ε₁＝|N∩U|-G，K_T＝G+ε₂.                签名P，ε₂以及相关联信息(参见小节2)。    校验COA实例从签名中提取P，ε₂。找出单元分组US-S_i，从而    (u_i∈U)(p_j∈P)min{‖u_i-p_j‖)＜ε₁.扫描当灯光照在S_i上时被照亮的κ’个点的组N’。if|N′∩U|＞K_τthen COA实例无效，elseif|N′∩P|≥Gζ then COA实例有效，else COA实例无效。

表格4.算法A3

验证证书的签发器和校验器对每个验证对象四分体S_i重复算法A3的各自部分。开始时签发器扫描验证对象实例，并收集有关灯光照在S_i上时所照亮的点组N的信息。然后，使用可用的Λ个比特，它压缩由A2返回的最大分组PN，|P|＝G。然后，A3找出分组US-S_i，从而每个单元u_i∈U与其最近单元p_j∈P之间的欧几里得距离最大为ε₁。单元分组U表示P的ε₁邻域。然后，签发器计算存在于U的N中点数K_T。因为，K_T不得不比G大以防止假阴性，签发器存储了消息m中后来用签发器私钥签名(参见小节II)的差值ε₂＝K_T-G以及P。使用签发器的公钥，校验器从所附签名中提取经压缩点分组P和ε₂，并重建相应的ε₁邻域U。然后，校验器为了灯光照在S_i上时所照亮的纤维组N’对验证对象进行扫描。通过检查U和N’中的共同点数至多为G+ε₂，而N’和P中的共同点数至少为Gζ，它宣布该实例是真的。

通过把ε₂存储在签名中，对手被强迫使用最多K_T＝G+ε₂次在P的ε₁邻域中定位纤维的试验。对手的目标是精确放置来自P的至少Gζ个纤维端点，因此对手可忍受在伪造过程中在P的ε₁邻域中G(1-ζ)+ε₂次错误放置。预期目标为点P_i的每次试验，如果成功最终该点位于P_i的ε₁邻域中。通过增大ε₁，校验器可在较大的邻域范围标识可能的错误放置；然而，这也可能增大验证证书设计者想要保持尽可能小值的ε₂期望值。

以下显示了一种经验设计方法，其采用给定ε₁＝常数，并从若干验证证书参数的角度追求使主要目标ζ_j(A2)的最大化。

B.设计一种COA系统

问题3.COA系统的设计目标。对于给定压缩算法A2、给定的RK≤Ф、ζ、ε₁和Λ，找出使以下等式最大化的可用纤维的一个分段(cut){R_*，K_*}：

$>>\{>>R>*>>,>>K>*>>\}>=>arg>>max>>(>R>,>K>|>RK>\le >\Phi >)>>>>\zeta >f>>>(>A>2>,>R>,>K>)>>,>->->->>(>22>)>>>>$

其中ζ_f是伪造COA实例的成本。

图12是为最佳成本效力设计的验证证书的图形表示。横坐标相对于L量化纤维长度R，而纵坐标示出了纤维数K。显示条示出伪造log-成本为log₁₀(ζ_f(A2，R，K))，其中限制极限Λ＝512比特且一组固定参数为：ζ＝0.9，ε₁＝8和ν＝0.8。该图还示出了为固定长度纤维RK＝Ф＝100L的所有分段而获取的方案质量。

可使用一种简单的搜索最佳纤维分段{R_*，K_*}的经验技术。使用图12示出搜索过程。横坐标和纵坐标分别表示R和K的值。显示条表示伪造验证证书实例的期望log-成本log₁₀(ζ_f(.42，R，K))。该成本相对于R、K、以及固定参数组Λ＝512，ζ＝0.9和ν＝0.8给出。图12中图表是经验计算的。A2应用于随着R＝{0.05L，0.10L，…，0.45L}和κ＝{80，96，…，192，256，384，512，768，1024}的每个组合而随机生成的500个验证证书(512，R，K)实例。{R，K}空间剩余部分中每个点的预期压缩性能是通过内插(interpolating)经验结果来获取的。从图12，可在邻域k.≈900和R.≈0.1L中找到最佳纤维分段。该结果指出了这样一个事实，即对于选定设计环境十字形验证证书是最佳选项。注意纤维分段的审慎选择可导致相对于RK＝Ф上随机选定点而在伪造成本上成数量级的改进。可应用在此例中使用的经验原理，以针对不同的验证证书环境和制造限制搜索接近最佳的参数组。

图13阐述了所述系统和方法可在其中全部或部分实现的示例计算装置1300。计算装置1300仅是计算系统的一个示例，并非旨在提出对本发明使用范围或功能性的任何限制。

计算装置1300也可在很多其它通用或专用计算系统环境或配置中实现。适于使用的众所周知的计算系统、环境、和/或配置的示例包括，但不限于，个人计算机、服务器计算机、瘦客户机、厚客户机、手持式或膝上型设备、多处理器系统、基于微处理器的系统、置顶盒、可编程电器消费品、网络PC、迷你计算机、大型机、游戏控制台、包括任一种以上系统或设备的分布式计算环境、等等。

计算装置1300的组件可包括，但不限于，处理器1302(例如任何微处理器、控制器等等)、系统存储器1304、输入装置1306、输出装置1308以及网络装置1310。

计算装置1300通常包括各种计算机可读介质。计算机可读介质可以是能被计算装置1300访问的任何可用介质，并包括易失和非易失介质、可移动和不可移动介质。系统存储器1304包括诸如随机存取存储器RAM的易失存储器和/或诸如只读存储器ROM的非易失存储器形式的计算机可读介质。包含有助于计算装置1300如起动时在元件间传送信息的基本例程的基本输入/输出系统BIOS通常存储在系统存储器1304中。系统存储器1304通常包含可被处理器1302立即访问和/或现时操作的数据和/或程序模块。

系统存储器1304还可包括其它可移动/不可移动、易失/非易失计算机存储介质。作为示例，可包括硬盘驱动器用来读取和写入不可移动、非易失磁性介质；磁盘驱动器用来读取和写入可移动、非易失磁盘(例如“软盘”)；以及光盘驱动器用来读取和写入可移动、非易失光盘，诸如CD-ROM、DVD或其它类型的光学介质。

盘驱动器及其相关联的计算机可读介质为计算装置1300提供计算机可读指令、数据结构、程序模块、和其它数据的非易失存储。可以理解，其它类型的计算装置1300可访问的可存储数据的计算机可读介质，如磁带或其它磁性存储设备、闪存卡、CD-ROM、数字化多功能光盘(DVD)或其它光学存储设备、随机存取存储器(RAM)、只读存储器(ROM)、电子可擦可编程只读存储器(EEPROM)等等，也可被用来实现示例性计算装置1300。任何数量的程序模块可被存储在系统存储器1304中，包括作为示例，操作系统1320、应用程序1328、以及数据1332。

计算装置1300可包括各种标识为通信介质的计算机可读介质。通信介质通常包含计算机可读指令、数据结构、程序模块、或其它已调制数据信号形式的数据，诸如载波或其它传送机制，且包含任何信息传递介质。术语“已调制数据信号”意指用将信息编码到信号中的方式设置或改变其一个或多个特征的信号。作为示例，而非限制，通讯介质包括诸如有线网络或有线直接连接的有线介质，和诸如声学、射频、红外线和其它无线介质的无线介质。所有以上内容的组合也应包含在“计算机可读介质”范围之内。

用户可通过诸如键盘和定位装置(如“鼠标”)的输入装置1306向计算装置1300输入指令和信息。其它输入装置1306可包括话筒、游戏杆、游戏垫、控制器、卫星接收器、串行端口、扫描仪、触摸屏、触摸垫、键板、和/或等等。输出装置1308可包括CRT监视器、LCD屏幕、扬声器、打印机等等。

计算装置1300可包括用来连接到诸如局域网(LAN)、广域网(WAN)等等的计算机网络的网络装置1310。

尽管本发明已用结构化特征和/或方法论步骤的专用语言作了说明，但可以理解的是在所附权利要求书中定义的本发明无须受限于所述特定特征或步骤。相反，特定特征和步骤是以实现所要求保护的本发明的示例性形式被揭示的。