Cryptography, Volume 4, Issue 4 (December 2020) – 12 articles

Cohen, Goldwasser, and Vaikuntanathan (TCC’15) introduced the concept of aggregate pseudo-random functions (PRFs), which allow efficiently computing the aggregate of PRF values over exponential-sized sets. In this paper, we explore the aggregation augmentation on verifiable random function (VRFs), introduced by Micali, Rabin and Vadhan (FOCS’99), as well as its application to e-lottery schemes. We introduce the notion of static aggregate verifiable random functions (Agg-VRFs), which perform aggregation for VRFs in a static setting. Our contributions can be summarized as follows: (1) we define static aggregate VRFs, which allow the efficient aggregation of VRF values and the corresponding proofs over super-polynomially large sets; (2) we present a static Agg-VRF construction over bit-fixing sets with respect to product aggregation based on the q-decisional Diffie–Hellman exponent assumption; (3) we test the performance of our static Agg-VRFs instantiation in comparison to a standard (non-aggregate) VRF in terms of costing time for the aggregation and verification processes, which shows that Agg-VRFs lower considerably the timing of verification of big sets; and (4) by employing Agg-VRFs, we propose an improved e-lottery scheme based on the framework of Chow et al.’s VRF-based e-lottery proposal (ICCSA’05). We evaluate the performance of Chow et al.’s e-lottery scheme and our improved scheme, and the latter shows a significant improvement in the efficiency of generating the winning number and the player verification. Full article

Cryptographic designs are vulnerable to side-channel analysis attacks. Evaluating their security during design stages is of crucial importance. The latter is achieved by very expensive (slow) analog transient-noise simulations over advanced fabrication process technologies. The main challenge of such rigorous security-evaluation analysis lies in the fact that technologies are becoming more and more complex and the physical properties of manufactured devices vary significantly due to process variations. In turn, a detailed security evaluation process imposes exponential time complexity with the circuit-size, the number of physical implementation corners (statistical variations) and the accuracy of the circuit-simulator. Given these circumstances, what is the cost of not exhausting the entire implementation space? In terms of simulation-time complexity, the benefits would clearly be significant; however, we are interested in evaluating the security implications. This question can be formulated for many other interesting side-channel contexts such as for example, how would an attack-outcome vary when the adversary is building a leakage template over one device, i.e., one physical corner, and it performs an evaluation (attack) phase of a device drawn from a different statistical corner? Alternatively, is it safe to assume that a typical (average) corner would represent the worst case in terms of security evaluation or would it be advisable to perform a security evaluation over another specific view? Finally, how would the outcome vary concretely? We ran in-depth experiments to answer these questions in the hope of finding a nice tradeoff between simulation efforts and expertise, and security-evaluation degradation. We evaluate the results utilizing methodologies such as template-attacks with a clear distinction between profiling and attack-phase statistical views. This exemplary view of what an adversary might capture in these scenarios is followed by a more complete statistical evaluation analysis utilizing tools such as the Kullback–Leibler (KL) divergence and the Jensen-Shannon (JS) divergence to draw conclusions. Full article

With the huge transfers of data involved in the modern world, it is both crucial and challenging to maintain the security of data. This paper proposes a novel algorithm of information embedding into digital images that could be used to protect confidential information. The presented algorithm makes use of the Chinese remainder theorem and adaptive embedding to achieve good imperceptibility along with the possibility of hiding a decent amount of confidential information. The algorithm is evaluated via computing experiments and evaluation results, as well as comparison with similar works, demonstrate good imperceptibility qualities of the proposed scheme. Full article

