International Association
for Cryptologic Research

This document details analyses of verifiability properties of the CH-Vote v1.3 electronic voting protocol, as defined by the preprint publication [12]. Informally, these properties are:

• Individual verifiability: a voter is convinced that a ballot confirmed as coming from the voter contains his intended vote • Ballot verifiability: all ballots that are confirmed contain correct votes • Eligibility uniqueness: there are no two distinct entries in the list of confirmed ballots which correspond to the same voter • Confirmed as intended: if a confirmed ballot is on the bulletin board for some voter, then that ballot records that voter’s voting intention • Universal verifiability: any party can verify that the votes on this board were tallied correctly

The analyses employ the currently well-established approach used within the scientific community. Specifically, they rely on mathematical abstractions for the adversary and for the system under analysis, as well as mathematical formulations of the properties to be established.

Mathematical proofs are then used to establish that (under certain assumptions) the security properties hold. We provide two types of analysis (which differ in the level of abstraction at which they operate). Part I contains a pen-and-paper computational/cryptographic analysis. Part II describes an automated symbolic analysis.

Broadly speaking, both the symbolic and the computational analyses conclude that CH-Vote satisfy the desired security properties under several assumptions. The assumptions include, for example, computational assumptions (which mathematical problems are assumed to be hard), trust assumptions (which parties, if any, are assumed to behave honestly and what are parties assume to know before they interact with the system).

Besides the concrete mathematical statements the analyses led to a number of recommendations which aim to improve the security. Part III concludes with a number of recommendations which reflect assumptions made in the analyses and weaknesses that were identified. The recommendations also sum up the results of a (light) code review of the code available via GitHub 1 – commit 9b0e7c9fcd409, from April 2017.

In this work, we study privacy-preserving storage primitives that are suitable for use in data analysis on outsourced databases within the differential privacy framework. The goal in differentially private data analysis is to disclose global properties of a group without compromising any individual’s privacy. Typically, differentially private adversaries only ever learn global properties. For the case of outsourced databases, the adversary also views the patterns of access to data. Oblivious RAM (ORAM) can be used to hide access patterns but ORAM might be excessive as in some settings it could be sufficient to be compatible with differential privacy and only protect the privacy of individual accesses.

We consider $(\epsilon, \delta)$-Differentially Private RAM, a weakening of ORAM that only protects individual operations and seems better suited for use in data analysis on outsourced databases. As differentially private RAM has weaker security than ORAM, there is hope that we can bypass the $\Omega(\log(n/c))$ bandwidth lower bounds for ORAM by Larsen and Nielsen [CRYPTO ’18] for storing an array of $n$ entries and a client with $c$ bits of memory. We answer in the negative and present an $\Omega(\log(n/c))$ bandwidth lower bound for privacy budgets of $\epsilon = O(1)$ and $\delta \le 1/3$.

The information transfer technique used for ORAM lower bounds does not seem adaptable for use with the weaker security guarantees of differential privacy. Instead, we prove our lower bounds by adapting the chronogram technique to our setting. To our knowledge, this is the first work that uses the chronogram technique for lower bounds on privacy-preserving storage primitives.

This work studies the problem of automatically penalizing intentional or unintentional data breach (APDB) by a receiver/custodian receiving confidential data from a sender. We solve this problem by augmenting a blockchain on-chain smart contract between the sender and receiver with an off-chain cryptographic protocol, such that any significant data breach from the receiver is penalized through a monetary loss. Towards achieving the goal, we develop a natural extension of oblivious transfer called doubly oblivious transfer (DOT) which, when combined with robust watermarking and a claim-or-refund blockchain contract provides the necessary framework to realize the APDB protocol in a provably secure manner. In our APDB protocol, a public data breach by the receiver leads to her Bitcoin (or other blockchain) private signing key getting revealed to the sender, which allows him to penalize the receiver by claiming the deposit from the claim-or-refund contract. Interestingly, the protocol also ensures that the malicious sender cannot steal the deposit, even as he knows the original document or releases it in any form. We implement our APDB protocol, develop the required smart contract for Bitcoin and observe our system to be efficient and easy to deploy in practice. We analyze our DOT-based design against partial adversarial leakages and observe it to be robust against even small leakages of data.

