路网环境下兴趣点查询的隐私保护方法

近年来,随着无线通信技术的迅猛发展,推动了基于位置服务（Location-based services,LBS）的发展进程.而其中兴趣点（Point of Interest,POI）查询是基于位置服务最重要的应用之一.针对在路网环境下,用户查询过程中位置隐私泄露的问题,提出了一种新的位置k匿名隐私保护方法.首先,匿名服务器将兴趣点作为种子节点生成网络Voronoi图,将整个路网划分为相互独立且不重叠的网络Voronoi单元（Network Voronoi Cell,NVC）;其次,利用Hilbert曲线遍历路网空间,并按照Hilbert顺序,对路网上所有的兴趣点进行排序.当用户发起查询时,提出的匿名算法通过查找与用户所在NVC的查询频率相同且位置分散的k-1个NVC,并根据用户的相对位置在NVC内生成匿名位置,从而保证了生成的匿名集中位置之间的相互性,克服了传统k-匿名不能抵御推断攻击的缺陷.最后,理论分析和实验结果表明本文提出的隐私保护方案,能有效保护用户位置隐私.     

基于安全多方计算的多候选人电子投票方案

多候选人的电子投票方案在很多实际选举场景中有重要的应用价值.全隐私性是安全电子投票方案关注的一个重要性质,是指对选民和候选人的隐私保护.本文基于安全多方计算提出了一个多选多的电子投票方案.此方案将选民的投票意见映射为数组的形式,结合ElGamal同态加密系统,在半诚实模型下由选民和候选人通过交互计算输出选举结果,实现了...     

在消息传递并行机上的高效的最小生成树算法

基于传统的Borǔ vka串行最小生成树算法,提出了一个在消息传递并行机上的高效的最小生成树算法.并且采用3种方法来提高该算法的效率,即通过两趟合并及打包收缩的方法来减少通信开销,通过平衡数据分布的办法使各个处理器的计算量平衡.该算法的计算和通信复杂度分别为O(n²/p)和O((t_sp+t_wn)n/p).在曙光-1000并行机上运行的实际效果是,对于有10 000个顶点的稀疏图,通过16个节点的运行加速比是12.     

基于数据流传播路径学习的智能合约时间戳漏洞检测

智能合约是一种被大量部署在区块链上的去中心化的应用. 由于其具有经济属性, 智能合约漏洞会造成潜在的巨大经济和财产损失, 并破坏以太坊的稳定生态. 因此, 智能合约的漏洞检测具有十分重要的意义. 当前主流的智能合约漏洞检测方法(诸如Oyente和Securify)采用基于人工设计的启发式算法, 在不同应用场景下的复用性较弱且耗时高, 准确率也不高. 为了提升漏洞检测效果, 针对智能合约的时间戳漏洞, 提出基于数据流传播路径学习的智能合约漏洞检测方法Scruple. 所提方法首先获取时间戳漏洞的潜在的数据传播路径, 然后对其进行裁剪并利用融入图结构的预训练模型对传播路径进行学习, 最后对智能合约是否具有时间戳漏洞进行检测. 相比而言, Scruple具有更强的漏洞捕捉能力和泛化能力, 传播路径学习的针对性强, 避免了对程序整体依赖图学习时造成的层次太深而无法聚焦漏洞的问题. 为了验证Scruple的有效性, 在真实智能合约的数据集上, 开展Scruple方法与13种主流智能合约漏洞检测方法的对比实验. 实验结果表明, Scruple在检测时间戳漏洞上的准确率, 召回率和F1值分别可以达到0.96, 0.90和0.93, 与13种当前主流方法相比, 平均相对提升59%, 46%和57%, 从而大幅提升时间戳漏洞的检测能力.     

基于节点1-邻居图相似性的社会网络匿名技术

