main-content

## Über dieses Buch

This book constitutes revised selected papers from the 22nd International Conference on Information Security and Cryptology, ICISC 2019, held in Seoul, South Korea, in December 2019.

The total of 18 papers presented in this volume were carefully reviewed and selected from 43 submissions. The papers were organized in topical sections named: public-key encryption and implementation; homomorphic encryption; secure multiparty computation; post-quantum cryptography; secret sharing and searchable encryption; storage security and information retrieval; and attacks and software security.

## Inhaltsverzeichnis

### Revised Version of Block Cipher CHAM

Abstract
CHAM is a family of lightweight block ciphers published in 2017 [22]. The CHAM family consists of three ciphers, CHAM-64/128, CHAM-128/128, and CHAM-128/256. CHAM can be implemented with a remarkably low area in hardware compared to other lightweight block ciphers, and it also performs well on software. We found new (related-key) differential characteristics and differentials of CHAM using a SAT solver. Although attacks using the new characteristics are limited to the reduced rounds of CHAM, it is preferable to increase the number of rounds to ensure a sufficient security margin. The numbers of rounds of CHAM-64/128, CHAM-128/128, and CHAM-128/256 are increased from 80 to 88, 80 to 112, and 96 to 120, respectively. We provide strong evidence that CHAM with these new numbers of rounds is secure enough against (related-key) differential cryptanalysis. Because increasing the number of rounds does not affect the area in low-area hardware implementations, the revised CHAM is still excellent in lightweight hardware implementations. In software, the revised CHAM is still comparable to SPECK, one of the top-ranked algorithms in software.
Dongyoung Roh, Bonwook Koo, Younghoon Jung, Il Woong Jeong, Dong-Geon Lee, Daesung Kwon, Woo-Hwan Kim

### Systematic Construction of Nonlinear Product Attacks on Block Ciphers

Abstract
A major open problem in block cipher cryptanalysis is discovery of new invariant properties of complex type. Recent papers show that this can be achieved for SCREAM, Midori64, MANTIS-4, T-310 or for DES with modified S-boxes. Until now such attacks are hard to find and seem to happen by some sort of incredible coincidence. In this paper we abstract the attack from any particular block cipher. We study these attacks in terms of transformations on multivariate polynomials. We shall demonstrate how numerous variables including key variables may sometimes be eliminated and at the end two very complex Boolean polynomials will become equal. We present a general construction of an attack where multiply all the polynomials lying on one or several cycles. Then under suitable conditions the non-linear functions involved will be eliminated totally. We obtain a periodic invariant property holding for any number of rounds. A major difficulty with invariant attacks is that they typically work only for some keys. In T-310 our attack works for any key and also in spite of the presence of round constants.
Nicolas T. Courtois, Matteo Abbondati, Hamy Ratoanina, Marek Grajek

### Authenticated Encryption Based on Lesamnta-LW Hashing Mode

Abstract
Authenticated encryption refers to symmetric cryptography providing both privacy and authenticity. It is most common to construct it as a block-cipher mode of operation. Another promising approach is to construct it based on cryptographic hashing. This paper proposes a nonce-based authenticated encryption scheme based on the Lesamnta-LW hashing mode. Lesamnta-LW is a block-cipher-based iterated hash function, which is specified in the ISO/IEC 29192-5 lightweight hash-function standard. This paper also shows that the proposed scheme is secure if the underlying block cipher is a pseudorandom permutation. Both of the other ISO/IEC 29192-5 mechanisms, PHOTON and SPONGENT, are hardware-oriented sponge-based hash functions, and nonce-based authenticated encryption schemes can also be constructed based on them. On the other hand, Lesamnta-LW is a software-oriented Merkle-Damgård hash function. Thus, the proposed scheme is a new option for authenticated encryption based on lightweight cryptographic hashing.
Shoichi Hirose, Hidenori Kuwakado, Hirotaka Yoshida

### All the HIGHT You Need on Cortex–M4

