International Association
for Cryptologic Research

As perfect building blocks for the diffusion layers of many symmetric-key primitives, the construction of MDS matrices with light-weight circuits has received much attention from the symmetric-key community. One promising way of realizing low-cost MDS matrices is based on the iterative construction: a low-cost matrix becomes MDS after rising it to a certain power. To be more specific, if $A^t$ is MDS, then one can implement $A$ instead of $A^t$ to achieve the MDS property at the expense of an increased latency with $t$ clock cycles. In this work, we identify the exact lower bound of the number of nonzero blocks for a $4 \times 4$ block matrix to be potentially iterative-MDS. Subsequently, we show that the theoretically lightest $4 \times 4$ iterative MDS block matrix (whose entries or blocks are $4 \times 4$ binary matrices) with minimal nonzero blocks costs at least 3 XOR gates, and a concrete example achieving the 3-XOR bound is provided. Moreover, we prove that there is no hope for previous constructions (GFS, LFS, DSI, and spares DSI) to beat this bound. Since the circuit latency is another important factor, we also consider the lower bound of the number of iterations for certain iterative MDS matrices. Guided by these bounds and based on the ideas employed to identify them, we explore the design space of lightweight iterative MDS matrices with other dimensions and report on improved results. Whenever we are unable to find better results, we try to determine the bound of the optimal solution. As a result, the optimality of some previous results is proved.

Saber is a module lattice-based CCA-secure key encapsulation mechanism (KEM) which has been shortlisted for the second round of NIST's Post Quantum Cryptography Standardization project. To attain simplicity and efficiency on constrained devices, the Saber algorithm is serial by construction. However, on high-end platforms, such as modern Intel processors with AVX2 instructions, Saber achieves limited speedup using vector processing instructions due to its serial nature.

