International Association
for Cryptologic Research

In this work, we study the proposal for a linkable ring signature (LRS) in [KTS+24]. It is instantiated from the group action based framework described in [BKP20], using the Lattice Isomorphism Group Action (LIGA), meaning that the security of the signature rests on the famous Lattice Isomorphism Problem (LIP).

We will show that this signature does not in fact fit the requirements to be a linkable ring signature, despite the guarantees of the [BKP20] framework, due to it straying from that framework by using a non-commutative group for the group actions. More specifically, we will show that the signature from [KTS+24] satisfies neither the property of correctness nor linkability, which are required of a LRS.

This further damages the signature, as it was already shown in [BCF25] that the linkable anonymity property of [KTS24+] isn't satisfied.

The group used in LIGA is the group of invertible integer matrices: $\mathrm{GL}_n(\mathbb{Z})$. As the main obstacle in successfully applying the framework mentioned above to construct a LRS based on LIP is the fact that this group is non-commutative, we try fixing the signature by restricting the secret key space to a commutative subgroup of $\mathrm{GL}_n(\mathbb{Z})$. However, we will see that finding a commutative subgroup of $\mathrm{GL}_n(\mathbb{Z})$ that maintains the hardness of the underlying LIP, and that at the same time is realistic to use is not as easy as it may seem.

Hax is a verification pipeline that translates a subset of Rust into F*, enabling machine-checked proofs of panic freedom and functional correctness for cryptographic implementations being developed in partnership with Google and tested in Signal's post-quantum protocol.

We study whether hax's translation preserves the security properties it claims to verify. Through a structural analysis of its 35-phase transformation engine, F* proof libraries, and specification API, we identify three classes of semantic gap between the Rust source and the F* verification target: translation infidelity, where pipeline transformations distort security-relevant semantics; unverifiable trust boundaries, where operations are axiomatized without postconditions; and specification gaming, where escape hatches inject unproven facts into the verification context.

We demonstrate each class through five proof-of-concept exploits against ML-DSA (FIPS 204), ML-KEM (FIPS 203), Ed25519 (FIPS 186-5), and ChaCha20 (RFC 8439). Every exploit meets a strict criterion: the Rust code compiles, passes functional tests, and extracts to F* without warnings, while harboring a security gap invisible to testing.

We distinguish three gradations: facade gaps where the F* model actively diverges from Rust semantics, a conditional gap dependent on the compilation mode, and a scope gap where the model is faithful but cannot cover a critical property. We call the resulting phenomenon a verification facade: verification that is performed but covers less than it appears to cover.

Payment channel networks (PCNs) are a leading method to deal with the scalability limitations of blockchain networks. PCNs allow users to execute transactions without committing them to the blockchain by relying on predefined payment channels. Transactions between pairs of users without a connecting channel are also supported through a path of multiple channels. Serving such transactions involves fees paid to intermediate users. In this paper, we uncover the potential existence of the Braess paradox in payment networks: Sometimes, establishing a new payment channel can increase the fees paid for serving some fixed transactions. We study conditions for the paradox to appear under two different models of fees: Liquidity-based fees as a function of the transaction value jointly with the channel liquidity values and proportional fees which are based only on the transaction value. We also provide indications for the appearance of the paradox based on real data from Lightning, a popular payment channel network of Bitcoin. Last, we discuss methods to mitigate the paradox upon establishing a new payment channel.

We consider the worst-case hardness of the gap version of the classic time-bounded Kolmogorov complexity problem—$Gap_pMK^tP[s_1,s_2]$—where the goal is to determine whether for a given string x, $K^t(x) ≤s_1(n)$ or $K^{p(t)}(x) > s_2(n)$, where $K^t(x)$ denotes the t-bounded Kolmogorov complexity of x. As shown by Hirahara (STOC’18), if $Gap_pMK^tP[s_1,s_2] \notin prBPP$ for every polynomial p, then (under appropriate derandomization assumption) $Gap_pMK^tP$ is errorless average-case hard with respect to BPP heuristics. The notion of errorless average-case hardness, however, is seemingly insufficient for cryptographic applications where one needs to consider average-case hardness against attacks that simply may err with some probability (i.e., two-sided error hardness).

