A proof of reserves (PoR) protocol enables a cryptocurrency exchange to prove to its users that it owns a certain amount of coins, as a first step towards proving that it is solvent. We present the design, implementation, and security analysis of MProve-Nova, a PoR protocol for Monero that leverages the Nova recursive SNARK to achieve two firsts (without requiring any trusted setup). It is the first Monero PoR protocol that reveals only the number of outputs owned by an exchange; no other information about the outputs or their key images is revealed. It is also the first Monero PoR protocol where the proof size and proof verification time are constant, i.e. they are independent of the number of outputs on the Monero blockchain and the number of outputs owned by the exchange. To achieve constant verification times, MProve-Nova requires a preprocessing step which creates two Merkle trees from all the outputs and key images on the Monero blockchain. MProve-Nova consists of two Nova-based subprotocols, a reserves commitment generator (RCG) protocol used to compute a commitment to the total reserves owned by an exchange and a non-collusion (NC) protocol used to prove non-collusion between two exchanges. For the RCG protocol, we observed proof sizes of about 28 KB and verification times of 4.3 seconds. For the NC protocol, we observed proof sizes of about 24 KB and verification times of 0.2 seconds. Proving times for both protocols increase linearly with the number of outputs owned by the exchange but remain independent of the number of outputs on the Monero blockchain. On average, the RCG protocol required about 42 minutes per 1000 outputs and the NC protocol required about 5 minutes per 1000 outputs.

CryptoNote blockchains like Monero represent the largest public deployments of linkable ring signatures. Beginning with the work of Kumar et al. (ESORICS 2017) and Möser et al. (PoPETs 2018), several techniques have been proposed to trace CryptoNote transactions, i.e. identify the actual signing key, by using the transaction history. Yu et al. (FC 2019) introduced the closed set attack for undeniable traceability and proved that it is optimal by showing that it has the same performance as the brute-force attack. However, they could only implement an approximation of the closed set attack due to its exponential time complexity. In this paper, we show that the Dulmage-Mendelsohn (DM) decomposition of bipartite graphs gives a polynomial-time implementation of the closed set attack. Our contribution includes open source implementations of the DM decomposition and the clustering algorithm (the approximation to the closed set attack proposed by Yu et al). Using these implementations, we evaluate the empirical performance of these methods on the Monero dataset in two ways - firstly using data only from the main Monero chain and secondly using data from four hard forks of Monero in addition to the main Monero chain. We have released the scripts used to perform the empirical analysis along with step-by-step instructions.

Proof of reserves protocols enable cryptocurrency exchanges to prove solvency, i.e. prove that they have enough reserves to meet their liabilities towards their customers. MProve (EuroS&PW, 2019) was the first proof of reserves protocol for Monero which provided some privacy to the exchanges' addresses. As the key images and the addresses are inherently linked in the MProve proof, an observer could easily recognize the exchange-owned address when a transaction spending from it appears on the blockchain. This is detrimental for an exchange's privacy and becomes a natural reason for exchanges to not adopt MProve. To this end, we propose MProve+, a Bulletproofs-based (S&P, 2018) NIZK protocol, which unlinks the key images and the addresses, thus alleviating the drawback of MProve. Furthermore, MProve+ presents a promising alternative to MProve due to an order of magnitude smaller proof sizes along with practical proof generation and verification times.

The problem of identifying the channel code from a received sequence of noise-affected codewords is known as the blind reconstruction of channel codes. Blind reconstruction of channel codes is an important problem in military surveillance applications to identify the channel code used by an adversary. In this paper, we consider the problem of the blind reconstruction of the binary cyclic codes of unknown length from an unsynchronized bitstream (i.e., when the location of codeword boundaries is not known). For the blind reconstruction of cyclic codes, it is sufficient to identify the correct synchronization, the length, and the factors of the generator polynomial of the code. Toward this, we study the distribution of the syndromes (remainders) of the received polynomials with respect to a candidate factor of the generator polynomial. We prove that the probability of zero syndrome is maximum when all the parameters are correct. Using this result, the problem of the blind reconstruction of cyclic codes is formulated and solved as a hypothesis testing problem.

We propose a method to identify an unknown linear block code using Groebner bases. It is inspired by a solution to the problem of learning parities with structured noise. The proposed method performs better than existing solutions when the number of observations is small.

Channel codebook detection is of interest in cognitive paradigm or security applications. A binary hypothesis testing problem is considered, where a receiver has to detect the channel-code from two possible choices upon observing noise-affected codewords through a communication channel. For analytical tractability, it is assumed that the two channel-codes are linear block codes with identical block-length. In a first, this work studies the likelihood ratio test for minimizing the error probability in this detection problem. In an asymptotic setting, where a large number of noise-affected codewords are available for detection, the Chernoff information characterizes the error probability. A lower bound on the Chernoff information, based on the parameters of the two hypothesis, is established. Further, it is shown that if likelihood based efficient (generalized distributive law or BCJR) bit-decoding algorithms are available for the two codes, then the likelihood ratio test for the code-detection problem can be performed in a computationally feasible manner.

In this paper, we consider the problem of distinguishing the noisy codewords of a known binary linear block code from a random bit sequence. We propose to use the generalized likelihood ratio test (GLRT) to solve this problem. We also give a formula to find approximate number of codewords required and compare our results with an existing method.