In this paper we overcome the above-mentioned algorithmic bottleneck and propose a high-throughput software implementation of Saber, which we call `SaberX4', targeting modern Intel processors with AVX2 vector processing support. We apply the batching technique at the highest level of the implementation hierarchy and process four Saber KEM operations simultaneously in parallel using the AVX2 vector processing instructions. Our proof-of-concept software implementation of SaberX4 achieves nearly 1.5 times higher throughput at the cost of latency degradation within acceptable margins, compared to the AVX2-optimized non-batched implementation of Saber by its authors.

We anticipate that both latency and throughput of SaberX4 will improve in the future with improved computer architectures and more optimization efforts.

Cryptosystems based on Learning with Errors or related problems are central topics in recent cryptographic research. One main witness to this is the NIST Post-Quantum Cryptography Standardization effort. Many submitted proposals rely on problems related to Learning with Errors. Such schemes often include the possibility of decryption errors with some very small probability. Some of them have a somewhat larger error probability in each coordinate, but use an error correcting code to get rid of errors. In this paper we propose and discuss an attack for secret key recovery based on generating decryption errors, for schemes using error correcting codes. In particular we show an attack on the scheme {\sf LAC}, a proposal to the NIST Post-Quantum Cryptography Standardization that has advanced to round 2. In a standard setting with CCA security, the attack first consists of a precomputation of special messages and their corresponding error vectors. This set of messages are submitted for decryption and a few decryption errors are observed. In a statistical analysis step, these vectors causing the decryption errors are processed and the result reveals the secret key. The attack only works for a fraction of the secret keys. To be specific, regarding {\sf LAC}256, the version for achieving the 256-bit classical security level, we recover one key among approximately \(2^{64}\) public keys with complexity \(2^{79}\), if the precomputation cost of \(2^{162}\) is excluded. We also show the possibility to attack a more probable key (say with probability \(2^{-16}\)). This attack is verified via extensive simulation.

We further apply this attack to {\sf LAC}256-v2, a new version of {\sf LAC}256 in round 2 of the NIST PQ-project and obtain a multi-target attack with slightly increased precomputation complexity (from \(2^{162}\) to \(2^{171}\)). One can also explain this attack in the single-key setting as an attack with precomputation complexity of \(2^{171}\) and success probability of \(2^{-64}\).

Distributed randomness is very useful for many applications, such as smart contract, the proof-of-stake-based blockchain, elliptic curve generation and lottery. Randomness beacon protocols are proposed, which are aimed at continuously distributed randomness generation. However, a reliable source of distributed randomness is gained with difficulty because of Byzantine behavior which may lead to bias for distributed randomness. These Byzantine behaviors include, but not limited to, the “last actor” problem, DoS attack, and collusion attack. Various cryptography schemes have been used to generate distributed randomness. Current constructions face challenging obstacles due to high communication overheads and collusion problems. Given these barriers, we propose a new protocol that is the first precept to utilize attribute-based encryption for distributed randomness (ABERand). Compared to existing state- of-the-art public distributed randomness protocols, ABERand possesses distinguished scalability, security and efficiency. More specifically, we resolve the “last actor” problem and make ABERand an intensive output randomness beacon with com- munication complexity O(n2), computation complexity O(1), verification complexity O(n), and communication complexity O(n) of nodes adding/removing.

Data, an important asset in digital economy, has fueled the emergence of a new data trading market. Big data market can efficiently promote data trading and further increases the utility of data. However, to realize effective data trading, several challenges needs to be resolved. First, it needs to resolve disputes over data availability in the data trad- ing. Second, atomic exchange and payment fairness between the seller and the buyer are hard to guarantee. Third, data trading platform is the single-point-failure. In this paper, we resolve these challenges by pre- senting a valid blockchain-based data trading ecosystem. The ecosystem constructs a decentralized arbitration mechanism to address the dispute over data availability in data trading. The ecosystem also designs a sale contract and a deterministic public-key encryption algorithm to guaran- tee fairness of data trading between the seller and buyer. The features of blockchain is preventing single-point-failure of data trading platform. We prove the desirable security properties that a secure data trading ecosystem should have. Discussion of the presented ecosystem is given. To demonstrate availability, we implement our proposed data trading ecosystem using smart contract in Solidity and program in Java, and evaluate its performance.

Event date: 14 September to 17 September 2020

Event date: 25 May to 28 May 2020
Submission deadline: 11 February 2020

Event date: 2 July to 3 July 2020

Event date: 8 June to 11 June 2020
Submission deadline: 17 February 2020
Notification: 10 April 2020

Genetic data is an indispensable part of big data, promoting the advancement of life science and biomedicine. Yet, highly private genetic data also brings concerns about privacy risks in data shar- ing. In our work, we adopt the cryptographic prim- itive Secure Function Evaluation (SFE) to address this problem. A secure SFE scheme allows insti- tutions and hospitals to compute a function while preserving the privacy of their input data, and each participant knows nothing but their own input and the final result. In our work, we present privacy-preserving solutions for Human Leukocyte Antigen (HLA) matching and two popular biostatistics tests: Chi-squared test and odds ratio test. We also show that our protocols are compatible with multiple databases simultaneously and could feasibly han- dle larger-scale data up to genome-wide level. This approach may serve as a new way to jointly analyze distributed and restricted genetic data among insti- tutions and hospitals. Meanwhile, it can potentially be extended to other genetic analysis algorithms, allowing individuals to analyze their own genomes without endangering data privacy.

An elliptic curve known as Curve448 over the finite field $\mathbb{F}_p$, where $p=2^{448}-2^{224}-1$ has been proposed as part of the Transport Layer Security (TLS) protocol, version 1.3. Elements of $\mathbb{F}_p$ can be represented using 7 limbs where each limb is a 64-bit quantity. In this paper, we describe efficient algorithms for reduction modulo $p$ that are required for performing field arithmetic in $\mathbb{F}_p$. A key feature of our algorithms is that we provide the relevant proofs of correctness. Based on the proofs of correctness we point out the incompleteness of the reduction methods in the previously known fastest code for implementing arithmetic in $\mathbb{F}_p$.

Traceable and linkable ring signature scheme (TLRS) plays a major role in the construction of regulatable privacy-preserving blockchains, as it empowers the regulator with traceability of signers' identities. A recent work by Li et al. gives a modular construction of TLRS by usage of classic ring signature, one-time signature and zero-knowledge proofs. In this paper, we propose a simpler method to construct TLRS directly from classic ring signature and one-time signature without additional zero-knowledge proofs and verifications for validity of users' public keys. Moreover, the security proof of the new TLRS is also given to achieve anonymity, unforgeability, linkability, nonslanderability and traceability.

Private Function Evaluation (PFE) enables two parties to jointly execute a computation such that one of them provides the input while the other chooses the function to compute. According to the traditional security requirements, a PFE protocol should leak no more information, neither about the function nor the input, than what is revealed by the output of the computation. Existing PFE protocols inherently restrict the scope of computable functions to a certain function class with given output size, thus ruling out the direct evaluation of such problematic functions as the identity map, which would entirely undermine the input privacy requirement. We observe that when not only the input $x$ is confidential but certain partial information $g(x)$ of it as well, standard PFE fails to provide meaningful input privacy if $g$ and the function $f$ to be computed fall into the same function class.

Our work investigates the question whether it is possible to achieve a reasonable level of input and function privacy simultaneously even in the above cases. We propose the notion of Controlled PFE (CPFE) with different flavours of security and answer the question affirmatively by showing simple, generic realizations of the new notions. Our main construction, based on functional encryption (FE), also enjoys strong reusability properties enabling, e.g. fast computation of the same function on different inputs. To demonstrate the applicability of our approach, we show a concrete instantiation of the FE-based protocol for inner product computation that enables secure statistical analysis (and more) under the standard Decisional Diffie--Hellman assumption.

In this paper we revisit the modular lattice signature scheme and its efficient instantiation known as pqNTRUSign. First, we show that a modular lattice signature scheme can be based on a standard lattice problem. The fundamental problem that needs to be solved by the signer or a potential forger is recovering a lattice vector with a restricted norm, given the least significant bits. We show that this problem is equivalent to the short integer solution (SIS) problem over the corresponding lattice.

In addition, we show that by replacing the uniform sampling in pqNTRUSign with a bimodal Gaussian sampling, we can further reduce the size of a signature. An important new contribution, enabled by this Gaussian sampling version of pqNTRUSign, is that we can now perform batch verification of messages signed by the same public key, which allows the verifier to check approximately 24 signatures in a single verification process.

We present an actively secure, practical protocol to generate the distributed secret keys needed in the SPDZ offline protocol. The resulting distribution of the public and secret keys is such that the associated SHE `noise' analysis is the same as if the distributed keys were generated by a trusted setup. We implemented the presented protocol for distributed BGV key generation within the SCALE-MAMBE framework. Our method makes use of a new method for creating doubly (or even more) authenticated bits in different MPC engines, which has applications in other areas of MPC-based secure computation. We were able to generate keys for two parties and a plaintext size of 64 bits in less than ten minutes, and approximately half an hour for a 128 bit prime.

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs in ICS 2010, have emerged in the last few years as a fundamental object at the intersection of cryptography and coding theory. Non-malleable codes provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely "unrelated value''.

