A survey of elliptic curves for proof systems Aranha, Diego F.; El Housni, Youssef; Guillevic, Aurore
Designs, codes, and cryptography,
11/2023, Letnik:
91, Številka:
11
Journal Article
Recenzirano
Odprti dostop
Elliptic curves have become key ingredients for instantiating zero-knowledge proofs and more generally proof systems. Recently, there have been many tailored constructions of these curves that aim at ...efficiently implementing different kinds of proof systems. In this survey we provide the reader with a comprehensive overview on existing work and revisit the contributions in terms of efficiency and security. We present an overview at three stages of the process: curves to instantiate a SNARK, curves to instantiate a recursive SNARK, and also curves to express an elliptic-curve related statement. We provide new constructions of curves for SNARKs and generalize the state-of-the-art constructions for recursive SNARKs. We also exhaustively document the existing work and open-source implementations.
Key distribution in Wireless Sensor Networks (WSNs) is challenging. Symmetric cryptosystems can perform it efficiently, but they often do not provide a perfect trade-off between resilience and ...storage. Further, even though conventional public key and elliptic curve cryptosystems are computationally feasible on sensor nodes, protocols based on them are not, as they require the exchange and storage of large keys and certificates, which is expensive.
Using Pairing-Based Cryptography (PBC) protocols parties can agree on keys without any interaction. In this work, we (i) show how security in WSNs can be bootstrapped using an authenticated identity-based non-interactive protocol and (ii) present TinyPBC, to our knowledge, the most efficient implementation of PBC primitives for 8, 16 and 32-bit processors commonly found in sensor nodes. TinyPBC is able to compute pairings, the most expensive primitive of PBC, in 1.90
s on ATmega128L, 1.27
s on MSP430 and 0.14
s on PXA27x.
Recent developments in telecommunications have allowed drawing new paradigms, including the Internet of Everything, to provide services by the interconnection of different physical devices enabling ...the exchange of data to enrich and automate people’s daily activities; and Fog computing, which is an extension of the well-known Cloud computing, bringing tasks to the edge of the network exploiting characteristics such as lower latency, mobility support, and location awareness. Combining these paradigms opens a new set of possibilities for innovative services and applications; however, it also brings a new complex scenario that must be efficiently managed to properly fulfill the needs of the users. In this scenario, the Fog Orchestrator component is the key to coordinate the services in the middle of Cloud computing and Internet of Everything. In this paper, key challenges in the development of the Fog Orchestrator to support the Internet of Everything are identified, including how they affect the tasks that a Fog service Orchestrator should perform. Furthermore, different service Orchestrator architectures for the Fog are explored and analyzed in order to identify how the previously listed challenges are being tackled. Finally, a discussion about the open challenges, technological directions, and future of the research on this subject is presented.
Abstract Privacy-preserving smart meter data collection and analysis are critical for optimizing smart grid environments without compromising privacy. Using homomorphic encryption techniques, smart ...meters can encrypt collected data to ensure confidentiality, and other untrusted nodes can further compute over the encrypted data without having to recover the underlying plaintext. As an illustrative example, this approach can be useful to compute the monthly electricity consumption without violating consumer privacy by collecting fine-granular data through small increments of time. Toward that end, we propose an architecture for privacy-preserving smart meter data collection, aggregation and analysis based on lattice-based homomorphic encryption. Furthermore, we compare the proposed method with the Paillier and Boneh–Goh–Nissim (BGN) cryptosystems, which are popular alternatives for homomorphic encryption in smart grids. We consider different services with different requirements in terms of multiplicative depth, e.g. billing, variance and nonlinear support vector machine classification. Accordingly, we measure and show the practical overhead of using the proposed homomorphic encryption method in terms of communication traffic (ciphertext size) and latency. Our results show that lattice-based homomorphic encryption is more efficient than Paillier and BGN for both multiplication and addition operations while offering more flexibility in terms of the computation that can be evaluated homomorphically.
Summary
This paper presents a new enhanced version of the QcBits key encapsulation mechanism, which is a constant‐time implementation of the Niederreiter cryptosystem using QC‐MDPC codes. In this ...version, we updated the implementation parameters to meet the 128‐bit quantum security level, replaced some of the core algorithms to avoid using slower instructions, vectorized the entire code using the AVX‐512 instruction set extension, and applied several other techniques to achieve a competitive performance level. Our implementation takes 928, 259, and 5008 thousand Skylake cycles to perform batch key generation (cost per key), encryption, and uniform decryption, respectively. Comparing with the current state‐of‐the‐art implementation for QC‐MDPC codes, BIKE, our code is 1.9 times faster when decrypting messages.
MitID is the new electronic identification (eID) solution in Denmark. It provides access to many online services, including online banking, insurance, taxes, and health information. In this paper, we ...analyze the security of the new solution from the user experience perspective concerning Denial of Service (DoS), Social Engineering (SocEng), and other possible attacks that can be mounted without special privileges or obtaining unauthorized access. Our analysis shows that, even though the solution is of paramount importance to the Danish online infrastructure, the analyzed version did not adequately defend against simple attacks targeting specific users. With simple automated scripts, we were able to prevent a targeted user from authenticating for a period of 9 days; and show how an attacker can collect information to mount convincing SocEng attacks aiming at identity theft. Our findings were disclosed to the affected parties in December 2021, and since then, the solution has been updated two times. The first update in January 2022 rendered the SocEng attacks ineffective. However, due to the inherent design trade-offs, targeted DoS attacks were still unmitigated. The second update was in June 2023 and appears to address all of our findings.
Several works have characterized weak instances of the Ring-LWE problem by exploring vulnerabilities arising from the use of algebraic structures. Although these weak instances are not addressed by ...worst-case hardness theorems, enabling other ring instantiations enlarges the scope of possible applications and favors the diversification of security assumptions. In this work, we extend the Ring-LWE problem in lattice-based cryptography to include algebraic lattices, realized through twisted embeddings. We define the class of problems Twisted Ring-LWE, which replaces the canonical embedding by an extended form. By doing so, we allow the Ring-LWE problem to be used over maximal real subfields of cyclotomic number fields. We prove that Twisted Ring-LWE is secure by providing a security reduction from Ring-LWE to Twisted Ring-LWE in both search and decision forms. It is also shown that the twist factor does not affect the asymptotic approximation factors in the worst-case to average-case reductions. Thus, Twisted Ring-LWE maintains the consolidated hardness guarantee of Ring-LWE and increases the existing scope of algebraic lattices that can be considered for cryptographic applications. Additionally, we expand on the results of Ducas and Durmus (Public-Key Cryptography, 2012) on spherical Gaussian distributions to the proposed class of lattices under certain restrictions. As a result, sampling from a spherical Gaussian distribution can be done directly in the respective number field while maintaining its format and standard deviation when seen in Zn via twisted embeddings.
Mechanisms for distributed coordination are used in the development of many distributed systems and, generally, are implemented on top of coordination infrastructures, such as tuple spaces. Although ...tuple spaces provide the coordination functionalities, a recent study showed that extensibility is fundamental for performance. The main idea behind extensibility is to allow the servers, supporting the coordination infrastructure, to access and process coordination information. Consequently, it is not necessary to move information from servers to clients or to reprocess requests due to concurrency. Unfortunately, existing proposals for extensible distributed coordination do not provide security and privacy once servers access data in plaintext. This work uses robust cryptographic schemes recently integrated into DepSpace, a tuple space implementation, to propose secure protocols for coordination with and without extensions. Experiments compare the proposed solutions and consider also the proposed protocols without security and privacy, showing that extensible coordination significantly improves system performance even using costly cryptographic operations.
Recent works challenged the number-theoretic transform (NTT) as the most efficient method for polynomial multiplication in GPU implementations of fully homomorphic encryption schemes such as CKKS and ...BFV. In particular, these works argue that the discrete galois transform (DGT) is a better candidate for this particular case. However, these claims were never rigorously validated, and only intuition was used to argue in favor of each transform. This work brings some light on the discussion by developing similar CUDA implementations of the CKKS cryptosystem, differing only in the underlying transform and related data structure. We ran several experiments and collected performance metrics in different contexts, ranging from the basic direct comparison between the transforms to measuring the impact of each one on the inference phase of the logistic regression algorithm. Our observations suggest that, despite some specific polynomial ring configurations, the DGT in a standalone implementation does not offer the same performances of the NTT. However, when we consider the entire cryptosystem, we noticed that the effects of the higher arithmetic density of the DGT on other parts of the implementation are substantial, implying a considerable performance improvement of up to
15
%
on the homomorphic multiplication. Furthermore, this speedup is consistent when we consider a more complex application, indicating that the DGT suits better the target architecture.
PDF
