Blockchain Papers

Zhedong Wang, Qiqi Lai, Feng-Hao Liu

No abstract is available for this record.

Vincenzo Botta, Michele Ciampi, Emmanuela Orsini, Luisa Siniscalchi · 5 authors

No abstract is available for this record.

Sri Kanth Mandru

Conventionally, organizations have used Privileged Access Management (PAM) techniques to secure, control, and monitor access to their critical information and resources. The PAM concepts have envisioned designing protocols that help protect user accounts that are deemed to have access to sensitive data ?the most valuable asset of a business. While in the past these techniques have proven vital to data protection and security, the onset of increasingly sophisticated technologies and more determined malicious actors warrants a change of data control and privacy strategies. It becomes impossible to secure a system to achieve 100 percent efficiency. Any system that is attached to the internet is vulnerable to cyberattacks. Hackers have numerous ways to compromise systems if traditional boundary security mechanisms are deployed. Detecting an intrusion in such a setup becomes increasingly challenging if an attacker successfully breaches that boundary layer of defense. Since traditional authentication and authorization might not be reliable in network systems, the zero - knowledge proof model comes in handy. Adding the zero - knowledge proof to the PAM to authenticate users or members and disclose or anonymize them through decentralized identifiers helps in solving the identification and privacy protection problem. We propose a PAM and zero - knowledge proof - inspired approach to address the authentication, data security, and privacy concerns. A zero - knowledge proof is a method that allows the prover to prove to the verifier that they know a certain information without disclosing it.

Varbinka Stefanova-Stoyanova, Ivan Stankov, Bogdan Danov

The need to send secure messages without having to disclose additional information beyond the content; checking data integrity without having visibility into the data itself; Providing the integrity of various systems through validation that does not require the disclosure of sensitive data leads to the discovery of the potential of Zero Knowledge Proof (ZKP) and the technique of Smart Questioning (SQ) to verify the authenticity of the given statement, which involves asking specific questions.

Hiroyuki Kido

Standard probabilistic models face fundamental challenges such as data scarcity, a large hypothesis space, and poor data transparency. To address these challenges, we propose a novel probabilistic model of data-driven temporal propositional reasoning. Unlike conventional probabilistic models where data is a product of domain knowledge encoded in the probabilistic model, we explore the reverse direction where domain knowledge is a product of data encoded in the probabilistic model. This more data-driven perspective suggests no distinction between maximum likelihood parameter learning and temporal propositional reasoning. We show that our probabilistic model is equivalent to a highest-order, i.e., full-memory, Markov chain, and it can also be viewed as a hidden Markov model requiring no distinction between hidden and observable variables. We discuss that limits provide a natural and mathematically rigorous way to handle data scarcity, including the zero-frequency problem. We also discuss that a probability distribution over data generated by our probabilistic model helps data transparency by revealing influential data used in predictions. The reproducibility of this theoretical work is fully demonstrated by the included proofs.

Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan

We prove that for every 3-player (3-prover) game $\mathcal G$ with value less than one, whose query distribution has the support $\mathcal S = \{(1,0,0), (0,1,0), (0,0,1)\}$ of hamming weight one vectors, the value of the $n$-fold parallel repetition $\mathcal G^{\otimes n}$ decays polynomially fast to zero; that is, there is a constant $c = c(\mathcal G)>0$ such that the value of the game $\mathcal G^{\otimes n}$ is at most $n^{-c}$. Following the recent work of Girish, Holmgren, Mittal, Raz and Zhan (STOC 2022), our result is the missing piece that implies a similar bound for a much more general class of multiplayer games: For $\textbf{every}$ 3-player game $\mathcal G$ over $\textit{binary questions}$ and $\textit{arbitrary answer lengths}$, with value less than 1, there is a constant $c = c(\mathcal G)>0$ such that the value of the game $\mathcal G^{\otimes n}$ is at most $n^{-c}$. Our proof technique is new and requires many new ideas. For example, we make use of the Level-$k$ inequalities from Boolean Fourier Analysis, which, to the best of our knowledge, have not been explored in this context prior to our work.

César Sabater, Jan Ramon

