Here you can see all recent updates to the IACR webpage. These updates are also available:

13
June
2019

ePrint Report
A Cautionary Note Regarding the Usage of Leakage Detection Tests in Security Evaluation
Carolyn Whitnall, Elisabeth Oswald

An established ingredient in the security evaluation of cryptographic devices is leakage detection, whereby physically observable characteristics such as the power consumption are measured during operation and statistically analysed in search of sensitive data dependencies. However, depending on its precise execution, this approach potentially suffers several drawbacks: a risk of false positives, a difficulty interpreting negative outcomes, and the infeasibility of covering every possible eventuality. Moreover, efforts to mitigate for these drawbacks can be costly with respect to the data complexity of the testing procedures. In this work, we clarify the (varying) goals of leakage detection and assess how well-geared current practice is towards meeting each of those goals. We introduce some new innovations on existing methodologies and make recommendations for best practice. Ultimately, though, we find that many of the obstacles cannot be fully overcome according to existing statistical procedures, so that it remains to be highly cautious and to clearly state the limitations of the methods used when reporting outcomes.

Plantlet is a lightweight stream cipher designed by Mikhalev, Armknecht and M\"{u}ller in IACR ToSC 2017. It has a Grain-like structure with two state registers of size 40 and 61 bits. In spite of this, the cipher does not seem to lose in security against generic Time-Memory-Data Tradeoff attacks due to the novelty of its design. The cipher uses a 80-bit secret key and a 90-bit IV. In this paper, we present a key recovery attack on Plantlet that requires around $2^{76.26}$ Plantlet encryptions. The attack leverages the fact that two internal states of Plantlet that differ in the 43rd LFSR location are guaranteed to produce keystream that are either equal or unequal in 45 locations with probability 1. Thus an attacker can with some probability guess that when 2 segments of keystream blocks possess the 45 bit difference just mentioned, they have been produced by two internal states that differ only in the 43rd LFSR location. Thereafter by solving a system of polynomial equations representing the keystream bits, the attacker can find the secret key if his guess was indeed correct, or reach some kind of contradiction if his guess was incorrect. In the latter event, he would repeat the procedure for other keystream blocks with the given difference. We show that the process when repeated a finite number of times, does indeed yield the value of the secret key.

ePrint Report
Decentralized Multi-authority Anonymous Authentication for Global Identities with Non-interactive Proofs
Hiroaki Anada

We propose a decentralized multi-authority anonymous authentication scheme in which a prover and a verifier are non-interactive. We give two security definitions; resistance against collusion attacks that cause misauthentication, and anonymity for privacy protection. Then we give a construction under a principle of ``commit-to-ID''. We employ two building blocks; the structure-preserving signature scheme and the Groth-Sahai non-interactive proof system, the both of which are based on bilinear groups. We give security proofs in the standard model, which reduce to the security of the building blocks.

ePrint Report
SAEB: A Lightweight Blockcipher-Based AEAD Mode of Operation
Yusuke Naito, Mitsuru Matsui, Takeshi Sugawara, Daisuke Suzuki

Lightweight cryptography in computationally constrained devices is actively studied. In contrast to advances of lightweight blockcipher in the last decade, lightweight mode of operation is seemingly not so mature, yet it has large impact in performance. Therefore, there is a great demand for lightweight mode of operation, especially that for authenticated encryption with associated data (AEAD). Among many known properties of conventional modes of operation, the following four properties are essential for constrained devices:

1. Minimum State Size: the state size equals to a block size of a blockcipher.

2. Inverse Free: no need for a blockcipher decryption.

3. XOR Only: only XOR is needed in addition to a blockcipher encryption.

4. Online: a data block is processed only once.

The properties 1 and 4 contribute to small memory usage, and the properties 2 and 3 contribute to small program/circuit footprint. On top of the above properties, the fifth property regarding associated data (AD) is also important for performance:

5. Efficient Handling of Static AD: static AD can be precomputed.

