## In this issue

1. [2024/216] Rate-1 Fully Local Somewhere Extractable Hashing ...
2. [2024/561] SQIAsignHD: SQIsignHD Adaptor Signature
3. [2024/614] Non-interactive Blind Signatures from Lattices
4. [2024/615] Subverting Cryptographic Protocols from A Fine- ...
5. [2024/616] $\mathsf{Cougar}$: Cubic Root Verifier Inner ...
6. [2024/617] Lattice-Based Succinct Mercurial Functional ...
7. [2024/618] Efficient KZG-based Univariate Sum-check and Lookup ...
8. [2024/619] BPDTE: Batch Private Decision Tree Evaluation via ...
9. [2024/620] New SAT-based Model for Quantum Circuit Decision ...
10. [2024/621] How to Lose Some Weight - A Practical Template ...
11. [2024/622] Deep Selfish Proposing in Longest-Chain Proof-of- ...
12. [2024/623] Complete group law for genus 2 Jacobians on ...
13. [2024/624] POKE: A Framework for Efficient PKEs, Split KEMs, ...
14. [2024/625] Interactive Threshold Mercurial Signatures and ...
15. [2024/626] Exponential Quantum Speedup for the Traveling ...
16. [2024/627] Distributed & Scalable Oblivious Sorting and Shuffling
17. [2024/628] MUSEN: Aggregatable Key-Evolving Verifiable Random ...
18. [2024/629] Unconditional correctness of recent quantum ...
19. [2024/630] Conditional disclosure of secrets with quantum ...
20. [2024/631] BackMon: IC Backside Tamper Detection using On-Chip ...
21. [2024/632] Further Investigations on Nonlinear Complexity of ...
22. [2024/633] Vision Mark-32: ZK-Friendly Hash Function Over ...
23. [2024/634] NTRU-based FHE for Larger Key and Message Space
24. [2024/635] Organizing Records for Retrieval in Multi- ...
25. [2024/636] Regev Factoring Beyond Fibonacci: Optimizing Prefactors
26. [2024/637] Towards Permissionless Consensus in the Standard ...
27. [2024/638] A note on ``a lightweight mutual and transitive ...
28. [2024/639] Computational Attestations of Polynomial Integrity ...
29. [2024/640] On Proving Pairings
30. [2024/641] Rondo: Scalable and Reconfiguration-Friendly ...
31. [2024/642] GraphOS: Towards Oblivious Graph Processing
32. [2024/643] Key-Homomorphic and Aggregate Verifiable Random ...
33. [2024/644] Jumping for Bernstein-Yang Inversion
34. [2024/645] Toward Independent Key Encryption based on Q-Problem
35. [2024/646] Efficient Quantum Algorithm for SUBSET-SUM Problem
36. [2024/647] Weightwise (almost) perfectly balanced functions ...
37. [2024/648] Encrypted KNN Implementation on Distributed Edge ...
38. [2024/649] Sphinx-in-the-Head: Group Signatures from Symmetric ...
39. [2024/650] Hash-based Direct Anonymous Attestation
40. [2024/651] A New Hash-based Enhanced Privacy ID Signature Scheme
41. [2024/652] Compact and Secure Zero-Knowledge Proofs for ...

## 2024/216