利用传统的k匿名技术在社会网络中进行隐私保护时会存在聚类准则单一、图中数据信息利用不足等问题. 针对该问题, 提出了一种利用Kullback-Leibler (KL)散度衡量节点1-邻居图相似性的匿名技术(anonymization techniques for measuring the similarity of node 1-neighbor graph based on Kullback-Leibler divergence, SNKL). 根据节点1-邻居图分布的相似性对原始图节点集进行划分, 按照划分好的类进行图修改, 使修改后的图满足k匿名, 完成图的匿名发布. 实验结果表明, SNKL方法与HIGA方法相比在聚类系数上的改变量平均降低了17.3%, 同时生成的匿名图与原始图重要性节点重合度保持在95%以上. 所提方法在有效保证隐私的基础上, 可以显著的降低对原始图结构信息的改变.     

基于安全多方求和的多候选人电子选举方案

多候选人电子选举方案在许多实际环境下具有重要的应用价值,但现有绝大多数方案由于技术限制只能进行“两选一”投票．设计了一种新型的选票结构,在一个多精度数中隐藏“m选k”形式的选票。对m个候选人至多可以投k个赞成票;将多精度计算及安全多方求和协议应用于投票和计票,选举过程中不需要可信任第3方,任何投票人都可以计票．与一般方案相比,该方案具有更强的安全性,包括选票的完全保密性和无收据性、计票的公平性和无争议性、系统的健壮性等;无需使用传统的加密技术．对n个投票人,计算的位复杂性为O （ nm （log2 n ））,其效率优于现有方案且容易实现．     

面向数值型敏感属性的隐私保护方案

针对现有的个性化隐私匿名技术不能很好地解决数值型敏感属性容易遭受近邻泄漏的问题,提出了一种基于聚类技术的匿名模型——（ε_i,k）-匿名模型.该模型首先基于聚类技术将按升序排列的敏感属性值划分到几个值域区间内;然后,提出了针对数值型敏感属性抵抗近邻泄漏的（ε_i,k）-匿名原则;最后,提出了一种最大桶优先算法来实现（ε_i,k）-匿名原则.实验结果表明,与已有的面向数值型敏感属性抗近邻泄漏方案相比,该匿名方案信息损失降低,算法执行效率提高,可以有效地降低用户隐私泄露风险.     

取定s的严格d-正则随机(3,2s)-SAT问题的可满足临界

3-CNF公式的随机难解实例生成对于揭示3-SAT问题的难解实质和设计满足性测试的有效算法有着重要意义.对于整数k>2和s>0,如果在一个k-CNF公式中每个变量正负出现次数均为s,则称该公式是严格正则（k,2s）-CNF公式.受严格正则（k,2s）-CNF公式的结构特征启发,提出每个变量正负出现次数之差的绝对值均为d的严格d-正则（k,2s）-CNF公式,并使用新提出的SDRRK2S模型生成严格d-正则随机（k,2s）-CNF公式.取定整数5<s<11,模拟实验显示,严格d-正则随机（3,2s）-SAT问题存在SAT-UNSAT相变现象和HARD-EASY相变现象.因此,立足于3-CNF公式的随机难解实例生成,研究了严格d-正则随机（3,2s）-SAT问题在s取定时的可满足临界.通过构造一个特殊随机实验和使用一阶矩方法,得到了严格d-正则随机（3,2s）-SAT问题在s取定时可满足临界值的一个下界.模拟实验结果验证了理论证明所得下界的正确性.     

离散多智能体系统中分布式事件触发的H∞滤波

研究了具有切换拓扑的离散时间多智能体系统的事件触发H_∞滤波问题.构造了一种新的分布式事件触发控制方案,以确定是否每个智能体应该传输当前采样数据到滤波器,从而有效的节约网络资源.考虑到网络诱导时延的存在,同时利用马尔可夫过程对网络拓扑的切换进行建模,采用事件触发控制方案并结合所提的H_∞滤波器,将分布式滤波误差系统建模成一个具有多时变时延的闭环系统.利用包含多区间上下界信息的Lyapunov-Krasovskii泛函和线性矩阵不等式方法,得到了保证闭环系统实现具有H_∞性能指标渐近稳定性的一些充分条件和H_∞滤波器参数的设计方法.最后,通过两个数值算例说明了该方法的有效性.     

