Huaxiong Wang

Xuankai Yang, Yan Wang, Xiuzhen Zhang et al.

Cross-domain fake news detection aims to mitigate domain shift and improve detection performance by transferring knowledge across domains. Existing approaches transfer knowledge based on news content and user engagements from a source domain to a target domain. However, these approaches face two main limitations, hindering effective knowledge transfer and optimal fake news detection performance. Firstly, from a micro perspective, they neglect the negative impact of veracity-irrelevant features in news content when transferring domain-shared features across domains. Secondly, from a macro perspective, existing approaches ignore the relationship between user engagement and news content, which reveals shared behaviors of common users across domains and can facilitate more effective knowledge transfer. To address these limitations, we propose a novel macro- and micro- hierarchical transfer learning framework (MMHT) for cross-domain fake news detection. Firstly, we propose a micro-hierarchical disentangling module to disentangle veracity-relevant and veracity-irrelevant features from news content in the source domain for improving fake news detection performance in the target domain. Secondly, we propose a macro-hierarchical transfer learning module to generate engagement features based on common users' shared behaviors in different domains for improving effectiveness of knowledge transfer. Extensive experiments on real-world datasets demonstrate that our framework significantly outperforms the state-of-the-art baselines.

Han Zhang, Yan Wang, Guanfeng Liu et al.

To enhance the reliability and credibility of graph neural networks (GNNs) and improve the transparency of their decision logic, a new field of explainability of GNNs (XGNN) has emerged. However, two major limitations severely degrade the performance and hinder the generalizability of existing XGNN methods: they (a) fail to capture the complete decision logic of GNNs across diverse distributions in the entire dataset's sample space, and (b) impose strict prerequisites on edge properties and GNN internal accessibility. To address these limitations, we propose OPEN, a novel c\textbf{O}mprehensive and \textbf{P}rerequisite-free \textbf{E}xplainer for G\textbf{N}Ns. OPEN, as the first work in the literature, can infer and partition the entire dataset's sample space into multiple environments, each containing graphs that follow a distinct distribution. OPEN further learns the decision logic of GNNs across different distributions by sampling subgraphs from each environment and analyzing their predictions, thus eliminating the need for strict prerequisites. Experimental results demonstrate that OPEN captures nearly complete decision logic of GNNs, outperforms state-of-the-art methods in fidelity while maintaining similar efficiency, and enhances robustness in real-world scenarios.

Jenn-Bing Ong, Wee-Keong Ng, Ivan Tjuawinata et al.

Data privacy is an important issue for organizations and enterprises to securely outsource data storage, sharing, and computation on clouds / fogs. However, data encryption is complicated in terms of the key management and distribution; existing secure computation techniques are expensive in terms of computational / communication cost and therefore do not scale to big data computation. Tensor network decomposition and distributed tensor computation have been widely used in signal processing and machine learning for dimensionality reduction and large-scale optimization. However, the potential of distributed tensor networks for big data privacy preservation have not been considered before, this motivates the current study. Our primary intuition is that tensor network representations are mathematically non-unique, unlinkable, and uninterpretable; tensor network representations naturally support a range of multilinear operations for compressed and distributed / dispersed computation. Therefore, we propose randomized algorithms to decompose big data into randomized tensor network representations and analyze the privacy leakage for 1D to 3D data tensors. The randomness mainly comes from the complex structural information commonly found in big data; randomization is based on controlled perturbation applied to the tensor blocks prior to decomposition. The distributed tensor representations are dispersed on multiple clouds / fogs or servers / devices with metadata privacy, this provides both distributed trust and management to seamlessly secure big data storage, communication, sharing, and computation. Experiments show that the proposed randomization techniques are helpful for big data anonymization and efficient for big data storage and computation.

Yanhong Xu, Reihaneh Safavi-Naini, Khoa Nguyen et al.

Policy-based signatures (PBS) were proposed by Bellare and Fuchsbauer (PKC 2014) to allow an {\em authorized} member of an organization to sign a message on behalf of the organization. The user's authorization is determined by a policy managed by the organization's trusted authority, while the signature preserves the privacy of the organization's policy. Signing keys in PBS do not include user identity information and thus can be passed to others, violating the intention of employing PBS to restrict users' signing capability. In this paper, we introduce the notion of {\em traceability} for PBS by including user identity in the signing key such that the trusted authority will be able to open a suspicious signature and recover the signer's identity should the needs arise. We provide rigorous definitions and stringent security notions of traceable PBS (TPBS), capturing the properties of PBS suggested by Bellare-Fuchsbauer and resembling the "full traceability" requirement for group signatures put forward by Bellare-Micciancio-Warinschi (Eurocrypt 2003). As a proof of concept, we provide a modular construction of TPBS, based on a signature scheme, an encryption scheme and a zero-knowledge proof system. Furthermore, to demonstrate the feasibility of achieving TPBS from concrete, quantum-resistant assumptions, we give an instantiation based on lattices.

