International Association
for Cryptologic Research

Side-channel power analysis is a powerful method of breaking secure cryptographic algorithms, but typically power analysis is considered to require specialized measurement equipment on or near the device. Assuming an attacker first gained the ability to run code on the unsecure side of a device, they could trigger encryptions and use the on-board ADC to capture power traces of that hardware encryption engine.

This is demonstrated on a SAML11 which contains a M23 core with a TrustZone-M implementation as the hardware security barrier. This attack requires 160 million traces, or approximately 5 GByte of data. This attack does not use any external measurement equipment, entirely performing the power analysis using the ADC on-board the microcontroller under attack. The attack is demonstrated to work both from the non-secure and secure environment on the chip, being a demonstration of a cross-domain power analysis attack.

To understand the effect of noise and sample rate reduction, an attack is mounted on the SAML11 hardware AES peripheral using classic external equipment, and results are compared for various sample rates and hardware setups. A discussion on how users of this device can help prevent such remote attacks is also presented, along with metrics that can be used in evaluating other devices. Complete copies of all recorded power traces and scripts used by the authors are publicly presented.

After Cheon et al. (Asiacrypt' 17) proposed approximate homomorphic encryption for operations between encrypted real (or complex) numbers, this scheme is widely used in various fields with the needs on privacy-preserving in data analysis. After that, the bootstrapping method is firstly proposed by Cheon et al. (Eurocrypt' 18) by replacing modulus reduction with sine function. In this paper, we generalize Full-RNS variant of HEAAN scheme to reduce the number of special primes which are used in key-switching. As a result, our scheme can use a smaller ring dimension or supports more depth computation without bootstrapping while preserving the same security level. And, we propose a bootstrapping specified polynomial approximation method to evaluate sine function in an encrypted state. In our method, the degree of a polynomial approximation is related to the plaintext size. This gives a smaller number of non-scalar multiplications which is about half of the previous work. With our variant of Full-RNS scheme and new sine evaluation method, we firstly implement bootstrapping on Full-RNS variant of approximate homomorphic encryption. Our implementation shows that bootstrapping takes about 120 seconds with 19-bit precisions.

