Publications

Journal Articles

1. DCC:THO24

   Chosen-Ciphertext Secure Code-Based Threshold Public Key Encryptions with Short Ciphertext

   Kota Takahashi, Keitaro Hashimoto, and Wakaha Ogata

   Designs, Codes and Cryptography, February 2024

   Abstract Springer

   

   Threshold public-key encryption (threshold PKE) has various useful applications. A lot of threshold PKE schemes are proposed based on RSA, Diffie-Hellman and lattice, but to the best of our knowledge, code-based threshold PKEs have not been proposed. In this paper, we provide three IND-CCA secure code-based threshold PKE schemes. The first scheme is the concrete instantiation of Dodis-Katz conversion (Dodis and Katz, TCC’05) that converts an IND-CCA secure PKE into an IND-CCA secure threshold PKE using parallel encryption and a signature scheme. This approach provides non-interactive threshold decryption, but ciphertexts are large (about 16 kilobytes for 128-bit security) due to long code-based signatures even in the state-of-the-art one. The second scheme is a new parallel encryption-based construction without signature schemes. Unlike the Dodis-Katz conversion, our parallel encryption converts an OW-CPA secure PKE into an OW-CPA secure threshold PKE. To enhance security, we use Cong et al.’s conversion (Cong et al., ASIACRYPT’21). Thanks to eliminating signatures, its ciphertext is 512 bytes, which is only 3% of the first scheme. The decryption process needs an MPC for computing hash functions, but decryption of OW-CPA secure PKE can be done locally. The third scheme is an MPC-based threshold PKE scheme from code-based assumption. We take the same approach Cong et al. took to construct efficient lattice-based threshold PKEs. We build an MPC for the decryption algorithm of OW-CPA secure Classic McEliece PKE. This scheme has the shortest ciphertext among the three schemes at just 192 bytes. Compared to the regular CCA secure Classic McEliece PKE, the additional ciphertext length is only 100 bytes. The cons are heavy distributed computation in the decryption process.

2. J. Cryptol.:HKKP22

   An Efficient and Generic Construction for Signal’s Handshake (X3DH): Post-Quantum, State Leakage Secure, and Deniable

   Keitaro Hashimoto, Shuichi Katsumata, Kris Kwiatkowski, and Thomas Prest

   Journal of Cryptology, May 2022

   Full version of [PKC:HKKP21].

   Abstract Springer Code

   

   The Signal protocol is a secure instant messaging protocol that underlies the security of numerous applications such as WhatsApp, Skype,Facebook Messenger among many others. The Signal protocol consists of two sub-protocols known as the X3DH protocol and the double ratchet protocol, where the latter has recently gained much attention. For instance, Alwen, Coretti, and Dodis (Eurocrypt’19) provided a concrete security model along with a generic construction based on simple building blocks that are instantiable from versatile assumptions, including post-quantum ones. In contrast, as far as we are aware, works focusing on the X3DH protocol seem limited. In this work, we cast the X3DH protocol as a specific type of authenticated key exchange (AKE) protocol, which we call a Signal-conforming AKE protocol, and formally define its security model based on the vast prior works on AKE protocols. We then provide the first efficient generic construction of a Signal-conforming AKE protocol based on standard cryptographic primitives such as key encapsulation mechanisms (KEM) and signature schemes. Specifically, this results in the first post-quantum secure replacement of the X3DH protocol based on well-established assumptions. Similar to the X3DH protocol, our Signal-conforming AKE protocol offers a strong(or stronger) flavor of security, where the exchanged key remains secure even when all the non-trivial combinations of the long-term secrets and session-specific secrets are compromised. Moreover, our protocol has a weak flavor of deniability and we further show how to progressively strengthen it using ring signatures and/or non-interactive zero-knowledge proof systems. Finally, we provide a full-fledged, generic C implementation of our (weakly deniable) protocol. We instantiate it with several Round 3 candidates (finalists and alternates) to the NIST post-quantum standardization process and compare the resulting bandwidth and computation performances. Our implementation is publicly available

