ABSTRACT. At ASIACRYPT 2020, Alamati et al. formalized the framework of group actions for abstracting isogeny-based cryptosystems. At CRYPTO 2022, Abdalla et al. extended the framework to represent the quardratic twist of elliptic curves, and proposed the first provably secure and tightly-secure one-round isogeny-based password authenticated key exchange (PAKE) scheme (X-GA-PAKE) by a bit-by-bit approach. However, in X-GA-PAKE, for the password length $\ell$, the number of group actions per party is $5\ell$ and the communication complexity per party is $2\ell$, thus there is a problem in efficiency. In this paper, we propose an efficient one-round PAKE scheme that reduces the number of group actions and the communication complexity compared to X-GA-PAKE. In X-GA-PAKE, it is necessary to send/receive $2\ell$ elements to prevent trivial attacks using twists, but in our scheme, by reducing $\ell$ elements of them to the number of common reference string (CRS), we can reduce the number of group actions per party to $4\ell+2|CRS|$ and the communication complexity per party to $\ell+|CRS|$. In addition, we show the tight security in the one-round PAKE security model based on the same assumptions as in X-GA-PAKE.

ABSTRACT. In homomorphic signatures for subset predicates (HSSB), each message (to be signed) is a set. Any signature on a set M allows us to derive a signature on any subset M' of M. Its superset version, which should be called homomorphic signatures for superset predicates (HSSP), allows us to derive a signature on any superset M' of M. In this paper, we propose homomorphic signatures for subset and superset mixed predicates (HSSM) as a simple combination of HSSB and HSSP. In HSSM, any signature on a message of a set-pair (M, W) allows us to derive a signature on any (M', W') such that M' is a subset of M and W' is a superset of W. We propose an original HSSM scheme which is unforgeable under the decisional linear assumption and completely context-hiding. We show that HSSM has various applications, which include disclosure-controllable HSSB, disclosure-controllable redactable signatures, (key-delegatable) superset/subset predicate signatures, and wildcarded identity-based signatures.

ABSTRACT. Despite offering numerous advantages, public decentralized cryptocurrencies such as Bitcoin suffer from scalability issues such as high transaction latency and low throughput. The vast array of so-called Layer-2 solutions tackling the scalability problem focus on throughput, and consider latency as a secondary objective. However, in the context of retail payments, instant finality of transactions is arguably a more pressing concern, besides the overarching concern for privacy.

In this paper, we provide an overlay network providing privacy-friendly low latency payments in a retail market privately. Our approach follows that of a recent work called Snappy, which achieved low latency but exposed identities of customers and their transaction histories. Our construction ensures this data is kept private, while providing merchants with protection against double-spending attacks. Although our system is still based upon customers registering with a collateral, crucially this collateral is reusable over time.

The technical novelty of our work comes from randomness-reusable threshold encryption (RRTE), a cryptographic primitive we designed specifically for the following features: our construction provable guarantees payments to merchants, preserves the secret identity of honest customers and prevents their transactions from being linked. We also present an implementation of our construction, showing the capacity for fast global payments in a retail setting with a delay of less than 1 second.

ABSTRACT. Homomorphic secret sharing (HSS) allows participants to share their private data among computing servers for joint computation of a public function without fully homomorphic encryption. It can serve as a competitive alternative to somewhat/fully homomorphic encryption (HE) in some scenarios. While the existing HSS schemes that enable computation on private data from independent multiple parties either only support a small number of parties for computing constant-degree polynomials, or involve relatively complex multi-key HE in their constructions. In this paper, we first introduce the formal notion of multi-key HSS, and propose a multi-key two-server HSS scheme from LWE without multi-key HE, by leveraging the technique of homomorphic linear combination that previously used to construct multi-key FHE from GSW-FHE in [1]. As a result, our scheme supports secure outsourcing computation of restricted multiplication straight-line (RMS) programs over private data from multiple independent sources, and the number of input clients and the degree of evaluated polynomials can be as high as a polynomial in the security parameter. Finally, we prove the security of the multi-key HSS scheme, and provide a concrete implementation.

