Cuproof: Range Proof with Constant Size

Zero-Knowledge Proof is widely used in blockchains. For example, zk-SNARK is used in Zcash as its core technology to identifying transactions without the exposure of the actual transaction values. Up to now, various range proofs have been proposed, and their efficiency and range-flexibility have also been improved. Bootle et al. used the inner product method and recursion to construct an efficient Zero-Knowledge Proof in 2016. Later, Benediky Bünz et al. proposed an efficient range proof scheme called Bulletproofs, which can convince the verifier that a secret number lies in [0,2κ−1] with κ being a positive integer. By combining the inner-product and Lagrange’s four-square theorem, we propose a range proof scheme called Cuproof. Our Cuproof can make a range proof to show that a secret number v lies in an interval [a,b] with no exposure of the real value v or other extra information leakage about v. It is a good and practical method to protect privacy and information security. In Bulletproofs, the communication cost is 6+2logκ, while in our Cuproof, all the communication cost, the proving time and the verification time are of constant sizes.     

Simple Majority Consensus in Networks with Unreliable Communication

In this work, we analyze the performance of a simple majority-rule protocol solving a fundamental coordination problem in distributed systems—binary majority consensus—in the presence of probabilistic message loss. Using probabilistic analysis for a large-scale, fully-connected, network of 2n agents, we prove that the Simple Majority Protocol (SMP) reaches consensus in only three communication rounds, with probability approaching 1 as n grows to infinity. Moreover, if the difference between the numbers of agents that hold different opinions grows at a rate of n, then the SMP with only two communication rounds attains consensus on the majority opinion of the network, and if this difference grows faster than n, then the SMP reaches consensus on the majority opinion of the network in a single round, with probability converging to 1 as exponentially fast as n→∞. We also provide some converse results, showing that these requirements are not only sufficient, but also necessary.     

Quantum Linear System Algorithm for General Matrices in System Identification

Solving linear systems of equations is one of the most common and basic problems in classical identification systems. Given a coefficient matrix A and a vector b, the ultimate task is to find the solution x such that Ax=b. Based on the technique of the singular value estimation, the paper proposes a modified quantum scheme to obtain the quantum state |x〉 corresponding to the solution of the linear system of equations in O(κ2rpolylog(mn)/ϵ) time for a general m×n dimensional A, which is superior to existing quantum algorithms, where κ is the condition number, r is the rank of matrix A and ϵ is the precision parameter. Meanwhile, we also design a quantum circuit for the homogeneous linear equations and achieve an exponential improvement. The coefficient matrix A in our scheme is a sparsity-independent and non-square matrix, which can be applied in more general situations. Our research provides a universal quantum linear system solver and can enrich the research scope of quantum computation.     

The κ-Deformed Calogero–Leyvraz Lagrangians and Applications to Integrable Dynamical Systems

The Calogero–Leyvraz Lagrangian framework, associated with the dynamics of a charged particle moving in a plane under the combined influence of a magnetic field as well as a frictional force, proposed by Calogero and Leyvraz, has some special features. It is endowed with a Shannon “entropic” type kinetic energy term. In this paper, we carry out the constructions of the 2D Lotka–Volterra replicator equations and the N=2 Relativistic Toda lattice systems using this class of Lagrangians. We take advantage of the special structure of the kinetic term and deform the kinetic energy term of the Calogero–Leyvraz Lagrangians using the κ-deformed logarithm as proposed by Kaniadakis and Tsallis. This method yields the new construction of the κ-deformed Lotka–Volterra replicator and relativistic Toda lattice equations.     

New Bounds and a Generalization for Share Conversion for 3-Server PIR

