论文标题

Coinmagic:环形签名方案的差异隐私框架

CoinMagic: A Differential Privacy Framework for Ring Signature Schemes

论文作者

Ni, Wangze, Wu, Han, Cheng, Peng, Chen, Lei, Lin, Xuemin, Chen, Lei, Lai, Xin, Zhang, Xiao

论文摘要

通过允许用户通过包括“ Mixins”(Chaff Coins)的交易来掩盖其交易,环形签名方案已被广泛用于保护发件人在隐私保护区块链系统中的交易的身份,例如Monero和Bytecoin。但是,最近的作品指出,现有的环形签名方案容易受到“链反应”分析的影响(即,可以通过消除来推导给定环签名中的花硬币)。特别是,当混合蛋白的多样性较低时,用过的硬币将具有很高的风险。为了克服弱点,环特征应由一组具有高多样性的混合蛋白组成,并产生对任何两个硬币的“相似”分布的观测值。在本文中,我们提出了一个概念,即$ε$ -coin-coin-rindistingability($ε$ -CI),以正式定义通过差异隐私方案保证的“相似”分布。然后,我们正式定义了Ci-Awawe Mixins的选择问题,该问题与脱节 - 苏佩塞特约束(CIA-MS-DS),该问题旨在找到具有最大多样性的Mixin集合,并满足$ε$ -CI和预算的约束。在CIA-MS-DS中,每个环签名与其先前的环签名的超集脱节或超集。我们证明了CIA-MS-DS是NP-HARD,因此棘手。为了解决CIA-MS-DS问题,我们提出了两种近似算法,即渐进算法和游戏理论算法,并提供理论保证。通过对实际数据集和合成数据集的广泛实验,我们证明了方法的效率和有效性。

By allowing users to obscure their transactions via including "mixins" (chaff coins), ring signature schemes have been widely used to protect a sender's identity of a transaction in privacy-preserving blockchain systems, like Monero and Bytecoin. However, recent works point out that the existing ring signature scheme is vulnerable to the "chain-reaction" analysis (i.e., the spent coin in a given ring signature can be deduced through elimination). Especially, when the diversity of mixins is low, the spent coin will have a high risk to be detected. To overcome the weakness, the ring signature should be consisted of a set of mixins with high diversity and produce observations having "similar" distributions for any two coins. In this paper, we propose a notion, namely $ε$-coin-indistinguishability ($ε$-CI), to formally define the "similar" distribution guaranteed through a differential privacy scheme. Then, we formally define the CI-aware mixins selection problem with disjoint-superset constraint (CIA-MS-DS), which aims to find a mixin set that has maximal diversity and satisfies the constraints of $ε$-CI and the budget. In CIA-MS-DS, each ring signature is either disjoint with or the superset of its preceding ring signatures. We prove that CIA-MS-DS is NP-hard and thus intractable. To solve the CIA-MS-DS problem, we propose two approximation algorithms, namely the Progressive Algorithm and the Game Theoretic Algorithm, with theoretic guarantees. Through extensive experiments on both real data sets and synthetic data sets, we demonstrate the efficiency and the effectiveness of our approaches.

扫码加入交流群

加入微信交流群

微信交流群二维码

扫码加入学术交流群,获取更多资源