Abstract
In this paper, we present high-speed and secure implementations of HIGHT block cipher on 32-bit ARM Cortex-M4 microcontrollers. We utilized both data parallelism and task parallelism to reduce the execution timing. In particular, we used the 32-bit wise ARM–SIMD instruction sets to perform the parallel computations in efficient way. Since the HIGHT block cipher is constructed upon 8-bit word, four 8-bit operations are performed in the 32-bit wise ARM–SIMD instruction of ARM Cortex-M4 microcontrollers. We also presented a novel countermeasure against fault attack on target microcontrollers. The method achieved the fault attack resistance with intra-instruction redundancy feature with reasonable performance. Finally, the proposed HIGHT implementation achieved much better performance and security level than previous works.
Hwajeong Seo, Zhe Liu

### Fast AES Implementation Using ARMv8 ASIMD Without Cryptography Extension

Abstract
While the ARMv8-A ISA allows for hardware accelerated cryptographic instructions, such extension is not available for every device, being added at the discretion of the CPU manufacturer. Prime examples of ARMv8 devices without this support are the low cost Raspberry Pi 3B/3B+/4 single board computers. This work presents an optimized AES implementation targeting CPUs without Cryptography Extension instructions, relying only on ASIMD operations. We show a new implementation that processes four blocks at the same time, which requires block permutations and modified versions of the main layers. In particular, we provide a new efficient formula for computing the MixColumns layer. The time performance our AES implementation outperforms the current ASIMD implementation found in the Linux Kernel by about 5%.
Hayato Fujii, Félix Carvalho Rodrigues, Julio López

### FACE–LIGHT: Fast AES–CTR Mode Encryption for Low-End Microcontrollers

Abstract
In this paper, we revisited the previous Fast AES–CTR mode Encryption (FACE) method for high-end processors and tailored the method to the microcontrollers, namely FACE–LIGHT. We targeted the 32-bit counter mode of operation for AES in constant timing. This optimized technique pre-computes the 2 Add-RoundKey, 2 Sub-Bytes, 2 Shift-Rows and 1 Mix-Columns operations. The FACE–LIGHT is implemented on the representative low-end microcontrollers (e.g. 8-bit AVR). The execution timing of AES–CTR algorithm for 128-bit and 256-bit security levels achieved the 2,218 and 3,184 clock cycles, respectively. This is faster than previous works by 22 % for 128-bit security level. The FACE–LIGHT can be used to extend the FACE to round 3. The AES is also implemented to be secure against the CPA (Correlation Power Analysis).
Kyungho Kim, Seungju Choi, Hyeokdong Kwon, Zhe Liu, Hwajeong Seo

### Sum It Up: Verifiable Additive Homomorphic Secret Sharing

Abstract
In many situations, clients (e.g., researchers, companies, hospitals) need to outsource joint computations based on joint inputs to external cloud servers in order to provide useful results. Often clients want to guarantee that the results are correct and thus, an output that can be publicly verified is required. However, important security and privacy challenges are raised, since clients may hold sensitive information and the cloud servers can be untrusted. Our goal is to allow the clients to protect their secret data, while providing public verifiability i.e., everyone should be able to verify the correctness of the computed result.
In this paper, we propose three concrete constructions of verifiable additive homomorphic secret sharing (VAHSS) to solve this problem. Our instantiations combine an additive homomorphic secret sharing (HSS) scheme, which relies on Shamir’s secret sharing scheme over a finite field $$\mathbb {F}$$, for computing the sum of the clients’ secret inputs, and three different methods for achieving public verifiability. More precisely, we employ: (i) homomorphic collision-resistant hash functions; (ii) linear homomorphic signatures; as well as (iii) a threshold RSA signature scheme. In all three cases we provide a detailed correctness, security and verifiability analysis and discuss their efficiency.
Georgia Tsaloli, Aikaterini Mitrokotsa

### There Is Always an Exception: Controlling Partial Information Leakage in Secure Computation

Abstract
Private Function Evaluation (PFE) enables two parties to jointly execute a computation such that one of them provides the input while the other chooses the function to compute. According to the traditional security requirements, a PFE protocol should leak no more information, neither about the function nor the input, than what is revealed by the output of the computation. Existing PFE protocols inherently restrict the scope of computable functions to a certain function class with given output size, thus ruling out the direct evaluation of such problematic functions as the identity map, which would entirely undermine the input privacy requirement. We observe that when not only the input x is confidential but certain partial information g(x) of it as well, standard PFE fails to provide meaningful input privacy if g and the function f to be computed fall into the same function class.
Our work investigates the question whether it is possible to achieve a reasonable level of input and function privacy simultaneously even in the above cases. We propose the notion of Controlled PFE (CPFE) with different flavours of security and answer the question affirmatively by showing simple, generic realizations of the new notions. Our main construction, based on functional encryption (FE), also enjoys strong reusability properties enabling, e.g. fast computation of the same function on different inputs. To demonstrate the applicability of our approach, we show a concrete instantiation of the FE-based protocol for inner product computation that enables secure statistical analysis (and more) under the standard Decisional Diffie–Hellman assumption.
Máté Horváth, Levente Buttyán, Gábor Székely, Dóra Neubrandt