We design a lightweight blockcipher-based AEAD mode of operation called SAEB: the first mode of operation that satisfies all the five properties to the best of our knowledge. Performance of SAEB is evaluated in various software and hardware platforms. The evaluation results show that SAEB outperforms conventional blockcipher-based AEAD modes of operation in various performance metrics for lightweight cryptography.

1. Minimum State Size: the state size equals to a block size of a blockcipher.

2. Inverse Free: no need for a blockcipher decryption.

3. XOR Only: only XOR is needed in addition to a blockcipher encryption.

4. Online: a data block is processed only once.

The properties 1 and 4 contribute to small memory usage, and the properties 2 and 3 contribute to small program/circuit footprint. On top of the above properties, the fifth property regarding associated data (AD) is also important for performance:

5. Efficient Handling of Static AD: static AD can be precomputed.

We design a lightweight blockcipher-based AEAD mode of operation called SAEB: the first mode of operation that satisfies all the five properties to the best of our knowledge. Performance of SAEB is evaluated in various software and hardware platforms. The evaluation results show that SAEB outperforms conventional blockcipher-based AEAD modes of operation in various performance metrics for lightweight cryptography.

ePrint Report
Quantum security of the Fiat-Shamir transform of commit and open protocols
AndrĂ© Chailloux

Applying the Fiat-Shamir transform on identification schemes is one of the main ways of constructing signature schemes. While the classical security of this transformation is well understood, it is only very recently that generic results for the quantum case has been proposed [DFMS19,LZ19]. In this paper, we show that if we start from a commit-and-open identification scheme, where the prover first commits to several strings and then as a second message opens a subset of them depending on the verifier's message, then the Fiat-Shamir transform is quantum secure, for a suitable choice of commitment scheme. Unlike previous generic results, our transformation doesn't require to reprogram the random function H used in the Fiat-Shamir transform and we actually only require a quantum one-wayness property.

Our techniques can in some cases lead to a much tighter security reduction. To illustrate this, we apply our techniques to identifications schemes at the core of the MQDSS signature scheme, the Picnic scheme (both present in the round 2 of the post quantum NIST competition) and the Stern signature scheme. For all these schemes, we show that our technique can be applied with essentially tight results.

Our techniques can in some cases lead to a much tighter security reduction. To illustrate this, we apply our techniques to identifications schemes at the core of the MQDSS signature scheme, the Picnic scheme (both present in the round 2 of the post quantum NIST competition) and the Stern signature scheme. For all these schemes, we show that our technique can be applied with essentially tight results.

In cryptocurrencies such as Bitcoin or Ethereum users control funds via secret keys. To transfer funds from one user to another, the owner of the money signs a new transaction that transfers the funds to the new recipient. This makes secret keys a highly attractive target for attacks, and has lead to prominent examples where millions of dollars worth in cryptocurrency have been stolen. To protect against these attacks, a widely used approach are so-called hot/cold wallets. In a hot/cold wallet system, the hot wallet is permanently connected to the network, while the cold wallet stores the secret key and is kept without network connection. In this work, we propose the first comprehensive security model for hot/cold wallets and develop wallet schemes that are provable secure within these models. At the technical level our main contribution is to provide a new provably secure ECDSA-based hot/cold wallet scheme that can be integrated into legacy cryptocurrencies such as Bitcoin. Our scheme makes several subtle changes to the BIP32 proposal and requires a technically involved security analysis.

Assuring security of the Internet of Things (IoT) is much more challenging than assuring security of centralized environments, like the cloud. A reason for this is that IoT devices are often deployed in domains that are remotely managed and monitored. Thus, their physical security cannot be guaranteed as reliably as physical security of data centers. Some believe that physical security becomes less important if all data processed and stored within a device is encrypted. However, an attacker with a physical access to a device implementing an encryption algorithm may be able to extract the encryption key and decrypt data. As a demonstration, in this paper we attack ACORN stream cipher, a finalist of CESAR competition for authenticated encryption. By injecting a single stuck-at-0 fault into ACORN's implementation, we reduce its non-linear feedback function to a linear one. Since this obviously makes ACORN weaker, many known attacks can be applied to break it. We apply an algebraic attack which recovers the key from $2^{15.34}$ keystream bits using $2^{35.46}$ operations.

