BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Or Sattath

Or Sattath appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
quant-phCryptography and SecurityComputational ComplexityComputer Science and Game Theorycond-mat.stat-mechcond-mat.str-elInformation Theorymath.COmath.IT

Catalog footprint

What is connected

12works
9topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

12 published item(s)

preprint2022arXiv

Quantum Amnesia Leaves Cryptographic Mementos: A Note On Quantum Skepticism

Leonard Shelby, the protagonist of Memento, uses mementos in the form of tattoos and pictures to handle his amnesia. Similar to Leonard, contemporary quantum computers suffer from "quantum amnesia": the inability to store quantum registers for a long duration. Quantum computers can only retain classical "mementos" of quantum registers by measuring them before those vanish. Some quantum skeptics argue that this quantum amnesia is inherent. We point out that this variant of a skeptic world is roughly described by the quantum bounded storage model, and although it is a computational obstacle that annuls potential quantum computational advantage, the seemingly undesired properties provide a cryptographic advantage. Namely, providing exotic primitives promised by the quantum bounded storage model, such as unconditionally secure commitment and oblivious transfer schemes, with constructions involving nothing but transmission and measurement of BB84 states.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Redesigning Bitcoin's fee market

The Bitcoin payment system involves two agent types: Users that transact with the currency and pay fees and miners in charge of authorizing transactions and securing the system in return for these fees. Two of Bitcoin's challenges are (i) securing sufficient miner revenues as block rewards decrease, and (ii) alleviating the throughput limitation due to a small maximal block size cap. These issues are strongly related as increasing the maximal block size may decrease revenue due to Bitcoin's pay-your-bid approach. To decouple them, we analyze the "monopolistic auction", showing: (i) its revenue does not decrease as the maximal block size increases, (ii) it is resilient to an untrusted auctioneer (the miner), and (iii) simplicity for transaction issuers (bidders), as the average gain from strategic bid shading (relative to bidding one's value) diminishes as the number of bids increases.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings

Valiant-Vazirani showed in 1985 [VV85] that solving NP with the promise that "yes" instances have only one witness is powerful enough to solve the entire NP class (under randomized reductions). We are interested in extending this result to the quantum setting. We prove extensions to the classes Merlin-Arthur MA and Quantum-Classical-Merlin-Arthur QCMA. Our results have implications for the complexity of approximating the ground state energy of a quantum local Hamiltonian with a unique ground state and an inverse polynomial spectral gap. We show that the estimation (to within polynomial accuracy) of the ground state energy of poly-gapped 1-D local Hamiltonians is QCMA-hard [AN02], under randomized reductions. This is in stark contrast to the case of constant gapped 1-D Hamiltonians, which is in NP [Has07]. Moreover, it shows that unless QCMA can be reduced to NP by randomized reductions, there is no classical description of the ground state of every poly-gapped local Hamiltonian that allows efficient calculation of expectation values. Finally, we discuss a few of the obstacles to the establishment of an analogous result to the class Quantum-Merlin-Arthur (QMA). In particular, we show that random projections fail to provide a polynomial gap between two witnesses.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Uncloneable Decryptors from Quantum Copy-Protection

Uncloneable decryptors are encryption schemes (with classical plaintexts and ciphertexts) with the added functionality of deriving uncloneable quantum states, called decryptors, which could be used to decrypt ciphers without knowledge of the secret key (Georgiou and Zhandry, IACR'20). We study uncloneable decryptors in the computational setting and provide increasingly strong security notions which extend the various indistinguishable security notions of symmetric encryption. We show that CPA secure uncloneable bit decryptors could be instantiated from a copy protection scheme (Aaronson, CCC'09) for any balanced binary function. We introduce a new notion of flip detection security for copy protection schemes inspired by the notions of left or right security for encryption schemes, and show that it could be used to instantiate CPA secure uncloneable decryptors for messages of unrestricted length. We then show how to strengthen the CPA security of uncloneable decryptors to CCA2 security using strong EUF-CMA secure digital signatures. We show that our constructions could be instantiated relative to either the quantum oracle used in [Aar09] or the classical oracle used in (Aaronson et al., CRYPTO'21) to instantiate copy protection schemes. Our constructions are the first to achieve CPA or CCA2 security in the symmetric setting.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Quantum Money Solution to the Blockchain Scalability Problem

We put forward the idea that classical blockchains and smart contracts are potentially useful primitives not only for classical cryptography, but for quantum cryptography as well. Abstractly, a smart contract is a functionality that allows parties to deposit funds, and release them upon fulfillment of algorithmically checkable conditions, and can thus be employed as a formal tool to enforce monetary incentives. In this work, we give the first example of the use of smart contracts in a quantum setting. We describe a simple hybrid classical-quantum payment system whose main ingredients are a classical blockchain capable of handling stateful smart contracts, and quantum lightning, a strengthening of public-key quantum money introduced by Zhandry (Eurocrypt'19). Our hybrid payment system employs quantum states as banknotes and a classical blockchain to settle disputes and to keep track of the valid serial numbers. It has several desirable properties: it is decentralized, requiring no trust in any single entity; payments are as quick as quantum communication, regardless of the total number of users; when a quantum banknote is damaged or lost, the rightful owner can recover the lost value.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

On Quantum Advantage in Information Theoretic Single-Server PIR

In (single-server) Private Information Retrieval (PIR), a server holds a large database $DB$ of size $n$, and a client holds an index $i \in [n]$ and wishes to retrieve $DB[i]$ without revealing $i$ to the server. It is well known that information theoretic privacy even against an `honest but curious' server requires $Ω(n)$ communication complexity. This is true even if quantum communication is allowed and is due to the ability of such an adversarial server to execute the protocol on a superposition of databases instead of on a specific database (`input purification attack'). Nevertheless, there have been some proposals of protocols that achieve sub-linear communication and appear to provide some notion of privacy. Most notably, a protocol due to Le Gall (ToC 2012) with communication complexity $O(\sqrt{n})$, and a protocol by Kerenidis et al. (QIC 2016) with communication complexity $O(\log(n))$, and $O(n)$ shared entanglement. We show that, in a sense, input purification is the only potent adversarial strategy, and protocols such as the two protocols above are secure in a restricted variant of the quantum honest but curious (a.k.a specious) model. More explicitly, we propose a restricted privacy notion called \emph{anchored privacy}, where the adversary is forced to execute on a classical database (i.e. the execution is anchored to a classical database). We show that for measurement-free protocols, anchored security against honest adversarial servers implies anchored privacy even against specious adversaries. Finally, we prove that even with (unlimited) pre-shared entanglement it is impossible to achieve security in the standard specious model with sub-linear communication, thus further substantiating the necessity of our relaxation. This lower bound may be of independent interest (in particular recalling that PIR is a special case of Fully Homomorphic Encryption).

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

On the insecurity of quantum Bitcoin mining

Grover's algorithm confers on quantum computers a quadratic advantage over classical computers for searching in an arbitrary data set, a scenario that describes Bitcoin mining. It has previously been argued that the only side-effect of quantum mining would be an increased difficulty. In this work, we argue that a crucial argument in the analysis of Bitcoin security breaks down when quantum mining is performed. Classically, a Bitcoin fork occurs rarely, i.e., when two miners find a block almost simultaneously, due to propagation time effects. The situation differs dramatically when quantum miners use Grover's algorithm, which repeatedly applies a procedure called a Grover iteration. The chances of finding a block grow quadratically with the number of Grover iterations applied. Crucially, a miner does not have to choose how many iterations to apply in advance. Suppose Alice receives Bob's new block. To maximize her revenue, she should stop and measure her state immediately in the hopes that her block (rather than Bob's) will become part of the longest chain. The strong correlation between the miners' actions and the fact that they all measure their states at the same time may lead to more forks -- which is known to be a security risk for Bitcoin. We propose a mechanism that, we conjecture, will prevent this form of quantum mining, thereby circumventing the high rate of forks.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Quantum Max-flow/Min-cut

The classical max-flow min-cut theorem describes transport through certain idealized classical networks. We consider the quantum analog for tensor networks. By associating an integral capacity to each edge and a tensor to each vertex in a flow network, we can also interpret it as a tensor network, and more specifically, as a linear map from the input space to the output space. The quantum max flow is defined to be the maximal rank of this linear map over all choices of tensors. The quantum min cut is defined to be the minimum product of the capacities of edges over all cuts of the tensor network. We show that unlike the classical case, the quantum max-flow=min-cut conjecture is not true in general. Under certain conditions, e.g., when the capacity on each edge is some power of a fixed integer, the quantum max-flow is proved to equal the quantum min-cut. However, concrete examples are also provided where the equality does not hold. We also found connections of quantum max-flow/min-cut with entropy of entanglement and the quantum satisfiability problem. We speculate that the phenomena revealed may be of interest both in spin systems in condensed matter and in quantum gravity.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

When a local Hamiltonian must be frustration-free

A broad range of quantum optimisation problems can be phrased as the question whether a specific system has a ground state at zero energy, i.e.\ whether its Hamiltonian is frustration free. Frustration-free Hamiltonians, in turn, play a central role for constructing and understanding new phases of matter in quantum many-body physics. Unfortunately, determining whether this is the case is known to be a complexity-theoretically intractable problem. This makes it highly desirable to search for efficient heuristics and algorithms in order to, at least, partially answer this question. Here we prove a general criterion - a sufficient condition - under which a local Hamiltonian is guaranteed to be frustration free by lifting Shearer's theorem from classical probability theory to the quantum world. Remarkably, evaluating this condition proceeds via a fully classical analysis of a hard-core lattice gas at negative fugacity on the Hamiltonian's interaction graph which, as a statistical mechanics problem, is of interest in its own right. We concretely apply this criterion to local Hamiltonians on various regular lattices, while bringing to bear the tools of spin glass physics which permit us to obtain new bounds on the SAT/UNSAT transition in random quantum satisfiability. These also lead us to natural conjectures for when such bounds will be tight, as well as to a novel notion of universality for these computer science problems. Besides providing concrete algorithms leading to detailed and quantitative insights, this underscores the power of marrying classical statistical mechanics with quantum computation and complexity theory.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

An Almost Sudden Jump in Quantum Complexity

The Quantum Satisfiability problem (QSAT) is the generalization of the canonical NP-complete problem - Boolean Satisfiability. (k,s)-QSAT is the following variant of the problem: given a set of projectors of rank 1, acting non-trivially on k qubits out of n qubits, such that each qubit appears in at most s projectors, decide whether there exists a quantum state in the null space of all the projectors. Let f*(k) be the maximal integer s such that every (k,s)-QSAT instance is satisfiable. Deciding (k,f*(k))-QSAT is computationally easy: by definition the answer is "satisfiable". But, by relaxing the conditions slightly, we show that (k,f*(k)+2)-QSAT is QMA_1-hard, for k >=15. This is a quantum analogue of a classical result by Kratochvíl et al. [KST93]. We use the term "an almost sudden jump" to stress that the complexity of (k,f*(k)+1)-QSAT is open, where the jump in the classical complexity is known to be sudden. We present an implication of this finding to the quantum PCP conjecture, arguably one of the most important open problems in the field of Hamiltonian complexity. Our implications impose constraints on one possible way to refute the quantum PCP.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the power of a unique quantum witness

In a celebrated paper, Valiant and Vazirani raised the question of whether the difficulty of NP-complete problems was due to the wide variation of the number of witnesses of their instances. They gave a strong negative answer by showing that distinguishing between instances having zero or one witnesses is as hard as recognizing NP, under randomized reductions. We consider the same question in the quantum setting and investigate the possibility of reducing quantum witnesses in the context of the complexity class QMA, the quantum analogue of NP. The natural way to quantify the number of quantum witnesses is the dimension of the witness subspace W in some appropriate Hilbert space H. We present an efficient deterministic procedure that reduces any problem where the dimension d of W is bounded by a polynomial to a problem with a unique quantum witness. The main idea of our reduction is to consider the Alternating subspace of the d-th tensor power of H. Indeed, the intersection of this subspace with the d-th tensor power of W is one-dimensional, and therefore can play the role of the unique quantum witness.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

A Quantum Lovasz Local Lemma

The Lovasz Local Lemma (LLL) is a powerful tool in probability theory to show the existence of combinatorial objects meeting a prescribed collection of "weakly dependent" criteria. We show that the LLL extends to a much more general geometric setting, where events are replaced with subspaces and probability is replaced with relative dimension, which allows to lower bound the dimension of the intersection of vector spaces under certain independence conditions. Our result immediately applies to the k-QSAT problem: For instance we show that any collection of rank 1 projectors with the property that each qubit appears in at most $2^k/(e \cdot k)$ of them, has a joint satisfiable state. We then apply our results to the recently studied model of random k-QSAT. Recent works have shown that the satisfiable region extends up to a density of 1 in the large k limit, where the density is the ratio of projectors to qubits. Using a hybrid approach building on work by Laumann et al. we greatly extend the known satisfiable region for random k-QSAT to a density of $Ω(2^k/k^2)$. Since our tool allows us to show the existence of joint satisfying states without the need to construct them, we are able to penetrate into regions where the satisfying states are conjectured to be entangled, avoiding the need to construct them, which has limited previous approaches to product states.

0 citations0 reviewsNo code linkedOpen access