In privacy-preserving machine learning, it is less obvious to verify correct behavior of participants because they are not supposed to reveal their inputs in cleartext to other participants. It is hence important to make federated machine learning robust against data poisoning and related attacks. While input data can be related to a distributed ledger (blockchain), a less studied input is formed by the random sampling parties perform. In this paper, we describe strategies based on zero knowledge proofs to allow parties to prove they perform sampling (and other computations) correctly. We sketch a number of alternative ways to implement our idea and provide some preliminary experimental results.

Arnab Bhattacharyya, Sutanu Gayen, Saravanan Kandasamy, Vedant Raval · 5 authors

We consider the problem of efficiently inferring interventional distributions in a causal Bayesian network from a finite number of observations. Let $\mathcal{P}$ be a causal model on a set $\mathbf{V}$ of observable variables on a given causal graph $G$. For sets $\mathbf{X},\mathbf{Y}\subseteq \mathbf{V}$, and setting ${\bf x}$ to $\mathbf{X}$, let $P_{\bf x}(\mathbf{Y})$ denote the interventional distribution on $\mathbf{Y}$ with respect to an intervention ${\bf x}$ to variables ${\bf x}$. Shpitser and Pearl (AAAI 2006), building on the work of Tian and Pearl (AAAI 2001), gave an exact characterization of the class of causal graphs for which the interventional distribution $P_{\bf x}({\mathbf{Y}})$ can be uniquely determined. We give the first efficient version of the Shpitser-Pearl algorithm. In particular, under natural assumptions, we give a polynomial-time algorithm that on input a causal graph $G$ on observable variables $\mathbf{V}$, a setting ${\bf x}$ of a set $\mathbf{X} \subseteq \mathbf{V}$ of bounded size, outputs succinct descriptions of both an evaluator and a generator for a distribution $\hat{P}$ that is $\varepsilon$-close (in total variation distance) to $P_{\bf x}({\mathbf{Y}})$ where $Y=\mathbf{V}\setminus \mathbf{X}$, if $P_{\bf x}(\mathbf{Y})$ is identifiable. We also show that when $\mathbf{Y}$ is an arbitrary set, there is no efficient algorithm that outputs an evaluator of a distribution that is $\varepsilon$-close to $P_{\bf x}({\mathbf{Y}})$ unless all problems that have statistical zero-knowledge proofs, including the Graph Isomorphism problem, have efficient randomized algorithms.

Thomas Attema, Ronald Cramer, Serge Fehr

No abstract is available for this record.

Joana Lorenz, Maria Inês Silva, David Aparício, João Tiago Ascensão · 5 authors

Every year, criminals launder billions of dollars acquired from serious felonies (e.g., terrorism, drug smuggling, or human trafficking), harming countless people and economies. Cryptocurrencies, in particular, have developed as a haven for money laundering activity. Machine Learning can be used to detect these illicit patterns. However, labels are so scarce that traditional supervised algorithms are inapplicable. Here, we address money laundering detection assuming minimal access to labels. First, we show that existing state-of-the-art solutions using unsupervised anomaly detection methods are inadequate to detect the illicit patterns in a real Bitcoin transaction dataset. Then, we show that our proposed active learning solution is capable of matching the performance of a fully supervised baseline by using just 5% of the labels. This solution mimics a typical real-life situation in which a limited number of labels can be acquired through manual annotation by experts.

Yi Deng

No abstract is available for this record.

Ahmed E. Kosba, Dimitrios Papadopoulos, Charalampos Papamanthou, Dawn Song

