Coding theory and cryptography

Edit Distance Robust Watermarks via Indexing Pseudorandom Codes

Motivated by the problem of detecting AI-generated text, we consider the problem of watermarking the output of language models with provable guarantees. We aim for watermarks which satisfy: (a)...

Hybrid Mamba-Transformer Decoder for Error-Correcting Codes

We introduce a novel deep learning method for decoding error correction codes based on the Mamba architecture, enhanced with Transformer layers. Our approach proposes a hybrid decoder that...

Neural-Inspired Advances in Integral Cryptanalysis

The study by Gohr et.al at CRYPTO 2019 and sunsequent related works have shown that neural networks can uncover previously unused features, offering novel insights into cryptanalysis. Motivated by...

Nested Construction of Polar Codes via Transformers

Tailoring polar code construction for decoding algorithms beyond successive cancellation has remained a topic of significant interest in the field. However, despite the inherent nested structure...

Row-Merged Polar Codes: Analysis, Design and Decoder Implementation

Row-merged polar codes are a family of pre-transformed polar codes (PTPCs) with little precoding overhead. Providing an improved distance spectrum over plain polar codes, they are capable to...

Relative hulls and quantum codes

Given two $q$-ary codes $C_1$ and $C_2$, the relative hull of $C_1$ with respect to $C_2$ is the intersection $C_1\cap C_2^\perp$. We prove that when $q>2$, the relative hull dimension can be...

Complexity Analysis of the SAT Attack on Logic Locking

Due to the adoption of horizontal business models following the globalization of semiconductor manufacturing, the overproduction of integrated circuits (ICs) and the piracy of intellectual...

In-depth analysis of S-boxes over binary finite fields concerning their differential and Feistel boomerang differential uniformities

Substitution boxes (S-boxes) play a significant role in ensuring the resistance of block ciphers against various attacks. The Difference Distribution Table (DDT), the Feistel Boomerang...

Locally Testable Codes with constant rate, distance, and locality

A locally testable code (LTC) is an error-correcting code that has a property-tester. The tester reads $q$ bits that are randomly chosen, and rejects words with probability proportional to their...

Fast List Decoding of High-Rate Polar Codes

Due to the ability to provide superior error-correction performance, the successive cancellation list (SCL) algorithm is widely regarded as one of the most promising decoding algorithms for polar...

KO codes: Inventing Nonlinear Encoding and Decoding for Reliable Wireless Communication via Deep-learning

Landmark codes underpin reliable physical layer communication, e.g., Reed-Muller, BCH, Convolution, Turbo, LDPC and Polar codes: each is a linear code and represents a mathematical breakthrough....

Strong blocking sets and minimal codes from expander graphs

A strong blocking set in a finite projective space is a set of points that intersects each hyperplane in a spanning set. We provide a new graph theoretic construction of such sets: combining...

Estimating the Weight Enumerators of Reed-Muller Codes via Sampling

This paper develops an algorithmic approach for obtaining estimates of the weight enumerators of Reed-Muller (RM) codes. Our algorithm is based on a technique for estimating the partition...

The hull of two classical propagation rules and their applications

In this work, we study and determine the dimensions of Euclidean and Hermitian hulls of two classical propagation rules, namely, the direct sum construction and the...

ORBGRAND Is Almost Capacity-Achieving

Decoding via sequentially guessing the error pattern in a received noisy sequence has received attention recently, and ORBGRAND has been proposed as one such decoding algorithm that is capable of...

Efficient Near Maximum-Likelihood Reliability-Based Decoding for Short LDPC Codes

In this paper, we propose an efficient decoding algorithm for short low-density parity check (LDPC) codes by carefully combining the belief propagation (BP) decoding and order statistic decoding...

MDS Variable Generation and Secure Summation with User Selection

A collection of $K$ random variables are called $(K,n)$-MDS if any $n$ of the $K$ variables are independent and determine all remaining variables. In the MDS variable generation problem, $K$ users...

On Lattices, Learning with Errors, Random Linear Codes, and Cryptography

Our main result is a reduction from worst-case lattice problems such as GapSVP and SIVP to a certain learning problem. This learning problem is a natural extension of the `learning from parity...