main-content

## Über dieses Buch

The two-volume set LNCS 12726 + 12727 constitutes the proceedings of the 19th International Conference on Applied Cryptography and Network Security, ACNS 2021, which took place virtually during June 21-24, 2021.

The 37 full papers presented in the proceedings were carefully reviewed and selected from a total of 186 submissions. They were organized in topical sections as follows:

Part I: Cryptographic protocols; secure and fair protocols; cryptocurrency and smart contracts; digital signatures; embedded system security; lattice cryptography;

Part II: Analysis of applied systems; secure computations; cryptanalysis; system security; and cryptography and its applications.

## Inhaltsverzeichnis

### Adaptive-ID Secure Hierarchical ID-Based Authenticated Key Exchange Under Standard Assumptions Without Random Oracles

Abstract
Hierarchical ID-based authenticated key exchange (HID-AKE) is a cryptographic protocol to establish a common session key between parties with authentication based on their IDs with the hierarchical delegation of key generation functionality. All existing HID-AKE schemes are selective ID secure, and the only known standard model scheme relies on a non-standard assumption such as the q-type assumption. In this paper, we propose a generic construction of HID-AKE that is adaptive ID secure in the HID-eCK model (maximal-exposure-resilient security model) without random oracles. One of the concrete instantiations of our generic construction achieves the first adaptive ID secure HID-AKE scheme under the (standard) k-lin assumption in the standard model. Furthermore, it has the advantage that the computational complexity of pairing and exponentiation operations and the communication complexity do not depend on the depth of the hierarchy. Also, the other concrete instantiation achieves the first HID-AKE scheme based on lattices (i.e., post-quantum).
Ren Ishibashi, Kazuki Yoneyama

### Analysis of Client-Side Security for Long-Term Time-Stamping Services

Abstract
Time-stamping services produce time-stamp tokens as evidences to prove that digital data existed at given points in time. Time-stamp tokens contain verifiable cryptographic bindings between data and time, which are produced using cryptographic algorithms. In the ANSI, ISO/IEC and IETF standards for time-stamping services, cryptographic algorithms are addressed in two aspects: (i) Client-side hash functions used to hash data into digests for nondisclosure. (ii) Server-side algorithms used to bind the time and digests of data. These algorithms are associated with limited lifespans due to their operational life cycles and increasing computational powers of attackers. After the algorithms are compromised, time-stamp tokens using the algorithms are no longer trusted. The ANSI and ISO/IEC standards provide renewal mechanisms for time-stamp tokens. However, the renewal mechanisms for client-side hash functions are specified ambiguously, that may lead to the failure of implementations. Besides, in existing papers, the security analyses of long-term time-stamping schemes only cover the server-side renewal, and the client-side renewal is missing. In this paper, we analyse the necessity of client-side renewal, and propose a comprehensive long-term time-stamping scheme that addresses both client-side renewal and server-side renewal mechanisms. After that, we formally analyse and evaluate the client-side security of our proposed scheme.
Long Meng, Liqun Chen

### Towards Efficient and Strong Backward Private Searchable Encryption with Secure Enclaves

Abstract
Dynamic searchable symmetric encryption (DSSE) can enable a cloud server to search and update over the encrypted data. Recently, forward and backward privacy in DSSE receive wide attention due to the rise in a number of emerging attacks exploiting the leakage in data update operations. Forward privacy ensures newly added data is not related to queries issued in the past, whilst backward privacy ensures previously deleted data is not revealed in the queries. Unfortunately, achieving strong forward and backward privacy, i.e., only revealing insertion timestamps of search results, requires the adoption of oblivious data structures, which incur heavy computation and communication overhead at both the client and server-side. In this paper, we resort to secure enclaves, aka Intel SGX, to tackle the above problem. Specifically, we propose Maiden, the first strong backward-private DSSE scheme without relying on ORAM. Our key idea is to keep track of the states of updates and the deletion information inside the secure enclave to prevent the leakage from the server. To speed up, we further leverage a compressed data structure to maintain a sketch of addition operations in the enclave to facilitate the fast generation of search tokens of non-deleted data. We conduct formal security analysis and perform comprehensive evaluations on both synthetic and real-world datasets. Our results confirm that Maiden outperforms the prior work.
Viet Vo, Shangqi Lai, Xingliang Yuan, Surya Nepal, Joseph K. Liu