The last few years have witnessed increasing interest in the deployment of zero-knowledge proof systems, in particular ones with succinct proofs and efficient verification (zk-SNARKs). One of the main challenges facing the wide deployment of zk-SNARKs is the requirement of a trusted key generation phase per different computation to achieve practical proving performance. Existing zero-knowledge proof systems that do not require trusted setup or have a single trusted preprocessing phase suffer from increased proof size and/or additional verification overhead. On the other other hand, although universal circuit generators for zk-SNARKs (that can eliminate the need for per-computation preprocessing) have been introduced in the literature, the performance of the prover remains far from practical for real-world applications. In this paper, we first present a new zk-SNARK system that is well-suited for randomized algorithms-in particular it does not encode randomness generation within the arithmetic circuit allowing for more practical prover times. Then, we design a universal circuit that takes as input any arithmetic circuit of a bounded number of operations as well as a possible value assignment, and performs randomized checks to verify consistency. Our universal circuit is linear in the number of operations instead of quasi-linear like other universal circuits. By applying our new zk-SNARK system to our universal circuit, we build MIRAGE, a universal zk-SNARK with very succinct proofs-the proof contains just one additional element compared to the per-circuit preprocessing state-of-the-art zk-SNARK by Groth (Eurocrypt 2016). Finally, we implement MIRAGE and experimentally evaluate its performance for different circuits and in the context of privacy-preserving smart contracts. © 2020 by The USENIX Association. All Rights Reserved.

Carsten Baum, Alex J. Malozemoff, Marc B. Rosen, Peter Schöll

No abstract is available for this record.

Shalev Ben-David, Robin Kothari

We define a new query measure we call quantum distinguishing complexity, denoted QD(f) for a Boolean function f. Unlike a quantum query algorithm, which must output a state close to |0> on a 0-input and a state close to |1> on a 1-input, a "quantum distinguishing algorithm" can output any state, as long as the output states for any 0-input and 1-input are distinguishable. 
\nUsing this measure, we establish a new relationship in query complexity: For all total functions f, Q_0(f)=O~(Q(f)^5), where Q_0(f) and Q(f) denote the zero-error and bounded-error quantum query complexity of f respectively, improving on the previously known sixth power relationship.
\nWe also define a query measure based on quantum statistical zero-knowledge proofs, QSZK(f), which is at most Q(f). We show that QD(f) in fact lower bounds QSZK(f) and not just Q(f). QD(f) also upper bounds the (positive-weights) adversary bound, which yields the following relationships for all f: Q(f) >= QSZK(f) >= QD(f) = Omega(Adv(f)). This sheds some light on why the adversary bound proves suboptimal bounds for problems like Collision and Set Equality, which have low QSZK complexity.
\nLastly, we show implications for lifting theorems in communication complexity. We show that a general lifting theorem for either zero-error quantum query complexity or for QSZK would imply a general lifting theorem for bounded-error quantum query complexity.

Chris Peikert, Sina Shiehian

No abstract is available for this record.

Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, Daniel Wichs

No abstract is available for this record.

Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler · 5 authors

In both query and communication complexity, we give separations between the class NISZK, containing those problems with non-interactive statistical zero knowledge proof systems, and the class UPP, containing those problems with randomized algorithms with unbounded error. These results significantly improve on earlier query separations of Vereschagin [Ver95] and Aaronson [Aar12] and earlier communication complexity separations of Klauck [Kla11] and Razborov and Sherstov [RS10]. In addition, our results imply an oracle relative to which the class NISZK is not contained in PP. This answers an open question of Watrous from 2002 [Aar]. The technical core of our result is a stronger hardness amplification theorem for approximate degree, which roughly says that composing the gapped-majority function with any function of high approximate degree yields a function with high threshold degree. Using our techniques, we also give oracles relative to which the following two separations hold: perfect zero knowledge (PZK) is not contained in its complement (coPZK), and SZK (indeed, even NISZK) is not contained in PZK (indeed, even HVPZK). Along the way, we show that HVPZK is contained in PP in a relativizing manner. We prove a number of implications of these results, which may be of independent interest outside of structural complexity. Specifically, our oracle separation implies that certain parameters of the Polarization Lemma of Sahai and Vadhan [SV03] cannot be much improved in a black-box manner. Additionally, it implies new lower bounds for property testing algorithms with error probability arbitrarily close to 1/2. Finally, our results imply that two-message protocols in the streaming interactive proofs model of Cormode et al. [CTY11] are surprisingly powerful in the sense that, with just logarithmic cost, they can compute functions outside of UPP^CC.

Rohit Chadha, A. Prasad Sistla, Mahesh Viswanathan, Yue Ben

No abstract is available for this record.

Peggy Eastman

