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

18
July
2017

ePrint Report
Impossibility of Secure Multi-Party Products in Non-Abelian Groups
Jessica Covington, Megan Golbek, Mike Rosulek

Suppose $n$ parties have respective inputs $x_1, \ldots, x_n \in \mathbb{G}$, where $\mathbb{G}$ is a finite group. The parties would like to privately compute $x_1 x_2 \cdots x_n$ (where multiplication refers to the group operation in $\mathbb{G}$). There is a well-known secure protocol that works for any number of parties $n$ when $\mathbb{G}$ is abelian.
In this note we consider private group-product protocols for non-abelian groups. We show that such protocols are possible for if and only if $n$ (the number of parties) is less than 4.

ePrint Report
On the Necessity of a Prescribed Block Validity Consensus: Analyzing Bitcoin Unlimited Mining Protocol
Ren Zhang, Bart Preneel

Bitcoin has not only attracted many users but also been considered as a technical breakthrough by academia. However, the expanding potential of Bitcoin is largely untapped due to its limited throughput. The Bitcoin community is now facing its biggest crisis in history as the community splits on how to increase the throughput. Among various proposals, Bitcoin Unlimited recently becomes a most popular candidate, as it allows miners to collectively decide the block size limit according to the real network capacity. However, the security of BU is heatedly debated and no consensus has been reached as the issue is discussed in different miner incentive models. In this paper, we systematically evaluate BU's security with three incentive models via testing the two major arguments of BU supporters: the block validity consensus is not necessary for BU's security; such consensus would emerge in BU on the run. Our results invalidate both arguments and therefore disprove BU's security claims. Our paper further contributes to the field by addressing the necessity of a prescribed block validity consensus for cryptocurrencies.

ePrint Report
Compact-LWE: Enabling Practically Lightweight Public Key Encryption for Leveled IoT Device Authentication
Dongxi Liu, Nan Li, Jongkil Kim, Surya Nepal

Leveled authentication allows resource-constrained IoT devices to be authenticated at different strength levels according to the particular types of communication. To achieve efficient leveled authentication, we propose a lightweight public key encryption scheme that can produce very short ciphertexts without sacrificing its security.

The security of our scheme is based on the Learning With Secretly Scaled Errors in Dense Lattice (referred to as Compact-LWE) problem. We prove the hardness of Compact-LWE by reducing Learning With Errors (LWE) to Compact-LWE. However, unlike LWE, even if the closest vector problem (CVP) in lattices can be solved, Compact-LWE is still hard, due to the high density of lattices constructed from Compact-LWE samples and the relatively longer error vectors. By using a lattice-based attack tool, we verify that the attacks, which are successful on LWE instantly, cannot succeed on Compact-LWE, even for a small dimension parameter like $n=13$, hence allowing small dimensions for short ciphertexts.

On the Contiki operating system for IoT, we have implemented our scheme, with which a leveled Needham-Schroeder-Lowe public key authentication protocol is implemented. On a small IoT device with 8MHZ MSP430 16-bit processor and 10KB RAM, our experiment shows that our scheme can complete 50 encryptions and 500 decryptions per second at a security level above 128 bits, with a public key of 2368 bits, generating 176-bit ciphertexts for 16-bit messages. With two small IoT devices communicating over IEEE 802.15.4 and 6LoWPAN, the total time of completing an authentication varies from 640ms (the 1st authentication level) to 8373ms (the 16th authentication level), in which the execution of our encryption scheme takes only a very small faction from 46ms to 445ms.

The security of our scheme is based on the Learning With Secretly Scaled Errors in Dense Lattice (referred to as Compact-LWE) problem. We prove the hardness of Compact-LWE by reducing Learning With Errors (LWE) to Compact-LWE. However, unlike LWE, even if the closest vector problem (CVP) in lattices can be solved, Compact-LWE is still hard, due to the high density of lattices constructed from Compact-LWE samples and the relatively longer error vectors. By using a lattice-based attack tool, we verify that the attacks, which are successful on LWE instantly, cannot succeed on Compact-LWE, even for a small dimension parameter like $n=13$, hence allowing small dimensions for short ciphertexts.

