CS Paper Radar

On Relative Greedy Weights

Olav Geil

cs.IT cs.CR ·submitted 2026-11-07 08:15 UTC · v1

Abstract

Relative greedy weights were introduced by Li and Liu in [19] as a measure of information leakage in coordinated two-party wire-tap channels of type II when the adversary follows a greedy strategy. Their definition can be viewed as a relative version of the CEZ greedy weights, which are only locally greedy. In this paper, we revisit the concept of greediness and relative greediness introducing new measures, and we discuss other perhaps more relevant applications of relative greedy weights than the coordinated two-party wire-tap channel of type II. We pay special attention to bottom-up greedy weights, which correspond to an adversary with an ultimate greedy approach, and we present families of nested codes for which such weights are larger than the relative CEZ greedy weights.

Closest papers

Nearest neighbours by meaning across the whole index.

On the Leakage of Massey Secret Sharing Schemes under Linear Computations

cs.CR ·2026-09-17 ·Nadja Aoutouf, Daniel Augot
hot direction similarity 0.57
Abstract

Leakage attacks on secret sharing schemes exploit partial information about individual shares to recover the underlying secret. In coding theory, linear exact repair schemes (LERSs) enable the recovery of one codeword symbol from a small amount of information obtained from the remaining symbols, provided that the code has sufficiently low rate. This can be interpreted as recovering the secret from partial information, namely subfield symbols, of the shares. Recently, a randomized construction based on subfield subcodes was proposed for constructing LERS-derived leakage attacks against Massey secret sharing schemes based on general linear codes. We extend this framework to multiple shared secrets whose corresponding shares are related through linear computations, with leakage also allowed on the computation outcomes. More precisely, we consider N secrets, of which K $\le$ N are linearly independent input values and the remaining N -K secrets are determined by linear computations on these inputs. We analyse the existence of LERS-derived leakage that exploits this structure. We first study the case of addition and then generalize our construction to arbitrary linear computations. Our analysis applies to general linear codes of length n+1 and dimension k over F\_{q^m} with k $\le$ N n/(Km), and supports arbitrary linear computations, whereas the previous subfield subcode construction only applies to k $\le$ n/m -1. Consequently, exploiting the linear relations enables LERS based leakage which extend the range of code parameters vulnerable to such attacks. Finally, identical leakage functions can arise for certain linear relations, making this a more realistic yet still potentially powerful attack model. Finally, simulations indicate that identical leakage functions can be used for certain linear relations, yielding a more realistic attack model.

0.37

Systematic Derivation of Leakage in Massey Secret Sharing Schemes

cs.CR ·2026-11-02 ·Nadja Aoutouf, Daniel Augot
similarity 0.55
Abstract

Leakage attacks on secret sharing schemes can be based on the exploitation of partial information about individual shares to recover the underlying secret. In coding theory, linear exact repair schemes (LERSs) allow the recovery of a codeword symbol from limited information obtained from the remaining symbols. When applied to code-based secret sharing schemes, such repair schemes can be interpreted as recovering the secret from partial information about the shares, expressed in terms of subfield symbols. Guruswami and Wootters introduced the first explicit constructions of LERSs for low-rate Reed--Solomon codes that is optimal in terms of bandwidth. In this work, we first investigate the construction and algebraic properties of LERSs, building on the Guruswami-Wootters construction. We derive new explicit repair schemes from their construction and establish structural properties of the resulting schemes. Second, we further develop a systematic computational approach based on a Gr{ö}bner bases approach to identify leakage functions associated with LERSs for arbitrary linear codes. This approach enables us to investigate the existence and structural properties of LERSs across different code families and parameter ranges. We first applied our method to Reed-Solomon codes, which gave as further insights into the algebraic structure of LERSs. Moreover, by applying our method to generalized Reed-Muller and Tamo-Barg codes, we identify several LERSs that, to the best of our knowledge, have not previously been described in the literature.

0.03

Secret Sharing Despite Non-Extractable Randomness

cs.CR ·2026-10-14 ·Divesh Aggarwal
similarity 0.54
Abstract