The family which received the most attention is the family of tampering functions in the so called (2-part) split-state model: here the message x is encoded into two shares L and R, and the attacker is allowed to arbitrarily tamper with each L and R individually.

In this work, we give a constant rate non-malleable code from the tampering family containing so called 2-lookahead functions and forgetful functions, and combined with the work of Dodis, Kazana and the authors from STOC 2015, this gives the first constant rate non-malleable code in the split-state model with negligible error.

MPC over rings like $\mathbb Z_{2^{32}}$ or $\mathbb Z_{2^{64}}$ has received a lot of attention recently due to their potential benefits in implementation and performance. Several protocols for active security over these rings have been proposed recently, including an implementation in the dishonest majority setting due to Damgård et al. (S&P 2019) and in the popular three-party and one corruption setting. However, to this date, no concretely-efficient protocol for arithmetic computation over rings in the honest majority setting, which works for any number of parties, have been proposed. In this work, we present a new compiler for MPC over the ring $\mathbb Z_{2^{k}}$ in the honest majority setting, that takes several building blocks, which can be essentially instantiated using semi-honest protocols, and turn them into a maliciously secure protocol. Our compiler follows the framework of Chida et al. (CRYPTO 18) for finite fields, and makes it compatible for rings using techniques from the work of Cramer et al. (CRYPTO 18), with only small additional overhead. Per multiplication gate, our compiler requires only two invocations of a semi-honest multiplication protocol over the larger ring $\mathbb Z_{2^{k+s}}$, where $s$ is the statistical security parameter. As with previous works in this area aiming to achieve high efficiency, our protocol is secure with abort and does not achieve fairness, meaning that the adversary may receive output while the honest parties do not.