We present a simple, deterministic protocol for ledger consensus that tolerates Byzantine faults. The protocol is executed by $n$ servers over a synchronous network and can tolerate any number $t$ of Byzantine faults with $t<n/3$. Furthermore, the protocol can offer (i) transaction processing at full network speed, in the optimistic case where no faults occur, (ii) instant confirmation: the client can be assured in a single round-trip time that a submitted transaction will be settled, (iii) instant proof of settlement: the client can obtain a receipt that a submitted transaction will be settled. A derivative, equally simple, binary consensus protocol can be easily derived as well. We also analyze the protocol in case of network splits and temporary loss of synchrony arguing the safety of the protocol when synchrony is restored. Finally, we examine the covert adversarial model showing that Byzantine resilience is increased to $t<n/2$.

During the last decade, the blockchain space has exploded with a plethora of new cryptocurrencies, covering a wide array of different features, performance and security characteristics. Nevertheless, each of these coins functions in a stand-alone manner, independently. Sidechains have been envisioned as a mechanism to allow blockchains to communicate with one another and, among other applications, allow the transfer of value from one chain to another, but so far there have been no decentralized constructions. In this paper, we put forth the first sidechains construction that allows communication between proof-of-work blockchains without trusted intermediaries. Our construction is generic in that it allows the passing of any information between blockchains. It gives rise to two illustrative examples: the ``remote ICO,'' in which an investor pays in currency on one blockchain to receive tokens in another, and the ``two-way peg,'' in which an asset can be transferred from one chain to another and back. We pinpoint the features needed for two chains to communicate: On the source side, a proof-of-work blockchain that has been interlinked, potentially with a velvet fork; on the destination side, a blockchain with any consensus mechanism that has sufficient expressibility to implement verification. We model our construction mathematically and give a formal proof of security. In the heart of our construction, we use a recently introduced cryptographic primitive, Non-Interactive Proofs of Proof-of-Work (NIPoPoWs). Our security proof uses a standard reduction from our new proof-of-work sidechains protocol to the security of NIPoPoWs, which has, in turn, been shown to be secure in previous work. Our working assumption is honest majority in each of the communicating chains. We demonstrate the feasibility of our construction by providing a pseudocode implementation in the form of a Solidity smart contract.

A white-box cryptographic implementation is to defend against white-box attacks that allow access and modification of memory or internal resources in the computing device. In particular, linear and non-linear transformations applied to this table-based cryptographic implementation are used to prevent key-dependent intermediate values from being seen by white-box attackers. However, it has been shown that there is a correlation before and after the linear and non-linear transformations, so that even a gray-box attacker can reveal secret keys hidden in a white-box cryptographic implementation. In this paper, we focus on the problem of linear transformations including the characteristics of block invertible binary matrices and the distribution of intermediate values. Based on our observation, we find out that a random byte insertion in the intermediate values before linear transformations can eliminate a problematic correlation to the key, and propose our white-box AES implementation using this principle. Our proposed implementations reduce the memory requirement by at most 33 percent compared to the masked implementations and also slightly reduce the number of table lookups. In addition, our method is a non-masking technique and does not require a static or dynamic run-time random source, unlike the existing gray-box (power analysis) countermeasures.

Little theoretical work has been done on $(n,m)$-functions when $\frac {n}{2}<m<n$, even though these functions can be used in Feistel ciphers, and actually play an important role in several block ciphers. Nyberg has shown that the differential uniformity of such functions is bounded below by $2^{n-m}+2$ if $n$ is odd or if $m>\frac {n}{2}$. In this paper, we first characterize the differential uniformity of those $(n,m)$-functions of the form $F(x,z)=\phi(z)I(x)$, where $I(x)$ is the $(m,m)$-Inverse function and $\phi(z)$ is an $(n-m,m)$-function. Using this characterization, we construct an infinite family of differentially $\Delta$-uniform $(2m-1,m)$-functions with $m\geq 3$ achieving Nyberg's bound with equality, which also have high nonlinearity and not too low algebraic degree. We then discuss an infinite family of differentially $4$-uniform $(m+1,m)$-functions in this form, which leads to many differentially $4$-uniform permutations. We also present a method to construct infinite families of $(m+k,m)$-functions with low differential uniformity and construct an infinite family of $(2m-2,m)$-functions with $\Delta\leq2^{m-1}-2^{m-6}+2$ for any $m\geq 8$. The constructed functions in this paper may provide more choices for the design of Feistel ciphers.

