## CryptoDB

### Willy Susilo

#### Publications

Year
Venue
Title
2022
EUROCRYPT
Unique signatures are digital signatures with exactly one unique and valid signature for each message. The security reduction for most unique signatures has a natural reduction loss (in the existentially unforgeable against chosen-message attacks, namely EUF-CMA, security model under a non-interactive hardness assumption). In Crypto 2017, Guo {\it et al.} proposed a particular chain-based unique signature scheme where each unique signature is composed of $n$ BLS signatures computed sequentially like a blockchain. Under the computational Diffie-Hellman assumption, their reduction loss is $n\cdot q_H^{1/n}$ for $q_H$ hash queries and it is logarithmically tight when $n=\log{q_H}$. However, it is currently unknown whether a better reduction than logarithmical tightness for the chain-based unique signatures exists. We show that the proposed chain-based unique signature scheme by Guo {\it et al.} must have the reduction loss $q^{1/n}$ for $q$ signature queries when each unique signature consists of $n$ BLS signatures. We use a meta reduction to prove this lower bound in the EUF-CMA security model under any non-interactive hardness assumption, and the meta-reduction is also applicable in the random oracle model. We also give a security reduction with reduction loss $4\cdot q^{1/n}$ for the chain-based unique signature scheme (in the EUF-CMA security model under the CDH assumption). This improves significantly on previous reduction loss $n\cdot q_H^{1/n}$ that is logarithmically tight at most. The core of our reduction idea is a {\em non-uniform} simulation that is specially invented for the chain-based unique signature construction.
2022
EUROCRYPT
In this paper, we propose a practical signature scheme based on the alternating trilinear form equivalence problem. Our scheme is inspired from the Goldreich-Micali-Wigderson's zero-knowledge protocol for graph isomorphism, and can be served as an alternative candidate for the NIST's post-quantum digital signatures. First, we present theoretical evidences to support its security, especially in the post-quantum cryptography context. The evidences are drawn from several research lines, including hidden subgroup problems, multivariate cryptography, cryptography based on group actions, the quantum random oracle model, and recent advances on isomorphism problems for algebraic structures in algorithms and complexity. Second, we demonstrate its potential for practical uses. Based on algorithm studies, we propose concrete parameter choices, and then implement a prototype. One concrete scheme achieves 128 bit security with public key size ~4100 bytes, signature size ~6800 bytes, and running times (key generation, sign, verify) ~0.8ms on a common laptop computer.
2022
CRYPTO
A software watermarking scheme can embed a message into a program while preserving its functionality. The embedded message can be extracted later by an extraction algorithm, and no one could remove it without significantly changing the functionality of the program. A watermarking scheme is public key if neither the marking procedure nor the extraction procedure needs a watermarking secret key. Prior constructions of watermarking schemes mainly focus on watermarking pseudorandom functions (PRFs), and the major open problem in this direction is to construct a public-key watermarkable PRF. In this work, we solve the open problem via constructing public-key watermarkable PRFs with different trade-oﬀs from various assumptions, ranging from standard lattice assumptions to the existence of indistinguishability obfuscation. To achieve the results, we first construct watermarking schemes in a weaker model, where the extraction algorithm is provided with a “hint” about the watermarked PRF key. Then we upgrade the constructions to standard watermarking schemes using a robust unobfuscatable PRF. We also provide the first construction of robust unobfuscatable PRF in this work, which is of independent interest.
2022
CRYPTO
We introduce Multimodal Private Signature (MPS) - an anonymous signature system that offers a novel accountability feature: it allows a designated opening authority to learn \emph{some partial information}~$\ms{op}$ about the signer's identity $\ms{id}$, and nothing beyond. Such partial information can flexibly be defined as $\ms{op} = \ms{id}$ (as in group signatures), or as $\ms{op} = \mb{0}$ (like in ring signatures), or more generally, as $\ms{op} = G_j(\ms{id})$, where $G_j(\cdot)$ is certain disclosing function. Importantly, the value of $op$ is known in advanced by the signer, and hence, the latter can decide whether she/he wants to disclose that piece of information. The concept of MPS significantly generalizes the notion of tracing in traditional anonymity-oriented signature primitives, and can enable various new and appealing privacy-preserving applications. We formalize the definitions and security requirements for MPS. We next present a generic construction to demonstrate the feasibility of designing MPS in a modular manner and from commonly used cryptographic building blocks (ordinary signatures, public-key encryption and NIZKs). We also provide an efficient construction in the standard model based on pairings, and a lattice-based construction in the random oracle model.
2021
PKC
Group encryption (\textsf{GE}), introduced by Kiayias, Tsiounis and Yung (Asiacrypt'07), is the encryption analogue of group signatures. It allows to send verifiably encrypted messages satisfying certain requirements to certified members of a group, while keeping the anonymity of the receivers. Similar to the tracing mechanism in group signatures, the receiver of any ciphertext can be identified by an opening authority - should the needs arise. The primitive of \textsf{GE} is motivated by a number of interesting privacy-preserving applications, including the filtering of encrypted emails sent to certified members of an organization. This paper aims to improve the state-of-affairs of \textsf{GE} systems. Our first contribution is the formalization of fully dynamic group encryption (\textsf{FDGE}) - a \textsf{GE} system simultaneously supporting dynamic user enrolments and user revocations. The latter functionality for \textsf{GE} has not been considered so far. As a second contribution, we realize the message filtering feature for \textsf{GE} based on a list of $t$-bit keywords and $2$ commonly used policies: permissive'' - accept the message if it contains at least one of the keywords as a substring; prohibitive'' - accept the message if all of its $t$-bit substrings are at Hamming distance at least $d$ from all keywords, for $d \geq 1$. This feature so far has not been substantially addressed in existing instantiations of \textsf{GE} based on DCR, DDH, pairing-based and lattice-based assumptions. Our third contribution is the first instantiation of GE under code-based assumptions. The scheme is more efficient than the lattice-based construction of Libert et al. (Asiacrypt'16) - which, prior to our work, is the only known instantiation of \textsf{GE} under post-quantum assumptions. Our scheme supports the $2$ suggested policies for message filtering, and in the random oracle model, it satisfies the stringent security notions for \textsf{FDGE} that we put forward.
2021
ASIACRYPT
Group encryption (GE) is a fundamental privacy-preserving primitive analog of group signatures, which allows users to decrypt speciﬁc ciphertexts while hiding themselves within a crowd. Since its ﬁrst birth, numerous constructions have been proposed, among which the schemes separately constructed by Libert et al. (Asiacrypt 2016) over lattices and by Nguyen et al. (PKC 2021) over coding theory are postquantum secure. Though the last scheme, at the ﬁrst time, achieved the full dynamicity (allowing group users to join or leave the group in their ease) and message ﬁltering policy, which greatly improved the state-of-aﬀairs of GE systems, its practical applications are still limited due to the rather complicated design, ineﬃciency and the weaker security (secure in the random oracles). In return, the Libert et al.’s scheme possesses a solid security (secure in the standard model), but it lacks the previous functions and still suﬀers from ineﬃciency because of extremely using lattice trapdoors. In this work, we re-formalize the model and security deﬁnitions of fully dynamic group encryption (FDGE) that are essentially equivalent to but more succinct than Nguyen et al.’s; Then, we provide a generic and eﬃcient zero-knowledge proof method for proving that a binary vector is non-zero over lattices, on which a proof for the Prohibitive message ﬁltering policy in the lattice setting is ﬁrst achieved (yet in a simple manner); Finally, by combining appropriate cryptographic materials and our presented zero-knowledge proofs, we achieve the ﬁrst latticebased FDGE schemes in a simpler manner, which needs no any lattice trapdoor and is proved secure in the standard model (assuming interaction during the proof phase), outweighing the existing post-quantum secure GE systems in terms of functions, eﬃciency and security.
2020
ASIACRYPT
Public key encryption (PKE) schemes are usually deployed in an open system with numerous users. In practice, it is common that some users are corrupted. A PKE scheme is said to be receiver selective opening (RSO) secure if it can still protect messages transmitted to uncorrupted receivers after the adversary corrupts some receivers and learns their secret keys. This is usually defined by requiring the existence of a simulator that can simulate the view of the adversary given only the opened messages. Existing works construct RSO secure PKE schemes in a single-challenge setting, where the adversary can only obtain one challenge ciphertext for each public key. However, in practice, it is preferable to have a PKE scheme with RSO security in the multi-challenge setting, where public keys can be used to encrypt multiple messages. In this work, we explore the possibility for achieving PKE schemes with receiver selective opening security in the multi-challenge setting. Our contributions are threefold. First, we demonstrate that PKE schemes with RSO security in the single-challenge setting are not necessarily RSO secure in the multi-challenge setting. Then, we show that it is impossible to achieve RSO security for PKE schemes if the number of challenge ciphertexts under each public key is a priori unbounded. In particular, we prove that no PKE scheme can be RSO secure in the $k$-challenge setting (i.e., the adversary can obtain $k$ challenge ciphertexts for each public key) if its secret key contains less than $k$ bits. On the positive side, we give a concrete construction of PKE scheme with RSO security in the $k$-challenge setting, where the ratio of the secret key length to $k$ approaches the lower bound 1.
2017
CRYPTO
2016
ASIACRYPT
2016
ASIACRYPT
2012
PKC
2010
PKC
2010
FSE
2009
EUROCRYPT
2009
FSE
2008
PKC
2008
ASIACRYPT
2007
PKC
2005
ASIACRYPT
2005
PKC
2004
PKC

Asiacrypt 2021
Asiacrypt 2020
Asiacrypt 2013
Asiacrypt 2011
Asiacrypt 2010