### CECMLP: New Cipher-Based Evaluating Collaborative Multi-layer Perceptron Scheme in Federated Learning

Abstract
Due to the large volume of available datasets and powerful computing infrastructures, federated learning has been widely explored in many scenarios, e.g. medical screening, and image processing. It refers to all participants to jointly learn shared models under the orchestration of the server without exposing their datasets. In federated learning, since the data qualities of the participants are extremely diverse, reliability is used to measure the data qualities of the participants. To make the learning task liberally and non-discriminative, participants’ reliability privacy related to their data quality should be well preserved. However, the existing work assumed that the reliability of participants is transparent for the server provider, resulting in a severe challenge in practical applications. To thwart this challenge, we propose a novel federated learning scheme, which prevents each participant’s training set privacy and reliability privacy from being revealed to the public. Moreover, to further reduce the impact of unreliable participants and improve training efficiency, we design a cipher-based reliability weighted method to differentiate and intensify different contributions of the (un)reliable participants for joint model training. Security analysis shows that our proposed scheme can achieve the desired security requirements. Moreover, extensive performance evaluations demonstrate that our design achieves higher accuracy and is more robust against unreliable participants than conventional federated learning.
Yuqi Chen, Xiaoyu Zhang, Yi Xie, Meixia Miao, Xu Ma

### Blind Polynomial Evaluation and Data Trading

Abstract
In this paper, we propose the first desirable mechanism that is practical and supports a wide variety of computing tasks—evaluation of arbitrary functions that can be represented as polynomials. We introduce a new cryptographic notion called blind polynomial evaluation and instantiate it with an explicit protocol. We further combine this notion with the blockchain paradigm to provide a practical framework that can satisfy the requirements mentioned above.
Yi Liu, Qi Wang, Siu-Ming Yiu

### Coin-Based Multi-party Fair Exchange

Abstract
Multi-party fair exchange (MFE) considers scenarios where fairness means that either all exchanges as agreed upon between multiple parties take place, or no item changes hands. The two-party case was widely studied starting with the seminal work of Asokan et al. in ACM CCS 1998. The state-of-the-art MFE protocol was shown by Kılınç and Küpçü in CT-RSA 2015. Unfortunately, it only works on items that can be efficiently verifiably encrypted, which, in particular, means that it cannot efficiently handle exchange of large files in a peer-to-peer file sharing scenario. In this work, first, we extend the optimistic two-party fair computation definition of Cachin and Camenisch in CRYPTO 2000 for the MFE setting, and prove the security of our protocol with ideal-real simulation. Secondly, we extend the CT-RSA 2015 solution of Kılınç and Küpçü in a way that our protocol enables parties to exchange any item, be it a large file. While doing so, we employ electronic payments, where if a party does not obtain the desired item at the end of the protocol, the payment of the item’s owner will be obtained instead. Third, we achieve asymptotic optimality with O(1) rounds and $$O(n^2)$$ messages, where n is the number of participating parties. Finally, we also provide experimental results from our prototype code.
Handan Kılınç Alper, Alptekin Küpçü

### P2DEX: Privacy-Preserving Decentralized Cryptocurrency Exchange