On the Contiki operating system for IoT, we have implemented our scheme, with which a leveled Needham-Schroeder-Lowe public key authentication protocol is implemented. On a small IoT device with 8MHZ MSP430 16-bit processor and 10KB RAM, our experiment shows that our scheme can complete 50 encryptions and 500 decryptions per second at a security level above 128 bits, with a public key of 2368 bits, generating 176-bit ciphertexts for 16-bit messages. With two small IoT devices communicating over IEEE 802.15.4 and 6LoWPAN, the total time of completing an authentication varies from 640ms (the 1st authentication level) to 8373ms (the 16th authentication level), in which the execution of our encryption scheme takes only a very small faction from 46ms to 445ms.

ePrint Report
Z-Channel: Scalable and Efficient Scheme in Zerocash
Yuncong Zhang, Yu Long, Zhen Liu, Zhiqiang Liu, Dawu Gu

Decentralized ledger-based cryptocurrencies such as Bitcoin provide a means to construct payment systems without requiring a trusted bank, yet the anonymity of Bitcoin is proved to be far from enough. Zerocash is the first full-fledged anonymouse digital currency based on the blockchain technology, using zk-SNARK as the zero-knowledge module for the privacy preserving. Zerocash solves the privacy problem but also brings some other issues, including insufficient scalability as in Bitcoin. Meanwhile, Lightning network proves to be a nice solution to solve the scalability problem in Bitcoin. However, to employ the idea of lightning network in Zerocash is a great challenge due to the lack of programmability of Zerocash.
We modify the Zerocash scheme to implement multisignature scheme and the lock time mechanism without compromising the privacy guarantee provided by Zerocash. With these two mechanisms, we present the construction of micropayment system Z-Channel on the basis of Zerocash.
The Z-Channel system effectively solves the scalability and instant payment problems in Zerocash.

Edit distance is an important non-linear metric that has many applications ranging from matching patient genomes to text-based intrusion detection. Privacy-preserving edit distance protocols have been a long-standing goal of many security researchers. In this paper, we propose efficient secure computation protocols for private edit distance as well as several generalized applications including weighted edit distance (with potentially content-dependent weights), longest common subsequence, and heaviest common subsequence. Our protocols run 20+ times faster and use an order-of-magnitude less bandwidth than their best previous counterparts. Alongside, we propose a garbling scheme that allows free arithmetic addition, free multiplication with constants, and low-cost comparison/minimum for inputs of restricted relative-differences. Moreover, the encodings (i.e. wire- labels) in our garbling scheme can be converted from and to encodings used by traditional binary circuit garbling schemes with light to moderate costs. Therefore, while being extremely efficient on certain kinds of computations, the new garbling scheme remains composable and capable of handling generic computational tasks, hence may be of independent interest.

ePrint Report
Conditional Blind Signatures
Alexandros Zacharakis, Panagiotis Grontas, Aris Pagourtzis

We propose a novel cryptographic primitive that we call conditional blind signatures. Our primitive allows a user to request blind signatures on messages of her choice. The signer has a secret Boolean
input which determines if the supplied signature is valid or not. The user should not be able to distinguish between valid and invalid signatures. A designated verifier, however, can tell which signatures verify correctly, and is in fact the only entity who can learn the secret input associated with the signed message after the unblinding process. We instantiate our primitive as an extension of the Okamoto-Schnorr blind signature scheme. We analyze and prove the security properties of the new scheme and explore potential applications.

ePrint Report
CONTROLLED-NOT FUNCTION CAN PROVOKE BIASED INTERPRETATION FROM BELL'S TEST EXPERIMENTS
Alexandre de Castro

Recently, we showed that the controlled-NOT function is a permutation that cannot be inverted in subexponential time in the worst case [Quantum Information Processing. 16:149 (2017)]. Here, we show that such a condition can provoke biased interpretations from Bell’s test experiments.

ePrint Report
SOFIA: MQ-based signatures in the QROM
Ming-Shing Chen, Andreas Hülsing, Joost Rijneveld, Simona Samardjiska, Peter Schwabe

We propose SOFIA, the first MQ-based signature scheme provably secure in the quantum-accessible random oracle model (QROM). Our construction relies on an extended version of Unruh's transform for 5-pass identification schemes that we describe and prove secure both in the ROM and QROM.

Based on a detailed security analysis, we provide concrete parameters for SOFIA that achieve 128 bit post-quantum security. The result is SOFIA-4-128 with parameters that are carefully optimized to minimize signature size and maximize performance. SOFIA-4-128 comes with an implementation targeting recent Intel processors with the AVX2 vector-instruction set; the implementation is fully protected against timing attacks.