In this work, we present several new consequences of the assumption that $Gap_pMK^tP[s_1,s_2]\notin P/poly$ for all polynomials p, for appropriate choices of $s_1$,$s_2$, and under appropriate (worst-case) derandomization assumptions. In particular, we show that this assumption implies:

- The existence of an (inefficient-prover) zero-knowledge proof system for NP with a non-uniform simulator w.r.t. adversaries with a-priori bounded-length auxiliary-input. - The existence of a hard disjoint NP pair, defined as a promise problem $(Y,N)$ where both $Y,N\in NP$; this provides a barrier towards showing that $Gap_pMK^tP$ is NP-complete.

The above results are proven via first showing that the above assumption implies the existence of a so-called conditional PRG—roughly speaking, a cryptographic PRG where indistinguishability only needs to hold for some (potentially not efficiently sampleable) distribution over the seed to the PRG. (In fact, this notion of a PRG also almost directly implies average-case hardness of $Gap_pMK^tP$, and as such, this provides a modular explanation to Hirahara’s results.) Finally, we show that for the results on conditional PRGs and Zero-knowledge Proofs, unconditional results can be obtained (that is, without making any derandomization assumptions), if considering an appropriate version of $Gap_pMK^tP$ concerning randomized $K^t$.

In recent years, the shuffle model has emerged as a prevalent paradigm in privacy-preserving data analysis, centered on the principle of \textit{privacy amplification via shuffling}: an individual user's report is obscured by the ``background noise'' of other users' messages, a phenomenon intuitively known as the \textit{privacy blanket}. This paper initiates a foundational and systematic study of this mechanism from an information-theoretic perspective. We investigate the following optimal noise-design problem: given that a target user's message $Y_1$ follows a distribution $P$, what is the optimal blanket noise distribution $Q$ that maximizes privacy? Specifically, when $Y_1 \sim P$ and the remaining messages $Y_2, \dots, Y_n \stackrel{\text{i.i.d.}}{\sim} Q$ are shuffled to produce an output $\boldsymbol{Z} = (Y_{\sigma(i)})_{i=1}^n$, we seek the $Q$ that affords the strongest protection for $Y_1$ under various metrics, including mutual information $I(Y_1; \mathbf{Z})$, total-variation-information $I_{\mathrm{TV}}(Y_1; \mathbf{Z})$, message recovery advantage, and expected posterior variance.

Our analysis reveals a series of non-intuitive results that challenge the conventional heuristic of setting $Q=P$. First, we prove that the optimal noise distribution $Q$ generally \textit{deviates} from the target distribution $P$. For binary alphabets, we show that the (near-)uniform distribution is optimal in a strong sense. For general finite alphabets, we derive an explicit analytical form $Q \propto \sqrt{P(1-P)}$ that achieves asymptotic optimality for mutual information. Furthermore, we demonstrate that our analytical framework transcends the shuffle model, yielding new security insights into broader cryptographic primitives such as the \textit{ideal cipher model} and \textit{honey encryption}.

Finally, we extend our results to the shuffle-DP paradigm, where messages $Y_i = \mathcal{R}(X_i)$ are outputs of $\varepsilon_0$-locally differentially private mechanisms. We establish a new, tight information-theoretic upper bound $I(X_1; \mathbf{Z} \mid (X_i)_{i=2}^n) \le \frac{(e^{\varepsilon_0/2}-1)^2}{2n} + \mathcal{O}(n^{-3/2})$. This result provides a sharp characterization that matches the optimal privacy-amplification parameters known in the literature, while offering a novel interpretation of the shuffling gain.

Post-quantum migration in TLS 1.3 should not be understood as a flat substitution problem in which one signature algorithm is replaced by another and the resulting deployment cost is read directly from primitive-level benchmarks. In certificate-based authentication, the practical effect of a signature family depends on where it appears in the certification hierarchy, how much of that hierarchy is exposed during the handshake, and how the resulting cryptographic burden is distributed across client and server roles. This makes post-quantum TLS migration a problem of cryptographic design in authenticated key establishment, rather than merely a matter of algorithm selection.

