We present a security analysis of the messaging service known as LINE, a popular platform used daily by millions of users in Southeast Asia - most notably Japan, Taiwan, Thailand, and Indonesia. More specifically, we focus on its underlying custom end-to-end encryption (E2EE) protocol, known as Letter Sealing v2. Our findings show that Letter Sealing allows a TLS Machine-in-the-Middle attacker or malicious server to violate integrity, authenticity, and confidentiality of communications. The stateless design of the protocol allows message replay, reordering, and blocking attacks without the user being notified. The lack of origin authentication facilitates impersonation attacks, in which the authorship of messages in one-to-one or group chats can be forged by malicious users colluding with the adversary. Lastly, stickers and URL previews present a notable leakage of plaintext, which leads to a violation of confidentiality. To verify the correctness of our findings, we mounted a Machine-in-the-Middle attack on an iOS device, yielding the device's outgoing traffic and the corresponding server responses. Utilizing this setup, we experimentally verified our attacks against the authentic LINE application and an independent implementation. We discuss our findings in comparison to the state-of-the-art E2EE protocols, and conclude that Letter Sealing does not satisfy the requirements expected from a modern E2EE messaging protocol.

We construct protocols for oblivious pseudorandom functions (OPRFs) based on alternating moduli assumptions in the 'Crypto Dark Matter' paradigm (Boneh et al, TCC 2016). Prior OPRFs based on this type of assumption were only secure against a semi-honest adversary. We show how to obtain maliciously secure protocols, by leveraging new cut-and-choose techniques for generating correlated randomness based on vector oblivious linear evaluation (VOLE), which allow efficient conversions between different moduli in zero-knowledge and secure two-party computation. Compared with the state-of-the-art GOLD OPRF (Yang et al, S&P 2025), our construction has a faster online phase in all settings, as well as overall better efficiency in the small-batch setting. Furthermore, our construction supports obtaining a secret-shared output, and can be extended to handle secretshared inputs. This opens up additional applications in variants of private set intersection and secure database operations.

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.

Cryptographic voting protocols have recently seen much interest from practitioners due to their (planned) use in countries such as Estonia, Switzerland, France, and Australia. Practical protocols usually rely on tested designs such as the mixing-and-decryption paradigm. There, multiple servers verifiably shuffle encrypted ballots, which are then decrypted in a distributed manner. While several efficient protocols implementing this paradigm exist from discrete log-type assumptions, the situation is less clear for post-quantum alternatives such as lattices. This is because the design ideas of the discrete log-based voting protocols do not carry over easily to the lattice setting, due to specific problems such as noise growth and approximate relations.

We generalize the Bernstein-Yang (BY) algorithm [11] for constant-time modular inversion to compute the Kronecker symbol, of which the Jacobi and Legendre symbols are special cases. We first develop a basic and easy-to-implement algorithm, defined with full-precision division steps. We then describe an optimized version due to Hamburg [21] over word-sized inputs, and formally verify its correctness. Along the way, we introduce a number of optimizations for implementing both versions in constant time. The resulting algorithms are particularly suitable for computing the Legendre symbol with dense prime p, where no efficient addition chain is known for exponentiating to p-1 over 2, as it is often the case in pairing-friendly elliptic curves. Our high-speed implementation for a range of parameters shows that the new algorithm is up to 40 times faster than exponentiation, and up to 25.7% faster than the previous state of the art. We illustrate our techniques with hashing to elliptic curves using the SwiftEC algorithm [17], with savings of 14.7%-48.1%, and to accelerating the CTIDH isogeny-based key exchange [7], with savings of 3.5-13.5%.

The security of modern cryptography depends on multiple factors, from sound hardness assumptions to correct implementations that resist side-channel cryptanalysis. Curve-based cryptography is not different in this regard, and substantial progress in the last few decades has been achieved in both selecting parameters and devising secure implementation strategies. In this context, the security of implementations of field inversion is sometimes overlooked in the research literature, because (i) the approach based on Fermat's Little Theorem (FLT) suffices performance-wise for many parameters used in practice; (ii) it is typically invoked only at the very end of a cryptographic computation, with a small impact on performance; (iii) it is challenging to implement securely for general parameters without a significant performance penalty. However, field inversion can process sensitive information and must be protected with side-channel countermeasures like any other cryptographic operation, as illustrated by recent attacks [1]–[3]. In this work, we focus on implementing field inversion for primes of cryptographic interest with security against timing attacks, irrespective of whether the FLT-based inversion can be efficiently implemented. We extend the Fiat-Crypto framework, which synthesizes provably correct-by-construction implementations, to implement the Bernstein-Yang inversion algorithm as a step towards this goal. This allows a correct implementation of prime field inversion to be synthesized for any prime. We benchmark the implementations across a range of primes for curve-based cryptography and they outperform traditional FLT-based approaches in most cases, with observed speedups up to 2 for the largest parameters. Our work is already used in production in the MirageOS unikernel operating system, zig programming language, and the ECCKiila framework [4]

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.

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.