Abstract
Cryptocurrency exchange services are either trusted central entities that have been routinely hacked (losing over 8 billion USD), or decentralized services that make all orders public before they are settled. The latter allows market participants to “front run” each other, an illegal operation in most jurisdictions. We extend the “Insured MPC” approach of Baum et al. (FC 2020) to construct an efficient universally composable privacy preserving decentralized exchange where a set of servers run private cross-chain exchange order matching in an outsourced manner, while being financially incentivised to behave honestly. Our protocol allows for exchanging assets over multiple public ledgers, given that users have access to a ledger that supports standard public smart contracts. If parties behave honestly, the on-chain complexity of our construction is as low as that of performing the transactions necessary for a centralized exchange. In case malicious behavior is detected, users are automatically refunded by malicious servers at low cost. Thus, an actively corrupted majority can only mount a denial-of-service attack that makes exchanges fail, in which case the servers are publicly identified and punished, while honest clients do not to lose their funds. For the first time in this line of research, we report experimental results on the MPC building block, showing the approach is efficient enough to be used in practice.
Carsten Baum, Bernardo David, Tore Kasper Frederiksen

### Up My Sleeve! A Hidden Secure Fallback for Cryptocurrency Wallets

Abstract
We introduce a new key generation mechanism where users can generate a “back up key”, securely nested inside the secret key of a signature scheme.
Our main motivation is that in case of leakage of the secret key, established techniques based on zero-knowledge proofs of knowledge are void since the key becomes public. On the other hand, the “back up key”, which is secret, can be used to generate a “proof of ownership”, i.e., only the real owner of this secret key can generate such a proof. To the best of our knowledge, this extra level of security is novel, and could have already been used in practice, if available, in digital wallets for cryptocurrencies that suffered massive leakage of account private keys. In this work, we formalize the notion of “Proof of Ownership” and “Fallback” as new properties. Then, we introduce our construction, which is compatible with major designs for wallets based on ECDSA, and adds a $$\text{ W-OTS}^{+}$$ signing key as a “back up key”. Thus offering a quantum secure fallback. This design allows the hiding of any quantum secure signature key pair, and is not exclusive to $$\text{ W-OTS}^{+}$$. Finally, we briefly discuss the construction of multiple generations of proofs of ownership.
David Chaum, Mario Larangeira, Mario Yaksetig, William Carter

### Terrorist Attacks for Fake Exposure Notifications in Contact Tracing Systems

Abstract
In this work we show that an adversary can attack the integrity of contact tracing systems based on Google-Apple Exposure Notifications (GAEN) by leveraging blockchain technology. We show that through smart contracts there can be an on-line market where infected individuals interested in monetizing their status can upload to the servers of the GAEN-based systems some keys (i.e., TEKs) chosen by a non-infected adversary. In particular, the infected individual can anonymously and digitally trade the upload of TEKs without a mediator and without running risks of being cheated. This vulnerability can therefore be exploited to generate large-scale fake exposure notifications of at-risk contacts with serious consequences (e.g., jeopardizing parts of the health system, affecting results of elections, imposing the closure of schools, hotels or factories).
As main contribution, we design a smart contract with two collateral deposits that works, in general, on GAEN-based systems. We then also suggest the design of a more sophisticated smart contract, using DECO, that could be used to attack in a different way GAEN-based systems (i.e., this second smart contract can succeed even in case GAEN systems are repaired making ineffective the first smart contract).
Our work shows how to realize with GAEN-based systems (in particular with Immuni and SwissCovid), the terrorist attack to decentralized contact tracing systems envisioned by Vaudenay.
Gennaro Avitabile, Daniele Friolo, Ivan Visconti

### Unlinkable and Invisible -Sanitizable Signatures

Abstract
Sanitizable signatures (SaS) allow a (single) sanitizer, chosen by the signer, to modify and re-sign a message in a somewhat controlled way, that is, only editing parts (or blocks) of the message that are admissible for modification.
This primitive is an efficient tool, with many formally defined security properties, such as unlinkability, transparency, immutability, invisibility, and unforgeability. An SaS scheme that satisfies these properties can be a great asset to the privacy of any field it will be applied to, e.g., anonymizing medical files.
In this work, we look at the notion of $$\gamma$$-sanitizable signatures ($$\gamma$$SaS): we take the sanitizable signatures one step further by allowing the signer to not only decide which blocks can be modified, but also how many of them at most can be modified within a single sanitization, setting a limit, denoted with $$\gamma$$. We adapt the security properties listed above to $$\gamma$$SaS and propose our own scheme, ULISS (Unlinkable Limited Invisible Sanitizable Signature), then show that it verifies these properties. This extension of SaS can not only improve current use cases, but also introduce new ones, e.g., restricting the number of changes in a document within a certain timeframe.
Angèle Bossuat, Xavier Bultel

