[continued from previous message]

Another contribution of our paper, is in defining and studying share conversion for evolving secret sharing schemes. In such a schemes, recently introduced by Komargodski et al. (IEEE ToIT'18), the number of parties is not bounded apriori, and
every party receives a share as it arrives, which never changes in the sequel. Our impossibility results have implications to the evolving setting as well. Interestingly, that unlike the standard setting, there is no maximum or minimum in a broad class
of evolving schemes, even without any restriction on the share size.
Finally, we show that, generally, there is no conversion between additive schemes over different fields, however by degrading to statistical security, it may be possible to create convertible schemes.



## 2024/1782

* Title: The Battery Insertion Attack: Is Periodic Pseudo-randomization Sufficient for Beacon Privacy?
* Authors: Liron David, Avinatan Hassidim, Yossi Matias, Moti Yung
* [Permalink](https://eprint.iacr.org/2024/1782)
* [Download](https://eprint.iacr.org/2024/1782.pdf)

### Abstract

In this paper, we investigate whether the privacy mechanism of periodically changing the pseudorandom identities of Bluetooth Low Energy (BLE) beacons is sufficient to ensure privacy.

We consider a new natural privacy notion for BLE broadcasting beacons which we call ``Timed-sequence- indistinguishability'' of beacons. This new privacy definition is stronger than the well-known indistinguishability, since it considers not just the
advertisements' content, but also the advertisements' broadcasting times which are observable in the physical world.

We then prove that beacons with periodically changing pseudorandom identities do not achieve timed-sequence- indistinguishability. We do this by presenting a novel privacy attack against BLE beacons, which we call the ``Battery Insertion Attack.'' This
new time-based privacy attack can be executed by merely inserting or reinserting the beacon's battery at the adversary's chosen time. We performed this attack against an actually deployed beacon.

To mitigate the ``Battery Insertion Attack'' and other attacks associated with periodic signaling, we propose a new countermeasure involving quasi-periodic randomized scheduling of identity changes. We prove that our countermeasure ensures timed-sequence
indistinguishability for beacons, thereby enhancing the beacon's privacy. Additionally, we show how to integrate this countermeasure in the attacked system while essentially preserving its feasibility and utility, which is crucial for practical
industrial adoption.



## 2024/1783

* Title: PriSrv: Privacy-Enhanced and Highly Usable Service Discovery in Wireless Communications
* Authors: Yang Yang, Robert H. Deng, Guomin Yang, Yingjiu Li, HweeHwa Pang, Minming Huang, Rui Shi, Jian Weng
* [Permalink](https://eprint.iacr.org/2024/1783)
* [Download](https://eprint.iacr.org/2024/1783.pdf)

### Abstract

Service discovery is essential in wireless communications. However, existing service discovery protocols provide no or very limited privacy protection for service providers and clients, and they often leak sensitive information (e.g., service type,
client’s identity and mobility pattern), which leads to various network-based attacks (e.g., spoofing, man-in-the-middle, identification and tracking). In this paper, we propose a private service discovery protocol, called PriSrv, which allows a
service provider and a client to respectively specify a fine-grained authentication policy that the other party must satisfy before a connection is established. PriSrv consists of a private service broadcast phase and an anonymous mutual authentication
phase with bilateral control, where the private information of both parties is hidden beyond the fact that a mutual match to the respective authentication policy occurred. As a core component of PriSrv, we introduce the notion of anonymous credential-
based matchmaking encryption (ACME), which exerts dual-layer matching in one step to simultaneously achieve bilateral flexible policy control, selective attribute disclosure and multi-show unlinkability. As a building block of ACME, we design a fast
anonymous credential (FAC) scheme to provide constant size credentials and efficient show/verification mechanisms, which is suitable for privacy-enhanced and highly usable service discovery in wireless networks. We present a concrete PriSrv protocol that
is interoperable with popular wireless communication protocols, such as Wi-Fi Extensible Authentication Protocol (EAP), mDNS, BLE and Airdrop, to offer privacy-enhanced protection. We present formal security proof of our protocol and evaluate its
performance on multiple hardware platforms: desktop, laptop, mobile phone and Raspberry Pi. PriSrv accomplishes private discovery and secure connection in less than 0.973 s on the first three platforms, and in less than 2.712 s on Raspberry Pi 4B. We
also implement PriSrv into IEEE 802.1X in the real network to demonstrate its practicality.



## 2024/1784

* Title: Fine-Grained Non-Interactive Key-Exchange without Idealized Assumptions
* Authors: Yuyu Wang, Chuanjie Su, Jiaxin Pan
* [Permalink](https://eprint.iacr.org/2024/1784)
* [Download](https://eprint.iacr.org/2024/1784.pdf)

### Abstract

In this paper, we study multi-party non-interactive key exchange (NIKE) in the fine-grained setting. More precisely, we propose three multi-party NIKE schemes in three computation models, namely, the bounded parallel-time, bounded time, and bounded
storage models. Their security is based on a very mild assumption (e.g., NC1 ⊊ ⊕L/poly) or even without any complexity assumption. This improves the recent work of Afshar, Couteau, Mahmoody, and Sadeghi (EUROCRYPT 2023) that requires idealized
assumptions, such as random oracles or generic groups.
Additionally, we show that all our constructions satisfy a natural desirable property that we refer to as extendability, and we give generic transformations from extendable multi-party NIKE to multi-party identity-based NIKEs in the fine-grained settings.



## 2024/1785

* Title: A General Quantum Duality for Representations of Groups with Applications to Quantum Money, Lightning, and Fire
* Authors: John Bostanci, Barak Nehoran, Mark Zhandry
* [Permalink](https://eprint.iacr.org/2024/1785)
* [Download](https://eprint.iacr.org/2024/1785.pdf)

### Abstract

Aaronson, Atia, and Susskind [Aaronson et al., 2020] established that efficiently mapping between quantum states $\ket{\psi}$ and $\ket{\phi}$ is computationally equivalent to distinguishing their superpositions $\frac{1}{\sqrt{2}}(|\psi\rangle + |\phi\
rangle)$ and $\frac{1}{\sqrt{2}}(|\psi\rangle - |\phi\rangle)$. We generalize this insight into a broader duality principle in quantum computation, wherein manipulating quantum states in one basis is equivalent to extracting their value in a
complementary basis. In its most general form, this duality principle states that for a given group, the ability to implement a unitary representation of the group is computationally equivalent to the ability to perform a Fourier subspace extraction from
the invariant subspaces corresponding to its irreducible representations.

Building on our duality principle, we present the following applications:

* Quantum money, which captures quantum states that are verifiable but unclonable, and its stronger variant, quantum lightning, have long resisted constructions based on concrete cryptographic assumptions. While (public-key) quantum money has been
constructed from indistinguishability obfuscation (iO)—an assumption widely considered too strong—quantum lightning has not been constructed from any such assumptions, with previous attempts based on assumptions that were later broken. We present the
first construction of quantum lightning with a rigorous security proof, grounded in a plausible and well-founded cryptographic assumption. We extend Zhandry's construction from Abelian group actions [Zhandry, 2024] to non-Abelian group actions, and
eliminate Zhandry's reliance on a black-box model for justifying security. Instead, we prove a direct reduction to a computational assumption—the pre-action security of cryptographic group actions. We show how these group actions can be realized with
various instantiations, including with the group actions of the symmetric group implicit in the McEliece cryptosystem.

* We provide an alternative quantum money and lightning construction from one-way homomorphisms, showing that security holds under specific conditions on the homomorphism. Notably, our scheme exhibits the remarkable property that four distinct security
notions—quantum lightning security, security against both worst-case cloning and average-case cloning, and security against preparing a specific canonical state—are all equivalent.

* Quantum fire captures the notion of a samplable distribution on quantum states that are efficiently clonable, but not efficiently telegraphable, meaning they cannot be efficiently encoded as classical information. These states can be spread like fire,
provided they are kept alive quantumly and do not decohere.
The only previously known construction relied on a unitary quantum oracle, whereas we present the first candidate construction of quantum fire in the plain model.



## 2024/1786

* Title: Black-Box Timed Commitments from Time-Lock Puzzles
* Authors: Hamza Abusalah, Gennaro Avitabile
* [Permalink](https://eprint.iacr.org/2024/1786)
* [Download](https://eprint.iacr.org/2024/1786.pdf)

### Abstract

A Timed Commitment (TC) with time parameter $t$ is hiding for time at most $t$, that is, commitments can be force-opened by any third party within time $t$. In addition to various cryptographic assumptions, the security of all known TC schemes relies on
the sequentiality assumption of repeated squarings in hidden-order groups. The repeated squaring assumption is therefore a security bottleneck.

In this work, we give a black-box construction of TCs from any time-lock puzzle (TLP) by additionally relying on one-way permutations and collision-resistant hashing.

Currently, TLPs are known from (a) the specific repeated squaring assumption, (b) the general (necessary) assumption on the existence of worst-case non-parallelizing languages and indistinguishability obfuscation, and (c) any iteratively sequential
function and the hardness of the circular small-secret LWE problem. The latter admits a plausibly post-quantum secure instantiation.

Hence, thanks to the generality of our transform, we get i) the first TC whose timed security is based on the the existence of non-parallelizing languages and ii) the first TC that is plausibly post-quantum secure.

We first define quasi publicly-verifiable TLPs (QPV-TLPs) and construct them from any standard TLP in a black-box manner without relying on any additional assumptions. Then, we devise a black-box commit-and-prove system to transform any QPV-TLPs into a
TC.



## 2024/1787

* Title: An Efficient and Secure Boolean Function Evaluation Protocol
* Authors: Sushmita Sarkar, Vikas Srivastava, Tapaswini Mohanty, Nibedita Kundu, Sumit Kumar Debnath
* [Permalink](https://eprint.iacr.org/2024/1787)
* [Download](https://eprint.iacr.org/2024/1787.pdf)

### Abstract

Boolean functions play an important role in designing and analyzing many cryptographic systems, such as block ciphers, stream ciphers, and hash functions, due to their unique cryptographic properties such as nonlinearity, correlation immunity, and
algebraic properties. The secure evaluation of Boolean functions or Secure Boolean Evaluation (SBE) is an important area of research. SBE allows parties to jointly compute Boolean functions without exposing their private inputs. SBE finds applications in
privacy-preserving protocols and secure multi-party computations. In this manuscript, we present an efficient and generic two-party protocol
(namely $\textsf{BooleanEval}$) for the secure evaluation of Boolean functions by utilizing a 1-out-of-2 Oblivious Transfer (OT) as a building block. $\textsf{BooleanEval}$ only employs XOR operations as the core computational step, thus making it
lightweight and fast. Unlike other lightweight state-of-the-art designs of SBE, $\textsf{BooleanEval}$ avoids the use of additional cryptographic primitives, such as hash functions and commitment schemes to reduce the computational overhead.



## 2024/1788

* Title: Advanced Transparency System
* Authors: Yuxuan Sun, Yuncong Hu, Yu Yu
* [Permalink](https://eprint.iacr.org/2024/1788)
* [Download](https://eprint.iacr.org/2024/1788.pdf)

### Abstract

In contemporary times, there are many situations where users need to verify that their information is correctly retained by servers. At the same time, servers need to maintain transparency logs. Many algorithms have been designed to address this problem.
For example, Certificate Transparency (CT) helps track certificates issued by Certificate Authorities (CAs), while CONIKS aims to provide key transparency for end users. However, these algorithms often suffer from either high append time or imbalanced
inclusion-proof cost and consistency-proof cost. To find an optimal solution, we constructed two different but similar authenticated data structures tailored to two different lookup protocols. We propose ATS (Advanced Transparency System), which uses
only linear storage cost to reduce append time and balances the time costs for both servers and users. When addressing the value-lookup problem, this system allows servers to append user information in constant time and enables radical-level inclusion
proof and consistency proof. For the key transparency problem, the system requires logarithmic time complexity for the append operation and offers acceptable inclusion proof and consistency proof.



## 2024/1789

* Title: Stealth and Beyond: Attribute-Driven Accountability in Bitcoin Transactions
* Authors: Alberto Maria Mongardini, Daniele Friolo, Giuseppe Ateniese
* [Permalink](https://eprint.iacr.org/2024/1789)
* [Download](https://eprint.iacr.org/2024/1789.pdf)

### Abstract

Bitcoin enables decentralized, pseudonymous transactions, but balancing privacy with accountability remains a challenge. This paper introduces a novel dual accountability mechanism that enforces both sender and recipient compliance in Bitcoin
transactions. Senders are restricted to spending Unspent Transaction Outputs (UTXOs) that meet specific criteria, while recipients must satisfy legal and ethical requirements before receiving funds. We enhance stealth addresses by integrating compliance
attributes, preserving privacy while ensuring policy adherence. Our solution introduces a new cryptographic primitive, Identity-Based Matchmaking Signatures (IB-MSS), which supports streamlined auditing. Our approach is fully compatible with existing
Bitcoin infrastructure and does not require changes to the core protocol, preserving both privacy and decentralization while enabling transaction auditing and compliance.



## 2024/1790

* Title: Revisiting subgroup membership testing on pairing-friendly curves via the Tate pairing
* Authors: Yu Dai, Debiao He, Dmitrii Koshelev, Cong Peng, Zhijian Yang
* [Permalink](https://eprint.iacr.org/2024/1790)
* [Download](https://eprint.iacr.org/2024/1790.pdf)

### Abstract

In 2023, Koshelev proposed an efficient method for subgroup membership testing on a list of non-pairing-friendly curves via the Tate pairing. In fact, this method can also be applied to certain pairing-friendly curves, such as the BLS and BW13 families,
at a cost of two small Tate pairings. In this paper, we revisit Koshelev's method to enhance its efficiency for these curve families. First, we present explicit formulas for computing the two small Tate pairings. Compared to the original formulas, the
new versions offer shorter Miller iterations and reduced storage requirements. Second, we provide a high-speed software implementation on a 64-bit processor. Our results demonstrate that the new method is up to $62.0\%$ and $22.4\%$ faster than the
state-of-the-art on the BW13-310 and BLS24-315 curves, respectively, while being $14.1\%$ slower on BLS12-381. When precomputation is utilized, our method achieves speed improvements of up to $34.8\%$, $110.6\%$, and $63.9\%$ on the BLS12-381, BW13-310,
and BLS24-315 curves, respectively.



## 2024/1791

* Title: Discrete gaussian sampling for BKZ-reduced basis
* Authors: Amaury Pouly, Yixin Shen
* [Permalink](https://eprint.iacr.org/2024/1791)
* [Download](https://eprint.iacr.org/2024/1791.pdf)

### Abstract

Discrete Gaussian sampling on lattices is a fundamental problem in lattice-based cryptography. In this paper, we revisit the Markov chain Monte Carlo (MCMC)-based Metropolis-Hastings-Klein (MHK) algorithm proposed by Wang and Ling
and study its complexity under the Geometric Series Assuption (GSA) when the given basis is BKZ-reduced. We give experimental evidence that the GSA is accurate in this context, and we give a very simple approximate formula for the complexity of the
sampler that is accurate over a large range of parameters and easily computable. We apply our results to the dual attack on LWE of [Pouly and Shen 2024] and significantly improve the complexity estimates of the attack. Finally, we provide some results of
independent interest on the Gaussian mass of a random $q$-ary lattices.



## 2024/1792

* Title: Towards Explainable Side-Channel Leakage: Unveiling the Secrets of Microarchitecture
* Authors: Ischa Stork, Vipul Arora, Łukasz Chmielewski, Ileana Buhan
* [Permalink](https://eprint.iacr.org/2024/1792)
* [Download](https://eprint.iacr.org/2024/1792.pdf)

### Abstract

We explore the use of microbenchmarks, small assembly code snippets, to detect microarchitectural side-channel leakage in CPU implementations. Specifically, we investigate the effectiveness of microbenchmarks in diagnosing the predisposition to side-
channel leaks in two commonly used RISC-V cores: Picorv32 and Ibex. We propose a new framework that involves diagnosing side-channel leaks, identifying leakage points, and constructing leakage profiles to understand the underlying causes. We apply our
framework to several realistic case studies that test our framework for explaining side-channel leaks and showcase the subtle interaction of data via order-reducing leaks.



## 2024/1793

* Title: On the Jordan-Gauss graphs and new multivariate public keys
* Authors: Vasyl Ustimenko, Tymoteusz Chojecki, Aneta Wróblewska
* [Permalink](https://eprint.iacr.org/2024/1793)
* [Download](https://eprint.iacr.org/2024/1793.pdf)

### Abstract

We suggest two families of multivariate public keys defined over arbitrary finite commutative ring \(K\) with unity. The first one has quadratic multivariate public rule, this family is an obfuscation of previously defined cryptosystem defined in terms
of well known algebraic graphs \(D(n, K)\) with the partition sets isomorphic to \(K^n\). Another family of cryptosystems uses the combination of Eulerian transformation of \(K[x_1, x_2, \ldots, x_n]\) sending each variable \(x_i\) to a monomial term
with the quadratic encryption map of the first cryptosystem. The resulting map has unbounded degree and the density \(O(n^4)\) like the cubic multivariate map. The space of plaintexts of the second cryptosystem is the variety \((K^*)^n\) and the space of
ciphertexts is the affine space \(K^n\).



## 2024/1794

* Title: How Much Public Randomness Do Modern Consensus Protocols Need?
* Authors: Joseph Bonneau, Benedikt Bünz, Miranda Christ, Yuval Efron
* [Permalink](https://eprint.iacr.org/2024/1794)
* [Download](https://eprint.iacr.org/2024/1794.pdf)

### Abstract

Modern blockchain-based consensus protocols
aim for efficiency (i.e., low communication and round complexity) while maintaining security against adaptive adversaries.
These goals are usually achieved using a public randomness beacon to select roles for each participant.
We examine to what extent this randomness is necessary.
Specifically, we provide tight bounds on the amount of entropy a Byzantine Agreement protocol must consume from a beacon in order to enjoy efficiency and adaptive security.
We first establish that no consensus protocol can simultaneously be efficient, be adaptively secure, and use $O(\log n)$ bits of beacon entropy. We then show this bound is tight and, in fact, a trilemma by presenting three consensus protocols that
achieve any two of these three properties.



## 2024/1795

* Title: How Fast Does the Inverse Walk Approximate a Random Permutation?
* Authors: Tianren Liu, Angelos Pelecanos, Stefano Tessaro, Vinod Vaikuntanathan
* [Permalink](https://eprint.iacr.org/2024/1795)
* [Download](https://eprint.iacr.org/2024/1795.pdf)

### Abstract

For a finite field $\mathbb{F}$ of size $n$, the (patched) inverse permutation $\operatorname{INV}: \mathbb{F} \to \mathbb{F}$ computes the inverse of $x$ over $\mathbb{F}$ when $x\neq 0$ and outputs $0$ when $x=0$, and the $\operatorname{ARK}_K$ (for
AddRoundKey) permutation adds a fixed constant $K$ to its input, i.e., $$\operatorname{INV}(x) = x^{n-2} \hspace{.1in} \mbox{and} \hspace{.1in} \operatorname{ARK}_K(x) = x + K \;.$$
We study the process of alternately applying the $\operatorname{INV}$ permutation followed by a random linear permutation $\operatorname{ARK}_K$, which is a random walk over the alternating (or symmetric) group that we call the inverse walk.

We show both lower and upper bounds on the number of rounds it takes for this process to approximate a random permutation over $\mathbb{F}$. We show that $r$ rounds of the inverse walk over the field of size $n$ with $$r = \Theta\left(n\log^2 n + n\log n\
log \frac{1}{\epsilon}\right)$$ rounds generates a permutation that is $\epsilon$-close (in variation distance) to a uniformly random even permutation (i.e. a permutation from the alternating group $A_{n}$). This is tight, up to logarithmic factors.

Our result answers an open question from the work of Liu, Pelecanos, Tessaro and Vaikuntanathan (CRYPTO 2023) by providing a missing piece in their proof of $t$-wise independence of (a variant of) AES. It also constitutes a significant improvement on a
result of Carlitz (Proc. American Mathematical Society, 1953) who showed a reachability result: namely, that every even permutation can be generated eventually by composing $\operatorname{INV}$ and $\operatorname{ARK}$. We show a tight convergence result,
namely a tight quantitative bound on the number of rounds to reach a random (even) permutation.



## 2024/1796

* Title: Isogeny interpolation and the computation of isogenies from higher dimensional representations
* Authors: David Jao, Jeanne Laflamme
* [Permalink](https://eprint.iacr.org/2024/1796)
* [Download](https://eprint.iacr.org/2024/1796.pdf)

### Abstract

The Supersingular Isogeny Diffie-Hellman (SIDH) scheme is a public key cryptosystem that was submitted to the National Institute of Standards and Technology's competition for the standardization of post-quantum cryptography protocols. The private key in
SIDH consists of an isogeny whose degree is a prime power. In July 2022, Castryck and Decru discovered an attack that completely breaks the scheme by recovering Bob's secret key, using isogenies between higher dimensional abelian varieties to interpolate
and reconstruct the isogenies comprising the SIDH private key. The original attack applies in theory to any prime power degree, but the implementation accompanying the original attack required one of the SIDH keys involved in a key exchange to have
degree equal to a power of $2$. An implementation of the power of $3$ case was published subsequently by Decru and Kunzweiler. However, despite the passage of several years, nobody has published any implementations for prime powers other than $2$ or $3$,
and for good reason --- the necessary higher dimensional isogeny computations rapidly become more complicated as the base prime increases. In this paper, we provide for the first time a fully general isogeny interpolation implementation that works for
any choice of base prime, and provide timing benchmarks for various combinations of SIDH base prime pairs. We remark that the technique of isogeny interpolation now has constructive applications as well as destructive applications, and that our methods
may open the door to increased flexibility in constructing isogeny-based digital signatures and cryptosystems.



## 2024/1797

* Title: FLock: Robust and Privacy-Preserving Federated Learning based on Practical Blockchain State Channels
* Authors: Ruonan Chen, Ye Dong, Yizhong Liu, Tingyu Fan, Dawei Li, Zhenyu Guan, Jianwei Liu, Jianying Zhou
* [Permalink](https://eprint.iacr.org/2024/1797)
* [Download](https://eprint.iacr.org/2024/1797.pdf)

### Abstract

\textit{Federated Learning} (FL) is a distributed machine learning paradigm that allows multiple clients to train models collaboratively without sharing local data. Numerous works have explored security and privacy protection in FL, as well as its
integration with blockchain technology. However, existing FL works still face critical issues. \romannumeral1) It is difficult to achieving \textit{poisoning robustness} and \textit{data privacy} while ensuring high \textit{model accuracy}. Malicious
clients can launch \textit{poisoning attacks} that degrade the global model. Besides, aggregators can infer private data from the gradients, causing \textit{privacy leakages}. Existing privacy-preserving poisoning defense FL solutions suffer from
decreased model accuracy and high computational overhead. \romannumeral2) Blockchain-assisted FL records iterative gradient updates on-chain to prevent model tampering, yet existing schemes are not compatible with practical blockchains and incur high
costs for maintaining the gradients on-chain. Besides, incentives are overlooked, where unfair reward distribution hinders the sustainable development of the FL community. In this work, we propose FLock, a robust and privacy-preserving FL scheme based on
practical blockchain state channels. First, we propose a lightweight secure \textit{Multi-party Computation} (MPC)-friendly robust aggregation method through quantization, median, and Hamming distance, which could resist poisoning attacks against up to $<
50\%$ malicious clients. Besides, we propose communication-efficient Shamir's secret sharing-based MPC protocols to protect data privacy with high model accuracy. Second, we utilize blockchain off-chain state channels to achieve immutable model records
and incentive distribution. FLock achieves cost-effective compatibility with practical cryptocurrency platforms, e.g. Ethereum, along with fair incentives, by merging the secure aggregation into a multi-party state channel. In addition, a pipelined \
textit{Byzantine Fault-Tolerant} (BFT) consensus is integrated where each aggregator can reconstruct the final aggregated results. Lastly, we implement FLock and the evaluation results demonstrate that FLock enhances robustness and privacy, while
maintaining efficiency and high model accuracy. Even with 25 aggregators and 100 clients, FLock can complete one secure aggregation for ResNet in $2$ minutes over a WAN. FLock successfully implements secure aggregation with such a large number of
aggregators, thereby enhancing the fault tolerance of the aggregation.



## 2024/1798

* Title: Quantum One-Time Protection of any Randomized Algorithm
* Authors: Sam Gunn, Ramis Movassagh
* [Permalink](https://eprint.iacr.org/2024/1798)
* [Download](https://eprint.iacr.org/2024/1798.pdf)

### Abstract

The meteoric rise in power and popularity of machine learning models dependent on valuable training data has reignited a basic tension between the power of running a program locally and the risk of exposing details of that program to the user. At the
same time, fundamental properties of quantum states offer new solutions to data and program security that can require strikingly few quantum resources to exploit, and offer advantages outside of mere computational run time. In this work, we demonstrate
such a solution with quantum one-time tokens.

A quantum one-time token is a quantum state that permits a certain program to be evaluated exactly once. One-time security guarantees, roughly, that the token cannot be used to evaluate the program more than once. We propose a scheme for building quantum
one-time tokens for any randomized classical program, which include generative AI models. We prove that the scheme satisfies an interesting definition of one-time security as long as outputs of the classical algorithm have high enough min-entropy, in a
black box model.

Importantly, the classical program being protected does not need to be implemented coherently on a quantum computer. In fact, the size and complexity of the quantum one-time token is independent of the program being protected, and additional quantum
resources serve only to increase the security of the protocol. Due to this flexibility in adjusting the security, we believe that our proposal is parsimonious enough to serve as a promising candidate for a near-term useful demonstration of quantum
computing in either the NISQ or early fault tolerant regime.



## 2024/1799

* Title: Consensus Under Adversary Majority Done Right
* Authors: Srivatsan Sridhar, Ertem Nusret Tas, Joachim Neu, Dionysis Zindros, David Tse
* [Permalink](https://eprint.iacr.org/2024/1799)
* [Download](https://eprint.iacr.org/2024/1799.pdf)

### Abstract

A spectre is haunting consensus protocols—the spectre of adversary majority. The literature is inconclusive, with possibilities and impossibilities running abound. Dolev and Strong in 1983 showed an early possibility for up to 99% adversaries. Yet, we
have known impossibility results for adversaries above 1/2 in synchrony, and above 1/3 in partial synchrony. What gives? It is high time that we pinpoint the culprit of this confusion: the critical role of the modeling details of clients. Are the clients
sleepy or always-on? Are they silent or communicating? Can validators be sleepy too? We systematize models for consensus across four dimensions (sleepy/always-on clients, silent/communicating clients, sleepy/always-on validators, and synchrony/partial-
synchrony), some of which are new, and tightly characterize the achievable safety and liveness resiliences with matching possibilities and impossibilities for each of the sixteen models. To this end, we unify folklore and earlier results, and fill gaps
left in the literature with new protocols and impossibility theorems.

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