[continued from previous message]

We study general $(t,c)$-ramp secret sharing schemes where the number of parties c needed to reconstruct the secret may be larger than $t$. We present a ramp secret sharing scheme whose reconstruction time is 2-7.8x faster than prior constructions
suitable against adversaries that adaptively corrupt parties. For $t = 2^{20}$, our new protocol has reconstruction time of 5 seconds whereas prior work requires nearly half a minute. We see improvements starting from as small as $t = 256$. Furthermore,
we obtain correctness threshold as small as $c \ge 1.05t$. To obtain our construction, we first improve the secret sharing frameworks by Cramer et al. (EUROCRYPT'15) and Applebaum et al. (CRYPTO'23) from erasure codes. Our new framework obtains secret
sharing schemes that may be used against adversaries with adaptive corruptions while requiring only weaker correctness guarantees from the underlying erasure code with a distributed generation property. Furthermore, our new framework also maintains the
linear homomorphism of the prior works. Afterwards, we present a concretely efficient erasure code from random band matrices that satisfies the distributed generation property.

We show that our secret sharing scheme can improve many real-world applications. In secure aggregation protocols for federated learning, we obtain up to 22% reductions in computational cost by replacing Shamir's scheme with our construction. We extend
our protocol to obtain a verifiable ramp secret sharing scheme where each party can verify the consistency of the shares. Our new verifiable ramp secret sharing has 8.2-25.2x faster sharing and 2.7-23.2x faster reconstruction time compared to prior works.
Finally, we present an improved distributed verifiable random function that may be used for decentralized randomness beacons.



## 2024/1046

