International Association for Cryptologic Research

International Association
for Cryptologic Research


Yanhong Xu


Fully Dynamic Attribute-Based Signatures for Circuits from Codes
Attribute-Based Signature (ABS), introduced by Maji et al. (CT-RSA'11), is an advanced privacy-preserving signature primitive that has gained a lot of attention. Research on ABS can be categorized into three main themes: expanding the expressiveness of signing policies, enabling new functionalities, and providing more diversity in terms of computational assumptions. We contribute to the development of ABS in all three dimensions, by providing a fully dynamic ABS scheme for arbitrary circuits from codes. The scheme is the first ABS from code-based assumptions and also the first ABS system offering the \texttt{full dynamicity} functionality (i.e., attributes can be enrolled and revoked simultaneously). Moreover, the scheme features much shorter signature size than a lattice-based counterpart proposed by El Kaafarani and Katsumata (PKC'18). In the construction process, we put forward a new theoretical abstraction of Stern-like zero-knowledge (ZK) protocols, which are the major tools for privacy-preserving cryptography from codes. Our main insight here actually lies in the questions we ask about the fundamental principles of Stern-like protocols that have remained unchallenged since their conception by Stern at CRYPTO'93. We demonstrate that these long-established principles are not essential, and then provide a refined framework generalizing existing Stern-like techniques and enabling enhanced constructions.
Bicameral and Auditably Private Signatures
This paper introduces Bicameral and Auditably Private Signatures (BAPS) -- a new privacy-preserving signature system with several novel features. In a BAPS system, given a certified attribute $\mathbf{x}$ and a certified policy $P$, a signer can issue a publicly verifiable signature $\Sigma$ on a message $m$ as long as $(m, \mathbf{x})$ satisfies $P$. A noteworthy characteristic of BAPS is that both attribute $\mathbf{x}$ and policy $P$ are kept hidden from the verifier, yet the latter is convinced that these objects were certified by an attribute-issuing authority and a policy-issuing authority, respectively. By considering \textsf{bicameral certification authorities} and requiring privacy for both attributes and policies, BAPS generalizes the spirit of existing advanced signature primitives with fine-grained controls on signing capabilities (e.g., attribute-based signatures, predicate signatures, policy-based signatures). Furthermore, BAPS provides an appealing feature named \textsf{auditable privacy}, allowing the signer of $\Sigma$ to verifiably disclose various pieces of partial information about $P$ and $\mathbf{x}$ when asked by auditor(s)/court(s) at later times. Auditable privacy is intrinsically different from and can be complementary to the notion of accountable privacy traditionally incorporated in traceable anonymous systems such as group signatures. Equipped with these distinguished features, BAPS can potentially address interesting application scenarios for which existing primitives do not offer a direct solution. We provide rigorous security definitions for BAPS, following a ``sim-ext'' approach. We then demonstrate a generic construction based on commonly used cryptographic building blocks, which makes use of a \textsf{sign-then-commit-then-prove} design. Finally, we present a concrete instantiation of BAPS, that is proven secure in the random oracle model under lattice assumptions. The scheme can handle arbitrary policies represented by polynomial-size Boolean circuits and can address quadratic disclosing functions. In the construction process, we develop a new technical building block that could be of independent interest: a zero-knowledge argument system allowing to prove the satisfiability of a certified-and-hidden Boolean circuit on certified-and-committed inputs.
Group Encryption: Full Dynamicity, Message Filtering and Code-Based Instantiation 📺
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.
Constant-Size Group Signatures from Lattices
Lattice-based group signature is an active research topic in recent years. Since the pioneering work by Gordon, Katz and Vaikuntanathan (Asiacrypt 2010), ten other schemes have been proposed, providing various improvements in terms of security, efficiency and functionality. However, in all known constructions, one has to fix the number N of group users in the setup stage, and as a consequence, the signature sizes are dependent on N.In this work, we introduce the first constant-size group signature from lattices, which means that the size of signatures produced by the scheme is independent of N and only depends on the security parameter $$\lambda $$λ. More precisely, in our scheme, the sizes of signatures, public key and users’ secret keys are all of order $$\widetilde{\mathcal {O}}(\lambda )$$O~(λ). The scheme supports dynamic enrollment of users and is proven secure in the random oracle model under the Ring Short Integer Solution (RSIS) and Ring Learning With Errors (RLWE) assumptions. At the heart of our design is a zero-knowledge argument of knowledge of a valid message-signature pair for the Ducas-Micciancio signature scheme (Crypto 2014), that may be of independent interest.