Several cryptographic primitives, especially succinct proofs of various forms, transform the satisfaction of high-level properties to the existence of a polynomial quotient between a polynomial that interpolates a set of values with a cleverly arranged divisor. Some examples are SNARKs, like Groth16, and polynomial commitments, such as KZG. Such a polynomial division naively takes O (n log n) time with Fast Fourier Transforms, and is usually the asymptotic bottleneck for these computations.

Zero-knowledge range proofs (ZKRPs) allow a prover to convince a verifier that a secret value lies in a given interval. ZKRPs have numerous applications: from anonymous credentials and auctions, to confidential transactions in cryptocurrencies. At the same time, a plethora of ZKRP constructions exist in the literature, each with its own trade-offs. In this work, we systematize the knowledge around ZKRPs. We create a classification of existing constructions based on the underlying building techniques, and we summarize their properties. We provide comparisons between schemes both in terms of properties as well as efficiency levels, and construct a guideline to assist in the selection of an appropriate ZKRP for different application requirements. Finally, we discuss a number of interesting open research problems.

status: Published

Traditional blockchains execute transactions through the use of consensus mechanisms that guarantee reasonable expectations of integrity and finality. However, often these incur costs making the throughput of transactions orders of magnitude slower than their web2 counterparts. To address this drawback, so called L2 layers offload transactions from the main chain, called L1, execute these fast and anchor back the result of these transaction through succinct checkpoints. ZK-Rollups are emerging as compelling methods to establish the integrity of such checkpoints, by the use of compressed cryptographic proofs.

Clustering and outlier detection are often studied as separate problems. However, previous work has shown that a unified approach can lead to better performance. Unified clustering and outlier detection is a hard combinatorial problem that has received significant attention in recent years. The recent emergence of specialized optimization hardware capable of solving combinatorial problems formulated as Quadratic Unconstrained Binary Optimization (QUBO) models has led to increased interest in harnessing these platforms in core data mining tasks. In this work, we present a novel QUBO formulation of the unified clustering and outlier detection problem and use the Fujitsu Digital Annealer, a specialized CMOS hardware, to solve it. Experiments on synthetic and real datasets demonstrate the effectiveness of our approach.

Recent hardware advances in quantum and quantum-inspired annealers promise substantial speedup for solving NP-hard combinatorial optimization problems compared to general-purpose computers. These special-purpose hardware are built for solving hard instances of Quadratic Unconstrained Binary Optimization (QUBO) problems. In terms of number of variables and precision of these hardware are usually resource-constrained and they work either in Ising space or in Boolean space. Many naturally occurring problem instances are higher-order in nature. The known method to reduce the degree of a higher-order optimization problem uses Rosenberg's polynomial. The method works in Boolean space by reducing the degree of one term by introducing one extra variable. In this work, we prove that in Ising space the degree reduction of one term requires the introduction of two variables. Our proposed method of degree reduction works directly in Ising space, as opposed to converting an Ising polynomial to Boolean space and applying previously known Rosenberg's polynomial. For sparse higher-order Ising problems, this results in a more compact representation of the resultant QUBO problem, which is crucial for utilizing resource-constrained QUBO solvers.

The emergence of specialized optimization hardware such as CMOS annealers and adiabatic quantum computers carries the promise of solving hard combinatorial optimization problems more efficiently in hardware. Recent work has focused on formulating different combinatorial optimization problems as Ising models, the core mathematical abstraction used by a large number of these hardware platforms, and evaluating the performance of these models when solved on specialized hardware. An interesting area of application is data mining, where combinatorial optimization problems underlie many core tasks. In this work, we focus on consensus clustering (clustering aggregation), an important combinatorial problem that has received much attention over the last two decades. We present two Ising models for consensus clustering and evaluate them using the Fujitsu Digital Annealer, a quantum-inspired CMOS annealer. Our empirical evaluation shows that our approach outperforms existing techniques and is a promising direction for future research.

Big Data has changed both technologies and practices for building data analytics systems. A number of working groups have been discussing the recent changes along a number of dimensions. The NIST Big Data Public Working Group organized a workshop to promote communication among working groups, technologists, and practitioners to come to an understanding of the current state of the Big Data discipline, collaboration best practices, future directions for this emerging specialization, and to identify security and privacy concerns.

In this paper, we describe a framework for a refinement scheme located in a centralized policy server that consists of three components: a knowledge database, a refinement rule set, and a policy repository. The refinement process includes two successive steps: policy transformation and policy composition. Our refinement scheme takes policies written in our logic-based abstract policy language as input and generates low level rules directly implementable by individual enforcement points. We provide concrete policy examples in a coalition scenario that forms a mobile ad hoc network (MANET). We demonstrate policy composition using a distributed firewall scheme named ROFL (ROuting as the Firewall Layer) and access control list as enforcement mechanisms.

Protocol authentication properties are generally trace-based, meaning that authentication holds for the protocol if authentication holds for individual traces (runs of the protocol and adversary). Computational secrecy conditions, on the other hand, often are not trace based: the ability to computa tionally distinguish a system that transmits a secret from one that does not is measured by overall success on the set of all traces of each system. Non-trace-based properties present a challenge for inductive or compositional methods: induction is a natural way of reasoning about traces of a system, but it does not appear directly applicable to non-trace properties. We therefore investigate the semantic connection between trace properties that could be established by induction and non-trace-based security requirements. Specifically, we prove that a certain trace property implies computational secrecy and authentication properties, assuming the encryption scheme provides chosen ciphertext security and ciphertext integrity. We also prove a similar theorem for computational secrecy assuming Decisional Diffie–Hellman and a chosen plaintext secure encryption scheme.

We propose a specification logic called Temporally Attributed Boolean (TAB) Logic for Assertion Based Verification, which allows us to: (i) represent assertions succinctly, (ii) incorporate data-orientation and (iii) associate timing to design intentions. TAB Logic allows us to write specifications functionally linking system variables from different temporal contexts. We present examples to show the motivation for this logic especially in the context of high level modeling of complex real time systems. We formally define TAB Logic, formulate the problem of verification on a simulation trace and present efficient algorithms to check TAB assertions, both offline and online. We present results of application of TAB Logic for Instruction Semantics and Bus Transaction Verification of a bus integrated pipelined processor core implementation. We also employ TAB Logic to validate the Interrupt mode behavior of the processor core implementation. Further, we show the utility of TAB Logic in fault detection. Finally, we demonstrate the applicability of TAB Logic in the domain of simulation based verification of analog circuits like Operational Amplifiers and DC-DC Converters. We finally discuss the limitations of TAB logic and conclude.

Microprocessor pipeline simulation at the system level is an extremely important activity in the architecture exploration process. In this article, we address the problem of validating and debugging a pipeline simulator from the specific perspective of instruction scheduling. We propose a general framework for a systematic validation process and show that the assumptions made are justified for most standard pipeline models. The framework does not need any formal specification of the pipeline logic and hence can be readily integrated into the simulation and iteration-based architectural design space exploration process. We propose a concept of semantic equivalence between two simulations called D* equivalence which effectively captures the dataflow between instructions through registers. We then proceed to propose an algorithm which decides this equivalence in time polynomial in the number of instructions executed and the number of registers. We implement the algorithm and demonstrate how the framework facilitates debugging.