Blockchain Papers

Follow blockchain research across journals, conferences, and preprint repositories.

75 papersLast indexed Aug 31, 2026
Search papers

Paper index

75 results · page 3 of 4

Clear filters
Jan 1, 2023·Journal of International Financial Markets Institutions and Money
22 cites
Contagion effects of permissionless, worthless cryptocurrency tokens: Evidence from the collapse of FTX

Thomas Conlon, Shaen Corbet, Yang Hou

This paper investigates the price discovery relationships between FTT Token, issued by the cryptocurrency exchange FTX, and a set of assets and liabilities held by FTX amid a period of catastrophic financial decline by applying novel information flow measurement techniques. Results indicate that during key phases associated with the collapse of FTX, FTT Token had an informational lead over multiple assets, including cryptocurrencies such as Ethereum. Furthermore, we identify significant interactions between the FTT Token and both Robinhood shares and the token Serum, raising concerns about the direct influence of permissionless, technically valueless tokens on other assets and the potential challenges to market stability and investor protection. Our findings underscore the need for stronger policy-making, regulatory, and ethical considerations in cryptocurrency markets.

Open access
2 source records
Blockchain Technology Applications and Security
Financial Markets and Investment Strategies
Market Dynamics and Volatility
Original source
Jan 1, 2023·SSRN Electronic Journal
2 cites
The Property Law of Crypto Tokens

Jakub Wyczik

This article addresses the lack of comprehensive studies on Web3 technologies, primarily due to lawyers' reluctance to explore technical intricacies. Understanding the underlying technological foundations is crucial to enhance the credibility of legal opinions. This article aims to illuminate these foundations, debunk myths, and concentrate on determining the legal status of crypto-assets in the context of property rights within the distributed economy. In addition, this article notes that the intangible nature of crypto-assets that derive value from distributed registries, and their resistance to deletion, makes crypto-assets more akin to the autonomy of intellectual property than physical media. The article presents illustrative examples from common law (United States, United Kingdom, New Zealand) and civil law (Germany, Austria, Poland) systems. Proposing a universal solution, it advocates a comprehensive framework safeguarding digital property - data ownership - extending beyond the confines of Web3. This article presents a comprehensive, multi-layered approach to the analysis of tokens as digital content and virtual goods. The approach, universally applicable to various of such goods, scrutinizes property on three distinct layers: first, the rights to the virtual good itself; second, the rights to the assets linked to the virtual good; and third, the rights to the intellectual property intricately associated with the token. Additionally, the paper provides concise analysis of the conflict of laws rules applicable to virtual goods. It also delves into issues concerning formal requirements for the transfer of intellectual property rights, licensing, the first sale (exhaustion) doctrine, the concept of the lawful acquirer, and other crucial aspects of intellectual property in the realm of virtual goods, particularly within the emerging metaverse.

Open access
3 source records
cs.CR
cs.CY
Chaos-based Image/Signal Encryption
Original source
Dec 31, 2022·International Journal of Engineering Technologies and Management Research
1 cites
APPLICATION OF BENFORD’S LAW ON TRADE VOLUME OF CRYPTOCURRENCIES

Ann Mary Alexander, Resia Beegam. S

Cryptocurrencies have become a global phenomenon and its trading volume has been increasing since 2017 Aloosh and Li (2019). However, cryptocurrencies have been accused of market manipulation in the past. Benford’s law is widely used for detecting probability of frauds and manipulation in various fields. This study applied Benford’s law on trade volume of cryptocurrencies. Chi- square statistics revealed that except for Cardano and USDT all the other cryptocurrencies did not conform to the distribution and reveals the dataset could have been manipulated. This method may be used as the pre-requisite before doing fine-grain screening such as machine learning and graph-based searching.

Open access
Benford’s Law and Fraud Detection
Digital Media Forensic Detection
Blockchain Technology Applications and Security
Original source
Sep 9, 2022·arXiv (Cornell University)
18 cites
On the Computational Hardness Needed for Quantum Cryptography

Zvika Brakerski, Ran Canetti, Luowen Qian