Jun Zhao, Jing Tang, Li Zengxiang et al.

Formal analyses of blockchain protocols have received much attention recently. Consistency results of Nakamoto's blockchain protocol are often expressed in a quantity $c$, which denotes the expected number of network delays before some block is mined. With $μ$ (resp., $ν$) denoting the fraction of computational power controlled by benign miners (resp., the adversary), where $μ+ ν= 1$, we prove for the first time that to ensure the consistency property of Nakamoto's blockchain protocol in an asynchronous network, it suffices to have $c$ to be just slightly greater than $\frac{2μ}{\ln (μ/ν)}$. Such a result is both neater and stronger than existing ones. In the proof, we formulate novel Markov chains which characterize the numbers of mined blocks in different rounds.

Martianus Frederic Ezerman, Hyung Tae Lee, San Ling et al.

We solve an open question in code-based cryptography by introducing two provably secure group signature schemes from code-based assumptions. Our basic scheme satisfies the CPA-anonymity and traceability requirements in the random oracle model, assuming the hardness of the McEliece problem, the Learning Parity with Noise problem, and a variant of the Syndrome Decoding problem. The construction produces smaller key and signature sizes than the previous group signature schemes from lattices, as long as the cardinality of the underlying group does not exceed $2^{24}$, which is roughly comparable to the current population of the Netherlands. We develop the basic scheme further to achieve the strongest anonymity notion, i.e., CCA-anonymity, with a small overhead in terms of efficiency. The feasibility of two proposed schemes is supported by implementation results. Our two schemes are the first in their respective classes of provably secure groups signature schemes. Additionally, the techniques introduced in this work might be of independent interest. These are a new verifiable encryption protocol for the randomized McEliece encryption and a novel approach to design formal security reductions from the Syndrome Decoding problem.

San Ling, Khoa Nguyen, Huaxiong Wang et al.

Group signatures allow users of a group to sign messages anonymously in the name of the group, while incorporating a tracing mechanism to revoke anonymity and identify the signer of any message. Since its introduction by Chaum and van Heyst (EUROCRYPT 1991), numerous proposals have been put forward, yielding various improvements on security, efficiency and functionality. However, a drawback of traditional group signatures is that the opening authority is given too much power, i.e., he can indiscriminately revoke anonymity and there is no mechanism to keep him accountable. To overcome this problem, Kohlweiss and Miers (PoPET 2015) introduced the notion of accountable tracing signatures (ATS) - an enhanced group signature variant in which the opening authority is kept accountable for his actions. Kohlweiss and Miers demonstrated a generic construction of ATS and put forward a concrete instantiation based on number-theoretic assumptions. To the best of our knowledge, no other ATS scheme has been known, and the problem of instantiating ATS under post-quantum assumptions, e.g., lattices, remains open to date. In this work, we provide the first lattice-based accountable tracing signature scheme. The scheme satisfies the security requirements suggested by Kohlweiss and Miers, assuming the hardness of the Ring Short Integer Solution (RSIS) and the Ring Learning With Errors (RLWE) problems. At the heart of our construction are a lattice-based key-oblivious encryption scheme and a zero-knowledge argument system allowing to prove that a given ciphertext is a valid RLWE encryption under some hidden yet certified key. These technical building blocks may be of independent interest, e.g., they can be useful for the design of other lattice-based privacy-preserving protocols.

Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami et al.

Shamir's celebrated secret sharing scheme provides an efficient method for encoding a secret of arbitrary length $\ell$ among any $N \leq 2^\ell$ players such that for a threshold parameter $t$, (i) the knowledge of any $t$ shares does not reveal any information about the secret and, (ii) any choice of $t+1$ shares fully reveals the secret. It is known that any such threshold secret sharing scheme necessarily requires shares of length $\ell$, and in this sense Shamir's scheme is optimal. The more general notion of ramp schemes requires the reconstruction of secret from any $t+g$ shares, for a positive integer gap parameter $g$. Ramp secret sharing scheme necessarily requires shares of length $\ell/g$. Other than the bound related to secret length $\ell$, the share lengths of ramp schemes can not go below a quantity that depends only on the gap ratio $g/N$. In this work, we study secret sharing in the extremal case of bit-long shares and arbitrarily small gap ratio $g/N$, where standard ramp secret sharing becomes impossible. We show, however, that a slightly relaxed but equally effective notion of semantic security for the secret, and negligible reconstruction error probability, eliminate the impossibility. Moreover, we provide explicit constructions of such schemes. One of the consequences of our relaxation is that, unlike standard ramp schemes with perfect secrecy, adaptive and non-adaptive adversaries need different analysis and construction. For non-adaptive adversaries, we explicitly construct secret sharing schemes that provide secrecy against any $τ$ fraction of observed shares, and reconstruction from any $ρ$ fraction of shares, for any choices of $0 \leq τ< ρ\leq 1$. Our construction achieves secret length $N(ρ-τ-o(1))$, which we show to be optimal. For adaptive adversaries, we construct explicit schemes attaining a secret length $Ω(N(ρ-τ))$.

