Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSecurity Improvements of Several Basic Quantum Private Query Protocols with O(log N) Communication Complexity
156
0
0.0
(
0
)
Added by
Fang Yu Dr.
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
New quantum private database (with N elements) query protocols are presented and analyzed. Protocols preserve O(logN) communication complexity of known protocols for the same task, but achieve several significant improvements in security, especially concerning user privacy. For example, the randomized form of our protocol has a cheat-sensitive property - it allows the user to detect a dishonest database with a nonzero probability, while the phase-encoded private query protocols for the same task do not have such a property. Moreover, when the database performs the computational basis measurement, a particular projective measurement which can cause a significant loss of user privacy in the previous private query protocols with O(logN) communication complexity, at most half of the user privacy could leak to such a database in our protocol, while in the QPQ protocol, the entire user privacy could leak out. In addition, it is proved here that for large N, the user could detect a cheating via the computational basis measurement, with a probability close to 1/2 using O(sqrt{N}) special queries. Finally, it is shown here, for both forms of our protocol, basic and randomized, how a dishonest database has to act in case it could not learn users queries.
rate research
Read More
Key-agreement protocols whose security is proven in the random oracle model are an important alternative to protocols based on public-key cryptography. In the random oracle model, the parties and the eavesdropper have access to a shared random function (an oracle), but the parties are limited in the number of queries they can make to the oracle. The random oracle serves as an abstraction for black-box access to a symmetric cryptographic primitive, such as a collision resistant hash. Unfortunately, as shown by Impagliazzo and Rudich [STOC 89] and Barak and Mahmoody [Crypto 09], such protocols can only guarantee limited secrecy: the key of any $ell$-query protocol can be revealed by an $O(ell^2)$-query adversary. This quadratic gap between the query complexity of the honest parties and the eavesdropper matches the gap obtained by the Merkles Puzzles protocol of Merkle [CACM 78]. In this work we tackle a new aspect of key-agreement protocols in the random oracle model: their communication complexity. In Merkles Puzzles, to obtain secrecy against an eavesdropper that makes roughly $ell^2$ queries, the honest parties need to exchange $Omega(ell)$ bits. We show that for protocols with certain natural properties, ones that Merkles Puzzle has, such high communication is unavoidable. Specifically, this is the case if the honest parties queries are uniformly random, or alternatively if the protocol uses non-adaptive queries and has only two rounds. Our proof for the first setting uses a novel reduction from the set-disjointness problem in two-party communication complexity. For the second setting we prove the lower bound directly, using information-theoretic arguments.
We propose a method for engineering security protocols that are aware of timing aspects. We study a simplified version of the well-known Needham Schroeder protocol and the complete Yahalom protocol, where timing information allows the study of different attack scenarios. We model check the protocols using UPPAAL. Further, a taxonomy is obtained by studying and categorising protocols from the well known Clark Jacob library and the Security Protocol Open Repository (SPORE) library. Finally, we present some new challenges and threats that arise when considering time in the analysis, by providing a novel protocol that uses time challenges and exposing a timing attack over an implementation of an existing security protocol.
Knowledge flow analysis offers a simple and flexible way to find flaws in security protocols. A protocol is described by a collection of rules constraining the propagation of knowledge amongst principals. Because this characterization corresponds closely to informal descriptions of protocols, it allows a succinct and natural formalization; because it abstracts away message ordering, and handles communications between principals and applications of cryptographic primitives uniformly, it is readily represented in a standard logic. A generic framework in the Alloy modelling language is presented, and instantiated for two standard protocols, and a new key management scheme.
The Nakamoto longest chain protocol is remarkably simple and has been proven to provide security against any adversary with less than 50% of the total hashing power. Proof-of-stake (PoS) protocols are an energy efficient alternative; however existing protocols adopting Nakamotos longest chain design achieve provable security only by allowing long-term predictability (which have serious security implications). In this paper, we prove that a natural longest chain PoS protocol with similar predictability as Nakamotos PoW protocol can achieve security against any adversary with less than 1/(1+e) fraction of the total stake. Moreover we propose a new family of longest chain PoS protocols that achieve security against a 50% adversary, while only requiring short-term predictability. Our proofs present a new approach to analyzing the formal security of blockchains, based on a notion of adversary-proof convergence.
Modern web applications often rely on third-party services to provide their functionality to users. The secure integration of these services is a non-trivial task, as shown by the large number of attacks against Single Sign On and Cashier-as-a-Service protocols. In this paper we present Bulwark, a new automatic tool which generates formally verified security monitors from applied pi-calculus specifications of web protocols. The security monitors generated by Bulwark offer holistic protection, since they can be readily deployed both at the client side and at the server side, thus ensuring full visibility of the attack surface against web protocols. We evaluate the effectiveness of Bulwark by testing it against a pool of vulnerable web applications that use the OAuth 2.0 protocol or integrate the PayPal payment system.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
