[continued from previous message]

In this work, we put forth new definitions and practical constructions for traceable secret sharing. In our model, some $f < t$ servers output a reconstruction box~$R$ that may arbitrarily depend on their shares. Given additional $t-f$ shares, $R$
reconstructs and outputs the secret. The task is to trace $R$ back to the corrupted servers given
black-box access to $R$. Unlike Goyal et al., we do not assume that the tracing algorithm has any information on how the corrupted servers constructed~$R$ from the shares in their possession.

We then present two very efficient constructions of traceable secret sharing based on two classic secret sharing schemes. In both of our schemes, shares are only twice as large as the secret, improving over the quadratic overhead of Goyal et al. Our
first scheme is obtained by presenting a new practical tracing algorithm for the widely-used Shamir secret sharing scheme. Our second construction is based on an extension of Blakley's secret sharing scheme. Tracing in this scheme is optimally efficient,
and requires just one successful query to $R$. We believe that our constructions are an important step towards bringing traceable secret-sharing schemes to practice. This work also raises several interesting open problems that we describe
in the paper.



## 2024/406

* Title: Some notes on algorithms for abelian varieties
* Authors: Damien Robert
* [Permalink](https://eprint.iacr.org/2024/406)
* [Download](https://eprint.iacr.org/2024/406.pdf)

### Abstract

A compilation of various notes written over the years on some algorithms on abelian varieties.



## 2024/407

* Title: Permutation-Based Hashing Beyond the Birthday Bound
* Authors: Charlotte Lefevre, Bart Mennink
* [Permalink](https://eprint.iacr.org/2024/407)
* [Download](https://eprint.iacr.org/2024/407.pdf)

### Abstract

It is known that the sponge construction is tightly indifferentiable from a random oracle up to around $2^{c/2}$ queries, where $c$ is the capacity. In particular, it cannot provide generic security better than half of the underlying permutation size. In
this paper, we aim to achieve hash function security beating this barrier. We present a hashing mode based on two $b$-bit permutations named the double sponge. The double sponge can be seen as the sponge embedded within the double block length hashing
paradigm, making two permutation calls in parallel interleaved with an efficient mixing function. Similarly to the sponge, the permutation size is split as $b = r+c$, and the underlying compression function absorbs $r$ bits at a time. We prove that the
double sponge is indifferentiable from a random oracle up to around $2^{2c/3}$ queries. This means that the double sponge achieves security beyond the birthday bound in the capacity. In addition, if $c>3b/4$, the double sponge beats the birthday bound in
the primitive size, to our knowledge being the first hashing mode based on a permutation that accomplices this feature.



## 2024/408

* Title: Modular Indexer: Fully User-Verified Execution Layer for Meta-Protocols on Bitcoin
* Authors: Hongbo Wen, Hanzhi Liu, Shuyang Tang, Shuhan Cao, Domo, Yu Feng
* [Permalink](https://eprint.iacr.org/2024/408)
* [Download](https://eprint.iacr.org/2024/408.pdf)

### Abstract

Before the emergence of inscriptions and ordinal protocols, Bitcoin was limited in its applications due to the Turing-incompleteness of its script language. Fortunately, with recent advances in techniques, Turing-complete off-chain execution layers are
established via Bitcoin indexers. Yet, existing indexers have their data integrity and availability strongly dependent on the honesty of indexers. This violated the trustlessness and decentralization principle of the cryptocurrency literature. To provide
an alternative Bitcoin indexer scheme and overcome the above limitations, we have reallocated the roles of committee indexers (for heavy computations), normal indexers, and light indexers (the client end), and established a fully user-verified execution
layer based on our modular indexer protocol. For the trustless relay of data, we have adopted Verkle trees to store and prove the states. Thus, data integrity and availability are guaranteed even in the case of a majority of malicious committee indexers.
Ideally, our modular indexer would safely bridge the gap between the Bitcoin layer-1 and applications from BRC-20, and contribute to the further prosperity of the Bitcoin ecosystem.



## 2024/409

* Title: Nebula: A Privacy-First Platform for Data Backhaul
* Authors: Jean-Luc Watson, Tess Despres, Alvin Tan, Shishir G. Patil, Prabal Dutta, Raluca Ada Popa
* [Permalink](https://eprint.iacr.org/2024/409)
* [Download](https://eprint.iacr.org/2024/409.pdf)

### Abstract

Imagine being able to deploy a small, battery-powered device nearly anywhere on earth that humans frequent and having it be able to send data to the cloud without needing to provision a network—without buying a physical gateway, setting up WiFi
credentials, or acquiring a cellular SIM. Such a capability would address one of the greatest bottlenecks to deploying the long-tail of small, embedded, and power-constrained IoT devices in nearly any setting. Unfortunately, decoupling the device
deployment from the network configuration needed to transmit, or backhaul, sensor data to the cloud remains a tricky challenge, but the success of Tile and AirTag offers hope. They have shown that mobile phones can crowd-source worldwide local network
coverage to find lost items, yet expanding these systems to enable general-purpose backhaul raises privacy concerns for network participants. In this work, we present Nebula, a privacy-focused architecture for global, intermittent, and low-rate data
backhaul to enable nearly any thing to eventually connect to the cloud while (i) preserving the privacy of the mobile network participants from the platform provider by decentralizing data flow through the system, (ii) incentivizing participation through
micropayments, and (iii) preventing system abuse.



## 2024/410

* Title: Recent Progress in Quantum Computing Relevant to Internet Security
* Authors: Hilarie Orman
* [Permalink](https://eprint.iacr.org/2024/410)
* [Download](https://eprint.iacr.org/2024/410.pdf)

### Abstract

Quantum computers at some future date might be able
to factor large numbers, and this poses a threat to some public key
and key exchange systems in use today. This overview of recent
progress in devising quantum algorithms and building quantum computing devices is meant to help technologists understand the difficult problems that quantum engineers are working on, where advances have been made, and how those things affect estimates of
if and when large scale quantum computation might happen.



## 2024/411

* Title: Polytopes in the Fiat-Shamir with Aborts Paradigm
* Authors: Henry Bambury, Hugo Beguinet, Thomas Ricosset, Eric Sageloli
* [Permalink](https://eprint.iacr.org/2024/411)
* [Download](https://eprint.iacr.org/2024/411.pdf)

### Abstract

The Fiat-Shamir with Aborts paradigm (FSwA) uses rejection sampling to remove a secret’s dependency on a given source distribution. Recent results revealed that unlike the uniform distribution in the hypercube, both the continuous Gaussian and the
uniform distribution within the hypersphere minimise the rejection rate and the size of the proof of knowledge. However, in practice both these distributions suffer from the complexity of their sampler. So far, those three distributions are the only
available alternatives, but none of them offer the best of all worlds: competitive proof of knowledge size and rejection rate with a simple sampler.
We introduce a new generic framework for FSwA using polytope based rejection sampling to enable a wider variety of constructions. As a matter of fact, this framework is the first to generalise these results to integral distributions. To complement the
lack of alternatives, we also propose a new polytope construction, whose uniform sampler approaches in simplicity that of the hypercube. At the same time, it provides competitive proof of knowledge size compared to that obtained from the Gaussian
distribution. Concurrently, we share some experimental improvements of our construction to further reduce the proof size. Finally, we propose a signature based on the FSwA paradigm using both our framework and construction. We prove it to be competitive
with Haetae in signature size and with Dilithium on sampler simplicity.



## 2024/412

* Title: Quasi-Optimal Permutation Ranking and Applications to PERK
* Authors: Slim Bettaieb, Alessandro Budroni, Marco Palumbi, Décio Luiz Gazzoni Filho
* [Permalink](https://eprint.iacr.org/2024/412)
* [Download](https://eprint.iacr.org/2024/412.pdf)

### Abstract

A ranking function for permutations maps every permutation of length $n$ to a unique integer between $0$ and $n!-1$. For permutations of size that are of interest in cryptographic applications, evaluating such a function requires multiple-precision
arithmetic. This work introduces a quasi-optimal ranking technique that allows us to rank a permutation efficiently without needing a multiple-precision arithmetic library. We present experiments that show the computational advantage of our method
compared to the standard lexicographic optimal permutation ranking. As an application of our result, we show how this technique improves the signature sizes and the efficiency of PERK digital signature scheme.



## 2024/413

* Title: Bent functions construction using extended Maiorana-McFarland’s class
* Authors: Juan Carlos Ku-Cauich, Javier Diaz-Vargas, Sara Mandujano-Velazquez * [Permalink](https://eprint.iacr.org/2024/413)
* [Download](https://eprint.iacr.org/2024/413.pdf)

### Abstract

In a particular case, we consider the extended Maiorana-McFarland’s class to obtain balanced bent functions restricted to vectors with even Hamming weight, an equal number of pre-images for each element in the range. Additionally, we demonstrate that
all bent functions are balanced when we restrict to vectors of even Hamming weight or vectors with odd Hamming weight. Given the necessary tools, we provide a simple algorithm to obtain new bent functions using Maiorana-McFarland.



## 2024/414

* Title: Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations
* Authors: Joseph Carolan, Alexander Poremba
* [Permalink](https://eprint.iacr.org/2024/414)
* [Download](https://eprint.iacr.org/2024/414.pdf)

### Abstract

Sponge hashing is a novel class of cryptographic hash algorithms which underlies the current international hash function standard SHA-3. In a nutshell, a sponge function takes as input a bit-stream of any length and processes it via a simple iterative
procedure: it repeatedly feeds each block of the input into a so-called block function, and then produces a short digest which consists of a subset of the final output bits. While much is known about the post-quantum security of the sponge construction
in the case when the block function is modeled as a random function or permutation, the case of invertible permutations, which more accurately models the construction underlying SHA-3, has so far remained a fundamental open problem.

In this work, we make new progress towards overcoming this barrier and show several results. First, we prove the ``double-sided zero-search'' conjecture proposed by Unruh (eprint' 2021) and show that finding zero-pairs in a random $2n$-bit permutation
requires at least $\Omega(2^{n/2})$ many queries---and this is tight due to Grover's algorithm. At the core of our proof lies a novel ``symmetrization argument'' which uses insights from the theory of Young subgroups. Second, we consider more general
variants of the double-sided search problem and show similar query lower bounds for them. As an application, we prove the quantum one-wayness of the single-round sponge with invertible permutations in the quantum random oracle model.



## 2024/415

* Title: Column-wise Garbling, and How to Go Beyond the Linear Model
* Authors: Lei Fan, Zhenghao Lu, Hong-Sheng Zhou
* [Permalink](https://eprint.iacr.org/2024/415)
* [Download](https://eprint.iacr.org/2024/415.pdf)

### Abstract

In the linear garbling model introduced by Zahur, Rosulek, and Evans (Eurocrypt 2015), garbling an AND gate requires at least \(2\kappa\) bits of ciphertext, where $\kappa$ is the security parameter. Though subsequent works, including those by Rosulek
and Roy (Crypto 2021) and Acharya et al. (ACNS 2023), have advanced beyond these linear constraints, a more comprehensive design framework is yet to be developed.

Our work offers a novel, unified, and arguably simple perspective on garbled circuits. We introduce a hierarchy of models that captures all existing practical garbling schemes. By determining the lower bounds for these models, we elucidate the
capabilities and limits of each. Notably, our findings suggest that simply integrating a nonlinear processing function or probabilistic considerations does not break the \(2\kappa\) lower bound by Zahur, Rosulek, and Evans. However, by incorporating
column correlations, the bound can be reduced to \((1+1/w)\kappa\), where \(w\ge 1\). Additionally, we demonstrate that a straightforward extension of Rosulek and Roy's technique (Crypto 2021) does not yield improved results. We also present a
methodology for crafting new models and for exploring further extensions of both the new and the existing models.

Our new models set the course for future designs. We introduce three innovative garbling schemes based on a common principle called ``majority voting.'' The third construction performs on par with the state-of-the-art.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)