Publications
2019
-
-
(2019) COMPUTER SCIENCE - THEORY AND APPLICATIONS. Kucherov G. & VanBevern R.(eds.). p. 359-371 (trueLecture Notes in Computer Science). Abstract
Preventing fake or duplicate e-identities (aka sybils) from joining an e-community may be crucial to its survival, especially if it utilizes a consensus protocol among its members or employs democratic governance, where sybils can undermine consensus, tilt decisions, or even take over. Here, we explore the use of a trust graph of identities, with trust edges representing trust among identity owners, to allow a community to grow without increasing its sybil penetration. Since identities are admitted to the e-community based on their trust by existing e-community members, corrupt identities, which may trust sybils, also pose a threat to the e-community. Sybils and their corrupt perpetrators are together referred to as Byzantines, and our overarching aim is to limit their penetration into an e-community. Our key tool in achieving this is graph conductance, and our key assumption is that honest people are averse to corrupt ones and tend to distrust them. Of particular interest is keeping the fraction of Byzantines below one third, as it would allow the use of Byzantine Agreement (see Lamport et al. The Byzantine generals problem, ACM Transactions on Programming Languages and Systems, 4(3):382-401, 1982) for consensus as well as for sybil-resilient social choice (see Shahaf et al., Sybil-resilient reality-aware social choice, arXiv preprint arXiv:1807.11105, 2019). We consider sequences of incrementally growing trust graphs and show that, under our key assumption and additional requirements, including keeping the conductance of the community trust graph sufficiently high, a community may grow safely.
-
Genuine Personal Identifiers and Mutual Sureties for Sybil-Resilient Community Formation(2019) arXiv. Abstract
While most of humanity is suddenly on the net, the value of this singularity is hampered by the lack of credible digital identities: Social networking, person-to-person transactions, democratic conduct, cooperation and philanthropy are all hampered by the profound presence of fake identities, as illustrated by Facebook's removal of 5.4Bn fake accounts since the beginning of 2019. Here, we introduce the fundamental notion of a \emph{genuine personal identifier}---a globally unique and singular identifier of a person---and present a foundation for a decentralized, grassroots, bottom-up process in which every human being may create, own, and protect the privacy of a genuine personal identifier. The solution employs mutual sureties among owners of personal identifiers, resulting in a mutual-surety graph reminiscent of a web-of-trust. Importantly, this approach is designed for a distributed realization, possibly using distributed ledger technology, and does not depend on the use or storage of biometric properties. For the solution to be complete, additional components are needed, notably a mechanism that encourages honest behavior and a sybil-resilient governance system.
-
(2019) Nucleic Acids Research. 47, 5, p. 2436-2445 Abstract
Short tandem repeats (STRs) are polymorphic genomic loci valuable for various applications such as research, diagnostics and forensics. However, their polymorphic nature also introduces noise duringin vitroamplification, making them difficult to analyze. Although it is possible to overcome stutter noise by using amplification-free library preparation, such protocols are presently incompatible with single cell analysis and with targeted-enrichment protocols. To address this challenge, we have designed a method for direct measurement of in vitro noise. Using a synthetic STR sequencing library, we have calibrated a Markov model for the prediction of stutter patterns at any amplification cycle. By employing this model, we have managed to genotype accurately cases of severe amplification bias, and biallelic STR signals, and validated our model for several high-fidelity PCR enzymes. Finally, we compared this model in the context of a naive STR genotyping strategy against the state-of-the-art on a benchmark of single cells, demonstrating superior accuracy.
-
(2019) Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019. Kraus S.(eds.). p. 572-579 Abstract
Sybil attacks, in which fake or duplicate identities (sybils) infiltrate an online community, pose a serious threat to such communities, as they might tilt community-wide decisions in their favor. While the extensive research on sybil identification may help keep the fraction of sybils in such communities low, it cannot however ensure their complete eradication. Thus, our goal is to enhance social choice theory with effective group decision mechanisms for communities with bounded sybil penetration. Inspired by Reality-Aware Social Choice [Shapiro and Talmon, 2018], we use the status quo as the anchor of sybil resilience, characterized by sybil safety - the inability of sybils to change the status quo against the will of the genuine agents, and sybil liveness - the ability of the genuine agents to change the status quo against the will of the sybils. We consider the social choice settings of deciding on a single proposal, on multiple proposals, and on updating a parameter. For each, we present social choice rules that are sybil-safe and, under certain conditions, satisfy sybil-liveness.