FigureWASHINGTON, DC—The ambitious continuous learning database project of the American Society of Clinical Oncology known as CancerLinQ (OT, 8/25/12) has demonstrated its feasibility for the first time, according to speakers at a news briefing at the National Press Club here. The new prototype, demonstrated for briefing attendees on a hypothetical post-surgical patient with hormone-responsive breast cancer, included anonymous data from 100,000 breast cancer patients treated at U.S. cancer care sites. CancerLinQ is not the only cancer continuous learning database—Georgetown University has pioneered a similar project (see box). The prototype CancerLinQ, which makes available to oncologists via computer massive amounts of data to inform clinical decision-making and improve the quality of cancer care, has now demonstrated through a real-time testing process that it can work in actual practice, said ASCO President Sandra M. Swain, MD, Medical Director of the Washington Cancer Institute at MedStar Washington Hospital Center. Swain noted that the majority of oncologists, about 60 percent, are currently using electronic health records (EHRs), a necessity for CancerLinQ. Swain explained that when ASCO embarked on this multi-stage project about a year and a half ago—which she described as “very bold” and “scary”—it was with the continuous learning vision of the Institute of Medicine (IOM) in mind. “Our work is really grounded in the work of the IOM over the last few years,” she said.Figure: ASCO President-Elect CIFFORD HUDIS, MD, noted that one key benefit of the new prototype is that it can accept data from different electronic health records: “The system is independent of the EHR that the physician is using. We will work with anyone; we hope all vendors will end up with transformable data.”The vision, as set forth in a number of IOM reports, seeks to help clinicians both learn from and contribute to diagnostic and treatment data through a health information technology (HIT) computerized database containing electronic health records (EHRs). Now, she said, “the physicians are just clamoring to give us the data,” because they realize its importance in making informed clinical decisions. She said use of the large data set should help to counter the fragmentation in cancer care that makes it very difficult to draw insights from the collective clinical experience with cancer patients. “It means having the whole medical community available for an opinion. It confirms that every cancer patient can be an information donor.” The database makes available a vast amount of valuable patient data that cannot now be mined because it is hidden away—since only about three percent of adult cancer patients participate in clinical trials. “The worst situation is not having information,” Swain continued. “Every time I see a patient, there are one or two things that make that patient different. This helps us to get more answers.” She said it isn't just oncology that will benefit, but that the data gathered will likely be relevant to other diseases as well. ‘Proof-of-Principle Prototype’ “This is a proof-of-principle prototype,” said ASCO President-Elect Clifford A. Hudis, MD, Chief of the Breast Cancer Medicine Service and Attending Physician at Memorial Sloan-Kettering Cancer Center and Professor of Medicine at Weill Medical College. “It's a real-time, push-of-the-button load of the patient data upfront.” Hudis said much work on the prototype remains, and that over the next year “we're going to write white papers on what we've learned.” He noted that right now ASCO's Quality Oncology Practice Initiative (QOPI), is paper-based—an initiative that could become much more streamlined and efficient if CancerLinQ is eventually widely adopted. One key benefit of the new prototype is that it can accept data from different EHRs, he said. “The system is independent of the EHR that the physician is using. We will work with anyone; we hope all vendors will end up with transformable data.”Figure: ASCO President SANDRA M. SWAIN, MD, said use of the large data set should help to counter the fragmentation in cancer care that makes it very difficult to draw insights from the collective clinical experience with cancer patients.In the hypothetical breast cancer case demonstrated, the patient is put on an aromatase inhibitor but develops arthralgia. The CancerLinQ database prototype tells her physician to consider using tamoxifen as an alternative, and provides supporting data for that treatment choice. “For 25 years I've been doing one-on-one medicine,” said another speaker, W. Charles Penley, MD, a partner with Tennessee Oncology, PLLC, Board Chair of the Conquer Cancer Foundation, and a member of the Dean's Advisory Board of the College of Arts and Sciences at the University of Tennessee. “Patients have been telling me, ‘Doctor, I want you to learn from my case to help other patients.’ This [CancerLinQ] is that taken to the modern information age.” Penley, who is one of about 25 clinicians in the network testing the ASCO database prototype and whose practice contributed breast cancer patient data to it, added, “This tool really can be a game changer in that regard.” What it means for cancer patients, he said, is that they can have confidence that they are receiving the highest quality care no matter where they are located. The database prototype, which he called “a remarkable step forward,” offers “an opportunity to query not just a few experts known to us, but the collective experience of treating clinicians—thus adding “second opinions times multiples.” Lessons from Pediatric Oncology Lynn M. Etheredge, who leads the Rapid Learning Project at George Washington University, said lessons from pediatric oncology can be valuable for CancerLinQ as it moves forward. Pediatric oncologists built a system to capture data from every patient as if he or she were on a clinical trial and then learn from that experience, noted Etheredge, who worked for the White House Office of Management and Budget in the Carter and Reagan Administrations, and who proposed the concept of the “rapid learning health system” in a special issue of Health Affairs in 2007 (26: w107-w118). “Pediatric oncologists realized early on that there were genetic differences,” he said. “Hopefully we will have the same success in treating adult patients.” Asked by OT if he could have envisioned his concept of a rapid learning health system coming to this database prototype point, Etheredge said, “I'm an optimist,” but noted that “This is astonishing.” He said that in the past physician groups have largely been reactive—responding to “things done to them,” and he praised ASCO for being proactive, innovative, and forward-thinking. “What we are saying now is that we have put the stake in the ground; we have demonstrated everything we wanted to demonstrate,” Joshua Mann, ASCO's Associate Director for Oncology Technology Solutions, Quality and Guidelines, said in an interview. “Now we're ready to engage the broader audience.” For the full CancerLinQ system, “we plan to siphon off data feeds from anyone,” including small oncology practices, not just large cancer centers. The message is: “Send us whatever you have however you can.” He noted that “machine-learning algorithms” convert data into a standardized format, thus allowing practices using different EHRs to participate in the continuous learning database. Lombardi's G-DOC Integrates New Knowledge with Practice At Georgetown University's Lombardi Comprehensive Cancer Center, Director Louis M. Weiner, MD, has pioneered a continuous learning system similar to CancerLinQ called Georgetown Database of Cancer, known as G-DOC. This system uses both local data and publicly available data sets to put the concept of personalized medicine into practice, Weiner explained. Commenting on ASCO's CancerLinQ prototype proof-of-principle, Weiner—a member of the Board of Scientific Advisors of the National Cancer Institute—said, “CancerLinQ is very ambitious. Currently, cancer specialists have access to only limited data to help them make critical life-altering decisions for their patients. In particular, it is very difficult to knowledgeably personalize therapies based upon a person's particular circumstances that are dictated by their genetics, comorbidities, and molecular properties of the cancers that afflict them. G-DOC has been designed as a first step towards that goal.”FigureWeiner noted that while there are patient confidentiality issues that need to be overcome in drawing on large databases to make treatment decisions, the concept is sound. It is clear that “it would be logical and desirable to link multiple datasets and then to create physician- and patient-friendly user interfaces that allow for shared decision-making that is based on a nuanced understanding of who to treat, what to use, and when to use it.”