Private Information Retrieval (PIR) protocols, which allow the client to obtain data from servers without revealing its request, have many applications such as anonymous communication, media streaming, blockchain security, advertisement, etc. Multi-server PIR protocols, where the database is replicated among the non-colluding servers, provide high efficiency in the information-theoretic setting. Beimel et al. in CCC 12’ (further referred to as BIKO) put forward a paradigm for constructing multi-server PIR, capturing several previous constructions for k≥3 servers, as well as improving the best-known share complexity for 3-server PIR. A key component there is a share conversion scheme from corresponding linear three-party secret sharing schemes with respect to a certain type of “modified universal” relation. In a useful particular instantiation of the paradigm, they used a share conversion from (2,3)-CNF over Zm to three-additive sharing over Zpβ for primes p1,p2,p where p1≠p2 and m=p1·p2, and the relation is modified universal relation CSm. They reduced the question of the existence of the share conversion for a triple (p1,p2,p) to the (in)solvability of a certain linear system over Zp, and provided an efficient (in m,logp) construction of such a sharing scheme. Unfortunately, the size of the system is Θ(m2) which entails the infeasibility of a direct solution for big m’s in practice. Paskin-Cherniavsky and Schmerler in 2019 proved the existence of the conversion for the case of odd p1, p2 when p=p1, obtaining in this way infinitely many parameters for which the conversion exists, but also for infinitely many of them it remained open. In this work, using some algebraic techniques from the work of Paskin-Cherniavsky and Schmerler, we prove the existence of the conversion for even m’s in case p=2 (we computed β in this case) and the absence of the conversion for even m’s in case p>2. This does not improve the concrete efficiency of 3-server PIR; however, our result is promising in a broader context of constructing PIR through composition techniques with k≥3 servers, using the relation CSm where m has more than two prime divisors. Another our suggestion about 3-server PIR is that it’s possible to achieve a shorter server’s response using the relation CSm′ for extended Sm′⊃Sm. By computer search, in BIKO framework we found several such sets for small m’s which result in share conversion from (2,3)-CNF over Zm to 3-additive secret sharing over Zpβ′, where β′>0 is several times less than β, which implies several times shorter server’s response. We also suggest that such extended sets Sm′ can result in better PIR due to the potential existence of matching vector families with the higher Vapnik-Chervonenkis dimension.     

Hypercontractive Inequalities for the Second Norm of Highly Concentrated Functions,and Mrs. Gerber’s-Type Inequalities for the Second Rényi Entropy

Let Tϵ, 0≤ϵ≤1/2, be the noise operator acting on functions on the boolean cube {0,1}n. Let f be a distribution on {0,1}n and let q>1. We prove tight Mrs. Gerber-type results for the second Rényi entropy of Tϵf which take into account the value of the qth Rényi entropy of f. For a general function f on {0,1}n we prove tight hypercontractive inequalities for the ℓ2 norm of Tϵf which take into account the ratio between ℓq and ℓ1 norms of f.     

On the Achievable Rate Region of the K-Receiver Broadcast Channels via Exhaustive Message Splitting

This paper focuses on K-receiver discrete-time memoryless broadcast channels (DM-BCs) with private messages, where the transmitter wishes to convey K private messages to K receivers. A general inner bound on the capacity region is proposed based on an exhaustive message splitting and a K-level modified Marton’s coding. The key idea is to split every message into submessages each corresponding to a set of users who are assigned to recover them, and then send these submessages via codewords chosen from a K-level structure codebooks. To guarantee the joint typicality among all transmitted codewords, a sufficient condition on the subcodebooks’ sizes is derived through a newly establishing hierarchical covering lemma, which extends the 2-level multivariate covering lemma to the K-level case with more intricate dependences. As the number of auxiliary random variables and rate conditions both increase exponentially with K, the standard Fourier–Motzkin elimination procedure becomes infeasible when K is large. To tackle this problem, we obtain a closed form of achievable rate region with a special observation of disjoint unions of sets that constitute the power set of {1,⋯,K}. The proposed achievable rate region allows arbitrary input probability mass functions and improves over previously known achievable (closed form) rate regions for K-receiver (K≥3) BCs.     

Contrarian Voter Model under the Influence of an Oscillating Propaganda: Consensus,Bimodal Behavior and Stochastic Resonance

We study the contrarian voter model for opinion formation in a society under the influence of an external oscillating propaganda and stochastic noise. Each agent of the population can hold one of two possible opinions on a given issue—against or in favor—and interacts with its neighbors following either an imitation dynamics (voter behavior) or an anti-alignment dynamics (contrarian behavior): each agent adopts the opinion of a random neighbor with a time-dependent probability p(t), or takes the opposite opinion with probability 1−p(t). The imitation probability p(t) is controlled by the social temperature T, and varies in time according to a periodic field that mimics the influence of an external propaganda, so that a voter is more prone to adopt an opinion aligned with the field. We simulate the model in complete graph and in lattices, and find that the system exhibits a rich variety of behaviors as T is varied: opinion consensus for T=0, a bimodal behavior for T<Tc, an oscillatory behavior where the mean opinion oscillates in time with the field for T>Tc, and full disorder for T≫1. The transition temperature Tc vanishes with the population size N as Tc≃2/lnN in complete graph. In addition, the distribution of residence times tr in the bimodal phase decays approximately as tr−3/2. Within the oscillatory regime, we find a stochastic resonance-like phenomenon at a given temperature T*. Furthermore, mean-field analytical results show that the opinion oscillations reach a maximum amplitude at an intermediate temperature, and that exhibit a lag with respect to the field that decreases with T.     

Construction of a Family of Maximally Entangled Bases in ℂd ⊗ ℂd′