Based on a detailed security analysis, we provide concrete parameters for SOFIA that achieve 128 bit post-quantum security. The result is SOFIA-4-128 with parameters that are carefully optimized to minimize signature size and maximize performance. SOFIA-4-128 comes with an implementation targeting recent Intel processors with the AVX2 vector-instruction set; the implementation is fully protected against timing attacks.

Outsourcing data to the cloud is becoming increasingly prevalent. To ensure data confidentiality, encrypting the data before outsourcing it is advised. While encryption protects the secrets in the data, it also prevents operations on the data. For example in a multi-user setting, data is often accessed via search, but encryption prevents search. Searchable encryption solves this dilemma. However, in a multi-user setting not all users may be allowed to access all data, requiring some means of access control. We address the question how searchable encryption and access control can be combined. Combining these technologies is required to achieve strong notions of confidentiality: if a ciphertext occurs as a search result, we learn something about the underlying document, even if access control does not let us access
the document. This illustrates a need to link search and access control, so that search results presented to users only feature data the users are allowed to access. Our searchable encryption scheme with access control establishes that link.

12
July
2017

ePrint Report
Differential Fault Attack on Grain v1, ACORN v3 and Lizard
Akhilesh Anilkumar Siddhanti, Santanu Sarkar, Subhamoy Maitra, Anupam Chattopadhyay