We consider the issue of securing dark pools/markets in the financial services sector. These markets currently are executed via trusted third parties, leading to potential fraud being able to be conducted by the market operators. We present a potential solution to this problem by using Multi-Party Computation to enable a trusted third party to be emulated in software. Our experiments show that whilst the standard market clearing mechanism of Continuous Double Auction in lit markets is not currently viable when executed using MPC, a popular mechanism for evaluating dark markets, namely the volume matching methodology, is viable. We present experimental validation of this conclusion by presenting the expected throughputs for such markets in two popular MPC paradigms; namely the two party dishonest majority setting and the honest majority three party setting.

A signature scheme is said to be weakly unforgeable, if it is hard to forge a signature on a message not signed before. A signature scheme is said to be strongly unforgeable, if it is hard to forge a signature on any message. In some applications, the weak unforgeability is not enough and the strong unforgeability is required, e.g., the Canetti, Halevi and Katz transformation.

Leakage-resilience is a property which guarantees that even if secret information such as the secret-key is partially leaked, the security is maintained. Some security models with leakage-resilience have been proposed. The hard-to-invert leakage model, a.k.a. auxiliary (input) leakage model, proposed by Dodis et al. at STOC'09 is especially meaningful one, since the leakage caused by a function which information-theoretically reveals the secret-key, e.g., one-way permutation, is considered.

In this work, we propose a generic construction of digital signature strongly unforgeable and resilient to polynomially hard-to-invert leakage which can be instantiated under standard assumptions such as the decisional linear assumption. We emphasize that our instantiated signature is not only the first one resilient to polynomially hard-to-invert leakage under standard assumptions, but also the first one which is strongly unforgeable and has hard-to-invert leakage-resilience.

Since Cheon et al. introduced a homomorphic encryption scheme for approximate arithmetic (Asiacrypt ’17), it has been recognized as suitable for important real-life usecases of homomorphic encryption, including training of machine learning models over encrypted data. A follow up work by Cheon et al. (Eurocrypt ’18) described an approximate bootstrapping procedure for the scheme. In this work, we improve upon the previous bootstrapping result. We improve the amortized bootstrapping time per plaintext slot by two orders of magnitude, from &#8764; 1 second to &#8764; 0.01 second. To achieve this result, we adopt a smart level-collapsing technique for evaluating DFT-like linear transforms on a ciphertext. Also, we replace the Taylor approximation of the sine function with a more accurate and numerically stable Chebyshev approximation, and design a modified version of the Paterson-Stockmeyer algorithm for fast evaluation of Chebyshev polynomials over encrypted data.

Physical attacks are a known threat to secure embedded systems. Notable among these is laser fault injection, which is probably the most powerful fault injection technique. Indeed, powerful injection techniques like laser fault injection provide a high spatial accuracy, which enables an attacker to induce bit level faults. However, experience gained from attacking 8-bit targets might not be relevant on more advanced micro-architectures and these attacks become increasingly challenging on 32-bit microcontrollers. In this article, we show that the flash memory area of a 32-bit microcontroller is sensitive to laser fault injection. These faults occur during the instruction fetch process, hence the stored value remains unaltered. After a thorough characterisation of the induced faults and the associated fault model, we provide detailed examples of bit-level corruptions of instruction and demonstrate practical applications in compromising the security of real-life codes. Based on these experimental results, we formulate a hypothesis about the underlying micro-architectural features that could explain the observed fault model.