ABSTRACT. CSI-FiSh is one of the most efficient isogeny-based signature schemes, which is proven to be secure in the Quantum Random Oracle Model (QROM). However, there is a bottleneck in CSI-FiSh in the threshold setting, which is that its public key needs to be generated by using $k-1$ secret keys. This leads to very inefficient threshold key generation protocols and also forces the parties to store $k-1$ secret shares. We present CSI-SharK, a new variant of CSI-FiSh that has more Sharing-friendly Keys and is as efficient as the original scheme. This is accomplished by modifying the public key of the ID protocol, used in the original CSI-FiSh, to the equal length Structured Public Key (SPK), generated by a single secret key, and then proving that the modified ID protocol and the resulting signature scheme remain secure in the QROM. We translate existing CSI-FiSh-based threshold signatures and Distributed Key Generation (DKG) protocols to the CSI-SharK setting. We find that DKG schemes based on CSI-SharK outperform the state-of-the-art actively secure DKG protocols from the literature by a factor of about $3$, while also strongly reducing the communication cost between the parties. We also uncover and discuss a flaw in the key generation of the actively secure CSI-FiSh based threshold signature Sashimi, that can prevent parties from signing. Finally, we discuss how (distributed) key generation and signature schemes in the isogeny setting are strongly parallelizable and we show that by using $C$ independent CPU threads, the total runtime of such schemes can basically be reduced by a factor $C$. As multiple threads are standard in modern CPU architecture, this parallelizability is a strong incentive towards using isogeny-based (distributed) key generation and signature schemes in practical scenarios.

ABSTRACT. A key encapsulation mechanism (KEM) is a basic building block for key exchange which must be combined with long-term keys in order to achieve authenticated key exchange (AKE). Although several KEM-based AKE protocols have been proposed, KEM-based modular building blocks are not available. We provide a KEM-based authenticator and a KEM-based protocol in the Authenticated Links model (AM), in the terminology of Canetti and Krawczyk (2001). Using these building blocks we achieve a set of generic AKE protocols. By instantiating with post quantum primitives we are able to propose several new post-quantum secure AKE protocols.

ABSTRACT. A verifiable random function (VRF) allows the generation of a random number with publicly verifiable proof, showing that the random number is honestly generated. The practical VRF used in real-world applications considers the security of uniqueness, pseudorandomness, and unpredictability under malicious key generation. In this paper, we propose the security model of {\it related-key attack} to VRF for capturing attacks like tampering attacks. We propose a new construction of VRF that satisfies the RKA security together with the existing security requirements. We implement our VRF construction and demonstrate that our scheme is practical for real-world applications.

ABSTRACT. Searchable Encryption (SE) allows users to perform a keyword search over encrypted documents. In Eurocrypt'04, Boneh et al. introduced Public-key Encryption with Keyword Search (PEKS). Broadcast Encryption with Keyword Search (BEKS) is a natural progression to allow some amount of access control. Unfortunately, PEKS and BEKS both suffer from the keyword guessing attack (KGA). In the case of KGA, an adversary guesses the keyword encoded in a trapdoor by creating a ciphertext on a sequence of keywords of its choice and testing them against the trapdoor. In ACISP'21, Liu et al. introduced a variant of BEKS called Broadcast Authenticated Encryption with Keyword Search (BAEKS), which tried to mitigate KGA in BEKS. This construction did not argue consistency and achieved weaker security in the random oracle model.

In this work, we first introduce the notion of consistency for BAEKS and introduce security models much stronger than those of Liu et al. We propose a new statistically-consistent construction of BAEKS in the standard model that achieves security in the newly introduced models. Our proposal is proven adaptively secure under the well-studied bilateral Matrix Diffie-Hellman Assumption and still achieves asymptotic efficiency similar to that of Liu et al.