### An Automated Security Analysis Framework and Implementation for MTD Techniques on Cloud

Abstract
Cloud service providers offer their customers with on-demand and cost-effective services, scalable computing, and network infrastructures. Enterprises migrate their services to the cloud to utilize the benefit of cloud computing such as eliminating the capital expense of their computing need. There are security vulnerabilities and threats in the cloud. Many researches have been proposed to analyze the cloud security using Graphical Security Models (GSMs) and security metrics. In addition, it has been widely researched in finding appropriate defensive strategies for the security of the cloud. Moving Target Defense (MTD) techniques can utilize the cloud elasticity features to change the attack surface and confuse attackers. Most of the previous work incorporating MTDs into the GSMs are theoretical and the performance was evaluated based on the simulation. In this paper, we realized the previous framework and designed, implemented and tested a cloud security assessment tool in a real cloud platform named UniteCloud. Our security solution can (1) monitor cloud computing in real-time, (2) automate the security modeling and analysis and visualize the GSMs using a Graphical User Interface via a web application, and (3) deploy three MTD techniques including Diversity, Redundancy, and Shuffle on the real cloud infrastructure. We analyzed the automation process using the APIs and showed the practicality and feasibility of automation of deploying all the three MTD techniques on the UniteCloud.
Hooman Alavizadeh, Hootan Alavizadeh, Dong Seong Kim, Julian Jang-Jaccard, Masood Niazi Torshiz

### Security Analysis of Group Action Inverse Problem with Auxiliary Inputs with Application to CSIDH Parameters

Abstract
In this paper, we consider the security of a problem called Group Action Inverse Problem with Auxiliary Inputs (GAIPwAI). The Group Action Inverse Problem (GAIP) plays an important role in the security of several isogeny-based cryptosystems, such as CSIDH, SeaSign and CSI-FiSh.
Briefly speaking, given two isogenous supersingular curves E and $$E'$$ over $$\mathbb F_p$$, where $$E'$$ is defined by an ideal $$\mathfrak a$$ in the $$\mathbb F_p$$-endomorphism ring of E and denoted by $$E' = [\mathfrak a]*E$$, GAIP requires finding $$\mathfrak a \subset {\text {End}}_{\mathbb F_p}(E)$$. Its best classical algorithm is based on the baby-step-giant-step method and it runs in time $$O(p^{1/4})$$.
In this paper, we show that if E and $$E'$$ are given together with $$[\mathfrak a^d]*E$$ for a positive divisor d that divides the order of the class group of $${\mathbb Z}[\sqrt{-p}]$$, then $$\mathfrak a$$ can be computed in $$O\big ( ( p^{1/2} /d)^{1/2} + d^{1/2} \big )$$ time complexity. In particular, when $$d \approx p^{1/4}$$, it can be solved in time $$O( p^{1/8} )$$ which is significantly less than $$O( p^{1/4} )$$.
Applying the idea to CSIDH-512 parameters, we show that, if an additional isogenous curve $$[\mathfrak a^d] * E$$ is given, the security level of this cryptosystem reduces to 68-bit security instead of 128-bit security as originally believed.
Taechan Kim

### Secure Key Encapsulation Mechanism with Compact Ciphertext and Public Key from Generalized Srivastava Code

Abstract
Code-based public key cryptosystems have been found to be an interesting option in the area of Post-Quantum Cryptography. In this work, we present a key encapsulation mechanism (KEM) using a parity check matrix of the Generalized Srivastava code as the public key matrix. Generalized Srivastava codes are privileged with the decoding technique of Alternant codes as they belong to the family of Alternant codes. We exploit the dyadic structure of the parity check matrix to reduce the storage of the public key. Our encapsulation leads to a shorter ciphertext as compared to DAGS proposed by Banegas et al. in Journal of Mathematical Cryptology which also uses Generalized Srivastava code. Our KEM provides IND-CCA security in the random oracle model. Also, our scheme can be shown to achieve post-quantum security in the quantum random oracle model.
Jayashree Dey, Ratna Dutta