In this paper, we investigate the timing acquisition problem for transmitted reference (TR) ultra-wideband systems employing direct-sequence (DS) spreading. We show that a two-level DS signaling helps in achieving good acquisition performance. We propose a two-stage acquisition scheme which exploits the TR signal structure to achieve a significant improvement in the mean detection time performance when compared with a conventional single-stage acquisition scheme.

The acquisition of ultra-wideband (UWB) signals is a potential bottleneck for system throughput in a packet-based network employing UWB signaling format in the physical layer. The problem is mainly due to the low received signal power and the fine time resolution which forces the acquisition system to process the signal over long periods of time before getting a reliable estimate of the timing of the signal. Hence, there is a need to develop more efficient acquisition schemes by taking into account the signal and channel characteristics. In this paper, we investigate two approaches, the square-and-integrate and the integrate-and-square, which collect the energy in the multipaths by performing equal-gain combining (EGC) to improve the acquisition performance. We define the hit set as the set of hypothesized phases which can guarantee adequate system performance after acquisition, and also study the effect of the EGC window length on the acquisition performance.

The usage of long spreading sequences and the fine timing resolution result in a large search space during acquisition in ultra-wideband (UWB) systems. This paper presents a two-stage signal acquisition scheme for UWB systems employing a hybrid signaling format involving direct sequence (DS) spreading and time hopping (TH), which significantly reduces the search space. The resulting acquisition system consists of two stages, one each for the acquisition of the TH and DS sequences. The dense multipath channel typical of UWB systems implies that there can exist more than one phase to which the receiver can lock on and achieve satisfactory demodulation performance subsequent to acquisition. We define the set of such phases as the hit set. The hybrid signaling format coupled with the multi-phase hit set help significantly improve the acquisition performance of the UWB system. The performance of the proposed acquisition system, measured in terms of the mean detection time, is evaluated analytically and supported by computer simulation

The ultra-wideband (UWB) channel is characterized by the presence of dense multipath and robustness to multipath fading. By taking system performance subsequent to acquisition into account, it was shown recently that there are multiple phases (called the hit set) where a receiver lock can be considered as successful acquisition. In this case, the serial search may no longer be the optimal choice for the sequential search strategy in the acquisition system. In this letter, we consider the problem of finding better search strategies in the set of all search strategies which are permutations of the search space. The large size of the search space and the absence of any exploitable structure make the problem of finding the permutation search strategy which minimizes the mean detection time prohibitively complex. However, if we take the first-order approximation that the probabilities of detection of all the hit-set phases are equal, then there exists a permutation search strategy which minimizes the mean detection time. Since the actual probabilities of detection are not equal, this search strategy, although not optimal, serves as a useful heuristic solution to an otherwise intractable problem. Furthermore, we see that this search strategy has a simple Jump-by-H structure, and improves the mean detection time by a significant amount compared with the serial search.

The asymptotic performance of timing acquisition systems having fixed dwell time in multipath fading channels is investigated. The detrimental effect of the multipath channel fading on the acquisition performance is isolated by considering the asymptotic performance as the average signal-to-noise ratio (SNR) increases. It is found that for any threshold such that the average probability of false alarm is less than a given tolerance, the channel fading results in a lower bound on the asymptotic average probability of miss which is nontrivial for a variety of fading scenarios. A threshold-based direct-sequence spread-spectrum signal acquisition system is considered and it is found that the detrimental effect of channel fading on asymptotic acquisition performance, albeit nontrivial, is not very significant. The asymptotic acquisition performance of two threshold-based acquisition schemes for ultra-wideband (UWB) signals with time-hopping (TH) spreading are also evaluated and compared. For both schemes, the detrimental effect of the channel fading on the asymptotic acquisition performance turns out to be significant.

The problem of estimating the location and time of origin of an instantaneous source of a particular gas using a simple sensor network is investigated in this paper. Here, the gas spreads by diffusion and the sensors make a binary decision on the existence of the gas by measuring its concentration in their immediate vicinity. The inability of the sensors to go beyond a binary resolution of the concentration justifies their classification as dumb. In this paper, it is restricted to the one-dimensional case where the sensors form a linear array. The analysis of the Cramer-Rao bound (CRB) to study the limits of estimation performance is numerically calculated. Based on the number of gas molecules the Poisson distribution by a Gaussian distribution with mean and variance is approximated.

In this paper, we investigate the asymptotic performance of threshold-based timing acquisition systems having fixed dwell time in multipath fading channels. We show that if the system involves the comparison of a decision statistic to a threshold in order to detect the true symbol timing, then it may not be possible to make the average probability of error in acquisition arbitrarily small, even if the signal-to-noise ratio increases without bound.

Low transmission power and a highly spread bandwidth makes the acquisition of ultra-wideband (UWB) signals a difficult problem. In a packet-based network employing UWB modulation in the physical layer, long preambles need to be prepended to each packet because the low signal power requires the receiver to process the signal for long periods of time in order to estimate the timing of the signal. The long spreading or hopping sequences used in UWB systems result in a large search space for the acquisition system at the receiver. This work presents a signal acquisition system for UWB which employs a hybrid signaling format involving direct sequence (DS) spreading and time hopping (TH), significantly reducing the search space in the UWB acquisition system. The acquisition system employs equal gain combining (EGC) which enables the utilization of the energy of the dense multipath, typical of a UWB channel. The performance of the acquisition system has been analytically evaluated and is corroborated through simulation.