Private set-intersection (PSI) is one of the most practically relevant special-purpose secure multiparty computation tasks, as it is motivated by many real-world applications. In this paper we present a new private set-intersection protocol which is laconic, meaning that the protocol only has two rounds and that the first message is independent of the set sizes. Laconic PSI can be useful in applications, where servers with large sets would like to learn the intersection of their set with smaller sets owned by resource-constrained clients and where multiple rounds of interactions are not possible.

We propose a privacy-preserving Naive Bayes classifier and apply it to the problem of private text classification. In this setting, a party (Alice) holds a text message, while another party (Bob) holds a classifier. At the end of the protocol, Alice will only learn the result of the classifier applied to her text input and Bob learns nothing. Our solution is based on Secure Multiparty Computation (SMC). Our Rust implementation provides a fast and secure solution for the classification of unstructured text. Applying our solution to the case of spam detection (the solution is generic, and can be used in any other scenario in which the Naive Bayes classifier can be employed), we can classify an SMS as spam or ham in less than 340ms in the case where the dictionary size of Bob’s model includes all words ($n = 5200$) and Alice’s SMS has at most$m = 160$unigrams. In the case with$n = 369$and$m = 8$(the average of a spam SMS in the database), our solution takes only 21ms.

Abstract In recent years, privacy research has been gaining ground in vehicular communication technologies. Collecting data from connected vehicles presents a range of opportunities for industry and government to perform data analytics. Although many researchers have explored some privacy solutions for vehicular communications, the conditions to deploy them are still maturing, especially when it comes to privacy for sensitive data aggregation analysis. In this work, we propose a hybrid solution combining the original differential privacy framework with an instance-based additive noise technique. The results show that for typical instances we obtain a significant reduction in outliers. As far as we know, our paper is the first detailed experimental evaluation of differentially private techniques applied to traffic monitoring. The validation of the proposed solution was performed through extensive simulations in typical traffic scenarios using real data.

Although it is one of the most popular signature schemes today, ECDSA presents a number of implementation pitfalls, in particular due to the very sensitive nature of the random value (known as the nonce) generated as part of the signing algorithm. It is known that any small amount of nonce exposure or nonce bias can in principle lead to a full key recovery: the key recovery is then a particular instance of Boneh and Venkatesan's hidden number problem (HNP). That observation has been practically exploited in many attacks in the literature, taking advantage of implementation defects or side-channel vulnerabilities in various concrete ECDSA implementations. However, most of the attacks so far have relied on at least 2 bits of nonce bias (except for the special case of curves at the 80-bit security level, for which attacks against 1-bit biases are known, albeit with a very high number of required signatures). In this paper, we uncover LadderLeak, a novel class of side-channel vulnerabilities in implementations of the Montgomery ladder used in ECDSA scalar multiplication. The vulnerability is in particular present in several recent versions of OpenSSL. However, it leaks less than 1 bit of information about the nonce, in the sense that it reveals the most significant bit of the nonce, but with probability <1. Exploiting such a mild leakage would be intractable using techniques present in the literature so far. However, we present a number of theoretical improvements of the Fourier analysis approach to solving the HNP (an approach originally due to Bleichenbacher), and this lets us practically break LadderLeak-vulnerable ECDSA implementations instantiated over the sect163r1 and NIST P-192 elliptic curves. In so doing, we achieve several significant computational records in practical attacks against the HNP.

Deterministic generation of per-signature randomness has been a widely accepted solution to mitigate the catastrophic risk of randomness failure in Fiat–Shamir type signature schemes. However, recent studies have practically demonstrated that such de-randomized schemes, including EdDSA, are vulnerable to differential fault attacks, which enable adversaries to recover the entire secret signing key, by artificially provoking randomness reuse or corrupting computation in other ways. In order to balance concerns of both randomness failures and the threat of fault injection, some signature designs are advocating a “hedged” derivation of the per-signature randomness, by hashing the secret key, message, and a nonce. Despite the growing popularity of the hedged paradigm in practical signature schemes, to the best of our knowledge, there has been no attempt to formally analyze the fault resilience of hedged signatures. We perform a formal security analysis of the fault resilience of signature schemes constructed via the Fiat–Shamir transform. We propose a model to characterize bit-tampering fault attacks, and investigate their impact across different steps of the signing operation. We prove that, for some types of faults, attacks are mitigated by the hedged paradigm, while attacks remain possible for others. As concrete case studies, we then apply our results to XEdDSA, a hedged version of EdDSA used in the Signal messaging protocol, and to Picnic2, a hedged Fiat–Shamir signature scheme in Round 2 of the NIST Post-Quantum standardization process.