### Partially Structure-Preserving Signatures: Lower Bounds, Constructions and More

Abstract
In this work we first provide a framework for defining a large subset of pairing-based digital signature schemes which we call Partially Structure-Preserving Signature (PSPS) schemes. PSPS schemes are similar in nature to structure-preserving signatures with the exception that in PSPS schemes messages are scalars from $$\mathbb {Z}_p$$ instead of being group elements. This class encompasses various existing schemes which have a number of desirable features which makes them an ideal building block for many privacy-preserving cryptographic protocols. Such schemes include the widely-used schemes of Camenisch-Lysyanskaya (CRYPTO 2004) and Pointcheval-Sanders (CT-RSA 2016). We then provide various impossibility and lower bound results for variants of this class. Our results include bounds for the signature and verification key sizes as well as lower bounds for achieving strong unforgeability. We also give a generic framework for transforming variants of PSPS schemes into structure-preserving ones. As part of our contribution, we also give a number of optimal PSPS schemes which may be of independent interest. Our results aid in understanding the efficiency of pairing-based signature schemes and show a connection between this class of schemes and structure-preserving ones.

### An Efficient Certificate-Based Signature Scheme in the Standard Model

Abstract
Certificate-based cryptography optimizes certificate management of the traditional public key infrastructure (PKI) and overcomes the problems of the key escrow and the key distribution in identity-based cryptography (IBC). Currently, many certificate-based signature (CBS) schemes have been proposed in the random oracle model or standard model. However, all existing schemes in the standard model are quietly inefficient. In this paper, we propose an efficient certificate-based signature over bilinear groups in the standard model. Compared with the state-of-the-art constructions in the standard model, the proposed scheme is superior in both communication cost and computational overhead.
Guoqiang Wang, Yanmei Cao

### SnakeGX: A Sneaky Attack Against SGX Enclaves

Abstract
Intel Software Guard eXtension (SGX) is a technology to create enclaves (i.e., trusted memory regions) hardware isolated from a compromised operating system. Recently, researchers showed that unprivileged adversaries can mount code-reuse attacks to steal secrets from enclaves. However, modern operating systems can use memory-forensic techniques to detect their traces. To this end, we propose SnakeGX, an approach that allows stealthier attacks with a minimal footprint; SnakeGX is a framework to implant a persistent backdoor in legitimate enclaves. Our solution encompasses a new architecture specifically designed to overcome the challenges SGX environments pose, while preserving their integrity and functionality. We thoroughly evaluate SnakeGX against StealthDB, which demonstrates the feasibility of our approach.
Flavio Toffalini, Mariano Graziano, Mauro Conti, Jianying Zhou

### Telepathic Headache: Mitigating Cache Side-Channel Attacks on Convolutional Neural Networks

Abstract
Convolutional Neural Networks (CNNs) are the target of several side-channel attacks aiming at recovering their parameters and hyper-parameters. Attack vectors include monitoring of the cache, power consumption analysis and execution time measurements. These attacks often rely on the knowledge of a certain – large – set of hyper-parameters among which the victim model lies. The goal of the potential attacker is then to reduce that search space or even deduce the correct architecture. One such attack, Cache Telepathy by Yan et al., monitors access to a common matrix multiplication algorithm, GeMM (Generalized Matrix Multiply), in order to determine the victim model’s hyper-parameters. In this paper, we propose to change the order in which the computations are made and add randomness to the said computations in order to mitigate Cache Telepathy. The security analysis of our protection shows that the Cache Telepathy attack on a protected VGG-16 has an increased search space: from 16 to $$2^{22}$$.
Hervé Chabanne, Jean-Luc Danger, Linda Guiga, Ulrich Kühne

