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

6
July
2017

ePrint Report
Differential Fault Analysis Automation
Sayandeep Saha, Ujjawal Kumar, Debdeep Mukhopadhyay, Pallab Dasgupta

Characterization of all possible faults in a cryptosystem exploitable for fault attacks is a problem which is of both theoretical and practical interest for the cryptographic community. The complete knowledge of exploitable fault space is desirable while designing optimal countermeasures for any given crypto-implementation. In this paper, we address the exploitable fault characterization problem in the context of Differential Fault Analysis (DFA) attacks on block ciphers. The formidable size of the fault spaces demands an automated albeit fast mechanism for verifying each individual fault instance and neither the traditional, cipher-specific, manual DFA techniques nor the generic and automated Algebraic Fault Attacks (AFA) by Zhang et. al. in 2016, fulfill these criteria. Further, the diversified structures of different block ciphers suggest that such an automation should be equally applicable to any block cipher.
This work presents a completely automated framework for DFA identification, fulfilling all aforementioned criteria, which, instead of performing the attack, just estimates the attack complexity for each individual fault instance. A generic and extendable data-mining assisted dynamic analysis framework capable of capturing
a large class of DFA distinguishers is devised, along with a graph-based complexity analysis scheme. The framework significantly outperforms another recently proposed one by Khanna et. al. in DAC 2017, in terms of attack class coverage and automation effort. Experimental evaluation on AES and PRESENT establishes
the effectiveness of the proposed framework in detecting most of the known DFAs, which eventually enables the characterization of the exploitable fault space.

ePrint Report
Coding for interactive communication beyond threshold adversaries
Anat Paskin-Cherniavsky, Slava Radune