3. Inf. Sci.:HO19

   Unrestricted and compact certificateless aggregate signature scheme

   Keitaro Hashimoto, and Wakaha Ogata

   Information Sciences, June 2019

   Abstract Elsevier

   

   A certificateless aggregate signature (CLAS) scheme employing a reduced signature size eliminates the complexity of certificate management in a traditional public key cryptosystem. A compact aggregate signature, where the size does not depend on the aggregate number, is desirable when the objective is to reduce storage cost and bandwidth. However, in conventional compact CLAS schemes, aggregation of signatures is restricted. The state information is meant to be used only once for security; it is generally used to restrict aggregation to signatures generated with the same state information. This paper proposes the first unrestricted and compact CLAS scheme where the signature size is constant and any combination of signatures can be aggregated. Aside from convenient storage and communication costs, our scheme is also equipped with a secure system against realistic adversaries. Moreover, we evaluate the performance of our CLAS scheme and demonstrate its effectiveness. Finally, this paper reveals that it is not possible to construct an unrestricted and compact CLAS scheme for a widely used structure with constant pairing computation.

Conference Articles

1. SCN:ZHO24

   Security Model for Authenticated Key Exchange, Reconsidered

   Xichen Zhang, Keitaro Hashimoto, and Wakaha Ogata

   In International Conference on Security and Cryptography for Networks (SCN), September 2024

   Abstract Springer

   

   Authenticated key exchange (AKE) is a fundamental cryptographic protocol that establishes a secure channel over the Internet. The security for AKE is defined as a security game between an adversary and the challenger. Especially, partners and freshness of the session are used to identify trivial attacks by the adversary. Roughly, partners are instances that derive the same session key, and freshness determines whether an adversary’s behavior constitutes trivial attacks. In this work, we reconsider security definitions for AKE and point out the shortcomings of the conventional partners and freshness definition. Then, we propose a new robust and strong security definition. First, we propose a new definition of partners based on round identifiers. Second, we propose a new freshness definition, which captures more non-trivial attacks than the conventional ones. We introduce a new notion of miscommunicators to identify the adversary’s behavior more accurately than conventional definitions. This allows, for example, the behavior of sending the first message as-is and tampering with the second message to be viewed as a non-trivial attack, which was considered a trivial attack in conventional definitions. Our new security definition is strictly stronger than the conventional one. As evidence of this, we provide a new construction of AKE that is secure in the conventional definition but insecure in the new definition.

2. CFAIL:YOH24

   Towards a Tightly Secure Signature in Multi-User Setting with Corruptions Based on Search Assumptions

   Hirofumi Yoshioka, Wakaha Ogata, and Keitaro Hashimoto

   In Conference for Failed Approaches and Insightful Losses in Cryptology (CFAIL), August 2024

   Abstract CFAIL Web Site EPRINT Video Slides

   This paper is a report on how we tackled constructing a digital signature scheme whose multi-user security with corruption can be tightly reduced to search assumptions. First, We reveal two new properties of signature schemes whose security cannot be tightly reduced to standard assumptions. More precisely, we generalize the negative result of Pan and Wagner, which shows that the reduction loss of the concrete signature scheme, called the Parallel-OR signature scheme, is lower bounded by the number of users. From this negative result, we have precious knowledge about designing a signature scheme that is tightly secure in multi-user settings with corruption. Next, we show a concrete construction of signature schemes based on the first result. Our scheme’s multi-user security can be reduced to the CDH assumption, and the reduction loss does not depend on the number of users, but, unfortunately, the loss linearly depends on the number of random oracle queries issued by the adversary. So, it remains open whether we can construct a signature scheme whose multi-user security with corruption can be tightly reduced to search assumptions.