In this paper, we present a new method for the construction of maximally entangled states in Cd⊗Cd′ when d′≥2d. A systematic way of constructing a set of maximally entangled bases (MEBs) in Cd⊗Cd′ was established. Both cases when d′ is divisible by d and not divisible by d are discussed. We give two examples of maximally entangled bases in C2⊗C4, which are mutually unbiased bases. Finally, we found a new example of an unextendible maximally entangled basis (UMEB) in C2⊗C5.     

A Review of the System-Intrinsic Nonequilibrium Thermodynamics in Extended Space (MNEQT) with Applications

The review deals with a novel approach (MNEQT) to nonequilibrium thermodynamics (NEQT) that is based on the concept of internal equilibrium (IEQ) in an enlarged state space SZ involving internal variables as additional state variables. The IEQ macrostates are unique in SZ and have no memory just as EQ macrostates are in the EQ state space SX⊂SZ. The approach provides a clear strategy to identify the internal variables for any model through several examples. The MNEQT deals directly with system-intrinsic quantities, which are very useful as they fully describe irreversibility. Because of this, MNEQT solves a long-standing problem in NEQT of identifying a unique global temperature T of a system, thus fulfilling Planck’s dream of a global temperature for any system, even if it is not uniform such as when it is driven between two heat baths; T has the conventional interpretation of satisfying the Clausius statement that the exchange macroheatdeQflows from hot to cold, and other sensible criteria expected of a temperature. The concept of the generalized macroheat dQ=deQ+diQ converts the Clausius inequality dS≥deQ/T0 for a system in a medium at temperature T0 into the Clausius equalitydS≡dQ/T, which also covers macrostates with memory, and follows from the extensivity property. The equality also holds for a NEQ isolated system. The novel approach is extremely useful as it also works when no internal state variables are used to study nonunique macrostates in the EQ state space SX at the expense of explicit time dependence in the entropy that gives rise to memory effects. To show the usefulness of the novel approach, we give several examples such as irreversible Carnot cycle, friction and Brownian motion, the free expansion, etc.     

Dirichlet Polynomials and Entropy

A Dirichlet polynomial d in one variable y is a function of the form d(y)=anny+⋯+a22y+a11y+a00y for some n,a0,…,an∈N. We will show how to think of a Dirichlet polynomial as a set-theoretic bundle, and thus as an empirical distribution. We can then consider the Shannon entropy H(d) of the corresponding probability distribution, and we define its length (or, classically, its perplexity) by L(d)=2H(d). On the other hand, we will define a rig homomorphism h:Dir→Rect from the rig of Dirichlet polynomials to the so-called rectangle rig, whose underlying set is R⩾0×R⩾0 and whose additive structure involves the weighted geometric mean; we write h(d)=(A(d),W(d)), and call the two components area and width (respectively). The main result of this paper is the following: the rectangle-area formula A(d)=L(d)W(d) holds for any Dirichlet polynomial d. In other words, the entropy of an empirical distribution can be calculated entirely in terms of the homomorphism h applied to its corresponding Dirichlet polynomial. We also show that similar results hold for the cross entropy.     

Robust Aggregation for Federated Learning by Minimum γ-Divergence Estimation

Federated learning is a framework for multiple devices or institutions, called local clients, to collaboratively train a global model without sharing their data. For federated learning with a central server, an aggregation algorithm integrates model information sent from local clients to update the parameters for a global model. Sample mean is the simplest and most commonly used aggregation method. However, it is not robust for data with outliers or under the Byzantine problem, where Byzantine clients send malicious messages to interfere with the learning process. Some robust aggregation methods were introduced in literature including marginal median, geometric median and trimmed-mean. In this article, we propose an alternative robust aggregation method, named γ-mean, which is the minimum divergence estimation based on a robust density power divergence. This γ-mean aggregation mitigates the influence of Byzantine clients by assigning fewer weights. This weighting scheme is data-driven and controlled by the γ value. Robustness from the viewpoint of the influence function is discussed and some numerical results are presented.     

Estimating Drift Parameters in a Sub-Fractional Vasicek-Type Process

This study deals with drift parameters estimation problems in the sub-fractional Vasicek process given by dxt=θ(μ−xt)dt+dStH, with θ>0, μ∈R being unknown and t≥0; here, SH represents a sub-fractional Brownian motion (sfBm). We introduce new estimators θ^ for θ and μ^ for μ based on discrete time observations and use techniques from Nordin–Peccati analysis. For the proposed estimators θ^ and μ^, strong consistency and the asymptotic normality were established by employing the properties of SH. Moreover, we provide numerical simulations for sfBm and related Vasicek-type process with different values of the Hurst index H.     

Controversial Variable Node Selection-Based Adaptive Belief Propagation Decoding Algorithm Using Bit Flipping Check for JSCC Systems