Starting from the one-way group action framework of Brassard and Yung (Crypto '90), we revisit building cryptography based on group actions. Several previous candidates for one-way group actions no longer stand, due to progress both on classical algorithms (e.g., graph isomorphism) and quantum algorithms (e.g., discrete logarithm).

We propose the general linear group action on tensors as a new candidate to build cryptography based on group actions. Recent works (Futorny--Grochow--Sergeichuk, Lin. Alg. Appl., 2019) suggest that the underlying algorithmic problem, the tensor isomorphism problem, is the hardest one among several isomorphism testing problems arising from areas including coding theory, computational group theory, and multivariate cryptography. We present evidence to justify the viability of this proposal from comprehensive study of the state-of-art heuristic algorithms, theoretical algorithms, and hardness results, as well as quantum algorithms.

We then introduce a new notion called pseudorandom group actions to further develop group-action based cryptography. Briefly speaking, given a group G acting on a set S, we assume that it is hard to distinguish two distributions of (s,t) either uniformly chosen from S×S, or where s is randomly chosen from S and t is the result of applying a random group action of g on s. This subsumes the classical decisional Diffie-Hellman assumption when specialized to a particular group action. We carefully analyze various attack strategies that support the general linear group action on tensors as a candidate for this assumption.

Finally, we establish the quantum security of several cryptographic primitives based on the one-way group action assumption and the pseudorandom group action assumption.

The complexity of collision-resistant hash functions has been long studied in the theory of cryptography. While we often think about them as a Minicrypt primitive, black-box separations demonstrate that constructions from one-way functions are unlikely. Indeed, theoretical constructions of collision-resistant hash functions are based on rather structured assumptions. We make two contributions to this study: 1. A New Separation: We show that collision-resistant hashing does not imply hard problems in the class Statistical Zero Knowledge in a black-box way. 2. New Proofs: We show new proofs for the results of Simon, ruling out black-box reductions of collision-resistant hashing to one-way permutations, and of Asharov and Segev, ruling out black-box reductions to indistinguishability obfuscation. The new proofs are quite different from the previous ones and are based on simple coupling arguments.

Most NIST Post-Quantum Cryptography (PQC) candidate algorithms use symmetric primitives internally for various purposes such as ``seed expansion'' and CPA to CCA transforms. Such auxiliary symmetric operations constituted only a fraction of total execution time of traditional RSA and ECC algorithms, but with faster lattice algorithms the impact of symmetric algorithm characteristics can be very significant. A choice to use a specific PQC algorithm implies that its internal symmetric components must also be implemented on all target platforms. This can be problematic for lightweight, embedded (IoT), and hardware implementations. It has been widely observed that current NIST-approved symmetric components (AES, GCM, SHA, SHAKE) form a major bottleneck on embedded and hardware implementation footprint and performance for many of the most efficient NIST PQC proposals. Meanwhile, a separate NIST effort is ongoing to standardize lightweight symmetric cryptography (LWC). Therefore it makes sense to explore which NIST LWC candidates are able to efficiently support internals of post-quantum asymmetric cryptography. We discuss R5Sneik, a variant of Round5 that internally uses SNEIK 1.1 permutation-based primitives instead of SHAKE and AES-GCM. The SNEIK family includes parameter selections specifically designed to support lattice cryptography. R5Sneik is up to 40\% faster than Round5 for some parameter sets on ARM Cortex M4, and has substantially smaller implementation footprint. We introduce the concept of a fast Entropy Distribution Function (EDF), a lightweight diffuser that we expect to have sufficient security properties for lattice seed expansion and many types of sampling, but not for plain encryption or hashing. The same SNEIK 1.1 permutation core (but with a different number of rounds) can also be used to replace AES-GCM as an AEAD when building lightweight cryptographic protocols, halving typical flash footprint on Cortex M4, while boosting performance.

We reveal Revelio, a new privacy-preserving proof of reserves protocol for Grin exchanges. By design, Revelio allows the detection of collusion between exchanges while hiding the identities of the outputs owned by the exchange in a larger anonymity set of outputs.

We revisit the definition of Transparency Order (TO) and that of Modified Transparency Order (MTO) as well, which were proposed to measure the resistance of an S-box against Differential Power Analysis (DPA). We spot a definitional flaw in original TO, which is proved to have significantly affected the soundness of TO and hinder it to be a good quantitative security criterion. Regretfully, the flaw itself remains virtually undiscovered in MTO, either. Surprisingly, MTO overlooks this flaw and yet it happens to incur no bad effects on the correctness of its formulation, even though the start point of this formulation is highly questionable. It is also this neglect of the flaw that made MTO take a variant of multi-bit DPA attack into consideration, which was mistakenly thought to appropriately serve as an alternative powerful attack. Based on this observation, we also find that MTO introduces such an alternative adversary that it might overestimate the resistance of an S-box in some cases, as the variant of multi-bit DPA attack considered in MTO is not that powerful as one may think. This implies the soundness of MTO is also more or less arguable. Consequently, we fix this definitional flaw, and provide a revised definition in which a powerful adversary is also involved. For demonstrating validity and soundness of our revised TO (RTO), we adopt both optimal $4\times4$ S-boxes and $8\times8$ S-boxes as study cases, and present simulated and practical DPA attacks as well on implementations of those S-boxes. The results of our attacks verify our findings and analysis as well. Furthermore, as a concrete application of the revised TO, we also present the distribution of RTO values for sixteen optimal affine equivalence classes of $4\times4$ S-boxes. Finally, we give some recommended guidelines on how to select optimal $4\times4$ S-boxes in practical implementations.

Secure cloud storage is considered as one of the most important issues that both businesses and end-users take into account before moving their private data to the cloud. Lately, we have seen some interesting approaches that are based either on the promising concept of Symmetric Searchable Encryption (SSE) or on the well-studied field of Attribute-Based Encryption (ABE). In the first case, researchers are trying to design protocols where users' data will be protected from both internal and external attacks without paying the necessary attention to the problem of user revocation. In the second case, existing approaches address the problem of revocation. However, the overall efficiency of these systems is compromised since the proposed protocols are solely based on ABE schemes and the size of the produced ciphertexts and the time required to decrypt grows with the complexity of the access formula. In this paper, we propose a hybrid encryption scheme that combines both SSE and ABE by utilizing the advantages of both these techniques. In contrast to many approaches, we design a revocation mechanism that is completely separated from the ABE scheme and solely based on the functionality offered by SGX.

The impending realization of scalable quantum computers has led to active research in Post Quantum Cryptography (PQC). The challenge is harder for embedded IoT (edge) devices, due to their pervasive diffusion in today's world as well as their stricter resources (tight area and energy budgets). Amongst various classes of quantum-resistant cryptography schemes, Lattice-based Cryptography (LBC) is emerging as one of the most viable, almost half of the `survivors' of second round of the NIST's PQC competition are lattice-based in construction. This paper surveys the practicality of deployment of these schemes. In this context, the state-of-the-art LBC implementations on the constrained devices (including low-power FPGAs and embedded microprocessors), leading in terms of low-power footprint, small area, compact bandwidth requirements and high performance is fairly evaluated and bench-marked. The work concludes by identifying a suite of some favorite LBC schemes in terms of various IoT critical performance bench-marks.

The Learning with Errors (LWE) problem is the fundamental backbone of modern lattice based cryptography, allowing one to establish cryptography on the hardness of well-studied computational problems. However, schemes based on LWE are often impractical, so Ring LWE was introduced as a form of `structured' LWE, trading off a hard to quantify loss of security for an increase in efficiency by working over a well chosen ring. Another popular variant, Module LWE, generalizes this exchange by implementing a module structure over a Ring LWE instance. In this work, we introduce a novel variant of LWE over cyclic algebras (CLWE) to replicate the addition of the ring structure taking LWE to Ring LWE by adding cyclic structure to Module LWE. The proposed construction is both more efficient than Module LWE and conjecturally more secure than Ring LWE, the best of both worlds. We show that the standard security reductions expected for an LWE problem hold, namely a reduction from certain structured lattice problems to the hardness of the decision variant of the CLWE problem. As a contribution of theoretic interest, we view CLWE as the first variant of LWE which naturally supports non-commutative multiplication operations.

FlexAEAD is one of the round-1 candidates in the ongoing NIST Lightweight Cryptography standardization project. In this note, we show several forgery attacks on FlexAEAD with complexity less than the security bound given by the designers, such as a block reordering attack on full FlexAEAD-128 with estimated success probability about $2^{-54}$. Additionally, we show some trivial forgeries and point out domain separation issues.

We propose a novel signature scheme based on a modified Reed--Muller (RM) code, which reduces the signing complexity and key size compared to existing code-based signature schemes. This cheme is called as the modified pqsigRM, and corresponds to an improvement of pqsigRM, the proposal submitted to NIST. Courtois, Finiasz, and Sendrier (CFS) proposed a code-based signature scheme using the Goppa codes based on a full domain hash approach. However, owing to the properties of Goppa codes, the CFS signature scheme has drawbacks such as signing complexity and large key size. We overcome these disadvantages of the CFS signature scheme using partially permuted RM code and its decoding, which finds a near codeword for any received vector. Using a partially permuted RM code, the signature scheme resists various known attacks on the RM code-based cryptography. Additionally, we further modify the RM codes by row insertion/deletion of the generator matrix and thereafter resolve the problems reported in the post-quantum cryptography forum by NIST, such as the Hamming weight distribution of the public code.

Bootstrapping is a crucial but computationally expensive step for realizing Fully Homomorphic Encryption (FHE). Recently, Chen and Han (Eurocrypt 2018) introduced a family of low-degree polynomials to extract the lowest digit with respect to a certain congruence, which helps improve the bootstrapping for both FV and BGV schemes. In this note, we present the following relevant findings about the work of Chen and Han (referred to as CH18):

1. We provide a simpler construction of the low-degree polynomials that serve the same purpose and match the asymptotic bound achieved in CH18;

2. We show the optimality and limit of our approach by solving a minimal polynomial degree problem;

3. We consider the problem of extracting other low-order digits using polynomials and provide negative results.

ByzCoin, a promising alternative of Bitcoin, is a scalable consensus protocol used as a building block of many research and enterprise-level decentralized systems. In this paper, we show that ByzCoin is unsuitable for deployment in an anopen, adversarial network and instead introduceMOTOR. MOTORis designed as a secure, robust, and scalable consensus suitable for permissionless sharded blockchains. MOTORachieves these properties by making four key design choices: (a) it prioritizes robustness in adversarial environments while maintaining adequate scalability, (b) it employees provably correct cryptography that resists DoS attacks from individual nodes, (c) it deploys unpredictable rotating leaders to defend against mildly-adaptive adversaries and prevents censorship, and (d) it creates an incentive compatible reward mechanism. These choices are materialized as (a) a “rotating subleader” communication pattern that balances the scalability needs with the robustness requirements under failures, (b) deployment of provable secure BLS multi-signatures, (c) use of deterministic thresh-old signatures as a source of randomness and (d) careful design of the reward allocation mechanism. We have implemented MOTORand compare it withByzCoin. We show that MOTORcan scale similar to ByzCoin with an at most2xoverhead whereas it maintains good performance even under high-percentage of faults, unlike ByzCoin.

Event date: 4 May to 8 May 2020
Submission deadline: 15 August 2019
Notification: 20 October 2019

Event date: 11 November 2019
Submission deadline: 1 August 2019
Notification: 15 August 2019

In cryptoeconomic protocols, financial deposits are fundamental to their security. Protocol designers and their agents face a trade-off when choosing the deposit size. While substantial deposits might increase the protocol security, for example by minimising the impact of adversarial behaviour or risks of currency fluctuations, locked-up capital incurs opportunity costs for agents. Moreover, some protocols require over-collateralization in anticipation of future events and malicious intentions of agents. We present Balance, an application-agnostic system that reduces over-collateralization without compromising protocol security. In Balance, malicious agents receive no additional utility for cheating once their deposits are reduced. At the same time, honest and rational agents increase their utilities for behaving honestly as their opportunity costs for the locked-up deposits are reduced. Balance is a round-based mechanism in which agents need to continuously perform desired actions. Rather than treating agents' incentives and behaviour as ancillary, we explicitly model agents' utility, proving the conditions for incentive compatibility. Balance improves social welfare given a distribution of honest, rational, and malicious agents. Further, we integrate Balance with a cross-chain interoperability protocol, XCLAIM, reducing deposits by 10% while maintaining the same utility for behaving honestly. Our implementation allows any number of agents to be maintained for at most 55,287 gas (ca. USD 0.07) to update the agents' scores, and at a cost of 54,948 gas (ca. USD 0.07) to update the assignment of agents to layers.

Cryptographic constructions based on hard lattice problems have emerged as a front runner for the standardization of post quantum public key cryptography. As the standardization process takes place, optimizing specific parts of proposed schemes becomes a worthwhile endeavor. Gaussian sampling over the integers is one of the fundamental building blocks of latticed-based cryptography. In this work, we propose a new integer Gaussian sampler based on polar codes, dubbed ``polar sampler". The polar sampler is asymptotically information theoretically optimum in the sense that the number of uniformly random bits it uses approaches the entropy bound. It also features quasi-linear complexity and constant-time implementation. Our algorithm becomes effective when sufficiently many samples are required at each query to the sampler. Security analysis is given based on the statistical distance, Kullback-Leibler divergence and R\'enyi divergence. A comparison between the polar sampler and the Knuth-Yao sampler verifies its time efficiency and the memory cost can be further optimized if space-efficient successive-cancellation decoding is adopted.

A new hash-based, server-supported digital signature scheme was proposed recently. We decompose the concept into forward-resistant tags and a generic cryptographic time-stamping service. Based on the decomposition, we propose more tag constructions which allow efficient digital signature schemes with interesting properties to be built. In particular, the new schemes are more suitable for use in personal signing devices, such as smart cards, which are used infrequently. We define the forward-resistant tags formally and prove that (1) the discussed constructs are indeed tags and (2) combining such tags with time-stamping services gives us signature schemes.

We present a server-supported, hash-based digital signature scheme. To achieve greater efficiency than current state of the art, we relax the security model somewhat. We postulate a set of design requirements, discuss some approaches and their practicality, and finally reach a forward-secure scheme with only modest trust assumptions, achieved by employing the concepts of authenticated data structures and blockchains. The concepts of blockchain authenticated data structures and the presented blockchain design could have independent value and are worth further research.