理论计算机科学电子笔记180（2007）55-76www.elsevier.com/locate/entcs弱概率焦虑1邓玉欣2INRIASOPHIA-AntipolisanddUniversit′eParis7庞军INRIAFutursandLIX，E'colePolytechn ique摘要匿名性意味着执行某个操作的用户的身份是保密的。 保证匿名性的协议通常使用可以概率描述的随机机制。 在本文中，我们提出了一个弱概率匿名的概念，其中弱是指这样一个事实，即一定量的概率信息可能会透露的协议。观察者可以使用该信息来推断该动作已经由某个用户执行的可能性。 这项工作的目的是研究的匿名性的程度，该协议仍然可以确保，尽管泄漏的信息。我们使用的例子来说明我们的想法有偏见的硬币的用餐密码。 我们认为这两种情况下的不确定性和概率用户。相应地，我们提出了两个弱匿名性的概念，我们研究了它们各自对硬币的偏置因子的依赖关系。保留字：随机性，概率，不确定性，用餐密码。1介绍保密性是指对执行某项操作的用户的身份保密的属性。匿名的需求可能会在很多情况下出现，比如在电子论坛上发帖、投票、删除、捐赠等等。用于确保匿名性的协议通常使用随机机制。例如，Dining Cryptographers [6]，Crowds [11]，Onion Routing [15]和SG-MIX [9]就是在文献[6，11，7，4]中已经研究了概率匿名的各种概念。在本文中，我们提出了一个弱概率匿名的概念，其中弱是指这样一个事实，即一些概率信息可能1此工作已部分由ACIS。2由欧盟PROFUNDIS项目支助。1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.05.04756Y. Deng等人理论计算机科学电子笔记180（2007）55由协议显示。典型的原因可能是攻击者的存在干扰了协议的正常执行，或者是内部机制的一些不可避免的缺陷，甚至可能是协议设计方式所固有的在任何情况下，观察者都可以使用系统泄露的信息来推断某个用户执行了该动作的可能性这项工作的目的是研究的匿名性的程度，该协议仍然可以确保，尽管泄漏的信息。我们用用餐密码问题（DCP）的例子来说明我们的想法在这个协议中，许多用户（密码学家）合作，以确保某个动作的发生是可见的，而执行它的密码学家保持匿名。他们通过执行某种涉及掷硬币的算法来实现这一目标在[6]的原始公式中，硬币是完全公平的，没有人（除了授权的密码学家）得到任何关于硬币结果的信息。作为这些假设的结果，该协议确保了强匿名性，从这个意义上说，从观察者的角度来看，没有办法推断出密码学家比另一个更有可能执行该操作。我们考虑一个更现实的情况下，一些概率信息可能会泄露的系统。特别是，我们考虑的情况下，这是由于其内部机制的不完善。在DCP的情况下，这意味着放松硬币完全公平的假设值得注意的是，即使观察者事先不知道DCP中的硬币是否有偏差以及有多少偏差，他也可以通过多次运行协议来进行统计推断[4]。这项工作的主要目的之一是研究如何在系统仍然可以实现的匿名性水平的偏差因素的硬币。当我们处理一个概率系统时，需要考虑的一个问题是是否也涉及到一些非确定性的选择。非确定性意味着选择是完全不可预测的，通常是因为决定它的机制每次都可能发生变化，因此无法用概率来描述行为，甚至无法通过重复统计观察来描述。可能意味着这些机制中存在规律性。概率分布可能仍然是未知的，例如，因为我们不知道机制是如何运作的在匿名协议中，根据不同的情况，用户可能是概率性的或不确定性的。通常，后者适用于动态场景，当用户一直在变化时。在非确定性的情况下，匿名的概率方面只能相对于可观察的概率，这完全来自于协议内部机制的随机性匿名性的自然概念是，观察到的概率不提供关于用户的信息。在概率用户的情况下，有两种可能的观点可以定义匿名的概念。也就是说，我们可以专注于可观测量的概率，并要求它们不允许推断信息Y. Deng等人理论计算机科学电子笔记180（2007）5557关于用户的概率（类似于非确定性的情况），或者我们可以关注用户的概率，并要求系统不允许通过可观测量推断关于它的额外信息。有趣的是，在强匿名的情况下，这两个概念已经被证明是等价的[4]。在本文中，我们考虑了不确定性和概率用户的情况下，我们提出了两个弱匿名性的概念，对应于上述两个观点。虽然，如前所述，在强匿名性的极限情况下，这两个概念是等价的，但它们对硬币的偏置因子的函数依赖性是完全不同的。1.1贡献这项工作的主要贡献是：• 我们提出了两个弱概率匿名的概念，分别为nondeterministic和概率用户• 我们考虑有偏见的硬币的用餐密码，我们研究了两个概念的弱匿名性依赖于硬币的偏见因素• 我们展示了如何编码的公式，表示弱匿名的PRISM，使他们的有效性可以检查一个通用的协议自动。1.2文件计划在下一节中，我们回顾了本文其余部分中使用的一些概念：概率自动机，用餐密码学家问题以及[4]中开发在第3节中，我们提出了一个不确定用户的弱匿名性的概念，我们研究了DCP的硬币的偏置因子的依赖性在第4节中，我们对概率用户的情况做了同样的处理。在第5节中，我们在PRISM中编码DCP和匿名的概念。最后，在第6节中，我们总结并讨论了一些相关的工作。2预赛2.1非决定论与概率在本文中，我们考虑的系统，可以执行概率和非决定性的选择。直观地说，概率选择代表一组可选的转换，每个转换都与被选中的特定概率相关联。所有选项的概率之和必须为1，也就是说，它们形成一个概率分布。不确定性选择也是一组备选方案，但我们没有关于一个备选方案被选中的可能性的信息我们的观点是，不确定性选择不是概率未知的概率选择：在后者中，如果我们重复运行程序，我们可以推断出概率。例如，如果我们在两个转换之间进行选择，并且我们观察到它们以相同的频率被选择，我们可以推断概率接近1/ 2。在非确定性的情况下，这个推论将是58Y. Deng等人理论计算机科学电子笔记180（2007）55一1/2s1s1s1c1/3sbas两个半S3C2/35S4Cb1/2S67（一）1/2S8(b)（c）第（1）款Fig. 1.概率自动机无效.非确定性意味着选择是完全不可预测的，并且没有关于确定选择的机制的时间规律性的假设在文献中已经提出了许多结合了非确定性和概率性选择的模型。其中最一般的是在[14]中提出的概率自动机我们在这里给它一个简短的和非正式的描述。概率自动机由一组状态和它们之间的标记转换组成。对于每个节点，传出转换被划分为称为步骤的组。每一步都代表一个概率性的选择，而步骤之间的选择是不确定的。图1展示了概率自动机的一些示例。我们通过在成员过渡中放置一个弧来表示一个步骤。例如，在（a）中，状态s1有两步，第一步是在标签为a和b的两个转移之间进行概率选择，每个转移的概率为1/ 2。当一个步骤中只有一个转换时，比如从状态s3到状态s6，概率当然是1，我们省略它。在本文中，我们只使用了一种简化的自动机，其中每个节点都有一个概率选择或一个非确定性选择（更准确地说，一个步骤或一组单例步骤），如（b）中所示。这不是一个真正的限制，因为它包含了所谓的交替模型，其中概率和非确定性选择交替，并且已知具有与完全概率自动机相同的表达能力。在选择都是概率性的特殊情况下，如（c）中，自动机被称为完全概率性的。给定一个自动机M，我们用etree（M）表示它的展开，即M的所有可能执行的树（在图1中，自动机与它们的展开一致，因为没有循环）。如果M是完全概率的，那么etree（M）的每个执行（最大分支）都有一个概率，该概率是沿着分支的边的概率的乘积。在有限的情况下，我们可以通过对元素3的概率求和来定义每组执行的概率度量，称为事件。给定一个事件x，我们用p（x）表示x的概率。为[3]在无限情况下，事情更加复杂：我们不能为所有的执行集定义一个概率测度，我们需要把由etree（M）的锥生成的σ场看作事件空间然而，在本文中，我们只考虑有限情况。一CB一C1/2 1/2一C1/2B1/61/3一个c1/21/2SY. Deng等人理论计算机科学电子笔记180（2007）5559例如，让事件c是c发生的所有计算的集合 在（c）中，它的概率是p（c）= 1/3× 1/2+ 1/6 = 1/3。当存在非决定性时，概率会有所不同，这取决于我们如何解决非决定性。换句话说，我们需要考虑一个函数，每次在不同的步骤之间进行选择时，都会选择其中一个。通过修剪未选择的步骤，我们获得了一个完全概率的执行树etree（M，M），我们可以像以前一样定义概率。由于历史原因（即非确定性通常来自并行运算符），函数EQUIPMENT被称为scheduler。然后应该清楚的是，事件的概率是相对于特定调度器的。我们用p（x）表示事件x在调度器下的概率。例如，考虑（a）。 我们有两个可能的候选人，由步骤 1 的 选 择 决 定 。 在 此 期 间 ， 您 的 预 算 为 1/2 。 在 另 一 种 情 况 下 ， 它 是2/3×1/2+1/3=2/3。 在（b）中，我们在持续的时间内有四个问题，而这些问题的概率分别为0、1/2和1。2.2餐饮密码学家一般的密码学家用餐问题[6]描述如下：位于给定连通图的节点上的许多密码学家正在吃饭。他们组织的代表（主人）可以也可以不支付晚餐的账单。如果他不这样做，那么他将选择一个密码学家，并命令他支付账单。主人会秘密地告诉每个密码破译者他是否要付钱。密码破译者希望揭示账单是由主人还是其中一人支付的，但是，在后一种情况下，他们希望匿名支付者的身份。在[6]中描述的这个问题的一个可能的解决方案是将硬币与图的每个边缘相关联，仅对相邻的密码学家可见。然后掷出硬币，每个密码学家计算相邻硬币的二进制和（比如说，正面为0，反面为1），如果他是付款人，则加1，文[6]证明了付款人是密码学家之一当且仅当所有输出的二进制和为1。此外，如果硬币是公平的，那么外部观察者无法识别付款人，因为它是密码学家之一DCP将是贯穿本文的一个运行示例2.3抗干扰系统在本节中，我们回顾了我们在[4]中开发的匿名方法。我们将匿名协议建模为一个概率自动机M。匿名的概念是相对于匿名用户的集合和观察者可见的内容而言的。因此，在[13，12]之后，我们将M的动作分为三个集合A，B和C，如下所示：• A是匿名操作A ={a（i）|i∈I}其中I是匿名用户的身份的集合，a是从I到集合的单射函数60Y. Deng等人理论计算机科学电子笔记180（2007）55我们称之为抽象行为。我们也称对（I，a）为匿名动作生成器。• B是可观察动作的集合。我们将使用b，b，J。. .来表示这个集合的元素。• C是剩余动作的集合（不可观察的）。注意，A中的动作通常对观察者不可见，或者至少对依赖于恒等式i的部分不可见。然而，为了定义和验证匿名性，我们将A的元素建模为系统的可见结果。定义2.1匿名系统是一个元组（M，I，a，B，Z，p），其中M是一个概率自动机，（I，a）是一个匿名动作生成器，B是一组可观察的动作，Z是M的所有可能的生成器的集合，对于每个n∈Z，pn是由etree（M，n）生成的事件空间上的概率测度。如果系统是完全概率的，那么Z是单例的，我们省略它。我们引入以下符号来表示感兴趣的事件：• a（i）：etree（M，M）中包含动作a（i）的所有执行• a：etree（M，M）中包含任意i的动作a（i）的所有执行;• o：etree（M，M）中的所有执行，其包含序列o作为其可观察动作的最大序列（其中o的形式为b1b2. b n对于一些b1，b2，. ，bn∈ B）。 我们用O（可观测量）表示所有这些O的集合。我们用符号、和<$分别表示事件的并、交和补。我们希望尽可能地保持可观测量的概念，但我们仍然需要对它们做一些假设。首先，我们希望观察到的是不相交的事件。其次，它们必须涵盖所有可能的结果。第三，一个可观察的o必须明确地表明a是否已经发生，也就是说，它要么意味着a，或者它意味着a。在集合论术语中，它意味着O是A的子集或a的补集形式上：假设1（关于可观察性）（i）n∈Z. o1，o2∈O. o1/= o2p（o1o2）= p（o1）+p（o2）(ii) Z ∈ Z。 （O）= 1(iii) Z ∈ Z。 o ∈ O. （p（o a）= p（o））p（o a）= p（o）类似地，我们需要对匿名操作做一些假设。我们首先考虑为非确定性用户量身定制的条件：每个调度程序完全确定a（i）形式的动作是否发生，并且在肯定的情况下，只有一个这样的i。形式上：假设2（关于匿名操作，对于不确定性用户）Z∈Z。 p<$（a）=0<$（<$i∈I. （pj∈I. j/=i<$p<$（a（j））=0））在[4]中，提出了以下强有力的匿名概念直觉，鉴于Y. Deng等人理论计算机科学电子笔记180（2007）5561对于都选择A的两个调度器A和B（分别假设A（i）和A（j）），不可能从可观测量的概率测量中检测调度器是A还是B（即，所选用户是i还是j）。定义2.2[非确定性用户的（强）匿名性]一个系统（M，I，a，B，Z，p）是匿名的，如果Z，Z ∈ Z。 o∈ O. p（a）= p（a）= 1 p（o）= p（o）我们现在考虑用户完全概率的情况。在这种情况下，对匿名操作的假设要弱得多：我们只要求最多有一个用户执行，即。a（i）和a（j）必须不相交对于i j。形式上：假设3（关于匿名操作，针对概率用户）i，j ∈ I。 i/= j <$p（a（i）<$a（j））= p（a（i））+p（a（j））定义2.2的概率对应物可以使用条件概率的概念形式化。回想一下，给定两个事件x和y，其中p（y）> 0，x给定y的条件概率，记为p（x|y），等于t o p（xy）/p（y）。定义2.3一个完全概率系统（M，I，a，B，p）是匿名的，如果i，j∈I。o∈O. （p（a（i））> 0 <$p（a（j））> 0）<$p（o|a（i））= p（o|a（j））到目前为止，所说明的匿名性概念都集中在观察对象的概率上。然而，在概率用户的情况下，也可以从与用户相关联的概率信息的角度来接近匿名的概念。这是[7]中采用的观点，以定义他们所谓的条件匿名。这个想法是，如果观察结果不改变a（i）的概率，则系统是匿名的换句话说，我们可以通过系统外部的某种手段知道a（i）的概率，但系统不应该增加我们关于它的知识。这个概念可以在我们的框架中表述如下：定义2.4[概率用户的（强）匿名性]一个完全概率系统（M，I，a，B，p）是匿名的，如果i∈I. o∈O. p（oa）> 0 p（a（i）|o）= p（a（i）|a）、尽管定义2.3和2.4是基于对匿名性的概念上不同的解释，但已经证明它们是等价的（见[4]）。只有当硬币是公平的时，DCP才能满足本节中所示的匿名性定义。在接下来的章节中，我们提出了这些定义的弱版本，当硬币有偏差时，也可以满足，这取决于偏差因子。62Y. Deng等人理论计算机科学电子笔记180（2007）55支付地穴0主人付钱o1O2地穴1支付地穴2支付O8O7O3O4o1O2O4O5O6O342Oo1oO3图二. 有三个密码学家和不确定性主机的DCP。3不确定用户在本节中，我们提出了定义2.2的一个弱变体，并在DCP的特定情况下研究了该属性如何取决于硬币的偏置因子。直觉上，弱化包括放松约束，即观察者暗示a的概率在每个调度器下都是相同的。相反，我们要求任何两个这样的概率之间的差异不超过某个参数α。形式上：定义3.1[非确定性用户的α-匿名性]给定α∈[0， 1]，系统（M，I，a，B，Z，p）是α-匿名的，如果max{p <$（o）− p <$（o）|其中，n ∈ Z，o ∈ O，p <$（o <$a）= p <$（o），p<$（o <$a）= p <$（o）}= α直觉上，p（o）−p（o）=α意味着，每当我们观察到o时，我们怀疑用户i比用户j更有可能通过加性因子α执行了该动作（其中i和j分别表示由和选择让我们考虑由三个节点组成的线性图上的DCP，即三个密码学家Crypt0，Crypt1和Crypt2，以及两条边，Crypt0和Crypt1之间的Coin0，以及Crypt1和Crypt2之间的Coin1。如果其中一个密码破译者支付（事件a），可能的可观察值为o1= 111o2 = 100o3 = 010o4 = 001其中，b0b1b2分别指Crypt0、Crypt1和Crypt2例如，如果Crypt1是付款人，那么当两个硬币都给出1时获得o1，当硬币0给出1而硬币1给出0时获得o2，等等。例如，当Coin0给出1，Coin1给出0时，得到o5= 110对应于这种情况的概率自动机如图2所示。为了简单起见，我们只画出了对应于观测值o 1、o 2等的重要的是要注意，我们将只考虑一种形式的非确定性：与主节点的选择相关联的非确定性主节点，在Y. Deng等人理论计算机科学电子笔记180（2007）5563观测值：o1= 111，o2= 100，o3= 010，o4= 001地穴0支付地穴1支付地穴2支付p（o1）β0（1 −β1）（1−β0）（1−β1）（1 −β0）β1p（o2）β0 β1（1 −β0）β1（1−β0）（1−β1）p（o3）（1 −β0）β1β0 β1β0（1 −β1）p（o4）（1−β0）（1−β1）β0（1 −β1）β0 β1表1线性图上3个密码学家情况下观测值的概率DCP是非确定性用户的同义词）。 一般来说，在一个系统中，也存在着由系统的各个组件的不同可能的交错所引起的不确定性在任何情况下，可以证明后一种形式的非决定论不会影响DCP关于匿名性的属性。让我们用βi表示硬币i的我们想确定匿名性（定义3.1）的参数α如何依赖于β0和β1。考虑，对于每个在密码学家中选择付款人的调度器，可能的可观察量及其概率度量。一个简单的计算给出了表1所示的数字。通过案例分析，我们得出：⎧⎨|1 −（β0+ β1）| 如果（β0，β1≤ 0. 5）或（β0，β1≥0. 5）、α=α|如果（β 0 > 0.| if (β0> 0. 5和β<10。5）或（β0<0. 5和β1> 0。5）、图3显示了α作为β0和β1的函数的曲线图。上述分析可以推广到具有任意数目节点的线性图的一般情况。定理3.2在n个节点的线性图上的DCP中，定义3.1中的α依赖于βiα=βi（1−βj）−（1−βi）βjβi ≥0。5βj<0.5βi≥0。5βj<0. 5一个可观测值的最高可能概率对应于硬币的配置Coini=0 对于β i≥ 0. 5 ，硬币j= 1为 β j<0. 5（1）相反，最小概率对应于对于β i≥ 0，硬币j =1。5和64Y. Deng等人理论计算机科学电子笔记180（2007）55CoinJ= 0，对于β j<0。第五章（二）I jY. Deng等人理论计算机科学电子笔记180（2007）5565我0n−20非确定性主：两个有偏见的硬币匿名性10.90.80.70.60.50.40.30.20.1000.10.2秒0.910.80.70.60.50.30.4个单位00.50.60.70.4升0.30.20.80.9100.1图3.第三章。三个密码学家情况下α-匿名性对β0和β1的依赖性显然，这些配置是分别以概率p1=βi（1−βj） 和p2=（1−βi）βjβi ≥0。5βj<0.5βi≥0。5βj<0. 5现在我们只需要证明，对于同一个可观测量，这两个概率都可以得到（在不同的条件下）。考虑（1）中的硬币配置设Crypt为选择Crypt0作为付款人的调度程序然后系统将输出可观测的o = b0b1. b n−1其中（使用表示二进制和）b0=硬币0 1bi=Coini−1<$Coinifor 1≤i≤n− 2bn−1=Coinn −2显然p（o）=p1。现在考虑（2）中的硬币配置设tcp为选择的调度程序Cryptn-1作为付款人。 很容易看出，输出oJ= bJbJ. BJ的0 1n−1系统与之前相同，事实上对于每个i，CoinJ=Coini<$1。 因此，我们有：J =硬币J=硬币0 1 =b0bJ=CoinJ <$CoinJ=Coini−1<$1<$Coini<$1ii−1i=Coini−1<$Coini=bifor 1≤i≤n− 2Jn−1 =硬币J1 =Coinn−2因此，我们有oJ=o和p（o）=p2。QBB166Y. Deng等人理论计算机科学电子笔记180（2007）55地穴0p0p1pp3主2支付支付o1O2地穴1支付地穴2支付O8O7O3O4O6o1O2O4O5OO34o1oO321.0510.950.90.850.80.750.70.650.60.550.50.450.40.350.30.250.20.150.10.050带偏因子3 密码学家4 密码学家5 密码学家6 密码学家0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 1.05硬币（Uniform Coins）见图4。 3-6人情况下α-匿名性对β的依赖性图五.有三个密码学家和概率大师的DCP。可以证明，当拓扑为 戒指另一方面，它不适用于包含一个或多个具有奇数个相邻边的节点的图。图4展示了3到6个密码学家的α对β的依赖关系，其中对于所有i，βi=β（均匀硬币）。我们注意到，匿名级别增加（即，α减小）随着密码学家的数量增加。如果硬币是公平的（β = 0。5），则我们具有强匿名性，即。α= 0。在β= 0或β= 1的两个极端情况下，α-匿名性总是1，这是最大的。也可以证明α可以用β上的多项式表示，如果n是偶数，则多项式的次数为n−1，如果n是奇数，则多项式的次数为n−4概率用户在本节中，我们考虑根据特定概率分布选择用户的情况。由于我们假设没有其他非确定性的来源，因此我们在本节中考虑的自动机是完全概率的。例如，在有三个密码学家的DCP的情况下，我们有图5所示的自动机。匿名性Y. Deng等人理论计算机科学电子笔记180（2007）5567我4.1专注于观察到定义3.1的完全概率版本，也对应于定义2.3的弱版本，如下所示定义4.1[概率用户的α-匿名性]给定α∈[0， 1]，一个完全概率系统（M，I，a，B，p）是α-匿名的，如果max{p（o|a（i））−p（o|a（j））|i，j∈I，o∈O，p（a（i））> 0，p（a（j））> 0}= α像定义3.1一样，这个概念关注的是可观测量的概率。可以证明，对于DCP，上述定义的α取决于βi事实上，在非确定性用户的情况下，考虑选择i的调度器，即，p∈（a（i））= 1. 然后假设，在概率用户的情况下，p∈（a（i））>0。 它 很容易看出p（o）= p（o|a㈠）。因此，从某种意义上说，定义4.1中提出的匿名性概念似乎并没有引入任何新的技术挑战。在下一节中，我们将研究定义2.4中给出的匿名性替代概念的弱版本。4.2关注用户的概率我们在这里采取的观点是，匿名意味着保留用户的概率，就像[6]和[7]一样。定义4.2[概率用户的α-匿名α∈[0， 1]，全概率系统（M，I，a，B，p）是α-匿名的，如果（i）a（i）|o）− p（a（i）|a）、|i ∈ I，o ∈ O，p（o ∈ a）> 0}= α直觉，p（a（i））|o）−p（a（i）|a）= α意味着，在观察到o之后，我们认为i是动作执行者的概率增加了一个加性因子α。现在我们研究在n为DCP的情况下α对βi的依赖性线性图上的密码学家。我们需要引入一些定义：设pi是Crypt是付款人的概率当然，其中一个乌斯季-1密码学家是付款人，那么p。 设k为密码学家概率最大，即i=0ip k= max {p i|i ∈ [0，n − 1]}对于i∈[0，n− 2]，定义⎧如果β i≥ 0，则为β i。5γi=π1−βi，否则68Y. Deng等人理论计算机科学电子笔记180（2007）55⎪⎪最后，对于任意j∈[0，n− 1]，定义⎧qj=j−1⎪⎨γii=0时克-1⎪⎩γik−1（1−γi）i=jj−1（1−γi）n−2i=kn−2γi，如果j≤kγi否则i=0时I=kI=j现在我们可以说明α如何依赖于βi定理4.3在n个节点的线性图上的DCP中，定义4.2中的α依赖于βiqk pkα=n−1qj pjj=0PK-n−1PJj=0（三）根据定义，具有最高概率的硬币的配置是当β i≥ 0时Coin i = 0的配置。5，否则Coini= 1该配置的概率为βi（1−βl）=n−2γi=qkβi ≥0。5β=<0。5i=0时现在考虑事件a（k），表示Cryptk是付款人，令o=b0b1. b n−1是对应于上述硬币配置与事件a（k）的可观察量。我们将证明o和a（k）使表达式p（a（i））最大化|oJ）−p（a（i）|并且它等于公式（3）。 第一我们需要计算条件概率p（a（k））|o）= p（o∈a（k））/p（o）。根据定义，p（oa（k））=qk pk。 对于p（o），观察p（o<$a（j））=qj pj，对于任何j∈[0，n- 1]，实际上当Cryptj是付款人时，要获得相同的o，就必须：将j和k之间的所有硬币进行IP化，这给出了具有概率的硬币配置qj. 因此，我们有n−1p（o）=j=0p（oa（j））=n−1j=0qj pj最后，很容易看出，p（a（k））|o）最大化p（a（i））|oJ），它是线性的在p（a（k）上，并且p（a（j））|a）= p（a（j））/p（a）。因此，p（a（k）|o）−p（a（k）|a）最大化p（a（i））|oJ）−p（a（i）|与公式（3）一致。Q图6显示了在三个密码子的情况下α对βi不同的图形表示付款人的不同概率分布。值得注意的是，与定义4.1中给出的α-匿名性概念相反，本节中给出的版本不仅依赖于βi在p（a（i））上。另一方面，在强匿名的极限情况下，这两个概念是等价的，如2.3节所解释的。Y. Deng等人理论计算机科学电子笔记180（2007）5569prbcallmaster：匿名，p（a0）=p（a1）=p（a2）匿名性0.70.60.50.40.30.20.1000.10.2秒0.910.80.70.60.50.30.4个单位00.50.60.70.80.90.4升0.30.2100.1匿名-匿名：p（a0）=0.5，p（a1）=0.3，p（a2）=0.2匿名性0.80.70.60.50.40.30.20.1000.10.2秒0.910.80.70.60.50.30.4个单位00.50.60.70.4升0.30.20.80.9100.1匿名性：p（a0）=0.98，p（a1）=0.05，p（a2）=0.05匿名性10.90.80.70.60.50.40.30.20.1000.10.2秒0.910.80.70.60.50.30.4个单位00.50.60.70.4升0.30.20.80.9100.1图六、三个密码学家情况下α-匿名性对βi的依赖性11170Y. Deng等人理论计算机科学电子笔记180（2007）555自动分析在一个非常简单的拓扑（线性图）的情况下，我们已经能够用一个数学公式来表示α对βi通过这种方式，如果我们有一个系统，其内部偏差是已知的，那么可以立即检查它是否满足弱匿名性（对于给定的α）。也可以将该方法扩展到环，但是随着图变得更加复杂，不清楚如何继续找到表示依赖关系的公式。这是大多数现实系统的典型情况：符号分析通常是不可行的，我们必须求助于计算机支持的自动工具。在这一节中，我们描述了如何使用概率模型检查器PRISM来检查DCP的α-匿名性。我们考虑非确定性和概率主节点（回想一下，在DCP中，非确定性/概率主节点是非确定性/概率用户的同义词我们建模的DCP作为一个离散时间马尔可夫链（DTMC）的情况下，一个概率的主，和马尔可夫决策过程（MDP）的情况下，一个不确定的主4。PRISM输入语言是一种简单的、基于状态的语言，它基于ReactiveModules formalism（英语：Reactive Modules formalism）[1]。使用时间概率逻辑PCTL [8]对事件进行形式化。一旦这个转换完成，我们可以使用PRISM来计算相关事件的概率，以检查α-匿名性。PRISM和PCTL的简要概述见附录。下面的代码是为三个密码学家和两个硬币排列成一行。它可以很容易地推广到更多的密码学家和不同的图结构。首先，我们描述我们在模型中使用的变量。N是密码学家的数量，由于拓扑结构是一条线，因此模型中有N-1个硬币。每个硬币出现正面的概率被定义为beta0，beta1等，我们定义了三个状态变量：s master：[0.. 2]为主人的硬币：[0... N-1]表示有多少硬币已被加密，s crypt：[0..表示有多少密码学家决定了他们的输出。payerid=N表示没有密码学家会付钱，或者主人还没有决定。最初，它们都是0。一旦执行终止，我们将得到s master=2，s coin=N-1，scrypt=N。变量payerid：[0.. N] init N用于记录谁是付款人。变量toss：bool initfalse用于在master做出决定后将硬币取出。在下面，我们考虑N= 3的情况。我们使用变量crypt0，crypt1，crypt2来记录每个密码学家计算的值，这些值是0或1，取决于密码学家是否支付以及密码学家可以看到的硬币的侧面。初始值为0。在模型中，有两个硬币coin0和coin1。第一个由密码学家0和1共享，第二个由密码学家1和2共享。我们用0表示头，1表示尾。接下来，我们描述主人、硬币和密码破译者的行为。4PRISM所接受的DTMC和MDP格式可以看作是概率自动机的特殊情况。Y. Deng等人理论计算机科学电子笔记180（2007）5571如果主人是不确定的，他将不确定地决定付款人：密码学家之一（payerid = 0，1或2）或他自己（payerid=3）。一旦他做出决定，toss的值被设置为true，以便让硬币被丢弃。[]（s master=0）→（s&&&[]（s master=1）（！toss）→（s &master '= 2）（toss'= true）;如果主人是概率性的，那么付款人的选择是基于概率分布的。例如：[]（s master=0）0.5：（s0.3：（s[]（s master=1）（！toss）→（s &master '= 2）（toss'= true）;一旦掷硬币成为真，硬币就开始翻转。在概率beta0和beta1的情况下，硬币的一面将是正面。在概率为1-beta 0和1-beta1的情况下，硬币的一面将是反面。每一次当一枚硬币被投掷时，的硬币增加了一个。[]（s coin=0）（toss）→beta0：（（1-beta0）：（beta1：（（1-beta1）：（在所有的硬币都被加密后（s coin=N-1），密码学家计算它们的变量crypt 0，crypt 1和crypt 2的值。一旦密码学家终止了这个计算，s crypt的值就增加1。由于密码学家0和2坐在线的两端，他们只能观察一枚硬币：密码学家0看到硬币0，密码学家2看到硬币1。 如果密码学家 0是付款人，如果他看到硬币0的头部，他会将变量crypt0设置为1，否则设置为0。如果Cryptographer 0不是付款人，如果他看到硬币0的头部，他会将crypt0设置为0，否则设置为1。Cryptographer 2的代码类似：将crypt0重命名为crypt2，将coin0重命名为coin1，将s crypt=0重命名为s crypt=2。[]（s crypt=0）（s coin=N-1）（payerid=0）（coin0=0）s→（crypt0'=1）（s crypt'=s crypt+1）;[]（s crypt=0）（s coin=N-1）！（payerid=0）&（coin0=0）→（[]（s crypt=0）（s coin=N-1）（payerid=0）（coin0=1）→（72Y. Deng等人理论计算机科学电子笔记180（2007）55[]（s crypt=0）（s coin=N-1）！（payerid=0）&（coin0=1）→（密码学家1的行为略有不同，因为他可以观察到两个硬币。如果他是付款人，如果两个硬币有相同的一面，他会将变量crypt1设置为1，否则设置为0。如果他不是付款人，如果两个硬币有相同的一面，他会将crypt1设置为0，否则设置为1。[]（s crypt=1）（s coin=N-1）（payerid=1）（coin1=coin0）→（[]（s crypt=1）（s coin=N-1）！（payerid=1）&（coin1=coin0）→（[]（s crypt=1）（s coin=N-1）（payerid=1）！（coin1=coin0）→（[]（s crypt=1）（s coin=N-1）！（payerid=1）！（coin1=coin0）→（在规范的末尾添加了自循环，以避免死锁状态5。[]（s coin=N-1）（s master=2）（s crypt=N）→（s在DCP中，外部观察者可以看到变量crypt0、crypt2和crypt2的值。此外，PRISM模型中变量的值定义了系统的状态。例如，下面的谓词表示所有密码学家输出1的最终状态。我们用O1表示。（crypt0=1）（crypt1=1）（crypt2=1）（s crypt=3）（s coin=2）（smaster=2）对于每种类型的主数据（非确定性或概率性），我们可以使用P运算符将观测值描述为PCTL公式（见附录A.2）。 然后，我们可以使用PRISM来计算每个观察点的概率以进行分析匿名性不确定性主节点：如果主机是不确定的，我们可以计算每个可观察的最大和最小概率，在任何可能的调度器，选择一个密码支付。下面，我们指定PCTL公式来计算可观测值o1的概率。Pmax=？[true U o1]和Pmin=？[trueUo1]因此，使用由以下命题给出的α-匿名性的公式是足够的，其证明是立即的：命题5.1一个系统（M，I，a，B，Z，p）是α-匿名的（关于非匿名的）5 这是PRISM设计的要求。Y. Deng等人理论计算机科学电子笔记180（2007）5573确定性用户），如果max{max {p <$（o）|<$∈ Z，p <$（o <$a）= p <$（o）}−min{p}（o） | ϑ ∈ Z, p（oa）= p（o）}|o∈ O}=α图4中的结果已经使用PRISM进行了检查。首席大法官：当主节点不确定时，α-匿名被定义为：（i）a（i）|o）− p（a（i）|a）、|i ∈ I，o ∈ O，p（o ∈ a）> 0}= α.由于PRISM不支持作为原语的条件概率的计算，因此我们必须计算每个p（a（i））|o）使用等价表达式p（a（i）o）/p（o）。对于p（a（i）|a），这与p（a（i））/p（a）相同。 例如，在三个密码学家的情况下，可以通过使用PCTL公式来计算p（a（0）≠P=？[trueUo1（payerid=0）]图6所示的结果已使用PRISM进行了检查。6结论及相关工作我们提出了两个弱概率匿名的概念，分别为nondeterministic和概率用户的情况下。我们已经将这两个概念应用于具有偏置硬币的DCP，并且我们已经描述了弱势水平对硬币的偏置因子的函数依赖性。此外，我们还在PRISM中编码了DCP和表示弱匿名性的公式本文建立在我们在2.3节中总结的[4]中提出的概率匿名框架上。我们在这里研究的概念代表了[4]中提出的强概率匿名性的推广。据我们所知，概率匿名的第一个概念是在[6]中提出的（尽管没有明确的定义）。这个概念对应于[4]中研究的概率用户的强匿名性概念之一，更确切地说，是定义2.4中提到的概念。这就是我们在定义4.2中给出的弱版本的概念。在
