[continued from previous message]

This work introduces homomorphic secret sharing (HSS) with succinct share size. In HSS, private inputs are shared between parties, who can then homomorphically evaluate a function on their shares, obtaining a share of the function output. In succinct HSS,
a portion of the inputs can be distributed using shares whose size is sublinear in the number of such inputs. The parties can then locally evaluate a function $f$ on the shares, with the restriction that $f$ must be linear in the succinctly shared
inputs.

We construct succinct, two-party HSS for branching programs, based on either the decisional composite residuosity assumption, a DDH-like assumption in class groups, or learning with errors with a superpolynomial modulus-to-noise ratio. We then give
several applications of succinct HSS, which were only previously known using fully homomorphic encryption, or stronger tools:

- Succinct vector oblivious linear evaluation (VOLE): Two parties can obtain secret shares of a long, arbitrary vector $\vec x$, multiplied by a scalar $\Delta$, with communication sublinear in the size of the vector.
- Batch, multi-party distributed point functions: A protocol for distributing a batch of secret, random point functions among $N$ parties, for any polynomial $N$, with communication sublinear in the number of DPFs.
- Sublinear MPC for any number of parties: Two new constructions of MPC with sublinear communication complexity, with $N$ parties for any polynomial $N$: (1) For general layered Boolean circuits of size $s$, with communication $O(N s/\log\log s)$, and (2)
For layered, sufficiently wide Boolean circuits, with communication $O(N s/\log s)$.



## 2024/815