In the classical model of computation, it is well established that one-way functions (OWF) are minimal for computational cryptography: They are essential for almost any cryptographic application that cannot be realized with respect to computationally unbounded adversaries. In the quantum setting, however, OWFs appear not to be essential (Kretschmer 2021; Ananth et al., Morimae and Yamakawa 2022), and the question of whether such a minimal primitive exists remains open. We consider EFI pairs - efficiently samplable, statistically far but computationally indistinguishable pairs of (mixed) quantum states. Building on the work of Yan (2022), which shows equivalence between EFI pairs and statistical commitment schemes, we show that EFI pairs are necessary for a large class of quantum-cryptographic applications. Specifically, we construct EFI pairs from minimalistic versions of commitments schemes, oblivious transfer, and general secure multiparty computation, as well as from QCZK proofs from essentially any non-trivial language. We also construct quantum computational zero knowledge (QCZK) proofs for all of QIP from any EFI pair. This suggests that, for much of quantum cryptography, EFI pairs play a similar role to that played by OWFs in the classical setting: they are simple to describe, essential, and also serve as a linchpin for demonstrating equivalence between primitives.

Open access
Cryptography and Data Security
Benford’s Law and Fraud Detection
Computability, Logic, AI Algorithms
Original source
Jan 5, 2022·Crime Science
181 cites
Cryptocurrencies and future financial crime

Arianna Trozze, Josh Kamps, Eray Arda Akartuna, Florian Hetzel · 7 authors

BACKGROUND: Cryptocurrency fraud has become a growing global concern, with various governments reporting an increase in the frequency of and losses from cryptocurrency scams. Despite increasing fraudulent activity involving cryptocurrencies, research on the potential of cryptocurrencies for fraud has not been examined in a systematic study. This review examines the current state of knowledge about what kinds of cryptocurrency fraud currently exist, or are expected to exist in the future, and provides comprehensive definitions of the frauds identified. METHODS: The study involved a scoping review of academic research and grey literature on cryptocurrency fraud and a 1.5-day expert consensus exercise. The review followed the PRISMA-ScR protocol, with eligibility criteria based on language, publication type, relevance to cryptocurrency fraud, and evidence provided. Researchers screened 391 academic records, 106 of which went on to the eligibility phase, and 63 of which were ultimately analysed. We screened 394 grey literature sources, 128 of which passed on to the eligibility phase, and 53 of which were included in our review. The expert consensus exercise was attended by high-profile participants from the private sector, government, and academia. It involved problem planning and analysis activities and discussion about the future of cryptocurrency crime. RESULTS: The academic literature identified 29 different types of cryptocurrency fraud; the grey literature discussed 32 types, 14 of which were not identified in the academic literature (i.e., 47 unique types in total). Ponzi schemes and (synonymous) high yield investment programmes were most discussed across all literature. Participants in the expert consensus exercise ranked pump-and-dump schemes and ransomware as the most profitable and feasible threats, though pump-and-dumps were, notably, perceived as the least harmful type of fraud. CONCLUSIONS: The findings of this scoping review suggest cryptocurrency fraud research is rapidly developing in volume and breadth, though we remain at an early stage of thinking about future problems and scenarios involving cryptocurrencies. The findings of this work emphasise the need for better collaboration across sectors and consensus on definitions surrounding cryptocurrency fraud to address the problems identified.

Open access
Cybercrime and Law Enforcement Studies
Blockchain Technology Applications and Security
Benford’s Law and Fraud Detection
Original source
Jan 1, 2022·SSRN Electronic Journal
9 cites
Gambling on Crypto Tokens?

Sudheer Chava, Fred Hu, Nikhil Paradkar

Abstract We proxy retail investor attention through Google Trends and find that fungible and non-fungible crypto tokens generate greater attention from high-gambling propensity regions. Crypto attention is higher during bubble-like episodes in the crypto market and for more lottery-like tokens. Moreover, retail crypto attention decreases after sports gambling is legalized. Higher token attention is associated with more contributors and higher fundraising. However, consumer credit default rates spike after periods of high crypto attention, but solely in the subprime segment. Overall, our findings suggest that gambling preferences strongly predict retail investor interest in the crypto market.

Open access
2 source records
Gambling Behavior and Treatments
Art History and Market Analysis
Benford’s Law and Fraud Detection
Original source
Dec 8, 2021·Machine Learning with Applications
16 cites
Cryptocurrency ecosystems and social media environments: An empirical analysis through Hawkes’ models and natural language processing

Marco Ortu, Stefano Vacca, Giuseppe Destefanis, Claudio Conversano