Bosley and Dodis (TCC 2007) proved that a class of imperfect randomness sources that suffices for information-theoretic encryption of messages longer than the logarithm of the key length must admit deterministic extraction of nearly uniform bits, and asked whether the same is true of two-out-of-two secret sharing. Aggarwal, Chung, Obremski, and Ribeiro (TCC 2022) gave a positive answer for schemes that are in addition leakage-resilient or non-malleable; the original question remained open. We answer it in the negative. For every $b\ge2$ we construct a class of flat sources on $\{0,1\}^{b+2}$, each of min-entropy at least $b$, together with a perfectly correct and perfectly private two-out-of-two scheme that shares a $b$-bit secret into two $(b+1)$-bit shares using any source in the class, and we show that every deterministic map from $\{0,1\}^{b+2}$ to $\{0,1\}$ is at statistical distance at least $1/6$ from uniform on some source in the class. This implies that sharing a long enough secret does not require extractable randomness. The proof is a short parity argument. The idea of the construction extends to other thresholds: for two-out-of-$n$ and $r$-out-of-$r$ sharing we give perfect schemes with $(b+1)$-bit shares, private for classes of flat sources from which no single bit can be extracted with error below $1/(4n-2)$ and $1/(2(2^r-1))$, respectively.

0.23

Adaptive Coding for Two-Way Wiretap Channels with One-Sided Strong Secrecy

cs.IT ·2026-09-12 ·Masahito Hayashi, Yanling Chen
theory similarity 0.54
Abstract

We study a discrete memoryless two-way wiretap channel under strong one-sided secrecy, where User 1's message is confidential and User 2's message is not required to be secret. We develop non-adaptive and key-assisted adaptive inner bounds from a common resolvability estimate for selected index components. For the adaptive construction, we prove a multiround leakage theorem that accounts both for information revealed about a key before its later use and for the possibility that an encoder uses an incorrectly decoded key. The proof includes an ideal-to-implemented coupling, deterministic codebook selection, and a growing-round argument that removes the initialization-rate loss. We eliminate the internal component rates exactly and characterize the adaptive gain at each fixed auxiliary distribution. For an open two-parameter family of binary channels, we also prove a converse for arbitrary non-adaptive stochastic codes and obtain an operational adaptive-versus-non-adaptive separation. For one representative channel, the complete non-adaptive strong one-sided secrecy capacity region is identified exactly.

0.16

A Public-Key-Dependent Adversarial-Deletion Ceiling for Fixed-Alphabet Multi-Bit Pseudorandom Codes

cs.CR cs.IT ·2026-08-31 ·Frederick Dehmel, Shilun Li
theoryhot direction similarity 0.53
Abstract

A pseudorandom code (PRC) is a keyed error-correcting code whose codewords are computationally indistinguishable from uniform strings. We study public-key PRCs over fixed alphabets against adversarial deletions, where the deletion channel may both depend on the public encoding key and the transmitted codeword. Let $γ_q^{\mathrm{LCS}}$ denote the asymptotic normalised longest-common-subsequence length of two independent uniform $q$-ary strings. We prove that for every fixed $q\ge2$ no multi-message public-key PRC with a single-output decoder is robust against all such $δ$-deletion channels for any $δ>1-γ_q^{\mathrm{LCS}}$. For $q=2$, the current rigorous bound $γ_2\ge0.792665992$ rules out every constant $δ>0.207334008$. The proof uses pseudorandomness only to transfer an LCS event from uniform strings to independently sampled codewords and therefore also the resulting collision argument is information-theoretic and requires no secret key. We also extend the argument to list decoding: for every fixed constant $L$, provided the message space contains at least $L+1$ messages, no such PRC with output lists of size at most $L$ is robust for $δ>1-γ_2^{(L+1)}$. Since $γ_2^{(m)}=1/2+Θ(1/\sqrt m)$, these thresholds approach $1/2$. Our bounds are specific to public-key-dependent adversarial channels and do not apply to oblivious edit channels.

0.36

K-out-of-N Oblivious Transfer over Erasure Channels: Capacity and Reductions

cs.IT cs.CR ·2026-11-16 ·Amirhossein Shekofteh, Rémi A. Chou
similarity 0.53
Abstract · Submitted to IEEE Transactions on Information Theory