We revisit the setting of coding for interactive communication, CIC, (initiated by Schulman 96') for
non-threshold tampering functions. In a nutshell, in the (special case of) the communication complexity setting, Alice and Bob holding inputs $x,y$ wish to compute a function $g(x,y)$ on their inputs over the identity channel using an interactive protocol. The goal here is to minimize the total communication complexity (CC). A "code" for interactive communication is a compiler transforming any $\pi_0$
working in the communication complexity setting into a protocol $\pi$ evaluating the same function over any channel $f$ picked from a family $\mathcal{F}$. Here $f$ is a function modifying the entire communication transcript. The goal here is to minimize the code's
\emph{rate}, which is the CC overhead $CC(\pi)/CC(\pi_0)$ incurred by the compiler.

All previous work in coding for interactive communication considered error correction (that is, $g(x,y)$ must be recovered correctly with high probability), which puts a limit of corrupting up to a $1/4$ of the symbols (Braverman and Rao 11'). In this work, we initiate the study of CIC for non-threshold families. We first come up with a robustness notion both meaningful and achievable by CIC for interesting non-threshold families. As a test case, we consider $\mathcal{F}_{\text{bit}}$, where each bit of the codeword is modified independently of the other bits (and all bits can be modified). Our robustness notion is an enhanced form of error-detection, where the output of the protocol is distributed over $\{\bot,f(x,y)\}$, and the distribution does not depend on $x,y$. This definition can be viewed as enhancing error detection by non malleability (as in the setting of non-malleable codes introduced by Dzembowski et. al. 10'). We devise CIC for several interesting tampering families (including $\mathcal{F}_{\text{bit}}$). As a building block, we introduce the notion of MNMC (non malleable codes for multiple messages), which may be of independent interest.

All previous work in coding for interactive communication considered error correction (that is, $g(x,y)$ must be recovered correctly with high probability), which puts a limit of corrupting up to a $1/4$ of the symbols (Braverman and Rao 11'). In this work, we initiate the study of CIC for non-threshold families. We first come up with a robustness notion both meaningful and achievable by CIC for interesting non-threshold families. As a test case, we consider $\mathcal{F}_{\text{bit}}$, where each bit of the codeword is modified independently of the other bits (and all bits can be modified). Our robustness notion is an enhanced form of error-detection, where the output of the protocol is distributed over $\{\bot,f(x,y)\}$, and the distribution does not depend on $x,y$. This definition can be viewed as enhancing error detection by non malleability (as in the setting of non-malleable codes introduced by Dzembowski et. al. 10'). We devise CIC for several interesting tampering families (including $\mathcal{F}_{\text{bit}}$). As a building block, we introduce the notion of MNMC (non malleable codes for multiple messages), which may be of independent interest.

ePrint Report
Guru: Universal Reputation Module for Distributed Consensus Protocols
Alex Biryukov, Daniel Feher, Dmitry Khovratovich

In this paper we describe how to couple reputation systems with distributed consensus protocols to provide high-throughput highly-scalable consensus for large peer-to-peer networks of untrusted validators.
We introduce reputation module Guru, which can be laid on top of various consensus protocols such as PBFT or HoneyBadger. It ranks nodes based on the outcomes of consensus rounds run by a small committee, and adaptively selects the committee based on the current reputation. The protocol can also take external reputation ranking as input.
Guru can tolerate larger threshold of malicious nodes (up to slightly above 1/2) compared to the 1/3 limit of BFT consensus algorithms.

ePrint Report
Private Set Intersection for Unequal Set Sizes with Mobile Applications
Ágnes Kiss, Jian Liu, Thomas Schneider, N. Asokan, Benny Pinkas

Private set intersection (PSI) is a cryptographic technique that is applicable to many privacy-sensitive scenarios. For decades, researchers have been focusing on improving its efficiency in both communication and computation. However, most of the existing solutions are inefficient for an unequal number of inputs, which is common in conventional client-server settings.

In this paper, we analyze and optimize the efficiency of existing PSI protocols to support precomputation so that they can efficiently deal with such input sets. We transform four existing PSI protocols into the precomputation form such that in the setup phase the communication is linear only in the size of the larger input set, while in the online phase the communication is linear in the size of the smaller input set. We implement all four protocols and run experiments between two PCs and between a PC and a smartphone and give a systematic comparison of their performance. Our experiments show that a protocol based on securely evaluating a garbled AES circuit achieves the fastest setup time by several orders of magnitudes, and the fastest online time in the PC setting where AES-NI acceleration is available. In the mobile setting, the fastest online time is achieved by a protocol based on the Diffie-Hellman assumption.

In this paper, we analyze and optimize the efficiency of existing PSI protocols to support precomputation so that they can efficiently deal with such input sets. We transform four existing PSI protocols into the precomputation form such that in the setup phase the communication is linear only in the size of the larger input set, while in the online phase the communication is linear in the size of the smaller input set. We implement all four protocols and run experiments between two PCs and between a PC and a smartphone and give a systematic comparison of their performance. Our experiments show that a protocol based on securely evaluating a garbled AES circuit achieves the fastest setup time by several orders of magnitudes, and the fastest online time in the PC setting where AES-NI acceleration is available. In the mobile setting, the fastest online time is achieved by a protocol based on the Diffie-Hellman assumption.

5
July
2017

ePrint Report
Speeding up Elliptic Curve Scalar Multiplication without Precomputation
Kwang Ho Kim, Junyop Choe, Song Yun Kim, Namsu Kim, Sekung Hong

This paper presents a series of Montgomery scalar multiplication algorithms on general short Weierstrass curves over odd characteristic fields, which need only 12 field multiplications plus 12 ~ 20 field additions per scalar bit using 8 ~ 10 field registers, thus significantly outperform the binary NAF method on average. Over binary fields, the Montgomery scalar multiplication algorithm which was presented at the first CHES workshop by L´opez and Dahab has been a favorite of ECC implementors, due to its nice properties such as high efficiency outperforming the binary NAF, natural SPA-resistance, generality coping with all ordinary curves and implementation easiness. Over odd characteristic fields, the new scalar multiplication algorithms are the first ones featuring all these properties. Building-blocks of our contribution are new efficient differential addition-and-doubling formulae and a novel conception of on-the-fly adaptive coordinates which softly represent points occurring during a scalar multiplication not only in accordance with the basepoint but also bits of the given scalar. Importantly, the new algorithms are equipped with built-in countermeasures against known side-channel attacks, while it is shown that previous Montgomery ladder algorithms with the randomized addressing countermeasure fail to thwart attacks exploiting address-dependent leakage.

ePrint Report
Spot the Black Hat in a Dark Room: Parallelized Controlled Access Searchable Encryption on FPGAs
Sikhar Patranabis, Debdeep Mukhopadhyay

The advent of cloud computing offers clients with the opportunity to outsource storage and processing of large volumes of shared data to third party service providers, thereby enhancing overall accessibility and operational productivity. However, security concerns arising from the threat of insider and external attacks often require the data to be stored in an encrypted manner. Secure and efficient keyword searching on such large volumes of encrypted data is an important and yet one of the most challenging services to realize in practice. Even more challenging is to incorporate fine-grained client-specific access control - a commonly encountered requirement in cloud applications - in such searchable encryption solutions. Existing searchable encryption schemes in literature tend to focus on the use of specialized data structures for efficiency, and are not explicitly designed to address controlled access scenarios. In this paper, we propose a novel controlled access searchable encryption (CASE) scheme. As the name suggests, CASE inherently embeds access control in its key management process, and scales efficiently with increase in the volume of encrypted data handled by the system. We provide a concrete construction for CASE that is privacy-preserving under well-known cryptographic assumptions. We then present a prototype implementation for our proposed construction on an ensemble of Artix 7 FPGAs. The architecture for our implementation exploits the massively parallel capabilities provided by hardware, especially in the design of data structures for efficient storage and retrieval of data. The implementation requires a total of 192 FPGAs to support a document collection comprising of 100 documents with a dictionary of 1000 keywords. In addition, the hardware implementation of CASE is found to outperform its software counterpart in terms of both search efficiency and scalability. To the best of our knowledge, this is the first hardware implementation of a searchable encryption scheme to be reported in the literature.

ePrint Report
High-speed key encapsulation from NTRU
Andreas Hülsing, Joost Rijneveld, John Schanck, Peter Schwabe

This paper presents software demonstrating that the 20-year-old NTRU cryptosystem is competitive with more recent lattice-based cryptosystems in terms of speed, key size, and ciphertext size. We present a slightly simplified version of textbook NTRU, select parameters for this encryption scheme that target the 128-bit post-quantum security level, construct a KEM that is CCA2-secure in the quantum random oracle model, and present highly optimized software targeting Intel CPUs with the AVX2 vector instruction set. This software takes only 307914 cycles for the generation of a keypair, 48646 for encapsulation, and 67338 for decapsulation. It is, to the best of our knowledge, the first NTRU software with full protection against timing attacks.

ePrint Report
On Ends-to-Ends Encryption: Asynchronous Group Messaging with Strong Security Guarantees
Katriel Cohn-Gordon, Cas Cremers, Luke Garratt, Jon Millican, Kevin Milner

In the past few years secure messaging has become mainstream, with over a billion active users of
end-to-end encryption protocols through apps such as WhatsApp, Signal, Facebook Messenger, Google
Allo, Wire and many more. While these users' two-party communications now enjoy very strong
security guarantees, it turns out that many of these apps provide,
without notifying the users, a weaker property for
group messaging: an adversary who compromises a single group member can intercept
communications indefinitely.

One reason for this discrepancy in security guarantees is that most existing group messaging protocols are fundamentally synchronous, and thus cannot be used in the asynchronous world of mobile communications. In this paper we show that this is not necessary, presenting a design for a tree-based group key exchange protocol in which no two parties ever need to be online at the same time. Our design achieves strong security guarantees, in particular including post-compromise security.

We give a computational security proof for our core design as well as a proof-of-concept implementation, showing that it scales efficiently even to large groups. Our results show that strong security guarantees for group messaging are achievable even in the modern, asynchronous setting, without resorting to using inefficient point-to-point communications for large groups. By building on standard and well-studied constructions, our hope is that many existing solutions can be applied while still respecting the practical constraints of mobile devices.

One reason for this discrepancy in security guarantees is that most existing group messaging protocols are fundamentally synchronous, and thus cannot be used in the asynchronous world of mobile communications. In this paper we show that this is not necessary, presenting a design for a tree-based group key exchange protocol in which no two parties ever need to be online at the same time. Our design achieves strong security guarantees, in particular including post-compromise security.

We give a computational security proof for our core design as well as a proof-of-concept implementation, showing that it scales efficiently even to large groups. Our results show that strong security guarantees for group messaging are achievable even in the modern, asynchronous setting, without resorting to using inefficient point-to-point communications for large groups. By building on standard and well-studied constructions, our hope is that many existing solutions can be applied while still respecting the practical constraints of mobile devices.

ePrint Report
Lower bounds on communication for multiparty computation of multiple «AND» instances with secret sharing
Michael Raskin

The present report contains a proof of a linear lower bound for a typical three-party secure computation scheme of $n$ independent $AND$ functions. The goal is to prove some linear communication lower bound
for a maximally broad definition of «typical».

The article [DNPR] contains various communications lower bounds for unconditionally secure multiparty computation. In particular, it contains a linear lower bound for communication complexity of a regular parallel multiplication protocol using an ideal secret sharing scheme. These conditions mean that the protocol starts with the input being secret-shared with each share of each input field element being a field element, all combinations are used, and the output is shared in the same way as input.

In this report a weaker property of the secret sharing scheme that still allows to prove a linear (w.r.t. the number of multiplications) lower bound on communication is presented. Namely, if we have two (out of three) sides and two options for each party's shares and three possible combinations decode as the same value, the remaining combination should also be a valid pair of shares and reveal the same value.

The article [DNPR] contains various communications lower bounds for unconditionally secure multiparty computation. In particular, it contains a linear lower bound for communication complexity of a regular parallel multiplication protocol using an ideal secret sharing scheme. These conditions mean that the protocol starts with the input being secret-shared with each share of each input field element being a field element, all combinations are used, and the output is shared in the same way as input.

In this report a weaker property of the secret sharing scheme that still allows to prove a linear (w.r.t. the number of multiplications) lower bound on communication is presented. Namely, if we have two (out of three) sides and two options for each party's shares and three possible combinations decode as the same value, the remaining combination should also be a valid pair of shares and reveal the same value.

ePrint Report
Message Franking via Committing Authenticated Encryption
Paul Grubbs, Jiahui Lu, Thomas Ristenpart

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.

ePrint Report
Securing Memory Encryption and Authentication Against Side-Channel Attacks Using Unprotected Primitives
Thomas Unterluggauer, Mario Werner, Stefan Mangard

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.

ePrint Report
A new signature scheme based on (U|U+V) codes
Thomas Debris-Alazard , Nicolas Sendrier, Jean-Pierre Tillich

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)$.