3. CANS:CHHTS24

   How to Apply Fujisaki-Okamoto Transformation to Registration-Based Encryption

   Sohto Chiku, Keisuke Hara, Keitaro Hashimoto, Toi Tomita, and Junji Shikata

   In International Conference on Cryptology And Network Security (CANS), September 2024

   Abstract Springer

   

   Registration-based encryption (RBE) is a solution for the key-escrow problem in identity-based encryption. Initial RBE schemes are too theoretical and inefficient, but recent advances make RBE schemes efficient enough to be incorporated into real-world systems. On the other hand, from a security point of view, existing schemes are insufficient for such systems because they only consider CPA security. Recently, Glaeser et al. (ACM CCS’23) presented a solution to this problem. They suggested the usage of the original Fujisaki-Okamoto (FO) transformation (CRYPTO’99) to realize CCA-secure RBE. However, they did not provide its formal analysis because they considered it can be applied in a straightforward manner. In this work, we reveal that the FO transformation for RBE is non-trivial, and provide an appropriate one suitable to RBE. The essence of achieving CCA security through FO transformation is that the receiver verifies that the received ciphertext is correctly generated by re-encryption. In RBE, we find that the sender and receiver must share the public parameter used for encryption since the decryption algorithm does not take it by default. Therefore, we make the sender explicitly send the current public parameter as part of the ciphertext. Furthermore, we show that a sufficiently large min-entropy of ciphertexts (so-called well-spreadness) is necessary to apply the FO transformation to RBE, in contrast to PKE or IBE. This property guarantees that no information is leaked from the decryption oracle even if the public parameter in the ciphertext is replaced. Based on these observations, we propose a new FO transformation tailored to RBE, which allows existing CPA-secure RBE schemes to be transformed into CCAsecure ones correctly.

4. RWC:HKPPW24

   More Efficient Protocols for Post-Quantum Secure Messaging

   Keitaro Hashimoto, Shuichi Katsumata, Eamonn W. Postlethwaite, Thomas Prest, and Bas Westerbaan

   In Real World Crypto (RWC), March 2024

   Talk based on [CCS:HKPPW21] and [AC:KKPP20].

   Abstract Video Slides

   The past year has marked significant progress in secure messaging technologies. In March 2023, the Messaging Layer Security (MLS) protocol was standardized by the IETF, followed by Signal’s introduction in May 2023 of PQXDH, a post-quantum alternative to the X3DH handshake. In the first part of this presentation, we identify scalability challenges that may hinder the widespread adoption of MLS and Signal in a post-quantum context, particularly in regions with limited mobile data plans. This analysis is backed by real-world quantitative data. In the second part of this talk, we propose a novel protocol with improved bandwidth consumption. It incorporates efficient post-quantum primitives, specifically multi-recipient public key encryption (mPKEs), optimized for secure messaging. We anticipate that our approach will be an order of magnitude more efficient than direct adaptations of existing protocols in practical scenarios.

5. RWC:HKP23

   Metadata Protection for MLS and Its Variants

   Keitaro Hashimoto, Shuichi Katsumata, and Thomas Prest

   In Real World Crypto (RWC), March 2023

   Talk based on [CCS:HKP22].

   Abstract Video Slides

   In this talk, we first systematically analyze the privacy offered by Signal and MLS and observe a critical shortcoming of MLS compared to Signal. In short, MLS leaks much more _metadata_ than Signal. In privacy-critical scenarios, dismissing this metadata leakage puts at risk the users who may otherwise believe that MLS offers the exact same level of security as Signal. We then propose an efficient and provably secure solution to bootstrap the current MLS to be as metadata-hiding (or, in some metrics, even more) as Signal. Our key insight is to leverage the existence of a unique continuously evolving group secret key shared by the group to perform an anonymous membership authentication protocol.