We study $K$-out-of-$N$ oblivious transfer (OT) between a server and a client over a discrete memoryless channel, under an honest-but-curious model. The client must retrieve $K$ out of $N$ messages stored by the server while learning nothing about the remaining $N-K$ messages, and the server must not learn the client's selection. For a binary erasure channel (BEC) with parameter $ε$, we show that the $K$-out-of-$N$ OT capacity is $\min\Big(\frac{Kε}{N-K},1-ε\Big)$. This characterization generalizes the known capacity results for $1$-out-of-$2$ OT and for $1$-out-of-$N$ OT when $ε\ge\tfrac{N-1}{N}$. We also investigate OT reductions, specifically, we show that constructing a $K$-out-of-$N$ OT protocol from repeating $K$ times an optimal $1$-out-of-$N$ OT protocol can be suboptimal, but we also identify certain ranges of $ε$ and $M < N$ for which a $1$-out-of-$N$ OT protocol can be optimally realized via the repetition of a $1$-out-of-$M$ OT protocol. Finally, we discuss extensions of our results to a generalized erasure channel (GEC).

0.28

Leakage-Resilient Computation via Matrix Refreshing

cs.CR ·2026-11-03 ·Stefan Dziembowski, Sebastian Faust
theory similarity 0.53
Abstract

Leakage-resilient cryptography protects secrets against side-channel attacks, in which a physical implementation reveals partial information about its internal state. A fundamental primitive in this area is a leakage-resilient storage, which allows a secret to be stored in a way that remains secure even if an adversary learns some information about the storage's internal state. A popular approach represents a secret as the inner product of two $n$-bit vectors, called shares. The shares are stored and processed separately by two parts of the implementation, called the left and right parties. Because leakage accumulates over time, the shares must be refreshed repeatedly. We prove that a simple refresh, in which the left party multiplies its share by a uniform invertible matrix $M$ and the right party multiplies its share by $M^{-1}$, is secure under continual local leakage. After $T$ refreshes, each allowing at most $λ$ bits of leakage per party, the transcripts for two stored secrets are at statistical distance at most $C\cdot T\cdot 2^{6λ-n/9}$ for an absolute constant $C$. We also obtain a Boolean-circuit compiler with statistical privacy error at most $C\cdot S\cdot 2^{18λ-n/27}$ for $S$ operations and at most $λ$ bits of local leakage per party per operation. The guarantee covers repeated stateful evaluations with adaptively chosen public inputs, with $S$ counting all operations across invocations. Thus, for polynomial-size circuits, a constant leakage fraction is tolerated with share length depending only on the security parameter. We formalize the refreshing bound, the composition and compiler guarantees, and the expected-work bounds in Lean 4. Our results also provide efficient simulation: the leakage can be reproduced from the public inputs and the circuit outputs alone, with expected polynomial overhead.

0.20

One-Shot Information Hiding and Compound Wiretap Channels

cs.IT ·2026-09-18 ·Yanxiao Liu, Cheuk Ting Li
similarity 0.53
Abstract

In recent years, due to the growing reliance on large amounts of data that are communicated, analyzed, and utilized, which inherently contain sensitive and personal information, secrecy and privacy in communication have become increasingly important. We present nonasymptotic information-theoretic analyses of two fundamental secrecy problems under channel uncertainties: the information hiding problem and the compound wiretap channel. The former admits a game-theoretic formulation, where one party (an information hider and a decoder) seeks to embed secret messages into a host signal for later reconstruction, while the opposing party (an attacker) attempts to remove or degrade the embedded information. The latter generalizes Wyner's wiretap channel by allowing multiple potential channel states. The information hiding problem concerns active attacks during data transmission, while the compound wiretap channel addresses passive eavesdropping and information leakage. The two problems, both of which consider channels with uncertainties, can be studied under a unified framework by utilizing a covering argument and the Poisson matching lemma by Li and Anantharam. We derive novel one-shot achievability results for both problems that are applicable to any source distribution and any class of channels (not necessarily memoryless or ergodic), and that apply to both discrete and continuous cases. We also show that existing asymptotic results on both problems can be recovered by applying our results to discrete memoryless channels.

0.17