To enhance the security or the efficiency of the standard RSA cryptosystem, some variants have been proposed based on elliptic curves, Gaussian integers or Lucas sequences. A typical type of these variants which we called Type-A variants have the specified modified Euler's totient function $\psi(N)=(p^2-1)(q^2-1)$. But in 2018, based on cubic Pell equation, Murru and Saettone presented a new RSA-like cryptosystem, and it is another type of RSA variants which we called Type-B variants, since their scheme has $\psi(N)=(p^2+p+1)(q^2+q+1)$. For RSA-like cryptosystems, four key-related attacks have been widely analyzed, i.e., the small private key attack, the multiple private keys attack, the partial key exposure attack and the small prime difference attack. These attacks are well-studied on both standard RSA and Type-A variants. Recently, the small private key attack on Type-B variants has also been analyzed. In this paper, we make further cryptanalysis of Type-B variants, that is, we propose the first theoretical results of multiple private keys attack, partial key exposure attack as well as small prime difference attack on Type-B variants, and the validity of our attacks are verified by experiments. Our results show that for all three attacks, Type-B variants are less secure than standard RSA.

We present a rate-$1$ construction of a publicly verifiable non-interactive argument system for batch-$\mathsf{NP}$ (also called a BARG), under the LWE assumption. Namely, a proof corresponding to a batch of $k$ NP statements each with an $m$-bit witness, has size $m + \mathsf{poly}(\lambda,\log k)$. In contrast, prior work either relied on non-standard knowledge assumptions, or produced proofs of size $m \cdot \mathsf{poly}(\lambda,\log k)$ (Choudhuri, Jain, and Jin, STOC 2021, following Kalai, Paneth, and Yang 2019). We show how to use our rate-$1$ BARG scheme to obtain the following results, all under the LWE assumption in the standard model: - A multi-hop BARG scheme for $\mathsf{NP}$. - A multi-hop aggregate signature scheme. - An incrementally verifiable computation (IVC) scheme for arbitrary $T$-time deterministic computations with proof size $\mathsf{poly}(\lambda,\log T)$. Prior to this work, multi-hop BARGs were only known under non-standard knowledge assumptions or in the random oracle model; aggregate signatures were only known under indistinguishability obfuscation (and RSA) or in the random oracle model; IVC schemes with proofs of size $\mathsf{poly}(\lambda,T^{\epsilon})$ were known under a bilinear map assumption, and with proofs of size $\mathsf{poly}(\lambda,\log T)$ were only known under non-standard knowledge assumptions or in the random oracle model.

Leakage resilient secret sharing (LRSS) allows a dealer to share a secret amongst $n$ parties such that any authorized subset of the parties can recover the secret from their shares, while an adversary that obtains shares of any unauthorized subset of parties along with bounded leakage from the other shares learns no information about the secret. Non-malleable secret sharing (NMSS) provides a guarantee that even shares that are tampered by an adversary will reconstruct to either the original message or something independent of it. The most important parameter of LRSS and NMSS schemes is the size of each share. For LRSS, in the "local leakage model" (i.e., when the leakage functions on each share are independent of each other and bounded), Srinivasan and Vasudevan (CRYPTO 2019), gave a scheme for threshold access structures with a share size of approximately ($3$.(message length) + $\mu$), where $\mu$ is the number of bits of leakage tolerated from every share. For the case of NMSS, the best known result (again due to the above work) has a share size of ($11$.(message length)). In this work, we build LRSS and NMSS schemes with much improved share sizes. Additionally, our LRSS scheme obtains optimal share and leakage size. In particular, we get the following results: -We build an information-theoretic LRSS scheme for threshold access structures with a share size of ((message length) + $\mu$). -As an application of the above result, we obtain an NMSS with a share size of ($4$.(message length)). Further, for the special case of sharing random messages, we obtain a share size of ($2$.(message length)).

Data privacy concerns are increasing significantly in the context of Internet of Things, cloud services, edge computing, artificial intelligence applications, and other applications enabled by next generation networks. Homomorphic Encryption addresses privacy challenges by enabling multiple operations to be performed on encrypted messages without decryption. This paper comprehensively addresses homomorphic encryption from both theoretical and practical perspectives. The paper delves into the mathematical foundations required to understand fully homomorphic encryption (FHE). It consequently covers design fundamentals and security properties of FHE and describes the main FHE schemes based on various mathematical problems. On a more practical level, the paper presents a view on privacy-preserving Machine Learning using homomorphic encryption, then surveys FHE at length from an engineering angle, covering the potential application of FHE in fog computing, and cloud computing services. It also provides a comprehensive analysis of existing state-of-the-art FHE libraries and tools, implemented in software and hardware, and the performance thereof.

A fully homomorphic encryption (FHE) scheme allows a client to encrypt and delegate its data to a server that performs computation on the encrypted data that the client can then decrypt. While FHE gives confidentiality to clients' data, it does not protect the server's input and computation. Nevertheless, FHE schemes are still helpful in building delegation protocols that reduce communication complexity, as FHE ciphertext's size is independent of the size of the computation performed on them. We can further extend FHE by a property called circuit privacy, which guarantees that the result of computing on ciphertexts reveals no information on the computed function and the inputs of the server. Thereby, circuit private FHE gives rise to round optimal and communication efficient secure two-party computation protocols. Unfortunately, despite significant efforts and much work put into the efficiency and practical implementations of FHE schemes, very little has been done to provide useful and practical FHE supporting circuit privacy. In this work, we address this gap and design the first randomized bootstrapping algorithm whose single invocation sanitizes a ciphertext and, consequently, serves as a tool to provide circuit privacy. We give an extensive analysis, propose parameters, and provide a C++ implementation of our scheme. Our bootstrapping can sanitize a ciphertext to achieve circuit privacy at an 80-bit statistical security level in 1.4 seconds. In addition, we can perform non-sanitized bootstrapping in around 0.14 seconds on a laptop without additional public keys. Crucially, we do not need to increase the parameters significantly to perform computation before or after the sanitization takes place. For comparison's sake, we revisit the Ducas-Stehl\'e washing machine method. In particular, we give a tight analysis, estimate efficiency, review old and provide new parameters.