12
June
2019

ePrint Report
Black-Box Language Extension of Non-Interactive Zero-Knowledge Arguments
Masayuki Abe, Miguel Ambrona, Miyako Ohkubo

Highly efficient non-interactive zero-knowledge arguments (NIZK) are often constructed for limited languages and it is not known how to extend them to cover wider classes of languages in general. In this paper we initiate a study on black-box language extensions for conjunctive and disjunctive relations, that is, building a NIZK system for ${\cal L} \diamond \hat{{\cal L}}$ (with $\diamond \in \{\land, \lor\}$) based on NIZK systems for languages ${\cal L}$ and $\hat{{\cal L}}$. While the conjunctive extension of NIZKs is straightforward by simply executing the given NIZKs in parallel, it is not known how disjunctive extensions could be achieved in a black-box manner. Besides, observe that the simple conjunctive extension does not work in the case of simulation-sound NIZKs (SS-NIZKs), as pointed out by Sahai (Sahai, FOCS 1999). Our main contribution is an impossibility result that negates the existence of the above extensions and implies other non-trivial separations among NIZKs, SS-NIZKs, and labelled SS-NIZKs.
Motivated by the difficulty of such transformations, we additionally present an efficient construction of signature schemes based on unbounded simulation-sound NIZKs (USS-NIZKs) for any language without language extensions.

ePrint Report
An Efficient Secure Three-Party Sorting Protocol with an Honest Majority
Koji Chida, Koki Hamada, Dai Ikarashi, Ryo Kikuchi, Naoto Kiribuchi, Benny Pinkas

We present a novel three-party sorting protocol secure against passive adversaries in the honest majority setting. The protocol can be easily combined with other secure protocols which work on shared data, and thus enable different data analysis tasks, such as data deduplication, set intersection, and computing percentiles.

The new sorting protocol is based on radix sort. It is asymptotically better compared to previous sorting protocols since it does not need to shuffle the entire length of the items after each comparison step. We further improve the concrete efficiency by using not only optimizations but also novel protocols, which are independent of interest.

We implemented our sorting protocol with those optimizations and protocols. Our experiments show that our implementation is concretely fast. For example, sorting one million $20$-bit items takes 4.6 seconds in 1G connection. It enables a new set of applications on large-scale datasets since the known implementations handle thousands of items about 10 seconds.

The new sorting protocol is based on radix sort. It is asymptotically better compared to previous sorting protocols since it does not need to shuffle the entire length of the items after each comparison step. We further improve the concrete efficiency by using not only optimizations but also novel protocols, which are independent of interest.

We implemented our sorting protocol with those optimizations and protocols. Our experiments show that our implementation is concretely fast. For example, sorting one million $20$-bit items takes 4.6 seconds in 1G connection. It enables a new set of applications on large-scale datasets since the known implementations handle thousands of items about 10 seconds.

Ratcheting, an umbrella term for certain techniques for achieving secure messaging with strong guarantees, has spurred much interest in the cryptographic community, with several novel protocols proposed as of lately. Most of them are composed from several sub-protocols, often sharing similar ideas across different protocols. Thus, one could hope to reuse the sub-protocols to build new protocols achieving different security, efficiency, and usability trade-offs. This is especially desirable in view of the community's current aim for group messaging, which has a significantly larger design space. However, the underlying ideas are usually not made explicit, but rather implicitly encoded in a (fairly complex) security game, primarily targeted at the overall security proof. This not only hinders modular protocol design, but also makes the suitability of a protocol for a particular application difficult to assess.

In this work we demonstrate that ratcheting components can be modeled in a composable framework, allowing for their reuse in a modular fashion. To this end, we first propose an extension of the Constructive Cryptography framework by so-called global event histories, to allow for a clean modularization even if the component modules are not fully independent but actually subtly intertwined, as in most ratcheting protocols. Second, we model a unified, flexibly instantiable type of strong security statement for secure messaging within that framework. Third, we show that one can phrase strong guarantees for a number of sub-protocols from the existing literature in this model with only minor modifications, slightly stronger assumptions, and reasonably intuitive formalizations.