### Efficient FPGA Design of Exception-Free Generic Elliptic Curve Cryptosystems

Abstract
Elliptic curve cryptography (ECC) is one of promising cryptosystems in embedded systems as it provides high security levels with short keys. Scalar multiplication is a dominating and time-consuming process that ensures security in ECC. We implement hardware modules for generic ECC over 256-bit prime fields on field-programmable gate array (FPGA). The key points in our design are (1) secure and exception-free for any scalar with less memory usage, (2) long-bit modular arithmetic modules utilizing today’s advanced and high-performance programmable logic and considering balance between the modules in terms of propagation delay, (3) parallelism extraction inside each elliptic curve point computation as well as between the point computations, and (4) efficient hardware–software co-processing facilitated by application interfaces between a processing core and hardware modules. The evaluation results demonstrate that our design achieves the best performance to existing FPGA designs without using a table for generic ECC.
Kiyofumi Tanaka, Atsuko Miyaji, Yaoan Jin

### Access Control Encryption from Group Encryption

Abstract
Access control encryption (ACE) enforces both read and write permissions. It kills off any unpermitted subliminal message channel via the help of a sanitizer who knows neither of the plaintext, its sender and receivers, nor the access control policy. This work aims to solve the open problem left by the seminal work of Damgård et al. (TCC 2016), namely, “to construct practically interesting ACE from noisy, post-quantum assumptions such as LWE.” We start with revisiting group encryption (GE), which allows anyone to encrypt to a certified group member, whom remains anonymous unless the opening authority decided to reveal him/her. We propose: 1) the notion of sanitizable GE (SGE), with specific changes for non-interactive proof, 2) the notion of traceable ACE (tACE), which helps damage control by tracing after-the-fact if some secret were leaked unluckily, 3) a generic construction of (t)ACE for equality policy (ACE-EP) from SGE, 4) a generic construction of ACE for general policy from ACE-EP, 5) a lattice-based instantiation of SGE, which comes with 6) a simple mechanism for checking that the randomness of ciphertexts can span the randomness space.
Xiuhua Wang, Harry W. H. Wong, Sherman S. M. Chow

### Password Protected Secret Sharing from Lattices

Abstract
A password protected secret sharing ($$\mathsf {PPSS}$$) allows a user to store shares of a secret on a set of L servers, and use a single password to authenticate itself to any subset of k servers at a later time to access the shares and reconstruct the secret. Security of $$\mathsf {PPSS}$$ ensures that a coalition of up to $$k-1$$ servers cannot reveal any information about the secret message or the password. A related primitive is threshold password authenticated key exchange protocol ($$\mathsf {TPAKE}$$) that allows a user to establish individual authenticated shared secret keys with members of a subset of k out of L servers, using a single password. These primitives are well motivated, with applications such as secure storage of secret keys, and secure group communication using passwords for authentication. In this paper, we give the first construction of these primitives that provide post-quantum security. We prove security of our constructions in concurrent setting, and in the standard model, reducing security to the decisional LWE problem.
Partha Sarathi Roy, Sabyasachi Dutta, Willy Susilo, Reihaneh Safavi-Naini

### Efficient Homomorphic Conversion Between (Ring) LWE Ciphertexts

Abstract
In the past few years, significant progress on homomorphic encryption (HE) has been made toward both theory and practice. The most promising HE schemes are based on the hardness of the Learning With Errors (LWE) problem or its ring variant (RLWE). In this work, we present new conversion algorithms that switch between different (R)LWE-based HE schemes to take advantage of them. Specifically, we present and combine three ideas to improve the key-switching procedure between LWE ciphertexts, transformation from LWE to RLWE, as well as packing of multiple LWE ciphertexts in a single RLWE encryption. Finally, we demonstrate an application of building a secure channel between a client and a cloud server with lightweight encryption, low communication cost, and capability of homomorphic computation.
Hao Chen, Wei Dai, Miran Kim, Yongsoo Song

### Backmatter

Weitere Informationen