International Association
for Cryptologic Research

Profiled side-channel attacks are the most powerful attacks and they consist of two steps. The adversary first builds a leakage model, using a device similar to the target one, then it exploits this leakage model to extract the secret information from the victim's device. These attacks can be seen as a classification problem, where the adversary needs to decide to what class (corresponding to the secret key) the traces collected from the victim's devices belong. For a number of years, the research community studied profiled attacks and proposed numerous improvements. Despite a large number of empirical works, a framework with strong theoretical foundations to address profiled side-channel attacks is still missing.

In this paper, we propose a framework capable of modeling and evaluating all profiled analysis attacks. This framework is based on the expectation estimation problem that has strong theoretical foundations. Next, we quantify the effects of perturbations injected at different points in our framework through robustness analysis. Finally, we experimentally validate our framework using publicly available traces, several classifiers, and performance metrics.

The current paper improves the number of queries of the previous quantum multi-collision nding algorithms presented by Hosoyamada et al. at Asiacrypt 2017. Let $l$-collision be $l$ distinct inputs that result in the same output of a target function. The previous algorithm finds $l$-collisions by recursively calling the algorithm for finding $(l-1)$-collisions, and it achieves the query complexity of $O(N^{(3^{l-1}-1) / (2 \cdot 3^{l-1})})$. The new algorithm removes the redundancy of the previous recursive algorithm so that computations among different recursive calls can share a part of computations. The new algorithm achieves the query complexity of $\tilde{O}(N^{(2^{l-1}-1) / (2^{l}-1)})$. Moreover, it finds multiclaws for random functions, which are harder to find than multicollisions.

ProtonMail is an online email service that claims to offer end-to-end encryption such that "even [ProtonMail] cannot read and decrypt [user] emails." The service, based in Switzerland, offers email access via webmail and smartphone applications to over five million users as of November 2018. In this work, we provide the first independent analysis of ProtonMail's cryptographic architecture. We find that for the majority of ProtonMail users, no end-to-end encryption guarantees have ever been provided by the ProtonMail service and that the "Zero-Knowledge Password Proofs" are negated by the service itself. We also find and document weaknesses in ProtonMail's "Encrypt-to-Outside" feature. We justify our findings against well-defined security goals and conclude with recommendations.

A cryptosystem for granting/rescinding access permission is proposed, based on elliptic curve cryptography. The `Organizational Cryptosystem' grants access permission not by giving secret (decription) key to the corresponding user but by converting the ciphertext so that the user can decript with their secret key. The `conversion key' for the document, which is created from the secret key which the ciphertext has been originally encrypted for, the public key of the member who shall be permitted to read the ciphertext, and a part of the ciphertext. Therefore it is not possible to decrypt the ciphertext with the conversion key. Nor, for the administrator who issues the conversion key, to obtain any information about the plaintext.

Two of the most significant challenges in the design of blockchain protocols is increasing their transaction processing throughput and minimising latency in terms of transaction settlement. In this work we put forth for the first time a formal execution model that enables to express transaction throughput while supporting formal security arguments regarding safety and liveness. We then introduce parallel-chains, a simple yet powerful non-black-box composition technique for blockchain protocols. We showcase our technique by providing two parallel-chains protocol variants, one for the PoS and one for PoW setting, that exhibit optimal throughput under adaptive fail-stop corruptions while they retain their resiliency in the face of Byzantine adversity assuming honest majority of stake or computational power, respectively. We also apply our parallel-chains composition method to improve settlement latency; combining parallel composition with a novel transaction weighing mechanism we show that it is possible to scale down the time required for a transaction to settle by any given constant while maintaining the same level of security.

We construct non-interactive non-malleable commitments without setup in the plain model, under well-studied assumptions.

First, we construct non-interactive non-malleable commitments with respect to commitment for $\epsilon \log \log n$ tags for a small constant $\epsilon > 0$, under the following assumptions:

- Sub-exponential hardness of factoring or discrete log.

- Quantum sub-exponential hardness of learning with errors (LWE).

Second, as our key technical contribution, we introduce a new tag amplification technique. We show how to convert any non-interactive non-malleable commitment with respect to commitment for $\epsilon\log \log n$ tags (for any constant $\epsilon>0$) into a non-interactive non-malleable commitment with respect to replacement for $2^n$ tags. This part only assumes the existence of sub-exponentially secure non-interactive witness indistinguishable (NIWI) proofs, which can be based on sub-exponential security of the decisional linear assumption.