This paper presents a local experimental study of TLS 1.3 authentication strategies built on OpenSSL 3 and oqsprovider. Using a reproducible laboratory, it compares ML-DSA and SLH-DSA across multiple certificate placements, hierarchy depths, and key-exchange modes, including classical, hybrid, and pure post-quantum configurations. The analysis is organized around four complementary campaigns: a leaf-only comparison, a full hierarchy strategy matrix, a depth comparison, and a key-exchange exploration.

Across the experimental matrix, the clearest discontinuity appears when SLH-DSA is placed in the server leaf certificate. In that configuration, handshake latency and server-side compute cost increase by orders of magnitude, while strategies that confine SLH-DSA to upper trust layers and preserve ML-DSA in the interactive leaf remain within a substantially more plausible operational range. The results further show that transport size alone does not explain the heavy regime: outside leaf-SLH scenarios, transferred bytes and observed chain size track latency closely, but once SLH-DSA reaches the leaf, server-side cryptographic cost becomes dominant.

The paper therefore argues that post-quantum TLS migration is best evaluated as a problem of certificate-hierarchy design, chain exposure, and cryptographic cost concentration during live authentication. In practical terms, signature placement matters at least as much as signature-family choice.

We introduce metric-aware code-based cryptography by moving beyond the Hamming metric to the Niederreiter-Rosenbloom-Tsfasman (NRT) and sum-rank metrics and by exploiting their linear isometry groups via Bruhat-Chevalley-Renner decompositions. On the structural side, we give isometry-invariant distance tests: a parity-check prefix-rank test for single-chain NRT, its multi-prefix extension for block-NRT, and a block rank-profile test for sum-rank. We also analyze orbit structure under the relevant isometry subgroups and prove NP-hardness of a block-NRT canonicalization problem via a reduction from Exact-3-Cover, pinning down the difficulty of public ``structure recovery.'' On the design side, we propose an inner-outer Niederreiter cryptosystem that couples a short rowwise single-chain NRT inner code with $k_V$ outer binary Goppa codes across columns. For the resulting matrix code we prove a distance guarantee $d_{\mathrm{NRT}}\!\ge\!\delta_V\cdot \min_t d^{(t)}$ and give a simple two-stage decoder (outer Goppa per coordinate, then inner per column). Public keys are dense, obfuscated parity-checks $M=S H_{\mathrm{sys}} (PD)$ drawn from a metric-preserving subgroup, preserving decodability while hiding structure. Finally, we reduce NRT and sum-rank syndrome decoding to classical Hamming/Rank decoding, yielding one-wayness of the public syndrome map at standard regimes.

In the noisy $k$-XOR problem, one is given $y \in \mathbb F_2^M$ and must distinguish between the case where $y$ is uniform and the case where $y = Ax + e$, where $A$ is the adjacency matrix of a $k$-left-regular bipartite graph with $N$ variables and $M$ constraints, $x \in \mathbb F_2^N$ is random, and $e$ is noise with rate $\eta$. Lower bounds in restricted computational models such as Sum-of-Squares and low-degree polynomials are closely tied to the expansion of the underlying constraint graph, leading to conjectures that expansion implies hardness. We show that such conjectures are false by constructing an explicit family of graphs with near-optimal expansion for which noisy $k$-XOR is solvable in polynomial time.

Our construction combines two powerful directions of work in pseudorandomness and coding theory that have not been previously put together. Specifically, our graphs are based on the lossless expanders of Guruswami, Umans and Vadhan (JACM 2009). Our key insight is that by an appropriate interpretation of the vertices of their graphs, the noisy XOR problem turns into the problem of decoding Reed-Muller codes from random errors. Then we build on a powerful body of work from the 2010s correcting from large amounts of random errors. Putting these together yields our construction.