Publish-subscribe protocols enable real-time multi-point-to-multi-point communications for many dispersed computing systems like Internet of Things (IoT) applications. Recent interest has focused on adding processing to such publish-subscribe protocols to enable computation over real-time streams such that the protocols can provide functionalities such as sensor fusion, compression, and other statistical analysis on raw sensor data. However, unlike pure publish-subscribe protocols, which can be easily deployed with end-to-end transport layer encryption, it is challenging to ensure security in such publish-process-subscribe protocols when the processing is carried out on an untrusted third party. In this work, we present XYZ, a secure publish-process-subscribe system that can preserve the confidentiality of computations and support multi-publisher-multi-subscriber settings. Within XYZ, we design two distinct schemes: the first using Yao's garbled circuits (the GC-Based Scheme) and the second using homomorphic encryption with proxy re-encryption (the Proxy-HE Scheme). We build implementations of the two schemes as an integrated publish-process-subscribe system. We evaluate our system on several functions and also demonstrate real-world applications. The evaluation shows that the GC-Based Scheme can finish most tasks two orders of magnitude times faster than the Proxy-HE Scheme while Proxy-HE can still securely complete tasks within an acceptable time for most functions but with a different security assumption and a simpler system structure.

There are many recent results on reverse-engineering (potentially hidden) structure in cryptographic S-boxes. The problem of recovering structure in the other main building block of symmetric cryptographic primitives, namely, the linear layer, has not been paid that much attention so far. To fill this gap, in this work, we develop a systematic approach to decomposing structure in the linear layer of a substitution-permutation network (SPN), covering the case in which the specification of the linear layer is obfuscated from applying secret linear transformations to the S-boxes. We first present algorithms to decide whether an $ms \times ms$ matrix with entries in a prime field $\mathbb{F}_p$ can be represented as an $m \times m$ matrix over the extension field $\mathbb{F}_{p^s}$. We then study the case of recovering structure in MDS matrices by investigating whether a given MDS matrix follows a Cauchy construction. As an application, for the first time, we show that the $8 \times 8$ MDS matrix over $\mathbb{F}_{2^8}$ used in the hash function Streebog is a Cauchy matrix.

The advent of quantum computers brought a large interest in post-quantum cryptography and in the migration to quantum-resistant systems. Protocols for Self-Sovereign Identity (SSI) are among the fundamental scenarios touched by this need. The core concept of SSI is to move the control of digital identity from third-party identity providers directly to individuals. This is achieved through Verificable Credentials (VCs) supporting anonymity and selective disclosure. In turn, the implementation of VCs requires cryptographic signature schemes compatible with a proper Zero-Knowledge Proof (ZKP) framework. We describe the two main ZKP VCs schemes based on classical cryptographic assumptions, that is, the signature scheme with efficient protocols of Camenisch and Lysyanskaya, which is based on the strong RSA assumption, and the BBS+ scheme of Boneh, Boyen and Shacham, which is based on the strong Diffie-Hellman assumption. Since these schemes are not quantum-resistant, we select as one of the possible post-quantum alternatives a lattice-based scheme proposed by Jeudy, Roux-Langlois, and Sander, and we try to identify the open problems for achieving VCs suitable for selective disclosure, non-interactive renewal mechanisms, and efficient revocation.

