# APKC ’18- Proceedings of the 5th ACM on ASIA Public-Key Cryptography Workshop

## SESSION: Invited Talk

###
Towards Ideal Self-bilinear Map

Bilinear maps (also called pairings) have been used for constructing various kinds of cryptographic primitives including (but not limited to) short signatures, identity-based encryption, attribute-based encryption, and non-interactive zero-knowledge proof systems. In known instantiations of cryptographic bilinear maps based on eliptic curves, source and target groups are different groups, which may restrict applications of bilinear maps. Cheon and Lee studied self-bilinear maps, which are bilinear maps whose source and target groups are identical. They showed huge potential of self-bilinear maps by showing that self-bilinear maps can be transformed into multilinear maps, which give further more cryptographic applications including (but not limited to) multiparty non-interactive key exchange, broadcast encryption, attribute-based encryption, homomorphic signatures, and obfuscation. However, they also showed a strong negative result on the existence of cryptographic self-bilinear maps. Namely, they showed that if there exists an efficiently computable self-bilinear map on a known order group, then the computational Diffie-Hellman (CDH) assumption does not hold on the group. This means that cryptographically useful self-bilinear maps do not exist on groups of known order. On the other hand, there is no negative result for self-bilinear maps on groups of unknown order. Indeed, Yamakawa et al. gave a partial positive result for self-bilinear maps on unknown order groups. Namely, they constructed self-bilinear maps with auxiliary information, which is a weaker variant of self-bilinear maps based on indistinguishability obfuscation. Though they showed that they are sufficient for some applications of self-bilinear maps, they are not as useful as “ideal” self-bilinear maps, which do not need auxiliary information. In this talk, we first review the construction of self-bilinear maps with auxiliary information given by Yamakawa et al. Then we consider the possibility of constructing ideal self-bilinear maps.

## SESSION: Card-based Protocol, Implementation, and Authentication for IoT

###
Five-Card AND Protocol in Committed Format Using Only Practical Shuffles

In card-based cryptography, designing AND protocols in committed format is a major topic of research. The state-of-the-art AND protocol proposed by Koch, Walzer, and Härtel in ASIACRYPT 2015 uses only four cards, which is the minimum permissible number. Their protocol»s minimality relies on somewhat complicated shuffles having non-uniform probabilities of possible outcomes. Restricting the allowed shuffles to “practical»» ones, namely uniform closed shuffles, to our knowledge, six cards are sufficient: The six-card AND protocol proposed by Mizuki and Sone in 2009 utilizes the random bisection cut, which is a uniform and cyclic (and hence, closed) shuffle. Thus, a question has arisen: Can we improve upon this six-card protocol using only practical shuffles? In other words, whether there exists a five-card AND protocol in committed format using only uniform closed shuffles has been one of the most important open questions in this field. In this paper, we answer the question affirmatively by designing a five-card committed-format AND protocol using only practical shuffles. The shuffles that our protocol uses are random cut and random bisection cut, both of which are uniform cyclic shuffles and can be easily implemented by humans.

###
SoK: A Performance Evaluation of Cryptographic Instruction Sets on Modern Architectures

The latest processors have included extensions to the instruction set architecture tailored to speed up the execution of cryptographic algorithms. Like the AES New Instructions (AES-NI) that target the AES encryption algorithm, the release of the SHA New Instructions (SHA-NI), designed to support the SHA-256 hash function, introduces a new scenario for optimizing cryptographic software. In this work, we present a performance evaluation of several cryptographic algorithms, hash-based signatures and data encryption, on platforms that support AES-NI and/or SHA-NI. In particular, we revisited several optimization techniques targeting multiple-message hashing, and as a result, we reduce by 21% the running time of this task by means of a pipelined SHA-NI implementation. In public-key cryptography, multiple-message hashing is one of the critical operations of the XMSS and XMSS^MT post-quantum hash-based digital signatures. Using SHA-NI extensions, signatures are computed 4x faster; however, our pipelined SHA-NI implementation increased this speedup factor to 4.3x. For symmetric cryptography, we revisited the implementation of AES modes of operation and reduced by 12% and 7% the running time of CBC decryption and CTR encryption, respectively.