Concretely, we obtain explicit families for which noisy $k$-XOR is solvable in polynomial time at constant noise rate $\eta = 1/3$, with graphs satisfying $M = 2^{O(\log^2 N)}$, $k = (\log N)^{O(1)}$, and $(N^{1-\alpha}, 1-o(1))$-expansion. Under standard conjectures on Reed--Muller codes over the binary erasure channel, this extends to families with $M = N^{O(1)}$, $k = (\log N)^{O(1)}$, $(N^{1-\alpha}, 1-o(1))$-expansion, and polynomial-time algorithms at noise rate $\eta = N^{-c}$.

ECDSA is a widely deployed digital signature scheme used in securing communications and distributed systems but its structure prevents efficient batch verification. This limitation is impactful in high-throughput applications such as blockchain transaction validation. In this paper, we consider two modified versions of standard ECDSA, namely ECDSA_rec and ECDSA_ast, which embed additional bits in the signature, that enable efficient batch verification. We contribute the first publicly available C implementations of ECDSA_ast on secp256k1 and of both ECDSA_ast and ECDSA_rec on secp256r1, built on top of Bitcoin and OpenSSL codebases, respectively. We evaluate both variants on the two curves and demonstrate batch verification using the two established randomization techniques, NMVR-rand and HSS-rand. The results of our software implementation indicate that batch verification of modified ECDSA signatures usingHSS-rand generally outperforms individual verification of standard ECDSA. Furthermore, the HSS-rand technique provides more efficient batch verification than NMVR-rand in the majority of cases. For a batch of 32 ECDSA_ast (ECDSA_rec resp.) signatures on secp256k1, HSS-rand batch verification improves individual verification by approximately 30.9% (17.2% for ECDSA_rec) and outperforms NMVR_rand batch verification, which achieves improvements of 10.6% (9.8% for ECDSA_rec). The improvements achieved by HSS-rand on secp256r1 are even more pronounced, reaching 53.9% for ECDSA_ast and 40.5% for ECDSA_rec over individual verification of standard ECDSA signatures. In comparison, HSS-rand yields improvements of 27.6% for ECDSA_ast and 22.9% for ECDSA_rec over NMVR-rand, respectively.

Succinct non-interactive arguments (SNARGs) for P are a powerful tool for verifiably outsourcing a computation to a single entity. In this work, we study verifiable outsourcing in a distributed divide-and-conquer setting: a party tasked with solving a large computational problem divides it into smaller subproblems, delegates each subproblem to a different party, and then combines their solutions. Moreover, each party may recursively apply the same strategy, further delegating its computation. Verifying such recursive outsourcing requires SNARGs that are \emph{mergeable}, so that proofs for subproblems can be efficiently combined into a single proof for the original problem.

While mergeable proofs have been known for nearly two decades (either based on heuristic assumptions such at SNARKs or, more recently, on standard hardness assumptions), in all existing approaches security degrades exponentially with the number of recursive merges. In this work, we overcome this barrier. Assuming the Learning with Errors (LWE) assumption, we construct a mergeable SNARG for P that supports an unbounded polynomial number of recursive merges. The proof size grows only linearly with the depth of the merge tree, and is independent of its total size.

This paper systematically analyzes the security of the two-branch Unified Feistel Lai Massey (UFLM) structure with independent random round functions under chosen plaintext and chosen ciphertext attacks, focusing on its indistinguishability from a random permutation. UFLM uses an invertible linear layer represented as a $2 \times 2$ block matrix $\varphi$ with blocks $A_{11}, A_{12}, A_{21}, A_{22}$. Previously, Dai et al. proved that when $A_{12}$ is invertible, $4$-round UFLM achieves CCA security and resists up to $\mathcal{O}(2^{n/2})$ queries, where the UFLM input is $2n$ bits. Our work imposes no restriction on $A_{12}$. We determine the minimal number of rounds for UFLM to achieve CPA and CCA security, fully determined by the parameters $T(A_{12}^{\top}, A_{11}^{\top})$ and $T(A_{12}, A_{22})$. For UFLM with enough rounds to be secure, the query bound is primarily determined by the rank of $A_{12}$. For all UFLM with too few rounds to be secure, we present successful distinguishing attacks that require at most four queries. Our results rigorously show, for the first time, that when $A_{12}$ has full rank, UFLM requires the fewest rounds to achieve CPA and CCA security and attains the highest query bound. Nevertheless, when $A_{12}$ is not full rank, CPA and CCA security can still be achieved by increasing the number of rounds unless $T(A_{12}^{\top}, A_{11}^{\top}) = \infty$ or $T(A_{12}, A_{22}) = \infty$. At last, for involutory $\varphi$, we find UFLM achieves CPA and CCA security if and only if $A_{12}$ has full rank.