We provide two efficient instantiations for our compiler. The first instantiation is for the three-party case and is based on replicated secret sharing, where the resulting protocol requires each party to send just $2(k+s)$ bits per multiplication gate. To the best of our knowledge, this is the most efficient three-party protocol for large rings to this date. Our second instantiation is for any number of parties. In this case we manage to instantiate our compiler with a variant of Shamir secret sharing that was recently proposed by Abspoel et al. (TCC 2019). We show that the theoretical constructions from Abspoel et al. (TCC 2019) can be instantiated efficiently and prove that they satisfy the properties required by our building blocks. The resulting protocol requires each party to send just $14(k+s) \log n$ bits per multiplication gate. To the best of our knowledge, this is the first concretely-efficient protocol for MPC over rings with an honest majority that works for any number of parties. We implemented our two protocols, run extensive experiments to measure their performance and report their efficiency. Our results prove that efficient honest-majority MPC over rings is possible.

Quantum computers threaten to compromise public-key cryptography schemes such as DSA and ECDSA in polynomial time, which poses an imminent threat to secure signal processing. The cryptography community has responded with the development and standardization of post-quantum cryptography (PQC) algorithms, a class of public-key algorithms based on hard problems that no known quantum algorithms can solve in polynomial time. Ring learning with error (RLWE) lattice- based cryptographic (LBC) protocols are one of the most promising families of PQC schemes in terms of efficiency and versatility. Two common methods to compute polynomial multiplication, the most compute-intensive routine in the RLWE schemes are convolutions and Number Theoretic Transform (NTT). In this work, we explore the energy efficiency of polynomial multiplier using systolic architecture for the first time. As an early exploration, we design two high-throughput systolic array polynomial multipliers, including NTT-based and convolution-based, and compare them to our low-cost sequential (non-systolic) NTT-based multiplier. Our sequential NTT-based multiplier achieves more than 3x speedup over the state-of-the-art FGPA implementation of the polynomial multiplier in the NewHope-Simple key exchange mechanism on a low-cost Artix7 FPGA. When synthesized on a Zynq UltraScale+ FPGA, the NTT-based systolic and convolution-based systolic designs achieve on average 1.7x and 7.5x speedup over our sequential NTT-based multiplier respectively, which can lead to generating over 2x more signatures per second by CRYSTALS-Dilithium, a PQC digital signature scheme. These explorations will help designers select the right PQC implementations for making future signal processing applications quantum- resistant.

FastSwap is a simple and concretely efficient contingent payment scheme for complex predicates, inspired by FairSwap. FastSwap only relies on symmetric primitives (in particular symmetric encryption and cryptographic hash functions) and avoids `heavy-weight' primitives such as general ZKP systems. FastSwap is particularly well-suited for applications where the witness or predicate is large (on the order of MBs / GBs) or expensive to calculate. Additionally FastSwap allows predicates to be implemented using virtually any computational model (including branching execution), which e.g. enables practitioners to express the predicate in smart contract languages already familiar to them, without an expensive transformation to satisfiability of arithmetic circuits. The cost of this efficiency during honest execution is a logarithmic number of rounds during a dispute resolution in the presence of a corrupted party (compared to constant round complexity for existing schemes). Let the witness be of size $|w|$ and the predicate of size $|P|$, where computing $P(w)$ takes $n$ steps. In the honest case the off-chain communication complexity is $|w| + |P| + c$ for a small constant $c$, the on-chain communication complexity is $c'$ for a small constant $c'$. In the malicious case the on-chain communication complexity is $O(\log n)$ with small constants. Concretely with suitable optimizations the number of rounds (on-chain transactions) for a computation of $2^{30}$ steps can be brought to $2$ in the honest case with an estimated cost of $\approx 2$ USD on the Ethereum blockchain and to $14$ rounds with an estimated cost of $\approx 4$ USD in case of a dispute.

Conventional asymmetric key exchange protocols rely on computing elements in commutative groups, where the employed trapdoor-permutation function is commutative, allowing Alice and Bob to compute the same element in $G$ as changing the orders of the variables or elements doesn't alter the output. The research found in this paper is focused on the analysis of key exchange protocols found in non-commutative cryptography, sometimes called group-based cryptography. Variations of these schemes made by the author are also included. Concretely, four schemes are presented using matrices over finite fields and permutation groups containing all the theory to break these schemes along with its pseudo-code and implementations in Mathematica.