Homomorphic Encryption (HE) is a powerful cryptographic primitive to address privacy and security issues in outsourcing computation on sensitive data to an untrusted computation environment. Comparing to secure Multi-Party Computation (MPC), HE has advantages in supporting non-interactive operations and saving on communication costs. However, it has not come up with an optimal solution for modern learning frameworks, partially due to a lack of efficient matrix computation mechanisms.

In this work, we present a practical solution to encrypt a matrix homomorphically and perform arithmetic operations on encrypted matrices. Our solution includes a novel matrix encoding method and an efficient evaluation strategy for basic matrix operations such as addition, multiplication, and transposition. We also explain how to encrypt more than one matrix in a single ciphertext, yielding better amortized performance.

Our solution is generic in the sense that it can be applied to most of the existing HE schemes. It also achieves reasonable performance for practical use; for example, our implementation takes 9.21 seconds to multiply two encrypted square matrices of order 64 and 2.56 seconds to transpose a square matrix of order 64.

Our secure matrix computation mechanism has a wide applicability to our new framework EDM, which stands for encrypted data and encrypted model. To the best of our knowledge, this is the first work that supports secure evaluation of the prediction phase based on both encrypted data and encrypted model, whereas previous work only supported applying a plain model to encrypted data. As a benchmark, we report an experimental result to classify handwritten images using convolutional neural networks (CNN). Our implementation on the MNIST dataset takes 28.59 seconds to compute ten likelihoods of 64 input images simultaneously, yielding an amortized rate of 0.45 seconds per image.

Event date: 16 June to 21 June 2019
Submission deadline: 15 March 2019
Notification: 15 April 2019

The deadline for nominating IACR members for the 2019 IACR Fellows class is earlier than in previous years! As announced at the Eurocrypt and Crypto membership meetings, all nomination materials must be received by November 15.

The IACR Fellows Program recognizes outstanding IACR members for technical and professional contributions to the field of cryptology. Information about nominating a Fellow is available from the IACR Fellows website.

We present practical attacks against OCB2, an ISO-standard authenticated encryption (AE) scheme. OCB2 is a highly-efficient blockcipher mode of operation. It has been extensively studied and widely believed to be secure thanks to the provable security proofs. Our attacks allows the adversary to create forgeries with (almost-known) single encryption query. The source of our attacks is the way OCB2 implements AE using a tweakable blockcipher, called XEX*. We have verified our attacks using a reference code of OCB2. Our attacks do not break the privacy of OCB2, and are not applicable to the others, including OCB1 and OCB3.

Mimblewimble is an electronic cash system proposed by an anonymous author in 2016. It combines several privacy-enhancing techniques initially envisioned for Bitcoin, such as Confidential Transactions (Maxwell, 2015), non-interactive merging of transactions (Saxena, Misra, Dhar, 2014), and cut-through of transaction inputs and outputs (Maxwell, 2013). As a remarkable consequence, coins can be deleted once they have been spent while maintaining public verifiability of the ledger, which is not possible in Bitcoin. This results in tremendous space savings for the ledger and efficiency gains for new users, who must verify their view of the system.

In this paper, we provide a provable-security analysis for Mimblewimble. We give a precise syntax and formal security definitions for an abstraction of Mimblewimble that we call an aggregate cash system. We then formally prove the security of Mimblewimble in this definitional framework. Our results imply in particular that two natural instantiations (with Pedersen commitments and Schnorr or BLS signatures) are provably secure against inflation and coin theft under standard assumptions.

It is well established that the method of choice for implementing a side-channel secure modular inversion, is to use Fermat's little theorem. So $1/x = x^{p-2} \bmod p$. This can be calculated using any multiply-and-square method safe in the knowledge that no branching or indexing with potentially secret data (such as $x$) will be required. However in the case where the modulus $p$ is a pseudo-Mersenne, or Mersenne, prime of the form $p=2^n-c$, where $c$ is small, this process can be optimized to greatly reduce the number of multiplications required. Unfortunately an optimal solution must it appears be tailored specifically depending on $n$ and $c$. What appears to be missing from the literature is a near-optimal heuristic method that works reasonably well in all cases.