The advancement of quantum computing poses a serious threat to widely-used public-key cryptographic systems, leaving organizations with the challenge of identifying quantum-vulnerable (QV) executables within their systems and migrating to post-quantum cryptography (PQC). The prior work QED achieves high detection precision through angr-based static call graph analysis (P3), but its processing time of a few to over ten minutes per dataset and RAM consumption of up to 5 GB pose practical limitations on exhaustive screening in largescale environments. In this paper, we propose QED-Lite, a lightweight approximation tool that lightens the analysis stages that incur high computational overhead relative to their detection precision, replacing them with version-based PQC support determination of cryptographic libraries. QED-Lite introduces a newly built PQC risk classification database for 11 major cryptographic libraries and is implemented with a single dependency on pyelftools. Experimental results on the Network dataset show that QED-Lite achieves an execution time up to 855× faster (0.84 seconds) and reduces memory usage by 228× (22.9 MB) compared to QED, while maintaining a TPR of 100%. QED-Lite delivers practical value relative to its cost as a first-pass screening tool that is operationally viable in large-scale organizational environments.

In this note, we review the formulation of SNOVA in three different languages: the ring-equation form, the whipping form, and the tensor form. Based on this, we propose a reformulation of SNOVA and discuss the security analysis of the resulting reformulated scheme. As a conclusion, we find that this new framework allows for greater flexibility in parameter selection and enables us to obtain parameter sets that remain competitive. In particular, as shown in the appendix, parameter sets over odd characteristic $\mathbb{F}_{q}$ lead to smaller key sizes and may offer improved resistance against certain attacks. This makes parameter sets over odd characteristic $\mathbb{F}_{q}$ especially interesting from a practical perspective. We propose a number of parameter sets that have certificate sizes below one kilobyte.

In incentivized outsourced computation,an outsourcer hands a computation to multiple contractors, and in return expects the same computation output from each. The state-of-the-art proposals succeed in incentivizing all contractors for honest computation by setting this behavior as the unique Nash equilibrium of the system. Yet, they are either limited to the two-contractor case or the multi-contractor case without security proof against fully collaborating coalitions. Further, employing a smart contract for managing submissions from the contractors has been a non-trivial task due to the copy attack. In this work, we target this issue and propose a smart contract based multi-contractor incentivized outsourced computation protocol Delegate, which is provably secure against coalitions. We further mitigate the copy attack by a universally composable response submission protocol based on commitments, in contrast to previous solutions which only disincentivize it.

The study of coin-tossing protocols lies at the intersection of cryptography and game theory, where parties with potentially conflicting interests aim to jointly generate an unbiased random bit. Classical cryptographic results establish that strong fairness is achievable with an honest majority in the statistical setting, but impossible with a dishonest majority. In parallel, game-theoretic approaches [TCC 2018, Eurocrypt 2022 \& CRYPTO 2024] have demonstrated that weaker equilibrium-based fairness guarantees can sometimes circumvent cryptographic lower bounds, raising the question of whether such techniques can overcome impossibility in the statistical regime.

In this work, we answer this question negatively.

- We show that for $n$ parties and $t \geq n/2$ corruptions, there exists no statistically secure, game-theoretic coin-tossing protocol, even assuming broadcast and bounded round complexity—with the sole exception of the case $n=4$ where all but one party share the same preference. This complements known feasibility results for $t < n/2$, thereby completing the statistical feasibility landscape.

- We further consider the setting without broadcast. Here we prove that no computationally secure game-theoretic coin-tossing protocol exists for $t \geq n/3$ and polynomial-round complexity, except for the corner case $n=6$ where all but one party share the same preference.

To establish these results, we refine existing frameworks for game-theoretic fairness to capture both broadcast and point-to-point communication models.

