International Association
for Cryptologic Research

We initiate the study of message franking, recently introduced in Facebook’s end-to-end encrypted message system. It targets verifiable reporting of abusive messages to Facebook without compromising security guarantees. We capture the goals of message franking via a new cryptographic primitive: compactly committing authenticated encryption with associated data (AEAD). This is an AEAD scheme for which a small part of the ciphertext can be used as a cryptographic commitment to the message contents. Decryption provides, in addition to the message, a value that can be used to open the commitment. Security for franking mandates more than that required of traditional notions associated with commitment. Nevertheless, and despite the fact that AEAD schemes are in general not committing (compactly or otherwise), we prove that many in-use AEAD schemes can be used for message franking by using secret keys as openings. An implication of our results is the first proofs that several in-use symmetric encryption schemes are committing in the traditional sense. We also propose and analyze schemes that retain security even after openings are revealed to an adversary. One is a generalization of the scheme implicitly underlying Facebook’s message franking protocol, and another is a new construction that offers improved performance.

Memory encryption is used in many devices to protect memory content from attackers with physical access to a device. However, many current memory encryption schemes can be broken using Differential Power Analysis (DPA). In this work, we present MEAS---the first Memory Encryption and Authentication Scheme providing security against DPA attacks. The scheme combines ideas from fresh re-keying and authentication trees by storing encryption keys in a tree structure to thwart first-order DPA without the need for DPA-protected cryptographic primitives. Therefore, the design strictly limits the use of every key to encrypt at most two different plaintext values. MEAS prevents higher-order DPA without changes to the cipher implementation by using masking of the plaintext values. MEAS is applicable to all kinds of memory, e.g., NVM and RAM, and has memory overhead comparable to existing memory authentication techniques without DPA protection, e.g., 7.3% for a block size fitting standard disk sectors.

We present here a new code-based digital signature scheme. This scheme uses $(U|U+V)$ codes, where both $U$ and $V$ are random. We prove that the scheme achieves {\em existential unforgeability under adaptive chosen message attacks} under two assumptions from coding theory, both strongly related to the hardness of decoding in a random linear code. The proof imposes a uniform distribution on the produced signatures, we show that this distribution is easily and efficiently achieved by rejection sampling. Our scheme is efficient to produce and verify signatures. For a (classical) security of 128 bits, the signature size is less than one kilobyte and the public key size a bit smaller than 2 megabytes. This gives the first practical signature scheme based on binary codes which comes with a security proof and which scales well with the security parameter: it can be shown that if one wants a security level of $2^\lambda$, then signature size is of order $O(\lambda)$, public key size is of size $O(\lambda^2)$, signature generation cost is of order $O(\lambda^3)$, whereas signature verification cost is of order $O(\lambda^2)$.

In this paper we tackle the practical challenges of searching encrypted multimodal data (i.e. data containing multiple media formats), stored in public cloud servers, with minimal information leakage. To this end we propose MuSE, a Multimodal Searchable Encryption scheme that, by combining only standard cryptographic primitives and symmetric-key block ciphers, allows cloud-backed applications to dynamically store, update, and search multimodal datasets with privacy and efficiency guarantees. As searching encrypted data requires a tradeoff between privacy and efficiency, we propose a variant of MuSE that resorts to partially homomorphic encryption to further reduce information leakage, but at the cost of additional computational overhead. Both schemes are formally proven secure and experimentally evaluated regarding performance, scalability, and search precision. Experiments with realistic datasets show that our contributions achieve interesting levels of efficiency and privacy, making them suitable for practical application scenarios.

Leakage model plays a very important role in side channel attacks. An accurate leakage model greatly improves the efficiency of attacks. However, how to profile a "good enough" leakage model, or how to measure the accuracy of a leakage model, is seldom studied. Durvaux et al. proposed leakage certification tests to profile "good enough" leakage model for unmasked implementations. However, they left the leakage model profiling for protected implementations as an open problem. To solve this problem, we propose the first practical higher-order leakage model certification tests for masked implementations. First and second order attacks are performed on the simulations of serial and parallel implementations of a first-order fixed masking. A third-order attack is performed on another simulation of a second order random masked implementation. The experimental results show that our new tests can profile the leakage models accurately.

