International Association
for Cryptologic Research

We investigate multiple implementations of a hash-based digital signature scheme in software and hardware for a RISC-V processor. For this, different instantiations of XMSS by leveraging SHA-256 and SHA-3 are considered. Moreover, we propose various optimisations for accelerating the signature scheme on resource-constrained FPGAs. Compared to the pure software version, the implemented hardware accelerators for SHA-256 and SHA-3 achieve a significant speedup of 25x and 87x respectively for generating 2^10 key pairs. Signing and verifying with such key pairs achieves a speedup of 17x and 10x in the case of SHA-256 and respectively 55x and 20x for SHA-3. Recently, Wang et al. presented an XMSS-specific software-hardware co-design, resulting in significant speedups. Our general-purpose hardware accelerator for SHA-256 further reduces the calculation cost for signing by 26%, and by 28% for verifying in comparison to results of Wang et al., and achieves as well a better time-area product for signing (3.3x) and verifying (2.5x).

Lattice-based cryptography offers quantum-resistant cryptosystems but there is not yet official recommendations to choose parameters with standard security levels. Some of these cryptosystems permit secure computations and aim at a wider audience than cryptographic community. We focus on one of them, a leveled homomorphic cryptosystem (LHE): Brakersi/Fan-Vercauteren's (BFV) one. The family of LHE cryptosystems needs to be well-instantiated not only to protect input and output ciphertexts and to perform efficiently computations, but also, for them, parametrization constrains the quantity of homomorphic computations that can be performed with guarantee of correctness. It demands to choose parameters accordingly. In addition, each implementation brings external constraints to optimize performance. All of this makes it tedious for the non-expert user to choose parameters. To solve this, we have developed CinguParam to help user to instantiate implementations of BFV in different libraries: Cingulata, FV-NFLlib and Microsoft SEAL. CinguParam permits to generate an up-to-date database of parameter sets in function of computation budget, security parameters and implementation choices. This tool includes a notion of budget to ensure correct homomorphic computations and the one of BKZ reduction cost model to grasp the gap from concrete security, nowadays. It makes use of the LWE-Estimator to obtain up-to-date security estimations. CinguParam permits to select automatically a suitable parameter set with Cingulata and it can be used to generate code snippets to set parameters with FV-NFLlib and Microsoft SEAL.

Metering is a critical process in large-scale distributed industrial plants, which enables multiple plants to collaborate to offer mutual services without outside interference. When distributed plants measure the data from a shared common source, e.g., flow metering in an oil pipeline, trustworthiness and immutability must be guaranteed among them. In this paper, we propose a hierarchical and scalable blockchain-based secure metering system, \textit{SMChain}, to provide strong security, trustworthy guarantee, and immutable services. {\em SMChain} adopts a two-layer blockchain structure, consisting of independent local blockchains stored at individual plants and one state blockchain stored in the cloud. To deal with the scalability issues within each plant, we propose a novel scalable Byzantine Fault Tolerance (BFT) consensus protocol based on \textit{(k, n)}-threshold signature scheme to deal with the Byzantine faults and reduce the intra-plant communication complexity from $O(n^2)$ to $O(n)$. For the state blockchain, we use a cloud-based service to synchronize and integrate the local blockchains into one state blockchain, which can further be distributed back to each plant.

We introduce an efficient transformation from univariate polynomial commitment based zk-SNARKs to their fully transparent counterparts. The transformation is achieved with the help of a new IOP primitive which we call a list polynomial commitment. This primitive is applicable for preprocessing zk-SNARKs over both prime and binary fields. We present the primitive itself along with a soundness analysis of the transformation and instantiate it with an existing universal proof system. We also present benchmarks for a proof of concept implementation alongside a comparison with a non-transparent alternative based on Kate commitments. Our results show competitive efficiency both in terms of proof size and generation times at large security levels.