Interestingly, for the tag amplification technique, we crucially rely on the leakage lemma due to Gentry and Wichs (STOC 2011). For the construction of non-malleable commitments for $\epsilon \log \log n$ tags, we rely on quantum supremacy. This use of quantum supremacy in classical cryptography is novel, and we believe it will have future applications. We provide one such application to two-message witness indistinguishable (WI) arguments from (quantum) polynomial hardness assumptions.

Recently, Gross et al. demonstrated a first-order probing-secure implementation of AES using only two bits of randomness for both the initial sharing and the entire computation of AES. In this note, we recall that first-order probing security may not be sufficient for practical first-order security when randomness is re-cycled. We demonstrate that without taking the transitional leakage into account, the expected security level in a serialized design based on their concept might not be achieved in practice.

We present an efficient implementation of FrodoKEM-640 on an ARM Cortex-M4 core. We leverage the single instruction, multiple data paradigm, available in the instruction set of the ARM Cortex-M4, together with a careful analysis of the memory layout of matrices to considerably speed up matrix multiplications. Our implementations take up to 79.4% less cycles than the reference. Moreover, we challenge the usage of a cryptographically secure pseudorandom number generator for the generation of the large public matrix involved. We argue that statistically good pseudorandomness is enough to achieve the same security goal. Therefore, we propose to use xoshiro128** as a PRNG instead: its structure can be easily integrated in FrodoKEM-640, it passes all known statistical tests and greatly outperforms previous choices. By using xoshiro128** we improve the generation of the large public matrix, which is a considerable bottleneck for embedded devices, by up to 96%.

Group signature is a central tool for privacy-preserving protocols, ensuring authentication, anonymity and accountability. It has been massively used in cryptography, either directly or through variants such as direct anonymous attestations. However it remains a complex tool, especially in the standard model where each of its building blocks is quite costly to instantiate.

In this work, we propose a new group signature scheme proven secure in the standard model which significantly decreases the complexity with respect to the state-of-the-art. More specifically, we halve both the size and the computational cost compared to the most efficient alternative in the standard model. Moreover, our construction is also competitive against the most efficient ones in the random oracle model, thus closing the traditional efficiency gap between these two models.

Our construction is based on a tailored combination of two popular signatures, which avoids the explicit use of encryption schemes or zero-knowledge proofs. It is flexible enough to achieve security in different models and is thus suitable for most contexts.

The 2018 election has closed and 465 IACR members cast ballots to select three members of the Board of Directors.

The results are as follows.

Michel Abdalla 253
Nadia Heninger 203
Anna Lysyanskaya 178
Maria Naya Plasencia 170
Ran Canetti 155
Josh Benaloh 137
Satya Lokam 93

Congratulations to Michel, Nadia, and Anna, who will serve as IACR Directors for three-year terms commencing January 1, 2019, and thank you to Maria, Ran, Josh, and Satya for your contributions to the IACR and willingness to serve.

Audit info is available at the Helios election page.

In CHES 2017, Moradi et al. presented a paper on ``Bit-Sliding'' in which the authors proposed lightweight constructions for SPN based block ciphers like AES, Present and SKINNY. The main idea behind these constructions was to reduce the length of the datapath to 1 bit and to reformulate the linear layer for these ciphers so that they require fewer scan flip-flops (which have built-in multiplexer functionality and so larger in area as compared to a simple flip-flop). In this paper we take the idea forward: is it possible to construct the linear layer using only 2 scan flip-flops? Take the case of Present: in the language of mathematics, the above question translates to: can the Present permutation be generated by some ordered composition only two types of permutations? The question can be answered in the affirmative by drawing upon the theory of permutation groups. However straightforward constructions would require that the ``ordered composition'' consist of a large number of simpler permutations. This would naturally take a large number of clock cycles to execute in a flip-flop array having only two scan flip-flops and thus incur heavy loss of throughput.

In this paper we try to analyze SPN ciphers like Present and Gift that have a bit permutation as their linear layer. We tried to construct the linear layer of the cipher using as little clock cycles as possible. As an outcome we propose smallest known constructions for Present and Gift block ciphers for both encryption and combined encryption+decryption functionalities. We extend the above ideas to propose the first known construction of the Flip stream cipher.