Forward privacy is a trending security notion of dynamic searchable symmetric encryption (DSSE). It guarantees the privacy of newly added data against the server who has knowledge of previous queries. The notion was very recently formalized by Bost (CCS '16) independently, yet the definition given is imprecise to capture how forward secure a scheme is. We further the study of forward privacy by proposing a generalized definition parametrized by a set of updates and restrictions on them. We then construct two forward private DSSE schemes over labeled bipartite graphs, as a generalization of those supporting keyword search over text files. The first is a generic construction from any DSSE, and the other is a concrete construction from scratch. For the latter, we designed a novel data structure called cascaded triangles, in which traversals can be performed in parallel while updates only affect the local regions around the updated nodes. Besides neighbor queries, our schemes support flexible edge additions and intelligent node deletions: The server can delete all edges connected to a given node, without having the client specify all the edges.

In the past two decades, targeted online advertising has led to massive data collection, aggregation, and exchange. This infrastructure raises significant privacy concerns. While several prominent theories of data privacy have been proposed over the same period of time, these notions have limited application to advertising ecosystems. Differential privacy, the most robust of them, is inherently inapplicable to queries about particular individuals in the dataset. We therefore formulate a new definition of privacy for accessing information about unknown individuals identified by some form of token that is chosen randomly but correlated with web interaction. Unlike most current privacy definitions, our's takes probabilistic prior information into account and is intended to reflect the use of aggregated web information for targeted advertising.

We explain how our theory captures the natural expectation of privacy in the advertising setting and avoids the limitations of existing alternatives. However, although we can construct artificial databases which satisfy our notion of privacy together with reasonable utility, we do not have evidence that real world databases can be sanitized to preserve reasonable utility. In fact we offer real world evidence that adherence to our notion of privacy almost completely destroys utility. Our results suggest that a significant theoretical advance or a change in infrastructure is needed in order to obtain rigorous privacy guarantees in the digital advertising ecosystem.

Attrapadung (Eurocrypt 2014) proposed a generic framework called pair encoding to simplify the design and proof of security of CPA-secure predicate encryption (PE) instantiated in composite order groups. Later Attrapadung (Asiacrypt 2016) extended this idea in prime order groups. Yamada et al. (PKC 2011, PKC 2012) and Nandi et al. (ePrint Archive: 2015/457, AAECC 2017) proposed generic conversion frameworks to achieve CCA-secure PE from CPA-secure PE provided the encryption schemes have properties like delegation or verifiability. The delegation property is harder to achieve and verifiability based conversion degrades the decryption performance due to a high number of additional pairing evaluations. Bl{\"o}mer et al. (CT-RSA 2016) proposed a direct fully CCA-secure predicate encryption in composite order groups but it was less efficient as it needed a large number of pairing evaluations to check ciphertext consistency. As an alternative, Nandi et al. (ePrint Archive: 2015/955) proposed a direct conversion technique in composite order groups. We extend the direct conversion technique of Nandi et al. in the prime order groups on the CPA-secure PE construction by Attrapadung (Asiacrypt 2016) and prove our scheme to be CCA-secure in a quite different manner. Our conversion technique incurs a cost of exactly three additional ciphertext components and only one additional unit pairing evaluation during decryption. This is a significant improvement over the available conversion mechanisms in prime order groups. We also have presented an alternative construction of direct CCA-secure predicate encryption scheme which is more efficient in the ciphertext size (only one additional ciphertext component) at the cost of increase in pairing evaluations (three additional unit precisely) required during decryption.

Bitcoin has proven to be very successful. The Bitcoin blockchain is backed up by a large-scale network of miners via proof-of-work mechanism. Unfortunately, these miners consume huge amount of non-recyclable resources (electricity and computing hardware). To address this issue, alternative blockchain constructions via proof-of-stake mechanism have been proposed. Unfortunately, those proposals either lack of security analysis or cannot scale to a large network of nodes in the open network setting where new players can safely join the blockchain protocol.

In this paper, we propose \iChing, the first scalable proof-of-stake blockchain in the open setting. We show that our blockchain protocol can achieve several important security properties including common prefix, chain quality, chain growth, and chain soundness.

The GMR-2 cipher is a kind of stream cipher currently being used in Inmarsat satellite phones. It has been proven that such cipher can be cracked using only one frame known keystream but with a moderate executing times. In this paper, we present a new thorough security analysis of the GMR-2 cipher. We first study the inverse properties and the relationship of the cipher's components to reveal a bad one-way character of the cipher. Then by introducing a new concept called "valid key chain" according to the cipher's key schedule, we for the first time propose a real-time inversion attack using one frame keystream. This attack contains three phases: (1) table generation (2) dynamic table looks-up, filtration and combination (3) verification. Our analysis shows that, using the proposed attack, the exhaustive search space for the 64-bit encryption key can be reduced to about $2^{13}$ when one frame (15 bytes) keystream is available. Compared with previous known attacks, this inversion attack is much more efficient. Finally, the proposed attack are carried out on a 3.3GHz platform, and the experimental results demonstrate that the 64-bit encryption-key could be recovered in around 0.02s on average.

—Traditional utility metering is to be replaced by smart metering. Smart metering enables very fine grained utility consumption measurements. These fine grained measurements raise privacy concerns due to the lifestyle information which can be inferred from the precise time at which utilities were consumed. This paper outlines two privacy respecting time of use billing protocols for smart metering. These protocols protect the privacy of customers by never transmitting the fine grained utility readings outside of the customer’s home network. One protocol favours complexity on the trusted smart meter hardware while the other uses homorphic commitments to offload computation to a third device. Both protocols are designed to operate on top of existing cryptographic secure channel protocols in place on smart meters. Proof of concept software implementations of these protocols have been written and their suitability for real world application to low performance smart meter hardware is discussed. These protocols may also have application to other privacy conscious aggregation systems such as electronic voting.

Universal forgery attack means that for any given message $M$, an adversary without the key can forge the corresponding Message Authentication Code (MAC) tag $\tau$, and the pair $(M,\tau)$ can be verified with probability 1. For a secure MAC, the universal forgery attack should be infeasible to be implemented, and the complexity is believed to be min{$(2^n, 2^k)$} queries, where $n$ is the tag length and $k$ is the key length of the MAC, respectively.

In this paper, we propose a general universal forgery attack framework to some blockcipher-based MACs and authenticated encryptions (AEs) using birthday attack, whose complexity is about $O(2^{n/2})$ queries in the classic setting. The attack shows that such MACs and AEs are totally insecure. However, this attack is not applicable in the quantum model, since no inclusion of period in the input messages is guaranteed.

We also propose another some generic universal forgery attacks using collision finding with structural input messages, by birthday paradox in the classic setting. Since our attacks are based on the collision finding with fixed but unknown differences (or period), such attack can also be implemented with only $O(n)$ queries using \textit{Simon's} algorithm in the quantum model, which shows that such MACs and AEs are completely broken in the quantum model.

Our attacks can be applied to CBC-MAC, XCBC, EMAC, OMAC, CMAC, PC-MAC, MT-MAC, XOR-MAC, PMAC, PMAC with parity, LightMAC and some of their variants. Moreover, such attacks are also applicable to the authenticated encryptions of the third round CAESAR candidates: CLOC, SILC, OCB, AEZ, OTR, COLM (including COPA and ELmD) and Deoxys.

In 1984, Goldreich, Goldwasser and Micali formalized the concept of pseudorandom functions and proposed a construction based on any length-doubling pseudorandom generator. Since then, pseudorandom functions have turned out to be an extremely influential abstraction, with applications ranging from message authentication to barriers in proving computational complexity lower bounds.

In this tutorial we survey various incarnations of pseudorandom functions, giving self-contained proofs of key results from the literature. Our main focus is on feasibility results and constructions, as well as on limitations of (and induced by) pseudorandom functions. Along the way we point out some open questions that we believe to be within reach of current techniques.

LoRaWAN is a worldwide deployed IoT security protocol. We provide an extensive analysis of the current 1.0 version and show that the protocol suffers from several weaknesses allowing to perform attacks, including practical ones. These attacks lead to breaches in the network availability, data integrity, and data confidentiality. Based on the inner weaknesses of the protocol, these attacks do not lean on potential implementation or hardware bugs. Likewise they do not entail a physical access to the targeted equipment and are independent from the means used to protect secret parameters. Finally we propose practical recommendations aiming at thwarting the attacks, while at the same time being compliant with the specification, and keeping the interoperability between patched and unmodified equipments.

We provide efficient constructions for trace-and-revoke systems with public traceability in the black-box confirmation model. Our constructions achieve adaptive security, are based on standard assumptions and achieve significant efficiency gains compared to previous constructions. Our constructions rely on a generic transformation from inner product functional encryption (IPFE) schemes to trace-and-revoke systems. Our transformation requires the underlying IPFE scheme to only satisfy a very weak notion of security-- the attacker may only request a bounded number of random keys -- in contrast to the standard notion of security where she may request an unbounded number of arbitrarily chosen keys. We exploit the much weaker security model to provide a new construction for bounded collusion and random key IPFE from the learning with errors assumption (LWE), which enjoys improved efficiency compared to the scheme of Agrawal et al. [CRYPTO'16]. Together with IPFE schemes from Agrawal et al., we obtain trace and revoke from LWE, Decision Diffie Hellman and Decision Quadratic Residuosity.

This paper presents a design of authenticated encryption (AE) focusing on minimizing the implementation size, i.e., hardware gates or working memory on software. The scheme is called COFB, for COmbined FeedBack. COFB uses an n-bit blockcipher as the underlying primitive, and relies on the use of a nonce for security. In addition to the state required for executing the underlying blockcipher, COFB needs only $n/2$ bits state as a mask. Till date, for all existing constructions in which masks have been applied, at least n bit masks have been used. Thus, we have shown the possibility of reducing the size of a mask without degrading the security level much. Moreover, it requires one blockcipher call to process one input block. We show COFB is provably secure up to $O(2^{n/2}/n)$ queries which is almost up to the standard birthday bound. We also present our hardware implementation results. Experimental implementation results suggest that our proposal has a good performance and the smallest footprint among all known blockcipher-based AE.

Software-update mechanisms are critical to the security of modern systems, but their typically centralized design presents a lucrative and frequently attacked target. In this work, we propose CHAINIAC, a decentralized software-update framework that eliminates single points of failure, enforces transparency, and provides efficient verifiability of integrity and authenticity for software-release processes. Independent $\textit{witness servers}$ collectively verify conformance of software updates to release policies, $\textit{build verifiers}$ validate the source-to-binary correspondence, and a tamper-proof release log stores collectively signed updates, thus ensuring that no release is accepted by clients before being widely disclosed and validated. The release log embodies a $\textit{skipchain}$, a novel data structure, enabling arbitrarily out-of-date clients to efficiently validate updates and signing keys.

Evaluation of our CHAINIAC prototype on reproducible Debian packages shows that the automated update process takes the average of 5 minutes per release for individual packages, and only 20 seconds for the aggregate timeline. We further evaluate the framework using real-world data from the PyPI package repository and show that it offers clients security comparable to verifying every single update themselves while consuming only one-fifth of the bandwidth and having a minimal computational overhead.

Lizard is a very recently proposed lightweight stream cipher that claims 60 bit security against distinguishing (related to state recovery) and 80 bit security against key recovery attack. This cipher has 121 bit state size. In this paper, we first note that using $\psi$ key stream bits one can recover $\psi$ unknown bits of the state when $\tau$ state bits are fixed to a specific pattern. This is made possible by guessing the remaining state bits. This helps us in mounting a TMDTO attack with preprocessing complexity $2^{67}$, and the maximum of Data, Time and Memory complexity during the online phase as $2^{54}$. The parameters in the online phase are significantly less than $2^{60}$.

Trust models are widely used in various computer science disciplines. The main purpose of a trust model is to continuously measure trustworthiness of a set of entities based on their behaviors. In this article, the novel notion of rational trust modeling is introduced by bridging trust management and game theory. Note that trust models/reputation systems have been used in game theory (e.g., repeated games) for a long time, however, game theory has not been utilized in the process of trust model construction; this is where the novelty of our approach comes from. In our proposed setting, the designer of a trust model assumes that the players who intend to utilize the model are rational/selfish, i.e., they decide to become trustworthy or untrustworthy based on the utility that they can gain. In other words, the players are incentivized (or penalized) by the model itself to act properly. The problem of trust management can be then approached by game theoretical analyses and solution concepts such as Nash equilibrium. Although rationality might be built-in in some existing trust models, we intend to formalize the notion of rational trust modeling from the designer's perspective. This approach will result in two fascinating outcomes. First of all, the designer of a trust model can incentivise trustworthiness in the first place by incorporating proper parameters into the trust function, which can be later utilized among selfish players in strategic trust-based interactions (e.g., e-commerce scenarios). Furthermore, using a rational trust model, we can prevent many well-known attacks on trust models. These two prominent properties also help us to predict behavior of the players in subsequent steps by game theoretical analyses.

We introduce SPHINCS-Simpira, which is a variant of the SPHINCS signature scheme with Simpira as a building block. SPHINCS was proposed by Bernstein et al. at EUROCRYPT 2015 as a hash-based signature scheme with post-quantum security. At ASIACRYPT 2016, Gueron and Mouha introduced the Simpira family of cryptographic permutations, which delivers high throughput on modern 64-bit processors by using only one building block: the AES round function. The Simpira family claims security against structural distinguishers with a complexity up to 2^128 using classical computers. In this document, we explain why the same claim can be made against quantum computers as well. Although Simpira follows a very conservative design strategy, our benchmarks show that SPHINCS-Simpira provides a 1.5x speed-up for key generation, a 1.4x speed-up for signing 59-byte messages, and a 2.0x speed-up for verifying 59-byte messages compared to the originally proposed SPHINCS-256.