What a lovely hat

We prove that Basefold(Crypto 2024) is secure in the $\textit{list decoding regime}$, within the double Johnson bound and with error probability $\frac{O(n)}{|F|}$. At the heart of this proof is a new, stronger statement for $\textit{correlated agreement}$, which roughly states that if a linear combination of vectors $\pi_L + r \pi_R$ agrees with a codeword at every element in $S \subset [n]$, then so do $\pi_L, \pi_R$. Our result is purely combinatorial and therefore extends to any finite...

Proof-Carrying Data (PCD) is a foundational tool for ensuring the correctness of incremental distributed computations that has found numerous applications in theory and practice. The state-of-the-art PCD constructions are obtained via accumulation or folding schemes. Unfortunately, almost all known constructions of accumulation schemes rely on homomorphic vector commitments (VCs), which results in relatively high computational costs and insecurity in the face of quantum adversaries. A recent...

This work presents Deepfold, a novel multilinear polynomial commitment scheme (PCS) based on Reed-Solomon code that offers optimal prover time and a more concise proof size. For the first time, Deepfold adapts the FRI-based multilinear PCS to the list decoding radius setting, requiring significantly fewer query repetitions and thereby achieving a 3× reduction in proof size compared to Basefold (Crypto'24), while preserving its advantages in prover time. Compared with PolyFRIM (USENIX...

In this writeup we discuss the soundness of the Basefold multilinear polynomial commitment scheme [Zeilberger, Chen, Fisch 23] applied to Reed-Solomon codes, and run with proximity parameters up to the Johnson list decoding bound. Our security analysis relies on a generalization of the celebrated correlated agreement theorem from [Ben-Sasson, et al., 20] to linear subcodes of Reed-Solomon codes, which turns out a by-product of the Guruswami-Sudan list decoder analysis. We further highlight...

With the advancement of NIST PQC standardization, three of the four candidates in Round 4 are code-based schemes, namely Classic McEliece, HQC and BIKE. Currently, one of the most important tasks is to further analyze their security levels for the suggested parameter sets. At PKC 2022 Esser and Bellini restated the major information set decoding (ISD) algorithms by using nearest neighbor search and then applied these ISD algorithms to estimate the bit security of Classic McEliece, HQC and...

The problem of decoding random codes is a fundamental problem for code-based cryptography, including recent code-based candidates in the NIST post-quantum standardization process. In this paper, we present a novel sieving-style information-set decoding (ISD) algorithm, addressing the task of solving the syndrome decoding problem. Our approach involves maintaining a list of weight-$2p$ solution vectors to a partial syndrome decoding problem and then creating new vectors by identifying pairs...

A $b$-error-correcting $m$-server Private Information Retrieval (PIR) protocol enables a client to privately retrieve a data item of a database from $m$ servers even in the presence of $b$ malicious servers. List-decodable PIR is a generalization of error-correcting PIR to achieve a smaller number of servers at the cost of giving up unique decoding. Previous constructions of error-correcting and list-decodable PIR have exponential computational complexity in $m$ or cannot achieve...

We propose a REinforced modified Dual-Ouroboros based on Gabidulin codes, shortly called REDOG. This is a code-based cryptosystem based on the well-known rank metric codes, Gabidulin codes. The public key sizes of REDOG are 14KB, 33KB, 63KB at the security levels of 128, 192, 256 bits respectively. There is no decoding failure in decryption. REDOG is IND-CPA. As a new result, we give the performance results of implementing REDOG including the time for Key generation, encryption, and...

The syndrome decoding problem lies at the heart of code-based cryptographic constructions. Information Set Decoding (ISD) algorithms are commonly used to assess the security of these systems. The most efficient ISD algorithms rely heavily on nearest neighbor search techniques. However, the runtime result of the fastest known ISD algorithm by Both-May (PQCrypto '17) was recently challenged by Carrier et al. (Asiacrypt '22), which introduce themselves a new technique called RLPN decoding which...

This document is an informal summary on the FRI low degree test [BSBHR18a], [BSCI+20], and DEEP algebraic linking from [BSGKS20]. Based on its most recent soundness analysis [BSCI+20], we discuss parameter settings for practical security levels, how FRI is turned into a polynomial commitment scheme, and the soundness of DEEP sampling in the list decoding regime. In particular, we illustrate the DEEP method applied to proving satisfiability of algebraic intermediate representations and prove...

The lattice sieving algorithm based on list-decoding of Becker-Ducas-Gama-Laarhoven (SODA 2016) is currently at the center of cryptanalysis cost estimates of candidate lattice schemes for post-quantum standardization. Yet, only an idealized version of this algorithm has been carefully modelled, i.e. given an efficient list-decoding oracle for a perfectly random spherical code. In this work, we propose an experimental analysis of the actual algorithm. The difficulty lies in estimating the...

Property-preserving hashing (PPH) consists of a family of compressing hash functions $h$ such that, for any two inputs $x,y$, we can correctly identify whether some property $P(x,y)$ holds given only the digests $h(x),h(y)$. In a basic PPH, correctness should hold with overwhelming probability over the choice of $h$ when $x,y$ are worst-case values chosen a-priori and independently of $h$. In an adversarially robust PPH (RPPH), correctness must hold even when $x,y$ are chosen adversarially...

Hashing arbitrary values to points on an elliptic curve is a required step in many cryptographic constructions, and a number of techniques have been proposed to do so over the years. One of the first ones was due to Shallue and van de Woestijne (ANTS-VII), and it had the interesting property of applying to essentially all elliptic curves over finite fields. It did not, however, have the desirable property of being indifferentiable from a random oracle when composed with a random oracle to...

Consider the identification (ID) via channels problem, where a receiver decides whether the transmitted identifier is its identifier, rather than decoding it. This model allows to transmit identifiers whose size scales doubly-exponentially in the blocklength, unlike common transmission codes with exponential scaling. Binary constant-weight codes (CWCs) suffice to achieve the ID capacity. Relating parameters of a binary CWC to the minimum distance of a code and using higher-order correlation...

We consider a set of security and privacy problems under reliability and storage constraints that can be tackled by using codes and particularly focus on the secret-key agreement problem. Polar subcodes (PSCs) are polar codes (PCs) with dynamically-frozen symbols and have a larger code minimum distance than PCs with only statically-frozen symbols. A randomized nested PSC construction, where the low-rate code is a PSC and the high-rate code is a PC, is proposed for successive cancellation...

We construct uniquely decodable codes against channels which are computationally bounded. Our construction requires only a public-coin (transparent) setup. All prior work for such channels either required a setup with secret keys and states, could not achieve unique decoding, or got worse rates (for a given bound on codeword corruptions). On the other hand, our construction relies on a strong cryptographic hash function with security properties that we only instantiate in the random oracle model.

A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are $\delta$-close to the property in relative Hamming distance or (ii) only a tiny fraction of members are $\delta$-close to the property. In particular, no set in the collection has roughly half of its members $\delta$-close to the property and the others $\delta$-far from it. We show that the collection of affine spaces displays a proximity gap with...

We give the first construction of three-round non-malleable commitments from the almost minimal assumption of injective one-way functions. Combined with the lower bound of Pass (TCC 2013), our result is almost the best possible w.r.t. standard polynomial-time hardness assumptions (at least w.r.t. black-box reductions). Our results rely on a novel technique which we call bidirectional Goldreich-Levin extraction. Along the way, we also obtain the first rewind secure delayed-input witness...

Motivated by the quest for scalable and succinct zero knowledge arguments, we revisit worst-case-to-average-case reductions for linear spaces, raised by [Rothblum, Vadhan, Wigderson, STOC 2013]. The previous state of the art by [Ben-Sasson, Kopparty, Saraf, CCC 2018] showed that if some member of an affine space $U$ is $\delta$-far in relative Hamming distance from a linear code $V$ — this is the worst-case assumption — then most elements of $U$ are almost-$\delta$-far from $V$ — this is the...

A repair of the Faure-Loidreau (FL) public-key code-based cryptosystem is proposed.The FL cryptosystem is based on the hardness of list decoding Gabidulin codes which are special rank-metric codes. We prove that the recent structural attack on the system by Gaborit et al. is equivalent to decoding an interleaved Gabidulin code. Since all known polynomial-time decoders for these codes fail for a large constructive class of error patterns, we are able to construct public keys that resist the...

With the fast development of quantum computation, code based cryptography arises public concern as a candidate of post quantum cryptography. However, the large key-size becomes a main drawback such that the code-based schemes seldom become practical although they performed pretty well on the speed of both encryption and decryption algorithm. Algebraic geometry codes was considered to be a good solution to reduce the size of keys, but because of its special construction, there have lots of...

We provide a new approach to the elliptic curve discrete logarithm problem (ECDLP). First, we construct Elliptic Codes (EC codes) from the ECDLP. Then we propose an algorithm of finding the minimum weight codewords for algebraic geometry codes, especially for the elliptic code, via list decoding. Finally, with the minimum weight codewords, we show how to solve ECDLP. This work may provide a potential approach to speeding up the computation of ECDLP

Recently we have defined Staircase-Generator codes (St-Gen codes) and their variant with a random split of the generator matrix of the codes. One unique property of these codes is that they work with arbitrary error sets. In this paper we give a brief overview of St-Gen codes and the list decoding algorithm for their decoding. We also analyze the semantic security against chosen plaintext attack (IND-CPA) and key-privacy i.e. indistinguishability of public keys under chosen plaintext attack...

Staircase-Generator codes (St-Gen codes) have recently been introduced in the design of code-based public key schemes and for the design of steganographic matrix embedding schemes. In this paper we propose a method for random splitting of St-Gen Codes and use it to design a new coding based public key encryption scheme. The scheme uses the known list decoding method for St-Gen codes, but introduces a novelty in the creation of the public and private key. We modify the classical approach for...

We present a novel method for constructing linear secret sharing schemes (LSSS) from linear error correcting codes and linear universal hash functions in a blackbox way. The main advantage of this new construction is that the privacy property of the resulting secret sharing scheme essentially becomes independent of the code we use, only depending on its rate. This allows us to fully harness the algorithmic properties of recent code constructions such as efficient encoding and decoding or...

Recently, Gligoroski et al. proposed code-based encryption and signature schemes using list decoding, blockwise triangular private keys, and a nonuniform error pattern based on ``generalized error sets." The general approach was referred to as \emph{McEliece in the World of Escher.} This paper demonstrates attacks which are significantly cheaper than the claimed security level of the parameters given by Gligoroski et al. We implemented an attack on the proposed 80-bit parameters which was...

Learning with errors (LWE) was introduced by Regev in 2005, which enjoys attractive worst-case hardness properties. It has served as the foundation for a variety of cryptographic schemes. There are two main types of attacks against LWE: one for the decision version of LWE, the other for the search version of LWE. In this paper, we apply the list decoding method to solve search version of LWE. Our algorithm runs in probabilistic polynomial time and results in specific security estimates for...

It is a long-standing open problem to prove the existence of (deterministic) hard-core predicates for the Computational Diffie-Hellman (CDH) problem over finite fields, without resorting to the generic approaches for any one-way functions (e.g., the Goldreich-Levin hard-core predicates). Fazio et al. (FGPS, Crypto '13) make important progress on this problem by defining a weaker Computational Diffie-Hellman problem over $\mathbb{F}_{p^2}$, i.e., Partial-CDH problem, and proving, when...

We present a new family of linear binary codes of length n and dimension k accompanied with a fast list decoding algorithm that can correct up to n/2 errors in a bounded channel with an error density $\rho$. The decisional problem of decoding random codes using these generalized error sets is NP-complete. Next we use the properties of these codes to design both an encryption scheme and a signature scheme. Although in the open literature there have been several proposals how to produce...

Locally decodable codes (LDC)~\cite{BFLS91,KT00} are error correcting codes that allow decoding (any) individual symbol of the message, by reading only few symbols of the codeword. Consider an application such as storage solutions for large data, where errors may occur in the disks (or some disks may just crush). In such an application, it is often desirable to recover only small portions of the data (have random access). Thus, in such applications, using LDC provides enormous efficiency...

A long-standing open problem in cryptography is proving the existence of (deterministic) hard-core predicates for the Diffie-Hellman problem defined over finite fields. In this paper, we make progress on this problem by defining a very natural variation of the Diffie-Hellman problem over $\mathbb{F}_{p^2}$ and proving the unpredictability of every single bit of one of the coordinates of the secret DH value. To achieve our result, we modify an idea presented at CRYPTO'01 by Boneh and...

Inspired by cold boot attacks, Heninger and Shacham (Crypto 2009) initiated the study of the problem of how to recover an RSA private key from a noisy version of that key. They gave an algorithm for the case where some bits of the private key are known with certainty. Their ideas were extended by Henecka, May and Meurer (Crypto 2010) to produce an algorithm that works when all the key bits are subject to error. In this paper, we bring a coding-theoretic viewpoint to bear on the problem of...

The wild McEliece cryptosystem uses wild Goppa codes over finite fields to achieve smaller public key sizes compared to the original McEliece cryptosystem at the same level of security against all attacks known. However, the cryptosystem drops one of the confidence-inspiring shields built into the original McEliece cryptosystem, namely a large pool of Goppa polynomials to choose from. This paper shows how to achieve almost all of the same reduction in key size while preserving this shield....

We analyze the multivariate generalization of Howgrave-Graham's algorithm for the approximate common divisor problem. In the $m$-variable case with modulus $N$ and approximate common divisor of size $N^\beta$, this improves the size of the error tolerated from $N^{\beta^2}$ to $N^{\beta^{(m+1)/m}}$, under a commonly used heuristic assumption. This gives a more detailed analysis of the hardness assumption underlying the recent fully homomorphic cryptosystem of van Dijk, Gentry, Halevi, and...

We prove that if one can predict any of the bits of the input to an elliptic curve based one-way function over a finite field, then we can invert the function. In particular, our result implies that if one can predict any of the bits of the input to a classical pairing-based one-way function with non-negligible advantage over a random guess then one can efficiently invert this function and thus, solve the Fixed Argument Pairing Inversion problem (FAPI-1/FAPI-2). The latter has implications...

The original McEliece cryptosystem uses length-n codes over F_2 with dimension >=n-mt efficiently correcting t errors where 2^m>=n. This paper presents a generalized cryptosystem that uses length-n codes over small finite fields F_q with dimension >=n-m(q-1)t efficiently correcting floor(qt/2) errors where q^m>=n. Previously proposed cryptosystems with the same length and dimension corrected only floor((q-1)t/2) errors for q>=3. This paper also presents list-decoding algorithms that...

Traitor tracing schemes are cryptographically secure broadcast methods that allow identification of conspirators: if a pirate key is generated by $k$ traitors out of a static set of $\ell$ legitimate users, then all traitors can be identified given the pirate key. In this paper we address three practicality and security issues of the Boneh-Franklin traitor-tracing scheme. In the first place, without changing the original scheme, we modify its tracing procedure in the non-black-box model such...

This paper presents several improvements to Stern's attack on the McEliece cryptosystem and achieves results considerably better than Canteaut et al. This paper shows that the system with the originally proposed parameters can be broken in just 1400 days by a single 2.4GHz Core 2 Quad CPU,or 7 days by a cluster of 200 CPUs. This attack has been implemented and is now in progress. This paper proposes new parameters for the McEliece and Niederreiter cryptosystems achieving standard levels...

Given a corrupted word $\w = (w_1, \ldots, w_n)$ from a Reed-Solomon code of distance $d$, there are many ways to efficiently find and correct its errors. But what if we are instead given $(g^{w_1}, \ldots, g^{w_n})$ where $g$ generates some large cyclic group --- can the errors still be corrected efficiently? This problem is called \emph{error correction in the exponent}, and though it arises naturally in many areas of cryptography, it has received little attention. We first show that...

Recently, Augot and Finiasz presented a coding theoretic public key cryptosystem that suggests a new approach for designing such systems based on the Polynomial Reconstruction Problem. Their cryptosystem is an instantiation of this approach under a specific choice of parameters which, given the state of the art of coding theory, we show in this work to be sub-optimal. Coron showed how to attack the Augot and Finiasz cryptosystem. A question left open is whether the general approach...

We apply powerful, recently discovered techniques for the list decoding of error-correcting codes to the problem of efficiently tracing traitors. Traitor tracing schemes have been extensively studied for use as a piracy deterrent. In a widely studied model for protecting digital content, each user in the system is associated with a unique set of symbols. For example, the sets may be used to install a software CD or decrypt pay-TV content. The assignment of sets is done in such a way that if...

The Chinese Remainder Theorem states that a positive integer m is uniquely specified by its remainder modulo k relatively prime integers p_1,...,p_k, provided m < \prod_{i=1}^k p_i. Thus the residues of m modulo relatively prime integers p_1 < p_2 < ... < p_n form a redundant representation of m if m <= \prod_{i=1}^k p_i and k < n. This suggests a number-theoretic construction of an ``error-correcting code'' that has been implicitly considered often in the past. In this paper we provide a...