* Title: The Sum-Check Protocol over Fields of Small Characteristic
* Authors: Suyash Bagad, Yuval Domb, Justin Thaler
* [Permalink](https://eprint.iacr.org/2024/1046)
* [Download](https://eprint.iacr.org/2024/1046.pdf)

### Abstract

The sum-check protocol of Lund, Fortnow, Karloff, and Nisan underlies SNARKs with the fastest known prover. In many of its applications, the prover can be implemented with a number of field operations that is linear in the number, $n$, of terms being
summed.

We describe an optimized prover implementation when the protocol is applied over an extension field of a much smaller base field. The rough idea is to keep most of the prover's multiplications over the base field, at the cost of performing more $\textit{
total}$ field multiplications. When the sum-check protocol is applied to a product of polynomials that all output values in the base field, our algorithm reduces the number of extension field operations by multiple orders of magnitude. In other settings,
our improvements are more modest but nonetheless meaningful.

In SNARK design, the sum-check protocol is often combined with a polynomial commitment scheme, which are growing faster, especially when the values being committed are small. These improved commitment schemes are likely to render the sum-check prover the
overall bottleneck, which our results help to mitigate.



## 2024/1047

* Title: Improved Multi-Party Fixed-Point Multiplication
* Authors: Saikrishna Badrinarayanan, Eysa Lee, Peihan Miao, Peter Rindal
* [Permalink](https://eprint.iacr.org/2024/1047)
* [Download](https://eprint.iacr.org/2024/1047.pdf)

### Abstract

Machine learning is widely used for a range of applications and is increasingly offered as a service by major technology companies. However, the required massive data collection raises privacy concerns during both training and inference. Privacy-
preserving machine learning aims to solve this problem. In this setting, a collection of servers secret share their data and use secure multi-party computation to train and evaluate models on the joint data. All prior work focused on the scenario where
the number of servers is two or three. In this work, we study the problem where there are $N \geq 3$ servers amongst whom the data is secret shared.

A key component of machine learning algorithms is to perform fixed-point multiplication with truncation of secret shared decimal values. In this work, we design new protocols for multi-party secure fixed-point multiplication where each of the $N$ parties
have one share each of the two values to be multiplied and receive one share of the product at the end of the protocol. We consider three forms of secret sharing - replicated, Shamir, and additive, and design an efficient protocol secure in the presence
of a semi-honest adversary for each of the forms. Our protocols are more communication efficient than all prior work on performing multi-party fixed-point multiplication. Additionally, for replicated secret sharing, we design another efficient protocol
that is secure in the presence of a malicious adversary. Finally, we leverage our fixed-point multiplication protocols to design secure multi-party computation (MPC) protocols for arbitrary arithmetic circuits that have addition and fixed-point
multiplication with truncation gates. All our protocols are proven secure using a standard simulation based security definition. Our protocols for replicated and Shamir sharing work in the presence of an honest majority of parties while the one for
additive sharing can tolerate a dishonest majority as well.



## 2024/1048

* Title: Distributional Secure Merge
* Authors: Gayathri Garimella, Srinivasan Raghuramam, Peter Rindal
* [Permalink](https://eprint.iacr.org/2024/1048)
* [Download](https://eprint.iacr.org/2024/1048.pdf)

### Abstract

Secure merge refers to the problem of merging two sorted lists. The problem appears in different settings where each list is held by one of two parties, or the lists are themselves shared among two or more parties. The output of a secure merge protocol
is secret shared. Each variant of the problem offers many useful applications.

The difficulty in designing secure merge protocols vis-a-vis insecure merge protocols (which work in linear time with a single pass over the lists) has to do with operations having to be oblivious or data-independent. In particular, the protocol cannot
leak the positions of items of each list in the final merged list. On account of this, sorting-based secure merge protocols have been a common solution to the problem. However, as they introduce (poly)logarithmic overheads, there has been active
investigation into the task of building (near) linear time secure merge protocols. Most recently, Hemenway et al. put forth a protocol for secure merge that does achieve linear communication and computation and a round complexity of $O({\log\log n})$,
where $n$ is the length of the lists being merged. While this shows the feasibility of a linear time secure merge, it still leaves room for the design of a concretely efficient linear time secure merge.

In this work, we consider a relaxation of the problem where the lists are uniformly random. We show a secure merge protocol for uniformly random lists that achieves $O({n\log\log n})$, i.e., near linear communication and computation and a round
complexity of $O({\log\log n})$, where $n$ is the length of the lists being merged. Our protocol design is general and can be instantiated in a variety of settings so long as the building blocks (basic ones such as comparisons and shuffles) can be
realized in said settings. Although we do not achieve the same asymptotic guarantees as Hemenway et al., our work is concretely efficient. We implement our protocol and compare it to the state of the art sorting protocols and demonstrate an order of
magnitude improvement in running times and communication for lists of size of $2^{20}$.

We also extend our protocol to work for lists sampled from arbitrary distributions. In particular, when the lists are (close to) identically distributed, we achieve the same efficiency as uniform lists. This immediately improve the performance of many
crucial applications including PSI & Secure Join, thus illustrating the significance and applicability of our protocol in practice.



## 2024/1049

* Title: KyberSlash: Exploiting secret-dependent division timings in Kyber implementations
* Authors: Daniel J. Bernstein, Karthikeyan Bhargavan, Shivam Bhasin, Anupam Chattopadhyay, Tee Kiah Chia, Matthias J. Kannwischer, Franziskus Kiefer, Thales Paiva, Prasanna Ravi, Goutam Tamvada
* [Permalink](https://eprint.iacr.org/2024/1049)
* [Download](https://eprint.iacr.org/2024/1049.pdf)

### Abstract

This paper presents KyberSlash1 and KyberSlash2 – two timing vulnerabilities in several implementations (including the official reference code) of the Kyber Post-Quantum Key Encapsulation Mechanism, currently undergoing standardization as ML-KEM. We
demonstrate the exploitability of both KyberSlash1 and KyberSlash2 on two popular platforms: the Raspberry Pi 2 (Arm Cortex-A7) and the Arm Cortex-M4 microprocessor. Kyber secret keys are reliably recovered within minutes for KyberSlash2 and a few hours
for KyberSlash1.
We responsibly disclosed these vulnerabilities to maintainers of various libraries and they have swiftly been patched. We present two approaches for detecting and avoiding similar vulnerabilities. First, we patch the dynamic analysis tool Valgrind to
allow detection of variable-time instructions operating on secret data, and apply it to more than 1000 implementations of cryptographic primitives in SUPERCOP. We report multiple findings. Second, we propose a more rigid approach to guarantee the absence
of variable-time instructions in cryptographic software using formal methods.



## 2024/1050

* Title: On Sequential Functions and Fine-Grained Cryptography
* Authors: Jiaxin Guan, Hart Montgomery
* [Permalink](https://eprint.iacr.org/2024/1050)
* [Download](https://eprint.iacr.org/2024/1050.pdf)

### Abstract

A sequential function is, informally speaking, a function $f$ for which a massively parallel adversary cannot compute "substantially" faster than an honest user with limited parallel computation power. Sequential functions form the backbone of many
primitives that are extensively used in blockchains such as verifiable delay functions (VDFs) and time-lock puzzles. Despite this widespread practical use, there has been little work studying the complexity or theory of sequential functions.

Our main result is a black-box oracle separation between sequential functions and one-way functions: in particular, we show the existence of an oracle $\mathcal{O}$ that implies a sequential function but not a one-way function. This seems surprising
since sequential functions are typically constructed from very strong assumptions that imply one-way functions and also since time-lock puzzles are known to imply one-way functions (Bitansky et al., ITCS '16).

We continue our exploration of the theory of sequential functions. We show that, informally speaking, the decisional, worst-case variant of a certain class of sequential function called a continuous iterative sequential function (CISF) is PSPACE-complete.
A CISF is, in a nutshell, a sequential function $f$ that can be written in the form $f \left(k, x \right) = g^{k} \left(x \right)$ for some function $g$ where $k$ is an input determining the number of "rounds" the function is evaluated. We then show
that more general forms of sequential functions are not contained in PSPACE relative to a random oracle.

Given these results, we then ask if it is possible to build any interesting cryptographic primitives from sequential functions that are not one-way. It turns out that even if we assume just the existence of a CISF that is not one-way, we can build
certain "fine-grained" cryptographic primitives where security is defined similarly to traditional primitives with the exception that it is only guaranteed for some (generally polynomial) amount of time. In particular, we show how to build "fine-grained"
symmetric key encryption and "fine-grained" MACs from a CISF. We also show how to build fine-grained public-key encryption from a VDF with a few extra natural properties and indistinguishability obfucsation (iO) for null circuits. We do not assume one-
way functions. Finally, we define a primitive that we call a commutative sequential function - essentially a sequential function that can be computed in sequence to get the same output in two different ways - and show that it implies fine-grained key
exchange.



## 2024/1051

* Title: Adaptor Signatures: New Security Definition and A Generic Construction for NP Relations
* Authors: Xiangyu Liu, Tzannetos Ioannis, Vassilis Zikas
* [Permalink](https://eprint.iacr.org/2024/1051)
* [Download](https://eprint.iacr.org/2024/1051.pdf)

### Abstract

An adaptor signatures (AS) scheme is an extension of digital signatures that allows the signer to generate a pre-signature for an instance of a hard relation. This pre-signature can later be adapted to a full signature with a corresponding witness.
Meanwhile, the signer can extract a witness from both the pre-signature and the signature. AS have recently garnered more attention due to its scalability and interoperability. Dai et al. [INDOCRYPT 2022] proved that AS can be constructed for any NP
relation using a generic construction. However, their construction has a shortcoming: the associated witness is exposed by the adapted signature. This flaw poses limits the applications of AS, even in its motivating setting, i.e., blockchain, where the
adapted signature is typically uploaded to the blockchain and is public to everyone.

To address this issue, in this work we augment the security definition of AS by a natural property which we call witness hiding. We then prove the existence of AS for any NP relation, assuming the existence of one-way functions. Concretely, we propose a
generic construction of witness-hiding AS from signatures and a weak variant of trapdoor commitments, which we term trapdoor commitments with a specific adaptable message. We instantiate the latter based on the Hamiltonian cycle problem. Since the
Hamiltonian cycle problem is NP-complete, we can obtain witness hiding adaptor signatures for any NP relation.



## 2024/1052

* Title: A New Fine Tuning Method for FHEW/TFHE Bootstrapping with IND-CPAD Security
* Authors: Deokhwa Hong, Young-Sik Kim, Yongwoo Lee, Eunyoung Seo
* [Permalink](https://eprint.iacr.org/2024/1052)
* [Download](https://eprint.iacr.org/2024/1052.pdf)

### Abstract

Fully homomorphic encryption (FHE) schemes enable computations on encrypted data, making them a crucial component of privacy-enhancing technologies.
Ducas and Micciancio introduced FHEW (Eurocrypt '15), and Chillotti et al. improved it in TFHE (Asiacrypt '16), both of which provide homomorphic binary (or larger) gate evaluations with fast latency due to their small parameters.
However, their evaluation failure probability is highly sensitive to parameter selection, resulting in a limited set of viable parameters and a trade-off between failure probability and runtime.

Recently, Cheon et al. proposed a key recovery attack against FHEW/TFHE schemes based on a new security model for FHE, called IND-CPA-D security, which was first introduced by Li and Micciancio (Eurocrypt '21).
To prevent this attack, it is necessary to make the failure probability negligible (e.g., $2^{-128}$).
However, due to limited choice parameters, it is forced to use a parameter set with unnecessarily low failure probabilities than needed, causing inefficiencies in runtime.

We propose a new bootstrapping method for FHEW/TFHE, providing a precise balance between runtime and failure probability, and easy to implement.
The proposed methods enable the selection of parameter sets that achieve negligible failure probabilities for each desired security level while optimizing runtime.



## 2024/1053

* Title: Stochastic Secret Sharing with $1$-Bit Shares and Applications to MPC * Authors: Benny Applebaum, Eliran Kachlon
* [Permalink](https://eprint.iacr.org/2024/1053)
* [Download](https://eprint.iacr.org/2024/1053.pdf)

### Abstract

The problem of minimizing the share size of threshold secret-sharing schemes is a basic research question that has been extensively studied. Ideally, one strives for schemes in which the share size equals the secret size. While this is achievable for
large secrets (Shamir, CACM '79), no similar solutions are known for the case of binary, single-bit secrets. Current approaches often rely on so-called ramp secret sharing that achieves a constant share size at the expense of a slight gap between the
privacy and the correctness thresholds. In the case of single-bit shares, this leads to a large gap which is typically unacceptable. The possibility of a meaningful notion of secret sharing scheme with 1-bit shares and almost optimal threshold has been
left wide open. Of special interest is the case of threshold 0.5, which is motivated by information-theoretic honest-majority secure multiparty computation (MPC).

In this work, we present a new stochastic model for secret-sharing where each party is corrupted by the adversary with probability $p$, independently of the other parties, and correctness and privacy are required to hold with high probability over the
choice of the corrupt parties. We present new secret sharing schemes with single-bit shares that tolerate any constant corruption probability $p<0.5$. Our construction is based on a novel connection between such stochastic secret-sharing schemes and
error-correcting codes that achieve capacity over the binary erasure channel.

Our schemes are linear and multiplicative. We demonstrate the usefulness of the model by using our new schemes to construct MPC protocols with security against an adversary that passively corrupts an arbitrary subset of $0.499n$ of the parties, where the
online communication per party consists of a single bit per AND gate and zero communication per XOR gate. Unlike competing approaches for communication-efficient MPC, our solution is applicable even in a real-time model in which the parties should
compute a Boolean circuit whose gates arrive in real-time, one at a time, and are not known in advance.



## 2024/1054

* Title: Optimized Computation of the Jacobi Symbol
* Authors: Jonas Lindstrøm, Kostas Kryptos Chalkias
* [Permalink](https://eprint.iacr.org/2024/1054)
* [Download](https://eprint.iacr.org/2024/1054.pdf)

### Abstract

The Jacobi Symbol is an essential primitive in cryptographic applications such as primality testing, integer factorization, and various encryption schemes. By exploring the interdependencies among modular reductions within the algorithmic loop, we have
developed a refined method that significantly enhances computational efficiency. Our optimized algorithm, implemented in the Rust language, achieves a performance increase of 72% over conventional textbook methods and is twice as fast as the previously
fastest known Rust implementation.

This work not only provides a detailed analysis of the optimizations but also includes comprehensive benchmark comparisons to illustrate the practical advantages of our methods. Our algorithm is publicly available under an open-source license, promoting
further research on foundational cryptographic optimizations.



## 2024/1055

* Title: Enhancing Local Verification: Aggregate and Multi-Signature Schemes
* Authors: Ahmet Ramazan Ağırtaş, Neslihan Yaman Gökce, Oğuz Yayla
* [Permalink](https://eprint.iacr.org/2024/1055)
* [Download](https://eprint.iacr.org/2024/1055.pdf)

### Abstract

An aggregate signature scheme is a digital signature protocol that enables the aggregation of multiple signatures. Given n signatures on n distinct messages from n different users, it is possible to combine all these signatures into a single, concise
signature. This single signature, along with the n original messages, convinces the verifier that the n users indeed signed their respective n original messages. However, the verifier must have access to all the original messages to perform the
verification, highlighting a potential limitation in terms of accessibility and efficiency. Goyal and Vaikuntanathan introduced the concept of local verification,
which allows the verifier to determine if a specific message m is part of the aggregated signature by only accessing the message m. In this paper, we extend the single-signer locally verifiable aggregate signature scheme initially proposed by Goyal and
Vaikuntanathan, adapting it to a multi-signer context. Our generalization allows the verifier to validate multiple signatures simultaneously using an auxiliary value generated by the LocalOpen algorithm, thereby enhancing verification efficiency.
Furthermore, we integrate this approach into the multi-signature scheme proposed by Boneh, Drijvers, and Neven, demonstrating its broader applicability and potential benefits in complex cryptographic systems.



## 2024/1056

* Title: Shuffle Arguments Based on Subset-Checking
* Authors: Behzad Abdolmaleki, Prastudy Fauzi, Toomas Krips, Janno Siim
* [Permalink](https://eprint.iacr.org/2024/1056)
* [Download](https://eprint.iacr.org/2024/1056.pdf)

### Abstract

Zero-knowledge shuffle arguments are a useful tool for constructing mix-nets which enable anonymous communication. We propose a new shuffle argument using a novel technique that probabilistically checks that each weighted set of input elements
corresponds to some weighted set of output elements, with weights from the same set as the input element weights. We achieve this using standard discrete log assumptions and the shortest integer solution (SIS) assumption. Our shuffle argument has prover
and verifier complexity linear in the size of the shuffled set, and communication complexity logarithmic both in the shuffled set size and security parameter.



## 2024/1057

* Title: Password-authenticated Key Exchange and Applications
* Authors: Kristian Gjøsteen
* [Permalink](https://eprint.iacr.org/2024/1057)
* [Download](https://eprint.iacr.org/2024/1057.pdf)

### Abstract

We analyse a two password-authenticated key exchange protocols, a variant of CPace and a protocol related to the well-known SRP protocol. Our security results are tight. The first result gives us some information about trade-offs for design choices in
CPace. The second result provides information about the security of SRP.

Our analysis is done in a new game-based security definition for password-authenticated key exchange. Our definition accomodates arbitrary password sampling methodologies. Our definition also supports modular security analysis, which we illustrate by
giving two example applications of password-authenticated key exchange: password-authenticated secure channels and password-authenticated device authorisation, capturing popular applications of passwords.



## 2024/1058

* Title: Natively Compatible Super-Efficient Lookup Arguments and How to Apply Them
* Authors: Matteo Campanelli, Dario Fiore, Rosario Gennaro
* [Permalink](https://eprint.iacr.org/2024/1058)
* [Download](https://eprint.iacr.org/2024/1058.pdf)

### Abstract

Lookup arguments allow an untrusted prover to commit to a vector $\vec f \in \mathbb{F}^n$ and show that its entries reside in a predetermined table $\vec t \in \mathbb{F}^N$. One of their key applications is to augment general-purpose SNARKs making them
more efficient on subcomputations that are hard to arithmetize. In order for this "augmentation" to work out, a SNARK and a lookup argument should have some basic level of compatibility with respect to the commitment on $\vec f$. However, not all
existing efficient lookup arguments are fully compatible with other efficient general-purpose SNARKs. This incompatibility can for example occur whenever SNARKs use multilinear extensions under the hood (e.g. Spartan) but the lookup argument is
univariate in flavor (e.g. Caulk or $\mathsf{cq}$).

In this paper we discuss how to widen the spectrum of "super-efficient" lookup arguments (where the proving time is independent of the size of the lookup table): we present a new construction inspired by $\mathsf{cq}$and based on multilinear polynomial
encodings (MLE). Our construction is the first lookup argument for any table that is also natively compatible with MLE-based SNARKs at comparable costs with other state-of-the-art lookup arguments, particularly when the large table is unstructured. This
case arises in various applications, such as using lookups to prove that the program in a virtual machine is fetching the right instruction and when proving the correct computation of floating point arithmetic (e.g., in verifiable machine learning).

We also introduce a second more general construction: a compiler that, given any super-efficient lookup argument compatible with univariate SNARKs, converts it into a lookup argument compatible with MLE-based SNARKs with a very small overhead.
Finally, we discuss SNARKs that we can compose with our constructions as well as approaches for this composition to work effectively.



## 2024/1059

* Title: HEProfiler: An In-Depth Profiler of Approximate Homomorphic Encryption Libraries
* Authors: Jonathan Takeshita, Nirajan Koirala, Colin McKechney, Taeho Jung
* [Permalink](https://eprint.iacr.org/2024/1059)
* [Download](https://eprint.iacr.org/2024/1059.pdf)

### Abstract

Fully Homomorphic Encryption (FHE) allows computation on encrypted
data. Various software libraries have implemented the approximate-
arithmetic FHE scheme CKKS, which is highly useful for applications
in machine learning and data analytics; each of these libraries have differing performance and features. It is useful for developers and researchers to learn details about these libraries’ performance and their differences. Some previous work has
profiled FHE and CKKS implementations for this purpose, but these comparisons are limited in their fairness and completeness.

In this article, we compare four major libraries supporting the CKKS
scheme. Working with the maintainers of each of the PALISADE,
Microsoft SEAL, HElib, and HEAAN libraries, we devise methods for fair comparisons of these libraries, even with their widely varied development strategies and library architectures. To show the practical performance of these libraries, we present HEProfiler, a simple and extensible framework
for profiling C++ FHE libraries. Our experimental evaluation is complete in both the scope of tasks tested and metrics evaluated, allowing
us to draw conclusions about the behaviors of different libraries under a
wide range of real-world workloads. This is the first work-giving experimental comparisons of different bootstrapping-capable CKKS libraries.



## 2024/1060

* Title: Quirky Interactive Reductions of Knowledge
* Authors: Joseph Johnston
* [Permalink](https://eprint.iacr.org/2024/1060)
* [Download](https://eprint.iacr.org/2024/1060.pdf)

### Abstract

Interactive proofs and arguments of knowledge can be generalized to the concept of interactive reductions of knowledge, where proving knowledge of a witness for one NP language is reduced to proving knowledge of a witness for another NP language. We take
this generalization and specialize it to a class of reductions we refer to as `quirky interactive reductions of knowledge' (or QUIRKs). This name reflects our particular design choices within the broad and diverse world of interactive reduction methods.
A central design choice is allowing the prover to rewind or regress to any previous reduction and repeat it as many times as desired. We prove completeness and extractability properties for QUIRKs. We also offer tools for constructing extraction
algorithms along with several simple examples of usage.



## 2024/1061

* Title: Insta-Pok3r: Real-time Poker on Blockchain
* Authors: Sanjam Garg, Aniket Kate, Pratyay Mukherjee, Rohit Sinha, Sriram Sridhar
* [Permalink](https://eprint.iacr.org/2024/1061)
* [Download](https://eprint.iacr.org/2024/1061.pdf)

### Abstract

We develop a distributed service for generating correlated randomness (e.g. permutations) for multiple parties, where each party’s output is private but publicly verifiable. This service provides users with a low-cost way to play online poker in real-
time, without a trusted party.
Our service is backed by a committee of compute providers, who run a multi-party computation (MPC) protocol to produce an (identity-based) encrypted permutation of a deck of cards, in an offline phase well ahead of when the players’ identities are
known. When the players join, what we call the online phase, they decrypt their designated cards immediately after deriving the identity-based decryption keys, a much simpler computation. In addition, the MPC protocol also generates a publicly-verifiable
proof that the output is a permutation.
In our construction, we introduce a new notion of succinctly verifiable multi-identity based encryption (SVME), which extends the existing notion of verifiable encryption to a multi-identity-based setting, but with a constant sized proof – this may be
of independent interest. We instantiate this for a permutation relation (defined over a small set) along with identity-based encryption, polynomial commitments and succinct proofs – our choices are made to enable a distributed computation when the card
deck is always secret shared. Moreover, we design a new protocol to efficiently generate a secret-sharing of random permutation of a small set, which is run prior to distributed SVME.
Running these protocols offline simplifies the online phase substantially, as parties only derive their identity-specific keys privately via secure channels with the MPC committee, and then decrypt locally to obtain their decks. We provide a rigorous UC-
based formalization in a highly modularized fashion.
Finally, we demonstrate practicality with an implementation that shows that for 8 MPC parties, gen- erating a secret publicly-verifiable permutation of 64 cards takes under 3 seconds, while accessing cards for a player takes under 0.3 seconds.



## 2024/1062

* Title: Compact Key Function Secret Sharing with Non-linear Decoder
* Authors: Chandan Kumar, Sikhar Patranabis, Debdeep Mukhopadhyay
* [Permalink](https://eprint.iacr.org/2024/1062)
* [Download](https://eprint.iacr.org/2024/1062.pdf)

### Abstract

We present a variant of Function Secret Sharing (FSS) schemes tailored for point, comparison, and interval functions, featuring compact key sizes at the expense of additional comparison. While existing FSS constructions are primarily geared towards $2$-
party scenarios, exceptions such as the work by Boyle et al. (Eurocrypt 2015) and Riposte (S&P 2015) have introduced FSS schemes for $p$-party scenarios ($p \geq 3$). This paper aims to achieve the most compact $p$-party FSS key size to date. We achieve
a noteworthy reduction in key size, a $2^p$-factor decrease compared to state-of-the-art FSS constructions (including computationally efficient constructions using symmetric-key primitives) of distributed point function (DPF). Compared to the previous
public-key-based FSS design for DPF, we also get a key size reduction equal to a $2^{n/2}$-sized row vector, where $2^n$ is the domain size of the point function. This reduction in key size comes at the cost of a required comparison operation by the
decoder (hence called a non-linear decoder), a departure from prior schemes. In $p$-party scenarios, our construction outperforms existing FSS constructions in key size, remaining on par with Riposte in evaluation time and showing significant improvement
over Boyle et al.


[continued in next message]

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