Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Communication Complexity of Key-Agreement Protocols
88
0
0.0
(
0
)
Added by
Noam Mazor
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We introduce a new approach for cryptanalysis of key agreement protocols based on noncommutative groups. This approach uses functions that estimate the distance of a group element to a given subgroup. We test it against the Shpilrain-Ushakov protocol, which is based on Thompsons group F.
As Byzantine Agreement (BA) protocols find application in large-scale decentralized cryptocurrencies, an increasingly important problem is to design BA protocols with improved communication complexity. A few existing works have shown how to achieve subquadratic BA under an {it adaptive} adversary. Intriguingly, they all make a common relaxation about the adaptivity of the attacker, that is, if an honest node sends a message and then gets corrupted in some round, the adversary {it cannot erase the message that was already sent} --- henceforth we say that such an adversary cannot perform after-the-fact removal. By contrast, many (super-)quadratic BA protocols in the literature can tolerate after-the-fact removal. In this paper, we first prove that disallowing after-the-fact removal is necessary for achieving subquadratic-communication BA. Next, we show new subquadratic binary BA constructions (of course, assuming no after-the-fact removal) that achieves near-optimal resilience and expected constant rounds under standard cryptographic assumptions and a public-key infrastructure (PKI) in both synchronous and partially synchronous settings. In comparison, all known subquadratic protocols make additional strong assumptions such as random oracles or the ability of honest nodes to erase secrets from memory, and even with these strong assumptions, no prior work can achieve the above properties. Lastly, we show that some setup assumption is necessary for achieving subquadratic multicast-based BA.
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.
Wireless Body Sensor Network (WBSN) is a developing technology with constraints in energy consumption, coverage radius, communication reliability. Also, communications between nodes contain very sensitive personal information in which sometimes due to the presence of hostile environments, there are a wide range of security risks. As such, designing authenticated key agreement (AKA) protocols is an important challenge in these networks. Recently, Li et al. proposed a lightweight scheme using the hash and XOR functions which is much more efficient compared with similar schemes based on elliptic curve. However, the investigations revealed that the claim concerning the unlinkability between the sessions of a sensor node is NOT true. The present paper considers the security issues of the scheme proposed by Li et al. and some of its new extensions in order to propose a new AKA scheme with anonymity and unlinkability of the sensor node sessions. The results of theoretical analysis compared with similar schemes indicate that the proposed scheme reduces average energy consumption and average computation time by 61 percent while reduces the average communication cost by 41 percent. Further, it has been shown by formal and informal analysis that, Besides the two anonymity and unlinkability features, the other main features of the security in the proposed scheme are comparable and similar to the recent similar schemes.
IoT security and privacy has raised grave concerns. Efforts have been made to design tools to identify and understand vulnerabilities of IoT systems. Most of the existing protocol security analysis techniques rely on a well understanding of the underlying communication protocols. In this paper, we systematically present the first manual reverse engineering framework for discovering communication protocols of embedded Linux based IoT systems. We have successfully applied our framework to reverse engineer a number of IoT systems. As an example, we present a detailed use of the framework reverse-engineering the WeMo smart plug communication protocol by extracting the firmware from the flash, performing static and dynamic analysis of the firmware and analyzing network traffic. The discovered protocol exposes severe design flaws that allow attackers to control or deny the service of victim plugs. Our manual reverse engineering framework is generic and can be applied to both read-only and writable Embedded Linux filesystems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
