Julia Hesse, Dennis Hofheinz, Lisa Kohl, Roman Langrehr
We investigate the quality of security reductions for non-interactive key exchange (NIKE) schemes. Unlike for many other cryptographic building blocks (like public-key encryption, signatures, or zero-knowledge proofs), all known NIKE security reductions to date are non-tight, i.e., lose a factor of at least the number of users in the system. In that sense, NIKE forms a particularly elusive target for tight security reductions. The main technical obstacle in achieving tightly secure NIKE schemes are adaptive corruptions. Hence, in this work, we explore security notions and schemes that lie between selective security and fully adaptive security. Concretely: We exhibit a tradeoff between key size and reduction loss. We show that a tighter reduction can be bought by larger public and secret NIKE keys. Concretely, we present a simple NIKE scheme with a reduction loss of O(N2log (ν) / ν2), and public and secret keys of O(ν) group elements, where N denotes the overall number of users in the system, and ν is a freely adjustable scheme parameter. Our scheme achieves full adaptive security even against multiple “test queries” (i.e., adversarial challenges), but requires keys of size O(N) to achieve (almost) tight security under the matrix Diffie-Hellman assumption. Still, already this simple scheme circumvents existing lower bounds. We show that this tradeoff is inherent. We contrast the security of our simple scheme with a lower bound for all NIKE schemes in which shared keys can be expressed as an “inner product in the exponent”. This result covers the original Diffie-Hellman NIKE scheme, as well as a large class of its variants, and in particular our simple scheme. Our lower bound gives a tradeoff between the “dimension” of any such scheme (which directly corresponds to key sizes in existing schemes), and the reduction quality. For ν= O(N), this shows our simple scheme and reduction optimal (up to a logarithmic factor). We exhibit a tradeoff between security and key size for tight reductions. We show that it is possible to circumvent the inherent tradeoff above by relaxing the desired security notion. Concretely, we consider the natural notion of semi-adaptive security, where the adversary has to commit to a single test query after seeing all public keys. As a feasibility result, we bring forward the first scheme that enjoys compact public keys and tight semi-adaptive security under the conjunction of the matrix Diffie-Hellman and learning with errors assumptions. We believe that our results shed a new light on the role of adaptivity in NIKE security, and also illustrate the special role of NIKE when it comes to tight security reductions.
Abstract It is well known that several cryptographic primitives cannot be achieved without a common reference string (CRS). Those include, for instance, non-interactive zero-knowledge for NP, or maliciously secure computation in fewer than four rounds. The security of those primitives heavily relies on the assumption that the trusted authority, who generates the CRS, does not misuse the randomness used in the CRS generation. However, we argue that there is no such thing as an unconditionally trusted authority and every authority must be held accountable for any trust to be well-founded. Indeed, a malicious authority can, for instance, recover private inputs of honest parties given transcripts of the protocols executed with respect to the CRS it has generated. While eliminating trust in the trusted authority may not be entirely feasible, can we at least move towards achieving some notion of accountability? We propose a new notion in which, if the CRS authority releases the private inputs of protocol executions to others, we can then provide a publicly-verifiable proof that certifies that the authority misbehaved. We study the feasibility of this notion in the context of non-interactive zero knowledge and two-round secure two-party computation.
Karim Baghery, Cyprien Delpech de Saint Guilhem, Emmanuela Orsini, Nigel P. Smart · 5 authors
This paper introduces M-Circuits, a program representation which generalizes arithmetic and binary circuits. This new representation is motivated by the way modern multi-party computation (MPC) systems based on linear secret sharing schemes actually operate. We then show how this representation also allows one to construct zero knowledge proof (ZKP) systems based on the MPC-in-the-head paradigm. The use of the M-Circuit program abstraction then allows for a number of program-specific optimizations to be applied generically. It also allows to separate complexity and security optimizations for program compilation from those for application protocols (MPC or ZKP).
Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, Mor Weiss
Zero-Knowledge PCPs (ZK-PCPs; Kilian, Petrank, and Tardos, STOC `97) are PCPs with the additional zero-knowledge guarantee that the view of any (possibly malicious) verifier making a bounded number of queries to the proof can be efficiently simulated up to a small statistical distance. Similarly, ZK-PCPs of Proximity (ZK-PCPPs; Ishai and Weiss, TCC `14) are PCPPs in which the view of an adversarial verifier can be efficiently simulated with few queries to the input. Previous ZK-PCP constructions obtained an exponential gap between the query complexity q of the honest verifier, and the bound q^* on the queries of a malicious verifier (i.e., q = poly log (q^*)), but required either exponential-time simulation, or adaptive honest verification. This should be contrasted with standard PCPs, that can be verified non-adaptively (i.e., with a single round of queries to the proof). The problem of constructing such ZK-PCPs, even when q^* = q, has remained open since they were first introduced more than 2 decades ago. This question is also open for ZK-PCPPs, for which no construction with non-adaptive honest verification is known (not even with exponential-time simulation). We resolve this question by constructing the first ZK-PCPs and ZK-PCPPs which simultaneously achieve efficient zero-knowledge simulation and non-adaptive honest verification. Our schemes have a square-root query gap, namely q^*/q = O(√n) where n is the input length. Our constructions combine the "MPC-in-the-head" technique (Ishai et al., STOC `07) with leakage-resilient secret sharing. Specifically, we use the MPC-in-the-head technique to construct a ZK-PCP variant over a large alphabet, then employ leakage-resilient secret sharing to design a new alphabet reduction for ZK-PCPs which preserves zero-knowledge.
Soumyashree S. Panda, Debasish Jena, Bhabendu Kumar Mohanta, Srikanta Patnaik
With the omnipresence of technology, intelligent transportation system (ITS) is no more a distant dream but has become an achievable reality. One of the fundamental challenges in the implementation of an ITS is the proper management of security and privacy issues, especially how the system confirms the validity of its users. Most of the existing security mechanisms are based on a centralized framework and assume the registration authority and roadside units to be trustful. Therefore, a distributed framework using Blockchain and, a very lightweight and privacy-preserving authentication protocol employing an interactive zero-knowledge proof (ZKP) based on elliptic curve cryptography (ECC) is proposed. An in-depth analysis of the protocol demonstrates that it meets all the security and privacy requisites of an ITS. In addition, the suggested protocol is also validated using the widely used AVISPA tool. The reliability and effectiveness of the protocol are analyzed through simulation using NS2 which proves the practicality of the protocol.
2 source records
Vehicular Ad Hoc Networks (VANETs)
Advanced Steganography and Watermarking Techniques
Recently, the right to privacy has become an important global issue, and laws are being enacted in different countries to ensure that citizens have control over how their data are stored and used. In this scenario, corporates face an increasing burden to comply with these laws, while ensuring that their business models and workflows are interrupted to as little a degree as possible. This article presents blockchain as a potential technology that can help users keep their data under their control and yet allow companies to responsibly access the data they need to function. It begins with an overview of blockchain as a technology and the properties that make it useful as a tool for privacy compliance. It then explores more niche fields, such as Zero Knowledge Proofs, and considers two industries where blockchain can be of benefit to consumers and corporates from a privacy standpoint.