We analyse, using a mixture of statistical models and natural language process techniques, what happened in social media from June 2019 onwards to understand the relationships between Cryptocurrencies’ prices and social media, focusing on the rise of the Bitcoin and Ethereum prices. In particular, we identify and model the relationship between the cryptocurrencies market price changes, and sentiment and topic discussion occurrences on social media, using Hawkes’ Model. We find that some topics occurrences and rise of sentiment in social media precedes certain types of price movements. Specifically, discussions concerning governments, trading, and Ethereum cryptocurrency as an exchange currency appear to negatively affect Bitcoin and Ethereum prices. Those concerning investments, appear to explain price rises, whilst discussions related to new decentralized realities and technological applications explain price falls. Finally, we validate our model using a real case study: the already famous case of ”Wallstreetbet and GameStop”1 that took place in January 2021.

Open access
Blockchain Technology Applications and Security
Benford’s Law and Fraud Detection
Complex Systems and Time Series Analysis
Original source
Nov 25, 2021·Journal of theoretical and applied electronic commerce research
21 cites
Application of Benford’s Law on Cryptocurrencies

Jernej Vičič, Aleksandar Toơić

The manuscript presents a study of the possibility of use of Benford’s law conformity test, a well proven tool in the accounting fraud discovery, on a new domain: the discovery of anomalies (possibly fraudulent behaviour) in the the cryptocurrency transactions. Blockchain-based currencies or cryptocurrencies have become a global phenomenon known to most people as a disruptive technology, and a new investment vehicle. However, due to their decentralized nature, regulating these markets has presented regulators with difficulties in finding a balance between nurturing innovation, and protecting consumers. The growing concerns about illicit activity have forced regulators to seek new ways of detecting, analyzing, and ultimately policing public blockchain transactions. Extensive research on machine learning, and transaction graph analysis algorithms has been done to track suspicious behaviour. However, having a macro view of a public ledger is equally important before pursuing a more fine-grained analysis. Benford’s law, the law of first digit, has been extensively used as a tool to discover accountant frauds (many other use cases exist). The basic motivation that drove our research presented in this paper was to test the applicability of the well established method to a new domain, in this case the identification of anomalous behavior using Benford’s law conformity test to the cryptocurrency domain. The research focused on transaction values in all major cryptocurrencies. A suitable time-period was identified that was long enough to present sufficiently large number of observations for Benford’s law conformity tests and was also situated long enough in the past so that the anomalies were identified and well documented. The results show that most of the cryptocurrencies that did not conform to Benford’s law had well documented anomalous incidents, the first digits of aggregated transaction values of all well known cryptocurrency projects were conforming to Benford’s law. Thus the proposed method is applicable to the new domain.

Open access
2 source records
Benford’s Law and Fraud Detection
Digital Media Forensic Detection
Imbalanced Data Classification Techniques
Original source
Jun 28, 2021·Pressacademia
1 cites
The suspicion of manipulation in Bitcoin returns: an investigation with Benford s law

Ömer İskenderoğlu, Nazif Ayyıldız

Purpose-Bitcoin is a blockchain-based digital currency that can be generated via data mining. Several complex computational methods along with random processes have been utilized in the production of that currency. Nonetheless, it is an important research question whether this process, which have been taking place in a entirely digital platform, involves manipulation. Accordingly, the amount of Bitcoin in circulation would involve manipulation as much as the Bitcoin price and returns do. Methodology-Related tests are performed to detect compliance with Benford's Law in the analyses conducted on the issue. Distribution frequency of the digits can be determined by Benford's Law in order to determine whether the random digital database is manipulated. In order to detect any possible manipulation in Bitcoin returns, the Chi-Square test is performed Findings-With the daily Bitcoin price data obtained over the period between 02.02.2012 -10.02.2020 its found out that Btcoin prices comply with Benford's Law reference distribution. Conclusion-According to the results of the analysis, it is concluded that the Bitcoin returns comply with Benford's Law. Therefore, there is no possible manipulation on the Bitcoin returns throughout the study period.

Open access
Benford’s Law and Fraud Detection
Original source
May 3, 2021·2021 IEEE International Conference on Blockchain and Cryptocurrency (ICBC)
7 cites
Detecting Text Reuse in Cryptocurrency Whitepapers

Andrew Morin, Marie Vasek, Tyler Moore