This note describes two pairing-friendly curves that embed ed25519, of different bit security levels. Our search is not novel; it follows the standard recipe of the Cocks-Pinch method. We implemented these two curves on arkworks-rs. This note is intended to document how the parameters are being generated and how to implement these curves in arkworks-rs 0.4.0, for further reference. We name the two curves as Yafa-108 and Yafa-146: - Yafa-108 is estimated to offer 108-bit security, which we parameterized to match the 103-bit security of BN254 - Yafa-146 is estimated to offer 146-bit security, which we parameterized to match the 132-bit security of BLS12-446 or 123-bit security of BLS12-381 We use these curves as an example to demonstrate two things: - The "elastic" zero-knowledge proof, Gemini (EUROCRYPT '22), is more than being elastic, but it is more curve-agnostic and hardware-friendly. - The cost of nonnative field arithmetics can be drastic, and the needs of application-specific curves may be inherent. This result serves as evidence of the necessity of EIP-1962, and the insufficiency of EIP-2537.

Shuffling is a well-known countermeasure against side-channel analysis. It typically uses the Fisher-Yates (FY) algorithm to generate a random permutation which is then utilized as the loop iterator to index the processing of the variables inside the loop. The processing order is scrambled as a result, making side-channel analysis more difficult. Recently, a side-channel attack on a masked and shuffled implementation of Saber requiring 61,680 power traces to extract the secret key was reported. In this paper, we present an attack that can recover the secret key of Saber from 4,608 traces. The key idea behind the 13-fold improvement is to recover FY indexes directly, rather than by extracting the message Hamming weight and bit flipping, as in the previous attack. We capture a power trace during the execution of the decapsulation algorithm for a given ciphertext, recover FY indexes 0 and 255, and extract the corresponding two message bits. Then, we modify the ciphertext to cyclically rotate the message, capture a power trace, and extract the next two message bits with FY indexes 0 and 255. In this way, all message bits can be extracted. By recovering messages contained in k ∗ l chosen ciphertexts constructed using a new method based on error-correcting codes with length l, where k is the security level, we recover the long term secret key. To demonstrate the generality of the presented approach, we also recover the secret key from a masked and shuffled implementation of CRYSTALS-Kyber, which NIST recently selected as a new public-key encryption and key-establishment algorithm to be standardized.

Modern attestation based on Trusted Execution Environments (TEEs) can significantly reduce the risk of secret compromise by attackers, while allowing users to authenticate across various services. However, this has also made TEEs a high-value attack target, driving an arms race between novel compromise attacks and continuous TEEs updates. Ideally, we would like to ensure that we achieve Post-Compromise Security (PCS): even after a compromise, we can update the TEE into a secure state. However, at the same time, we would like the privacy of users to be respected, preventing providers (such as Intel, Google, or Samsung) or services from tracking users. In this work, we develop TokenWeaver, the first privacy-preserving post-compromise secure attestation method with automated formal proofs for its core properties. We base our construction on weaving together two types of token chains, one of which is linkable and the other is unlinkable. We provide the full formal models, including protocol, security properties, and proofs for reproducibility, as well as a proof-of-concept implementation in python that shows the simplicity and applicability of our solution.

We introduce the first candidate lattice-based Designated Verifier (DV) ZK-SNARK protocol with \emph{quasi-optimal proof length} (quasi-linear in the security/privacy parameter), avoiding the use of the exponential smudging technique. Our ZK-SNARK also achieves significant improvements in proof length in practice, with proofs length below $6$ KB for 128-bit security/privacy level. Our main technical result is a new regularity theorem for `private' re-randomization of Module LWE (MLWE) samples using discrete Gaussian randomization vectors, also known as a lattice-based leftover hash lemma with leakage, which applies with a discrete Gaussian re-randomization parameter that is polynomial in the statistical privacy parameter. To obtain this result, we obtain bounds on the smoothing parameter of an intersection of a random $q$-ary SIS module lattice, Gadget SIS module lattice, and Gaussian orthogonal module lattice over standard power of 2 cyclotomic rings, and a bound on the minimum of module gadget lattices. We then introduce a new candidate \emph{linear-only} homomorphic encryption scheme called Module Half-GSW (HGSW), which is a variant of the GSW somewhat homomorphic encryption scheme over modules, and apply our regularity theorem to provide smudging-free circuit-private homomorphic linear operations for Module HGSW.

Transport Layer Security (TLS) constitutes one of the most widely used protocols for securing Internet communications and has also found broad acceptance in the Internet of Things (IoT) domain. As we progress toward a security environment resistant to quantum computer attacks, TLS needs to be transformed to support post-quantum cryptography. However, post-quantum TLS is still not standardised, and its overall performance, especially in resource-constrained, IoT-capable, embedded devices, is not well understood. In this paper, we showcase how TLS 1.3 can be transformed into quantum-safe by modifying the TLS 1.3 architecture in order to accommodate the latest Post-Quantum Cryptography (PQC) algorithms from NIST PQC process. Furthermore, we evaluate the execution time, memory, and bandwidth requirements of this proposed post-quantum variant of TLS 1.3 (PQ TLS 1.3). This is facilitated by integrating the pqm4 and PQClean library implementations of almost all PQC algorithms selected for standardisation by the NIST PQC process, as well as the alternatives to be evaluated in a new round (Round 4). The proposed solution and evaluation focuses on the lower end of resource-constrained embedded devices. Thus, the evaluation is performed on the ARM Cortex-M4 embedded platform NUCLEO-F439ZI that provides $180$ MHz clock rate, $2$ MB Flash Memory, and $256$ KB SRAM. To the authors' knowledge, this is the first systematic, thorough, and complete timing, memory usage, and network traffic evaluation of PQ TLS 1.3 for all the NIST PQC process selections and upcoming candidate algorithms, that explicitly targets resource-constrained embedded systems.

Blockchain technology provides efficient and secure solutions to various online activities by utilizing a wide range of cryptographic tools. In this paper, we survey the existing literature on post-quantum secure digital signatures that possess exotic advanced features and which are crucial cryptographic tools used in the blockchain ecosystem for (i) account management, (ii) consensus efficiency, (iii) empowering scriptless blockchain, and (iv) privacy. The exotic signatures that we particularly focus on in this work are the following: multi-/aggregate, threshold, adaptor, blind and ring signatures. Herein the term exotic refers to signatures with properties which are not just beyond the norm for signatures e.g. unforgeability, but also imbue new forms of functionalities. Our treatment of such exotic signatures includes discussions on existing challenges and future research directions in the post-quantum space. We hope that this article will help to foster further research to make post-quantum cryptography more accessible so that blockchain systems can be made ready in advance of the approaching quantum threats.

Achieving adaptive (or proactive) security in cryptographic protocols is notoriously difficult due to the adversary's power to dynamically corrupt parties as the execution progresses. Inspired by the work of Benhamouda et al. in TCC 2020, Gentry et al. in CRYPTO 2021 introduced the YOSO (You Only Speak Once) model for constructing adaptively (or proactively) secure protocols in massively distributed settings (e.g. blockchains). In this model, instead of having all parties execute an entire protocol, smaller anonymous committees are randomly chosen to execute each individual round of the protocol. After playing their role, parties encrypt protocol messages towards the the next anonymous committee and erase their internal state before publishing their ciphertexts. However, a big challenge remains in realizing YOSO protocols: efficiently encrypting messages towards anonymous parties selected at random without learning their identities, while proving the encrypted messages are valid w.r.t. the protocol. In particular, the protocols of Benhamouda et al. and of Gentry et al. require showing ciphertexts contain valid shares of secret states. We propose concretely efficient methods for encrypting a protocol's secret state towards a random anonymous committee. We start by proposing a very simple and efficient scheme for encrypting messages towards randomly and anonymously selected parties. We then show constructions of publicly verifiable secret (re-)sharing (PVSS) schemes with concretely efficient proofs of (re-)share validity that can be generically instantiated from encryption schemes with certain linear homomorphic properties. Finally, we show that our PVSS schemes can be efficiently realized from our encyption scheme.

We propose a novel privacy-preserving, two-party computation of various distance metrics (e.g., Hamming distance, Scalar Product) followed by a comparison with a fixed threshold, which is known as one of the most useful and popular building blocks for many different applications including machine learning, biometric matching, etc. Our solution builds upon recent advances in functional secret sharing and makes use of an optimized version of arithmetic secret sharing. Thanks to this combination, our new solution named Funshade is the first to require only one round of communication and two ring elements of communication in the online phase, outperforming all prior state-of-the-art schemes while relying on lightweight cryptographic primitives. Lastly, we implement the solution from scratch in Python using efficient C++ blocks, testifying its high performance.

Various matrix relations widely appeared in data-intensive computations, as a result their zero-knowledge proofs/arguments (ZKP/ZKA) are naturally required in large-scale private computing applications. In the first part of this paper, we concretely establish efficient zero-knowledge arguments for linear matrix relation AU = B and bilinear relation UQV = Y over the residue ring Zm with logarithmic message complexity. We take a direct, matrix-oriented (rather than vector-oriented in usual) approach to such establishments on basis of the elegant commitment scheme over the ring recently established by Attema et al[16]. The constructed protocols are public coin and in c.r.s paradigm (c.r.s used only as the public-key of the commitment scheme), suitable for any size matrices and outperform the protocols constructed in usual approach when number of columns > log(number of rows) with significantly smaller c.r.s., fewer rounds and lower message complexity, particularly for large-size squares. The on-line computational complexity is almost the same for both approaches. In the second part, on basis of the simulation-sound tag-based trapdoor commitment schemes we establish a general compiler to transform any public coin proof/argument protocol into the one which is concurrently non-malleable with unchanged number of rounds, properly increased message and computational complexity. Such enhanced protocols, e.g., the versions compiled from those constructed in the first part of this work, can run in parallel environment while keeping all their security properties, particularly resisting man-in-the-middle attacks.

Lyubashevsky’s signatures are based on the Fiat-Shamir with aborts paradigm, whose central ingredient is the use of rejection sampling to transform secret-dependent signature samples into samples from (or close to) a secret-independent target distribution. Several choices for the underlying distributions and for the rejection sampling strategy can be considered. In this work, we study Lyubashevsky’s signatures through the lens of rejection sampling, and aim to minimize signature size given signing runtime requirements. Several of our results concern rejection sampling itself and could have other applications. We prove lower bounds for compactness of signatures given signing run- time requirements, and for expected runtime of perfect rejection sampling strategies. We also propose a Rényi-divergence-based analysis of Lyuba- shevsky’s signatures which allows for larger deviations from the target distribution, and show hyperball uniforms to be a good choice of distri- butions: they asymptotically reach our compactness lower bounds and offer interesting features for practical deployment. Finally, we propose a different rejection sampling strategy which circumvents the expected runtime lower bound and provides a worst-case runtime guarantee.

During the last decades there has been an increasing interest in Elliptic curve cryptography (ECC) and, especially, the Elliptic Curve Digital Signature Algorithm (ECDSA) in practice. The rather recent developments of emergent technologies, such as blockchain and the Internet of Things (IoT), have motivated researchers and developers to construct new cryptographic hardware accelerators for ECDSA. Different types of optimizations (either platform dependent or algorithmic) were presented in the literature. In this context, we turn our attention to ECC and propose a new method for generating ECDSA moduli with a predetermined portion that allows one to double the speed of Barrett's algorithm. Moreover, we take advantage of the advancements in the Artificial Intelligence (AI) field and bring forward an AI-based approach that enhances Schoof's algorithm for finding the number of points on an elliptic curve in terms of implementation efficiency. Our results represent algorithmic speed-ups exceeding the current paradigm as we are also preoccupied by other particular security environments meeting the needs of governmental organizations.

Private information retrieval (PIR) is a cryptographic protocol that enables a wide range of privacy-preserving applications. Despite being extensively studied for decades, it is still not efficient enough to be used in practice. In this paper, we propose a novel PIR protocol named PIRANA, based on the recent advances in constant-weight codes. It is upto 188.6$\times$ faster than the original constant-weight PIR (presented in Usenix SEC '22). Most importantly, PIRANA naturally supports multi-query. It allows a client to retrieve a batch of elements from the server with a very small extra-cost in both communication and computation, compared to retrieving a single element. To retrieve 2730 elements, the amortized cost for retrieving a single element is only 3.9ms in runtime and 3.0KB in bandwidth. We also discuss a way to extend PIRANA to labeled private set intersection (LPSI). Compared to existing LPSI protocols, PIRANA is more friendly to the scenarios where the database updates frequently.

The paper concerns several theoretical aspects of oriented supersingular $\ell$-isogeny volcanoes and their relationship to closed walks in the supersingular $\ell$-isogeny graph. Our main result is a bijection between the rims of the union of all oriented supersingular $\ell$-isogeny volcanoes over $\overline{\mathbb{F}}_p$ (up to conjugation of the orientations), and isogeny cycles (non-backtracking closed walks which are not powers of smaller walks) of the supersingular $\ell$-isogeny graph over $\overline{\mathbb{F}}_p$. The exact proof and statement of this bijection are made more intricate by special behaviours arising from extra automorphisms and the ramification of $p$ in certain quadratic orders. We use the bijection to count isogeny cycles of given length in the supersingular $\ell$-isogeny graph exactly as a sum of class numbers of these orders, and also give an explicit upper bound by estimating the class numbers.

Adaptor signatures have seen wide applications in layer-2 and peer-to-peer blockchain ap- plications such as atomic swaps and payment channels. We first identify two shortcomings of previous literature on adaptor signatures. (1) Current aim of “script-less” adaptor signatures restricts instantiability, limiting designs based on BLS or current NIST PQC candidates. (2) We identify gaps in current formulations of security. In particular, we show that current notions do not rule out a class of insecure schemes. Moreover, a natural property concerning the on-chain unlinkability of adaptor signatures has not been formalized. We then address these shortcomings by providing new and stronger security notions, as well as new generic constructions from any signature scheme and hard relation. On definitions: 1. We develop security notions that strictly imply previous notions. 2. We formalize the notion of unlinkability for adaptor signatures. 3. We give modular proof frameworks that facilitate simpler proofs. On constructions: 1. We give a generic construction of adaptor signature from any signature scheme and any hard relation, showing that theoretically, (linkable) adaptor signatures can be constructed from any one-way function. 2. We also give an unlinkable adaptor signature construction from any signature scheme and any strongly random-self reducible relation, which we show instantiations of using DL, RSA, and LWE.

Biometric data are uniquely suited for connecting individuals to their digital identities. Deriving cryptographic key exchange from successful biometric authentication therefore gives an additional layer of trust compared to password-authenticated key exchange. However, biometric data differ from passwords in two crucial points: firstly, they are sensitive personal data that need to be protected on a long-term basis. Secondly, efficient feature extraction and comparison components resulting in high intra-subject tolerance and inter-subject distinguishability, documented with good biometric performance, need to be applied in order to prevent zero-effort impersonation attacks. In this work, we present a protocol for biometric resilient authenticated key exchange that fulfils the above requirements of biometric information protection compliant with ISO/IEC 24745. The protocol is based on established improved fuzzy vault schemes and validated with good recognition performance. We build our protocol from trusted primitives for password-authenticated key exchange using oblivious pseudo-random functions. Our protocol is independent of the biometric modality and can be implemented based on the security of discrete logarithms as well as lattices. We provide an open-source implementation of our protocol instantiated with elliptic curves and a state-of-the art unlinkable fingerprint fuzzy vault scheme which achieves real-time efficiency with transaction times of less than one second from the image capture to the completed key exchange.

E-voting offers significant potential savings in time and money compared to current voting systems. Unfortunately, many current e-voting schemes are susceptible to quantum attacks. In this paper, we expand upon EVOLVE, an existing lattice-based quantum-secure election scheme introduced by Pino et al. We are able to make these expansions by extending the dimensions of the voter's ballot and creating additional proofs, allowing for applicability to realistic election schemes. Thus, we present our system of schemes, called EVOLVED (Electronic Voting from Lattices with Verification and Extended Dimensions). We present schemes for numerous different types of elections including Single-Choice Voting, Borda Count, and Instant Runoff.

Today, authentication faces the trade-off of security versus usability. Two factor authentication, for example, is one way to improve security at the cost of requiring user interaction for every round of authentication. Most 2FA methods are bound to user's phone and fail if the phone is not available. We propose CoRA, a Collaborative Risk-aware Authentication method that takes advantage of any and many devices that the user owns. CoRA increases security, and preserves usability and privacy by using threshold MACs and by tapping into the knowledge of the devices instead of requiring user knowledge or interaction. Using CoRA, authentication tokens are generated collaboratively by multiple devices owned by the user, and the token is accompanied by a risk factor that indicates the reliability of the token to the authentication server. CoRA relies on a device-centric trust assessment to determine the relative risk factor and on threshold cryptography to ensure no single point of failure. CoRA does not assume any secure element or physical security for the devices. In this paper, we present the architecture and security analysis of CoRA. In an associated user study we discover that 78% of users have at least three devices with them at most times, and 93% have at least two, suggesting that deploying CoRA multi-factor authentication is practical today.

Recent works of Roughgarden (EC'21) and Chung and Shi (SODA'23) initiate the study of a new decentralized mechanism design problem called transaction fee mechanism design (TFM). Unlike the classical mechanism design literature, in the decentralized environment, even the auctioneer (i.e., the miner) can be a strategic player, and it can even collude with a subset of the users facilitated by binding side contracts. Chung and Shi showed two main impossibility results that rule out the existence of a dream TFM. First, any TFM that provides incentive compatibility for individual users and miner-user coalitions must always have zero miner revenue, no matter whether the block size is finite or infinite. Second, assuming finite block size, no non-trivial TFM can simultaenously provide incentive compatibility for any individual user, and for any miner-user coalition. In this work, we explore what new models and meaningful relaxations can allow us to circumvent the impossibility results of Chung and Shi. Besides today’s model that does not employ cryptography, we introduce a new MPC-assisted model where the TFM is implemented by a joint multi-party computation (MPC) protocol among the miners. We prove several feasibility and infeasibility results for achieving strict and approximate incentive compatibility, respectively, in the plain model as well as the MPC-assisted model. We show that while cryptography is not a panacea, it indeed allows us to overcome some impossibility results pertaining to the plain model, leading to non-trivial mechanisms with useful guarantees that are otherwise impossible in the plain model. Our work is also the first to characterize the mathematical landscape of transaction fee mechanism design under approximate incentive compatibility, as well as in a cryptography-assisted model.

In [1], a novel cryptographic key exchange technique was proposed using the plactic monoid, based on the apparent difficulty of solving division problems in that monoid. Specifically, given elements c, b in the plactic monoid, the problem is to find q for which qb = c, given that such a q exists. In this paper, we introduce a metric on the plactic monoid and use it to give a probabilistic algorithm for solving that problem which is fast for parameter values in the range of interest.

We introduce puncturable key wrapping (PKW), a new cryptographic primitive that supports fine-grained forward security properties in symmetric key hierarchies. We develop syntax and security definitions, along with provably secure constructions for PKW from simpler components (AEAD schemes and puncturable PRFs). We show how PKW can be applied in two distinct scenarios. First, we show how to use PKW to achieve forward security for TLS 1.3 0-RTT session resumption, even when the server's long-term key for generating session tickets gets compromised. This extends and corrects a recent work of Aviram, Gellert, and Jager (Journal of Cryptology, 2021). Second, we show how to use PKW to build a protected file storage system with file shredding, wherein a client can outsource encrypted files to a potentially malicious or corrupted cloud server whilst achieving strong forward-security guarantees, relying only on local key updates.

In this paper we study linearization proposed on ePrint 2021/583, that's addressed to entropic quasigroups cryptography. We show how this attack can be avoided and actually linearization can be used to build valid cryptosystems.

This paper continues previous ones about compression of points on elliptic curves $E_b\!: y^2 = x^3 + b$ (with $j$-invariant $0$) over a finite field $\mathbb{F}_{\!q}$ of characteristic $p > 3$. More precisely, we will show in detail how any two (resp. three) points from $E_b(\mathbb{F}_{\!q})$ can be quickly compressed to two (resp. three) elements of $\mathbb{F}_{\!q}$ (apart from a few auxiliary bits) in such a way that the corresponding decompression stage requires to extract only one cubic (resp. sextic) root in $\mathbb{F}_{\!q}$ (with several multiplications and without inversions). As a result, for many $q$ occurring in practice the new compression-decompression methods are more efficient than the classical one with the two (resp. three) $x$ or $y$ coordinates of the points, which extracts two (resp. three) roots in $\mathbb{F}_{\!q}$. It will be explained why the new methods are useful in the context of modern real-world pairing-based protocols such as Groth16. As a by-product, when $q \equiv 2 \ (\mathrm{mod} \ 3)$ (in particular, $E_b$ is supersingular), we will obtain a two-dimensional analogue of Boneh--Franklin's encoding, that is a way to sample two ``independent'' $\mathbb{F}_{\!q}$-points on $E_b$ at the cost of one cubic root in $\mathbb{F}_{\!q}$. Finally, the case of four and more points from $E_b(\mathbb{F}_{\!q})$ will be commented on.

Dynamic-committee proactive secret sharing (DPSS) enables the update of secret shares and the alternation of shareholders without changing the secret. Such a proactivization functionality makes DPSS a promising technology for long-term key management and committee governance. Although non-asynchronous DPSS schemes have achieved cubic communication cost w.r.t. the number of shareholders, the overhead of asynchronous DPSS remains exponential. In this paper, we fill this gap and propose DyCAPS, an efficient asynchronous DPSS scheme with a cubic communication cost. DyCAPS can be efficiently integrated into asynchronous BFT protocols without increasing the overall asymptotic communication cost. Experimental results show that given a payload of 15 MB per party, DyCAPS achieves member change in Dumbo2 (CCS 2020) at the cost of 5%–22% throughput degradation, when the committee size varies from 4 to 22.

In this work, we present a systematic study of Side-Channel Attacks (SCA) and Fault Injection Attacks (FIA) on structured lattice-based schemes, with a focus on Kyber Key Encapsulation Mechanism (KEM) and Dilithium signature scheme, which are leading candidates in the NIST standardization process for Post-Quantum Cryptography (PQC). Through our study, we attempt to understand the underlying similarities and differences between the existing attacks, while classifying them into different categories. Given the wide variety of reported attacks, simultaneous protection against all the attacks requires to implement customized protections/countermeasures for both Kyber and Dilithium. We therefore present a range of customized countermeasures, capable of providing defenses/mitigations against existing SCA/FIA, and incorporate several SCA and FIA countermeasures within a single design of Kyber and Dilithium. Among the several countermeasures discussed in this work, we present novel countermeasures that offer simultaneous protection against several SCA and FIA-based chosen-ciphertext attacks for Kyber KEM. We implement the presented countermeasures within the well-known pqm4 library for the ARM Cortex-M4 based microcontroller. Our performance evaluation reveals that the presented custom countermeasures incur reasonable performance overheads, on the ARM Cortex-M4 microcontroller. We therefore believe our work argues for the usage of custom countermeasures within real-world implementations of lattice-based schemes, either in a standalone manner or as reinforcements to generic countermeasures such as masking.

The $q$-Strong Diffie-Hellman ($q$-SDH) parameters are foundational to efficient constructions of many cryptographic primitives such as zero-knowledge succinct non-interactive argument of knowledge, polynomial/vector commitments, verifiable secret sharing, and randomness beacon. The only existing method to generate these parameters securely is highly sequential, requires strong network synchrony assumptions, and has very high communication and computation cost. For example, to generate parameters for any given $q$, each party incurs a communication cost of $\Omega(nq)$ and requires $\Omega(n)$ rounds. Here $n$ is the number of parties in the secure multiparty computation protocol. Since $q$ is typically large, i.e., on the order of billions, the cost is highly prohibitive. In this paper, we present Tauron, a distributed protocol to generate $q$-SDH parameters in an asynchronous network. In a network of $n$ parties, Tauron tolerates up to one-third of malicious parties. Each party incurs a communication cost of $O(q + n^2\log q)$ and the protocol finishes in $O(\log q + \log n)$ expected rounds. We provide a rigorous security analysis of our protocol. We implement Tauron and evaluate it with up to 128 geographically distributed parties. Our evaluation illustrates that Tauron is highly scalable and results in a 2-6$\times$ better runtime and 4-13$\times$ better per-party bandwidth usage.

Authentication is the first, crucial step in securing digital assets like cryptocurrencies and online services like banking and social networks. It relies on principals maintaining exclusive access to credentials like cryptographic signing keys, passwords, and physical devices. But both individuals and organizations struggle to manage their credentials, resulting in loss of assets and identity theft. Multi-factor authentication improves security, but its analysis and design are mostly limited to one-shot mechanisms, which decide immediately. In this work, we study mechanisms with back-and-forth interaction with the principals. For example, a user receives an email notification about sending money from her bank account and is given a period of time to abort the operation. We formally define the authentication problem, where an authentication mechanism interacts with a user and an attacker and tries to identify the user. A mechanism's success depends on the scenario~-- whether the user / attacker know the different credentials; each credential can be safe, lost, leaked, or stolen. The profile of a mechanism is the set of all scenarios in which it succeeds. Thus, we have a partial order on mechanisms, defined by the subset relation on their profiles. We find an upper bound on the profile size and discover three types of $n$-credential mechanisms (for any $n$) that are maximally secure, meeting this bound. We show these are all the unique maximal mechanisms for $n \le 3$. We show the efficacy of our model by analyzing existing mechanisms, both theoretical and deployed in widely-used systems, and make concrete improvement proposals. We demonstrate the practicality of our mechanisms by implementing a maximally-secure cryptocurrency wallet.

For both cloud and client applications, the protection of the confidentiality and integrity of remotely processed information is an increasingly common feature request. It is also a very challenging goal to achieve with reasonable costs in terms of memory overhead and performance penalty. In turn, this usually leads to security posture compromises. In this paper we review the main technologies that have been proposed so far to address this problem, as well as some new techniques and combinations thereof. We systematise the treatment of the protection of data in use by starting with models of the adversaries, thus allowing us to define different, yet consistent protection levels. Several different schemes for memory protection are benchmarked for each protection level. We evaluate storage and performance impacts when the benchmarks are the only running tasks and when simulating a server under load. To make just one example of our results: Using advanced techniques to compress counters can make it viable to store them on-chip -- for instance by adding on-chip DRAM that can be as small as to 1/256th of the off-chip memory. This allows for implementations of memory protection providing full confidentiality, integrity and anti-replay protection with hitherto unattained penalties, especially in combination with the repurposing of ECC bits to store integrity tags. The performance penalty on a server with a saturated memory subsystem can thus be contained under 2% with a memory overhead of 1/256 and even under 1% with a memory overhead of 1/128.

Post-quantum Cryptography (PQC) has reached the verge of standardization competition, with Kyber as a winning candidate. In this work, we demonstrate practical backdoor insertion in Kyber through kleptrography. The backdoor can be inserted using classical techniques like ECDH or post-quantum Classic Mceliece. The inserted backdoor targets the key generation procedure where generated output public keys subliminally leak information about the secret key to the owner of the backdoor. We demonstrate first practical instantiations of such attack at the protocol level by validating it on TLS 1.3.

In our survey of the various zk-EVM constructions, it becomes apparent that verifiable storage of the EVM state starts to be one of the dominating costs. This is not surprising because a big differentiator of EVM from UTXO is exactly the ability to carry states and, most importantly, their transitions; i.e., EVM is a **state** machine. In other words, to build an efficient zk-EVM, one must first build an efficient verifiable state. The common approach, which has been used in production, is a Merkle forest to authenticate the memory that would be randomly accessed within zk-SNARK, and optimize the verification of such memory accesses. In this note, we describe a way to instantiate a Merkle tree with very few gates in TurboPlonk. We use customized gates in TurboPlonk to implement a SNARK-friendly hash function called Anemoi and its Jive mode of operation, by Clémence Bouvier, Pierre Briaud, Pyrros Chaidos, Léo Perrin, Robin Salen, Vesselin Velichkov, and Danny Willems. We demonstrate that with $14$ gates ($\approx1$ gate per round in a 12-round Amenoi hash), one can verify a 3-to-1 compression in a 3-ary Merkle tree. Before this, prior implementations would often require hundreds of gates. We anticipate this technique to benefit a large number of applications built off zk-SNARK. Our implementation can be found in $\mathtt{noah}$, a library for modern privacy tokens: https://github.com/FindoraNetwork/noah

In "Optimal collision side-channel attacks" (https://eprint.iacr.org/2019/828) we studied, and derived an optimal distinguisher for key ranking. In this note we propose a heuristic estimation procedure for key ranking based on this distinguisher, and provide estimates of lower bounds for secret key ranks in collision side channel attacks.

The UK government is considering advanced primitives such as identity-based encryption (IBE) for adoption as they transition their public-safety communications network from TETRA to an LTE-based service. However, the current LTE standard relies on elliptic-curve-based IBE, which will be vulnerable to quantum computing attacks, expected within the next 20--30 years. Lattices can provide quantum-safe alternatives for IBE. These schemes have shown promising results in terms of practicality. To date, several IBE schemes over lattices have been proposed, but there has been little in the way of practical evaluation. This paper provides the first complete optimised practical implementation and benchmarking of Latte, a promising Hierarchical IBE scheme proposed by the United Kingdom (UK) National Cyber Security Centre (NCSC) in 2017 and endorsed by European Telecommunications Standards Institute (ETSI). We propose optimisations for the KeyGen, Delegate, Extract and Gaussian sampling components of Latte, to increas attack costs, reduce decryption key lengths by 2x--3x, ciphertext sizes by up to 33%, and improve speed. In addition, we conduct a precision analysis, bounding the Rényi divergence of the Gaussian sampling procedures from the ideal distribution in corroboration of our claimed security levels. Our resulting implementation of the Delegate function takes 0.4 seconds at 80-bit security level on a desktop machine at 4.2GHz, significantly faster than the order of minutes estimated in the ETSI technical report. Furthermore, our optimised Latte Encrypt/Decrypt implementation reaches speeds up to 9.7x faster than the ETSI implementation.

Romulus-H is a hash function that currently competes as a finalist in the NIST Lightweight Cryptography competition. It is based on the Hirose DBL construction which is provably secure when used with an ideal block cipher. However, in practice, ideal block ciphers can only be approximated. The security of concrete instantiations must be cryptanalyzed carefully; the security margin may be higher or lower than in the secret-key setting. So far, the Hirose DBL construction has been studied with only a few other block ciphers, like IDEA and AES. However, Romulus-H uses Hirose DBL with the SKINNY block cipher where only very little analysis has been published so far. In this work, we present the first practical analysis of Romulus-H. We propose a new framework for finding collisions in hash functions based on the Hirose DBL construction. This is in contrast to previous work that only focused on free-start collisions. Our framework is based on the idea of joint differential characteristics which capture the relationship between the two block cipher calls in the Hirose DBL construction. To identify good joint differential characteristics, we propose a combination of a MILP and CP model. Then, we use these characteristics in another CP model to find collisions. Finally, we apply this framework to Romulus-H and find practical collisions of the hash function for 10 out of 40 rounds and practical semi-free-start collisions up to 14 rounds.

Authenticated encryption with associated data (AEAD) forms the core of much of symmetric cryptography, yet the standard techniques for modeling AEAD assume recipients have no ambiguity about what secret key to use for decryption. This is divorced from what occurs in practice, such as in key management services, where a message recipient can store numerous keys and must identify the correct key before decrypting. To date there has been no formal investigation of their security properties or efficacy, and the ad hoc solutions for identifying the intended key deployed in practice can be inefficient and, in some cases, vulnerable to practical attacks. We provide the first formalization of nonce-based AEAD that supports key identification (AEAD-KI). Decryption now takes in a vector of secret keys and a ciphertext and must both identify the correct secret key and decrypt the ciphertext. We provide new formal security definitions, including new key robustness definitions and indistinguishability security notions. Finally, we show several different approaches for AEAD-KI and prove their security.

{We investigate the problem of recovering integer inputs (up to an affine scaling) when given only the integer monotonic polynomial outputs. Given $n$ integer outputs of a degree-$d$ integer monotonic polynomial whose coefficients and inputs are integers within known bounds and $n \gg d$, we give an algorithm to recover the polynomial and the integer inputs (up to an affine scaling). A heuristic expected time complexity analysis of our method shows that it is exponential in the size of the degree of the polynomial but polynomial in the size of the polynomial coefficients. We conduct experiments with real-world data as well as randomly chosen parameters and demonstrate the effectiveness of our algorithm over a wide range of parameters. Using only the polynomial evaluations at specific integer points, the apparent hardness of recovering the input data served as the basis of security of a recent protocol proposed by Kesarwani et al. for secure $k$-nearest neighbour computation on encrypted data that involved secure sorting. The protocol uses the outputs of randomly chosen monotonic integer polynomial to hide its inputs except to only reveal the ordering of input data. Using our integer polynomial recovery algorithm, we show that we can recover the polynomial and the inputs within a few seconds, thereby demonstrating an attack on the protocol of Kesarwani et al.

Distributed key generation (DKG) allows bootstrapping threshold cryptosystems without relying on a trusted party, nowadays enabling fully decentralized applications in blockchains and multiparty computation (MPC). While we have recently seen new advancements for asynchronous DKG (ADKG) protocols, their performance remains the bottleneck for many applications, with only one protocol being implemented (DYX+ ADKG, IEEE S&P 2022). DYX+ ADKG relies on the Decisional Composite Residuosity assumption (expensive to instantiate) and the Decisional Diffie-Hellman assumption, incurring a high latency (more than 100s with a failure threshold of 16). Moreover, the security of DYX+ ADKG is based on the random oracle model (ROM) which takes hash function as an ideal function; assuming the existence of random oracle is a strong assumption and up to now we cannot find any theoretically-sound implementation. Furthermore, the ADKG protocol needs public key infrastructure (PKI) to support the trustworthiness of public keys. The strong models (ROM and PKI) further limit the applicability of DYX+ ADKG, as they would add extra and strong assumptions to underlying threshold cryptosystems. For instance, if the original threshold cryptosystem works in the standard model, then the system using DYX+ ADKG would need to use ROM and PKI. In this paper, we design and implement a modular ADKG protocol that offers improved efficiency and stronger security guarantees. We explore a novel and much more direct reduction from ADKG to the underlying blocks, reducing both the computational overhead and communication rounds of ADKG in the normal case. Our protocol works for both the low-threshold and high-threshold scenarios, being secure under the standard assumption (the well-established discrete logarithm assumption only) in the standard model (no trusted setup, ROM, or PKI).

QC-MDPC (quasi cyclic moderate density parity check) code-based McEliece cryptosystems are considered to be one of the candidates for post-quantum cryptography. Decreasing DER (decoding error rate) is one of important factor for their security, since recent attacks to these cryptosystems effectively use DER information. In this paper, we pursue the possibility of optimization-base decoding, concretely we examine ADMM (alternating direction method of multipliers), a recent developing method in optimization theory. Further, RSPA (reproducing sum-product algorithm), which efficiently reuse outputs of SPA (sum-product algorithm) is proposed for the reduction of execution time in decoding. By numerical simulations, we show that the proposing scheme shows considerable decrement in DER compared to the conventional decoding methods such as BF (bit-flipping algorithm) variants or SPA.

This paper analyses the lightweight, sponge-based NAEAD mode $\textsf{ISAP}$, one of the finalists of the NIST Lightweight Cryptography (LWC) standardisation project, that achieves high-throughput with inherent protection against differential power analysis (DPA). We observe that $\textsf{ISAP}$ requires $256$-bit capacity in the authentication module to satisfy the NIST LWC security criteria. In this paper, we study the analysis carefully and observe that this is primarily due to the collision in the associated data part of the hash function which can be used in the forgery of the mode. However, the same is not applicable to the ciphertext part of the hash function because a collision in the ciphertext part does not always lead to a forgery. In this context, we define a new security notion, named $\textsf{2PI+}$ security, which is a strictly stronger notion than the collision security, and show that the security of a class of encrypt-then-hash based MAC type of authenticated encryptions, that includes $\textsf{ISAP}$, reduces to the $\textsf{2PI+}$ security of the underlying hash function used in the authentication module. Next we investigate and observe that a feed-forward variant of the generic sponge hash achieves better $\textsf{2PI+}$ security as compared to the generic sponge hash. We use this fact to present a close variant of $\textsf{ISAP}$, named $\textsf{ISAP+}$, which is structurally similar to $\textsf{ISAP}$, except that it uses the feed-forward variant of the generic sponge hash in the authentication module. This improves the overall security of the mode, and hence we can set the capacity of the ciphertext part to $192$ bits (to achieve a higher throughput) and yet satisfy the NIST LWC security criteria.