Signal is a famous secure messaging protocol used by billions of people, by virtue of many secure text messaging applications including Signal itself, WhatsApp, Facebook Messenger, Skype, and Google Allo. At its core it uses the concept of "double ratcheting," where every message is encrypted and authenticated using a fresh symmetric key; it has many attractive properties, such as forward security, post-compromise security, and "immediate (no-delay) decryption," which had never been achieved in combination by prior messaging protocols.

While the formal analysis of the Signal protocol, and ratcheting in general, has attracted a lot of recent attention, we argue that none of the existing analyses is fully satisfactory. To address this problem, we give a clean and general definition of secure messaging, which clearly indicates the types of security we expect, including forward security, post-compromise security, and immediate decryption. We are the first to explicitly formalize and model the immediate decryption property, which implies (among other things) that parties seamlessly recover if a given message is permanently lost---a property not achieved by any of the recent "provable alternatives to Signal." We build a modular "generalized Signal protocol" from the following components: (a) continuous key agreement (CKA), a clean primitive we introduce and which can be easily and generically built from public-key encryption (not just Diffie-Hellman as is done in the current Signal protocol) and roughly models "public-key ratchets;" (b) forward-secure authenticated encryption with associated data (FS-AEAD), which roughly captures "symmetric-key ratchets;" and (c) a two-input hash function that is a pseudorandom function (resp. generator with input) in its first (resp. second) input, which we term PRF-PRNG. As a result, in addition to instantiating our framework in a way resulting in the existing, widely-used Diffie-Hellman based Signal protocol, we can easily get post-quantum security and not rely on random oracles in the analysis.

We further show that our design can be elegantly extended to include other forms of "fine-grained state compromise" recently studied at CRYPTO'18, but without sacrificing the immediate decryption property. However, we argue that the additional security offered by these modifications is unlikely to justify the efficiency hit of using much heavier public-key cryptography in place of symmetric-key cryptography.

Whether there exist Almost Perfect Non-linear permutations (APN) operating on an even number of bit is the so-called Big APN Problem. It has been solved in the 6-bit case by Dillon et al. in 2009 but, since then, the general case has remained an open problem.

In 2016, Perrin et al. discovered the butterfly structure which contains Dillon et al.'s permutation over $\mathbb{F}_{2^6}$. Later, Canteaut et al. generalised this structure and proved that no other butterflies with exponent $3$ can be APN. Recently, Yongqiang et al. further generalized the structure with Gold exponent and obtained more differentially 4-uniform permutations with the optimal nonlinearity. However, the existence of more APN permutations in their generalization was left as an open problem.

In this paper, we adapt the proof technique of Canteaut et al. to handle all Gold exponents and prove that a generalised butterfly with Gold exponents over $\mathbb{F}_{2^{2n}}$ can never be APN when $n>3$. More precisely, we prove that such a generalised butterfly being APN implies that the branch size is strictly smaller than 5. Hence, the only APN butterflies operate on 3-bit branches, i.e. on 6 bits in total.

In this paper we focus on Polynomial Learning with Errors (PLWE). This problem is parametrized by a polynomial and we are interested in relating the hardness of the $\text{PLWE}^f$ and $\text{PLWE}^h$ problems for different polynomials $f$ and $h$. More precisely, our main result shows that for a fixed monic polynomial $f$, $\text{PLWE}^{f\circ g}$ is at least as hard as $\text{PLWE}^f$, in both search and decision variants, for any monic polynomial $g$. As a consequence, $\text{PLWE}^{\phi_n}$ is harder than $\text{PLWE}^{f},$ for a minimal polynomial $f$ of an algebraic integer from the cyclotomic field $\mathbb{Q}(\zeta_n)$ with specific properties. Moreover, we prove in decision variant that in the case of power-of-2 polynomials, $\text{PLWE}^{\phi_n}$ is at least as hard as $\text{PLWE}^f,$ for a minimal polynomial $f$ of algebraic integers from the $n$th cyclotomic field with weaker specifications than those from the previous result.