Thousands of new cryptocurrencies have been introduced in recent years. Most are introduced with a so-called "whitepaper" containing a mix of technical documentation, legal boilerplate and marketing material. Notably, many proposed currencies reuse text from previous established cryptocurrencies. We analyze the whitepapers from 1 260 actively traded cryptocurrencies and 2 039 ICOs. We develop two measures of similarity. Moderately similar papers reuse text in a portion of the paper, often the legal disclaimers. By contrast, some highly similar whitepapers appear to copy most of the text. 4% of coin and 19% of ICO whitepapers are highly similar to those of traded coins. The fraction rises to 64% for coins and 67% for ICOs when we consider moderate text reuse.

Open access
Blockchain Technology Applications and Security
Spam and Phishing Detection
Benford’s Law and Fraud Detection
Original source
Jan 29, 2021·Psychology and Education Journal
1 cites
Computational Cost Reduction of Transaction Signing in Blockchain

Kiattikul Sooksomsatarn Et al.

Nowadays, Blockchain is a disruptive technology, particularly in the financial context. Moreover, Blockchain is behind the success of cryptocurrencies, e.g., Bitcoin and Ethereum. Unlike traditional currencies, cryptocurrencies are entirely virtual. There is no physical money, but it can directly make payments in digital currency from one person to another without intermediaries. Moreover, Hashing's cryptographic algorithm makes Blockchain resist tampering from any transacting participants because the submitted block cannot be altered or re-engineered. However, another big problem is how users of cryptocurrencies stop somebody from adding or editing a transaction that spends someone else's money to them. To do this, Blockchain needs another cryptosystem called Public/Private Keys, a primitive asymmetric cryptosystem, e.g., the RSA encryption, to sign the transactions for proving the authenticity of the ownership without revealing the signed secret information. The generated public key is regarded as a ledger account number or digital wallet of the sender and the recipient. Simultaneously, the paired private keys are used to identify whether the digital wallets' owners are authentic. As growing network entities and propagated Blockchain transactions, computing millions of replicated tokens in the blocks to sign and verify the digital wallet's ownership is computationally expensive. However, a certain of chosen arithmetical transformations that can simplify mathematical cost can significantly reduce computational complexity. This research's main contribution is developing a protocol that can reduce the complexity and mathematical cost in generating the digital wallet and verifying its authenticity of ownership. Finally, performance analyses of the RSA algorithm for the protocol have been measured and visualized using Python.

Open access
Blockchain Technology Applications and Security
Benford’s Law and Fraud Detection
Original source
Aug 26, 2020·Ushus - Journal of Business Management
1 cites
Solving the Mystery of Crypto’s Bubble

Harsh Sengar

Blockchain is the vehicle on which cryptocurrencies run, and it can’t be regulated by any legal entity during its operation.The huge growth in various cryptocurrency segments in 10 years has created the controversy of an inevitable bubble. A bubble can be generated either by queer herd behaviour or logical secular movement. Traces of evident bubbles have been a certainty and they take the perceived valuation of crypto to figures far away from its true value. This sudden diversion can be lethal due to the illogical, irrational propensity of regular market participants. This study observes ten cryptos under surveillance from September 2014 to August 2019. The selected ten (Monero, Bitcoin, XRP Ripple, Litecoin, Dogecoin, Monacoin, Ethereum, Bytecoin, Digibite, Potcoin) cryptocurrencies were studied for the last five years using Right Tailed ADF Test. Prominent traces of the rational bubble in all the underlying cryptocurrencies were found and have been considered for the study.

Open access
Blockchain Technology Applications and Security
Benford’s Law and Fraud Detection
Original source
Jan 1, 2020·Advances in Science Technology and Engineering Systems Journal
3 cites
Comparative Study of Cryptocurrency Algorithms: Coronavirus Towards Bitcoin’s Expansion

Fatma Mallouli, Aya Hellal, Fatimah Abdulraheem Alzahrani, Abdulsalam Almadani · 5 authors

The widespread presence of Corona virus (COVID-19) is causing organizations and individuals major economics downsizing.The way this virus is transmitted from one individual to another is the real cause of the problem.For that, researchers in different fields started seriously looking for touch-less and contact-less exchange.Particularly in the finance world, cash transactions and key pad based transactions are becoming obsolete because they are some of the major causes of the spread of this virus (and other viruses and bacteria).Cryptocurrency could be one of the solutions to the above mentioned situation.This novel money is based on Blockchain technology, which is based on cryptography algorithms for the safety and the security of the transactions.This paper exhibits a comparative study of the asymmetric cryptography algorithms.This helps the user to best choose the most secure, safe and reliable method to encrypt/decrypt the transactions created in the Blockchain.