* Title: Rate-1 Fully Local Somewhere Extractable Hashing from DDH
* Authors: Pedro Branco, Nico Döttling, Akshayaram Srinivasan, Riccardo Zanotto
* [Permalink](https://eprint.iacr.org/2024/216)
* [Download](https://eprint.iacr.org/2024/216.pdf)

### Abstract

Somewhere statistically binding (SSB) hashing allows us to sample a special hashing key such that the digest statistically binds the input at $m$ secret locations. This hash function is said to be somewhere extractable (SE) if there is an additional
trapdoor that allows the extraction of the input bits at the $m$ locations from the digest.

Devadas, Goyal, Kalai, and Vaikuntanathan (FOCS 2022) introduced a variant of somewhere extractable hashing called rate-1 fully local SE hash functions. The rate-1 requirement states that the size of the digest is $m + \mathsf{poly}(\lambda)$ (where
$\lambda$ is the security parameter). The fully local property requires that for any index $i$, there is a "very short" opening showing that $i$-th bit of the hashed input is equal to $b$ for some $b \in \{0,1\}$. The size of this opening is required to
be independent of $m$ and in particular, this means that its size is independent of the size of the digest. Devadas et al. gave such a construction from Learning with Errors (LWE).

In this work, we give a construction of a rate-1 fully local somewhere extractable hash function from Decisional Diffie-Hellman (DDH) and BARGs. Under the same assumptions, we give constructions of rate-1 BARG and RAM SNARG with partial input
soundness whose proof sizes are only matched by prior constructions based on LWE.



## 2024/561

* Title: SQIAsignHD: SQIsignHD Adaptor Signature
* Authors: Farzin Renan, Péter Kutas
* [Permalink](https://eprint.iacr.org/2024/561)
* [Download](https://eprint.iacr.org/2024/561.pdf)

### Abstract

Adaptor signatures can be viewed as a generalized form of the standard digital signature schemes where a secret randomness is hidden within a signature. Adaptor signatures are a recent cryptographic primitive and are becoming an important tool for
blockchain applications such as cryptocurrencies to reduce on-chain costs, improve fungibility, and contribute to off-chain forms of payment in payment-channel networks, payment-channel hubs, and atomic swaps. However, currently used adaptor signature
constructions are vulnerable to quantum adversaries due to Shor's algorithm. In this work, we introduce $\mathsf{SQIAsignHD}$, a new quantum-resistant adaptor signature scheme based on isogenies of supersingular elliptic curves, using SQIsignHD - as the
underlying signature scheme - and exploiting the idea of the artificial orientation on the supersingular isogeny Diffie-Hellman key exchange protocol, SIDH, as the underlying hard relation. We, furthermore, show that our scheme is secure in the Quantum
Random Oracle Model (QROM).



## 2024/614

* Title: Non-interactive Blind Signatures from Lattices
* Authors: Foteini Baldimtsi, Jiaqi Cheng, Rishab Goyal, Aayush Yadav
* [Permalink](https://eprint.iacr.org/2024/614)
* [Download](https://eprint.iacr.org/2024/614.pdf)

### Abstract

Blind signatures enable a receiver to obtain signatures on messages of its choice without revealing any message to the signer. Round-optimal blind signatures are designed as a two-round interactive protocol between a signer and receiver. Coincidentally,
the choice of message is not important in many applications, and is routinely set as a random (unstructured) message by a receiver.
With the goal of designing more efficient blind signatures for such applications, Hanzlik (Eurocrypt '23) introduced a new variant called non-interactive blind signatures (NIBS). These allow a signer to asynchronously generate partial signatures for any
recipient such that only the intended recipient can extract a blinded signature for a random message. This bypasses the two-round barrier for traditional blind signatures, yet enables many known applications.
Hanzlik provided new practical designs for NIBS from bilinear pairings. In this work, we investigate efficient NIBS with post-quantum security. We design the first practical NIBS, as well as non-interactive partially blind signatures called tagged NIBS,
from lattice-based assumptions. We also propose a new generic paradigm for NIBS from circuit-private leveled homomorphic encryption achieving optimal-sized signatures (i.e., same as any non-blind signature). Finally, we propose new enhanced security
properties for NIBS, that could be of practical and theoretical interest.



## 2024/615

* Title: Subverting Cryptographic Protocols from A Fine-Grained Perspective - A Case Study on 2-Party ECDSA
* Authors: Jialiu Cheng, Yi Wang, Rongmao Chen, Xinyi Huang
* [Permalink](https://eprint.iacr.org/2024/615)
* [Download](https://eprint.iacr.org/2024/615.pdf)

### Abstract

The revelations of Edward Snowden in 2013 rekindled concerns within the cryptographic community regarding the potential subversion of cryptographic systems. Bellare et al. (CRYPTO'14) introduced the notion of Algorithm Substitution Attacks (ASAs), which
aim to covertly leak sensitive information by undermining individual cryptographic primitives. In this work, we delve deeply into the realm of ASAs against protocols built upon cryptographic primitives. In particular, we revisit the existing ASA model
proposed by Berndt et al. (AsiaCCS'22), providing a more fine-grained perspective. We introduce a novel ASA model tailored for protocols, capable of capturing a wide spectrum of subversion attacks. Our model features a modular representation of subverted
parties within protocols, along with fine-grained definitions of undetectability. To illustrate the practicality of our model, we applied it to Lindell's two-party ECDSA protocol (CRYPTO'17), unveiling a range of ASAs targeting the protocol's parties
with the objective of extracting secret key shares. Our work offers a comprehensive ASA model suited to cryptographic protocols, providing a useful framework for understanding ASAs against protocols.



## 2024/616

* Title: $\mathsf{Cougar}$: Cubic Root Verifier Inner Product Argument under Discrete Logarithm Assumption
* Authors: Hyeonbum Lee, Seunghun Paik, Hyunjung Son, Jae Hong Seo
* [Permalink](https://eprint.iacr.org/2024/616)
* [Download](https://eprint.iacr.org/2024/616.pdf)

### Abstract

An inner product argument (IPA) is a cryptographic primitive used to construct a zero-knowledge proof (ZKP) system, which is a notable privacy-enhancing technology. We propose a novel efficient IPA called $\mathsf{Cougar}$. $\mathsf{Cougar}$ features
cubic root verifier and logarithmic communication under the discrete logarithm (DL) assumption. At Asiacrypt2022, Kim et al. proposed two square root verifier IPAs under the DL assumption. Our main objective is to overcome the limitation of square root
complexity in the DL setting. To achieve this, we combine two distinct square root IPAs from Kim et al.: one with pairing ($\mathsf{Protocol3}$) and one without pairing ($\mathsf{Protocol4}$). To construct $\mathsf{Cougar}$, we first revisit $\mathsf{
Protocol4}$ and reconstruct it to make it compatible with the proof system for the homomorphic commitment scheme. Next, we utilize $\mathsf{Protocol3}$ as the proof system for the reconstructed $\mathsf{Protocol4}$. Furthermore, we provide a soundness
proof for $\mathsf{Cougar}$ in the DL assumption.



## 2024/617

* Title: Lattice-Based Succinct Mercurial Functional Commitment for Circuits: Definitions and Constructions
* Authors: Hongxiao Wang, Siu-Ming Yiu, Yanmin Zhao, Zoe L. Jiang, Min Xie
* [Permalink](https://eprint.iacr.org/2024/617)
* [Download](https://eprint.iacr.org/2024/617.pdf)

### Abstract

Vector commitments gain a lot of attention because of their wide usage in applications such as blockchain and accumulator. Mercurial vector commitments and mercurial functional commitments (MFC), as significant variants of VC, are the central techniques
to construct more advanced cryptographic primitives such as zero-knowledge set and zero-knowledge functional elementary database (ZK-FEDB).
However, the current MFC only supports linear functions, limiting its application, i.e. building the ZK-FEDB that only supports linear function queries. Besides, to our best knowledge, the existing MFC and ZK-FEDBs, including the one proposed by Zhang
and Deng (ASIACRYPT '23) using RSA accumulators, are all in the group model and cannot resist the attack of quantum computers.

To break these limitations, we formalize the first system model and security model of MFC for circuits. Then, we target some specific properties of a new falsifiable assumption, i.e. the $\mathsf{BASIS}$ assumption proposed by Wee and Wu (EUROCRYPT '23)
to construct the first lattice-based succinct mercurial functional commitment for circuits. To the application, we show that our constructions can be used to build the first lattice-based ZK-FEDB directly within the existing generic framework.



## 2024/618

* Title: Efficient KZG-based Univariate Sum-check and Lookup Argument
* Authors: Yuncong Zhang, Shi-Feng Sun, Dawu Gu
* [Permalink](https://eprint.iacr.org/2024/618)
* [Download](https://eprint.iacr.org/2024/618.pdf)

### Abstract

We propose a novel KZG-based sum-check scheme, dubbed $\mathsf{Losum}$, with optimal efficiency. Particularly, its proving cost is one multi-scalar-multiplication of size $k$---the number of non-zero entries in the vector, its verification cost is one
pairing plus one group scalar multiplication, and the proof consists of only one group element.

Using $\mathsf{Losum}$ as a component, we then construct a new lookup argument, named $\mathsf{Locq}$, which enjoys a smaller proof size and a lower verification cost compared to the state of the arts $\mathsf{cq}$, $\mathsf{cq}$+ and $\mathsf{cq}$++.
Specifically, the proving cost of $\mathsf{Locq}$ is comparable to $\mathsf{cq}$, keeping the advantage that the proving cost is independent of the table size after preprocessing. For verification, $\mathsf{Locq}$ costs four pairings, while $\mathsf{cq}$,
$\mathsf{cq}$+ and $\mathsf{cq}$++ require five, five and six pairings, respectively. For proof size, a $\mathsf{Locq}$ proof consists of four $\mathbb{G}_1$ elements and one $\mathbb{G}_2$ element; when instantiated with the BLS12-381 curve, the proof
size of $\mathsf{Locq}$ is $2304$ bits, while $\mathsf{cq}$, $\mathsf{cq}$+ and $\mathsf{cq}$++ have $3840$, $3328$ and $2944$ bits, respectively. Moreover, $\mathsf{Locq}$ is zero-knowledge as $\mathsf{cq}$+ and $\mathsf{cq}$++, whereas $\mathsf{cq}$ is
not. $\mathsf{Locq}$ is more efficient even compared to the non-zero-knowledge (and more efficient) versions of $\mathsf{cq}$+ and $\mathsf{cq}$++.



## 2024/619

* Title: BPDTE: Batch Private Decision Tree Evaluation via Amortized Efficient Private Comparison
* Authors: Huiqiang Liang, Haining Lu, Geng Wang
* [Permalink](https://eprint.iacr.org/2024/619)
* [Download](https://eprint.iacr.org/2024/619.pdf)

### Abstract

Machine learning as a service requires the client to trust the server and provide its own private information to use this service. Usually, clients may worry that their private data is being collected by server without effective supervision, and the
server also aims to ensure proper management of the user data to foster the advancement of its services. In this work, we focus on private decision tree evaluation (PDTE) which can alleviates such privacy concerns associated with classification tasks
using decision tree. After the evaluation, except for some hyperparameters, the client only receives the classification results from the server, while the server learns nothing.

Firstly, we propose three amortized efficient private comparison algorithms: TECMP, RDCMP, and CDCMP, which are based on the leveled homomorphic encryption. They are non-interactive, high precision (up to 26624-bit), many-to-many, and output expressive,
achieving an amortized cost of less than 1 ms under 32-bit, which is an order of magnitude faster than the state-of-the-art. Secondly, we propose three batch PDTE schemes using this private comparison: TECMP-PDTE, RDCMP-PDTE, and CDCMP-PDTE. Due to the
batch operations, we utilized a clear rows relation (CRR) algorithm, which obfuscates the position and classification results of the different row data. Finally, in decision tree exceeding 1000 nodes under 16-bit each, the amortized runtime of TECMP-PDTE
and RDCMP-PDTE both more than 56$\times$ faster than state-of-the-art, while the TECMP-PDTE with CRR still achieves 14$\times$ speedup. Even in a single row and a tree of fewer than 100 nodes with 64-bit, the TECMP-PDTE maintains a comparable performance
with the current work.



## 2024/620

* Title: New SAT-based Model for Quantum Circuit Decision Problem: Searching for Low-Cost Quantum Implementation
* Authors: Jingwen Chen, Qun Liu, Yanhong Fan, Lixuan Wu, Boyun Li, Meiqin Wang * [Permalink](https://eprint.iacr.org/2024/620)
* [Download](https://eprint.iacr.org/2024/620.pdf)

### Abstract

In recent years, quantum technology has been rapidly developed. As security analyses for symmetric ciphers continue to emerge, many require an evaluation of the resources needed for the quantum circuit implementation of the encryption algorithm. In this
regard, we propose the quantum circuit decision problem, which requires us to determine whether there exists a quantum circuit for a given permutation f using M ancilla qubits and no more than K quantum gates within the circuit depth D. Firstly, we
investigate heuristic algorithms and classical SAT-based models in previous works, revealing their limitations in solving the problem. Hence, we innovatively propose an improved SAT-based model incorporating three metrics of quantum circuits. The model
enables us to find the optimal quantum circuit of an arbitrary 3 or 4-bit S-box under a given optimization goal based on SAT solvers, which has proved the optimality of circuits constructed by the tool, LIGHTER-R. Then, by combining different criteria in
the model, we find more compact quantum circuit implementations of S-boxes such as RECTANGLE and GIFT. For GIFT S-box, our model provides the optimal quantum circuit that only requires 8 gates with a depth of 31. Furthermore, our model can be generalized
to linear layers and improve the previous SAT-based model proposed by Huang et al. in ASIACRYPT 2022 by adding the criteria on the number of qubits and the circuit depth.



## 2024/621

* Title: How to Lose Some Weight - A Practical Template Syndrome Decoding Attack
* Authors: Sebastian Bitzer, Jeroen Delvaux, Elena Kirshanova, Sebastian Maaßen, Alexander May, Antonia Wachter-Zeh
* [Permalink](https://eprint.iacr.org/2024/621)
* [Download](https://eprint.iacr.org/2024/621.pdf)

### Abstract

We study the hardness of the Syndrome Decoding problem, the base of most code-based cryptographic schemes, such as Classic McEliece, in the presence of side-channel information. We use ChipWhisperer equipment to perform a template attack on Classic
McEliece running on an ARM Cortex-M4, and accurately classify the Hamming weights of consecutive 32-bit blocks of the secret error vector. With these weights at hand, we optimize Information Set Decoding algorithms. Technically, we show how to speed up
information set decoding via a dimension reduction, additional parity-check equations, and an improved information set search, all derived from the Hamming weight information.

Consequently, using our template attack, we can practically recover an error vector in dimension n=2197 in a matter of seconds. Without side-channel information, such an instance has a complexity of around 88 bit.
We also estimate how our template attack affects the security of the proposed McEliece parameter sets. Roughly speaking, even an error-prone leak of our Hamming weight information leads for n=3488 to a security drop of 89 bits.



## 2024/622

* Title: Deep Selfish Proposing in Longest-Chain Proof-of-Stake Protocols
* Authors: Roozbeh Sarenche, Svetla Nikova, Bart Preneel
* [Permalink](https://eprint.iacr.org/2024/622)
* [Download](https://eprint.iacr.org/2024/622.pdf)

### Abstract

It has been shown that the selfish mining attack enables a miner to achieve an unfair relative revenue, posing a threat to the progress of longest-chain blockchains. Although selfish mining is a well-studied attack in the context of Proof-of-Work
blockchains, its impact on the longest-chain Proof-of-Stake (LC-PoS) protocols needs yet to be addressed. This paper involves both theoretical and implementation-based approaches to analyze the selfish proposing attack in the LC-PoS protocols. We discuss
how factors such as the nothing-at-stake phenomenon and the proposer predictability in PoS protocols can make the selfish proposing attack in LC-PoS protocols more destructive compared to selfish mining in PoW. In the first part of the paper, we use
combinatorial tools to theoretically assess the selfish proposer’s block ratio in simplistic LC-PoS environments and under simplified network connection. However, these theoretical tools or classical MDP-based approaches cannot be applied to analyze
the selfish proposing attack in real-world and more complicated LC-PoS environments. To overcome this issue, in the second part of the paper, we employ deep reinforcement learning techniques to find the near-optimal strategy of selfish proposing in more
sophisticated protocols. The tool implemented in the paper can help us analyze the selfish proposing attack across diverse blockchain protocols with different reward mechanisms, predictability levels, and network conditions.



## 2024/623

* Title: Complete group law for genus 2 Jacobians on Jacobian coordinates
* Authors: Elif Ozbay Gurler, Huseyin Hisil
* [Permalink](https://eprint.iacr.org/2024/623)
* [Download](https://eprint.iacr.org/2024/623.pdf)

### Abstract

This manuscript provides complete, inversion-free, and explicit group law formulas in Jacobian coordinates for the genus 2 hyperelliptic curves of the form $y^2 = x^5 + a_3 x^3 + a_2 x^2 + a_1 x + a_0$ over a field $K$ with $char(K) \ne 2$. The formulas
do not require the use of polynomial arithmetic operations such as resultant, mod, or gcd computations but only operations in $K$.



## 2024/624

* Title: POKE: A Framework for Efficient PKEs, Split KEMs, and OPRFs from Higher-dimensional Isogenies
* Authors: Andrea Basso
* [Permalink](https://eprint.iacr.org/2024/624)
* [Download](https://eprint.iacr.org/2024/624.pdf)

### Abstract

We introduce a new framework, POKE, to build cryptographic protocols from irrational isogenies using higher-dimensional representations. The framework enables two parties to manipulate higher-dimensional representations of isogenies to efficiently
compute their pushforwards, and ultimately to obtain a shared secret.

We provide three constructions based on POKE: the first is a PKE protocol, which is one of the most compact post-quantum PKEs and possibly the most efficient isogeny-based PKE to date. We then introduce a validation technique to ensure the correctness of
uniSIDH public keys: by combining the validation method with a POKE-based construction, we obtain a split KEM, a primitive that generalizes NIKEs and can be used to instantiate a post-quantum version of the Signal's X3DH protocol. The third construction
builds upon the split KEM and its validation method to obtain a round-optimal verifiable OPRF. It is the first such construction that does not require more than $\lambda$ isogeny computations, and it is significantly more compact and more efficient than
all other isogeny-based OPRFs.



## 2024/625

* Title: Interactive Threshold Mercurial Signatures and Applications
* Authors: Masaya Nanri, Octavio Perez Kempner, Mehdi Tibouchi, Masayuki Abe
* [Permalink](https://eprint.iacr.org/2024/625)
* [Download](https://eprint.iacr.org/2024/625.pdf)

### Abstract

Equivalence class signatures allow a controlled form of malleability based on equivalence classes defined over the message space. As a result, signatures can be publicly randomized and adapted to a new message representative in the same equivalence class.
Notably, security requires that an adapted signature-message pair looks indistinguishable from a random signature-message pair in the space of valid signatures for the new message representative. Together with the decisional Diffie-Hellman assumption,
this yields an unlinkability notion (class-hiding), making them a very attractive building block for privacy-preserving primitives.

Mercurial signatures are an extension of equivalence class signatures that allow malleability for the key space. Unfortunately, the most efficient construction to date suffers a severe limitation that limits their application: only a weak form of public
key class-hiding is supported. In other words, given knowledge of the original signing key and randomization of the corresponding public key, it is possible to identify whether they are related.

In this work, we put forth the notion of interactive threshold mercurial signatures and show how they help to overcome the above-mentioned limitation. Moreover, we present constructions in the two-party and multi-party settings, assuming at least one
honest signer. We also discuss related applications, including blind signatures, multi-signatures, and threshold ring signatures. To showcase the practicality of our approach, we implement the proposed constructions, comparing them against related
alternatives.



## 2024/626

* Title: Exponential Quantum Speedup for the Traveling Salesman Problem
* Authors: Anant Sharma, Nupur Deshpande, Sanchita Ghosh, Sreetama Das, Shibdas Roy
* [Permalink](https://eprint.iacr.org/2024/626)
* [Download](https://eprint.iacr.org/2024/626.pdf)

### Abstract

The traveling salesman problem is the problem of finding out the shortest route in a network of cities, that a salesman needs to travel to cover all the cities, without visiting the same city more than once. This problem is known to be $NP$-hard with a
brute-force complexity of $O(N^N)$ or $O(N^{2N})$ for $N$ number of cities. This problem is equivalent to finding out the shortest Hamiltonian cycle in a given graph, if at least one Hamiltonian cycle exists in it. Quantum algorithms for this problem
typically provide with a quadratic speedup only, using Grover's search, thereby having a complexity of $O(N^{N/2})$ or $O(N^N)$. We present a bounded-error quantum polynomial-time (BQP) algorithm for solving the problem, providing with an exponential
speedup. The overall complexity of our algorithm is $O(N^3\log(N)\kappa/\epsilon + 1/\epsilon^3)$, where the errors $\epsilon$ are $O(1/{\rm poly}(N))$, and $\kappa$ is the not-too-large condition number of the matrix encoding all Hamiltonian cycles.



## 2024/627

* Title: Distributed & Scalable Oblivious Sorting and Shuffling
* Authors: Nicholas Ngai, Ioannis Demertzis, Javad Ghareh Chamani, Dimitrios Papadopoulos
* [Permalink](https://eprint.iacr.org/2024/627)
* [Download](https://eprint.iacr.org/2024/627.pdf)

### Abstract

Existing oblivious systems offer robust security by concealing memory access patterns, but they encounter significant scalability and performance challenges. Recent efforts to enhance the practicality of these systems involve embedding oblivious
computation, e.g., oblivious sorting and shuffling, within Trusted Execution Environments (TEEs). For instance, oblivious sort has been heavily utilized: in Oblix (S&P'18), when oblivious indexes are created and accessed; in Snoopy's high-throughput
oblivious key-value (SOSP'21) during initialization and when the input requests are deduplicated and prepared for delivery; in Opaque (NSDI'17) for all the proposed oblivious SQL operators; in the state-of-the-art non-foreign key oblivious join approach (
PVLDB'20). Additionally, oblivious sort/shuffle find applications in Signal's commercial solution for contact discovery, anonymous Google's Key Transparency, Searchable Encryption, software monitoring, and differentially private federated learning with
user privacy.

In this work, we address the scalability bottleneck of oblivious sort and shuffle by re-designing these approaches to achieve high efficiency in distributed multi-enclave environments. First, we propose a multi-threaded bitonic sort optimized for the
distributed setting, making it the most performant oblivious sort for small number of enclaves (up to 4). For larger numbers of enclaves, we propose a novel oblivious bucket sort, which improves data locality and network consumption and outperforms our
optimized distributed bitonic-sort by up to 5-6x. To the best of our knowledge, these are the first distributed oblivious TEE-based sorting solutions. For reference, we are able to sort 2 GiB of data in 1 second and 128 GiB in 53.4 seconds in a multi-
enclave test. A fundamental building block of our oblivious bucket-sort is an oblivious shuffle that improves the prior state-of-the-art result (CCS'22) by up to 9.5x in the distributed multi-enclave setting---interestingly it is better by 10% even in
the single-enclave/multi-thread setting.



## 2024/628

* Title: MUSEN: Aggregatable Key-Evolving Verifiable Random Functions and Applications
* Authors: Bernardo David, Rafael Dowsley, Anders Konring, Mario Larangeira
* [Permalink](https://eprint.iacr.org/2024/628)
* [Download](https://eprint.iacr.org/2024/628.pdf)

### Abstract

A Verifiable Random Function (VRF) can be evaluated on an input by a prover who holds a secret key, generating a pseudorandom output and a proof of output validity that can be verified using the corresponding public key. VRFs are a central building block
of committee election mechanisms that sample parties to execute tasks in cryptographic protocols, e.g. generating blocks in a Proof-of-Stake (PoS) blockchain or executing a round of MPC protocols. We propose the notion, and a matching construction, of an
Aggregatable Key-Evolving VRF (A-KE-VRF) with the following extra properties: 1. Aggregation: combining proofs for several VRF evaluations of different inputs under different secret keys into a single constant size proof; 2. Key-Evolving: preventing
adversaries who corrupt a party (learning their secret key) from ``forging'' proofs of past VRF evaluations. As an immediate application, we improve on the block size of PoS blockchains and on the efficiency of Proofs of Proof-of-Stake (PoPoS).
Furthermore, the A-KE-VRF notion allows us to construct Encryption to the Future (EtF) and Authentication from the Past (AfP) schemes with a Key-Evolving property, which provides forward security. An EtF scheme allows for sending a message to a party
who is randomly selected to execute a role in the future, while an AfP scheme allows for this party to authenticate their messages as coming from a past execution of this role. These primitives are essential for realizing the YOSO MPC Framework (CRYPTO'
21).



## 2024/629

* Title: Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms
* Authors: Cédric Pilatte
* [Permalink](https://eprint.iacr.org/2024/629)
* [Download](https://eprint.iacr.org/2024/629.pdf)

### Abstract

In 1994, Shor introduced his famous quantum algorithm to factor integers and compute discrete logarithms in polynomial time. In 2023, Regev proposed a multi-dimensional version of Shor's algorithm that requires far fewer quantum gates. His algorithm
relies on a number-theoretic conjecture on the elements in $(\mathbb{Z}/N\mathbb{Z})^{\times}$ that can be written as short products of very small prime numbers. We prove a version of this conjecture using tools from analytic number theory such as zero-
density estimates. As a result, we obtain an unconditional proof of correctness of this improved quantum algorithm and of subsequent variants.



## 2024/630

* Title: Conditional disclosure of secrets with quantum resources
* Authors: Vahid R. Asadi, Kohdai Kuroiwa, Debbie Leung, Alex May, Sabrina Pasterski, Chris Waddell
* [Permalink](https://eprint.iacr.org/2024/630)
* [Download](https://eprint.iacr.org/2024/630.pdf)

### Abstract


[continued in next message]

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