6. CCS:HKP22

   How to Hide MetaData in MLS-Like Secure Group Messaging: Simple, Modular, and Post-Quantum

   Keitaro Hashimoto, Shuichi Katsumata, and Thomas Prest

   In The ACM Conference on Computer and Communications Security (ACM CCS), November 2022

   Awareded Abstract ACM DL EPRINT Slides

   

   Grand prize of Tsujii Shigeo Security Award 2023

   Secure group messaging (SGM) protocols allow large groups of users to communicate in a secure and asynchronous manner. In recent years, continuous group key agreements (CGKAs) have provided a powerful abstraction to reason on the security properties we expect from SGM protocols. While robust techniques have been developed to protect the contents of conversations in this context, it is in general more challenging to protect metadata (e.g. the identity and social relationships of group members), since their knowledge is often needed by the server in order to ensure the proper function of the SGM protocol.
   
   In this work, we provide a simple and generic wrapper protocol that upgrades non-metadata-hiding CGKAs into metadata-hiding CGKAs. Our key insight is to leverage the existence of a unique continuously evolving group secret key shared among the group members. We use this key to perform a group membership authentication protocol that convinces the server in an anonymous manner that a user is a legitimate group member. Our technique only uses a standard signature scheme, and thus, the wrapper protocol can be instantiated from a wide range of assumptions, including post-quantum ones. It is also very efficient, as it increases the bandwidth cost of the underlying CGKA operations by at most a factor of two.
   
   To formally prove the security of our protocol, we use the universal composability (UC) framework and model a new ideal functionality F^mh_CGKA capturing the correctness and security guarantee of metadata-hiding CGKA. To capture the above intuition of a “wrapper” protocol, we also define a restricted ideal functionality F^ctxt_CGKA, which roughly captures a non-metadata-hiding CGKA. We then show that our wrapper protocol UC-realizes F^mh_CGKA in the F^ctxt_CGKA-hybrid model, which in particular formalizes the intuition that any non-metadata-hiding CGKA can be modularly bootstrapped into metadata-hiding CGKA.

7. CCS:HKPPW21

   A Concrete Treatment of Efficient Continuous Group Key Agreement via Multi-Recipient PKEs

   Keitaro Hashimoto, Shuichi Katsumata, Eamonn W. Postlethwaite, Thomas Prest, and Bas Westerbaan

   In The ACM Conference on Computer and Communications Security (ACM CCS), November 2021

   Awareded Abstract ACM DL EPRINT Video Code Slides

   

   Tsujii Shigeo Security Award 2022

   Continuous group key agreements (CGKAs) are a class of protocols that can provide strong security guarantees to secure group messaging protocols such as Signal and MLS. Protection against device compromise is provided by commit messages: at a regular rate, each group member may refresh their key material by uploading a commit message, which is then downloaded and processed by all the other members. In practice, propagating commit messages dominates the bandwidth consumption of existing CGKAs.
   
   We propose Chained CmPKE, a CGKA with an asymmetric bandwidth cost: in a group of N members, a commit message costs O(N) to upload and O(1) to download, for a total bandwidth cost of O(N). In contrast, TreeKEM [19, 24, 76] costs Ω(logN)in both directions, for a total cost Ω(NlogN). Our protocol relies on generic primitives, and is therefore readily post-quantum.
   
   We go one step further and propose post-quantum primitives that are tailored to Chained CmPKE, which allows us to cut the growth rate of uploaded commit messages by two or three orders of magnitude compared to naive instantiations. Finally, we realize a software implementation of Chained CmPKE. Our experiments show that even for groups with a size as large as N=2^10, commit messages can be computed and processed in less than 100 ms.