Lattice-based encryption schemes are often subject to the possibility of decryption failures, in which valid encryptions are decrypted incorrectly. Such failures, in large number, leak information about the secret key, enabling an attack strategy alternative to pure lattice reduction. Extending the failure boosting technique of D'Anvers et al. in PKC 2019, we propose an approach that we call directional failure boosting that uses previously found failing ciphertexts to accelerate the search for new ones. We analyse in detail the case where the lattice is defined over polynomial ring modules quotiented by $\langle X^{N} + 1 \rangle$ and demonstrate it on a simple Mod-LWE-based scheme parametrized à la Kyber768/Saber. We show that using our technique, the cost of searching for additional failing ciphertexts after one or more have already been found can be sped up dramatically, thus demonstrating that these schemes should be designed so that it is hard to even obtain one decryption failure.

The inconsistency of Nash equilibrium of rational delegated computation scheme in the UC framework will lead to the lack of strict security proof of the protocols fundamentally. The consistency proof of Nash equilibrium between the ideal world and the real world has always been a challenge in the research field. In this paper, we analyze the Nash equilibrium according to the game model of rational delegated computation, and the ideal functionality for rational delegation of computation based on incentive-driven adversary is proposed, then we construct a rational delegated computation protocol for UC-realizing the ideal functionality. In a word, the proposed rational delegated computing protocol based on incentive-driven adversary has been proven to be secure in the universally composable framework, furthermore, we effectively solve the inconsistency problem of Nash equilibrium between the real world and the ideal world.

Secret sharing splits a secret $s$ into $\ell$ shares in such a way that $k\leq \ell$ shares suffice to reconstruct $s$. Let $\rho_{i,j}$ be the probability that shareholder $i$ disclose their share to shareholder $j$, with $0 \leq i,j < n$.

Given $k \leq \ell \leq n$, to whom $\ell$ individuals should we hand shares, if we wish to minimize the probability that one of them reconstitutes $s$?

A new multivariate cryptosystem based on a linear code was proposed by Smith-Tone and Tone quite recently. This short note points out that it is a variant of UOV.

Recent results have shown that some post-quantum cryptographic systems have encryption and decryption performance comparable to fast elliptic-curve cryptography (ECC) or even better. However, this performance metric is considering only CPU time and ignoring bandwidth and storage. High-confidence post-quantum encryption systems have much larger keys than ECC. For example, the code-based cryptosystem recommended by the PQCRYPTO project uses public keys of 1MB.

Fast key erasure (to provide ``forward secrecy'') requires new public keys to be constantly transmitted. Either the server needs to constantly generate, store, and transmit large keys, or it needs to receive, store, and use large keys from the clients. This is not necessarily a problem for overall bandwidth, but it is a problem for storage and computation time on tiny network servers. All straightforward approaches allow easy denial-of-service attacks.

This paper describes a protocol, suitable for today's networks and tiny servers, in which clients transmit their code-based one-time public keys to servers. Servers never store full client public keys but work on parts provided by the clients, without having to maintain any per-client state. Intermediate results are stored on the client side in the form of encrypted cookies and are eventually combined by the server to obtain the ciphertext. Requirements on the server side are very small: storage of one long-term private key, which is much smaller than a public key, and a few small symmetric cookie keys, which are updated regularly and erased after use. The protocol is highly parallel, requiring only a few round trips, and involves total bandwidth not much larger than a single public key. The total number of packets sent by each side is 971, each fitting into one IPv6 packet of less than 1280 bytes.

The protocol makes use of the structure of encryption in code-based cryptography and benefits from small ciphertexts in code-based cryptography.

FPGAs are increasingly used in cloud applications and being integrated into Systems-on-Chip (SoCs). For these systems, various side-channel attacks on cryptographic implementations have been reported, motivating to apply proper countermeasures. Beyond cryptographic implementations, maliciously introduced covert channel receivers and transmitters can allow to exfiltrate any kind of secret information from the FPGA. In this paper, we present a fast covert channel on FPGAs, which exploits the on-chip power distribution network. This can be achieved without any logical connection between the transmitter and receiver blocks. Compared to FPGA thermal covert channels that reach about 1 bit/s, we can show a transmission rate of 8 MBit/s which is almost error free. We reach a small raw bit error ratio (BER) below 10 $\times$ 10$^{-6}$ BER, even in the presence of noise generated from another functional module in the FPGA, and without using error correction codes. When we place and operate other co-tenant modules that require 85% total FPGA area, the BER increases to $\approx$100-1000$\times$ 10$^{-6}$, depending on the platform. This error rate is still reasonably low for a covert channel. Overall, the transmitter and receiver work with less than 3% FPGA resources together.