Security and access control aspects are becoming more and more essential to consider during the design of various systems and the tremendous growth of digitization. One of the related key building blocks in this regard is, essentially, the authentication process. Conventional schemes based on one or two authenticating factors can no longer provide the required levels of flexibility and pro-activity of the access procedures, thus, the concept of threshold-based multi-factor authentication (MFA) was introduced, in which some of the factors may be missing, but the access can still be granted. In turn, secret sharing is a crucial component of the MFA systems, with Shamir’s schema being the most widely known one historically and based on Lagrange interpolation polynomial. Interestingly, the older Newtonian approach to the same problem is almost left without attention. At the same time, it means that the coefficients of the existing secret polynomial do not need to be re-calculated while adding a new factor. Therefore, this paper investigates this known property of Newton’s interpolation formula, illustrating that, in specific MFA cases, the whole system may become more flexible and scalable, which is essential for future authentication systems. Full article

An efficient member revocation mechanism is a desirable feature when group signature schemes are applied in practical scenarios. Revocation methods, such as verifier-local revocation (VLR), provide an efficient member revocation in applications of group signatures. However, VLR-group signatures rely on a weaker security notion. On the other hand, group signature schemes for static groups gain stronger security with the full-anonymity security notion. Even though an outsider sees the secret signing keys of all group members in the full-anonymity, the signer is still anonymous. Achieving the full-anonymity for VLR group signature schemes is challenging due to the structure of secret signing keys. The secret signing keys of those schemes consist of tokens, which are used to manage revocation. The reveal of tokens may destroy the anonymity of the signers. We obtain stronger security for the lattice-based VLR group signature schemes by providing a new key generation method, which outputs revocation tokens without deriving from the members’ secret signing keys. We propose a new group signature scheme from lattices with VLR, which achieves stronger security than the previous related works. To avoid signature forgeries, we suggest a new zero-knowledge proof system that requires signers to validate themselves. Moreover, we output an efficient tracing mechanism. Full article

For a blockchain, consensus is the foundation protocol that enables cryptocurrencies such as Bitcoin to maintain state. Additionally, to ensure safety and liveness for a publicly accessible and verifiable ledger, fault tolerance must be robust. However, there appears to be a degree of misunderstanding about how consensus is applied across blockchains. To assist researchers considering variations between them, this study presents a rational classification of consensus methods applied to current blockchains. The study provides a survey of 19 methods classified by the scarce resource they employ: clock-cycles, bits, tokens, votes, time, and biometrics. Blockchain implementations are split between consensus algorithms requiring proof of resource and those that use majority voting to update the ledger. Full article

In conventional cryptography, information-theoretically secure message authentication can be achieved by means of universal hash functions, and requires that the two legitimate users share a random secret key, which is at least twice as long as the tag. We address the question of whether quantum resources can offer any advantage over classical unconditionally secure message authentication codes. It is shown that a broad class of symmetric prepare-and-measure quantum message-authentication schemes cannot do better than their classical counterparts. Full article

Electromagnetic and power side-channel analysis (SCA) provides attackers a prominent tool to extract the secret key from the cryptographic engine. In this article, we present our cross-device deep learning (DL)-based side-channel attack (X-DeepSCA) which reduces the time to attack on embedded devices, thereby increasing the threat surface significantly. Consequently, with the knowledge of such advanced attacks, we performed a ground-up white-box analysis of the crypto IC to root-cause the source of the electromagnetic (EM) side-channel leakage. Equipped with the understanding that the higher-level metals significantly contribute to the EM leakage, we present STELLAR, which proposes to route the crypto core within the lower metals and then embed it within a current-domain signature attenuation (CDSA) hardware to ensure that the critical correlated signature gets suppressed before it reaches the top-level metal layers. CDSA-AES256 with local lower metal routing was fabricated in a TSMC 65 nm process and evaluated against different profiled and non-profiled attacks, showing protection beyond $1B$ encryptions, compared to ∼$10K$ for the unprotected AES. Overall, the presented countermeasure achieved a $100\times$ improvement over the state-of-the-art countermeasures available, with comparable power/area overheads and without any performance degradation. Moreover, it is a generic countermeasure and can be used to protect any crypto cores while preserving the legacy of the existing implementations. Full article