8. PKC:HKKP21

   An Efficient and Generic Construction for Signal’s Handshake (X3DH): Post-Quantum, State Leakage Secure, and Deniable

   Keitaro Hashimoto, Shuichi Katsumata, Kris Kwiatkowski, and Thomas Prest

   In International Conference on Practice and Theory of Public-Key Cryptography (PKC), May 2021

   Awareded Abstract Springer EPRINT Video Code Slides

   Tsujii Shigeo Security Award 2021

   The Signal protocol is a secure instant messaging protocol that underlies the security of numerous applications such as WhatsApp, Skype, Facebook Messenger among many others. The Signal protocol consists of two sub-protocols known as the X3DH protocol and the double ratchet protocol, where the latter has recently gained much attention. For instance, Alwen, Coretti, and Dodis (Eurocrypt’19) provided a concrete security model along with a generic construction based on simple building blocks that are instantiable from versatile assumptions, including post-quantum ones. In contrast, as far as we are aware, works focusing on the X3DH protocol seem limited.
   
   In this work, we cast the X3DH protocol as a specific type of authenticated key exchange (AKE) protocol, which we call a Signal-conforming AKE protocol, and formally define its security model based on the vast prior work on AKE protocols. We then provide the first efficient generic construction of a Signal-conforming AKE protocol based on standard cryptographic primitives such as key encapsulation mechanisms (KEM) and signature schemes. Specifically, this results in the first post-quantum secure replacement of the X3DH protocol on well-established assumptions. Similar to the X3DH protocol, our Signal-conforming AKE protocol offers a strong (or stronger) flavor of security, where the exchanged key remains secure even when all the non-trivial combinations of the long-term secrets and session-specific secrets are compromised. Moreover, our protocol has a weak flavor of deniability and we further show how to strengthen it using ring signatures. Finally, we provide a full-fledged, generic C implementation of our (weakly deniable) protocol. We instantiate it with several Round 3 candidates (finalists and alternates) to the NIST post-quantum standardization process and compare the resulting bandwidth and computation performances. Our implementation is publicly available.

Preprints

1. EPRINT:CHHS23

   Identity-Based Matchmaking Encryption, Revisited: Improved Constructions with Strong Security

   Sohto Chiku, Keitaro Hashimoto, Keisuke Hara, and Junji Shikata

   Cryptology ePrint Archive, Report 2023/1435 , September 2023

   Abstract EPRINT

   Identity-based matchmaking encryption (IB-ME) [Ateniese et al. Crypto 2019] allows users to communicate privately in an anonymous and authenticated manner. After the seminal paper by Ateniese et al., a lot of work has been done on the security and construction of IB-ME. In this work, we revisit the security definitions of IB-ME and provide improved constructions of it. First, we classify the existing security notions of IB-ME, systematically categorizing privacy into three categories (CPA, CCA, and privacy in the case of mismatch) and authenticity into four categories (NMA and CMA both against insiders and outsiders).In particular, we reconsider the privacy when the sender’s identity is mismatched during decryption, and provide a new simple security game, called mismatch security, capturing the essence of it. Second, we propose efficient and strongly secure IB-ME schemes from the bilinear Diffie-Hellman assumption in the random oracle model and from anonymous identity-based encryption, identity-based signature, and reusable extractors in the standard model. The first scheme is based on Boneh-Franklin IBE similar to the Ateniese et al. scheme, but ours achieves a more compact decryption key and ciphertext and stronger CCA-privacy, CMA-authenticity, and mismatch security. The second scheme is an improved generic construction, which active not only stronger security but also the shortest ciphertext among existing generic constructions. Through this construction, we obtain, for example, a more efficient scheme from the symmetric external Diffie-Hellman assumption in the standard model, and a practical scheme from lattices in the quantum random oracle model.

2. EPRINT:HOT19

   Tight reduction for generic construction of certificateless signature and its instantiation from DDH assumption

   Keitaro Hashimoto, Wakaha Ogata, and Toi Tomita

   Cryptology ePrint Archive, Report 2019/1367 , November 2019

   Abstract EPRINT

   Certificateless signature was proposed by Al-Riyami and Paterson to eliminate the certificate management in the public-key infrastructures and solve the key escrow problem in the identity-based signature. In 2007, Hu et al. proposed a generic construction of certificateless signature. They construct certificateless signature scheme from any standard identity-based signature and signature scheme. However, their security reduction is loose; the security of the constructed scheme depends on the number of users. In this paper, we give the tight reduction for their construction and instantiate a tightly-secure certificateless signature scheme without pairing from DDH assumption. Best of our knowledge, this scheme is the first tightly-secure certificateless signature scheme.

Miscellaneous

