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.
Many attempts of having a secure digital currency failed in the past until the introduction of Bitcoin. Bitcoin&s;s solution to this problem also introduced a new technology called blockchain, which is a tamper-proof distributed ledger. Security of cryptocurrencies and blockchains depend on cryptographic algorithms. This chapter is dedicated to the cryptographic foundations of blockchain technology. Moreover, the security of the cryptographic algorithms that are used in blockchains are investigated with an emphasis on lightweight cryptography suitable for constrained IoT devices and Bitcoin, since it is the pioneer of this disruptive technology.
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.
Blockchain-based cryptocurrencies offer an appealing alternative to Fiat currencies, due to their decentralized and borderless nature. However the decentralized settings make the authentication process more challenging: Standard cryptographic methods often rely on the ability of users to reliably store a (large) secret information. What happens if one user's key is lost or stolen? Blockchain systems lack of fallback mechanisms that allow one to recover from such an event, whereas the traditional banking system has developed and deploys quite effective solutions. In this work, we develop new cryptographic techniques to integrate security policies (developed in the traditional banking domain) in the blockchain settings. We propose a system where a smart contract is given the custody of the user's funds and has the ability to invoke a two-factor authentication (2FA) procedure in case of an exceptional event (e.g., a particularly large transaction or a key recovery request). To enable this, the owner of the account secret-shares the answers of some security questions among a committee of users. When the 2FA mechanism is triggered, the committee members can provide the smart contract with enough information to check whether an attempt was successful, and nothing more. We then design a protocol that securely and efficiently implements such a functionality: The protocol is round-optimal, is robust to the corruption of a subset of committee members, supports low-entropy secrets, and is concretely efficient. As a stepping stone towards the design of this protocol, we introduce a new threshold homomorphic encryption scheme for linear predicates from bilinear maps, which might be of independent interest. To substantiate the practicality of our approach, we implement the above protocol as a smart contract in Ethereum and show that it can be used today as an additional safeguard for suspicious transactions, at minimal added cost. We also implement a second scheme where the smart contract additionally requests a signature from a physical hardware token, whose verification key is registered upfront by the owner of the funds. We show how to integrate the widely used universal two-factor authentication (U2F) tokens in blockchain environments, thus enabling the deployment of our system with available hardware.
Know Your Customer (KYC) is a costly and heavily regulated process that financial institutions are legally required to undertake to conduct business with their customers. Distributed Ledger Technology (DLT) can be used as a coordination mechanism for financial institutions to share KYC costs in a common jurisdiction. Previous techniques that use DLT to support the KYC process, perhaps unexpectedly, introduce a single point of failure in the system. Indeed, financial institutions are vulnerable to repercussions if a single institution makes an operational mistake during the onboarding stage. We tackle this problem by introducing a probabilistic mechanism, where some of the financial institutions involved need to independently repeat the KYC process in the form of a randomised audit. This novel approach mitigates the single point of failure of the previous DLT-based KYC designs and introduces a natural trade-off between the security of the KYC process and its cost efficiency. In our approach the audit probability can be either set as a global DLT parameter or be dependent on attributes associated with the particular client.
Mathematics, Computing, and Information Processing
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.
Random algorithms have a unique place in complexity theory as a model of computation that ispotentially more powerful than “normal” algorithms, and is also practical. However, it is still notclear how much more power randomness adds. The primary goal in studying random algorithmsis derandomization – some method to simulate random algorithms without actually using random-ness. While full derandomization is quite difficult, we show some weak derandomization results –one using advice, and one using multi-pseudodeterminism. We show that improving these resultswould have major implications. Finally, we show new containments and oracle separations betweentraditional random classes and zero-knowledge proofs.
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.