An end-to-end joint source–channel (JSC) encoding matrix and a JSC decoding scheme using the proposed bit flipping check (BFC) algorithm and controversial variable node selection-based adaptive belief propagation (CVNS-ABP) decoding algorithm are presented to improve the efficiency and reliability of the joint source–channel coding (JSCC) scheme based on double Reed–Solomon (RS) codes. The constructed coding matrix can realize source compression and channel coding of multiple sets of information data simultaneously, which significantly improves the coding efficiency. The proposed BFC algorithm uses channel soft information to select and flip the unreliable bits and then uses the redundancy of the source block to realize the error verification and error correction. The proposed CVNS-ABP algorithm reduces the influence of error bits on decoding by selecting error variable nodes (VNs) from controversial VNs and adding them to the sparsity of the parity-check matrix. In addition, the proposed JSC decoding scheme based on the BFC algorithm and CVNS-ABP algorithm can realize the connection of source and channel to improve the performance of JSC decoding. Simulation results show that the proposed BFC-based hard-decision decoding (BFC-HDD) algorithm (ζ = 1) and BFC-based low-complexity chase (BFC-LCC) algorithm (ζ = 1, η = 3) can achieve about 0.23 dB and 0.46 dB of signal-to-noise ratio (SNR) defined gain over the prior-art decoding algorithm at a frame error rate (FER) = 10−1. Compared with the ABP algorithm, the proposed CVNS-ABP algorithm and BFC-CVNS-ABP algorithm achieve performance gains of 0.18 dB and 0.23 dB, respectively, at FER = 10−3.     

A Super Fast Algorithm for Estimating Sample Entropy

Sample entropy, an approximation of the Kolmogorov entropy, was proposed to characterize complexity of a time series, which is essentially defined as −log(B/A), where B denotes the number of matched template pairs with length m and A denotes the number of matched template pairs with m+1, for a predetermined positive integer m. It has been widely used to analyze physiological signals. As computing sample entropy is time consuming, the box-assisted, bucket-assisted, x-sort, assisted sliding box, and kd-tree-based algorithms were proposed to accelerate its computation. These algorithms require O(N2) or O(N2−1m+1) computational complexity, where N is the length of the time series analyzed. When N is big, the computational costs of these algorithms are large. We propose a super fast algorithm to estimate sample entropy based on Monte Carlo, with computational costs independent of N (the length of the time series) and the estimation converging to the exact sample entropy as the number of repeating experiments becomes large. The convergence rate of the algorithm is also established. Numerical experiments are performed for electrocardiogram time series, electroencephalogram time series, cardiac inter-beat time series, mechanical vibration signals (MVS), meteorological data (MD), and 1/f noise. Numerical results show that the proposed algorithm can gain 100–1000 times speedup compared to the kd-tree and assisted sliding box algorithms while providing satisfactory approximate accuracy.     

An Enhanced Belief Propagation Flipping Decoder for Polar Codes with Stepping Strategy

The Belief Propagation (BP) algorithm has the advantages of high-speed decoding and low latency. To improve the block error rate (BLER) performance of the BP-based algorithm, the BP flipping algorithm was proposed. However, the BP flipping algorithm attempts numerous useless flippings for improving the BLER performance. To reduce the number of decoding attempts needed without any loss of BLER performance, in this paper a metric is presented to evaluate the likelihood that the bits would correct the BP flipping decoding. Based on this, a BP-Step-Flipping (BPSF) algorithm is proposed which only traces the unreliable bits in the flip set (FS) to flip and skips over the reliable ones. In addition, a threshold β is applied when the magnitude of the log–likelihood ratio (LLR) is small, and an enhanced BPSF (EBPSF) algorithm is presented to lower the BLER. With the same FS, the proposed algorithm can reduce the average number of iterations efficiently. Numerical results show the average number of iterations for EBPSF-1 decreases by 77.5% when N = 256, compared with the BP bit-flip-1 (BPF-1) algorithm at Eb/N0 = 1.5 dB.     

Quantum Walk on the Generalized Birkhoff Polytope Graph

We study discrete-time quantum walks on generalized Birkhoff polytope graphs (GBPGs), which arise in the solution-set to certain transportation linear programming problems (TLPs). It is known that quantum walks mix at most quadratically faster than random walks on cycles, two-dimensional lattices, hypercubes, and bounded-degree graphs. In contrast, our numerical results show that it is possible to achieve a greater than quadratic quantum speedup for the mixing time on a subclass of GBPG (TLP with two consumers and m suppliers). We analyze two types of initial states. If the walker starts on a single node, the quantum mixing time does not depend on m, even though the graph diameter increases with it. To the best of our knowledge, this is the first example of its kind. If the walker is initially spread over a maximal clique, the quantum mixing time is O(m/ϵ), where ϵ is the threshold used in the mixing times. This result is better than the classical mixing time, which is O(m1.5/ϵ).