Card-based protocols allow to evaluate an arbitrary fixed Boolean function $f$ on a hidden input to obtain a hidden output, without the executer learning anything about either of the two (e.g. Crépeau and Kilian, CRYPTO 1993). We explore the case where $f$ implements a universal function, i.e. $f$ is given the encoding $\langle P\rangle$ of a program $P$ and an input $x$ and computes $f(\langle P\rangle, x) = P(x)$. More concretely, we consider universal circuits, Turing machines, RAM machines, and branching programs, giving secure and conceptually simple card-based protocols in each case.

We argue that card-based cryptography can be performed in a setting that is only very weakly interactive, which we call the “surveillance” model. Here, when Alice executes a protocol on the cards, the only task of Bob is to watch that Alice does not illegitimately turn over cards and that she shuffles in a way that nobody knows anything about the total permutation applied to the cards. We believe that because of this very limited interaction, our results can be called program obfuscation.

As a tool, we develop a useful sub-protocol $\mathsf{sort}_{\Pi}X\mathop{\uparrow}Y$ that couples the two equal-length sequences $X, Y$ and jointly and obliviously permutes them with the permutation $\pi\in\Pi$ that lexicographically minimizes $\pi(X)$. We argue that this generalizes ideas present in many existing card-based protocols. In fact, AND, XOR, bit copy (Mizuki and Sone, FAW 2009), coupled rotation shuffles (Koch and Walzer, ePrint 2017) and the “permutation division” protocol of (Hashimoto et al., ICITS 2017) can all be expressed as “coupled sort protocols”.

A blockchain system is a replicated state machine that must be fault tolerant. When designing a blockchain system, there is usually a trade-off between decentralization, scalability, and security. In this paper, we propose a novel blockchain system, DEXON, which achieves high scalability while remaining decentralized and robust in the real-world environment.

We have two main contributions. First, we present a highly scalable sharding framework for blockchain. This framework takes an arbitrary number of single chains and transforms them into the blocklattice data structure, enabling high scalability and low transaction confirmation latency with asymptotically optimal communication overhead. Second, we propose a single-chain protocol based on our novel verifiable random function and a new Byzantine agreement that achieves high decentralization and low latency.

In this paper, we cryptanalyze the signature scheme Wave, which has recently appeared as a preprint. First, we show that there is a severe information leakage occurring from honestly-generated signatures. Then, we illustrate how to exploit this leakage to retrieve an alternative private key, which enables efficiently forging signatures for arbitrary messages. Our attack manages to break the proposed 128-bit secure Wave parameters in just over a minute, most of which is actually spent collecting genuine signatures. Finally, we explain how our attack applies to generalized versions of the scheme which could potentially be achieved using generalized admissible $(U,U+V)$ codes and larger field characteristics.

Permissionless blockchain systems, such as Bitcoin, rely on users using their computational power to solve a puzzle in order to achieve a consensus. To incentivise users in maintaining the system, newly minted coins are assigned to the user who solves this puzzle. A hardware race that has hence ensued among the users, has had a detrimental impact on the environment, with enormous energy consumption and increased global carbon footprint. On the other hand, proof of stake systems incentivise coin hoarding as players maximise their utility by holding their stakes. As a result, existing cryptocurrencies do not mimic the day-to-day usability of a fiat currency, but are rather regarded as cryptoassets or investment vectors.

In this work we initiate the study of minting mechanisms in cryptocurrencies as a primitive on its own right, and as a solution to prevent coin hoarding we propose a novel minting mechanism based on waiting-time first-price auctions. Our main technical tool is a protocol to run an auction over any blockchain. Moreover, our protocol is the first to securely implement an auction without requiring a semi-trusted party, i.e., where every miner in the network is a potential bidder. Our approach is generically applicable and we show that it is incentive-compatible with the underlying blockchain, i.e., the best strategy for a player is to behave honestly. Our proof-of-concept implementation shows that our system is efficient and scales to tens of thousands of bidders.

We speed up the isogeny-based ``SeaSign'' signature scheme recently proposed by De Feo and Galbraith. The core idea in SeaSign is to apply the ``Fiat–Shamir with aborts'' transform to the parallel repeated execution of an identification scheme based on CSIDH. We optimize this general transform by allowing the prover to not answer a limited number of said parallel executions, thereby lowering the overall probability of rejection. The performance improvement ranges between factors of approximately 4.4 and 65.7 for various instantiations of the scheme, at the expense of roughly doubling the signature sizes.