When expressing existing protocols' guarantees in a simulation-based framework, one has to address the so-called commitment problem. We do so by reflecting the removal of access to certain oracles under specific conditions, appearing in game-based security definitions, in the real world of our composable statements. We also propose a novel non-committing protocol for settings where the number of messages a party can send before receiving a reply is bounded.

In this work we demonstrate that ratcheting components can be modeled in a composable framework, allowing for their reuse in a modular fashion. To this end, we first propose an extension of the Constructive Cryptography framework by so-called global event histories, to allow for a clean modularization even if the component modules are not fully independent but actually subtly intertwined, as in most ratcheting protocols. Second, we model a unified, flexibly instantiable type of strong security statement for secure messaging within that framework. Third, we show that one can phrase strong guarantees for a number of sub-protocols from the existing literature in this model with only minor modifications, slightly stronger assumptions, and reasonably intuitive formalizations.

When expressing existing protocols' guarantees in a simulation-based framework, one has to address the so-called commitment problem. We do so by reflecting the removal of access to certain oracles under specific conditions, appearing in game-based security definitions, in the real world of our composable statements. We also propose a novel non-committing protocol for settings where the number of messages a party can send before receiving a reply is bounded.

ePrint Report
Security-Efficiency Tradeoffs in Searchable Encryption -- Lower Bounds and Optimal Constructions
Raphael Bost, Pierre-Alain Fouque

Besides their security, the efficiency of searchable encryption schemes is a major criteria when it comes to their adoption: in order to replace an unencrypted database by a more secure construction, it must scale to the systems which rely on it. Unfortunately, the relationship between the efficiency and the security of searchable encryption has not been widely studied, and the minimum cost of some crucial security properties is still unclear.
In this paper, we present new lower bounds on the tradeoffs between the size of the client state, the efficiency and the security for searchable encryption schemes. These lower bounds target two kinds of schemes: schemes hiding the repetition of search queries, and forward-private dynamic schemes, for which updates are oblivious.
We also show that these lower bounds are tight, by either constructing schemes matching them, or by showing that even a small increase in the amount of leaked information allows for constructing schemes breaking the lower bounds.

ePrint Report
Synchronous Consensus with Optimal Asynchronous Fallback Guarantees
Erica Blum, Jonathan Katz, Julian Loss

Typically, protocols for Byzantine agreement (BA) are designed to run in either a synchronous network (where all messages are guaranteed to be delivered within some known time $\Delta$ from when they are sent) or an asynchronous network (where messages may be arbitrarily delayed). Protocols designed for synchronous networks are generally insecure if the network in which they run does not ensure synchrony; protocols designed for asynchronous networks are (of course) secure in a synchronous setting as well, but in that case tolerate a lower fraction of faults than would have been possible if synchrony had been assumed from the start.

Fix some number of parties $n$, and $0 < t_a < n/3 \leq t_s < n/2$. We ask whether it is possible (given a public-key infrastructure) to design a BA protocol that (1) is resilient to $t_s$ corruptions when run in a synchronous network and (2) remains resilient to $t_a$ faults even if the network happens to be asynchronous. We show matching feasibility and infeasibility results demonstrating that this is possible if and only if $t_a + 2\cdot t_s < n$.

Fix some number of parties $n$, and $0 < t_a < n/3 \leq t_s < n/2$. We ask whether it is possible (given a public-key infrastructure) to design a BA protocol that (1) is resilient to $t_s$ corruptions when run in a synchronous network and (2) remains resilient to $t_a$ faults even if the network happens to be asynchronous. We show matching feasibility and infeasibility results demonstrating that this is possible if and only if $t_a + 2\cdot t_s < n$.

This paper describes the limits of various "security proofs", using 36 lattice-based KEMs as case studies. This description allows the limits to be systematically compared across these KEMs; shows that some previous claims are incorrect; and provides an explicit framework for thorough security reviews of these KEMs.