Computer-aided cryptography is an active area of research that develops and applies formal, machine-checkable approaches to the design, analysis, and implementation of cryptography. We present a cross-cutting systematization of the computer-aided cryptography literature, focusing on three main areas: (i) design-level security (both symbolic security and computational security), (ii) functional correctness and efficiency, and (iii) implementation-level security (with a focus on digital side-channel resistance). In each area, we first clarify the role of computer-aided cryptography---how it can help and what the caveats are---in addressing current challenges. We next present a taxonomy of state-of-the-art tools, comparing their accuracy and scope of analysis, trustworthiness, and usability. Then, we highlight their main achievements, trade-offs, and research challenges. After covering the three main areas, we present two case studies. First, we study efforts in combining tools focused on different areas to consolidate the guarantees they can provide. Second, we distill the lessons learned from the computer-aided cryptography community's involvement in the TLS 1.3 standardization effort. Finally, we conclude with recommendations to paper authors, tool developers, and standardization bodies moving forward.

The user of an imperfectly correct lattice-based public-key encryption scheme leaks information about their secret key with each decryption query that they answer---even if they answer all queries successfully. Through a refinement of the D'Anvers--Guo--Johansson--Nilsson--Vercauteren--Verbauwhede failure boosting attack, we show that an adversary can use this information to improve his odds of finding a decryption failure. We also propose a new definition of $\delta$-correctness, and we re-assess the correctness of several submissions to NIST's post-quantum standardization effort.

Using a set of pairing product equations (PPEs) to verify the correctness of an untrusted set of pairing elements with respect to another set of trusted elements has numerous cryptographic applications. These include the design of basic and structure-preserving signature schemes, building oblivious transfer schemes from “blind” IBE, finding new verifiable random functions and keeping the IBE/ABE authority “accountable” to the user.

A natural question to ask is: are all trusted-untrusted pairing element groups in the literature PPE testable? We provide original observations demonstrating that the answer is no, and moreover, it can be non-trivial to determine whether or not there exists a set of PPEs that can verify some pairing elements with respect to others. Many IBE schemes have PPE-testable private keys (with respect to the public parameters), while others, such as those based on dual-system encryption, provably do not.

To aid those wishing to use PPE-based element verification in their cryptosystems, we devised rules to systematically search for a set of PPEs that can verify untrusted elements with respect to a set of trusted elements. We prove the correctness of each rule and combine them into a main searching algorithm for which we also prove correctness. We implemented this algorithm in a new software tool, called AutoPPE. Tested on over two dozen case studies, AutoPPE found a set of PPEs (on schemes where they exist) usually in just a matter of seconds. This work represents an important step towards the larger goal of improving the speed and accuracy of pairing-based cryptographic design via computer automation.

Secure multiparty computation enables a set of parties to securely carry out a joint computation on their private inputs without revealing anything but the output. A particularly motivated setting is that of three parties with a single corruption (hereafter denoted 3PC). This 3PC setting is particularly appealing for two main reasons: (1) it admits {\em more efficient} MPC protocols than in other standard settings; (2) it allows in principle to achieve {\em full security} (and fairness).

Highly efficient protocols exist within this setting with security against a semi-honest adversary; however, a significant gap remains between these and protocols with stronger security against a malicious adversary.

In this paper, we narrow this gap within concretely efficient protocols. More explicitly, we have the following contributions:

* Concretely Efficient Malicious 3PC. We present an optimized 3PC protocol for arithmetic circuits over rings with (amortized) communication of 1 ring element per multiplication gate per party, matching the best semi-honest protocols. The protocol applies also to Boolean circuits, significantly improving over previous protocols even for small circuits.

Our protocol builds on recent techniques of Boneh et al.\ (Crypto 2019) for sublinear zero-knowledge proofs on distributed data, together with an efficient semi-honest protocol based on replicated secret sharing (Araki et al., CCS 2016).