k-LSAT (k≥3)是NP-完全的

合取范式(conjunctive normal form,简称CNF)公式F是线性公式,如果F中任意两个不同子句至多有一个公共变元.如果F中的任意两个不同子句恰好含有一个公共变元,则称F是严格线性的.所有的严格线性公式均是可满足的,而对于线性公式类LCNF,对应的判定问题LSAT仍然是NP-完全的.LCNF_≥k是子句长度大于或等于k的CNF公式子类,判定问题LSA(≥k)的NP-完全性与LCNF(≥k)中是否含有不可满足公式密切相关.即LSAT_≥k的NP-完全性取决于LCNF_≥k是否含有不可满足公式.S.Porschen等人用超图和拉丁方的方法构造了LCNF_≥3和LCNF_≥4中的不可满足公式,并提出公开问题:对于k≥5,LCNF_≥k是否含有不可满足公式?将极小不可满足公式应用于公式的归约,引入了一个简单的一般构造方法.证明了对于k≥3,k-LCNF含有不可满足公式,从而证明了一个更强的结果:对于k≥3,k-LSAT是NP-完全的.     

Credibility of Social Network Sites for Political Information Among Politically Interested Internet Users

Scholars have confirmed that political candidates are increasingly turning to social network sites (SNS) to persuade voters to vote for them, and that these sites have become prominent sources of political information. But a fundamental question arises about the sustainability of social networks as a campaign tool: How much do users trust the information they find there? This study employed an online survey to examine the degree to which politically interested online users view SNS as credible. SNS were ranked the least credible among the nine traditional and online sources examined. Reliance on social networks proved the strongest predictor of SNS credibility.     

一种Internet上的匿名电子投票协议的研究与设计

文章讨论了一种适合在Internet上进行大范围投票的电子投票协议,这个协议通过传送不可追踪的授权消息允许投票者进行匿名投票。协议保证了以下几点:(1)只有符合条件的投票者可以投票;(2)每个投票者只能投票一次;(3)投票者可以查询他的投票是否生效;(4)除了投票者本人,任何人都不能根据投票找到投票者;(5)如果某个投票者弃权,任何人都不能以他的名义进行投票。     

Towards a dichotomy for the Possible Winner problem in elections based on scoring rules

To make a joint decision, agents (or voters) are often required to provide their preferences as linear orders. To determine a winner, the given linear orders can be aggregated according to a voting protocol. However, in realistic settings, the voters may often only provide partial orders. This directly leads to the Possible Winner problem that asks, given a set of partial votes, whether a distinguished candidate can still become a winner. In this work, we consider the computational complexity of Possible Winner for the broad class of voting protocols defined by scoring rules. A scoring rule provides a score value for every position which a candidate can have in a linear order. Prominent examples include plurality, k-approval, and Borda. Generalizing previous NP-hardness results for some special cases, we settle the computational complexity for all but one scoring rule. More precisely, for an unbounded number of candidates and unweighted voters, we show that Possible Winner is NP-complete for all pure scoring rules except plurality, veto, and the scoring rule defined by the scoring vector (2,1,…,1,0), while it is solvable in polynomial time for plurality and veto.     

The complexity of online voter control in sequential elections

Previous work on voter control, which refers to situations where a chair seeks to change the outcome of an election by deleting, adding, or partitioning voters, takes for granted that the chair knows all the voters’ preferences and that all votes are cast simultaneously. However, elections are often held sequentially and the chair thus knows only the previously cast votes and not the future ones, yet needs to decide instantaneously which control action to take. We introduce a framework that models online voter control in sequential elections. We show that the related problems can be much harder than in the standard (non-online) case: For certain election systems, even with efficient winner problems, online control by deleting, adding, or partitioning voters is \(\mathrm {PSPACE}\)-complete, even if there are only two candidates. In addition, we obtain (by a new characterization of coNP in terms of weight-bounded alternating Turing machines) completeness for \({\mathrm {coNP}}\) in the deleting/adding cases with a bounded deletion/addition limit, and we obtain completeness for \({\mathrm {NP}}\) in the partition cases with an additional restriction. We also show that for plurality, online control by deleting or adding voters is in \({\mathrm {P}}\), and for partitioning voters is \({\mathrm {coNP}}\)-hard.     