With the rapid growth of smart devices and technological advancements in tracking geospatial data, the demand for Location-Based Services (LBS) is facing a constant rise in several domains, including military, healthcare and transportation. It is a natural step to migrate LBS to a cloud environment to achieve on-demand scalability and increased resiliency. Nonetheless, outsourcing sensitive location data to a third-party cloud provider raises a host of privacy concerns as the data owners have reduced visibility and control over the outsourced data. In this paper, we consider outsourced LBS where users want to retrieve map directions without disclosing their location information. Specifically, our paper aims to address the following problem: Given a user’s location s, a target destination t, and a graph G stored in a cloud, can users retrieve the shortest path route from s to t in a privacy-preserving manner? Although there exist a few solutions to this problem, they are either inefficient or insecure. For example, existing solutions either leak intermediate results to untrusted cloud providers or incur significant costs on the end-user. To address this gap, we propose an efficient and secure solution based on homomorphic encryption properties combined with a novel data aggregation technique. We formally show that our solution achieves semantic security guarantees under the semi-honest model. Additionally, we provide complexity analysis and experimental results to demonstrate that the proposed protocol is significantly more efficient than the current state-of-the-art techniques. Full article

In the area of searchable encryption, public key encryption with keyword search (PEKS) has been a critically important and promising technique which provides secure search over encrypted data in cloud computing. PEKS can protect user data privacy without affecting the usage of the data stored in the untrusted cloud server environment. However, most of the existing PEKS schemes concentrate on data users’ rich search functionalities, regardless of their search permission. Attribute-based encryption technology is a good method to solve the security issues, which provides fine-grained access control to the encrypted data. In this paper, we propose a privacy-preserving and efficient public key encryption with keyword search scheme by using the ciphertext-policy attribute-based encryption (CP-ABE) technique to support both fine-grained access control and keyword search over encrypted data simultaneously. We formalize the security definition, and prove that our scheme achieves selective indistinguishability security against an adaptive chosen keyword attack. Finally, we present the performance analysis in terms of theoretical analysis and experimental analysis, and demonstrate the efficiency of our scheme. Full article

Cryptographic implementations need to be robust amidst the widespread use of crypto-libraries and attacks targeting their implementation, such as side-channel attacks (SCA). Many certification schemes, such as Common Criteria and FIPS 140, continue without addressing side-channel flaws. Research works mostly tackle sophisticated attacks with simple use-cases, which is not the reality where end-to-end evaluation is not trivial. In this study we used all due diligence to assess the invulnerability of a given implementation from the shoes of an evaluator. In this work we underline that there are two kinds of SCA: horizontal and vertical. In terms of quotation, measurement and exploitation, horizontal SCA is easier. If traces are constant-time, then vertical attacks become convenient, since there is no need for specific alignment (“value based analysis”). We introduce our new methodology: Vary the key to select sensitive samples, where the values depend upon the key, and subsequently vary the mask to uncover unmasked key-dependent leakage, i.e., the flaws. This can be done in the source code (pre-silicon) for the designer or on the actual traces (post-silicon) for the test-lab. We also propose a methodology for quotations regarding SCA unlike standards that focus on only one aspect (like number of traces) and forgets about other aspects (such as equipment; cf. ISO/IEC 20085-1. Full article

Reconfigurable computing is becoming ubiquitous in the form of consumer-based Internet of Things (IoT) devices. Reconfigurable computing architectures have found their place in safety-critical infrastructures such as the automotive industry. As the target architecture evolves, it also needs to be updated remotely on the target platform. This process is susceptible to remote hijacking, where the attacker can maliciously update the reconfigurable hardware target with tainted hardware configuration. This paper proposes an architecture of establishing Root of Trust at the hardware level using cryptographic co-processors and Trusted Platform Modules (TPMs) and enable over the air updates. The proposed framework implements a secure boot protocol on Xilinx based FPGAs. The project demonstrates the configuration of the bitstream, boot process integration with TPM and secure over-the-air updates for the hardware reconfiguration. Full article