ePrint Report
The Art of Guessing in Combined Side-Channel Collision Attacks
Changhai Ou, Siew-Kei Lam, Guiyuan Jiang

Recent combined collision attacks have shown promising results for exploiting side-channel leakage information from both divide-and-conquer and analytical distinguishers. However, divide-and-conquer distinguishers used such as Correlation Power Analysis (CPA) cannot directly provide the success probability of attack which impedes effective threshold setting for determining the candidate space. In particular, they uniformly demarcate the thresholds for all sub-keys, which restricts the candidate space that is able to be analyzed and increases the attack difficulty. Moreover, the existing works mainly focus on improving collision detection algorithms, and lacks theoretical basis. Finally, the inadequate use of collision information and backward fault-tolerant mechanism of existing schemes lead to low attack efficiency. To overcome these problems, this work first introduces guessing theory into Template Attack (TA) to facilitate the estimation of success probability and the corresponding complexity of key recovery. We also extend Multiple-Differential Collision Attack (MDCA) to a new combined collision attack named Multiple-Differential Combined Collision Filter (MDCCF), which achieves the multiple-differential voting mechanism via two levels: Distinguisher Voting (DV) and Collision Voting (CV). DV exploits the information from CPA, TA and Correlation enhanced Collision Attack (CCA) to filter the candidates of TA that fall within a threshold. CV further applies differential voting on the selected sub-keys with the smallest number of candidates to vote other sub-keys. The experimental results show that the proposed MDCCF significantly improves key ranking, reduces the candidate space and lowers the complexity of collision detection, without compromising on the success probability of attacks.

11
June
2019

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.

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.

ePrint Report
Better Bootstrapping for Approximate Homomorphic Encryption
Kyoohyung Han, Dohyeong Ki

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.

ePrint Report
General Linear Group Action on Tensors: A Candidate for Post-Quantum Cryptography
Zhengfeng Ji, Youming Qiao, Fang Song, Aaram Yun

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.

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.

ePrint Report
On the Complexity of Collision Resistant Hash Functions: New and Old Black-Box Separations
Nir Bitansky, Akshay Degwekar

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.

ePrint Report
Exploring NIST LWC/PQC Synergy with R5Sneik: How SNEIK 1.1 Algorithms were Designed to Support Round5
Markku-Juhani O. Saarinen

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.

ePrint Report
Revelio: A MimbleWimble Proof of Reserves Protocol
Arijit Dutta, Saravanan Vijayakumaran

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.

ePrint Report
The Notion of Transparency Order, Revisited
Huizhong Li, Yongbin Zhou, Jingdian Ming, Guang Yang, Chengbin Jin

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.

ePrint Report
Modern Family: A Revocable Hybrid Encryption Scheme Based on Attribute-Based Encryption, Symmetric Searchable Encryption and SGX
Alexandros Bakas, Antonis Michalas

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.

ePrint Report
Lattice-based Cryptography for IoT in A Quantum World: Are We Ready?
Ayesha Khalid, Sarah McCarthy, Weiqiang Liu, Maire O'Neill

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.

ePrint Report
Forgery Attacks on FlexAE and FlexAEAD
Maria Eichlseder, Daniel Kales, Markus Schofnegger

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.

ePrint Report
A Modified pqsigRM: RM Code-Based Signature Scheme
Yongwoo Lee, Wijik Lee, Young-Sik Kim, Jong-Seon No

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.

ePrint Report
A Note on Lower Digits Extraction Polynomial for Bootstrapping
Mingjia Huo, Kewen Wu, Qi Ye

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.

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.

ePrint Report
Robust and Scalable Consensus for Sharded Distributed Ledgers
Eleftherios Kokoris-Kogias

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.

6
June
2019

ePrint Report
Balance : Dynamic Adjustment of Cryptocurrency Deposits
Dominik Harz, Lewis Gudgeon, Arthur Gervais, William J. Knottenbelt

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.

ePrint Report
Polar Sampler: Discrete Gaussian Sampling over the Integers Using Polar Codes
Jiabo Wang, Cong Ling

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.