Paper detail

Linear time encodable binary code achieving GV bound with linear time encodable dual achieving GV bound

We initiate the study of what we term ``fast good codes'' with ``fast good duals.'' Specifically, we consider the task of constructing a rate 1/2 binary linear code such that both it and its dual are asymptotically good (in fact, have rate-distance tradeoff approaching the GV bound), and are encodable in linear time. While we believe such codes should find applications more broadly, as motivation we describe how such codes can be used the secure computation task of encrypted matrix-vector product. Our main contribution is a construction of such a fast good code with fast good dual. Our construction is inspired by the repeat multiple accumulate (RMA) code. To create the rate 1/2 code, after repeating each message coordinate, we perform accumulation steps -- where first a uniform coordinate permutation is applied, and afterwards the prefix-sum mod 2 is applied -- which are alternated with discrete derivative steps -- where again a uniform coordinate permutation is applied, and afterwards the previous two coordinates are summed mod 2. Importantly, these two operations are inverse of each other. In particular, the dual of the code is very similar, with the accumulation and discrete derivative steps reversed. Our analysis is inspired by a prior analysis of RMA: we bound the expected number of codewords of weight below the GV bound. We face new challenges in controlling the behaviour of the discrete derivative operation (which can significantly drop the weight of a vector), which we overcome by careful case analysis.