ePrint Report
MuSE: Multimodal Searchable Encryption for Cloud Applications
Bernardo Ferreira, João Leitão, Henrique Domingos

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.

ePrint Report
Profiling Good Leakage Models For Masked Implementations
Changhai Ou, Zhu Wang, Degang Sun, Xinping Zhou

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.

ePrint Report
Forward-Secure Searchable Encryption on Labeled Bipartite Graphs
Russell W. F. Lai, Sherman S. M. Chow

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.

ePrint Report
Privacy for Targeted Advertising
Avradip Mandal, John Mitchell, Hart Montgomery, Arnab Roy

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.

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.

ePrint Report
CCA-secure Predicate Encryption from Pair Encoding in Prime Order Groups: Generic and Efficient
Sanjit Chatterjee, Sayantan Mukherjee, Tapas Pandit

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.

ePrint Report
iChing: A Scalable Proof-of-Stake Blockchain in the Open Setting (or, How to Mimic Nakamoto's Design via Proof-of-Stake)
Lei Fan, Hong-Sheng Zhou

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.

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.

ePrint Report
A Real-time Inversion Attack on the GMR-2 Cipher Used in the Satellite Phones
Jiao Hu, Ruilin Li, Chaojing Tang

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.

ePrint Report
Universal Forgery with Birthday Paradox: Application to Blockcipher-based Message Authentication Codes and Authenticated Encryptions
Fanbao Liu, Fengmei Liu

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 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.

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.

ePrint Report
Efficient Public Trace and Revoke from Standard Assumptions
Shweta Agrawal, Sanjay Bhattacherjee, Duong Hieu Phan, Damien Stehle, Shota Yamada

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.

ePrint Report
Blockcipher-based Authenticated Encryption: How Small Can We Go?
Avik Chakraborti, Tetsu Iwata, Kazuhiko Minematsu, Mridul Nandi

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.

ePrint Report
CHAINIAC: Proactive Software-Update Transparency via Collectively Signed Skipchains and Verified Builds
Kirill Nikitin, Eleftherios Kokoris-Kogias, Philipp Jovanovic, Linus Gasser, Nicolas Gailly, Ismail Khoffi, Justin Cappos, Bryan Ford

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.

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.

ePrint Report
A TMDTO Attack Against Lizard
Subhamoy Maitra, Nishant Sinha, Akhilesh Siddhanti, Ravi Anand, Sugata Gangopadhyay

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.

ePrint Report
SPHINCS-Simpira: Fast Stateless Hash-based Signatures with Post-quantum Security
Shay Gueron, Nicky Mouha

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.

In this paper we study space-scarce economy in massively replicated open blockchain systems. In these systems, such as Bitcoin, memory to hold a current state snapshot needed to validate transactions becomes the most scarce resource eventually. The issue is even more critical for blockchain systems used to store data~(votes, certificates, logs etc.). Uncontrolled state size growth could lead to security issues, such as denial-of-service attacks. Only technical solutions, not economic, have been proposed to tackle this problem to the moment. In contrast, we propose to add a new component to a transaction fee scheme based on how much additional space will be needed for new objects created in result of transaction processing and for how long they will live in the state. We provide three possible options towards implementing the new fee component, namely prepaid outputs, postpaid outputs and scheduled payments. We provide an analysis of the model with respect to all the three options. We show that the state growth could be bounded by a fee factor, miners are getting additional stable rewards and lost coins are being taken back into circulation eventually.