###
You Shall Not Pass! (Once Again): An IoT Application of Post-quantum Stateful Signature Schemes

This paper presents an authentication protocol specifically tailored for IoT devices that inherently limits the number of times that an entity can authenticate itself with a given key pair. The protocol we propose is based on a stateful hash-based digital signature system called eXtended Merkle Signature Scheme (XMSS), which has increased its popularity of late due to its resistance to quantum-computer-aided attacks. We propose a 1-pass authentication protocol that can be customized according to the server capabilities to keep track of the key pair state. In addition, we present results when ported to ARM Cortex-M3 and M0 processors.

## SESSION: Code-based and Elliptic Curve Cryptography

###
A New LRPC-Kronecker Product Codes Based Public-Key Cryptography

In this paper, we propose a variant of the McEliece cryptosystem, called LRPC-Kronecker cryptosystem. LRPC-Kronecker product codes are LRPC codes with higher rank and better error-correction capability. For this, we introduce a new decoding algorithm using blocks which has lower decoding complexity and higher error-correction capability compared to those of the LRPC decoding algorithm. Furthermore, it is shown that this scheme is secure against existing attacks.

###
A Note on Subgroup Security in Pairing-Based Cryptography

Barreto~et al.\ (LATINCRYPT~2015) proposed a security notion, called *subgroup security,* for elliptic curves in pairing-based cryptography. They also claimed that, in some schemes, if an elliptic curve is subgroup-secure, the membership check, called full membership check, can be replaced by a cheaper membership check, called light membership check, which results in faster schemes than the original ones. However, they also noticed that some schemes will not maintain security if this replacement is done. It is unclear what schemes allow a secure replacement of the membership check. In this paper, we show a concrete example of insecurity in the sense of subgroup security in order to help developers understand what subgroup security is and what properties are actually preserved. In our conclusion, we recommend the developers to use the full membership check because it is a simple and general technique to securely implement schemes. If the developers use the light membership check for performance reasons, it is critical to carefully check that security is preserved.

###
On Several Verifiable Random Functions and the q-decisional Bilinear Diffie-Hellman Inversion Assumption

In 1999, Micali, Rabin and Vadhan introduced the notion of Verifiable Random Functions (VRF)\citeFOCS:MicRabVad99. VRFs compute for a given input *x* and a secret key $sk$ a unique function value $y=V_sk (x)$, and additionally a publicly verifiable proof π. Each owner of the corresponding public key $pk$ can use the proof to non-interactivly verify that the function value was computed correctly. Furthermore, the function value provides the property of pseudorandomness. Most constructions in the past are based on q-type assumptions. Since these assumptions get stronger for a larger factor q, it is desirable to show the existence of VRFs under static or general assumptions. In this work we will show for the constructions presented in \citePKC:DodYam05 \citeCCS:BonMonRag10 the equivalence of breaking the VRF and solving the underlying q-type assumption.

###
SoK: The Problem Landscape of SIDH

The Supersingular Isogeny Diffie-Hellman protocol (SIDH) has recently been the subject of increased attention in the cryptography community. Conjecturally quantum-resistant, SIDH has the feature that it shares the same data flow as ordinary Diffie-Hellman: two parties exchange a pair of public keys, each generated from a private key, and combine them to form a shared secret. To create a potentially quantum-resistant scheme, SIDH depends on a new family of computational assumptions involving isogenies between supersingular elliptic curves which replace both the discrete logarithm problem and the computational and decisional Diffie-Hellman problems. As in the case of ordinary Diffie-Hellman, one is interested in knowing if these problems are related. In fact, more is true: there is a rich network of reductions between the isogeny problems securing the private keys of the participants in the SIDH protocol, the computational and decisional SIDH problems, and the problem of validating SIDH public keys. In this article we explain these relationships, which do not appear elsewhere in the literature, in hopes of providing a clearer picture of the SIDH problem landscape to the cryptography community at large.