A fundamental property of Physical Unclonable Functions (PUFs) is uniqueness, which results from the intrinsic characteristics of each PUF instance. However, PUF architectures employ elements whose physical characteristics and behavior may be very similar among different instances, thus leaking unwanted information. We explore the consequences of this effect by mounting Template Attacks over XOR Arbiter PUFs. In the attack, Challenge-Respose Pairs (CRPs) are profiled in one FPGA instance of the PUF to predict responses of a different FPGA instance, obtaining up to 80% of accuracy. We show that replicating the same attack strategy with a well-known Machine Learning (ML) algorithm would not be as effective, since different PUFs instances will not share similar CRP sets. Our template attack only needs few CRPs for profiling (at most 170), but it can be applied to different instances without additional training, which Machile Learning cannot do with unbiased PUF instances.

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.

Mechanisms for coordination and synchronization, like shared counters and distributed queues, are used in the development of many distributed systems. These mechanisms are implemented on top of coordination infrastructures, such as tuple spaces. A recent study showed that extensibility is fundamental for performance: the main idea is to allow the servers supporting the coordination infrastructure to access and process coordination information, consequently, it is not necessary to transfer information to clients or to reprocess requests due to concurrency. Unfortunately, existing proposals for extensible distributed coordination do not provide security and privacy once servers must access data in plaintext. This work proposes the use of robust cryptographic schemes, recently integrated into DEPSPACE, to develop secure protocols for extensible coordination. Experiments show that the proposed solutions significantly improve system performance.

Decades went by since Mark Weiser published his influential work on how a computer of the 21st century would look like. Over the years, some of the UbiComp features presented in that paper have been gradually adopted by industry players in the technology market. While this technological evolution resulted in many benefits to our society, it has also posed, along the way, countless challenges that we have yet to surpass. In this paper, we address major challenges from two areas that most afflict the UbiComp revolution: security and privacy. We examine open problems on software protection, long-term security, cryptography engineering, and privacy implications. We also point out promising directions towards the solutions of those problems. We claim that if we get all this right, we will turn the science fiction of UbiComp into science fact.

A multiset hash function associates a hash value to arbitrary collections of objects with possible repetitions. Such a hash function is said to be homomorphic, or incremental, when the hash of the union of two collections is easy to compute from the hashes of the two collections themselves: it is usually their sum under a suitable group operation. In particular, hash values of large collections can be computed incrementally and/or in parallel. This makes homomorphic hashing a very useful primitive, with applications ranging from database integrity verification to streaming set/multiset comparison and network coding. Unfortunately, constructions of homomorphic hash functions proposed in the literature are hampered by two main drawbacks. They tend to be much longer than usual hash functions at the same security level (e.g. to achieve a collision resistance of 2128, they are several thousand bits long, as opposed to 256 bits for usual hash functions), and they are also quite slow. In this paper, we introduce the Elliptic Curve Multiset Hash (ECMH), which combines a usual bit string-valued hash function like BLAKE2 with an efficient encoding into binary elliptic curves to overcome both difficulties. On the one hand, the size of ECMH digests is essentially optimal: 2m-bit hash values provide O(2m) collision resistance. On the other hand, we demonstrate a highly-efficient software implementation of ECMH, which our thorough empirical evaluation shows to be capable of processing over 3 million set elements per second on a 4 GHz Intel Haswell machine at the 128 bit security level—many times faster than previous practical methods. While incremental hashing based on elliptic curves has been considered previously (Brown, D.R.L. (2008) The encrypted elliptic curve hash. IACR Cryptology ePrint Archive, 2008, 12.), the proposed method was less efficient, susceptible to timing attacks, and potentially patent-encumbered (Brown, D. and Yamada, A. (2007) Method and apparatus for performing validation of elliptic curve public keys. US Patent, 7, 257, 709.), and no practical implementation was demonstrated.