Xiang Xie, Rui Xue, Minqian Wang

No abstract is available for this record.

Andrew Drucker

Given an instance of a hard decision problem, a limited goal is to compress that instance into a smaller, equivalent instance of a second problem. As one example, consider the problem where, given Boolean formulas $\psi^1, \ldots, \psi^t$, we must determine if at least one $\psi^j$ is satisfiable. An $\mathrm{OR}$-compression scheme for SAT is a polynomial-time reduction $R$ that maps $(\psi^1, \ldots, \psi^t)$ to a string $z$, such that $z$ lies in some “target” language $L'$ if and only if $\bigvee_j [\psi^j \in \mathrm{SAT}]$ holds. (Here, $L'$ can be arbitrarily complex.) AND-compression schemes are defined similarly. A compression scheme is strong if $|z|$ is polynomially bounded in $n = \max_j |\psi^j|$, independent of $t$. Strong compression for SAT seems unlikely. Work of Harnik and Naor [SIAM J. Comput., 39 (2010), pp. 1667--1713] and Bodlaender, Downey, Fellows, and Hermelin [J. Comput. System Sci., 75 (2009), pp. 423--434] showed that the infeasibility of strong OR-compression for SAT would show limits to instance compression for a large number of natural problems. Bodlaender et al. also showed that the infeasibility of strong AND-compression for SAT would have consequences for a different list of problems. Motivated by this, Fortnow and Santhanam [J. Comput. System Sci., 77 (2011), pp. 91--106] showed that if SAT is strongly OR-compressible, then $\mathsf{NP} \subseteq \mathsf{coNP/poly}$. Finding similar evidence against AND-compression was left as an open question. We provide such evidence: we show that strong AND- or OR-compression for SAT would imply nonuniform, statistical zero-knowledge proofs for SAT---an even stronger and more unlikely consequence than $\mathsf{NP} \subseteq \mathsf{coNP/poly}$. Our method applies against probabilistic compression schemes of sufficient “quality” with respect to the reliability and compression amount (allowing for tradeoff). This greatly strengthens the evidence given by Fortnow and Santhanam against probabilistic OR-compression for SAT. We also give variants of these results for the analogous task of quantum instance compression, in which a polynomial-time quantum reduction must output a quantum state that, in an appropriate sense, “preserves the answer” to the input instance. The central idea in our proofs is to exploit the information bottleneck in an AND-compression scheme for a language $L$ in order to fool a cheating prover in a proof system for $\overline{L}$. Our key technical tool is a new method to “disguise” information being fed into a compressive mapping; we believe this method may find other applications.