Together, our results establish the boundaries of game-theoretic fairness in multi-party coin tossing: while it extends feasibility in the computational setting, it offers no advantage in the statistical setting once an honest majority is lost.

The Hamming Quasi-Cyclic (HQC) cryptosystem, recently selected by NIST for standardization, uses a concatenation of Reed-Muller (RM) and Reed-Solomon (RS) codes to ensure correct decryption. This work optimizes the underlying code and decoder with the goal of reducing ciphertext and public-key sizes. First, we propose a two-level generalized concatenated code (GCC), exploiting the observation that the inner RM code contains a repetition subcode. The repetition layer incurs a smaller inner failure probability and, therefore, admits a higher code rate than the RS code. Second, we develop a reliability-based decoding framework for the outer code. The inner decoder provides a reliability measure whose distribution, jointly with the decoding outcome, is bounded analytically. These bounds allow deriving conservative DFR guarantees for two erasure-assignment strategies (threshold-based and partition-based). Combining both contributions, we observe that public-key and ciphertext sizes can be reduced by up to 4.34%.

Secure multiparty computation (MPC) enables mutually distrustful parties to jointly compute over private data without revealing their inputs. While protocols in both synchronous and asynchronous settings have achieved impressive efficiency in either communication or round complexity, combining the two has remained challenging. Only recently, Abraham, Asharov, Patil, and Patra (Eurocrypt’23, Eurocrypt’24) achieved protocols that combine low communication complexity ($O((Cn + Dn^2 + n^4)\log n)$) with fast execution ($O(D)$ rounds) in both synchronous and asynchronous models, for circuits of size $C$ and depth $D$, in the perfect setting with optimal resilience. However, both protocols crucially assume advanced knowledge of the network type and are fragile under mismatched or varying network conditions.

The fragility of protocols under mismatched network assumptions highlights the need for network-agnostic MPC, where security and correctness are preserved in both synchronous and asynchronous settings. Yet, all known perfect network-agnostic protocols incur $\Omega(D+n)$ rounds and communication complexity in the order of $n^3$ or higher, far worse than their network-specific counterparts.

In this work, we present the first network-agnostic MPC protocol in the perfect security setting, achieving expected round complexity $O(D)$. Our protocol has expected communication complexity $O((Cn^2 + Dn^2 + n^4)\log n)$, improving on the state of the art by a factor of $n^3$ for small circuits and $n^2$ for large circuits in communication, in addition to an additive $O(n)$ improvement in round complexity. Our design departs from the structure of prior network-agnostic protocols and introduces several new technical ideas that enable both round and communication efficiency.

