[continued from previous message]

* [Download](https://eprint.iacr.org/2024/715.pdf)

### Abstract

The advent of quantum computing technology will compromise many of the current cryptographic algorithms, especially public-key cryptography, which is widely used to protect digital information. Most algorithms on which we depend are used worldwide in
components of many different communications, processing, and storage systems. Once access to practical quantum computers becomes available, all public-key algorithms and associated protocols will be vulnerable to criminals, competitors, and other
adversaries. It is critical to begin planning for the replacement of hardware, software, and services that use public-key algorithms now so that information is protected from future attacks.” [1].
For this purpose, we have developed a new algorithm that contributes to deal with the aforementioned problem. Instead to use a classical scheme of encoding / decoding methods (keys, prime numbers, etc.), our algorithm is rather based on a combination of
functions. Because the cardinality of the set of functions is infinite, it would be impossible for a third party (e.g. a hacker) to decode the secret information transmitted by the sender (Bob) to the receiver (Alice).



## 2024/716

* Title: Unclonable Secret Sharing
* Authors: Prabhanjan Ananth, Vipul Goyal, Jiahui Liu, Qipeng Liu
* [Permalink](https://eprint.iacr.org/2024/716)
* [Download](https://eprint.iacr.org/2024/716.pdf)

### Abstract

Unclonable cryptography utilizes the principles of quantum mechanics to addresses cryptographic tasks that are impossible classically. We introduce a novel unclonable primitive in the context of secret sharing, called unclonable secret sharing (USS). In
a USS scheme, there are $n$ shareholders, each holding a share of a classical secret represented as a quantum state. They can recover the secret once all parties (or at least $t$ parties) come together with their shares. Importantly, it should be
infeasible to copy their own shares and send the copies to two non-communicating parties, enabling both of them to recover the secret.

Our work initiates a formal investigation into the realm of unclonable secret sharing, shedding light on its implications, constructions, and inherent limitations.
** Connections: We explore the connections between USS and other quantum cryptographic primitives such as unclonable encryption and position verification, showing the difficulties to achieve USS in different scenarios.

**Limited Entanglement: In the case where the adversarial shareholders do not share any entanglement or limited entanglement, we demonstrate information-theoretic constructions for USS.

**Large Entanglement: If we allow the adversarial shareholders to have unbounded entanglement resources (and unbounded computation), we prove that unclonable secret sharing is impossible. On the other hand, in the quantum random oracle model where
the adversary can only make a bounded polynomial number of queries, we show a construction secure even with unbounded entanglement.

Furthermore, even when these adversaries possess only a polynomial amount of entanglement resources, we establish that any unclonable secret sharing scheme with a reconstruction function implementable using Cliffords and logarithmically many T-
gates is also unattainable.



## 2024/717

* Title: An Improved Threshold Homomorphic Cryptosystem Based on Class Groups
* Authors: Lennart Braun, Guilhem Castagnos, Ivan Damgård, Fabien Laguillaumie, Kelsey Melissaris, Claudio Orlandi, Ida Tucker
* [Permalink](https://eprint.iacr.org/2024/717)
* [Download](https://eprint.iacr.org/2024/717.pdf)

### Abstract

We present distributed key generation and decryption protocols for an additively homomorphic cryptosystem based on class groups, improving on a similar system proposed by Braun, Damgård, and Orlandi at CRYPTO '23. Our key generation is similarly
constant round but achieves lower communication complexity than the previous work. This improvement is in part the result of relaxing the reconstruction property required of the underlying integer verifiable secret sharing scheme. This eliminates the
reliance on potentially costly proofs of knowledge in unknown order groups. We present a new method to batch zero-knowledge proofs in unknown order groups which strengthens these improvements. We also present a protocol which is proven secure against
adaptive adversaries in the single inconsistent player (SIP) model. Our protocols are secure in the universal composability (UC) framework and provide guaranteed output delivery. We demonstrate the relative efficiency of our techniques by presenting the
running times and communication costs associated with our implementation of the statically secure protocol and provide a direct comparison with alternate state of the art constructions.



## 2024/718

* Title: PAC-Private Algorithms
* Authors: Mayuri Sridhar, Hanshen Xiao, Srinivas Devadas
* [Permalink](https://eprint.iacr.org/2024/718)
* [Download](https://eprint.iacr.org/2024/718.pdf)

### Abstract

Provable privacy typically requires involved analysis and is often associated with unacceptable accuracy loss. While many empirical verification or approximation methods, such as Membership Inference Attacks (MIA) and Differential Privacy Auditing (DPA),
have been proposed, these do not offer rigorous privacy guarantees. In this paper, we apply recently-proposed Probably Approximately Correct (PAC) Privacy to give formal, mechanized, simulation-based proofs for a range of practical, black-box algorithms:
K-Means, Support Vector Machines (SVM), Principal Component Analysis (PCA) and Random Forests. To provide these proofs, we present a new simulation algorithm that efficiently determines anisotropic noise perturbation required for any given level of
privacy. We provide a proof of correctness for this algorithm and demonstrate that anisotropic noise has substantive benefits over isotropic noise.

Stable algorithms are easier to privatize, and we demonstrate privacy amplification resulting from introducing regularization in these algorithms; meaningful privacy guarantees are obtained with small losses in accuracy. We also propose new techniques in
order to canonicalize algorithmic output and convert intractable geometric stability verification into efficient deterministic stability verification. Thorough experiments are included, and we validate our provable adversarial inference hardness against
state-of-the-art empirical attacks.



## 2024/719

* Title: Client-Efficient Online-Offline Private Information Retrieval
* Authors: Hoang-Dung Nguyen, Jorge Guajardo, Thang Hoang
* [Permalink](https://eprint.iacr.org/2024/719)
* [Download](https://eprint.iacr.org/2024/719.pdf)

### Abstract

Private Information Retrieval (PIR) permits clients to query entries from a public database hosted on untrusted servers in a privacy-preserving manner. Traditional PIR model suffers from high computation and/or bandwidth cost due to entire database
processing for privacy. Recently, Online-Offline PIR (OO-PIR) has been suggested to improve the practicality of PIR, where query-independent materials are precomputed beforehand to accelerate online access. While state-of-the-art OO-PIR schemes (e.g., S&
P’24, CRYPTO’23) successfully reduce the online processing overhead to sublinear, they still impose sustainable bandwidth and storage burdens on the client, especially when operating on large databases.
In this paper, we propose Pirex, a new OO-PIR scheme with eminent client performance while maintaining the sublinear server processing efficiency. Specifically, Pirex offers clients with sublinear processing, minimal inbound bandwidth, and low storage
requirements. Our Pirex design is fairly simple yet efficient, where the majority of operations are naturally low-cost and streamlined (e.g., XOR, PRF, modular arithmetic).
We have fully implemented Pirex and evaluated its real-world performance using commodity hardware. Our experimental results demonstrated that Pirex outperforms existing OO-PIR schemes by at least two orders of magnitude. Concretely, with a 1 TB database,
Pirex only takes 0.8s to query a 256-KB entry, compared with 30-220s by the state-of-the-art.



## 2024/720

* Title: MQ maps are not binding - Revisiting Multivariate Blind Signatures
* Authors: Ward Beullens
* [Permalink](https://eprint.iacr.org/2024/720)
* [Download](https://eprint.iacr.org/2024/720.pdf)

### Abstract

In 2017, Petzoldt, Szepieniec, and Mohamed proposed a blind signature scheme, based on multivariate cryptography. This construction has been expanded on by several other works. This short paper shows that their construction is susceptible to an efficient
polynomial-time attack. The problem is that the authors implicitly assumed that for a random multivariate quadratic map $\mathcal{R}:\mathbb{F}_q^m \rightarrow \mathbb{F}_q^m$ and a collision-resistant hash function $H: \{0,1\}^* \rightarrow \mathbb{F}_q^
m$, the function $\mathsf{Com}(m;\mathbf{r}) := H(m) - \mathcal{R}(\mathbf{r})$ is a binding commitment. This paper shows that this is not the case. Given any pair of messages, one can efficiently produce a commitment that opens to both of them. We hope
that by pointing out that multivariate quadratic maps are not binding, similar problems can be avoided in the future.



## 2024/721

* Title: Real-world Universal zkSNARKs are non-malleable
* Authors: Antonio Faonio, Dario Fiore, Luigi Russo
* [Permalink](https://eprint.iacr.org/2024/721)
* [Download](https://eprint.iacr.org/2024/721.pdf)

### Abstract

Simulation extractability is a strong security notion of zkSNARKs that guarantees that an attacker who produces a valid proof must know the corresponding witness, even if the attacker had prior access to proofs generated by other users. Notably,
simulation extractability implies that proofs are non-malleable and is of fundamental importance for applications of zkSNARKs in distributed systems. In this work, we study sufficient and necessary conditions for constructing simulation-extractable
universal zkSNARKs via the popular design approach based on compiling polynomial interactive oracle proofs (PIOP). Our main result is the first security proof that popular universal zkSNARKs, such as PLONK and Marlin, as deployed in the real world, are
simulation-extractable. Our result fills a gap left from previous work (Faonio et al. TCC’23, and Kohlweiss et al. TCC’23) which could only prove the simulation extractability of the “textbook” versions of these schemes and does not capture their
optimized variants, with all the popular optimization tricks in place, that are eventually implemented and deployed in software libraries.



## 2024/722

* Title: Ultrametric integral cryptanalysis
* Authors: Tim Beyne, Michiel Verbauwhede
* [Permalink](https://eprint.iacr.org/2024/722)
* [Download](https://eprint.iacr.org/2024/722.pdf)

### Abstract

A systematic method to analyze \emph{divisibility properties} is proposed.
In integral cryptanalysis, divisibility properties interpolate between bits that sum to zero (divisibility by two) and saturated bits (divisibility by $2^{n - 1}$ for $2^n$ inputs).
From a theoretical point of view, we construct a new cryptanalytic technique that is a non-Archimedean multiplicative analogue of linear cryptanalysis. It lifts integral cryptanalysis to characteristic zero in the sense that, if all quantities are
reduced modulo two, then one recovers the algebraic theory of integral cryptanalysis.
The new technique leads to a theory of trails. We develop a tool based on off-the-shelf solvers that automates the analysis of these trails and use it to show that many integral distinguishers on PRESENT and SIMON are stronger than expected.



## 2024/723

* Title: $\mathsf{OPA}$: One-shot Private Aggregation with Single Client Interaction and its Applications to Federated Learning
* Authors: Harish Karthikeyan, Antigoni Polychroniadou
* [Permalink](https://eprint.iacr.org/2024/723)
* [Download](https://eprint.iacr.org/2024/723.pdf)

### Abstract

Our work aims to minimize interaction in secure computation due to the high cost and challenges associated with communication rounds, particularly in scenarios with many clients. In this work, we revisit the problem of secure aggregation in the single-
server setting where a single evaluation server can securely aggregate client-held individual inputs. Our key contribution is One-shot Private Aggregation ($\mathsf{OPA}$) where clients speak only once (or even choose not to speak) per aggregation
evaluation. Since every client communicates just once per aggregation, this streamlines the management of dropouts and dynamic participation of clients, contrasting with multi-round state-of-the-art protocols for each aggregation.

We initiate the study of $\mathsf{OPA}$ in several ways. First, we formalize the model and present a security definition. Second, we construct $\mathsf{OPA}$ protocols based on class groups, DCR, and LWR assumptions. Third, we demonstrate $\mathsf{OPA}$
with two applications: private stream aggregation and privacy-preserving federated learning. Specifically, $\mathsf{OPA}$ can be used as a key building block to enable privacy-preserving federated learning and critically, where client speaks once. This
is a sharp departure from prior multi-round protocols whose study was initiated by Bonawitz et al. (CCS, 2017). Moreover, unlike the YOSO (You Only Speak Once) model for general secure computation, $\mathsf{OPA}$ eliminates complex committee selection
protocols to achieve adaptive security. Beyond asymptotic improvements, $\mathsf{OPA}$ is practical, outperforming state-of-the-art solutions. We leverage $\mathsf{OPA}$ to develop a streaming variant named $\mathsf{SOPA}$, serving as the building block
for privacy-preserving federated learning. We utilize $\mathsf{SOPA}$ to construct logistic regression classifiers for two datasets.

A new distributed key homomorphic PRF is at the core of our construction of $\mathsf{OPA}$. This key component addresses shortcomings observed in previous works that relied on DDH and LWR in the work of Boneh et al. (CRYPTO, 2013), marking it as an
independent contribution to our work. Moreover, we also present new distributed key homomorphic PRFs based on class groups or DCR or the LWR assumption.

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