Abhishek Jain, Stephan Krenn, Krzysztof Pietrzak, Aris Tentes

No abstract is available for this record.

Mohammad Mahmoody, David Xiao

A Zero-Knowledge PCP (ZK-PCP) is a randomized PCP such that the view of any (perhaps cheating) efficient verifier can be efficiently simulated up to small statistical distance. Kilian, Petrank, and Tardos (STOC '97) constructed ZK-PCPs for all languages in NEXP. Ishai, Mahmoody, and Sahai (TCC '12), motivated by cryptographic applications, revisited the possibility of efficient ZK-PCPs for all of NP where the PCP is encoded as a polynomial-size circuit that given a query i returns the ith symbol of the PCP. Ishai et al showed that there is no efficient ZK-PCP for NP with a non-adaptive verifier, that prepares all of its PCP queries before seeing any answers, unless NP⊆coAM and the polynomial-time hierarchy collapses. The question of whether adaptive verification can lead to efficient ZK-PCPs for NP remained open. In this work, we resolve this question and show that any language or promise problem with efficient ZK-PCPs must be in SZK (the class of promise problems with a statistical zero-knowledge single prover proof system). Therefore, no NP-complete problem can have an efficient ZK-PCP unless NP⊆SZK (which also implies NP⊆coAM and the polynomial-time hierarchy collapses). We prove our result by reducing any promise problem with an efficient ZK-PCP to two instances of the Conditional Entropy Approximation problem defined and studied by Vadhan (FOCS'04) which is known to be complete for the class SZK.

Mohammad Mahmoody, David Xiao

We prove new results regarding the complexity of various complexity classes under randomized oracle reductions. We first prove that BPPPSZK⊆ AM ∩ coAM, where PSZK is the class of promise problems having statistical zero knowledge proofs. This strengthens the previously known facts that PSZK is closed under NC1truth-table reductions (Sahai and Vadhan, J. ACM '03) and that PPSZK⊆ AM ∩ coAM (Vadhan, personal communication). Our proof relies on showing that a certain class of real-valued functions that we call ℝ-TUAM can be approximated using an AM protocol. Then we investigate the power of randomized oracle reductions with relation to the notion of instance checking (Blum and Kannan, J. ACM '95). We observe that a theorem of Beigel implies that if any problem in TFNP such as Nash equilibrium is NP-hard under randomized oracle reductions, then SAT is checkable. We also observe that Beigel's theorem can be extended to an average-case setting by relating checking to the notion of program testing (Blum et al., JCSS '93). From this, we derive that if one-way functions can be based on NP-hardness via a randomized oracle reduction, then SAT is checkable. By showing that NP has a non-uniform tester, we also show that worst-case to average-case randomized oracle reduction for any relation (or language) R E NP implies that R has a nonuniform instance checker. These results hold even for adaptive randomized oracle reductions.