Haifeng Yu

Jian Ding, Cheng Wang, Haifeng Yu et al.

Disjunctive Hierarchical Secret Sharing (DHSS) scheme is a secret sharing scheme in which the set of all participants is partitioned into disjoint subsets. Each disjoint subset is said to be a level, and different levels have different degrees of trust and different thresholds. If the number of cooperating participants from a given level falls to meet its threshold, the shortfall can be compensated by participants from higher levels. Many ideal DHSS schemes have been proposed, but they often suffer from big share sizes. Conversely, existing non-ideal DHSS schemes achieve small share sizes, yet they fail to be both secure and asymptotically ideal simultaneously. In this work, we present an explicit construct of an asymptotically ideal DHSS scheme by using a polynomial, multiple linear homogeneous recurrence relations and one-way functions. Although our scheme has computational security and many public values, it has a small share size and the dealer is required polynomial time.

Jian Ding, Cheng Wang, Hongju Li et al.

In Shamir's secret sharing scheme, all participants possess equal privileges. However, in many practical scenarios, it is often necessary to assign different levels of authority to different participants. To address this requirement, Hierarchical Secret Sharing (HSS) schemes were developed, which partitioned all participants into multiple subsets and assigned a distinct privilege level to each. Existing Chinese Remainder Theorem (CRT)-based HSS schemes benefit from flexible share sizes, but either exhibit security flaws or have an information rate less than $\frac{1}{2}$. In this work, we propose a disjunctive HSS scheme and a conjunctive HSS scheme by using the CRT for integer ring and one-way functions. Both schemes are asymptotically ideal and are proven to be secure.

Jian Ding, Cheng Wang, Hongju Li et al.

Conjunctive Hierarchical Secret Sharing (CHSS) is a type of secret sharing that divides participants into multiple distinct hierarchical levels, with each level having a specific threshold. An authorized subset must simultaneously meet the threshold of all levels. Existing Chinese Remainder Theorem (CRT)-based CHSS schemes either have security vulnerabilities or have an information rate lower than $\frac{1}{2}$. In this work, we utilize the CRT for polynomial ring and one-way functions to construct an asymptotically perfect CHSS scheme. It has computational security, and permits flexible share sizes. Notably, when all shares are of equal size, our scheme is an asymptotically ideal CHSS scheme with an information rate one.

Da Zhang, Xin Li, Yibin Guo et al.

The rapid development of machine learning and quantum computing has placed quantum machine learning at the forefront of research. However, existing quantum machine learning algorithms based on quantum variational algorithms face challenges in trainability and noise robustness. In order to address these challenges, we introduce a gradient-free, noise-robust quantum reservoir computing algorithm that harnesses discrete time crystal dynamics as a reservoir. We first calibrate the memory, nonlinear, and information scrambling capacities of the quantum reservoir, revealing their correlation with dynamical phases and non-equilibrium phase transitions. We then apply the algorithm to the binary classification task and establish a comparative quantum kernel advantage. For ten-class classification, both noisy simulations and experimental results on superconducting quantum processors match ideal simulations, demonstrating the enhanced accuracy with increasing system size and confirming the topological noise robustness. Our work presents the first experimental demonstration of quantum reservoir computing for image classification based on digital quantum simulation. It establishes the correlation between quantum many-body non-equilibrium phase transitions and quantum machine learning performance, providing new design principles for quantum reservoir computing and broader quantum machine learning algorithms in the NISQ era.

Z. T. Wang, Qiuhao Chen, Yuxuan Du et al.

To effectively implement quantum algorithms on noisy intermediate-scale quantum (NISQ) processors is a central task in modern quantum technology. NISQ processors feature tens to a few hundreds of noisy qubits with limited coherence times and gate operations with errors, so NISQ algorithms naturally require employing circuits of short lengths via quantum compilation. Here, we develop a reinforcement learning (RL)-based quantum compiler for a superconducting processor and demonstrate its capability of discovering novel and hardware-amenable circuits with short lengths. We show that for the three-qubit quantum Fourier transformation, a compiled circuit using only seven CZ gates with unity circuit fidelity can be achieved. The compiler is also able to find optimal circuits under device topological constraints, with lengths considerably shorter than those by the conventional method. Our study exemplifies the codesign of the software with hardware for efficient quantum compilation, offering valuable insights for the advancement of RL-based compilers.

Ruomu Hou, Haifeng Yu, Prateek Saxena

Fault tolerance of a blockchain is often characterized by the fraction $f$ of "adversarial power" that it can tolerate in the system. Despite the fast progress in blockchain designs in recent years, existing blockchain systems can still only tolerate $f$ below $0.5$. Can practically usable blockchains tolerate a malicious majority, i.e., $f$ above $0.5$? This work presents a positive answer to this question. We first note that the well-known impossibility of {\em byzantine consensus} for $f$ above $0.5$ does not carry over to blockchains. To tolerate $f$ above $0.5$, we use {\em byzantine broadcast}, instead of byzantine consensus, as the core of the blockchain. A major obstacle in doing so, however, is that the resulting blockchain may have extremely low throughput. To overcome this central technical challenge, we propose a novel byzantine broadcast protocol OverlayBB, that can tolerate $f$ above $0.5$ while achieving good throughput. Using OverlayBB as the core, we present the design, implementation, and evaluation of a novel Proof-of-Stake blockchain called BCube. BCube can tolerate a malicious majority, while achieving practically usable transaction throughput and confirmation latency in our experiments with $10000$ nodes and under $f = 0.7$. To our knowledge, BCube is the first blockchain that can achieve such properties.

Seth Gilbert, Xiao Liu, Haifeng Yu

In collaborative recommendation systems, privacy may be compromised, as users' opinions are used to generate recommendations for others. In this paper, we consider an online collaborative recommendation system, and we measure users' privacy in terms of the standard differential privacy. We give the first quantitative analysis of the trade-offs between recommendation quality and users' privacy in such a system by showing a lower bound on the best achievable privacy for any non-trivial algorithm, and proposing a near-optimal algorithm. From our results, we find that there is actually little trade-off between recommendation quality and privacy for any non-trivial algorithm. Our results also identify the key parameters that determine the best achievable privacy.