Khoa Nguyen, Benjamin Hong Meng Tan, Huaxiong Wang

Passwords are ubiquitous and most commonly used to authenticate users when logging into online services. Using high entropy passwords is critical to prevent unauthorized access and password policies emerged to enforce this requirement on passwords. However, with current methods of password storage, poor practices and server breaches have leaked many passwords to the public. To protect one's sensitive information in case of such events, passwords should be hidden from servers. Verifier-based password authenticated key exchange, proposed by Bellovin and Merrit (IEEE S\&P, 1992), allows authenticated secure channels to be established with a hash of a password (verifier). Unfortunately, this restricts password policies as passwords cannot be checked from their verifier. To address this issue, Kiefer and Manulis (ESORICS 2014) proposed zero-knowledge password policy check (ZKPPC). A ZKPPC protocol allows users to prove in zero knowledge that a hash of the user's password satisfies the password policy required by the server. Unfortunately, their proposal is not quantum resistant with the use of discrete logarithm-based cryptographic tools and there are currently no other viable alternatives. In this work, we construct the first post-quantum ZKPPC using lattice-based tools. To this end, we introduce a new randomised password hashing scheme for ASCII-based passwords and design an accompanying zero-knowledge protocol for policy compliance. Interestingly, our proposal does not follow the framework established by Kiefer and Manulis and offers an alternate construction without homomorphic commitments. Although our protocol is not ready to be used in practice, we think it is an important first step towards a quantum-resistant privacy-preserving password-based authentication and key exchange system.

San Ling, Khoa Nguyen, Huaxiong Wang et al.

In this work, we provide the first lattice-based group signature that offers full dynamicity (i.e., users have the flexibility in joining and leaving the group), and thus, resolve a prominent open problem posed by previous works. Moreover, we achieve this non-trivial feat in a relatively simple manner. Starting with Libert et al.'s fully static construction (Eurocrypt 2016) - which is arguably the most efficient lattice-based group signature to date, we introduce simple-but-insightful tweaks that allow to upgrade it directly into the fully dynamic setting. More startlingly, our scheme even produces slightly shorter signatures than the former, thanks to an adaptation of a technique proposed by Ling et al. (PKC 2013), allowing to prove inequalities in zero-knowledge. Our design approach consists of upgrading Libert et al.'s static construction (EUROCRYPT 2016) - which is arguably the most efficient lattice-based group signature to date - into the fully dynamic setting. Somewhat surprisingly, our scheme produces slightly shorter signatures than the former, thanks to a new technique for proving inequality in zero-knowledge without relying on any inequality check. The scheme satisfies the strong security requirements of Bootle et al.'s model (ACNS 2016), under the Short Integer Solution (SIS) and the Learning With Errors (LWE) assumptions. Furthermore, we demonstrate how to equip the obtained group signature scheme with the deniability functionality in a simple way. This attractive functionality, put forward by Ishida et al. (CANS 2016), enables the tracing authority to provide an evidence that a given user is not the owner of a signature in question. In the process, we design a zero-knowledge protocol for proving that a given LWE ciphertext does not decrypt to a particular message.

San Ling, Khoa Nguyen, Huaxiong Wang et al.

Group signature is a fundamental cryptographic primitive, aiming to protect anonymity and ensure accountability of users. It allows group members to anonymously sign messages on behalf of the whole group, while incorporating a tracing mechanism to identify the signer of any suspected signature. Most of the existing group signature schemes, however, do not guarantee security once secret keys are exposed. To reduce potential damages caused by key exposure attacks, Song (ACMCCS 2001) put forward the concept of forward-secure group signature (FSGS), which prevents attackers from forging group signatures pertaining to past time periods even if a secret group signing key is revealed at the current time period. For the time being, however, all known secure FSGS schemes are based on number-theoretic assumptions, and are vulnerable against quantum computers. In this work, we construct the first lattice-based FSGS scheme. Our scheme is proven secure under the Short Integer Solution and Learning With Errors assumptions. At the heart of our construction is a scalable lattice-based key evolving mechanism, allowing users to periodically update their secret keys and to efficiently prove in zero-knowledge that key evolution process is done correctly. To realize this essential building block, we first employ the Bonsai tree structure by Cash et al. (EUROCRYPT 2010) to handle the key evolution process, and then develop Langlois et al.'s construction (PKC 2014) to design its supporting zero-knowledge protocol.

