Beyond DCR: HSS and PCFs from Subgroup Indistinguishability (Sebastian Hasler) ia.cr/2026/2006
ePrint Updates
@eprint.ing.bot
1.2K followers 1 following 7.8K posts
Unofficial bot tracking the IACR Cryptology ePrint Archive (eprint.iacr.org). Maintained by @str4d.xyz. Currently only posts about new papers. Author names are linkified to Bluesky accounts (cryptography.social); contact maintainer for inclusion/removal.
![Abstract. Repeat–accumulate–accumulate (RAA) codes have minimum distance linear in the block length with probability tending to one, both with and without random coordinate scaling. Sharp results, however, reveal a tradeoff between the two constructions. For block length N = rn and fixed repetition factor r ≥ 4, the probability that the minimum distance is at most δN is Θ(N^(2 − r)) for unscaled RAA and Θ(N^(1 − r)) for scaled RAA, on their common proved range 0 < δ ≤ 1/10. Thus scaling reduces the failure probability by a factor of order N. This improvement comes at a cost: the scaled result requires q = Ω(N) over $\F_q$, and the encoder uses two length-N layers of coordinatewise field multiplications. In contrast, unscaled RAA works over a fixed field of characteristic greater than r, and its accumulator stages use only field additions.
In this work, we show that adding a third accumulator provides a substantially larger reliability gain without random scaling. For the unscaled repeat–accumulate–accumulate–accumulate ensemble
G₃ = RΠ₁AΠ₂AΠ₃A,
where R is r-fold repetition, A is the accumulator, and the Π_(i) are independent uniform interleavers, we prove that
$$
\Prb[d_{\min}(G_3)\le\delta N]
=\Theta_{r,\delta}\!\left(N^{\,2-r-\ceil{r/2}}\right)
$$
for every fixed r ≥ 4 and 0 < δ ≤ 1/10, uniformly over all finite fields of characteristic greater than r. Hence the field size need not grow with N, and the encoder requires three accumulator passes but no coordinatewise field multiplications. On the common threshold range, its failure probability is smaller by a factor of order $N^{\ceil{r/2}}$ than that of unscaled RAA and by a factor of order $N^{\ceil{r/2}-1}$ than that of scaled RAA. For example, when r = 4, the respective failure probabilities have orders N⁻², N⁻³, and N⁻⁴.](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:fwa55bujvdrwlwlwgqmmxmuf/bafkreifnwr2ft7mgmgucc7lahfqwqcm3cteseh2cpdj3qs36he43evamzy)
![Abstract. Verifiable secret sharing (VSS) is a core primitive in multiparty computation (MPC). Bhimrajka et al. [PKC’24, TIT’26] proposed the first computationally network-agnostic VSS and VSS-based MPC, which seamlessly accommodate both synchronous and asynchronous network models. However, their VSS requires Byzantine Agreement (BA) and incurs O(n⁵) bits of communication per sharing among n parties, and their MPC requires honest participation from nearly all parties.
We revisit the network-agnostic VSS architecture and propose a more efficient and general network-agnostic VSS structure. Our key technique is a new virtual-party strategy, which introduces more parties for reconstruction. With this technique, network-agnostic VSS is BA-free and performs as efficiently as synchronous VSS. Specifically, in terms of communication, our VSS costs O(n²) bits in the one-shot case and O(n) bits in the round-by-round case with the dispute-control technique, yielding the first computationally network-agnostic VSS protocols with amortized linear communication complexity. Besides, we further address a series of subtle yet necessary hurdles in adapting existing results to network-agnostic models, including the erasure coding techniques in Reliable Broadcast (RBC), packed secret sharing techniques in VSS, and the correlated polynomial techniques in MPC.](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:fwa55bujvdrwlwlwgqmmxmuf/bafkreigjlasgdrb3xy2rr2aqp2yqv7ok4ihiblyidoapr2kteoogkl5jpm)
![Abstract. Virtually all deployed private payment systems publish a nullifier for every transaction to prevent double spending. At a million transactions per second, the nullifier set grows by a petabyte each year. In this work, we tackle the question of sustaining massive throughput in private payments while ensuring the system can be run on commodity hardware.
We construct Bonsai, an account-based private payment scheme where validators store a single commitment per account and never store any nullifiers. Instead, each user privately maintains the nullifiers of the payments it has received, and can prune older nullifiers to cold storage so that its active state remains small. An external observer only learns that an account performed some action (send/receive) but never learns the amount or counterparty of a payment.
To verify proofs at this rate, we add zero-knowledge to Pari [USENIX ’26] with no increase in proof size and negligible prover overhead, and use it with a batch verification strategy. Our prototype verifies over a million operations per second on an M5 MacBook Pro.](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:fwa55bujvdrwlwlwgqmmxmuf/bafkreifb7h2u4va7ctekmztg5ijlgtssr6mx3k3sd5lrjnkuawiwptbdb4)
![Abstract. We report on the solution to the TII-254 McEliece key recovery challenge – currently the hardest solved challenge under the original brute-force metric (2²⁵⁴). The parameters of TII-254 are (m, t, n) = (8, 12, 223), defining a binary [223, 127] code specified by a full-rank (96 × 223) parity-check matrix. We state the method as a thirteen-step process, separating heuristic and non-heuristic choices. At a high level, we computed two complete 121-dimensional relation kernels conditioned at distinct public coordinates, combined them to isolate a certified 80-dimensional pair core, removed a 64-dimensional common nuisance space, and identified the remaining 16 dimensions as an 𝔽_(2⁸) projective-line geometry. This yielded all 87 visible locators, after which a deterministic completion search recovered the full support and polynomial. The two final Krylov sequences alone used 27.2 GPU-hours on NVIDIA GH200s, excluding GPU reconstruction and CPU processing. We provide a self-contained artifact with compact recovery inputs and code, an independent key verifier, and Lean proofs of the reusable linear-algebraic steps.](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:fwa55bujvdrwlwlwgqmmxmuf/bafkreiafeul6ypa4l6ci4w5sv6b4dz6a3knya6uywsj2dwsg7xbjru7tae)