We present a concrete analysis of communication and computation costs, including several optimizations. For example, for 40-bit statistical security, and Boolean circuit with a million (nonlinear) gates, the overhead on top of the semi-honest protocol can involve less than 0.5KB of communication {\em for the entire circuit}, while the computational overhead is dominated by roughly 30 multiplications per gate in the field $F_{2^{47}}$. In addition, we implemented and benchmarked the protocol for varied circuit sizes.

* Full Security. We augment the 3PC protocol to further provide full security (with guaranteed output delivery) while maintaining amortized 1 ring element communication per party per multiplication gate, and with hardly any impact on concrete efficiency. This is contrasted with the best previous 3PC protocols from the literature, which allow a corrupt party to mount a denial-of-service attack without being detected.

Tweakable block ciphers are increasingly becoming a common primitive to build new resilient modes as well as a concept for multiple dedicated designs. While regular block ciphers define a family of permutations indexed by a secret key, tweakable ones define a family of permutations indexed by both a secret key and a public tweak. In this work we formalize and study a generic framework for building such a tweakable block cipher based on regular block ciphers, the iterated tweakable FX construction, which includes many such previous constructions of tweakable block ciphers. Then we describe a cryptanalysis from which we can derive a provable security upper-bound for all constructions following this tweakable iterated FX strategy. Concretely, the cryptanalysis of r rounds of our generic construction based on n-bit block ciphers with \kap-bit keys requires O(2^{r(n + \kap)/(r+1)}) online and offline queries. For r = 2 rounds this interestingly matches the proof of the particular case of XHX2 by Lee and Lee (ASIACRYPT 2018) thus proving for the first time its tightness. In turn, the XHX and XHX2 proofs show that our generic cryptanalysis is information theoretically optimal for 1 and 2 rounds.

Code-based public key cryptosystems have been found to be an interesting option in the area of Post-Quantum Cryptography. In this work, we present a key encapsulation mechanism (KEM) using a parity check matrix of the Generalized Srivastava code as the public key matrix. Generalized Srivastava codes are privileged with the decoding technique of Alternant codes as they belong to the family of Alternant codes. We exploit the dyadic structure of the parity check matrix to reduce the storage of the public key. Our encapsulation leads to a shorter ciphertext as compared to DAGS proposed by Banegas et al. in Journal of Mathematical Cryptology which also uses Generalized Srivastava code. Our KEM provides IND-CCA security in the random oracle model. Also, our scheme can be shown to achieve post-quantum security in the quantum random oracle model.

Let $A/\overline{\mathbb{F}}_p$ and $A'/\overline{\mathbb{F}}_p$ be supersingular principally polarized abelian varieties of dimension $g>1$. For any prime $\ell \ne p$, we give an algorithm that finds a path $\phi : A \rightarrow A'$ in the $(\ell, \dots , \ell)$-isogeny graph in $\widetilde{O}(p^{g-1})$ group operations on a classical computer, and $\widetilde{O}(\sqrt{p^{g-1}})$ calls to the Grover oracle on a quantum computer. The idea is to find paths from $A$ and $A'$ to nodes that correspond to products of lower dimensional abelian varieties, and to recurse down in dimension until an elliptic path-finding algorithm (such as Delfs--Galbraith) can be invoked to connect the paths in dimension $g=1$. In the general case where $A$ and $A'$ are any two nodes in the graph, this algorithm presents an asymptotic improvement over all of the algorithms in the current literature. In the special case where $A$ and $A'$ are a known and relatively small number of steps away from each other (as is the case in higher dimensional analogues of SIDH), it gives an asymptotic improvement over the quantum claw finding algorithms and an asymptotic improvement over the classical van Oorschot--Wiener algorithm.

Three-party key exchange, where two clients aim to agree a session key with the help of a trusted server, is prevalent in present-day systems. In this paper, we present a practical and secure three-party password-based authenticated key exchange protocol over ideal lattices. Aside from hash functions our protocol does not rely on external primitives in the construction and the security of our protocol is directly relied on the Ring Learning with Errors (RLWE) assumption. Our protocol attains provable security. A proof-of-concept implementation shows our protocol is indeed practical.