Information flow analyses traditionally use the Program Dependence Graph (PDG) as a supporting data-structure. This graph relies on Ferrante et al.'s notion of control dependences to represent implicit flows of information. A limitation of this approach is that it may create O(|I| x |E|) implicit flow edges in the PDG, where I are the instructions in a program, and E are the edges in its control flow graph. This paper shows that it is possible to compute information flow analyses using a different notion of implicit dependence, which yields a number of edges linear on the number of definitions plus uses of variables. Our algorithm computes these dependences in a single traversal of the program's dominance tree. This efficiency is possible due to a key property of programs in Static Single Assignment form: the definition of a variable dominates all its uses. Our algorithm correctly implements Hunt and Sands system of security types. Contrary to their original formulation, which required O(IxI) space and time for structured programs, we require only O(I). We have used our ideas to build FlowTracker, a tool that uncovers side-channel vulnerabilities in cryptographic algorithms. FlowTracker handles programs with over one-million assembly instructions in less than 200 seconds, and creates 24% less implicit flow edges than Ferrante et al.'s technique. FlowTracker has detected an issue in a constant-time implementation of Elliptic Curve Cryptography; it has found several time-variant constructions in OpenSSL, one issue in TrueCrypt and it has validated the isochronous behavior of the NaCl library.

Physical Unclonable Functions (PUFs) are devices which exploit manufacturing variability to uniquely distinguish individuals, thus preventing them from cloning for malicious purposes. With the increasing demand of low-cost devices, PUF designs which can effectively combine small silicon area and power consumption with high resistance to attacks have become of great interest. Unfortunately, many delay-based PUFs have revealed security weaknesses, making them less useful in such domains. This paper presents a novel delay-based strong PUF, the CRPUF (Cylindrical Reconvergence PUF). CRPUF is based on a carefully designed cylindrical XOR fabric, which allows for a large number of delay paths, thus producing a large combination of challenge-response pairs (CRPs) with relatively low transistor count. Simulations based on circuit delay variability models were performed to evaluate CRPUF with respect to well-known delay PUFs. Experimental results show that CRPUF has Hamming Distance, Hamming Weight and Entropy comparable to the best results published so far, with acceptable levels of Bit Error Rate. Moreover, experiments also show that CRPUF is much more resistant to modeling attacks than other delay and some memory-based PUFs, making it a good candidate to systems which have stringent cost and security constraints.

The consumer electronics industry is witnessing a surge in Internet of Things (IoT) devices, ranging from mundane artifacts to complex biosensors connected across disparate networks. As the demand for IoT devices grows, the need for stronger authentication and access control mechanisms is greater than ever. Legacy authentication and access control mechanisms do not meet the growing needs of IoT. In particular, there is a dire need for a holistic authentication mechanism throughout the IoT device life-cycle, namely from the manufacturing to the retirement of the device. As a plausible solution, we present Authentication of Things (AoT), a suite of protocols that incorporate authentication and access control during the entire IoT device life span. Primarily, AoT relies on Identity- and Attribute-Based Cryptography to cryptographically enforce Attribute-Based Access Control (ABAC). Additionally, AoT facilitates secure (in terms of stronger authentication) wireless interoperability of new and guest devices in a seamless manner. To validate our solution, we have developed AoT for Android smartphones like the LG G4 and evaluated all the cryptographic primitives over more constrained devices like the Intel Edison and the Arduino Due. This included the implementation of an Attribute-Based Signature (ABS) scheme. Our results indicate AoT ranges from highly efficient on resource-rich devices to affordable on resource-constrained IoT-like devices. Typically, an ABS generation takes around 27 ms on the LG G4, 282 ms on the Intel Edison, and 1.5 s on the Arduino Due.

Recent works have shown the usefulness of network and application layer protocols that connect low-power sensor nodes directly to multiple applications and users on the Internet. We propose a security solution for this scenario. While previous works have provided security support for various communication patterns in sensor networks, such as among nodes, from nodes to a base station, and from users to nodes, the security of communication from sensor nodes to multiple users has not been sufficiently addressed. Specifically, we explore this design space and develop a security solution, named Secure Tiny Web Service, for efficient authentication of data sent by a resource-constrained sensor node to multiple users, using digital signatures. We investigate the resource overheads in communication and computation of four suitable signature schemes—the Elliptic Curve Digital Signature Algorithm, the (elliptic curve) Schnorr signature, and the Boneh–Lynn–Shacham and Zhang–Safavi-Naini–Susilo short signature schemes. We implement these schemes on two popular sensor node architectures (based on AVR ATmega128L and MSP430 processors with 802.15.4 radios) and experimentally characterize relevant trade-offs.

After a few years of intense research, wireless sensor networks (WSNs) still demand new secure and cryptographic schemes. On the other hand, the advent of cryptography from pairings has enabled a wide range of novel cryptosystems. In this work we present TinyTate, the first known implementation of pairings for sensor nodes based on the 8-bit/7.3828-MHz ATmega128L microcontroller (e.g., MICA2 and MICAz motes). We then conclude that cryptography from pairings is indeed viable in resource-constrained nodes.