Open access
Blockchain Technology Applications and Security
Advanced Steganography and Watermarking Techniques
Benford’s Law and Fraud Detection
Original source
Sep 1, 2019·2019 4th International Conference on Computer Science and Engineering (UBMK) (2019) 183-188
45 cites
Blockchain-Based Electronic Voting System for Elections in Turkey

Rumeysa Bulut, Alperen Kantarci, Safa Keskin, Serif Bahtiyar

Traditional elections satisfy neither citizens nor political authorities in recent years. They are not fully secure since it is easy to attack votes. It threatens also privacy and transparency of voters. Additionally, it takes too much time to count the votes. This paper proposes a solution using Blockchain to eliminate all the disadvantages of conventional elections. Security and data integrity of votes are absolutely provided theoretically. Voter privacy is another requirement that is ensured in the system. Lastly, the waiting time for results decreased significantly in the proposed Blockchain voting system.

Open access
2 source records
cs.CR
cs.CY
Internet Traffic Analysis and Secure E-voting
Original source
Feb 7, 2019·IntechOpen eBooks
0 cites
On the Origin of the Value of Cryptocurrencies

Er’el Granot

Bitcoin and other cryptocurrencies received a lot of criticism during the last 9 years. It is not surprising that this criticism came from organizations that are threatened by the crypto revolution (banks, government, central banks, finance companies, etc.). Nevertheless, it is very surprising to hear criticism from economics schools, which oppose central banking and advocate free choice in currencies (such as the Austrian school of economics). Unlike the ordinary criticism (that Bitcoin is a scam, a bubble, etc.), which can easily be refuted, the criticism of part of the Austrian school economists is based on interesting arguments, which requires a different level of explanation. For example, it was claimed that Bitcoin should be worthless; otherwise, it contradicts Mises’ regression theorem. The object of the chapter is twofold: first to explain why the criticism is unfounded and second to analyze the origin of the value of Bitcoin and other cryptocoins from the perspective of the Austrian school of economics. In particular, it is explained that Bitcoin does not contradict the regression theorem for two reasons. First, the initial value estimation can be a random event, and second, the Bitcoin network (even now) has a nonmonetary value.

Open access
Blockchain Technology Applications and Security
Benford’s Law and Fraud Detection
Original source
Jan 1, 2019·SSRN Electronic Journal
2 cites
Flexible Majority Rules for Cryptocurrency Issuance

Hans Gersbach

We suggest that flexible majority rules for currency issuance decisions foster the stability of a cryptocurrency. With flexible majority rules, the voteshare needed to approve a particular currency issuance growth is increasing with this growth rate. By choosing suitable parameters for these flexible majority rules, we show that optimal growth rates can be achieved in simple settings. Moreover, with flexible majority rules, changes in the composition of growth-friendly and growth-adverse agents only have a comparatively moderate impact on growth rates, and extreme growth rates are avoided. Finally, we show that optimal money growth rates are realized if agents entering financial contracts anticipate ensuing inflation rates determined by these flexible majority rules.

Open access
2 source records
Cryptography and Data Security
Blockchain Technology Applications and Security
Benford’s Law and Fraud Detection
Original source
Jun 29, 2018·Digital Access to Scholarship at Harvard (DASH) (Harvard University)
4 cites
Zero Knowledge Proofs and Applications to Financial Regulation

Nihal R. Gowravaram

We consider zero-knowledge proofs, a class of cryptographic protocols by which an agent (a Prover) can prove to another agent (a Verifier) that a statement is true without revealing any additional information. For example, a zero-knowledge proof allows one to prove knowledge of a password to somebody at the other end of the communication without actually revealing the password.
\nWe present an introduction to and survey literature on zero-knowledge proofs, covering the history, formal definition, and classical applications of zero-knowledge proofs. In addition, we consider connections to complexity, demonstrating that all problems in the complexity class NP have zero-knowledge proofs, and also discuss more exotic applications of zero-knowledge, namely in electronic voting and nuclear disarmament.
\nWe then consider applications of zero-knowledge to financial regulation, specifically in balancing transparency and confidentiality in financial reporting. Namely, we polled professionals in the financial industry to identify three major classes of regulatory problems. We then utilize zero-knowledge proofs to develop and present cryptographic protocols/mechanisms and solutions to these regulatory problems: (1) An employer verifying an employee has no financial holdings on a blacklist without revealing the other (allowed) holdings of the employee, (2) A fund convincing its investors that its holdings subscribe to particular risk constraints, without disclosing the actual holdings, (3) A collection of investors of a fund verifying aggregate information provided by the fund, while preserving pairwise anonymity. Applications (1) and (3) are novel applications developed in this paper, while (2) is drawn from [47].