* Title: Faster verifications and smaller signatures: Trade-offs for ALTEQ using rejections
* Authors: Arnaud Sipasseuth
* [Permalink](https://eprint.iacr.org/2024/815)
* [Download](https://eprint.iacr.org/2024/815.pdf)

### Abstract

In this paper, we introduce a new probability function parameter in the instantiations of the Goldreich-Micali-Wigderson with Fiat-Shamir and unbalanced challenges used in ALTEQ, a recent NIST PQC candidate in the call for additional signatures. This
probability set at 100% does not bring any changes in the scheme, but modifies the public challenge generation process when below 100%, by injecting potential rejections in otherwise completely valid inputs.
From a theoretical point of view, this does not improve the asymptotical hardness of the scheme and negatively affects the efficiency of the signatory, and might itself seem trivial. However, from a practical point of view, implementation-wise and
performance-wise, this triviality allows an extra degree of freedom in optimizing parameters, as the heuristic security level is also increased against forgers: previously valid combinations now can be deemed invalid. This allows us to make trade-offs to
reduce the computational load in verifiers, accelerating verifications, marginally reduce the signature size, at the cost of making signatures slower and unlikely to be constant-time.
In particular, this extra degree of freedom allows to make implementation choices that enable smoother and faster executions of the aforementioned protocols, especially in the context of parallelization using vectorized instructions. We also demonstrate
the usefulness of our proposal to ALTEQ for other options, when slowing down the signing process is not an issue: significantly smaller signatures but longer verifications, or lower public key sizes.
The ideas presented apply to any primitive, and can be used beyond ALTEQ.



## 2024/816

* Title: Zero-knowledge IOPs Approaching Witness Length
* Authors: Noga Ron-Zewi, Mor Weiss
* [Permalink](https://eprint.iacr.org/2024/816)
* [Download](https://eprint.iacr.org/2024/816.pdf)

### Abstract

Interactive Oracle Proofs (IOPs) allow a probabilistic verifier interacting with a prover to verify the validity of an NP statement while reading only few bits from the prover messages. IOPs generalize standard Probabilistically-Checkable Proofs (PCPs)
to the interactive setting, and in the few years since their introduction have already exhibited major improvements in main parameters of interest (such as the proof length and prover and verifier running times), which in turn led to significant
improvements in constructions of succinct arguments. Zero-Knowledge (ZK) IOPs additionally guarantee that the view of any query-bounded (possibly malicious) verifier can be efficiently simulated. ZK-IOPs are the main building block of succinct ZK
arguments which use the underlying cryptographic object (e.g., a collision-resistant hash function) as a black box.

In this work, we construct the first ZK-IOPs approaching the witness length for a natural NP problem. More specifically, we design constant-query and constant-round IOPs for 3SAT in which the total communication is $(1+\gamma)m$, where $m$ is the number
of variables and $\gamma>0$ is an arbitrarily small constant, and ZK holds against verifiers querying $m^\beta$ bits from the prover's messages, for a constant $\beta>0$. This gives a ZK variant of a recent result of Ron-Zewi and Rothblum (FOCS `20), who
construct (non-ZK) IOPs approaching the witness length for a large class of NP languages. Previous constructions of ZK-IOPs incurred an (unspecified) large constant multiplicative overhead in the proof length, even when restricting to ZK against the
honest verifier.

We obtain our ZK-IOPs by improving the two main building blocks underlying most ZK-IOP constructions, namely ZK codes and ZK-IOPs for sumcheck. More specifically, we give the first ZK-IOPs for sumcheck that achieve both sublinear communication for
sumchecking a general tensor code, and a ZK guarantee. We also show a strong ZK preservation property for tensors of ZK codes, which extends a recent result of Bootle, Chiesa, and Liu (EC `22). Given the central role of these objects in designing ZK-IOPs,
these results might be of independent interest.



## 2024/817

* Title: DVA: Dangerous Variations of ALTEQ
* Authors: Arnaud Sipasseuth
* [Permalink](https://eprint.iacr.org/2024/817)
* [Download](https://eprint.iacr.org/2024/817.pdf)

### Abstract

In this paper, we present three types of variations of the ALTEQ cryptosystem, a recent submission to the NIST's additional call for signatures. We name these Dangerous Variations of ALTEQ (DVA), as there is always a certain danger in stepping out of
usual constructions, although we attempt to maintain heuristic security.
First, we present DVA-GG (Graph Generalization), that can be seen as a more abstract point-of-view on the operations done in ALTEQ and encourages more research on the algebraic variants. In particular, we show this approach can lead to a patch counter to
Beullens' recent seed collision attack on ALTEQ that only depends on the primitive, and showcase some fancy usages of the primitive for experimental protocols.
Second, we present DVA-PC (Precomputations) which is ``likely'' as secure as ALTEQ in the random oracle model, and allow to drastically reduce the intermediate memory requirements within both the signature and verification process through an easily
parallelizable extra operation. In particular, this facilitates precomputation variants with online phases that only depends on the complexity of basic matrix operations. We can then choose between either a tiny offline memory per signature, or get one
of the fastest online signing speed for post-quantum cryptography.
Third, we present DVA-DM (Distinct Matrices), some cryptanalytic targets that deviates from ALTEQ's original algebraic structure. Those structures can serve as plain computational acceleration or just compress data sizes,
and provide good options to motivate the study of specialized
cryptanalysis for ALTEQ: if those are safe, then ALTEQ gain safe variants, and otherwise, we gain further understanding of the problems.
In particular, the ideas can be applied beyond ALTEQ and beyond, and hopefully extend to MEDS, LESS, and group-action-based cryptography.



## 2024/818

* Title: The Brave New World of Global Generic Groups and UC-Secure Zero-Overhead SNARKs
* Authors: Jan Bobolz, Pooya Farshim, Markulf Kohlweiss, Akira Takahashi
* [Permalink](https://eprint.iacr.org/2024/818)
* [Download](https://eprint.iacr.org/2024/818.pdf)

### Abstract

The universal composability (UC) model provides strong security guarantees for protocols used in arbitrary contexts. While these guarantees are highly desirable, in practice, schemes with a standalone proof of security, such as the Groth16 proof system,
are preferred. This is because UC security typically comes with undesirable overhead, sometimes making UC-secure schemes significantly less efficient than their standalone counterparts. We establish the UC security of Groth16 without any significant
overhead. In the spirit of global random oracles, we design a global (restricted) observable generic group functionality that models a natural notion of observability: computations that trace back to group elements derived from generators of other
sessions are observable. This notion turns out to be surprisingly subtle to formalize. We provide a general framework for proving protocols secure in the presence of global generic groups, which we then apply to Groth16.



## 2024/819

* Title: A new stand-alone MAC construct called SMAC
* Authors: Dachao Wang, Alexander Maximov, Patrik Ekdahl, Thomas Johansson
* [Permalink](https://eprint.iacr.org/2024/819)
* [Download](https://eprint.iacr.org/2024/819.pdf)

### Abstract

In this paper, we present a new efficient stand-alone MAC construct based on processing using the FSM part of the stream cipher family SNOW, which in turn uses the AES round function. It offers a combination of very high speed in software and hardware
with a truncatable tag. Two concrete versions of SMAC are proposed with different security levels, although other use cases are also possible. For example, SMAC can be combined with an external ciphering engine in AEAD mode. Every design choice is
justified and supported by the results of our analysis and simulations. A novelty of the proposal is that it meets future performance requirements but is still not directly vulnerable to attacks using repeated nonce when the tag size is short, as is the
case for other very fast MACs (MACs based on polynomial hashing). This can be an important aspect in practical applications.



## 2024/820

* Title: Rate-1 Arithmetic Garbling from Homomorphic Secret-Sharing
* Authors: Pierre Meyer, Claudio Orlandi, Lawrence Roy, Peter Scholl
* [Permalink](https://eprint.iacr.org/2024/820)
* [Download](https://eprint.iacr.org/2024/820.pdf)

### Abstract

We present a new approach to garbling arithmetic circuits using techniques from homomorphic secret sharing, obtaining constructions with high rate that support free addition gates. In particular, we build upon non-interactive protocols for computing
distributed discrete logarithms in groups with an easy discrete-log subgroup, further demonstrating the versatility of tools from homomorphic secret sharing. Relying on distributed discrete log for the Damgård-Jurik cryptosystem (Roy and Singh, Crypto `
21), whose security follows from the decisional composite residuosity assumption (DCR), we get the following main results:

[**Two ciphertexts per multiplication, from IND-CPA security of Damgård-Jurik.**]
Assuming the Damgård-Jurik cryptosystem is semantically secure (which follows from DCR), there is a garbling scheme for circuits with $B$-bounded integer arithmetic using only two ciphertexts per multiplication. The total bit-size of the resulting
garbled circuit is:
$$(n + 2s_\times+2D_\times)\cdot (\zeta + 1) \cdot \log N$$
where $n$ is the number of inputs, $s_\times$ is the number of multiplications, $D_\times$ is the multiplicative depth of the circuit, $N$ is an RSA modulus and $N^{\zeta-1}$ is a rough bound on the magnitude of wire values in the computation.

[**One ciphertext per multiplication, from KDM security of Damgård-Jurik.**] Assuming the Damgård-Jurik encryption scheme remains secure given encryption of the key and its inverse, the construction achieves rate-$1$. The total bit-size of the resulting garbled circuit is:
$$(n + s_\times + 1) \cdot (\zeta + 1) \cdot \log N$$
where the parameters are as above, except $N^{\zeta-2}$ is the magnitude bound.

As a side result, we show that our scheme based on IND-CPA security achieves rate $3/5$ for levelled circuits.



## 2024/821

* Title: A General Framework for Lattice-Based ABE Using Evasive Inner-Product Functional Encryption
* Authors: Yao-Ching Hsieh, Huijia Lin, Ji Luo
* [Permalink](https://eprint.iacr.org/2024/821)
* [Download](https://eprint.iacr.org/2024/821.pdf)

### Abstract

We present a general framework for constructing attribute-based encryption (ABE) schemes for arbitrary function class based on lattices from two ingredients, i) a noisy linear secret sharing scheme for the class and ii) a new type of inner-product
functional encryption (IPFE) scheme, termed *evasive* IPFE, which we introduce in this work. We propose lattice-based evasive IPFE schemes and establish their security under simple conditions based on variants of evasive learning with errors (LWE)
assumption recently proposed by Wee [EUROCRYPT ’22] and Tsabary [CRYPTO ’22].

Our general framework is modular and conceptually simple, reducing the task of constructing ABE to that of constructing noisy linear secret sharing schemes, a more lightweight primitive. The versatility of our framework is demonstrated by three new ABE
schemes based on variants of the evasive LWE assumption.

- We obtain two ciphertext-policy ABE schemes for all polynomial-size circuits with a predetermined depth bound. One of these schemes has *succinct* ciphertexts and secret keys, of size polynomial in the depth bound, rather than the circuit size. This
eliminates the need for tensor LWE, another new assumption, from the previous state-of-the-art construction by Wee [EUROCRYPT ’22].

- We develop ciphertext-policy and key-policy ABE schemes for deterministic finite automata (DFA) and logspace Turing machines ($\mathsf{L}$). They are the first lattice-based public-key ABE schemes supporting uniform models of computation. Previous
lattice-based schemes for uniform computation were limited to the secret-key setting or offered only weaker security against bounded collusion.

Lastly, the new primitive of evasive IPFE serves as the lattice-based counterpart of pairing-based IPFE, enabling the application of techniques developed in pairing-based ABE constructions to lattice-based constructions. We believe it is of independent
interest and may find other applications.



## 2024/822

* Title: Early Stopping Byzantine Agreement in $(1+\epsilon)\cdot f$ Rounds
* Authors: Fatima Elsheimy, Julian Loss, Charalampos Papamanthou
* [Permalink](https://eprint.iacr.org/2024/822)
* [Download](https://eprint.iacr.org/2024/822.pdf)

### Abstract

In this paper, we present two early stopping Byzantine agreement protocols in the authenticated setting against a corrupt minority $t < n/2$, where $t$ represents the maximum number of malicious parties. Early stopping protocols ensure termination within
a number of rounds determined solely by the actual number of malicious nodes $f$ present during execution, irrespective of $t$.

Our first protocol is deterministic and ensures early stopping termination in $ (d+5) \cdot (\lfloor f/d \rfloor +3)$ rounds, where $d$ is a fixed constant. For example, for all $d\ge 6$, our protocol runs in at most $(1+\epsilon )\cdot f$ rounds (where $
0<\epsilon<1$), improving (for large $f$) upon the best previous early stopping deterministic broadcast protocol by Perry and Toueg~\cite{Perry}, which terminates in $min(2f+4,2t+2)$ rounds. Additionally, our second protocol is randomized, ensuring
termination in an expected constant number of rounds and achieving early stopping in $(d+9) \cdot (\lfloor f/d \rfloor +2)$ rounds in the worst case. This marks a significant improvement over a similar result by Goldreich and Petrank[GOLDREICH1990],
which always requires an expected constant number of rounds and $O(t)$ rounds in the worst case, i.e., does not have the early stopping property.



## 2024/823

* Title: Batched Distributed Point Function from Sparse LPN and Homomorphic Secret Sharing
* Authors: Lucas Piske, Jaspal Singh, Ni Trieu
* [Permalink](https://eprint.iacr.org/2024/823)
* [Download](https://eprint.iacr.org/2024/823.pdf)

### Abstract

A function secret sharing (FSS) scheme ($\mathsf{gen},\mathsf{eval}$) for a class of programs $\mathcal{F}$ allows a dealer to secret share any function $f \in \mathcal{F}$, such that each function share hides the function, and the shares can be used to
non-interactively compute additive shares of $f(x)$ for any input $x$. All FSS related applications often requires the dealer to generate and share secret sharings for a batch of functions.
We initiate the study of batched function secret sharing - where the objective is to secret share a set of functions from the class $\mathcal{F}$ while minimizing the size of the collection of FSS keys.

We use standard homomorphic secret sharing (HSS) schemes, variant of the Learning with Parity Noise assumption and the Quadratic Residuosity assumption to construct batched FSS schemes for point functions with single-bit and multi-bit output. Our scheme
is asymptotically superior than naively batching state of the art FSS schemes for point functions. Concretely our batch key sizes are smaller by a factor of $3-80\times$ as batch size is increased from $2^{13}$ to $2^{19}$. Although our protocol relies
on public key operations, it exhibits inefficiency in a LAN setting. However, it demonstrates up to a 120-fold improvement in a WAN setting with slow network bandwidth.

As a building block in our protocols, we introduce a new HSS ciphertext compression algorithm, that can decompress a short compressed ciphertext to give low noise ciphertexts of array of input message bits. This primitive might be of independent interest
for other HSS related applications.



## 2024/824

* Title: Improved Meet-LWE Attack via Ternary Trees
* Authors: Eunmin Lee, Joohee Lee, Yuntao Wang
* [Permalink](https://eprint.iacr.org/2024/824)
* [Download](https://eprint.iacr.org/2024/824.pdf)

### Abstract

The Learning with Errors (LWE) problem with its variants over structured lattices has been widely exploited in efficient post-quantum cryptosystems. Recently, May suggests the Meet-LWE attack, which poses a significant advancement in the line of work on
the Meet-in-the-Middle approach to analyze LWE with ternary secrets.

In this work, we generalize and extend the idea of Meet-LWE by introducing ternary trees, which result in diverse representations of the secrets. More precisely, we split the secrets into three pieces with the same dimension and expand them into a
ternary tree to leverage the increased representations to improve the overall attack complexity. We carefully analyze and optimize the time and memory costs of our attack algorithm exploiting ternary trees, and compare them to those of the Meet-LWE
attack. With asymptotic and non-asymptotic comparisons, we observe that our attack provides improved estimations for all parameter settings, including those of the practical post-quantum schemes, compared to the Meet-LWE attack. We also evaluate the
security of the Round 2 candidates of the KpqC competition which aims to standardize post-quantum public key cryptosystems in the Republic of Korea, and report that the estimated complexities for our attack applied to SMAUG-T are lower than the claimed
for some of the recommended parameters.

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