The notion of covert security for secure two-party computation serves as a compromise between the traditional semi-honest and malicious security definitions. Roughly, covert security ensures that cheating behavior is detected by the honest party with reasonable probability. It provides more realistic guarantees than semi-honest security with significantly less overhead than is required by malicious security.

The rationale for covert security is that it dissuades cheating by parties that care about their reputation and do not want to risk being caught. Further thought, however, shows that a much stronger disincentive is obtained if the honest party can generate a publicly verifiable certificate of misbehavior when cheating is detected. While the corresponding notion of publicly verifiable covert (PVC) security has been explored, existing PVC protocols are complex and less efficient than the best-known covert protocols, and have impractically large certificates.

We propose a novel PVC protocol that significantly improves on prior work. Our protocol uses only ``off-the-shelf'' primitives (in particular, it avoids signed oblivious transfer) and, for deterrence factor 1/2, has only 20-40% overhead (depending on the circuit size and network bandwidth) compared to state-of-the-art semi-honest protocols. Our protocol also has, for the first time, constant-size certificates of cheating (e.g., 354 bytes long at the 128-bit security level).

As our protocol offers strong security guarantees with low overhead, we suggest that it is the best choice for many practical applications of secure two-party computation.

SIMON and SPECK families of block ciphers are well-known lightweight ciphers designed by NSA. In this note, based on the previous investigations on SIMON, a closed formula for the squared correlations and differential probabilities of the mapping $\phi(x) = x \odot S^1(x)$ on $\mathbb{F}_2^n$ is given. From the aspects of linear and differential cryptanalysis, this mapping is equivalent to the core quadratic mapping of SIMON via rearrangement of coordinates and EA-equivalence. Based upon the proposed explicit formula, a full description of DDT and LAT of $\phi$ is provided. In the case of SPECK, as the only nonlinear operation in this family of ciphers is, addition mod $2^n$, after reformulating the formula for linear and differential probabilities of addition mod $2^n$, straightforward algorithms for finding the output masks with maximum squared correlation, given the input masks as well as the output differences with maximum differential probability, given the input differences, are presented.

Electronic toll collection (ETC) is widely used all over the world not only to finance our road infrastructures, but also to realize advanced features like congestion management and pollution reduction by means of dynamic pricing. Unfortunately, existing systems rely on user identification and allow tracing a user's movements. Several abuses of this personalized location data have already become public. In view of the planned European-wide interoperable tolling system EETS and the new EU General Data Protection Regulation, location privacy becomes of particular importance.

In this paper, we propose a flexible cryptographic model and protocol framework designed for privacy-preserving toll collection in the most dominant setting, i.e., Dedicated Short Range Communication (DSRC) ETC. As opposed to our work, most related cryptographic proposals target a less popular type of toll collection based on Global Navigation Satellite Systems (GNSS), and do not come with a thorough security model and proof. In fact, to the best of our knowledge, our system is the first in the DSRC setting with a (rigorous) security model and proof. A major challenge in designing the framework at hand was to combine provable security and practicality, where the latter includes practical performance figures and a suitable treatment of real-world issues, like broken on-board units etc.

For our ETC system, we make use of and significantly extend a payment protocol building block, called Black-Box Accumulators, introduced at ACM CCS 2017. Additionally, we provide a prototypical implementation of our system on realistic hardware. This implementation already features fairly practical performance figures, even though there is still room for optimizations. An interaction between an on-board unit and a road-side unit is estimated to take less than a second allowing for toll collection at full speed assuming one road-side unit per lane.

Proof-of-stake (PoS) protocols are emerging as one of the most promising alternative to the wasteful proof-of-work (PoW) protocols for consensus in Blockchains (or distributed ledgers).

However, current PoS protocols inherently disclose both the identity and the wealth of the stakeholders, and thus seem incompatible with privacy-preserving cryptocurrencies (such as ZCash, Monero, etc.).

In this paper we initiate the formal study for PoS protocols with privacy properties. Our results include:

- A (theoretical) feasibility result showing that it is possible to construct a general class of private PoS (PPoS) protocols; and to add privacy to a wide class of PoS protocols,

- A privacy-preserving version of a popular PoS protocol, Ouroboros Praos.

Towards our result, we define the notion of anonymous verifiable random function, which we believe is of independent interest.