### Improvement of Binary and Non Binary Statistical Decoding Algorithm

Abstract
The security of McEliece’s cryptosystem relies heavily on the hardness of decoding a random linear code. The best known generic decoding algorithms are derived from the Information-Set Decoding (ISD) algorithm. This was first proposed in 1962 by Prange and subsequently improved in 1989 by Stern and later in 1991 by Dumer. In 2001 Al Jabri introduced a new decoding algorithm for general linear block codes which does not belong to this family, called Statistical Decoding (SD). Since then, like for the Information Set Decoding algorithm, there have been numerous work done to improve and generalize the SD algorithm. In this paper, we improve the SD algorithm using the notion of bases lists in binary case. Then, we give a non binary version of this improvement. Finally, we have computed complexity analysis and have made a complexity comparison of our results with that of recent results on SD algorithm and complexity of classic ISD algorithm.
Pierre-Louis Cayrel, Cheikh Thiécoumba Gueye, Junaid Ahmad Khan, Jean Belo Klamti, Edoardo Persichetti

### LizarMong: Excellent Key Encapsulation Mechanism Based on RLWE and RLWR

Abstract
The RLWE family algorithms submitted to the NIST post-quantum cryptography standardization process have each merit in terms of security, correctness, performance, and bandwidth. However, there is no splendid algorithm in all respects. Besides, various recent studies have been published that affect security and correctness, such as side-channel attacks and error dependencies. To date, though, no algorithm has fully considered all the aspects. We propose a novel Key Encapsulation Mechanism scheme called LizarMong, which is based on RLizard. LizarMong combines the merit of each algorithm and state-of-the-art studies. As a result, it achieves up to 85% smaller bandwidth and 3.3 times faster performance compared to RLizard. Compared to the NIST’s candidate algorithms with a similar security, the bandwidth is about 5–42% smaller, and the performance is about 1.2-4.1 times faster. Also, our scheme resists the known side-channel attacks.
Chi-Gon Jung, JongHyeok Lee, Youngjin Ju, Yong-Been Kwon, Seong-Woo Kim, Yunheung Paek

### Efficient Identity-Based Encryption from LWR

Abstract
The Learning with Rounding (LWR) problem is a deterministic variant of the classical Learning with Errors (LWE) problem, for which sampling an instance does not involve discrete Gaussian sampling. We propose the first probabilistic Identity-Based Encryption (IBE) from the LWR problem which is secure in the standard model. The encryption of our IBE scheme does not require discrete Gaussian sampling as it is based on the LWR problem, and hence it is simpler and faster than that of LWE-based IBEs such as ABB scheme. We also present an efficient instantiation employing algebraic ring structure and MP12 trapdoor sampling algorithms with an implementation result. With our proposed parameter sets, the ciphertext sizes can be reduced in a large extent compared to the ABB scheme with the same security level.
Jung Hee Cheon, Haejin Cho, Jaewook Jung, Joohee Lee, Keewoo Lee

### Faster Bootstrapping of FHE over the Integers

Abstract
In FHE over the integers, decryption function is simplified by sparse subset subset sum problem (SSSP) assumption, which is introduced by Dijk et al. (Eurocrypt 2010), so that bootstrapping can be achieved successfully. Later, Nuida and Kurowasa (Eurocrypt 2015) proposed an advanced method of which the degree is very low and the message space is non-binary. These previous methods require low degree but more than $$O(\lambda ^4)$$ homomorphic multiplications which make them very slow. For a general bootstrapping method in FHE over the integers, the number of homomorphic multiplications and the degree of decryption function are important factors for the efficiency of bootstrapping procedure.
In this paper, we propose a new bootstrapping method for FHE over the integers requiring only $$O(\log ^2 \lambda )$$ homomorphic multiplications which is significantly lower than previous methods. Implementing our bootstrapping method on the scale-invariant FHE over the integers called CLT scheme, it takes 6 s for 500-bit message space and 80-bit security on a desktop. We also apply our bootstrapping method to the homomorphic evaluation of AES-128 circuit: It takes about 8 s per 128-bit block and is faster than the previous results of homomorphic AES evaluation using FHEs over the integers without bootstrapping.
Jung Hee Cheon, Kyoohyung Han, Duhyeong Kim