Differential Fault Attack (DFA) is presently a very well known technique to evaluate security of a stream cipher. This considers that the stream cipher can be weakened by injection of the fault. In this paper we study DFA on three ciphers, namely Grain v1, Lizard and ACORN v3. We show that Grain v1 (an eStream cipher) can be attacked with injection of only 5 faults instead of 10 that has been reported in 2012. For the first time, we have mounted the fault attack on Lizard, a very recent design and show that one requires only 5 faults to obtain the state. ACORN v3 is a third round candidate of CAESAR and there is only one hard fault attack on an earlier version of this cipher. However, the `hard fault' model requires a lot more assumption than the generic DFA. In this paper, we mount a DFA on ACORN v3 that requires 9 faults to obtain the state. In case of Grain v1 and ACORN v3, we can obtain the secret key once the state is known. However, that is not immediate in case of Lizard. While we have used the basic framework of DFA that appears in literature quite frequently, specific tweaks have to be explored to mount the actual attacks that were not used earlier. To the best of our knowledge, these are the best known DFA on these three ciphers.

ePrint Report
Unbalanced Approximate Private Set Intersection
Amanda Cristina Davi Resende, Diego F. Aranha

Protocols for Private Set Intersection (PSI) are an important cryptographic primitive to perform joint operations on datasets in a privacy-preserving way. They allow two entities to compute the intersection of their private sets without revealing any additional information beyond the intersection, which can be learned by only one of the parties, as in one-way PSI protocols, or by both parties in mutual PSI protocols. In addition, the PSI setting may be unbalanced when one set is substantially smaller than the other or balanced when the sets have approximately the same size. However, even with several PSI protocols already proposed, applications keep using insecure naive approaches that are more efficient in both run time and communication. To make matters worse, implementations in the literature do not use the best possible implementation techniques, especially when implementing PSI protocols instantiated with curve-based public-key cryptography. This paper proposes an efficient one-way PSI protocol based on public-key cryptography for the unbalanced scenario. Security is based on the hardness of the One-More-Gap-Diffie-Hellman (OMGDH) problem against semi-honest adversaries and includes forward secrecy on the client side. A Cuckoo filter is also used to reduce the amount of data exchanged and stored by the client. Our implementation employs the state-of-the-art Galbraith-Lin-Scot (GLS-254) binary elliptic curve with point compression.

ePrint Report
Dynamic Verifiable Encrypted Keyword Search Using Bitmap Index and Homomorphic MAC
Rajkumar Ramasamy, S.Sree Vivek, Praveen George, Bharat S. Rawal Kshatriya

Outsourcing data storage to the cloud securely and retrieving the remote data in an efficient way is a very significant research topic, with high relevance to secure cloud deployment. With the ever growing security and privacy concerns, encrypting the data stored remotely is inevitable but using traditional encryption thwarts performing search operation on the encrypted data. Encrypted keyword search is a cryptographic setting, which offers search functionality and at the same time, ensures security and privacy of the remotely stored data.

Searchable Symmetric Encryption (SSE) is a technique to securely outsource the data, which is encrypted using symmetric key primitives, while maintaining search functionality. While several solutions have been proposed to realize SSE over various data structures, the efficient solution using inverted index is due to Curtmola et.al. Hwang et.al. introduced a SSE scheme based on bitmaps in-order to reduce the index size.

In this paper, we consider Searchable Symmetric Encryption (SSE) in the presence of a Semi-Honest-But-Curious Cloud Service Provider (SHBC-CSP). We have defined a new security notion for SSE in presence of SHBC-CSP, contrived two new SSE schemes and proved their security formally in the proposed security notion. Dynamic Verifiable Encrypted Keyword Search (DVSSE), is the first SSE scheme to the best of our knowledge, which is both dynamic and verifiable. We have implemented our schemes, compared their performance and complexity with existing schemes.

Searchable Symmetric Encryption (SSE) is a technique to securely outsource the data, which is encrypted using symmetric key primitives, while maintaining search functionality. While several solutions have been proposed to realize SSE over various data structures, the efficient solution using inverted index is due to Curtmola et.al. Hwang et.al. introduced a SSE scheme based on bitmaps in-order to reduce the index size.

In this paper, we consider Searchable Symmetric Encryption (SSE) in the presence of a Semi-Honest-But-Curious Cloud Service Provider (SHBC-CSP). We have defined a new security notion for SSE in presence of SHBC-CSP, contrived two new SSE schemes and proved their security formally in the proposed security notion. Dynamic Verifiable Encrypted Keyword Search (DVSSE), is the first SSE scheme to the best of our knowledge, which is both dynamic and verifiable. We have implemented our schemes, compared their performance and complexity with existing schemes.

11
July
2017

Cryptographic reductions typically aim to be tight by transforming an adversary A into an algorithm that uses essentially the same resources as A. In this work we initiate the study of memory efficiency in reductions. We argue that the amount of working memory used (relative to the initial adversary) is a relevant parameter in reductions, and that reductions that are inefficient with memory will sometimes yield less meaningful security guarantees. We then point to several common techniques in reductions that are memory-inefficient and give a toolbox for reducing memory usage. We review common cryptographic assumptions and their sensitivity to memory usage. Finally, we prove an impossibility result showing that reductions between some assumptions must unavoidably be either memory- or time-inefficient. This last result follows from a connection to data streaming algorithms for which unconditional memory lower bounds are known.

6
July
2017

ePrint Report
Transparent Memory Encryption and Authentication
Mario Werner, Thomas Unterluggauer, Robert Schilling, David Schaffenrath, Stefan Mangard

Security features of modern (SoC) FPAGs permit to protect the confidentiality of hard- and software IP when the devices are powered off as well as to validate the authenticity of IP when being loaded at startup. However, these approaches are insufficient since attackers with physical access can also perform attacks during runtime, demanding for additional security measures. In particular, RAM used by modern (SoC) FPGAs is under threat since RAM stores software IP as well as all kinds of other sensitive information during runtime.

To solve this issue, we present an open-source framework for building transparent RAM encryption and authentication pipelines, suitable for both FPGAs and ASICs. The framework supports various ciphers and modes of operation as shown by our comprehensive evaluation on a Xilinx Zynq-7020 SoC. For encryption, the ciphers Prince and AES are used in the ECB, CBC and XTS mode. Additionally, the authenticated encryption cipher Ascon is used both standalone and within a TEC tree. Our results show that the data processing of our encryption pipeline is highly efficient with up to 94% utilization of the read bandwidth that is provided by the FPGA interface. Moreover, the use of a cryptographically strong primitive like Ascon yields highly practical results with 54% bandwidth utilization.

To solve this issue, we present an open-source framework for building transparent RAM encryption and authentication pipelines, suitable for both FPGAs and ASICs. The framework supports various ciphers and modes of operation as shown by our comprehensive evaluation on a Xilinx Zynq-7020 SoC. For encryption, the ciphers Prince and AES are used in the ECB, CBC and XTS mode. Additionally, the authenticated encryption cipher Ascon is used both standalone and within a TEC tree. Our results show that the data processing of our encryption pipeline is highly efficient with up to 94% utilization of the read bandwidth that is provided by the FPGA interface. Moreover, the use of a cryptographically strong primitive like Ascon yields highly practical results with 54% bandwidth utilization.

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.