San Ling, Khoa Nguyen, Huaxiong Wang et al.

Efficient user revocation is a necessary but challenging problem in many multi-user cryptosystems. Among known approaches, server-aided revocation yields a promising solution, because it allows to outsource the major workloads of system users to a computationally powerful third party, called the server, whose only requirement is to carry out the computations correctly. Such a revocation mechanism was considered in the settings of identity-based encryption and attribute-based encryption by Qin et al. (ESORICS 2015) and Cui et al. (ESORICS 2016), respectively. In this work, we consider the server-aided revocation mechanism in the more elaborate setting of predicate encryption (PE). The latter, introduced by Katz, Sahai, and Waters (EUROCRYPT 2008), provides fine-grained and role-based access to encrypted data and can be viewed as a generalization of identity-based and attribute-based encryption. Our contribution is two-fold. First, we formalize the model of server-aided revocable predicate encryption (SR-PE), with rigorous definitions and security notions. Our model can be seen as a non-trivial adaptation of Cui et al.'s work into the PE context. Second, we put forward a lattice-based instantiation of SR-PE. The scheme employs the PE scheme of Agrawal, Freeman and Vaikuntanathan (ASIACRYPT 2011) and the complete subtree method of Naor, Naor, and Lotspiech (CRYPTO 2001) as the two main ingredients, which work smoothly together thanks to a few additional techniques. Our scheme is proven secure in the standard model (in a selective manner), based on the hardness of the Learning With Errors (LWE) problem.

Fuchun Lin, Reihaneh Safavi-Naini, Mahdi Cheraghchi et al.

Non-malleable codes are randomized codes that protect coded messages against modification by functions in a tampering function class. These codes are motivated by providing tamper resilience in applications where a cryptographic secret is stored in a tamperable storage device and the protection goal is to ensure that the adversary cannot benefit from their tamperings with the device. In this paper we consider non-malleable codes for protection of secure communication against active physical layer adversaries. We define a class of functions that closely model tampering of communication by adversaries who can eavesdrop on a constant fraction of the transmitted codeword, and use this information to select a vector of tampering functions that will be applied to a second constant fraction of codeword components (possibly overlapping with the first set). We derive rate bounds for non-malleable codes for this function class and give two modular constructions. The first construction adapts and provides new analysis for an existing construction in the new setting. The second construction uses a new approach that results in an explicit construction of non-malleable codes. We show applications of our results in securing message communication against active physical layer adversaries in two settings: wiretap II with active adversaries and Secure Message Transmission (SMT) in networks. We discuss our results and directions for future work.

Jie Chen, Hoon Wei Lim, San Ling et al.

In Identity-Based Encryption (IBE) systems, key revocation is non-trivial. This is because a user's identity is itself a public key. Moreover, the private key corresponding to the identity needs to be obtained from a trusted key authority through an authenticated and secrecy protected channel. So far, there exist only a very small number of revocable IBE (RIBE) schemes that support non-interactive key revocation, in the sense that the user is not required to interact with the key authority or some kind of trusted hardware to renew her private key without changing her public key (or identity). These schemes are either proven to be only selectively secure or have public parameters which grow linearly in a given security parameter. In this paper, we present two constructions of non-interactive RIBE that satisfy all the following three attractive properties: (i) proven to be adaptively secure under the Symmetric External Diffie-Hellman (SXDH) and the Decisional Linear (DLIN) assumptions; (ii) have constant-size public parameters; and (iii) preserve the anonymity of ciphertexts---a property that has not yet been achieved in all the current schemes.

Yeow Meng Chee, Huaxiong Wang, Liang Feng Zhang

Extended private information retrieval (EPIR) was defined by \cite{BCPT07} at CANS'07 and generalized by \cite{BC09} at AFRICACRYPT'09. In the generalized setting, EPIR allows a user to evaluate a function on a database block such that the database can learn neither which function has been evaluated nor on which block the function has been evaluated and the user learns no more information on the database blocks except for the expected result. An EPIR protocol for evaluating polynomials over a finite field $L$ was proposed by Bringer and Chabanne in \cite{BC09}. We show that the protocol does not satisfy the correctness requirement as they have claimed. In particular, we show that it does not give the user the expected result with large probability if one of the coefficients of the polynomial to be evaluated is primitive in $L$ and the others belong to the prime subfield of $L$.