1. SCIS:CHHS24

   BDH仮定に基づく高効率かつ強安全なIDベースマッチメイキング暗号

   知久奏斗,  橋本啓太郎,  原啓祐, and  四方順司

   2024年暗号と情報セキュリティシンポジウム (SCIS2024) , January 2024

   See also [EPRINT:CHHS23].
2. SCIS:YOH24

   デジタル署名の複数ユーザセキュリティにおける帰着ロスの下限について

   吉岡啓史,  尾形わかは, and  橋本啓太郎

   2024年暗号と情報セキュリティシンポジウム (SCIS2024) , January 2024

   See also [CFAIL:YOH24].
3. SCIS:HYH24

   On the Security of Multi-Designated Verifier Signature

   Keitaro Hashimoto, Kyosuke Yamashita, and Keisuke Hara

   2024年暗号と情報セキュリティシンポジウム (SCIS2024) , January 2024

   The improved version of this paper is under submission.
4. SCIS:HYH24

   組み込み機器向けファームウェア更新における脅威抽出と課題提起

   橋本啓太郎,  伊東真理,  小川知之,  佐藤眞司,  辛星漢, and  吉田博隆

   2024年暗号と情報セキュリティシンポジウム (SCIS2024) , January 2024
5. CSS:AHHAW24

   A Generic Construction of Deletable Registered Attribute-Based Encryption from Slotted Registered Attribute-Based Encryption

   Kyoichi Asano, Keisuke Hara, Keitaro Hashimoto, Nuttapong Attrapadung, and Yohei Watanabe

   コンピュータセキュリティシンポジウム2024 (CSS 2024) , October 2024

   Awareded

   Best Student Paper Award

6. CSS:CHHTS24

   CCA安全な登録ベース暗号

   知久奏斗,  原啓祐,  橋本啓太郎,  冨田斗威, and  四方順司

   コンピュータセキュリティシンポジウム2024 (CSS 2024) , October 2024

   See also [CANS:CHHTS24].

   Awareded

   Best Paper Award

7. SCIS:HKKP21

   Signal に適用可能な耐量子認証鍵交換プロトコルの設計と実装

   橋本啓太郎,  勝又秀一, Kris Kwiatkowski, and Thomas Prest

   2021年暗号と情報セキュリティシンポジウム (SCIS2021) , January 2021

   See also [PKC:HKKP21].

   Awareded

   Best Paper Award

8. SCIS:HOT20

   Certificateless signature の一般的構成法に対するタイトな帰着とDDH仮定に基づく構成

   橋本啓太郎,  尾形わかは, and  冨田斗威

   2020年暗号と情報セキュリティシンポジウム (SCIS2020) , January 2020

   See also [EPRINT:HOT19].
9. SCIS:HO18

   Certificateless Aggregate Signature Schemeの構成法と安全性に関する研究

   橋本啓太郎, and  尾形わかは

   2018年暗号と情報セキュリティシンポジウム (SCIS2018) , January 2018

   See also [Inf. Sci.:HO19].

Theses

1. Ph.D. Thesis

   Construction and Analysis of Post-Quantum Key Exchange Protocols for Secure Messaging

   Keitaro Hashimoto

   Tokyo Institute of Technology , March 2023

   This is based on [J. Cryptol.:HKKP22], [CCS:HKPPW21] and [CCS:HKP22]. There are several typos.

   Awareded Abstract Tokyo Tech Research Repository

   Seiichi Tejima Research Award Doctoral Dissertation Award

   See Tokyo Tech Research Repository

2. Master Thesis

   Certificateless signatureの構成法に関する研究

   Keitaro Hashimoto

   Tokyo Institute of Technology , March 2020

   A part of this work was published as [EPRINT:HOT19].
3. Bachelor Thesis

   Certificateless Aggregate Signature Schemeの構成法と安全性に関する研究

   Keitaro Hashimoto

   Tokyo Institute of Technology , March 2018

   A part of this work was published as [Inf. Sci.:HO19].