Open access
Cryptography and Data Security
Benford’s Law and Fraud Detection
Auction Theory and Applications
Original source
Jan 1, 2017·BIBSYS Brage (BIBSYS (Norway))
5 cites
Comparative Analysis of Bitcoin and Ethereum

Marit Rudlang

Since Bitcoin was launched in 2009, several new cryptocurrencies have been initiated with variations to Bitcoin's original design. Although Bitcoin still remains the most prominent actor in the market, some technical problems have been raised to the design of the protocol. The objective of this thesis is to determine whether the newer cryptocurrencies handle the technical problems of Bitcoin, or if they also suffer from the same issues. Instead of evaluating several cryptocurrencies for this comparison, the cryptocurrency Ethereum has been chosen as a proxy for the others. Ethereum was started in 2014, is widely backed in the community and is second in line to Bitcoin when it comes to market capitalization. \n\nAs a basis for the comparative analysis a rigorous study of the Bitcoin and Ethereum protocols have been performed, and parallel descriptions of the systems have been devised. Three technical problem have shaped the focus of the analysis: computational waste, concentration of power and ambiguity of transactions. Real world statistical data has been gathered and synthesized to enlighten the findings in the comparison. The main result of the comparison is that both systems suffer from the same problems to a certain degree, due to the fact that they utilize the same consensus mechanism. However, Ethereum utilizes several newer techniques to try and reduce the severity of these problems compared to Bitcoin, with varying degrees of success.

Open access
Computability, Logic, AI Algorithms
Blockchain Technology Applications and Security
Benford’s Law and Fraud Detection
Original source
Jan 1, 2017·Metaphilosophy
43 cites
On the Philosophy of Bitcoin/Blockchain Technology: Is it a Chaotic, Complex System?

Renato P. dos Santos

Abstract The philosophy of blockchain technology is concerned, among other things, with blockchain ontology, how it might be characterised, how it is being created, implemented, and adopted, how it operates in the world, and how it evolves over time. This paper concentrates on whether Bitcoin/blockchain can be considered a complex system and, if so, whether it is a chaotic one. Beyond mere academic curiosity, a positive response would raise concerns about the likelihood of Bitcoin/blockchain entering a 2010‐Flash‐Crash‐type of chaotic regime, with catastrophic consequences for financial systems based on it. The paper starts by highlighting the relevant details of the Bitcoin/blockchain ecosystem formed by the blockchain itself, bitcoin end users (payers and payees), capital gains seekers, miners, full nodes maintainers, and developers, and their interactions. Then the Information Theory of Complex Systems is briefly discussed for later use. Finally, the blockchain is investigated with the help of Crutchfield's Statistical Complexity measure. The low non‐null statistical complexity value obtained suggests that the blockchain may be considered algorithmically complicated but hardly a complex system and unlikely to enter a chaotic regime.

Open access
3 source records
Complex Systems and Time Series Analysis
Benford’s Law and Fraud Detection
Complex Network Analysis Techniques
Original source
Sep 9, 2016·arXiv
0 cites
On the Power of Statistical Zero Knowledge

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

We examine the power of statistical zero knowledge proofs (captured by the complexity class SZK) and their variants. First, we give the strongest known relativized evidence that SZK contains hard problems, by exhibiting an oracle relative to which SZK (indeed, even NISZK) is not contained in the class UPP, containing those problems solvable by randomized algorithms with unbounded error. This answers an open question of Watrous from 2002 [Aar]. Second, we "lift" this oracle separation to the setting of communication complexity, thereby answering a question of Göös et al. (ICALP 2016). Third, we give relativized evidence that perfect zero knowledge proofs (captured by the class PZK) are weaker than general zero knowledge proofs. Specifically, we exhibit oracles relative to which SZK is not contained in PZK, NISZK is not contained in NIPZK, and PZK is not equal to coPZK. The first of these results answers a question raised in 1991 by Aiello and HÄstad (Information and Computation), and the second answers a question of Lovett and Zhang (2016). We also describe additional applications of these results outside of structural complexity. The technical core of our results 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.

Open access
2 source records
cs.CC
Complexity and Algorithms in Graphs
Benford’s Law and Fraud Detection
Original source