اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOptimal bounds for semi-honest quantum oblivious transfer
357
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Oblivious transfer is a fundamental cryptographic primitive in which Bob transfers one of two bits to Alice in such a way that Bob cannot know which of the two bits Alice has learned. We present an optimal security bound for quantum oblivious transfer protocols under a natural and demanding definition of what it means for Alice to cheat. Our lower bound is a smooth tradeoff between the probability B with which Bob can guess Alices bit choice and the probability A with which Alice can guess both of Bobs bits given that she learns one of the bits with certainty. We prove that 2B + A is greater than or equal to 2 in any quantum protocol for oblivious transfer, from which it follows that one of the two parties must be able to cheat with probability at least 2/3. We prove that this bound is optimal by exhibiting a family of protocols whose cheating probabilities can be made arbitrarily close to any point on the tradeoff curve.
قيم البحث
اقرأ أيضاً
Random access coding is an information task that has been extensively studied and found many applications in quantum information. In this scenario, Alice receives an $n$-bit string $x$, and wishes to encode $x$ into a quantum state $rho_x$, such that
Bob, when receiving the state $rho_x$, can choose any bit $i in [n]$ and recover the input bit $x_i$ with high probability. Here we study two variants: parity-oblivious random access codes, where we impose the cryptographic property that Bob cannot infer any information about the parity of any subset of bits of the input apart from the single bits $x_i$; and even-parity-oblivious random access codes, where Bob cannot infer any information about the parity of any even-size subset of bits of the input. In this paper, we provide the optimal bounds for parity-oblivious quantum random access codes and show that they are asymptotically better than the optimal classical ones. Our results provide a large non-contextuality inequality violation and resolve the main open problem in a work of Spekkens, Buzacott, Keehn, Toner, and Pryde (2009). Second, we provide the optimal bounds for even-parity-oblivious random access codes by proving their equivalence to a non-local game and by providing tight bounds for the success probability of the non-local game via semidefinite programming. In the case of even-parity-oblivious random access codes, the cryptographic property holds also in the device-independent model.
Due to the commonly known impossibility results, unconditional security for oblivious transfer is seen as impossible even in the quantum world. In this paper, we try to overcome these impossibility results by proposing a protocol which is asymptotica
lly secure. The protocol makes use of the basic properties of non-orthogonal quantum states. Apart from security, the advantages of our protocol include the fact that the honest players do not need to have quantum memory or create entanglement between individual qubits. The relation of our work to the known impossibility results is also discussed.
Due to the commonly known impossibility results, information theoretic security is considered impossible for oblivious transfer (OT) in both the classical and the quantum world. In this paper, we proposed a weak version of the all-or-nothing OT. In o
ur protocol the honest parties do not need long term quantum memory, entanglements, or sophisticated quantum computations. We observe some difference between the classical and quantum OT impossibilities.
Oblivious transfer, a central functionality in modern cryptography, allows a party to send two one-bit messages to another who can choose one of them to read, remaining ignorant about the other, whereas the sender does not learn the receivers choice.
Oblivious transfer the security of which is information-theoretic for both parties is known impossible to achieve from scratch. - The joint behavior of certain bi-partite quantum states is non-local, i.e., cannot be explained by shared classical information. In order to better understand such behavior, which is classically explainable only by communication, but does not allow for it, Popescu and Rohrlich have described a non-locality machine: Two parties both input a bit, and both get a random output bit the XOR of which is the AND of the input bits. - We show a close connection, in a cryptographic sense, between OT and the PR primitive. More specifically, unconditional OT can be achieved from a single realization of PR, and vice versa. Our reductions, which are single-copy, information-theoretic, and perfect, also lead to a simple and optimal protocol allowing for inverting the direction of OT.
We prove an $Omega(d lg n/ (lglg n)^2)$ lower bound on the dynamic cell-probe complexity of statistically $mathit{oblivious}$ approximate-near-neighbor search ($mathsf{ANN}$) over the $d$-dimensional Hamming cube. For the natural setting of $d = Thet
a(log n)$, our result implies an $tilde{Omega}(lg^2 n)$ lower bound, which is a quadratic improvement over the highest (non-oblivious) cell-probe lower bound for $mathsf{ANN}$. This is the first super-logarithmic $mathit{unconditional}$ lower bound for $mathsf{ANN}$ against general (non black-box) data structures. We also show that any oblivious $mathit{static}$ data structure for decomposable search problems (like $mathsf{ANN}$) can be obliviously dynamized with $O(log n)$ overhead in update and query time, strengthening a classic result of Bentley and Saxe (Algorithmica, 1980).
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
