Abstract Decomposition puzzles are pencil-and-paper logic puzzles that involve partitioning a rectangular grid into several regions to satisfy certain rules. In this paper, we construct a generic card-based protocol called printing protocol , which can be used to physically verify solutions of decompositon puzzles. We apply the printing protocol to develop card-based zero-knowledge proof protocols for two such puzzles: Five Cells and Meadows. These protocols allow a prover to physically show that he/she knows solutions of the puzzles without revealing them.
Electronic voting is one of the most interesting application of modern cryptography, as it involves many innovative tools (such as homomorphic public-key encryption, non-interactive zero-knowledge proofs, and distributed cryptography) to guarantee several a priori contradictory security properties: the integrity of the tally and the privacy of the individual votes. While many efficient solutions exist for honest-but-curious voters, that follow the official procedure but try to learn more than just the public result, preventing attacks from malicious voters is much more complex: when voters may have incentive to send biased ballots, the privacy of the ballots is much harder to satisfy, whereas this is the crucial security property for electronic voting. We present a new technique to prove that an ElGamal ciphertext contains a message from a specific subset (quasi-adaptive NIZK of subset membership), using linearly-homomorphic signatures. The proofs are both quite efficient to generate, allowing the use of low-power devices to vote, and randomizable, which is important for the strong receipt-freeness property. They are well-suited to prevent vote-selling and replay attacks, which are the main threats against the privacy in electronic voting, with security proofs in the generic group model and the random oracle model.
We examine which decentralized finance architectures enable meaningful regulation by combining financial and computational theory. We show via deduction that a decentralized and permissionless Turing-complete system cannot provably comply with regulations concerning anti-money laundering, know-your-client obligations, some securities restrictions and forms of exchange control. Any system that claims to follow regulations must choose either a form of permission or a less-than-Turing-complete update facility. Compliant decentralized systems can be constructed only by compromising on the richness of permissible changes. Regulatory authorities must accept new tradeoffs that limit their enforcement powers if they want to approve permissionless platforms formally. Our analysis demonstrates that the fundamental constraints of computation theory have direct implications for financial regulation. By mapping regulatory requirements onto computational models, we characterize which types of automated compliance are achievable and which are provably impossible. This framework allows us to move beyond traditional debates about regulatory effectiveness to establish concrete boundaries for automated enforcement.
Ball sort puzzle is a popular logic puzzle consisting of several bins containing balls of multiple colors. Each bin works like a stack; a ball has to follow the last-in first-out order. The player has to sort the balls by color such that each bin contains only balls of a single color. In this paper, we propose a physical zero-knowledge proof protocol for the ball sort puzzle using a deck of playing cards, which enables a prover to physically show that he/she knows a solution with $t$ moves of the ball sort puzzle without revealing it. Our protocol is the first zero-knowledge proof protocol for an interactive puzzle involving moving objects.
People are getting familiar with cryptocurrencies because of the rapid development of cryptography, and bitcoin, a traditional decentralized digital currency, becomes famous. Thus, it is necessary to establish a digital currency allocation framework. Two existing methods both share the same goal of reaching blockchain consensus; however, the processes are different: The proof of Work system is completely related to tasks, but the Proof of Stake system is related to tokens. Hence, service providers are more than glad to apply the Proof of Work theory after distinguishing the difference between these two systems; this system which does not have high limitations is more fair and balanced. To enhance the traditional Proof of Work system, Artificial Intelligence can properly help and make the new framework works more efficiently. AI model can pre-assign a trustworthy score via the IP address, and then it can take the responsibility to generate the puzzle for the qualification. After the model verifies the output, the trustworthy score can increase or decrease based on the performance. Finally, it can establish a loop from the trustworthy score to puzzle difficulty, and then back to the trustworthy score. Therefore, an AI assistant can accurately monitor the entire transaction process and ensure validation to be environmentally friendly.
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.
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.
Robert Benkoczi, Daya Ram Gaur, Naya Nagy, Marius Nagy · 5 authors
This paper studies the effect of quantum computers on Bitcoin mining. The shift in computational paradigm towards quantum computation allows the entire search space of the golden nonce to be queried at once by exploiting quantum superpositions and entanglement. Using Groverâs algorithm, a solution can be extracted in time O(2256/t), where t is the target value for the nonce. This is better using a square root over the classical search algorithm that requires O(2256/t) tries. If sufficiently large quantum computers are available for the public, mining activity in the classical sense becomes obsolete, as quantum computers always win. Without considering quantum noise, the size of the quantum computer needs to be â104 qubits.
In this paper we describe protocols which use a standard deck of cards to provide a perfectly sound zero-knowledge proof for Hamiltonian cycles and Flow Free puzzles. The latter can easily be extended to provide a protocol for a zero-knowledge proof of many-to-many k-disjoint path coverings.
Liquidity is a liveness property of programs managing resources that pinpoints those programs not freezing any resource forever. We consider a simple stateful language whose resources are assets (digital currencies, non fungible tokens, etc.). Then we define a type system that tracks in a symbolic way the input-output behaviour of functions with respect to assets. These types and their composition, which define types of computations, allow us to design two algorithms for liquidity that have different precisions and costs. We also demonstrate the correctness of the algorithms.
The conventional wisdom is that you must reveal something about how you pick stocks in order to prove that you have stock-picking skill. In this paper I show that, prior to executing any trades, it is possible to prove you have stock-picking skill without revealing any additional information about your underlying trading signal. Here is how the protocol works. The evaluator presents you with a sequence of paired return data sets, one real and the other suitably randomized. A profitable trading signal will only be able to predict the cross-section of returns in the real data set. So by repeatedly using your trading signal to identify the real data set, you can prove that you have stock-picking skill without revealing anything else about your underlying signal. This protocol represents a zero-knowledge proof of stock-picking skillâi.e., a proof which reveals nothing except for the validity of your claim. Zero-knowledge proofs allow any skilled stock picker to advertise his ability without fear of his trading signal getting scooped. As a result, they have important implications for how the active-management industry is organized.
Peg solitaire is a very popular traditional single-player board game, known to be NP-complete. In this paper, we present a zero-knowledge proof of knowledge for solutions of peg solitaire instances. Our proof is straightforward, in the sense that it does not use any reduction to another NP-complete problem, and uses the standard design of sigma protocols. Our construction relies on cryptographic commitments, which can be replaced by envelopes to make the protocol physical. As a side contribution, we introduce the notion of isomorphisms for peg solitaire, which is the key tool of our protocol.
We propose a new doubly efficient interactive proof protocol for general arithmetic circuits. The protocol generalizes the interactive proof for layered circuits proposed by Goldwasser, Kalai and Rothblum to arbitrary circuits, while preserving the optimal prover complexity that is strictly linear to the size of the circuits. The proof size remains succinct for low depth circuits and the verifier time is sublinear for structured circuits. We then construct a new zero knowledge argument scheme for general arithmetic circuits using our new interactive proof protocol together with polynomial commitments. Our key technique is a new sumcheck equation that reduces a claim about the output of one layer to claims about its input only, instead of claims about all the layers above which inevitably incurs an overhead proportional to the depth of the circuit. We developed efficient algorithms for the prover to run this sumcheck protocol and to combine multiple claims back into one in linear time in the size of the circuit. Not only does our new protocol achieve optimal prover complexity asymptotically, but it is also efficient in practice. Our experiments show that it only takes 0.3 seconds to generate the proof for a circuit with more than 600,000 gates, which is 13 times faster than the original interactive proof protocol on the corresponding layered circuit. The proof size is 208 kilobytes and the verifier time is 66 milliseconds. Our implementation can take general arithmetic circuits directly, without transforming them to layered circuits with a high overhead on the size of the circuit.
The incorporation of robots in the social fabric of our society has taken giant leaps, enabled by advances in artificial intelligence and big data. As these robots become increasingly adept at parsing through enormous datasets and making decisions where humans fall short, a significant challenge lies in the analysis of robot behavior. Capturing interactions between robots, humans and IoT devices in traditional structures such as graphs poses challenges in the storage and analysis of large data sets in dense graphs generated by frequent activities. This paper proposes a framework that uses the blockchain for the storage of robotic interactions, and the use of sheaf theory for analysis of these interactions. Applications of our framework for social robots and swarm robots incorporating imperfect information and irrationality on the blockchain sheaf are proposed. This work shows the application of such a framework for various blockchain applications on the spectrum of human-robot interaction, and identifies key challenges that arise as a result of using the blockchain for robotic applications.
Verifiable delay functions have found a lot of applications in blockchain technology in recent times. Continuous verifiable delay functions are an improvement over the basic notion of VDFs with recursive capabilities. We are proposing the application of VDF for constructing more space time-efficient provers and simulators required for the iterative non-interactive zero-knowledge systems.
The article discusses the V.V. Tselishchevâs original and unique systematic study of the specific and extremely complicated problems of Gödel results regarding the question of artificial intelligence essence. Tselishchev argues that the reflexive property should be considered not only as an advantage of human reasoning, but also as an objective internal limitation that appears in case of adding Gödel sentence to a theory to build a new theory. The article analyzes so-called mentalistic Gödelâs argument for fundamental superiority of human intelligence over machine one and the non-algorithmic nature of natural thinking. The discussion about the Gödel argument is not entirely speculative, but contains new knowledge. An example of such knowledge are the results of R. Smullyan levels of computers âawareness,â which are may be interpreted in a psychophysical sense. The concept of âzero level of intelligenceâ is proposed for such a reflexive property as âawareness of selfconsciousness.â Reflexive ranks below the awareness of self-consciousness can be considered negative levels of thinking in the sense that the intelligence, being reduced to them, significantly loses its completeness. Even self-consciousness turns out to be a negative level of thinking, since, according to Smullyan, the subject of self-consciousness is unaware of the type of thought to which he belongs. A thought experiment is proposed that allows us to establish the distribution of the properties of Smullyan stability and normality and to answer the question âDoes an intuitive belief in the truth of a formal proof affect the truth of a proposition being proved?â According to intuitionism, the most unpleasant epistemic property is instability: beliefs that are not based on deep intuitions have no value. According to the constructivist philosophy of mathematics, instability is a less negative property than abnormality: the fact that high-ranking beliefs cannot be immersed to the very foundations is not significant because violation of truth due to lowering the rank of reflection is not critical.
In this paper, we introduce a new approach to fix the validation of a block and the assignment of a new block in a blockchain infrastructure by using a novel negotiation procedure. The block validation and assignment are reached thanks to negotiation procedures based on an extended probability environment. Also, by using a multiscale approach (typical of Complexity Theory) and Quantum and Relativistic Mechanics, the result appears to solve some of the most relevant questions in the Blockchain context, which are the democracy and the randomness of the validator of a block and the assignment of the new one. The selection of actors to mine is invariant concerning the number of addresses, i.e., the coins of owners, which have more chance to be selected generally. This work is the companion of CQKD (Computational Quantum Key Distribution), as we will see in the introduction, where we considered the infrastructural question of the key distribution; also, it is a very effective application of the decision and reasoning in incompleteness or uncertainty conditions as described in the previous and prodromic paper as described in the introduction too.
Linear Legendre pseudorandom functions were introduced in 1988 by Damgrd, and higher degree generalisations were introduced by Russell and Shparlinski in 2004. We present new key recovery methods that improve the state of the art for both cases. For degree r 3 we give an attack that runs in time O( p r -3 ) after O( p 3 ) precomputation for the most relevant high degree case; it is based on the action of the group of Mbius transformations on degree r polynomials. For r < 3 we give an O( p r/2 ) attack with O( p r/4 ) oracle queries. In the linear case we recovered the keys for the 64, 74 and 84-bit prime Ethereum challenges, being the first to solve the 84-bit case.
This paper proposes a protocol for lottery and a protocol for auction on quantum Blockchain. Our protocol of lottery satisfies randomness, unpredictability, unforgeability, verifiability, decentralization and unconditional security. Our protocol of auction satisfies bid privacy, posterior privacy, bids' binding, decentralization and unconditional security. Except quantum Blockchain, the main technique involved in both protocols is quantum bit commitment.
This article integrates existing theory from distributed computing and cryptology with anecdotal material from the cryptocurrency industry, to provide a comprehensive description of the minimum requirements of the hypothetical academic blockchain. The paper argues that such a community could significantly reduce the biases and misconduct that now exist in the academic peer review process. Theory suggests such a system could operate effectively as a distributed encrypted telecommunications network where nodes are anonymous, do not trust each other, and there is minimal central authority. To incentivize the academic community to join such a proposed community, the paper proposes a pseudo-cryptocurrency called litcoin (literature coin). This litcoin-based system would create economic scarcity based on proof of knowledge (POK), which is a synthesis of the proof of work (POW) mechanism used in bitcoin, and the proof of stake (POS) mechanism used in various altcoin communities. The paper argues that the proposed POK system would enable the academic community to more effectively develop the research it finds valuable.