Multi-Candidate Voting Model Based on Blockchain

Electronic voting has partially solved the problems of poor anonymity and low efficiency associated with traditional voting. However, the difficulties it introduces into the supervision of the vote counting, as well as its need for a concurrent guaranteed trusted third party, should not be overlooked. With the advent of blockchain technology in recent years, its features such as decentralization, anonymity, and non-tampering have made it a good candidate in solving the problems that electronic voting faces. In this study, we propose a multi-candidate voting model based on the blockchain technology. With the introduction of an asymmetric encryption and an anonymity-preserving voting algorithm, votes can be counted without relying on a third party, and the voting results can be displayed in real time in a manner that satisfies various levels of voting security and privacy requirements. Experimental results show that the proposed model solves the aforementioned problems of electronic voting without significant negative impact from an increasing number of voters or candidates.      

融合可链接环签密的智能合约电子投票协议

电子投票与传统投票方式相比更具经济性,但存在安全性论证不够严谨、运行时间长、计算消耗较大等问题。提出融合可链接环签密的智能合约电子投票协议,分别设计投票、秘密份额上传、计票等阶段的算法,在投票阶段基于椭圆曲线离散对数问题生成选票的可链接环签密,并在一个逻辑步骤内实现加密和签名,以确保投票的公正性、机密性和可验证性,避免重复投票情况的发生,从总体上降低协议运行时间和计算消耗的gas。此外,详细分析协议的安全性,基于椭圆曲线上的离散对数问题证明选票环签密的不可伪造性。使用truffle框架将智能合约部署到本地以太坊私有网络上,并通过挖矿以确认交易完成。实验结果表明,与Lyu协议相比,该协议节省了约10⁷ Gwei的计算消耗以及450 ms左右的运行时间。     

基于以太坊区块链的公平可搜索加密方案

传统的对称可搜索加密解决了云存储中加密数据的检索问题,但是没有考虑到检索的公平性问题,即用户在支付了服务费后服务器没有返回检索结果或返回错误的检索结果的情况。随着区块链的出现,基于比特币的对称可搜索加密方案被提出,但是比特币系统的交易周期长,且比特币的脚本语言不是图灵完备的,不能适用于更多的场景。因此提出基于以太坊区块链和智能合约的对称可搜索加密方案,在保证数据隐私性的同时,解决了检索的公平性问题。安全性和性能分析结果表明该方案是可行的。     

RLWE同态加密算法的多候选人电子投票协议

使用安全协议保护选民隐私、保证投票公正有效是投票电子信息化的基础,安全协议的复杂度则是电子投票应用的最大阻碍。提出了一种基于RLWE同态加密算法的多候选人电子投票协议,可支持多候选人,也能满足对选民隐私的保护。该协议利用基于RLWE的同态加密算法的加法同态性质在计票环节使用密文计票保护选民的私密,利用中国剩余定理的性质对选票进行批处理,提升计票能力。该投票协议能支持多候选人投票并最终知晓每个候选人最终票数,并设置公示机构公示投票过程中的每个步骤,用于公开验证。     

电子投票匿名性分析

电子投票公布计票结果会影响投票者的匿名性。针对该问题,定义匿名性为投票选择的不确定度,利用熵衡量投票系统的投票者匿名性,比较计票结果公布前后投票者的匿名性变化。分析结果表明,投票规模越小,投票者匿名性在结果公布后受到的损失越大;在小规模电子投票情况下,计票结果应该选择只公布获胜者,不公布具体得票数,以减少投票者匿名的损失。     

无可信中心的电子投票方案*

给出一个无可信中心的电子投票方案,即使在管理机构和计票机构都不可信的情况下仍能够保证投票的安全性。该方案能够始终保证投票者的匿名性,即使选票公开,任何人都不能确定投票者的身份;解决了选票碰撞的问题,即不同的投票人必定产生不同的选票。