اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAdaptive Concurrent Non-Malleability with Bare Public-Keys
71
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Concurrent non-malleability (CNM) is central for cryptographic protocols running concurrently in environments such as the Internet. In this work, we formulate CNM in the bare public-key (BPK) model, and show that round-efficient concurrent non-malleable cryptography with full adaptive input selection can be established, in general, with bare public-keys (where, in particular, no trusted assumption is made). Along the way, we clarify the various subtleties of adaptive concurrent non-malleability in the bare public-key model.
قيم البحث
اقرأ أيضاً
Non-malleability is an important security property for public-key encryption (PKE). Its significance is due to the fundamental unachievability of integrity and authenticity guarantees in this setting, rendering it the strongest integrity-like propert
y achievable using only PKE, without digital signatures. In this work, we generalize this notion to the setting of quantum public-key encryption. Overcoming the notorious recording barrier known from generalizing other integrity-like security notions to quantum encryption, we generalize one of the equivalent classical definitions, comparison-based non-malleability, and show how it can be fulfilled. In addition, we explore one-time non-malleability notions for symmetric-key encryption from the literature by defining plaintext and ciphertext variants and by characterizing their relation.
Knowledge extraction is a fundamental notion, modelling machine possession of values (witnesses) in a computational complexity sense. The notion provides an essential tool for cryptographic protocol design and analysis, enabling one to argue about th
e internal state of protocol players without ever looking at this supposedly secret state. However, when transactions are concurrent (e.g., over the Internet) with players possessing public-keys (as is common in cryptography), assuring that entities ``know what they claim to know, where adversaries may be well coordinated across different transactions, turns out to be much more subtle and in need of re-examination. Here, we investigate how to formally treat knowledge possession by parties (with registered public-keys) interacting over the Internet. Stated more technically, we look into the relative power of the notion of ``concurrent knowledge-extraction (CKE) in the concurrent zero-knowledge (CZK) bare public-key (BPK) model.
In encryption, non-malleability is a highly desirable property: it ensures that adversaries cannot manipulate the plaintext by acting on the ciphertext. Ambainis, Bouda and Winter gave a definition of non-malleability for the encryption of quantum da
ta. In this work, we show that this definition is too weak, as it allows adversaries to inject plaintexts of their choice into the ciphertext. We give a new definition of quantum non-malleability which resolves this problem. Our definition is expressed in terms of entropic quantities, considers stronger adversaries, and does not assume secrecy. Rather, we prove that quantum non-malleability implies secrecy; this is in stark contrast to the classical setting, where the two properties are completely independent. For unitary schemes, our notion of non-malleability is equivalent to encryption with a two-design (and hence also to the definition of Ambainis et al.). Our techniques also yield new results regarding the closely-related task of quantum authentication. We show that total authentication (a notion recently proposed by Garg, Yuen and Zhandry) can be satisfied with two-designs, a significant improvement over the eight-design construction of Garg et al. We also show that, under a mild adaptation of the rejection procedure, both total authentication and our notion of non-malleability yield quantum authentication as defined by Dupuis, Nielsen and Salvail.
A relational bipartite communication problem is presented that has an efficient quantum simultaneous-messages protocol, but no efficient classical two-way protocol.
We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product
on a constant number of inputs. Let $IP$ denote Inner Product on $2b$ bits. 1) If $f$ is a total Boolean function that depends on all of its inputs, the bounded-error one-way quantum communication complexity of $f circ IP$ equals $Omega(n(b-1))$. 2) If $f$ is a partial Boolean function, the deterministic one-way communication complexity of $f circ IP$ is at least $Omega(b cdot D_{dt}^{rightarrow}(f))$, where $D_{dt}^{rightarrow}(f)$ denotes the non-adaptive decision tree complexity of $f$. For our quantum lower bound, we show a lower bound on the VC-dimension of $f circ IP$, and then appeal to a result of Klauck [STOC00]. Our deterministic lower bound relies on a combinatorial result due to Frankl and Tokushige [Comb.99]. It is known due to a result of Montanaro and Osborne [arXiv09] that the deterministic one-way communication complexity of $f circ XOR_2$ equals the non-adaptive parity decision tree complexity of $f$. In contrast, we show the following with the gadget $AND_2$. 1) There exists a function for which even the randomized non-adaptive AND decision tree complexity of $f$ is exponentially large in the deterministic one-way communication complexity of $f circ AND_2$. 2) For symmetric functions $f$, the non-adaptive AND decision tree complexity of $f$ is at most quadratic in the (even two-way) communication complexity of $f circ AND_2$. In view of the first point, a lower bound on non-adaptive AND decision tree complexity of $f$ does not lift to a lower bound on one-way communication complexity of $f circ AND_2$. The proof of the first point above uses the well-studied Odd-Max-Bit function.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