The Inner Product Extractor (IPE) of Impagliazzo, Levin, and Luby (STOC'89) takes a seed $h\in\mathbb{F}^\gamma$ and a source $x\in\{0,1\}^\gamma$ for some $\gamma\in\mathbb{N}$ and produces $\langle h,x\rangle$ with error $\varepsilon=\mathsf{SD}((\langle\mathcal{H},\mathcal{X}\rangle,\mathcal{H}),(\mathcal{Y},\mathcal{H}))$ such that $$ \varepsilon\le\frac{1}{2}\sqrt{|\mathbb{F}|^{\gamma}/2^{H_\infty(\mathcal{H})}}\,\,\sqrt{|\mathbb{F}|/2^{H_\infty(\mathcal{X})}} $$ where $\mathcal{Y}$ is the uniform distribution over $\mathbb{F}$, and $\mathcal{H}$ and $\mathcal{X}$ are the independent but possibly non-uniform distributions from which $h$ and $x$ are drawn, respectively. In other words, the IPE's error grows with the square root of seed bias, at most. This square root arises because prior works bound the squared error using the 2-universality of the IPE. The analysis requires an even power of the error, and the IPE is not $4$-universal.

Motivated by applications to multiparty computation, we revisit the problem of the IPE with biased seeds and prove far tighter bounds on the influence of seed bias by bypassing universal hashing. We first prove an Elevated General Leftover Hash Lemma, which yields an $n^{\text{th}}$ root bound for functions that are almost $n$-universal. Bounding number of inputs on which the IPE is not 4-universal yields $\varepsilon=\mathsf{SD}((\langle\mathcal{H},\mathcal{W}\rangle,\mathcal{H}),(\mathcal{Y},\mathcal{H}))$ where $$ \varepsilon\lesssim\frac{2.1}{2}\left(|\mathcal{F}|^\gamma/2^{H_\infty(\mathcal{H})}\right)^{\frac14} \sqrt{|\mathbb{F}|/2^{H_\infty(\mathcal{W})}} $$ for any oblivious bit-fixing source $\mathcal{W}$ with $2^{0.585 H_\infty(\mathcal{W})} \le |\mathbb{F}| \le 2^{H_\infty(\mathcal{W})}$. Next, we use matroid theory to directly analyze the $n$-way multicollision probability of the IPE, yielding an asymptotic bound for any even $n$. For $n\ge4$, $0 < \epsilon \le 0.83/(n - 2)$, and $|\mathbb{F}| \le 2^{(1 - \epsilon)\cdot H_\infty(\mathcal{W})}$, as $|\mathbb{F}|\to\infty$, $$ \varepsilon \le\frac{(n - 1)}{2}\left({|\mathcal{F}|}^\gamma/2^{H_\infty(\mathcal{H})}\right)^{\frac1n} \sqrt{\vphantom{/}2^{-\epsilon\cdot H_\infty(\mathcal{W})}}\,\, (1 + o(1)). $$ Computing a \emph{concrete} version of this bound requires time exponential in $n$. We compute concrete $\{4,6,8\}^{\text{th}}$-root bounds and demonstrate that no one choice of $n$ is optimal. Finally, we introduce a new class of seed-adaptive oblivious bit-fixing sources, extend our results to such sources, and use this extension to improve recent constructions of actively-secure oblivious linear evaluation in the oblivious-transfer hybrid model.

Secret Sharing schemes allows a dealer to distribute $n$ shares $s_1,\ldots, s_n$ of a secret $s$ so that any $t$ shares suffice to reconstruct the secret, while any $t-1$ shares reveal no information about $s$. In fact, schemes such as Shamir Secret Sharing satisfy a stronger guarantee called $(t\!-\!1)$-perfect privacy, meaning that for any subset $S \subseteq [n]$ with $|S| \le t-1$, the joint distribution $(s_i)_{i \in S}$ is uniformly distributed over its domain. This strong guarantee is essential for applications such as fuzzy password-authenticated key exchange (fPAKE) and conditional encryption --- a recent cryptographic primitive introduced to enable secure personalized password typo correction. Unfortunately, Shamir secret sharing is not robust: corrupted shares can prevent correct reconstruction or cause reconstruction of an incorrect secret. Existing robust secret sharing schemes address this issue but necessarily sacrifice perfect privacy. We introduce and construct \emph{Random Robust Secret Sharing with Perfect Privacy} (RRSS), a new notion that preserves $(t\!-\!1)$-perfect privacy while providing robustness against random share corruptions. In our schemes, the secret is recovered with high probability even if an arbitrary subset of up to $n-t$ shares is independently corrupted at random. We demonstrate the utility of RRSS through two applications. First, we present the first practically efficient fPAKE construction that tolerates Hamming errors. Second, we obtain the first efficient conditional encryption scheme for arbitrary Hamming distances, improving upon prior work that achieved efficiency only for constant distances. We implement both constructions and empirically demonstrate their practicality.

A recent paper by Calderini et al. investigates the use of a CCZ transformation to mask the quadratic central map in a multivariate scheme, providing an instance leading to a system of degree four. A following paper by Caminata et al. presents two methods to reduce the masked system back to a quadratic system. In this work we further study the method based on the quadratic relations between input and output of the masked function, generalizing it and applying to any CCZ transformation (of any quadratic map). Moreover, we study how the existence of these quadratic relations can be used to study whether a function can be CCZ equivalent to a quadratic map and, more generally, to study whether two functions can be CCZ equivalent. In fact, this analysis gives us necessary conditions that can be checked also in relatively large dimensions.