[continued from previous message]

In this paper, we present an improved framework for proving query bounds in the Quantum Random Oracle Model (QROM) for algorithms with both quantum and classical query interfaces, where the classical input is partially controlled by the adversary. By
extending existing techniques, we develop a method to bound the progress an adversary can make with such partial-control classical queries. While this framework is applicable to different hash function properties, we decided to demonstrate the impact of
the new techniques by giving an analysis of the multi-target extended target collision resistance property (m-eTCR). This new approach allows us to achieve an improved bound that significantly reduces the required function key size. Our proof is tight in
terms of query complexity and has significant implications for cryptographic applications, especially for signature schemes in the hash & sign paradigm, enabling more efficient instantiations with reduced salt sizes and smaller signature lengths. For an
example of multiple signatures aggregation, we achieve a signature size of 30 kB smaller.



## 2025/634

* Title: Cryptography based on 2D Ray Tracing
* Authors: Sneha Mohanty, Christian Schindelhauer
* [Permalink](https://eprint.iacr.org/2025/634)
* [Download](https://eprint.iacr.org/2025/634.pdf)

### Abstract

We introduce a novel symmetric key cryptographic scheme involving a light ray's interaction with a 2D cartesian coordinate setup, several smaller boxes within this setup, of either reflection or refraction type and $1^{st}$, $2^{nd}$ or $3^{rd}$ degree
polynomial curves inside each of these smaller boxes. We also incorporate boolean logic gates of types XOR, NOT-Shift and Permutation which get applied to the light ray after each interaction with a reflecting or refracting polynomial curve. This
alternating interaction between Optical gates (polynomial curves) and Non-optical gates creates a complex and secure cryptographic system. Furthermore, we design and launch customized attacks on our cryptographic system and discuss the robustness of it
against these.



## 2025/635

* Title: Towards Scalable YOSO MPC via Packed Secret-Sharing
* Authors: Daniel Escudero, Elisaweta Masserova, Antigoni Polychroniadou
* [Permalink](https://eprint.iacr.org/2025/635)
* [Download](https://eprint.iacr.org/2025/635.pdf)

### Abstract

The YOSO (You Only Speak Once) model, introduced by Gentry et al. (CRYPTO 2021), helps to achieve strong security guarantees in cryptographic protocols for distributed settings, like blockchains, with large number of parties. YOSO protocols typically
employ smaller anonymous committees to execute individual rounds of the protocol instead of having all parties execute the entire protocol. After completing their tasks, parties encrypt protocol messages for the next anonymous committee and erase their
internal state before publishing ciphertexts, thereby enhancing security in dynamically changing environments.

In this work, we consider the problem of secure multi-party computation (MPC), a fundamental problem in cryptography and distributed computing. We assume honest majority among the committee members, and work in the online-offline, i.e., preprocessing,
setting.
In this context, we present the first YOSO MPC protocol where efficiency---measured as communication complexity---improves as the number of parties increases. Specifically, for $0<\epsilon<1/2$ and an adversary corrupting $t<n(\frac{1}{2}-\epsilon)$
out of $n$ parties, our MPC protocol exhibits enhanced scalability as $n$ increases, where the online phase communication becomes independent of $n$.
Prior YOSO MPC protocols considered $t$ as large as $(n-1)/2$, but a significant hurdle persisted in obtaining YOSO MPC with communication that does not scale linearly with the number of committee members, a challenge that is exagerbated when the
committee size was large per YOSO's requirements.
We show that, by considering a small ``gap'' of $\epsilon>0$, the sizes of the committees are only marginally increased, while online communication is significantly reduced.


Furthermore, we explicitly consider fail-stop adversaries, i.e., honest participants who may inadvertently fail due to reasons such as denial of service or software/hardware errors. In prior YOSO work, these adversaries were grouped with fully malicious
parties. Adding explicit support for them allows us to achieve even better scalability.



## 2025/636

* Title: Impossible Differential Attack on SAND-64
* Authors: Nobuyuki Sugio
* [Permalink](https://eprint.iacr.org/2025/636)
* [Download](https://eprint.iacr.org/2025/636.pdf)

### Abstract

SAND is an AND-RX-based lightweight block cipher proposed by Chen et al. There are two variants of SAND, namely SAND-64 and SAND-128, due to structural differences. In this paper, we search for impossible differential distinguishers of SAND-64 using the
Constraint Programming (CP) and reveal 56 types of impossible differential distinguishers up to 11 rounds. Furthermore, we demonstrate a key recovery attack on 17-round SAND-64. The complexities for the attack require $2^{56}$ data, $2^{127}$ encryptions,
and $2^{60}$ bytes of memory, respectively. Although this result currently achieves the best attack on round-reduced SAND-64, this attack does not threaten the security of SAND-64 against impossible differential attack.



## 2025/637

* Title: A Study of Blockchain Consensus Protocols
* Authors: Shymaa M. Arafat
* [Permalink](https://eprint.iacr.org/2025/637)
* [Download](https://eprint.iacr.org/2025/637.pdf)

### Abstract

When Nakamoto invented Bitcoin, the first generation of cryptocurrencies followed it in applying POW (Proof of Work) consensus mechanism; due to its excessive energy consumption and heavy carbon footprints, new innovations evolved like Proof of Space,
POS (Proof of Stake), and a lot more with many variants for each. Furthermore, the emergence of more blockchain applications and kinds beyond just cryptocurrencies needed more consensus mechanisms that is optimized to fit requirements of each application
or blockchain kind; examples range from IoT (Internet of Things) blockchains for sustainability applications that often use variants of BFT (Byzantine Fault Tolerance) algorithm, and consensus needed to relay transactions and/or assets between different
blockchains in interoperability solutions. Previous studies concentrated on surveying and/or proposing different blockchain consensus rules, on a specific consensus issue like attacks, randomization, or on deriving theoretical results. Starting from
discussing most important theoretical results, this paper tries to gather and organize all significant existing material about consensus in the blockchain world explaining design challenges, tradeoffs and research areas. We realize that the topic could
fit for a complete textbook, so we summarize the basic concepts and support with tables and appendices. Then we highlight some case examples from interoperability solutions to show how flexible and wide the design space is to fit both general and special
purpose systems. The aim is to provide researchers with a comprehensive overview of the topic, along with the links to go deeper into every detail.



## 2025/638

* Title: Round-Efficient Adaptively Secure Threshold Signatures with Rewinding * Authors: Yanbo Chen
* [Permalink](https://eprint.iacr.org/2025/638)
* [Download](https://eprint.iacr.org/2025/638.pdf)

### Abstract

A threshold signature scheme allows distributing a signing key to $n$ users, such that any $t$ of them can jointly sign, but any $t-1$ cannot. It is desirable to prove \emph{adaptive security} of threshold signature schemes, which considers adversaries
that can adaptively corrupt honest users even after interacting with them. For a class of signatures that relies on security proofs with rewinding, such as Schnorr signatures, proving adaptive security entails significant challenges.

This work proposes two threshold signature schemes that are provably adaptively secure with rewinding proofs. Our proofs are solely in the random oracle model (ROM), without relying on the algebraic group model (AGM).

- We give a 3-round scheme based on the algebraic one-more discrete logarithm (AOMDL) assumption. The scheme outputs a standard Schnorr signature.

- We give a 2-round scheme based on the DL assumption. Signatures output by the scheme contain one more scalar than a Schnorr signature.

We follow the recent work by Katsumata, Reichle, and Takemure (Crypto 2024) that proposed the first threshold signature scheme with a rewinding proof of full adaptive security. Their scheme is a 5-round threshold Schnorr scheme based on the DL assumption.
Our results significantly improve the round complexity.

Katsumata et al.'s protocol can be viewed as applying a masking technique to Sparkle, a threshold Schnorr signature scheme by Crites, Komlo, and Maller (Crypto 2023). This work shows wider applications of the masking technique. Our first scheme is
obtained by masking FROST, a threshold Schnorr protocol by Komlo and Goldberg (SAC 2020). The second scheme is obtained by masking a threshold version of HBMS, a multi-signature scheme by Bellare and Dai (Asiacrypt 2021).

Katsumata et al. masked Sparkle at the cost of 2 additional rounds. Our main insight is that this cost varies across schemes, especially depending on how to simulate signing in the security proofs. The cost is 1 extra round for our first scheme, and is 0
for our second scheme.



## 2025/639

* Title: Cryptomania v.s. Minicrypt in a Quantum World
* Authors: Longcheng Li, Qian Li, Xingjian Li, Qipeng Liu
* [Permalink](https://eprint.iacr.org/2025/639)
* [Download](https://eprint.iacr.org/2025/639.pdf)

### Abstract

We prove that it is impossible to construct perfect-complete quantum public-key encryption (QPKE) with classical keys from quantumly secure one-way functions (OWFs) in a black-box manner, resolving a long-standing open question in quantum cryptography.

Specifically, in the quantum random oracle model (QROM), no perfect-complete QPKE scheme with classical keys, and classical/quantum ciphertext can be secure. This improves the previous works which require either unproven conjectures or imposed
restrictions on key generation algorithms. This impossibility even extends to QPKE with quantum public key if the public key can be uniquely determined by the secret key, and thus is tight to all existing QPKE constructions.



## 2025/640

* Title: Multi-Party Private Set Operations from Predicative Zero-Sharing
* Authors: Minglang Dong, Yu Chen, Cong Zhang, Yujie Bai, Yang Cao
* [Permalink](https://eprint.iacr.org/2025/640)
* [Download](https://eprint.iacr.org/2025/640.pdf)

### Abstract

Typical protocols in the multi-party private set operations (MPSO) setting enable $m > 2$ parties to perform certain secure computation on the intersection or union of their private sets, realizing a very limited range of MPSO functionalities. Most works
in this field focus on just one or two specific functionalities, resulting in a large variety of isolated schemes and a lack of a unified framework in MPSO research. In this work, we present an MPSO framework, which allows $m$ parties, each holding a set,
to securely compute any set formulas (arbitrary compositions of a finite number of binary set operations, including intersection, union and difference) on their private sets. Our framework is highly versatile and can be instantiated to accommodate a
broad spectrum of MPSO functionalities. To the best of our knowledge, this is the first framework to achieve such a level of flexibility and generality in MPSO, without relying on generic secure multi-party computation (MPC) techniques.

Our framework exhibits favorable theoretical and practical performance. The computation and communication complexity scale linearly with the set size $n$, and it achieves optimal complexity that is on par with the naive solution for widely used
functionalities, such as multi-party private set intersection (MPSI), MPSI with cardinality output (MPSI-card), and MPSI with cardinality and sum (MPSI-card-sum), in the standard semi-honest model. Furthermore, the instantiations of our framework mainly
from symmetric-key techniques yield efficient protocols for MPSI, MPSI-card, MPSI-card-sum, and multi-party private set union (MPSU), with online performance surpassing or matching the state of the art.

At the technical core of our framework is a newly introduced primitive called predicative zero-sharing. This primitive captures the universality of a number of MPC protocols and is composable. We believe it may be of independent interest.



## 2025/641

* Title: Scalable Non-Fungible Tokens on Bitcoin
* Authors: Jordi Herrera-Joancomartí, Cristina Pérez-Solà, Toni Mateos
* [Permalink](https://eprint.iacr.org/2025/641)
* [Download](https://eprint.iacr.org/2025/641.pdf)

### Abstract

This paper presents a protocol for scaling the creation, management, and trading of non-fungible tokens (NFTs) on Bitcoin by extending bridgeless minting patterns previously used on other blockchains. The protocol leverages on-chain Bitcoin data to
handle all aspects of token ownership, including trading, while integrating a secondary consensus system for minting and optionally modifying token metadata. To minimize its on-chain footprint, the protocol utilizes the OP_RETURN mechanism for ownership
records, while complementary NFT-related actions are stored on the LAOS blockchain. All data remains permanently on-chain, with no reliance on bridges or third-party operators.



## 2025/642

* Title: A Meta-Complexity Characterization of Quantum Cryptography
* Authors: Bruno P. Cavalar, Eli Goldin, Matthew Gray, Peter Hall
* [Permalink](https://eprint.iacr.org/2025/642)
* [Download](https://eprint.iacr.org/2025/642.pdf)

### Abstract

We prove the first meta-complexity characterization of a quantum cryptographic primitive. We show that one-way puzzles exist if and only if there is some quantum samplable distribution of binary strings over which it is hard to approximate Kolmogorov
complexity. Therefore, we characterize one-way puzzles by the average-case hardness of a uncomputable problem. This brings to the quantum setting a recent line of work that characterizes classical cryptography with the average-case hardness of a meta-
complexity problem, initiated by Liu and Pass. Moreover, since the average-case hardness of Kolmogorov complexity over classically polynomial-time samplable distributions characterizes one-way functions, this result poses one-way puzzles as a natural
generalization of one-way functions to the quantum setting. Furthermore, our equivalence goes through probability estimation, giving us the additional equivalence that one-way puzzles exist if and only if there is a quantum samplable distribution over
which probability estimation is hard. We also observe that the oracle worlds of defined by Kretschmer et. al. rule out any relativizing characterization of one-way puzzles by the hardness of a problem in $\mathbf{NP}$ or $\mathbf{QMA}$, which means
that it may not be possible with current techniques to characterize one-way puzzles with another meta-complexity problem.



## 2025/643

* Title: Obfuscation for Deep Neural Networks against Model Extraction: Attack Taxonomy and Defense Optimization
* Authors: Yulian Sun, Vedant Bonde, Li Duan, Yong Li
* [Permalink](https://eprint.iacr.org/2025/643)
* [Download](https://eprint.iacr.org/2025/643.pdf)

### Abstract

Well-trained deep neural networks (DNN), including large
language models (LLM), are valuable intellectual property assets. To defend against model extraction attacks, one of the major ideas proposed in a large body of previous research is obfuscation: splitting the original DNN and storing the components
separately. However, systematically analyzing the methods’ security against various attacks and optimizing the efficiency of defenses are still challenging. In this paper, We propose a taxonomy of model-based extraction attacks, which enables us to
identify vulnerabilities of several existing obfuscation methods. We also propose an extremely efficient model obfuscation method called O2Splitter using trusted execution environment (TEE). The secrets we store in TEE have O(1)-size, i.e., independent
of model size. Although O2Splitter relies on a pseudo-random function to provide a quantifiable guarantee for protection and noise compression, it does not need any complicated training or filtering of the weights. Our comprehensive experiments show that
O2Splitter can mitigate norm-clipping and fine-tuning attacks. Even for
small noise (ϵ = 50), the accuracy of the obfuscated model is close to
random guess, and the tested attacks cannot extract a model with comparable accuracy. In addition, the empirical results also shed light on discovering the relation between DP parameters in obfuscation and the risks of concrete extraction attacks.



## 2025/644

* Title: Attacking at non-harmonic frequencies in screaming-channel attacks
* Authors: Jeremy Guillaume, Maxime Pelcat, Amor Nafkha, Ruben Salvador
* [Permalink](https://eprint.iacr.org/2025/644)
* [Download](https://eprint.iacr.org/2025/644.pdf)

### Abstract

Screaming-channel attacks enable Electromagnetic (EM) Side-Channel Attacks (SCAs) at larger distances due to higher EM leakage energies than traditional SCAs, relaxing the requirement of close access to the victim. This attack can be mounted on devices
integrating Radio Frequency (RF) modules on the same die as digital circuits, where the RF can unintentionally capture, modulate, amplify, and transmit the leakage along with legitimate signals. Leakage results from digital switching activity, so the
hypothesis of previous works was that this leakage would appear at multiples of the digital clock frequency, i.e., harmonics. This work demonstrates that compromising signals appear not only at the harmonics and that leakage at non-harmonics can be
exploited for successful attacks. Indeed, the transformations undergone by the leaked signal are complex due to propagation effects through the substrate and power and ground planes, so the leakage also appears at other frequencies. We first propose two
methodologies to locate frequencies that contain leakage and demonstrate that it appears at non-harmonic frequencies. Then, our experimental results show that screaming-channel attacks at non-harmonic frequencies can be as successful as at harmonics when
retrieving a 16-byte AES key. As the RF spectrum is polluted by interfering signals, we run experiments and show successful attacks in a more realistic, noisy environment where harmonic frequencies are contaminated by multi-path fading and interference.
These attacks at non-harmonic frequencies increase the attack surface by providing attackers with an increased number of potential frequencies where attacks can succeed.



## 2025/645

* Title: GIGA Protocol: Unlocking Trustless Parallel Computation in Blockchains * Authors: Alberto Garoffolo, Dmytro Kaidalov, Roman Oliynykov, Daniele Di Tullio, Mariia Rodinko
* [Permalink](https://eprint.iacr.org/2025/645)
* [Download](https://eprint.iacr.org/2025/645.pdf)

### Abstract

The scalability of modern decentralized blockchain systems is constrained by the requirement that the participating nodes execute the entire chains transactions without the ability to delegate the verification workload across multiple actors trustlessly.
This is further limited by the need for sequential transaction execution and repeated block validation, where each node must re-execute all transactions before accepting blocks, also leading to delayed broadcasting in many architectures.

Consequently, throughput is limited by the capacity of individual nodes, significantly preventing scalability.

In this paper, we introduce GIGA, a SNARK-based protocol that enables trustless parallel execution of transactions, processing non-conflicting operations concurrently, while preserving security guarantees and state consistency. The protocol organizes
transactions into non-conflicting batches which are executed and proven in parallel, distributing execution across multiple decentralized entities. These batch proofs are recursively aggregated into a single succinct proof that validates the entire block.

As a result, the protocol both distributes the execution workload and removes redundant re-execution from the network, significantly improving blockchain throughput while not affecting decentralization.

Performance estimates demonstrate that, under the same system assumptions (e.g., consensus, networking, and virtual machine architecture) and under high degrees of transaction parallelism (i.e., when most transactions operate on disjoint parts of the
state), our protocol may achieve over a 10000x throughput improvement compared to popular blockchain architectures that use sequential execution models, and over a 500x improvement compared to blockchain architectures employing intra-node parallelization
schemes.

Furthermore, our protocol enables a significant increase in transaction computational complexity, unlocking a wide range of use cases that were previously unfeasible on traditional blockchain architectures due to the limited on-chain computational
capacity.

Additionally, we propose a reward mechanism that ensures the economic sustainability of the proving network, dynamically adjusting to computational demand while fostering competition among provers based on cost-efficiency and reliability.



## 2025/646

* Title: Secret-Key PIR from Random Linear Codes
* Authors: Caicai Chen, Yuval Ishai, Tamer Mour, Alon Rosen
* [Permalink](https://eprint.iacr.org/2025/646)
* [Download](https://eprint.iacr.org/2025/646.pdf)

### Abstract

Private information retrieval (PIR) allows to privately read a chosen bit from an $N$-bit database $x$ with $o(N)$ bits of communication. Lin, Mook, and Wichs (STOC 2023) showed that by preprocessing $x$ into an encoded database $\hat x$, it suffices to
access only $polylog(N)$ bits of $\hat x$ per query. This requires $|\hat x|\ge N\cdot polylog(N)$, and prohibitively large server circuit size.

We consider an alternative preprocessing model (Boyle et al. and Canetti et al., TCC 2017), where the encoding $\hat x$ depends on a client's short secret key. In this secret-key PIR (sk-PIR) model we construct a protocol with $O(N^\epsilon)$
communication, for any constant $\epsilon>0$, from the Learning Parity with Noise assumption in a parameter regime not known to imply public-key encryption. This is evidence against public-key encryption being necessary for sk-PIR.

Under a new conjecture related to the hardness of learning a hidden linear subspace of $\mathbb{F}_2^n$ with noise, we construct sk-PIR with similar communication and encoding size $|\hat x|=(1+\epsilon)\cdot N$ in which the server is implemented by a
Boolean circuit of size $(4+\epsilon)\cdot N$. This is the first candidate PIR scheme with such a circuit complexity.



## 2025/647

* Title: Anamorphic Voting: Ballot Freedom Against Dishonest Authorities
* Authors: Rosario Giustolisi, Mohammadamin Rakeei, Gabriele Lenzini
* [Permalink](https://eprint.iacr.org/2025/647)
* [Download](https://eprint.iacr.org/2025/647.pdf)

### Abstract

Electronic voting schemes typically ensure ballot privacy by
assuming that the decryption key is distributed among tallying authorities, preventing any single authority from decrypting a voter’s ballot.
However, this assumption may fail in a fully dishonest environment where
all tallying authorities collude to break ballot privacy.
In this work, we introduce the notion of anamorphic voting, which enables voters to convey their true voting intention to an auditor while
casting an (apparently) regular ballot. We present new cryptographic
techniques demonstrating that several existing voting schemes can support anamorphic voting.



## 2025/648

* Title: HQC Beyond the BSC: Towards Error Structure-Aware Decoding
* Authors: Marco Baldi, Sebastian Bitzer, Nicholas Lilla, Paolo Santini
* [Permalink](https://eprint.iacr.org/2025/648)
* [Download](https://eprint.iacr.org/2025/648.pdf)

### Abstract

In Hamming Quasi-Cyclic (HQC), one of the finalists in the NIST competition for the standardization of post-quantum cryptography, decryption relies on decoding a noisy codeword through a public error-correcting code. The noise vector has a special form
that depends on the secret key (a pair of sparse polynomials). However, the decoder, which is currently employed in HQC, is agnostic to the secret key, operating under the assumption that the error arises from a Binary Symmetric Channel (BSC). In this
paper, we demonstrate that this special noise structure can instead be leveraged to develop more powerful decoding strategies.

We first study the problem from a coding-theoretic perspective. The current code design, which admits a non-zero decryption failure rate, is close to optimal in the setting of a decoder that is agnostic to the error structure. We show that there are code-
decoder pairs with a considerably shorter code length that can guarantee unique decoding by taking the error structure into account. This result is non-constructive, i.e., we do not provide an explicit code construction and it remains open whether
efficient decoding is possible. Nevertheless, it highlights the potential that can be tapped by taking the error structure into account.
We then argue that, in practice, the matter of decoding in HQC can be related to solving an instance of the noisy syndrome decoding problem, in which the parity-check matrix is constituted by the polynomials in the secret key. We show that, using
decoders for Low-Density Parity-Check (LDPC) and Moderate-Density Parity-Check (MDPC) codes, one can significantly reduce the entity of the noise and, de facto, also the Decoding Failure Rate (DFR) of the HQC decoder.

This preliminary study leaves some open questions and problems. While it shows that decoding in HQC can be improved, the modeling of the DFR gets more complicated: even for the basic decoder we propose in this paper, we have not been able to devise a
reliable DFR model. This is likely due to the fact that the decoder structure resembles the iterative nature of LDPC/MDPC decoders, for which devising a reliable DFR estimation is a well-known difficult problem.



## 2025/649

* Title: Guaranteed Termination Asynchronous Complete Secret Sharing with Lower Communication and Optimal Resilience
* Authors: Ying Cai, Chengyi Qin, Mingqiang Wang
* [Permalink](https://eprint.iacr.org/2025/649)
* [Download](https://eprint.iacr.org/2025/649.pdf)

### Abstract

Asynchronous Complete Secret Sharing (ACSS) is a foundational module for asynchronous networks, playing a critical role in cryptography. It is essential for Asynchronous Secure Multi-Party Computation (AMPC) and, with termination, is widely applied in
Validated Asynchronous Byzantine Agreement (VABA) and Asynchronous Distributed Key Generation (ADKG) to support secure distributed systems.
Currently, there are relatively few statistical secure ACSS protocols that can guarantee termination, and their communication complexity is relatively high. To reduce communication complexity, we propose a new multi-receiver signature scheme, ARICP,
which supports linear operations on signatures. Leveraging the ARICP scheme and the properties of symmetric polynomials, we propose an ACSS protocol that ensures termination and optimal resilience ($t < n / 3$) with $\mathcal{O}(n^{2}\kappa$) bits per
sharing. Compared with the best-known result of ACSS protocols that guarantee termination [CP23], the amortized communication complexity of our protocol is reduced by a factor of $\mathcal{O}(n)$.



## 2025/650

* Title: ADC-BE: Optimizing Worst-Case Bandwidth in Broadcast Encryption with Boolean Functions
* Authors: Yadi Zhong
* [Permalink](https://eprint.iacr.org/2025/650)
* [Download](https://eprint.iacr.org/2025/650.pdf)

### Abstract

Recently, Dupin and Abelard proposed a broadcast encryption scheme which outperforms the Complete Subtree-based and Subset Difference broadcast encryption in terms of encryption cost and bandwidth requirement. However, Dupin and Abelard acknowledge that
the worst-case bound for bandwidth requirement of Complete Subtree approach can be reached in their scheme as well. In this paper, we answer the call to further reduce this bandwidth bottleneck. We first provide concrete analysis to show how this worst-
case upper-bound is reached from concrete Boolean functions. Then we present two improved broadcast encryption schemes to significantly reduce this worst-case bandwidth consumption for further optimization of Dupin and Abelard’s technique. Our proposed
approach ADC-BE, composed of two algorithms, AD-BE and AC-BE, can significantly optimize this worst-case complexity from n/2 down to 1 for a system of n users. This is efficient especially for large number of users in the system. Our proposed schemes
combines the algebraic normal form, disjunctive normal form, and conjunctive normal form to optimize a Boolean function to its minimized representation. In addition, our approaches can be made secure against quantum adversaries and are therefore post-
quantum, where both algorithms AD-BE and AC-BE require minimal assumptions based on existence of one-way function.



## 2025/651

* Title: Low-Latency Bootstrapping for CKKS using Roots of Unity
* Authors: Jean-Sébastien Coron, Robin Köstler
* [Permalink](https://eprint.iacr.org/2025/651)
* [Download](https://eprint.iacr.org/2025/651.pdf)

### Abstract

We introduce a new bootstrapping equation for the CKKS homomorphic encryption scheme of approximate numbers. The original bootstrapping approach for CKKS consists in homomorphically evaluating a polynomial that approximates the modular reduction modulo q.
In contrast, our new bootstrapping equation directly embeds the additive group modulo q into the complex roots of unity, which can be evaluated natively in the CKKS scheme. Due to its reduced multiplicative depth, our new bootstrapping equation achieves
a 7x latency improvement for a single slot compared to the original CKKS bootstrapping, though it scales less efficiently when applied to a larger number of slots.



## 2025/652

* Title: MultiCent: Secure and Scalable Centrality Measures on Multilayer Graphs
* Authors: Andreas Brüggemann, Nishat Koti, Varsha Bhat Kukkala, Thomas Schneider
* [Permalink](https://eprint.iacr.org/2025/652)
* [Download](https://eprint.iacr.org/2025/652.pdf)

### Abstract

As real-world networks such as social networks and computer networks are often complex and distributed, modeling them as multilayer graphs is gaining popularity. For instance, when studying social interactions across platforms like LinkedIn, Facebook,
TikTok, and Bluesky, users may be connected on several of these platforms. To identify important nodes/users, the platforms might wish to analyze user interactions using, e.g., centrality measures when accounting for connections across all platforms.
That raises the challenge for platforms to perform such computation while simultaneously protecting their user data to shelter their own business as well as uphold data protection laws. This necessitates designing solutions that allow for performing
secure
computation on a multilayer graph which is distributed among mutually distrusting parties while keeping each party's data hidden.


[continued in next message]

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