### Complete Addition Law for Montgomery Curves

Abstract
Montgomery curves allow efficient and side-channel resistant computation of ECDH using the Montgomery ladder. But the addition law of a Montgomery curve derived from the chord-tangent method is less efficient than other curve models such as a short Weierstrass curve and an Edwards curve. So, the usage of a Montgomery curve is strictly limited to ECDH only, such as $$\mathsf {X25519}$$ and $$\mathsf {X448}$$ functions in IETF RFC 7748. For other operations including fixed-base and multiple scalar multiplications, their birationally-equivalent (twisted) Edwards curves are recommended for use since the conversions between Montgomery curves and their Edwards equivalents are simple. This conversion enables the use of the efficient complete addition law of the Edwards curve that works for all pairs of input points with no exceptional cases. As a result, the combination allows secure and exception-free implementations, but at the expense of additional storage for the two curve parameters and for the conversion between them. However, smart devices in IoT environments that mainly operate ECDH (for example, RawPublicKey mode of IETF RFC 7250) do not need to implement such a conversion if a complete addition law does exist for the Montgomery curves.
To make such implementations possible, we provide a complete addition law on Montgomery curves. The explicit formulas for the complete addition law are not as efficient as those of Edwards curves, but they can make the Montgomery curve addition operation more efficient compared to using the conversion to the (twisted) Edwards equivalent. We also confirmed the validity of the comparison by implementing such two methods of realizing the addition operation on $$\text {Curve25519}$$.
Jaeheon Kim, Je Hong Park, Dong-Chan Kim, Woo-Hwan Kim

### Improved CRT-RSA Secret Key Recovery Method from Sliding Window Leakage

Abstract
In this paper, we discuss side-channel attacks on the CRT-RSA scheme (RSA scheme with Chinese Remainder Theorem) implemented by the left-to-right sliding window method. This method calculates exponentiations by repeating squaring and multiplication. In CHES 2017, Bernstein et al. proposed side-channel attacks on the CRT-RSA signature scheme implemented by the left-to-right sliding window method. We can obtain square-and-multiply sequences by their side-channel attacks, but cannot calculate CRT-RSA secret keys because there are multiple candidates of multiplications. Then, Bernstein et al. calculated CRT-RSA secret keys by using two methods. First, they recovered CRT-RSA secret keys partially and calculated all secret key bits by using the Heninger–Shacham method. Second, they applied the Heninger–Shacham method to square-and-multiply sequences directly. They showed that we can calculate CRT-RSA secret keys more efficiently when we use square-and-multiply sequences directly. They also showed that we can recover CRT-RSA secret keys in polynomial time when $$w \le 4$$. Moreover, they experimentally showed that we can recover secret keys of 2048-bit CRT-RSA scheme when $$w=5$$. However, their latter method is simple and has room for improvement. Here, we study bit recovery more profoundly to improve their method. First, we calculate the exact rate of all knowable bits. Next, we propose a new method for calculating the proportion of each bit 0 or 1 in each nonrecovery bit. Finally, we propose a new method for calculating CRT-RSA secret key using this bit information. In our proposed algorithm, we extend Bernstein et al.’s method in combination with Kunihiro et al.’s method. We calculate more secret keys when $$w=5$$ by our proposed method compared to Bernstein et al.’s method.
Kento Oonishi, Xiaoxuan Huang, Noboru Kunihiro

### Differential Random Fault Attacks on Certain CAESAR Stream Ciphers

Abstract
We show that a particular class of stream ciphers – namely those in which the output function contains a bitwise AND operation – are susceptible to a differential fault attack using random faults. Several finalists and other candidates from the recent CAESAR competition fall into this category, including the AEGIS variants, Tiaoxin and the MORUS family. Attack outcomes range from key or full state recovery for Tiaoxin, to full state recovery for the AEGIS family and partial state recovery for MORUS. We present attack requirements and success probabilities on these ciphers, along with design considerations to mitigate against this attack.
Kenneth Koon-Ho Wong, Harry Bartlett, Leonie Simpson, Ed Dawson

### Backmatter

Weitere Informationen